EECS 122: Introduction to Computer Networks Interdomain RoutingToday’s LectureDistance Vector: Link Cost ChangesDistance Vector: Count to Infinity ProblemDistance Vector: Poisoned ReverseLink State vs. Distance VectorAre We Done?Issues We Haven’t AddressedScalingNetwork StructureAutonomous Systems (AS)ImplicationsIntradomain And InterdomainInterconnectionOutlineAssigning Addresses (Ideally)Original Addressing SchemeClassless Interdomain Routing (CIDR)#1: Address Space ExhaustionCIDR AddressingMore FormallyProblem #2: Routing Table SizeBorder Gateway ProtocolWho speaks BGP?Purpose of BGPI-BGP and E-BGPIssuesChoice of Routing AlgorithmPath Vector ProtocolBGP Routing TableAdvertising RoutesBasic Messages in BGPRoutes Have AttributesMulti-Exit Discriminator (MED)Local PreferenceChoosing Best RouteRouting Process OverviewImport and Export PoliciesTransit vs. Nontransit ASAS Relationships and Export RulesCustomer-Transit ProblemIs Reachability Guaranteed?Peering & TransitPeeringTransitReachability?BGP and PerformanceResearch AsideKatz, Stoica F04EECS 122: Introduction to Computer Networks Interdomain RoutingComputer Science DivisionDepartment of Electrical Engineering and Computer SciencesUniversity of California, BerkeleyBerkeley, CA 94720-17762Katz, Stoica F04Today’s LectureNetwork (IP)ApplicationTransportLinkPhysical27, 8, 910, 1117, 18, 1914, 15, 1621, 22, 232563Katz, Stoica F04Distance Vector: Link Cost ChangesAC1450B1“goodnews travelsfast”D C NA 4 AC 1 BNode BD C NA 5 BB 1 BNode CD C NA 1 AC 1 BD C NA 5 BB 1 BD C NA 1 AC 1 BD C NA 2 BB 1 BD C NA 1 AC 1 BD C NA 2 BB 1 BLink cost changes heretime7 loop:8 wait (until A sees a link cost change to neighbor V 9 or until A receives update from neighbor V) 10 if (D(A,V) changes by d) 11 for all destinations Y through V do 12 D(A,Y) = D(A,Y) + d 13 else if (update D(V, Y) received from V) 14 D(A,Y) = D(A,V) + D(V, Y);15 if (there is a new minimum for destination Y)16 send D(A, Y) to all neighbors 17 forever Algorithm terminates4Katz, Stoica F04Distance Vector: Count to Infinity Problem AC1450B60“badnews travelsslowly”D C NA 4 AC 1 BNode BD C NA 5 BB 1 BNode CD C NA 6 CC 1 BD C NA 5 BB 1 BD C NA 6 CC 1 BD C NA 7 BB 1 BD C NA 8 CC 1 BD C NA 2 BB 1 BLink cost changes here; recall from slide 24 that B also maintains shortest distance to A through C, which is 6. Thus D(B, A) becomes 6 !time7 loop:8 wait (until A sees a link cost change to neighbor V 9 or until A receives update from neighbor V) 10 if (D(A,V) changes by d) 11 for all destinations Y through V do 12 D(A,Y) = D(A,Y) + d ;13 else if (update D(V, Y) received from V) 14 D(A,Y) = D(A,V) + D(V, Y);15 if (there is a new minimum for destination Y)16 send D(A, Y) to all neighbors 17 forever …5Katz, Stoica F04Distance Vector: Poisoned ReverseAC1450B60If C routes through B to get to A:-C tells B its (C’s) distance to A is infinite (so B won’t route to A via C)-Will this completely solve count to infinity problem? D C NA 4 AC 1 BNode BD C NA 5 BB 1 BNode CD C NA 60 AC 1 BD C NA 5 BB 1 BD C NA 50 AB 1 BLink cost changes here; B updates D(B, A) = 60 as C has advertised D(C, A) = ∞timeD C NA 60 AC 1 BD C NA 50 AB 1 BD C NA 51 CC 1 BD C NA 50 AB 1 BD C NA 51 CC 1 BAlgorithm terminates6Katz, Stoica F04Link State vs. Distance VectorPer-node message complexityLS: O(e) messages-e: number of edgesDV: O(d) messages, many times-d is node’s degreeComplexity/ConvergenceLS: O(n2) computation DV: convergence time varies-may be routing loops-count-to-infinity problemRobustness: what happens if router malfunctions?LS: -node can advertise incorrect link cost-each node computes only its own tableDV:-node can advertise incorrect path cost-each node’s table used by others; error propagate through network7Katz, Stoica F04Are We Done?We now know how to route scalablyWhat more is there to do?8Katz, Stoica F04Issues We Haven’t AddressedScaling-Addressing-Router table sizeStructure-Autonomy-Policy9Katz, Stoica F04ScalingEvery router must be able to forward based on *any* destination IP address-Given address, it needs to know “next hop” (table)Naive: Have an entry for each address-There would be 10^8 entries!Better: Have an entry for a range of addresses-But can’t do this if addresses are assigned randomly!Addresses allocation is a big deal10Katz, Stoica F04Network StructureLarge ISPLarge ISPDial-UpISPAccessNetworkSmall ISPStub StubStubThe Internet contains a large number of diverse networks11Katz, Stoica F04Autonomous Systems (AS)Internet is not a single network!The Internet is a collection of networks, each controlled by different administrationsAn autonomous system (AS) is a network under a single administrative control12Katz, Stoica F04ImplicationsASs want to choose own local routing algorithm-AS takes care of getting packets to/from their own hosts-Interdomain routing and Intradomain routingASs want to choose own nonlocal routing policy-Interdomain routing must accommodate this-BGP is the current interdomain routing protocol13Katz, Stoica F04Intradomain And InterdomainABC6785431212101311643213B243613OSPFRIPIGRPBGPIntraDomainIntraDomainIntraDomain14Katz, Stoica F04InterconnectionIP unifies network technologies-allows any network to communicate with anotherBGP unifies network organizations-ties them into a global Internet15Katz, Stoica F04OutlineAddressingBGP16Katz, Stoica F04Assigning Addresses (Ideally)Host: gets IP address from its organization or ISPOrganization: gets IP address block from ISPISP: gets address block from routing registry:-ARIN: American Registry for Internet Numbers-RIPE: Reseaux IP Europeens-APNIC: Asia Pacific Network Information CenterEach AS is assigned a 16-bit number (65536 total) -Currently 10,000 AS’s in use-Most stub, so don’t really need own number17Katz, Stoica F04Class-based addressing schemes:-32 bits divided into 2 parts: -Class A -Class B-Class C Original Addressing Schemenetwork host 00network host 1160network host 1240~2M nets254 hosts801 0~16K nets~65K hosts126 nets~16M hostsOriginal Vision: Route on network numberAll nodes with same net # are directly connected18Katz, Stoica F04Classless Interdomain Routing (CIDR)Introduced to solve two problems:exhaustion of IP address spacesize and growth rate of routing table19Katz, Stoica F04#1: Address Space
View Full Document
Unlocking...