BooksLecture 3: Internet Routing (The real picture) (Notes. Also you can find the material in P&D 4.2 except 4.2.5, 4.3.1, 4.3.2, IP Addresses & IP HeaderForwardingPicture of the InternetTwo Main Approaches to Intra-domain Routing Distributed Bellman-Ford AlgorithmDistributed Bellman-Ford AlgorithmDistributed Bellman-Ford AlgorithmDistributed Bellman-Ford AlgorithmFormallyA Problem with Bellman-FordA Problem with Bellman-FordHow are These Loops Caused?Counting to Infinity Problem SolutionsTwo Main Approaches to Intra-domain Routing Link StateDijkstra’s Shortest Path First AlgorithmInter-Domain Routing & BGPPicture of the InternetInternet HierarchyAS Numbers (ASNs)A Logical View of the InternetInter-AS Relationship: Transit vs. PeeringPolicy Impact on RoutingCustomer-Provider HierarchyThe Peering RelationshipPeering Provides ShortcutsPolicy-Based RoutingBGP: Distance Vector with PathBGP Operations (Simplified) Four Types of BGP MessagesImplementing Customer/Provider and Peer/Peer relationships using BGPImporting RoutesExporting RoutesImport Routes Export Routes An instance of the Stable Paths Problem (SPP)An SPP may have multiple solutions BAD GADGET : No Stable SolutionKnown ResultsTwo Types of BGP Neighbor RelationshipsiBGPInternal BGP (iBGP)We learned6.263 Data Communication NetworksDina [email protected]/~dinaLecture 3: Internet Routing(some slides are taken from I. Stoica and N. Mckewon & T. Griffin)2BooksText Book Data Communication Networks, by DimitriBetsekas and Robert GallagerRecommended Computer Networks - A Systems Approach, by Larry L. Peterson and Bruce S. Davie, 3rdedition.3Lecture 3: Internet Routing (The real picture) (Notes. Also you can find the material in P&D 4.2 except 4.2.5, 4.3.1, 4.3.2, 4.3.3. For algs., see B&G-5.2.3)Lecture 1: Taxonomy of Networks(Mainly notes. Reading: P&D 3.1 pp. 164-180 )Lecture 2: Routing AlgorithmsBertsekas and Gallager4IP Addresses & IP Header¾ IP address: e.g., 18.26.0.1¾ IP prefix: • e.g., 18/8 contains 224addresses• e.g, 18.26/16 or 18.26.0/24ECNversionheaderlengthDS total length (in bytes)Identification Fragment offsetsource IP addressdestination IP addressoptions (0 to 40 bytes)payload4 bytestime-to-live (TTL) protocol header checksumbit # 0 15 23 248317160MFDF5Forwarding What’s the difference between routing and forwarding?¾ Routing is finding the path¾ Forwarding is the action of sending the packet to the next-hop toward its destination Each router has a forwarding table¾ Forwarding tables are created by a routing protocol Forwarding:¾ When a packet arrives, • router looks up the dst. IP in the forwarding table• finds nexthop• queues packet to be sent on the interface connected to nexthop Forwarding needs to be fast18.2/1619.26/165.1.1/24137/818/8Dest. AddrR2R1R3R2R1Next-hop18.2/165.1.1/2419.26/1618/8137/8R2R3R1Router6Picture of the Internet Internet: A collection of Autonomous Systems (ASes)¾ E.g., MIT network, AT&T, Quest, Sprint, … Routing is hierarchical¾ Intra-Domain Routing inside an AS¾ Inter-Domain Routing between ASesAS-1AS-2AS-3Interior routerBorder router7Two Main Approaches to Intra-domain Routing Distance Vector Protocols¾ E.g., RIP¾ Based on Distributed Bellman-Ford Algorithm¾ Periodically, each node tells its neighbors about its shortest route to all other nodes in the network Link State Protocols¾ E.g., OSPF¾ Based on Dijkstra Algorithm¾ Periodically, each node tells all nodes about its neighbors (it floods that information)8Distance Vector: Control Traffic When the routing table of a node changes, the node sends its table to its neighbors A node updates its table with information received from its neighborsHost AHost BHost EHost DHost CN1N2N3N4N5N7N69Distributed Bellman-Ford AlgorithmR5R3R7R8R6R4R2R1Example: Compute routes to R81142422323∞∞∞∞∞∞∞Initial State: All routers except R8 set their route length to ∞. R8 sets its route length to 0.010Distributed Bellman-Ford AlgorithmR5R3R7R8R6R4R2R11122323424∞∞∞R1InfR2InfR34, R8R4InfR52, R8R62, R8R73, R84232Example: Compute routes to R8 Every T seconds, each router tells its neighbors its lowest-cost to R8 When a router receives a message from neighbor j, it updates its path cost as: If (j is my current nexthop) then cost= j’s cost to R8 + cost of the link to j else cost =min(current cost, j’s cost to R8 + cost of the link to j)Note, routing tables at each router have both the next-hop and the costIterative step:11Distributed Bellman-Ford AlgorithmR5R3R7R8R6R4R2R11122323424R16, R3R24, R5R34, R8R46, R7R52, R8R62, R8R73, R84232646Example: Compute routes to R8Repeat until no costs change12Distributed Bellman-Ford AlgorithmR5R3R7R8R6R4R2R11122323424R16, R3R24, R5R34, R8R46, R7R52, R8R62, R8R73, R84232646R5R3R7R8R6R4R2R11422232R16, R3R24, R5R34, R8R45, R2R52, R8R62, R8R73, R84232645SolutionExample: Compute routes to R813Formally7 loop:8 wait (link cost update or update message)9 if (c(A,V) changes by d) 10 for all destinations Y through V do11 D(A,Y) = D(A,Y) + d12 else if (update D(V, Y) received from V) 13 for all destinations Y do14 if (destination Y through V)15 D(A,Y) = c(A,V) + D(V, Y);16 else17 D(A, Y) = min(D(A, Y), c(A, V) + D(V, Y));18 if (there is a new minimum for destination Y)19 send D(A, Y) to all neighbors 20 forever1 Initialization:2 for all neighbors V do3 if V adjacent to A4 D(A, V) = c(A,V); 5 else6 D(A, V) = ∞; At router A, assume c(A,V) is the cost of the edge A-V and D(A,V) is the cost of the path from A to V14A Problem with Bellman-FordR4R3R2R1111Consider the calculation of distances to R4:“Bad news travels slowly”3211, R42,R33,R20R3R2R1TimeX3,R22,R33,R2R3ÆR4fails15A Problem with Bellman-FordR4R3R2R111Consider the calculation of distances to R4:“Bad news travels slowly”……5,R24,R35,R23211, R42,R33,R20R3R2R1Time……“Counting to infinity”3,R22,R33,R2R3ÆR4fails3,R24,R33,R216How are These Loops Caused? Observation 1:¾ R3’s metric increases Observation 2:¾ R2 picks R3 as next hop to R4; But, the implicit pathfrom R2 to R4 includes R3!17Counting to Infinity ProblemSolutions1. Set infinity = “some small integer” (e.g. 200). Stop when count = 200.2. Split Horizon: Because R2received lowest cost path from R3, it does not advertise cost to R33. Split-horizon with poison reverse: R2advertises infinity
View Full Document