What we have learnt so far Sending IP packets from source to destination through a series of routers Router looks up destination IP address in a table Forwards the packet to the corresponding next hop Shortest Path Routing Sending Ethernet frames from source to destination through a series of switches Reading Sections P D 4 2 Switch looks up destination MAC address in a table Forwards the frame on the corresponding port EE122 Intro to Communication Networks Fall 2006 MW 4 00 5 30 in Donner 155 What important task did we NOT talk about Vern Paxson How are these forwarding tables filled with information Routing TAs Dilip Antony Joseph and Sukun Kim http inst eecs berkeley edu ee122 Materials with thanks to Jennifer Rexford Ion Stoica and colleagues at Princeton and UC Berkeley What about self learning in switches 1 What is Routing 2 Why Does Routing Matter A famous quotation from RFC 791 We need good end to end performance A name indicates what we seek An address indicates where it is A route indicates how we get there Jon Postel Find the shortest best path 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 3 Know Thy Network Modeled as a graph Routers nodes Link edges 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 Edge cost delay congestion level E g Protocol OSPF 5 2 A 3 B 2 D C 3 1 Every router knows the complete network structure Independently calculates routes Distance Vector Routing Problems with this approach E g Algorithm Bellman Ford Distributed only local state 4 Modeling a Network Routing requires knowledge of the network structure Distributed global state Failures maintenance and load balancing Limit packet loss and delay during changes 1 5 F 1 E 2 E g Protocol RIP Goal of Routing Every router knows only about its neighboring routers Independently calculates routes Problems with this approach 5 Determine a good path through the network from source to destination Good means usually the shortest path 6 1 Link State Routing Dijkstra s Shortest Path Algorithm Each router has a complete picture of the network C A Host A Host CA D B E N2 D B Host B Host D B C A Named after Edsger W Dijkstra 1930 2002 E E D N3 C A D D B N1 C A C N5 E B E C A A D B N4 N6 B E C D HostE E N7 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 INPUT Dijkstra s Shortest Path Algorithm 8 Dijsktra s Algorithm 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 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 D v min D v D w c w v new cost to v is either old cost to v or known shortest path cost to w plus cost from w to v 13 until all nodes in S c i j link cost from node i to j cost infinite if not direct neighbors 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 1 E F 2 least cost path definitively known Source 9 Example Dijkstra s Algorithm start S A A B 2 1 D 3 C 3 1 5 1 E F 2 10 Example Dijkstra s Algorithm D B p B D C p C D D p D D E p E D F p F 2 A 5 A 1 A 5 2 Least cost paths from one node source to all other nodes 7 Notation Step 0 1 2 3 4 5 Net topology link costs known to all nodes OUTPUT 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 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 5 A 1 A 4 D 2 D start S A AD 5 2 A 2 1 11 B D 3 C 3 1 5 1 E F 2 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 D v min D v D w c w v 13 until all nodes in S 12 2 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 5 A 1 A 4 D 2 D 3 E 4 E start S A AD ADE 3 B 2 2 1 C D 5 1 3 F 2 E 1 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 D v min D v D w c w v 13 until all nodes in S 5 A Example Dijkstra s Algorithm D B p B D C p C D D p D D E p E D F p F 2 A 5 A 1 A 4 D 2 D 3 E 4 E start S A AD ADE ADEB 5 2 3 B A 2 1 C D 1 5 1 3 E F 2 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 D v min D v D w c w v 13 until all nodes in S 13 Example Dijkstra s Algorithm 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 D v min D v D w c w v 13 until all nodes in S 5 3 B 2 A 2 1 C 5 1 3 D Example Dijkstra s …
View Full Document
Unlocking...