EE 122 Intra domain routing Distance Vector Computer Science Division Department of Electrical Engineering and Computer Science University of California Berkeley Berkeley CA 94720 1776 September 16 2004 based partially on Kurose Ross slides Katz Stoica F04 Problem How is a packet transmitted from source to destination in the Internet Example how does packet sent by B reaches D Host C Host D Host A Node 1 Node 2 Node 3 Node 5 Host B Node 6 Node 7 Host E Node 4 Katz Stoica F04 2 Forwarding vs Routing Forwarding 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 Katz Stoica F04 3 IP Packet Forwarding Each router maintains a mapping of address prefixes to output ports Upon receiving a packet a router performs the longest prefix matching on packet s destination address and forwards it to corresponding output Prefix interface 128 16 120 xxx 1 12 82 xxx xxx 3 12 82 100 xxx 2 12 82 100 101 1 128 16 120 111 2 Katz Stoica F04 4 Internet Routing Internet organized as a two level hierarchy First level autonomous systems AS s AS region of network under a single administrative domain ASes 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 4 Katz Stoica F04 5 Example Interior router BGP router AS 1 AS 3 AS 2 Katz Stoica F04 6 Intra domain Routing Protocols Based 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 length Link 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 overhead Katz Stoica F04 7 Routing Goal determine a good path through the network from source to destination Good means usually the shortest path Network modeled as a graph A Routers nodes 1 Link edges Edge cost delay congestion level 2 5 B 2 D 3 C 3 1 5 F 1 E 2 Katz Stoica F04 8 Distance Vector Routing Algorithm Iterative continues until no nodes exchange info Asynchronous nodes need not exchange info iterate in lock steps Distributed each node communicates only with directlyattached neighbors Each 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 destination Katz Stoica F04 9 Distance Vector Routing Each local iteration caused by Local link cost change Message from neighbor its least cost path change from neighbor to destination Each node notifies neighbors only when its least cost path to any destination changes Neighbors then notify their neighbors if necessary Each node wait for change in local link cost or msg from neighbor recompute distance table if least cost path to any dest has changed notify neighbors Katz Stoica F04 10 Distance Vector Algorithm cont d 1 Initialization 2 for all neighbors V do 3 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 do 14 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 forever Katz Stoica F04 11 Example Distance Vector Algorithm Node A 2 A B 7 Dest 3 1 C D 1 Node B Cost NextHop Cost NextHop B 2 B A 2 A C 7 C C 1 C D D 3 D Node C 1 Initialization 2 for all neighbors V do 3 if V adjacent to A 4 D A V c A V 5 else 6 D A V Dest Node D Dest Cost NextHop Dest Cost NextHop A 7 A A B 1 B B 3 B D 1 D C 1 C Katz Stoica F04 12 Example 1st Iteration C A Node A 2 A B 7 Dest 3 1 C D 1 Cost NextHop Dest Cost NextHop B 2 B A 2 A C 7 C C 1 C D D 3 D op else if update D V Y received from V for all destinations Y do if destination Y through V D A Y D A V D V Y else D A Y min D A Y D A V D V Y if there is a new minimum for dest Y send D A Y to all neighbors orever Node B Node C D C A D C B D C D Node D Dest Cost NextHop Dest Cost NextHop A 7 A A B 1 B B 3 B D 1 D C 1 C Katz Stoica F04 13 Example 1st Iteration C A Node A 2 A B 7 Dest Cost NextHop 3 1 C Node B D 1 Cost NextHop B 2 B A 2 A C 7 C C 1 C D 8 C D 3 D D A D min D A D D A C D C D min 7 1 8 op else if update D V Y received from V for all destinations Y do if destination Y through V D A Y D A V D V Y else D A Y min D A Y D A V D V Y if there is a new minimum for dest Y send D A Y to all neighbors orever Dest Node C D C A D C B D C D Node D Dest Cost NextHop Dest Cost NextHop A 7 A A B 1 B B 3 B D 1 D C 1 C Katz Stoica F04 14 Example 1st Iteration C A Node A 2 A B 7 Dest Cost NextHop 3 1 C Node B D 1 Dest Cost NextHop B 2 B A 2 A C 7 C C 1 C D 8 C D 3 D op else if update D V Y received from V for all destinations Y do if destination Y through V D A Y …
View Full Document
Unlocking...