Distance Vector Algorithm

1 Distance Vector Algorithm Bellman-Ford Equation (dynamic programming). Define dx(y) := cost of least-cost path from x to y Then dx(y) = min v {c(x,v) + dv(y) }. where min is taken over all neighbors v of x Network Layer 4-1. Bellman-Ford example 5. 3. Clearly, dv(z) = 5, dx(z) = 3, dw(z) = 3. v w 5. 2. u 2 1 z B-F equation says: 3. 1 2 du(z) = min { c(u,v) + dv(z), x y 1 c(u,x) + dx(z), c(u,w) + dw(z) }. = min {2 + 5, 1 + 3, 5 + 3} = 4. Node that achieves minimum is next hop in shortest path forwarding table Network Layer 4-2. 1. Distance Vector Algorithm Dx(y) = estimate of least cost from x to y Node x knows cost to each neighbor v: c(x,v).

2 Node x maintains Distance Vector Dx =. [Dx(y): y N ]. Node x also maintains its neighbors'. Distance vectors For each neighbor v, x maintains Dv = [Dv(y): y N ]. Network Layer 4-3. Distance Vector Algorithm (4). Basic idea: Each node periodically sends its own Distance Vector estimate to neighbors When a node x receives new DV estimate from neighbor, it updates its own DV using B-F equation: Dx(y) minv{c(x,v) + Dv(y)} for each node y N. Under minor, natural conditions, the estimate Dx(y) converge to the actual least cost dx(y). Network Layer 4-4. 2. Distance Vector Algorithm (5). Iterative, asynchronous: Each node: each local iteration caused by: local link cost change wait for (change in local link DV update message from cost or msg from neighbor).

3 Neighbor Distributed: recompute estimates each node notifies neighbors only when its DV. changes if DV to any dest has neighbors then notify changed, notify neighbors their neighbors if necessary Network Layer 4-5. Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} Dx(z) = min{c(x,y) +. = min{2+0 , 7+1} = 2 Dy(z), c(x,z) + Dz(z)}. node x table = min{2+1 , 7+0} = 3. cost to cost to x y z x y z x 0 2 7 x 0 2 3. from from y y 2 0 1. z z 7 1 0. node y table cost to x y z y 2 1. x . x z y 2 0 1 7. from z . node z table cost to x y z x . from y . z 71 0. time Network Layer 4-6. 3. Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} Dx(z) = min{c(x,y) +. = min{2+0 , 7+1} = 2 Dy(z), c(x,z) + Dz(z)}.

4 Node x table = min{2+1 , 7+0} = 3. cost to cost to cost to x y z x y z x y z x 0 2 7 x 0 2 3 x 0 2 3. from from y y 2 0 1. from y 2 0 1. z z 7 1 0 z 3 1 0. node y table cost to cost to cost to x y z x y z x y z y 2 1. x x 0 2 7 x 0 2 3 x z from y 2 0 1 y 2 0 1 7. from from y 2 0 1. z z 7 1 0 z 3 1 0. node z table cost to cost to cost to x y z x y z x y z x x 0 2 7 x 0 2 3. from from y 2 0 1 y 2 0 1. from y . z 71 0 z 3 1 0 z 3 1 0. time Network Layer 4-7. Distance Vector : link cost changes Link cost changes: 1. node detects local link cost change y 4 1. updates routing info, recalculates x z Distance Vector 50. if DV changes, notify neighbors At time t0, y detects the link-cost change, updates its DV, and informs its neighbors.

5 Good At time t1, z receives the update from y and updates its table. news It computes a new least cost to x and sends its neighbors its DV. travels fast At time t2, y receives z's update and updates its Distance table. y's least costs do not change and hence y does not send any message to z. Network Layer 4-8. 4. Distance Vector : link cost changes Link cost changes: 60. good news travels fast y 4 1. bad news travels slow - count to infinity problem! x z 50. 44 iterations before Algorithm stabilizes: see text 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?

6 Network Layer 4-9. Comparison of LS and DV algorithms Message complexity Robustness: what happens LS: with n nodes, E links, if router malfunctions? O(nE) msgs sent LS: DV: exchange between node can advertise neighbors only incorrect link cost convergence time varies each node computes only Speed of Convergence its own table LS: O(n2) Algorithm requires DV: O(nE) msgs DV node can advertise may have oscillations incorrect path cost DV: convergence time varies each node's table used by may be routing loops others error propagate thru count-to-infinity problem network Network Layer 4-10. 5. Chapter 4: Network Layer 4. 1 Introduction routing algorithms Virtual circuit and Link state datagram networks Distance Vector Hierarchical routing What's inside a router routing in the IP: Internet Internet RIP.

7 protocol . OSPF. Datagram format BGP. IPv4 addressing ICMP Broadcast and IPv6 multicast routing Network Layer 4-11. Hierarchical routing Our routing study thus far - idealization all routers identical network flat . not true in practice scale: with 200 million administrative autonomy destinations: internet = network of can't store all dest's in networks routing tables! each network admin may routing table exchange want to control routing in its would swamp links! own network Network Layer 4-12. 6. Hierarchical routing aggregate routers into Gateway router regions, autonomous Direct link to router in systems (AS). another AS. routers in same AS run same routing protocol intra-AS routing protocol routers in different AS.

8 Can run different intra- AS routing protocol Network Layer 4-13. Interconnected ASes 3c 3a 2c 3b 2a AS3 2b 1c AS2. 1a 1b 1d AS1. forwarding table configured by both intra- and inter-AS. Intra-AS. routing Inter-AS. routing routing Algorithm intra-AS sets entries Algorithm Algorithm . Forwarding for internal dests inter-AS & Intra-As table . sets entries for external dests Network Layer 4-14. 7. Inter-AS tasks AS1 must: suppose router in AS1 1. learn which dests receives datagram reachable through dest outside of AS1 AS2, which through router should AS3. forward packet to 2. propagate this gateway router, but reachability info to all which one?

9 Routers in AS1. Job of inter-AS routing ! 3c 3a 2c 3b 2a AS3 2b 1c AS2. 1a 1b 1d AS1. Network Layer 4-15. Example: Setting forwarding table in router 1d suppose AS1 learns (via inter-AS protocol ) that subnet x reachable via AS3 (gateway 1c) but not via AS2. inter-AS protocol propagates reachability info to all internal routers. router 1d determines from intra-AS routing info that its interface I is on the least cost path to 1c. installs forwarding table entry (x,I). 3c x 3a 2c 3b 2a AS3 2b 1c AS2. 1a 1b AS1. 1d Network Layer 4-16. 8. Example: Choosing among multiple ASes now suppose AS1 learns from inter-AS protocol that subnet x is reachable from AS3 and from AS2.

10 To configure forwarding table, router 1d must determine towards which gateway it should forward packets for dest x. this is also job of inter-AS routing protocol ! 3c x . 3a 2c 3b 2a AS3 2b 1c AS2. 1a 1b 1d AS1. Network Layer 4-17. Example: Choosing among multiple ASes now suppose AS1 learns from inter-AS protocol that subnet x is reachable from AS3 and from AS2. to configure forwarding table, router 1d must determine towards which gateway it should forward packets for dest x. this is also job of inter-AS routing protocol ! hot potato routing : send packet towards closest of two routers. Use routing info Determine from Learn from inter-AS Hot potato routing : forwarding table the from intra-AS.