15-441 Computer NetworkingHierarchical RoutingSlide 3Intra-AS and Inter-AS routingSlide 5Why different Intra- and Inter-AS routing ?OutlineHistoryChoicesSolution: Distance Vector with PathSnapshot of Routing TableInterconnecting BGP PeersHop-by-hop ModelAS CategoriesSlide 15Policy with BGPExamples of BGP PoliciesBGP Common HeaderBGP MessagesBGP UPDATE MessagePath Selection CriteriaLOCAL PREFAS_PATHCIDR and BGPOptionsSets and SequencesMulti-Exit Discriminator (MED)MEDSlide 29Other AttributesTypical Decision ProcessSlide 32Internal vs. External BGPInternal BGP (I-BGP)Slide 35Link FailuresFailure on an E-BGP LinkFailure on an I-BGP LinkSlide 39Multi-homingMulti-homing to Multiple ProvidersAddress Space from one ISPPitfallsAddress Space from Both ISPsIndependent Address SpaceProblemsRouting Table Size15-441 Computer NetworkingInter-Domain RoutingBGP (Border Gateway Protocol)Lecture #11: 10-02-01 2Hierarchical Routingscale: with 50 million destinations:•can’t store all dest’s in routing tables!•routing table exchange would swamp links! administrative autonomy•internet = network of networks•each network admin may want to control routing in its own networkOur routing study thus far - idealization •all routers identical•network “flat”… not true in practiceLecture #11: 10-02-01 3Hierarchical Routing•aggregate routers into regions, “autonomous systems” (AS)•routers in same AS run same routing protocol•“intra-AS” routing protocol•routers in different AS can run different intra-AS routing protocols•special routers in AS•run intra-AS routing protocol with all other routers in AS•also responsible for routing to destinations outside AS•run inter-AS routing protocol with other gateway routersgateway routersLecture #11: 10-02-01 4Intra-AS and Inter-AS routingGateways:•perform inter-AS routing amongst themselves•perform intra-AS routers with other routers in their ASinter-AS, intra-AS routing in gateway A.cnetwork layerlink layerphysical layerabbaaCABdA.aA.cC.bB.acbcLecture #11: 10-02-01 5Intra-AS and Inter-AS routingHost h2abbaaCABdcA.aA.cC.bB.acbHosth1Intra-AS routingwithin AS AInter-AS routingbetween A and BIntra-AS routingwithin AS BLecture #11: 10-02-01 6Why different Intra- and Inter-AS routing ? Policy: •Inter-AS: admin wants control over how its traffic routed, who routes through its net. •Intra-AS: single admin, so no policy decisions neededScale:•hierarchical routing saves table size, reduced update trafficPerformance: •Intra-AS: can focus on performance•Inter-AS: policy may dominate over performanceLecture #11: 10-02-01 7Outline•External BGP (E-BGP)•Internal BGP (I-BGP)•Multi-HomingLecture #11: 10-02-01 8History•Mid-80s: EGP•Reachability protocol (no shortest path)•Did not accommodate cycles (tree topology)•Evolved when all networks connected to NSF backbone•Result: BGP introduced as routing protocol•Latest version = BGP 4•BGP-4 supports CIDR•Primary objective: connectivity not performanceLecture #11: 10-02-01 9Choices•Link state or distance vector?•No universal metric – policy decisions•Problems with distance-vector:•Bellman-Ford algorithm may not converge•Problems with link state:•Metric used by routers not the same – loops•LS database too large – entire Internet•May expose policies to other AS’sLecture #11: 10-02-01 10Solution: Distance Vector with Path•Each routing update carries the entire path•Loops are detected as follows:•When AS gets route, check if AS already in path•If yes, reject route•If no, add self and (possibly) advertise route further•Advantage:•Metrics are local - AS chooses path, protocol ensures no loopsLecture #11: 10-02-01 11Snapshot of Routing Table CIDR block next hop MED PREF AS PATH*>i12.16.212.0/23 206.157.77.73 10 100 0 3561 6347 6411 i* i 137.39.166.122 10 100 0 1239 6347 6411 i*>i12.16.244.0/22 165.87.33.4 10 100 0 2685 5673 6201 i*>i12.17.10.0/23 157.130.9.110 20 100 0 (65535 65518 65525 65488) 6507 i*>i12.18.74.0/24 157.130.192.14 100 0 7018 11154 i*>i12.18.236.0/23 137.39.166.122 10 100 0 1239 11107 i*>i12.18.240.0/22 137.39.166.122 10 100 0 1239 5650 6188 6188 11741 i* i12.20.66.0/23 206.157.77.73 10 100 0 3561 11589 11589 11589 11589 11589 i*>i 206.157.77.77 10 100 0 3561 11589 11589 11589 11589 11589 i*>i12.20.92.0/24 206.157.77.77 10 100 0 3561 11857 i* i 206.157.77.73 10 100 0 3561 11857 i*>i12.20.166.0/24 165.117.52.233 10 100 0 2548 11235 i* i 157.130.192.14 100 0 7018 11235 iTaken from a UUNet router in Palo AltoLecture #11: 10-02-01 12Interconnecting BGP Peers•BGP uses TCP to connect peers•Advantages:•Simplifies BGP•No need for periodic refresh - routes are valid until withdrawn, or the connection is lost•Incremental updates•Disadvantages•Congestion control on a routing protocol?•Poor interaction during high loadLecture #11: 10-02-01 13Hop-by-hop Model•BGP advertises to neighbors only those routes that it uses•Consistent with the hop-by-hop Internet paradigm•e.g., AS1 cannot tell AS2 to route to other AS’s in a manner different than what AS2 has chosen (need source routing for that)Lecture #11: 10-02-01 14AS Categories•Stub: an AS that has only a single connection to one other AS - carries only local traffic.•Multi-homed: an AS that has connections to more than one AS, but does not carry transit traffic•Transit: an AS that has connections to more than one AS, and carries both transit and local traffic (under certain policy restrictions)Lecture #11: 10-02-01 15AS CategoriesAS1AS3AS2AS1AS2AS3AS1AS2StubMulti-homedTransitLecture #11: 10-02-01 16Policy with BGP•BGP provides capability for enforcing various policies•Policies are not part of BGP: they are provided to BGP as configuration information•BGP enforces policies by choosing paths from multiple alternatives and controlling advertisement to other AS’sLecture #11: 10-02-01 17Examples of BGP Policies•A multi-homed AS refuses to act as transit•Limit path advertisement•A multi-homed AS can become transit for some AS’s•Only advertise paths to some AS’s•An AS can favor or disfavor certain AS’s for traffic transit from itselfLecture #11: 10-02-01 18BGP Common
View Full Document