What is Routing Routing implements the core function of a network EE 122 Shortest Path Routing It ensures that information accepted for transfer at a source node is delivered to the correct set of destination nodes at reasonable levels of performance Ion Stoica TAs Junda Liu DK Moon David Zats http inst eecs berkeley edu ee122 fa09 Materials with thanks to Vern Paxson Jennifer Rexford and colleagues at UC Berkeley 1 Internet Routing Interior router BGP router AS 1 AS region of network under a single administrative domain AS 3 AS s run an intra domain routing protocols Example Internet organized as a two level hierarchy First level autonomous systems AS s 2 Distance Vector e g Routing Information Protocol RIP Link State e g Open Shortest Path First OSPF AS 2 Between AS s runs inter domain routing protocols e g Border Gateway Routing BGP De facto standard today BGP 4 3 4 1 Forwarding vs Routing Forwarding data plane Know Thy Network 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 5 5 Routers nodes Link edges B Possible edge costs Every router knows the complete network structure Independently calculates routes Distance Vector Routing Problems with this approach E g Algorithm Bellman Ford E g Protocol RIP Distributed no global state Every router knows only about its neighboring routers Independently calculates routes Problems with this approach 6 Link State Control Traffic delay congestion level 2 A Distributed global state Modeled as a graph Single entity knows the complete network structure Can calculate all routes centrally Link State Routing E g Algorithm Dijkstra Problems with this approach E g Protocol OSPF Modeling a Network Routing requires knowledge of the network structure Centralized global state 3 2 3 1 D C 1 5 E Host D Host A F 1 Each node floods its local information to every other node in the network Each node ends up knowing the entire network topology use Dijkstra to compute the shortest path to every other node Host C 2 N1 N2 N3 Goal of Routing N5 Determine a good path through the network from source to destination Good usually means the shortest path Host B 7 Host E N4 N6 N7 8 2 Link State Node State Notation C A Host A Host C D D D Host D B B E B E E N2 N1 C A D N3 A C D B E N5 B Host B E A D D B N4 N6 C C A B E c i j link cost from node i to j cost infinite if not direct neighbors 0 D v current value of cost of path from source to destination v p v predecessor node along path from source to v that is next to v S set of nodes whose least cost path definitively known C A C A Host EE N7 5 2 A B 2 1 D 3 C 3 1 5 F 1 E 2 Source 9 Dijsktra s Algorithm 10 Example Dijkstra s Algorithm c i j link cost from node i to j D v current cost source v p v predecessor node along 1 Initialization 2 S A 3 for all nodes v path from source to v that is 4 if v adjacent to A next to v 5 then D v c A v S set of nodes whose least 6 else D v cost path definitively known 7 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 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 2 1 11 B D 3 C 3 1 5 F 1 E 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 12 3 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 Example Dijkstra s Algorithm D E p E D F p F Step 0 1 2 3 4 5 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 D B p B D C p C D D p D 2 A 1 A 5 A start S A AD 5 2 B A 3 2 1 C 1 F 1 3 D 5 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 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 14 Example Dijkstra s Algorithm 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 15 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 B 2 1 D 3 C 3 1 5 F 1 E 2 8 Loop 9 find w not in S s t D w is a minimum 10 add …
View Full Document
Unlocking...