Iteration #1 Optimum 2-hop paths Table for a Table for b Dst Cst Hop Dst Cst Hop 3 A ABC 047725 ABFBEE BCDEF 40234 ABFDFF 6 D 4 EF B Table for c 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 A 2 B F 731 AFF 511 C 0 CC BBCD D|1 D 0 E DFF E BCDEF 44 E ABCDEF 230 BBCCEF F1 F 2 F 9/28/2006 Lecture 10: Intra-Domain Routing
9/28/2006 Lecture 10: Intra-Domain Routing 11 Iteration #1 Table for A Dst Cst Hop A 0 A B 4 B C 7 F D 7 B E 2 E F 5 E Table for B Dst Cst Hop A 4 A B 0 B C 2 F D 3 D E 4 F F 1 F Table for C Dst Cst Hop A 7 F B 2 F C 0 C D 1 D E 4 F F 1 F Table for D Dst Cst Hop A 7 B B 3 B C 1 C D 0 D E – F 2 C Table for E Dst Cst Hop A 2 A B 4 F C 4 F D – E 0 E F 3 F Table for F Dst Cst Hop A 5 B B 1 B C 1 C D 2 C E 3 E F 0 F Optimum 2-hop paths A E F C D B 2 3 6 4 1 1 1 3
Iteration #2 Optimum 3-hop paths Table for a Table for b Dst Cst Hop Dst Cst Hop 3 A 0 A A C6E 725 BEE BCDEF 40234 ABFDFF 6 D 4 EF B Table for c Table for d Table for e Table for f Dst Cst Hop Dst Cst Hop Dst Cst Hop Dst Cst Hop A b2 FF A A 2 731 511 C 0 CC D|1 D E DFF E 052 BBCDCc BCDEF 44503 AFFFEF ABCDEF 230 BBCCEF F1 F 9/28/2006 Lecture 10: Intra-Domain Routing 12
9/28/2006 Lecture 10: Intra-Domain Routing 12 Iteration #2 Table for A Dst Cst Hop A 0 A B 4 B C 6 E D 7 B E 2 E F 5 E Table for B Dst Cst Hop A 4 A B 0 B C 2 F D 3 D E 4 F F 1 F Table for C Dst Cst Hop A 6 F B 2 F C 0 C D 1 D E 4 F F 1 F Table for D Dst Cst Hop A 7 B B 3 B C 1 C D 0 D E 5 C F 2 C Table for E Dst Cst Hop A 2 A B 4 F C 4 F D 5 F E 0 E F 3 F Table for F Dst Cst Hop A 5 B B 1 B C 1 C D 2 C E 3 E F 0 F Optimum 3-hop paths A E F C D B 2 3 6 4 1 1 1 3
Distance Vector: Link Cost Changes Link cost changes Node detects local link cost change Updates distance table If cost change in least cost path, notify □ 50 neighbors vIa D x Z x Z algorithm terminates good x|④6 6 news travels via X DI XY X fast X50 X50 X|50(2 x|50(2 c(X,Y) change 9/28/2006 Lecture 10: Intra-Domain routing 13
9/28/2006 Lecture 10: Intra-Domain Routing 13 Distance Vector: Link Cost Changes Link cost changes: • Node detects local link cost change • Updates distance table • If cost change in least cost path, notify neighbors X Z 4 1 50 Y 1 algorithm terminates “good news travels fast
Distance Vector: Link Cost Changes Link cost changes: 60 Good news travels fast Bad news travels slow count to infinity" problem 50 vIa D X Z D x Z D X Z x Z D x Z algorith x|④6x160x60⑥x|608 X 60(8 continues vIa X Y 子1xy1x X50 X|50 X50 ⑦ X50 ⑦ x|50(9 (X,Y) time change 9/28/2006 Lecture 10: Intra-Domain routing 14
9/28/2006 Lecture 10: Intra-Domain Routing 14 Distance Vector: Link Cost Changes Link cost changes: • Good news travels fast • Bad news travels slow - “count to infinity” problem! X Z 4 1 50 Y 60 algorithm continues on!
Distance Vector Split Horizon If Z routes through Y to get to X 60 z does not advertise its route to x back to y 50 algorithm VIa X Z D X Z Dx Z D Z terminates ④?x16?x16?x16061 vIa X Y X X X50 X50 ⑥x|6061X| C(X,Y) time change 9/28/2006 Lecture 10: Intra-Domain routing 15
9/28/2006 Lecture 10: Intra-Domain Routing 15 Distance Vector: Split Horizon If Z routes through Y to get to X : • Z does not advertise its route to X back to Y algorithm terminates X Z 4 1 50 Y 60 ? ? ?