EE 122: Intra-domain routing: Distance VectorProblemForwarding vs. RoutingIP Packet ForwardingInternet RoutingExampleIntra-domain Routing ProtocolsRoutingDistance Vector Routing AlgorithmDistance Vector RoutingDistance Vector Algorithm (cont’d)Example: Distance Vector AlgorithmExample: 1st Iteration (C A)Slide 14Slide 15Example: 1st Iteration (BA, CA)Example: End of 1st IterationExample: End of 3nd IterationLink Cost ChangesCount-to-Infinity ProblemSplit HorizonPoison ReverseIs “Count To Infinity” Solved?Katz. Stoica F04EE 122: Intra-domain routing: Distance VectorComputer Science DivisionDepartment of Electrical Engineering and Computer ScienceUniversity of California, Berkeley,Berkeley, CA 94720-1776September 16, 2004(* based partially on Kurose & Ross’ slides)2Katz. Stoica F04ProblemHow is a packet transmitted from source to destination in the Internet?Example: how does packet sent by B reaches DHost AHost BHost EHost DHost CNode 1Node 2Node 3Node 4Node 5Node 6Node 73Katz. Stoica F04Forwarding vs. RoutingForwarding: the process by which a router sends an arriving packet to the next router towards final destination Routing: the process by which a router acquires the information to perform packet forwarding (e.g., routing tables)4Katz. Stoica F04IP Packet ForwardingEach router maintains a mapping of address prefixes to output portsUpon receiving a packet, a router performs the longest prefix matching on packet’s destination address and forwards it to corresponding output…… 312.82.xxx.xxx 1128.16.120.xxx12128.16.120.11112.82.100.10112.82.100.xxx 2interfacePrefix5Katz. Stoica F04Internet RoutingInternet organized as a two level hierarchyFirst level – autonomous systems (AS’s)-AS – region of network under a single administrative domainASes run an intra-domain routing protocols-Distance Vector, e.g., Routing Information Protocol (RIP)-Link State, e.g., Open Shortest Path First (OSPF)Between ASes runs inter-domain routing protocols, e.g., Border Gateway Routing (BGP)-De facto standard today, BGP-46Katz. Stoica F04ExampleAS-1AS-2AS-3Interior routerBGP router7Katz. Stoica F04Intra-domain Routing ProtocolsBased on UDP (unreliable datagram delivery)Distance vector-Routing Information Protocol (RIP), based on Bellman-Ford-Each neighbor periodically exchange reachability information to its neighbors-Minimal communication overhead, but it takes long to converge, i.e., in proportion to the maximum path lengthLink state-Open Shortest Path First (OSPF), based on Dijkstra-Each network periodically floods immediate reachability information to other routers-Fast convergence, but high communication and computation overhead8Katz. Stoica F04RoutingGoal: determine a “good” path through the network from source to destination-Good means usually the shortest pathNetwork modeled as a graph-Routers nodes-Link edges•Edge cost: delay, congestion level,…AEDCBF22131125359Katz. Stoica F04Distance Vector Routing AlgorithmIterative: continues until no nodes exchange infoAsynchronous: nodes need not exchange info/iterate in lock stepsDistributed: each node communicates only with directly-attached neighborsEach router maintains-Row for each possible destination-Column for each directly-attached neighbor to node-Entry in row Y and column Z of node X best known distance from X to Y, via Z as next hop (remember this !)Note: for simplicity in this lecture examples we show only the shortest distances to each destination10Katz. Stoica F04Distance Vector RoutingEach local iteration caused by: -Local link cost change -Message from neighbor: its least cost path change from neighbor to destinationEach node notifies neighbors only when its least cost path to any destination changes-Neighbors then notify their neighbors if necessarywait for (change in local link cost or msg from neighbor)recompute distance tableif least cost path to any dest has changed, notify neighbors Each node:11Katz. Stoica F04Distance Vector Algorithm (cont’d)1 Initialization: 2 for all neighbors V do3 if V adjacent to A 4 D(A, V) = c(A,V); 5 else 6 D(A, V) = ∞; 7 loop: 8 wait (until A sees a link cost change to neighbor V or until A receives update from neighbor V) 9 if (c(A,V) changes by d) 10 for all destinations Y through V do 11 D(A,Y) = D(A,Y) + d 12 else if (update D(V, Y) received from V) 13 for all destinations Y do14 if (destination Y through V)15 D(A,Y) = D(A,V) + D(V, Y);16 else /* update D(A, Y) if there is a shorter path through V */17 D(A, Y) = min(D(A, Y), D(A, V) + D(V, Y));18 if (there is a new minimum for destination Y)19 send D(A, Y) to all neighbors 20 forever12Katz. Stoica F04Example: Distance Vector AlgorithmAC127BD31Dest. Cost NextHopB 2 BC 7 CD ∞ -Node ADest. Cost NextHopA 2 AC 1 CD 3 DNode BDest. Cost NextHopA 7 AB 1 BD 1 DNode CDest. Cost NextHopA ∞ -B 3 BC 1 CNode D1 Initialization: 2 for all neighbors V do3 if V adjacent to A 4 D(A, V) = c(A,V); 5 else 6 D(A, V) = ∞; …13Katz. Stoica F04Dest. Cost NextHopB 2 BC 7 CD ∞ -Node AExample: 1st Iteration (C A)AC127BD31Dest. Cost NextHopA 2 AC 1 CD 3 DNode BDest. Cost NextHopA 7 AB 1 BD 1 DNode CDest. Cost NextHopA ∞ -B 3 BC 1 CNode D(D(C,A), D(C,B), D(C,D))…7 loop: …12 else if (update D(V, Y) received from V) 13 for all destinations Y do14 if (destination Y through V)15 D(A,Y) = D(A,V) + D(V, Y);16 else17 D(A, Y) = min(D(A, Y), D(A, V) + D(V, Y));18 if (there is a new minimum for dest. Y)19 send D(A, Y) to all neighbors 20 forever14Katz. Stoica F04Dest. Cost NextHopB 2 BC 7 CD 8 CNode AExample: 1st Iteration (C A)AC127BD31Dest. Cost NextHopA 2 AC 1 CD 3 DNode BDest. Cost NextHopA 7 AB 1 BD 1 DNode CDest. Cost NextHopA ∞ -B 3 BC 1 CNode DD(A, D) = min(D(A, D), D(A, C) + D(C,D) = min(∞ , 7 + 1) = 8(D(C,A), D(C,B), D(C,D))…7 loop: …12 else if (update D(V, Y) received from V) 13 for all destinations Y do14 if (destination Y through V)15 D(A,Y) = D(A,V) + D(V, Y);16 else17 D(A, Y) = min(D(A, Y), D(A, V) + D(V, Y));18 if (there is a new minimum for dest. Y)19 send D(A, Y) to all neighbors 20 forever15Katz. Stoica F04…7 loop: …12 else if (update D(V, Y) received from V) 13 for all
View Full Document
Unlocking...