Shortest Path Routing EE 122 Intro to Communication Networks Fall 2007 WF 4 5 30 in Cory 277 Vern Paxson TAs Lisa Fowler Daniel Killebrew Jorge Ortiz http inst eecs berkeley edu ee122 Materials with thanks to Jennifer Rexford Ion Stoica and colleagues at Princeton and UC Berkeley 1 Announcements Guest lecturer next Wednesday Brighten Godfrey I will have office hours as usual next Friday but not next Wednesday Send email for an appointment M Tu Th Section next week will cover Spanning Tree algorithm plus questions re routing algorithms Do attend as usual 2 1 Goals of Today s Lecture Routing vs forwarding Control plane vs Data plane Link state routing Dijkstra s algorithm Suitable as Interior Gateway Protocol IGP o i e used within a single ISP Topology change detection convergence Distance vector routing Bellman Ford Suitable as Exterior Gateway Protocol EGP o Between ISPs o Though really need something more BGP next lecture 3 Forwarding vs Routing Forwarding data plane Directing a data packet to an outgoing link Individual router using a forwarding table Routing control plane Computing paths the packets will follow Routers talking amongst themselves Individual router creating a forwarding table 4 2 Why Does Routing Matter We need good end to end performance Find the shortest best path o Propagation delay throughput packet loss Ensure efficient use of network resources Balance traffic over the routers and links Avoid congestion by directing traffic to lightlyloaded links Withstand disruptions Failures maintenance load balancing Limit packet loss and delay during changes 5 Know Thy Network Routing requires knowledge of the network structure Centralized global state Single entity knows the complete network structure Can calculate all routes centrally Link State Routing Problems with this approach E g Algorithm Dijkstra Distributed global state E g Protocol OSPF Every router knows the complete network structure Independently calculates routes Distance Vector Routing Problems with this approach E g Algorithm Bellman Ford Distributed no global state E g Protocol RIP Every router knows only about its neighboring routers Independently calculates routes Problems with this approach 6 3 Modeling a Network Modeled as a graph Routers nodes Link edges o Possible edge costs delay congestion level 5 2 A 3 B 2 3 1 D C 1 5 F 1 E 2 Goal of Routing Determine a good path through the network from source to destination Good usually means the shortest path 7 Link State Routing Each router has a complete picture of the network How does each router get the global state Each router reliably floods information about its neighbors to every other router more later Each router independently calculates the shortest path from itself to every other router Dijkstra s Shortest Path Algorithm INPUT o Network topology graph link costs known to all nodes OUTPUT o Least cost paths from one node source to all other nodes 8 4 Notation c i j link cost from node i to j cost infinite if not direct neighbors 0 D v current value of cost 5 of path from source to destination v p v predecessor node along path from source to v that is next to v 2 A B 2 1 D S set of nodes whose 3 C 3 1 5 F 1 E 2 least cost path definitively known Source 9 Dijsktra s Algorithm c i j link cost from node i to j 1 Initialization D v current cost source v 2 S A 3 for all nodes v p v predecessor node along 4 if v adjacent to A path from source to v that is 5 then D v c A v next to v 6 else D v S set of nodes whose least 7 cost path definitively known 8 Loop 9 find w not in S such that D w is a minimum 10 add w to S 11 update D v for all v adjacent to w and not in S 12 if D w c w v D v then w gives us a shorter path to v than we ve found so far 13 D v D w c w v p v w 14 until all nodes in S 10 5 Example Dijkstra s Algorithm Step 0 1 2 3 4 5 D B p B D C p C D D p D 2 A 1 A 5 A start S A 5 2 A B 3 2 1 D C 3 F 1 E 1 5 2 D E p E D F p F 1 Initialization 2 S A 3 for all nodes v 4 if v adjacent to A 5 then D v c A v 6 else D v 11 Example Dijkstra s Algorithm Step 0 1 2 3 4 5 D B p B D C p C D D p D 2 A 1 A 5 A start S A 5 2 A B 2 1 D 3 C 3 1 5 F 1 E 2 D E p E D F p F 8 Loop 9 find w not in S s t D w is a minimum 10 add w to S 11 update D v for all v adjacent to w and not in S 12 If D w c w v D v then 13 D v D w c w v p v w 14 until all nodes in S 12 6 Example Dijkstra s Algorithm Step 0 1 2 3 4 5 D B p B D C p C D D p D 2 A 1 A 5 A start S A AD 5 2 A B 3 2 1 D C 3 F 1 E 1 5 2 D E p E D F p F 8 Loop 9 find w not in S s t D w is a minimum 10 add w to S 11 update D v for all v adjacent to w and not in S 12 If D w c w v D v then 13 D v D w c w v p v w 14 until all nodes in S 13 Example Dijkstra s Algorithm Step 0 1 2 3 4 5 D B p B D C p C D D p D 2 A 1 A 5 A 4 D start S A AD 5 2 A B 2 1 D 3 C 3 1 5 F 1 E 2 D E p E D F p F 2 D 8 Loop 9 find w not in S s t D w is a minimum 10 add w to S 11 update D v for all v adjacent to w and not in S 12 If D w c w v D v then 13 D v D w c w v p v w 14 until all nodes in S 14 7 Example Dijkstra s Algorithm Step 0 1 2 3 4 5 D B p B D C p C D D p D D E p E D F p F 2 A 1 A 5 A 4 D 2 D 3 E 4 E start S A AD ADE 5 2 A …
View Full Document
Unlocking...