Interdomain Routing EECS 122: Lecture 11ReviewTodayHierarchical RoutingThe Importance of InterconnectionsInterconnections and CompetitionBig PictureTwo ways to interconnect IP Networks…PeeringTransitBenefits of Transit v/s PeeringMoving from Transit to PeeringName of the Game: ReachabilityBGP in conceptI-BGP and E-BGPBGPSharing routesFour message typesBGP Update MessageIssuesAddressingClass-base AddressingClass-based addresses did not scale wellCurrent Solution: Classless Internet Domain Routing (CIDR)Slide 25Classless Inter-domain Routing AddressesAssigning IP address (Ideally)Advertising a RouteBGP Routing Table ScalingSlide 30BGP: A Path-vector protocolMultihomingMultiexit Discriminators (MEDs)Routing Process OverviewAttribute: Local PreferenceChoosing best routeBGP PoliciesTransit vs. Nontransit ASCustomer-Transit ProblemBGP and PerformanceSlide 41Skitter LegendSlide 43SummaryInterdomain RoutingEECS 122: Lecture 11Department of Electrical Engineering and Computer SciencesUniversity of CaliforniaBerkeleyFebruary 25, 2003Abhay Parekh, EE122 S2003:Updated from Stoica EE122 F20022ReviewABC6785431212101311643213B243613OSPFRIPIGRPBGPIntraDomainIntraDomainIntraDomainIntradomainFormulate the routing problem as a Shortest Path ProblemLink State v/s Distance VectorBoth work reasonably well in a well engineered networkFebruary 25, 2003Abhay Parekh, EE122 S2003:Updated from Stoica EE122 F20023TodayWhy Hierarchical Routing?InterconnectionsAddressingInterdomain RoutingBGPFebruary 25, 2003Abhay Parekh, EE122 S2003:Updated from Stoica EE122 F20024Hierarchical RoutingIs a natural way for routing to scaleSizeNetwork AdministrationGovernanceAllows multiple metrics at different levels of the hierarchyExploits address aggregation and allocation6432132436137851121011Inter DomainRoutingOSPFRIPIGRPFebruary 25, 2003Abhay Parekh, EE122 S2003:Updated from Stoica EE122 F20025The Importance of InterconnectionsThe internet is an interconnection of unequal networksInterconnection arrangements drive the competitive landscapethe robustness of the networkEnd-to-end performanceInterconnection is central to all large networksVoiceDataWirelessCableFebruary 25, 2003Abhay Parekh, EE122 S2003:Updated from Stoica EE122 F20026Interconnections and Competitionwww.thelist.comHow many ISP’s in the 415 area code?That start with A-C: about 200…Just DSL that start with A-C: about 80In the telephone networkHow many independent telephone companies in 1894-1902 in the US?3039 commercial companies, 979 co-operativesBy controlling interconnection Bell got rid of themInterconnection is now regulated (CLECs)February 25, 2003Abhay Parekh, EE122 S2003:Updated from Stoica EE122 F20027Big PictureLarge ISPLarge ISPDial-UpISPAccessNetworkSmall ISPStub StubStubThe Internet contains a large number of diverse networksFebruary 25, 2003Abhay Parekh, EE122 S2003:Updated from Stoica EE122 F20028Two ways to interconnect IP Networks…PeeringThe business relationship whereby ISPs reciprocally provide to each other connectivity to each others’ transit customersTransitThe business relationship whereby one ISP provides (usually sells) access to all destinations in it’s routing tableWilliam B. Norton, “Internet Service Providers and Peering”February 25, 2003Abhay Parekh, EE122 S2003:Updated from Stoica EE122 F20029PeeringFigure fromWilliam B. Norton, “Internet Service Providers and Peering”West and East Peer with USNet but they can’t reach each otherFebruary 25, 2003Abhay Parekh, EE122 S2003:Updated from Stoica EE122 F200210TransitFigure fromWilliam B. Norton, “Internet Service Providers and Peering”February 25, 2003Abhay Parekh, EE122 S2003:Updated from Stoica EE122 F200211Benefits of Transit v/s PeeringWilliam B. Norton, “Internet Service Providers and Peering”February 25, 2003Abhay Parekh, EE122 S2003:Updated from Stoica EE122 F200212Moving from Transit to PeeringWilliam B. Norton, “Internet Service Providers and Peering”February 25, 2003Abhay Parekh, EE122 S2003:Updated from Stoica EE122 F200213Name of the Game: ReachabilityInterdomain routing is about implementing policies of reachabiltyRouting efficiency and performance is important, but not essentialISPs could be competitors and do not want to share internal network statistics such as load and topologyUse Border Gateway Protocol (BGP)Border routers communicate over TCP port 179A Path Vector ProtocolCommunicate entire paths: Route Advertisements A Router Can be involved multiple BGP sessionsFebruary 25, 2003Abhay Parekh, EE122 S2003:Updated from Stoica EE122 F200214Rborder routerinternal routerBGPR2R1R3AAS1AS2you can reachnet A via metraffic to Atable at R1:dest next hopA R2Share connectivity information across ASesBGP in conceptFebruary 25, 2003Abhay Parekh, EE122 S2003:Updated from Stoica EE122 F200215I-BGP and E-BGPRborder routerinternal routerR1AS1R4R5BAS3E-BGPR2R3AAS2announce BIGP: Interior Gateway Protocol.Example: OSPFI-BGPIGPFebruary 25, 2003Abhay Parekh, EE122 S2003:Updated from Stoica EE122 F200216BGPBorder Routers from the same AS speak IBGPfrom different AS’s speak EBGPEBGP and IBGP are essentially the same protocolIBGP can only propagate routes it has learned directly from its EBGP neighborsAll routers in the same AS form an IBGP meshImportant to keep IBGP and EBGP in syncFebruary 25, 2003Abhay Parekh, EE122 S2003:Updated from Stoica EE122 F200217Sharing routesOne router can participate in many BGP sessions.Initially … node advertises ALL routes it wants neighbor to know (could be > 50K routes)Ongoing … only inform neighbor of changesBGP SessionsAS1AS2AS3February 25, 2003Abhay Parekh, EE122 S2003:Updated from Stoica EE122 F200218Four message typesOpen: Session establishment id exchangeNotification: exception driven informationKeep Alive: soft state Update: path vector informationFebruary 25, 2003Abhay Parekh, EE122 S2003:Updated from Stoica EE122 F200219BGP Update MessageContains information aboutNew RoutesWithdrawn Routes: No longer validPath Attributes: Attribute information allows policies to be implementedFebruary 25, 2003Abhay Parekh, EE122 S2003:Updated from Stoica EE122 F200220IssuesHow are the routes advertised?AddressingHow are routing policies implemented?February 25, 2003Abhay Parekh, EE122 S2003:Updated from Stoica EE122
View Full Document