Shortest Path Routing Link State Distance Vector 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 1 Dijkstra s Shortest Path Algorithm Iterative algorithm After k iterations know least cost path to k nodes S nodes whose least cost path definitively known Initially S u where u is the source node Add one node to S in each iteration D v current cost of path from source to node v Initially D v c u v for all nodes v adjacent to u and D v for all other nodes v Continually update D v as shorter paths are learned 2 Dijsktra s Algorithm 1 Initialization 2 S u 3 for all nodes v 4 if v adjacent to u 5 D v c u v 6 else D v 7 8 Loop 9 find w not in S with the smallest D w 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 3 Dijkstra s Algorithm Example 2 3 2 1 1 4 1 4 4 5 3 1 1 4 1 5 4 1 1 1 2 3 2 2 3 5 4 3 2 3 2 3 2 1 1 1 4 4 5 3 4 Dijkstra s Algorithm Example 2 3 2 1 1 4 1 4 4 5 3 1 1 4 1 5 4 1 1 1 2 3 2 2 3 5 4 3 2 3 2 3 2 1 1 1 4 4 5 3 5 Shortest Path Tree Shortest path tree from u v 3 u 1 2 1 w y 2 4 x s z t 3 link 1 4 5 Forwarding table at u v w x y z s t u v u w u w u v u v u w u w 6 Distance Vector Algorithm c x v cost for direct link from x to v Node x maintains costs of direct links c x v Dx y estimate of least cost from x to y Node x maintains distance vector Dx Dx y y N Node x maintains its neighbors distance vectors For each neighbor v x maintains Dv Dv y y N Each node v periodically sends Dv to its neighbors And neighbors update their own distance vectors Dx y minv c x v Dv y for each node y N Over time the distance vector Dx converges 7 Distance Vector Example Step 1 Optimum 1 hop paths Table for A Table for B Dst Cst Hop Dst Cst Hop A 0 A A 4 A B 4 B B 0 B C C D D 3 D E 2 E E F 6 F F 1 F Table for C E 3 C 1 1 F 2 6 A 1 3 4 D B Table for D Table for E Table for F Dst Cst Hop Dst Cst Hop Dst Cst Hop Dst Cst Hop A A A 2 A A 6 A B B 3 B B B 1 B C 0 C C 1 C C C 1 C D 1 D D 0 D D D E E E 0 E E 3 E F 1 F F F 3 F F 0 F 8 Distance Vector Example Step 2 Optimum 2 hop paths Table for A Table for B Dst Cst Hop Dst Cst Hop A 0 A A 4 A B 4 B B 0 B C 7 F C 2 F D 7 B D 3 D E 2 E E 4 F F 5 E F 1 F Table for C E 3 C 1 1 F 2 6 A 1 3 4 D B Table for D Table for E Table for F Dst Cst Hop Dst Cst Hop Dst Cst Hop Dst Cst Hop A 7 F A 7 B A 2 A A 5 B B 2 F B 3 B B 4 F B 1 B C 0 C C 1 C C 4 F C 1 C D 1 D D 0 D D D 2 C E 4 F E E 0 E E 3 E F 1 F F 2 C F 3 F F 0 F 9 Distance Vector Example Step 3 Optimum 3 hop paths Table for A Table for B Dst Cst Hop Dst Cst Hop A 0 A A 4 A B 4 B B 0 B C 6 E C 2 F D 7 B D 3 D E 2 E E 4 F F 5 E F 1 F Table for C E 3 C 1 1 F 2 6 A 1 3 4 D B Table for D Table for E Table for F Dst Cst Hop Dst Cst Hop Dst Cst Hop Dst Cst Hop A 6 F A 7 B A 2 A A 5 B B 2 F B 3 B B 4 F B 1 B C 0 C C 1 C C 4 F C 1 C D 1 D D 0 D D 5 F D 2 C E 4 F E 5 C E 0 E E 3 E F 1 F F 2 C F 3 F F 0 F 10
View Full Document
Unlocking...