Distance Vector: link cost changes Link cost changes o node detects local link cost change o updates distance table (line 15) o if cost change in least cost path, 50 notify neighbors(lines 23, 24) vIa D x Z x Z algorithn good terminates X(4)6 6 news travels via X DI XY X fast X50 X50 x50(2 x|50(2 c(X,Y) change Network le 4-26
Network Layer 4-26 Distance Vector: link cost changes Link cost changes: node detects local link cost change updates distance table (line 15) if cost change in least cost path, notify neighbors (lines 23,24) X Z 4 1 50 Y 1 algorithm terminates “good news travels fast
Distance Vector: link cost changes Link cost changes g good news travels fast a bad news travels slow Z count to infinity"problem 50 vIa D X Z D x Z D X Z x Z D x Z algorithn x|④6x1606x60⑥x160(x60( continues on vIa X Y 子1xy1x X50 X|50 X50 ⑦ X50 ⑦ x|50(9 (X,Y) time change Network Layer 4-27
Network Layer 4-27 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: poisoned reverse If Z routes through y to get to x: 60 g Z tells y its(z's)distance to X is infinite( so y won't route to x via Z) o will this completely solve count to 50 infinity problem? VIa algorithm d'Ixz DI Z DIX Z DIx z DIx z terminates x|④=x10∞x∞x606x606 vIa X X Y X Y X5⑥x|661x|(61xG xn t change e Network le 4-28
Network Layer 4-28 Distance Vector: poisoned reverse If Z routes through Y to get to X : Z tells Y its (Z’s) distance to X is infinite (so Y won’t route to X via Z) will this completely solve count to infinity problem? X Z 4 1 50 Y 60 algorithm terminates
Comparison of ls and dv algorithms Message complexity Robustness: what happens O LS: with n nodes, e links if router malfunctions? O(nE)msgs sent each LS: 口DV: exchange between o node can advertise ne ighbors only incorrect link cost o convergence time varies o each node computes only Speed of convergence its own table o LS: O(n )algorithm requires DV: O(nE)msgs o DV node can advertise o may have oscillations incorrect path cost o DV: convergence time varies o each node's table used by o may be routing loops others o count-to-infinity problem error propagate thru network Network Layer 4-29
Network Layer 4-29 Comparison of LS and DV algorithms Message complexity LS: with n nodes, E links, O(nE) msgs sent each DV: exchange between neighbors only convergence time varies Speed of Convergence LS: O(n2) algorithm requires O(nE) msgs may have oscillations 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
Chapter 4 roadmap 4. 1 Introduction and Network Service Models 4.2 Routing Principles 4.3 Hierarchical Routing 4.4 The Internet(Ip) protocol 4.5 Routing in the Internet 4.6 What's Inside a router 4.7 IPv6 4.8 Multicast Routing 4.9 Mobility Network Layer 4-30
Network Layer 4-30 Chapter 4 roadmap 4.1 Introduction and Network Service Models 4.2 Routing Principles 4.3 Hierarchical Routing 4.4 The Internet (IP) Protocol 4.5 Routing in the Internet 4.6 What’s Inside a Router 4.7 IPv6 4.8 Multicast Routing 4.9 Mobility