Interdomain Routing EECS 122 Lecture 11 Department of Electrical Engineering and Computer Sciences University of California Berkeley Review 44 BGP 5 2 2 B 66 B 7 IntraDomain 4 Intradomain 8 RIP 3 3 6 13 13 11 2 10 OSPF IntraDomain 3 1 Formulate the routing problem as a Shortest Path Problem Link State v s Distance Vector Both work reasonably well in a well engineered network IGRP A February 25 2003 IntraDomain 13 12 C Abhay Parekh EE122 S2003 Updat ed from Stoica EE122 F2002 2 Today Why Hierarchical Routing Interconnections Addressing Interdomain Routing BGP February 25 2003 Abhay Parekh EE122 S2003 Updat ed from Stoica EE122 F2002 3 Hierarchical Routing Is a natural way for routing to scale Size Network Administration Governance Allows multiple metrics at different levels of the hierarchy Exploits address aggregation and allocation February 25 2003 5 44 7 8 RIP 66 22 1 33 Inter Domain Routing 11 10 13 13 OSPF 12 IGRP Abhay Parekh EE122 S2003 Updat ed from Stoica EE122 F2002 4 The Importance of Interconnections The internet is an interconnection of unequal networks Interconnection arrangements drive the competitive landscape the robustness of the network End to end performance Interconnection is central to all large networks Voice Data Wireless Cable February 25 2003 Abhay Parekh EE122 S2003 Updat ed from Stoica EE122 F2002 5 Interconnections and Competition www thelist com How many ISP s in the 415 area code That start with A C about 200 Just DSL that start with A C about 80 In the telephone network How many independent telephone companies in 1894 1902 in the US 3039 commercial companies 979 co operatives By controlling interconnection Bell got rid of them Interconnection is now regulated CLECs February 25 2003 Abhay Parekh EE122 S2003 Updat ed from Stoica EE122 F2002 6 Big Picture Large ISP Large ISP Stub Dial Up ISP Small ISP Stub Access Network Stub e Internet containsAbhay a large number of diverse network February 25 2003 7 Parekh EE122 S2003 Updat ed from Stoica EE122 F2002 Two ways to interconnect IP Networks Peering The business relationship whereby ISPs reciprocally provide to each other connectivity to each others transit customers Transit The business relationship whereby one ISP provides usually sells access to all destinations in it s routing table William B Norton Internet Service Providers and Peering February 25 2003 Abhay Parekh EE122 S2003 Updat ed from Stoica EE122 F2002 8 Peering Figure from William B Norton Internet Service Providers and Peering West and East Peer with USNet but they can t reach each other February 25 2003 Abhay Parekh EE122 S2003 Updat ed from Stoica EE122 F2002 9 Transit February 25 2003 Figure from William B Norton Internet Service Providers and Peering Abhay Parekh EE122 S2003 Updat ed from Stoica EE122 F2002 10 Benefits of Transit v s Peering William B Norton Internet Service Providers and Peering February 25 2003 Abhay Parekh EE122 S2003 Updat ed from Stoica EE122 F2002 11 Moving from Transit to Peering William B Norton Internet Service Providers and Peering February 25 2003 Abhay Parekh EE122 S2003 Updat ed from Stoica EE122 F2002 12 Name of the Game Reachability Interdomain routing is about implementing policies of reachabilty Routing efficiency and performance is important but not essential ISPs could be competitors and do not want to share internal network statistics such as load and topology Use Border Gateway Protocol BGP Border routers communicate over TCP port 179 A Path Vector Protocol Communicate entire paths Route Advertisements A Router Can be involved multiple BGP sessions February 25 2003 Abhay Parekh EE122 S2003 Updat ed from Stoica EE122 F2002 13 BGP in concept you can reach net A via me AS2 BGP AS1 R3 R2 traffic to A R1 table at R1 dest next hop A R2 A R border router internal router Share connectivity information across ASes February 25 2003 Abhay Parekh EE122 S2003 Updat ed from Stoica EE122 F2002 14 I BGP and E BGP IGP Interior Gateway Protocol Example OSPF I BGP R2 R3 IGP A AS1 E BGP announce B AS2 R1 AS3 R5 R4 R border router internal router February 25 2003 B Abhay Parekh EE122 S2003 Updat ed from Stoica EE122 F2002 15 BGP Border Routers from the same AS speak IBGP from different AS s speak EBGP EBGP and IBGP are essentially the same protocol IBGP can only propagate routes it has learned directly from its EBGP neighbors All routers in the same AS form an IBGP mesh Important to keep IBGP and EBGP in sync February 25 2003 Abhay Parekh EE122 S2003 Updat ed from Stoica EE122 F2002 16 Sharing routes One 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 changes AS1 BGP Sessions AS3 AS2 February 25 2003 Abhay Parekh EE122 S2003 Updat ed from Stoica EE122 F2002 17 Four message types Open Session establishment id exchange Notification exception driven information Keep Alive soft state Update path vector information February 25 2003 Abhay Parekh EE122 S2003 Updat ed from Stoica EE122 F2002 18 BGP Update Message Contains information about New Routes Withdrawn Routes No longer valid Path Attributes Attribute information allows policies to be implemented February 25 2003 Abhay Parekh EE122 S2003 Updat ed from Stoica EE122 F2002 19 Issues How are the routes advertised Addressing How are routing policies implemented February 25 2003 Abhay Parekh EE122 S2003 Updat ed from Stoica EE122 F2002 20 Addressing Every router must be able to forward based on any destination IP address One strategy Have a row for each address There would be 10 8 rows Better strategy Have a row for a range of addresses If addresses are assigned at random that wouldn t work too well MAC addresses Addresses allocation is a big deal February 25 2003 Abhay Parekh EE122 S2003 Updat ed from Stoica EE122 F2002 21 Class base Addressing Addressing reflects internet hierarchy 32 bits divided into 2 parts 8 0 Class A Class B Class C February 25 2003 0 network 0 10 host 16 network 0 host 24 110 network host Abhay Parekh EE122 S2003 Updat ed from Stoica EE122 F2002 2 million nets 256 hosts 22 Class based addresses did not scale well Example an organization initially needs 100 addresses Allocate it a class C address Organization grows to need 300 addresses Class B address is allocated 64K hosts That s overkill a huge waste Only about 8200 class B addresses Artificial Address crises February 25 2003 Abhay Parekh EE122 S2003 Updat ed from Stoica EE122 F2002 23
View Full Document
Unlocking...