How Distance-Vector (DV) works Each router maintains its shortest distance to every destination via each of its neighbours via B via C to B to C to D From node A Neighbour (next-hop) Destinations distC(A, D): shortest distance from A to D via C A Network Layer44How Distance-Vector (DV) works Each router computes its shortest distance to every destination via any of its neighbors via B via C to B to C to D MIN { distB(A,B), distC(A, B) } A min dist to B to C to D From node A A’s distance vector (DV) Network Layer45How Distance-Vector (DV) works How does A initialize its dist() table and DV? via B via C to B ? ? to C ? ? to D ? ? From node A A min dist to B ? to C ? to D ? A’s DV Network Layer46How Distance-Vector (DV) works A B C Link costs How does A initialize its dist() table and DV? Network Layer47How Distance-Vector (DV) works Each router initializes its dist() table based on its immediate neighbors and link costs via B via C to B c(A,B) ∞ to C ∞ c(A,C) to D ∞ ∞ From node A A B C mindist to B c(A,B) to C c(A,C) to D ∞ A’s DV Network Layer48How Distance-Vector (DV) works Each router sends its DV to its immediate neighbors via B via C to B c(A,B) ∞ to C ∞ c(A,C) to D ∞ ∞ From node A A B C mindist to B c(A,B) to C c(A,C) to D ∞ A’s DV 5 6 2 Network Layer49 Assume that A’s DV is as follows at some later timeHow Distance-Vector (DV) works Routers process received DVs A B C A’s DV mi n to B 5 to C 6 to D 2 via A via C to A 5 ∞ to C 15 1 to D ∞ ∞ From node B B’s DV mindist to A 5 to C 1 to D ∞ Network Layer50How Distance-Vector (DV) works A B C A’s DV mi n to B 5 to C 6 to D 2 via A via C to A 5 ∞ to C 15 1 to D ∞ ∞ From node B B’s DV mindist to A 5 to C 1 to D ∞ new = c(B,A) + mindist(A, C) 11 new = c(B,A) + mindist(A, D) 7 7 Routers process received DVs And repeat… Network Layer51Distance Vector Routing v Each router knows the links to its neighbors v Each router has provisional “shortest path” to every other router -- its distance vector (DV) v Routers exchange this DV with their neighbors v Routers look over the set of options offered by their neighbors and select the best one v Iterative process converges to set of shortest paths Network Layer52Network Layer iterative, asynchronous: each local iteration caused by: v local link cost change v DV update message from neighbor distributed: v each node notifies neighbors only when its DV changes § neighbors then notify their neighbors if necessary wait for (change in local link cost or msg from neighbor) recompute estimates if DV to any dest has changed, notify neighbors each node: Distance vector routing 53Distance Vector v c(i,j): link cost from node i to j v distZ(A,V): shortest dist. from A to V via Z v mindist(A,V): shortest dist. from A to V 0 At node A 1 Initialization: 2 for all destinations V do 3 if V is neighbor of A 4 distV(A, V) = mindist(A,V) = c(A,V); 5 else 6 distV(A, V) = mindist(A,V) = ∞; 7 send mindist(A, *) to all neighbors loop: 8 wait (until A sees a link cost change to neighbor V /* case 1 */ 9 or until A receives mindist(V,*) from neighbor V) /* case 2 */ 10 if (c(A,V) changes by ±d) /* Ü case 1 */ 11 for all destinations Y do 12 distV(A,Y) = distV(A,Y) ± d 13 else /* Ü case 2: */ 14 for all destinations Y do 15 distV(A,Y) = c(A,V) + mindist(V, Y); 16 update mindist(A,*) 15 if (there is a change in mindist(A, *)) 16 send mindist(A, *) to all neighbors 17 forever Network Layer54Distance Vector v c(i,j): link cost from node i to j v distZ(A,V): shortest dist. from A to V via Z v mindist(A,V): shortest dist. from A to V 0 At node A 1 Initialization: 2 for all destinations V do 3 if V is neighbor of A 4 distV(A, V) = mindist(A,V) = c(A,V); 5 else 6 distV(A, V) = mindist(A,V) = ∞; 7 send mindist(A, *) to all neighbors loop: 8 wait (until A sees a link cost change to neighbor V /* case 1 */ 9 or until A receives mindist(V,*) from neighbor V) /* case 2 */ 10 if (c(A,V) changes by ±d) /* Ü case 1 */ 11 for all destinations Y do 12 distV(A,Y) = distV(A,Y) ± d 13 else /* Ü case 2: */ 14 for all destinations Y do 15 distV(A,Y) = c(A,V) + mindist(V, Y); 16 update mindist(A,*) 15 if (there is a change in mindist(A, *)) 16 send mindist(A, *) to all neighbors 17 forever Network Layer55Example: Initialization A C 2 1 7 B 3 D 1 via B via C to A - - to B 2 ∞ to C ∞ 7 to D ∞ ∞ from Node A via A via C via D to A 2 ∞ ∞ to B - - - to C ∞ 1 ∞ to D ∞ ∞ 3 from Node B from Node C via A via B via D to A 7 ∞ ∞ to B ∞ 1 ∞ to C - - - to D ∞ ∞ 1 via B via C to A ∞ ∞ to B 3 ∞ to C ∞ 1 to D - - from Node D min dist to A 0 to B 2 to C 7 to D ∞ min dist 0 2 7 ∞ min dist 2 0 1 3 min dist ∞ 3 1 0 min dist 7 1 0 1Example: C sends update to A via B via C to A - - to B 2 ∞ to C ∞ 7 to D ∞ ∞ from Node A via A via C via D to A 2 ∞ ∞ to B - - - to C ∞ 1 ∞ to D ∞ ∞ 3 from Node B from Node C via A via B via D to A 7 ∞ ∞ to B ∞ 1 ∞ to C - - - to D ∞ ∞ 1 via B via C to A ∞ ∞ to B 3 ∞ to C ∞ 1 to D - - from Node D min dist 0 2 7 ∞ min dist ∞ 3 1 0 min dist 7 1 0 1 A C 2 1 7 B 3 D 1 min dist 2 0 1 3Example: C sends update to A via B via C to A - - to B 2 ∞ to C ∞ 7 to D ∞ ∞ from Node A min dist 0 2 7 ∞ A C 2 1 7 B 3 D 1 min dist 7 1 0 1Example: C sends update to A via B via C to A - - to B 2 8 to C ∞ 7 to D ∞ 8 from Node A min dist 0 2 7 ∞ A C 2 1 7 B 3 D 1 min dist 7 1 0 1Example: C sends update to A via B via C to A - - to B 2 8 to C ∞ 7 to D ∞ 8 from Node A min dist 0 2 7 8 A C 2 1 7 B 3 D 1Example: now B sends update to A via A via C via D to A 2 ∞ ∞ to B - - - to C ∞ 1 ∞ to D ∞ ∞ 3 from Node B from Node C via A via B via D to A 7 ∞ ∞ to B ∞ 1 ∞ to C - - - to D ∞ ∞ 1 via B via C to A ∞ ∞ to B 3 ∞ to C ∞ 1 to D - - from Node D min dist ∞ 3 1 0 min dist 7 1 0 1 A C 2 1 7 B 3 D 1 min dist 2 0 1 3 via B via C to A - - to B 2 8 to C ∞ 7 to D ∞ 8 from Node A min dist 0 2 7 8Example: now B sends update to A via A via C via D to A 2 ∞ ∞ to B - - - to C ∞ 1 ∞ to D ∞ ∞ 3 from Node B from Node C via A via B via D to A 7 ∞ ∞ to B ∞ 1 ∞ to C - - - to D ∞ ∞ 1 via B via C to A ∞ ∞ to B 3 ∞ to C ∞ 1 to D - - from Node D min dist ∞ 3 1 0 min dist 7 1 0 1 A C 2 1 7 B 3 D 1 min dist 2 0 1 3 via B via C to A - - to B 2 8 to C ∞ 7 to D ∞ 8 from Node A min dist 0 2 7 8Example: now B sends update to A via A via C via D to A 2 ∞ ∞ to B - - - to C ∞ 1 ∞ to D ∞ ∞ 3 from Node B from Node C via A via B via D to A 7 ∞ ∞ to B ∞ 1 ∞ to C - - - to D ∞ ∞ 1 via B via C to A ∞ ∞ to B 3 ∞ to C ∞ 1 to D - - from Node D min dist ∞ 3 1 0 min dist 7 1 0 1 A C 2 1 7 B 3 D 1 min dist 2 0 1 3 via B via C to A - - to B 2 8 to C 3 7 to D 5 8 from Node A min dist 0 2 7 8 Make sure you know why this is 5, not 4!Example: now B sends update to A via A via C via D to A 2 ∞ ∞ to B - - - to C ∞ 1 ∞ to D ∞ ∞ 3 from Node B from Node C via A via B via D to A 7 ∞ ∞ to B ∞ 1 ∞ to C - - - to D ∞ ∞ 1 via B via C to A ∞ ∞ to B 3 ∞ to C ∞ 1 to D - - from Node D min dist ∞ 3 1 0 min dist 7 1 0 1 A C 2 1 7 B 3 D 1 min dist 2 0 1 3 via B via C to A - - to B 2 8 to C 3 7 to D 5 8 from Node A min dist 0 2 3 5Example: After 1st Full Exchange via A via C via D to A 2 8 ∞ to B - - - to C 9 1 4 to D ∞ 2 3 from Node B from Node C via A via B via D to A 7 3 ∞ to B 9 1 4 to C - - - to D ∞ 4 1 via B via C to A 5 8 to B 3 2 to C 4 1 to D - - from Node D min dist 5 2 1 0 min dist 3 1 0 1 A C 2 1 7 B 3 D 1 min dist 2 0 1 2 via B via C to A - - to B 2 8 to C 3 7 to D 5 8 from Node A min dist 0 2 3 5 Make sure you understand why some entries are still ∞ All nodes know the best two-hop paths. Make sure you believe thisExample: Now A sends update to B from Node B from Node C from Node D min dist 5 2 1 0 min dist 3 1 0 1 A C 2 1 7 B 3 D 1 min dist 2 0 1 2 from Node A min dist 0 2 3 5 via B via C to A - - to B 2 8 to C 3 7 to D 5 8 via A via B via D to A 7 3 ∞ to B 9 1 4 to C - - - to D ∞ 4 1 via B via C to A 5 8 to B 3 2 to C 4 1 to D - - via A via C via D to A 2 8 ∞ to B - - - to C 9 1 4 to D ∞ 2 3Example: Now A sends update to B via A via C via D to A 2 8 ∞ to B - - - to C 5 1 4 to D 7 2 3 from Node B from Node C from Node D min dist 5 2 1 0 min dist 3 1 0 1 A C 2 1 7 B 3 D 1 min dist 2 0 1 2 from Node A min dist 0 2 3 5 via B via C to A - - to B 2 8 to C 3 7 to D 5 8 Updated via A via B via D to A 7 3 ∞ to B 9 1 4 to C - - - to D ∞ 4 1 via B via C to A 5 8 to B 3 2 to C 4 1 to D - -Example: End of 2nd Full Exchange via A via C via D to A 2 4 8 to B - - - to C 5 1 4 to D 7 2 3 from Node B from Node C from Node D min dist 4 2 1 0 min dist 3 1 0 1 A C 2 1 7 B 3 D 1 min dist 2 0 1 2 from Node A min dist 0 2 3 4 via B via C to A - - to B 2 8 to C 3 7 to D 4 8 via A via B via D to A 7 3 6 to B 9 1 3 to C - - - to D 12 3 1 via B via C to A 5 4 to B 3 2 to C 4 1 to D - - Check Check: All nodes know the best three-hop paths.Example: End of 3nd Full Exchange via A via C via D to A 2 4 7 to B - - - to C 5 1 4 to D 6 2 3 from Node B from Node C from Node D min dist 4 2 1 0 min dist 3 1 0 1 A C 2 1 7 B 3 D 1 min dist 2 0 1 2 from Node A min dist 0 2 3 4 via B via C to A - - to B 2 8 to C 3 7 to D 4 8 via A via B via D to A 7 3 5 to B 9 1 3 to C - - - to D 11 3 1 via B via C to A 5 4 to B 3 2 to C 4 1 to D - - No further change in DVs à Convergence!Intuition v Initial state: best one-hop paths v One simultaneous round: best two-hop paths v Two simultaneous rounds: best three-hop paths v … v Kth simultaneous round: best (k+1) hop paths v Must eventually converge § as soon as it reaches longest best path v …..but how does it respond to changes in cost? The key here is that the starting point is not the initialization, but some other set of entries. Convergence could be different! Network Layer70DV: Link Cost Changes A C A 4 6 C 9 1 Node B A B A 50 5 B 54 1 Node C Link cost changes here A C A 1 6 C 6 1 A B A 50 5 B 54 1 A C A 1 6 C 3 1 A B A 50 5 B 51 1 A C A 1 6 C 3 1 A B A 50 2 B 51 1 B C B 4 51 C 5 50 Node A B C B 1 51 C 2 50 B C B 1 51 C 2 50 B C B 1 51 C 2 50 A C A 1 3 C 3 1 A B A 50 2 B 51 1 B C B 1 51 C 2 50 Stable state A-B changed A sends its DV to B, C B sends its DV to A, C C sends its DV to A, B A C 4 1 50 1 B “good news travels fast” to via Note: none of B’s paths use link (A,C) deduct 3 from distances dist B(A,*) and distA(B,*) Network Layer71DV: Link Cost Changes A C A 4 6 C 9 1 Node B A B A 50 5 B 54 1 Node C Link cost changes here A C A 60 6 C 65 1 A B A 50 5 B 54 1 B C B 4 51 C 5 50 Node A B C B 60 51 C 61 50 Stable state A-B changed A C 4 1 50 60 B to via add 56 to distances dist B(A,*) and distA(B,*) Network Layer72DV: Link Cost Changes A C A 4 6 C 9 1 Node B A B A 50 5 B 54 1 Node C Link cost changes here A C A 60 6 C 65 1 A B A 50 5 B 54 1 A C A 60 6 C 110 1 A B A 50 5 B 101 1 A C A 60 6 C 110 1 A B A 50 7 B 101 1 B C B 4 51 C 5 50 Node A B C B 60 51 C 61 50 B C B 60 51 C 61 50 B C B 60 51 C 61 50 A C A 60 8 C 110 1 A B A 50 7 B 101 1 B C B 60 51 C 61 50 Stable state A-B changed A sends its DV to B, C B sends its DV to A, C C sends its DV to A, B A C 4 1 50 60 B “bad news travels slowly” (not yet converged) to via This is the “Counting to Infinity” Problem Network Layer73The “Poisoned Reverse” Rule v Heuristic to avoid count-to-infinity v If B routes via C to get to A: § B tells C its (B’s) distance to A is infinite (so C won’t route to A via B) Network Layer74DV: Poisoned Reverse A C A 4 6 C 9 1 Node B A B A 50 5 B 54 1 Node C Link cost changes here A C A 60 6 C 65 1 A B A 50 5 B 54 1 B C B 4 51 C 5 50 Node A B C B 60 51 C 61 50 Stable state A-B changed A C 4 1 50 60 B to via If B routes through C to get to A: B tells C its (B’s) distance to A is infinite ∞ ∞ Network Layer75DV: Poisoned Reverse A C A 4 6 C 9 1 Node B A B A 50 5 B 54 1 Node C Link cost changes here A C A 60 6 C 65 1 A B A 50 5 B 54 1 A C A 60 6 C 110 1 A B A 50 5 B 101 1 A C A 60 6 C 110 1 A B A 50 7 B 101 1 B C B 4 51 C 5 50 Node A B C B 60 51 C 61 50 B C B 60 51 C 61 50 B C B 60 51 C 61 50 Stable state A-B changed A sends its DV to B, C B sends its DV to A, C A C 4 1 50 60 B to via If B routes through C to get to A: B tells C its (B’s) distance to A is infinite ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ Network Layer76DV: Poisoned Reverse A C A 4 6 C 9 1 Node B A B A 50 5 B 54 1 Node C Link cost changes here A C A 60 6 C 65 1 A B A 50 5 B 54 1 A C A 60 6 C 110 1 A B A 50 5 B 101 1 A C A 60 6 C 110 1 A B A 50 61 B 101 1 B C B 4 51 C 5 50 Node A B C B 60 51 C 61 50 B C B 60 51 C 61 50 B C B 60 51 C 61 50 Stable state A-B changed A sends its DV to B, C B sends its DV to A, C A C 4 1 50 60 B to via If B routes through C to get to A: B tells C its (B’s) distance to A is infinite ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ Network Layer77DV: Poisoned Reverse A C A 4 6 C 9 1 Node B A B A 50 5 B 54 1 Node C Link cost changes here A C A 60 6 C 65 1 A B A 50 5 B 54 1 A C A 60 6 C 110 1 A B A 50 5 B 101 1 A C A 60 6 C 110 1 A B A 50 61 B 101 1 B C B 4 51 C 5 50 Node A B C B 60 51 C 61 50 B C B 60 51 C 61 50 B C B 60 51 C 61 50 A B A 50 61 B 101 1 B C B 60 51 C 61 50 Stable state A-B changed A sends its DV to B, C B sends its DV to A, C C sends its DV to A, B A C 4 1 50 60 B to via If B routes through C to get to A: B tells C its (B’s) distance to A is infinite ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ A C A 60 51 C 110 1 Converges after C receives another update from B ∞ 78Will Poison-Reverse Completely Solve the Count-to-Infinity Problem? A 1 C D B 1 1 1 1 1 2 2 ∞ ∞ ∞ 100 100 100 3 ∞ 4 ∞ 4 5 6 Numbers in blue denote the best cost to destination D advertised along the link Network Layer 79Network Layer Comparison of LS and DV algorithms message complexity v LS: with n nodes, E links, O(nE) msgs sent v DV: exchange between neighbors only § convergence time varies speed of convergence v LS: O(n2) algorithm requires O(nE) msgs § may have oscillations v DV: convergence time varies § may be routing loops § count-to-infinity problem robustness: what happens if router malfunctions? LS: § node can advertise incorrect link cost § each node computes only its own table DV: § DV node can advertise incorrect path cost § each node’s table used by others • error propagate thru network 80Network Layer Real Protocols Link State Open Shortest Path First (OSPF) Intermediate system to intermediate system (ISIS) Distance Vector Routing Information Protocol (RIP) Interior Gateway Routing Protocol (IGRP-Cisco) Border Gateway Protocol (BGP) 81