Slide #1.

Distance Vector Routing Computer Networks A15
More slides like this


Slide #2.

DV Routing Outline     Internet Context Network Layer Routing (**K&R slides) Quick Routing Overview Distance Vector Routing (my version) – Adapted from Tanenbaum & Perlman Texts  Distance Vector Routing (K&R version) Computer Networks Distance Vector Routing 2
More slides like this


Slide #3.

Internet Context Computer Networks Distance Vector Routing
More slides like this


Slide #4.

Metropolitan Area Network (MAN) Organization Servers Gatewa y To the Internet or wide area network s Backbon e R R Departmental Server R s R S S S R R s s s s s s s s s Leon-Garcia & Widjaja: Communication Networks Computer Networks Distance Vector Routing 4
More slides like this


Slide #5.

Wide Area Network (WAN) Interdomain level Border routers Autonomous system or domain Border routers Internet service provider LAN level Leon-Garcia & Widjaja: Communication Networks Intradomain level Computer Networks Distance Vector Routing 5
More slides like this


Slide #6.

Modern Internet Backbone National service provider A National service provider B NAP NAP National service provider C Network Access Point National Internet Service Providers Leon-Garcia & Widjaja: Communication Networks Computer Networks Distance Vector Routing 6
More slides like this


Slide #7.

Network Access Point NAP RA Route server RB LAN RC Leon-Garcia & Widjaja: Communication Networks Computer Networks Distance Vector Routing 7
More slides like this


Slide #8.

Network Layer Routing Computer Networks Distance Vector Routing
More slides like this


Slide #9.

Network Layer      transport segment from sending to receiving host. on sending side, encapsulates segments into datagram packets. on receiving side, delivers segments to transport layer. network layer protocols in every host and router. router examines Computer header fields inNetworks all IP applicatio n transport network data link physical network data link physical network data link physical network data link physical network data link physical network data link physical network network data link data link physical physical network data link physical network data link physical network data link physical network data link physical applicatio n transport network data link physical K&R Distance Vector Routing 9
More slides like this


Slide #10.

Two Key Network Layer Functions   forwarding: move analogy: packets from  routing: process of router’s input to planning trip from appropriate source to router output. destination routing: determine route taken by packets from source to destination. Computer Networks  forwarding: process of getting through single interchange Distance Vector Routing 10
More slides like this


Slide #11.

Interplay between Routing and Forwarding routing algorithm local forwarding table header value output link 0100 0101 0111 1001 3 2 2 1 value in arriving packet’s header 0111 1 3 2 Computer Networks Distance Vector Routing 11
More slides like this


Slide #12.

Router Node node 15 packet packet Incoming Link 17 Outgoing Link Router Buffer Computer Networks Server Distance Vector Routing 12
More slides like this


Slide #13.

The Internet Network Layer Host, router network layer functions: Transport Layer: TCP, UDP Network Layer IP protocol • addressing conventions • datagram format • packet handling conventions Routing protocols • path selection • RIP, OSPF, BGP forwarding table ICMP protocol • error reporting • router “signaling” Data Link Layer Physical Layer Computer Networks Distance Vector Routing 13
More slides like this


Slide #14.

Quick Routing Overview Computer Networks Distance Vector Routing
More slides like this


Slide #15.

Routing Routing algorithm:: that part of the Network Layer responsible for deciding on which output line to transmit an incoming packet. Remember: For virtual circuit subnets the routing decision is made ONLY at set up. Algorithm properties:: correctness, simplicity, robustness, stability, fairness, optimality, and scalability. Computer Networks Distance Vector Routing 15
More slides like this


Slide #16.

Routing Classification Adaptive Routing based on current measurements of traffic and/or topology. 1. centralized 2. isolated 3. distributed Computer Networks Non-Adaptive Routing routing computed in advance and off-line 1. flooding 2. static routing using shortest path algorithms Distance Vector Routing 16
More slides like this


Slide #17.

Internetwork Routing [Halsall] Adaptive Routing Centralized [RCC] Distributed [IGP] Intradomain routing Interior Gateway Protocols Isolated Interdomain routing[EGP] [BGP,IDRP] Exterior Gateway Protoco Distance Vector routing Link State routing [RIP] [OSPF,IS-IS,PNNI] Computer Networks Distance Vector Routing 17
More slides like this


Slide #18.

Adaptive Routing Design Design Issues: 1. How much overhead is incurred due to gathering the routing information and sending routing packets? 2. What is the time frame (i.e, the frequency) for sending routing packets in support of adaptive routing? 3. What is the complexity of the routing strategy? Computer Networks Distance Vector Routing 18
More slides like this


Slide #19.

Adaptive Routing Basic functions: 1. Measurement of pertinent network data. 2. Forwarding of information to where the routing computation will be done. 3. Compute the routing tables. 4. Convert the routing table information into a routing decision and then dispatch the data packet. Computer Networks Distance Vector Routing 19
More slides like this


Slide #20.

Centralized Routing A W RCC B Z Computer Networks Distance Vector Routing 20
More slides like this


Slide #21.

Distance Vector Routing {Tanenbaum & Perlman version} Computer Networks Distance Vector Routing
More slides like this


Slide #22.

Distance Vector Routing Historically known as the old ARPANET routing algorithm {or known as Bellman-Ford (BF) algorithm}. BF Basic idea: each router maintains a Distance Vector table containing the distance between itself and ALL possible destination nodes. Distances,based on a chosen metric, are computed using information from the neighbors’ distance vectors. Computer Networks Distance Vector Routing 22
More slides like this


Slide #23.

Distance Vector Routing 1. 2. Information kept by DV router each router has an ID associated with each link connected to a router, there is a link cost (static or dynamic). Distance Vector Table Initialization Distance to itself = 0 Distance to ALL other routers = infinity number Computer Networks Distance Vector Routing 23
More slides like this


Slide #24.

Distance Vector Algorithm [Perlman] 1. 2. 3. A router transmits its distance vector to each of its neighbors in a routing packet. Each router receives and saves the most recently received distance vector from each of its neighbors. A router recalculates its distance vector when: a. It receives a distance vector from a neighbor containing different information than before. b. It discovers that a link to a neighbor has gone down (i.e., a topology change). The DV calculation is based on minimizing the cost to each Computer Networks Distance Vector Routing 24
More slides like this


Slide #25.

Distance Vector Example Figure 5-9.(a) A subnet. (b) Input from A, I, H, K, and the new routing table for J. Tanenbaum 25
More slides like this


Slide #26.

Distance Vector Routing {Kurose & Ross version} Computer Networks Distance Vector Routing
More slides like this


Slide #27.

Distance Vector Algorithm Bellman-Ford Equation (dynamic programming) Define dx(y) := cost of least-cost path from x to y Then v dx(y) = min {c(x,v) + dv (y)} where min is taken over all neighbors v of x. Computer Networks Distance Vector Routing 27
More slides like this


Slide #28.

Bellman-Ford Example 5 u 2 v 2 3 w 3 1 Clearly, dv(z) = 5, dx(z) = 3, dw(z) = 3 5 z B-F equation says: du(z) = min { c(u,v) + dv(z), 1 c(u,x) + dx(z), c(u,w) + dw(z) } = min {2 + 5, 1 + 3, The node that achieves minimum is next5 + 3} = 4 hop in shortest path ➜ forwarding table. Namely, packets from u destined for z are forwarded out link between u and x. 1 x y 2 Computer Networks Distance Vector Routing 28
More slides like this


Slide #29.

Distance Vector Algorithm (3)     Dx(y) = estimate of least cost from x to y Node x knows cost to each neighbor v: c(x,v) 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 ] Computer Networks Distance Vector Routing 29
More slides like this


Slide #30.

Distance Vector Algorithm (4) DV Basic idea:  From time-to-time, each node sends its own distance vector estimate to neighbors.  Asynchronous  When a node x receives a new DV estimate from any neighbor v, it saves v’s distance vector and it updates its own DV using B-F equation: Dx(y) ← min {c(x,v) + Dv(y)} for each node y ∊ N v  Under minor, natural conditions, the estimate Dx(y) converges to the actual least cost dx(y). Computer Networks Distance Vector Routing 30
More slides like this


Slide #31.

Distance Vector Algorithm (5) Iterative, asynchronous: each   local iteration caused by: local link cost change DV update message from neighbor Distributed:  each node notifies neighbors only when its DV changes – neighbors then notify their neighbors if necessary. Computer Networks Each node: wait for (change in local link cost or msg from neighbor) recompute estimates if DV to any destination has changed, notify neighbors Distance Vector Routing 31
More slides like this


Slide #32.

from x 0 2 7 y ∞∞ ∞ z ∞∞ ∞ node y table cost to x y z from Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)} = min{2+0 , 7+1} = 2 node x table = min{2+1 , 7+0} = 3 cost to cost to x y z x y z x 0 2 3 y 2 0 1 z 7 1 0 2 x ∞∞ ∞ y 2 0 1 z ∞∞ ∞ node z table cost to x y z from from x x ∞∞ ∞ y ∞ ∞ ∞ z 7 1 0 Computer Networks y 7 1 z time Distance Vector Routing 32
More slides like this


Slide #33.

Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)}Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)} = min{2+0 , 7+1} = 2 node x table = min{2+1 , 7+0} = 3 x 0 2 7 y ∞∞ ∞ z ∞∞ ∞ node y table ∞ cost to x y z x 0 2 3 y 2 0 1 z 7 1 0 x 0 2 3 y 2 0 1 z 3 1 0 x 0 2 7 y 2 0 1 z 7 1 0 x 0 2 3 y 2 0 1 z 3 1 0 from from cost to x y z x 0 2 7 y 2 0 1 z 3 1 0 Computer Networks 2 x y 7 1 z cost to x y z from x ∞∞ ∞ y ∞ ∞ ∞ z 71 0 cost to x y z cost to x y z from from from x ∞ ∞ ∞ y 2 0 1 z ∞∞ ∞ node z table cost to x y z from cost to x y z from cost to x y z from cost to x y z x 0 2 3 y 2 0 1 z 3 1 0 time Distance Vector Routing 33
More slides like this


Slide #34.

Distance Vector: Link Cost Changes Link cost changes:  node detects local link cost change.  updates routing info, recalculates 1 y 4 1 x 50 z distance vector. At time t0, y detects the link-cost change, updates  if DV changes, it notifies its DV, and informs its neighbors. neighbors . “good At time t1, z receives the update from y and updates its news table. travels It computes a new least cost to x and sends its neighbors At time t2, y receives z’s update and updates its distance its DV. fast” table. y’s least costs do not change and hence y does not send any message to z. Computer Networks Distance Vector Routing 34
More slides like this


Slide #35.

Distance Vector: Link Cost Changes Link cost changes:  good news travels fast  bad news travels slow - “count to infinity” problem!  44 iterations before algorithm stabilizes: see text! 60 y 4 1 x 50 z 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? Computer Networks Distance Vector Routing 35
More slides like this


Slide #36.

Distance Vector Summary The Network Layer is responsible for routing and forwarding. The routing process is used to build forwarding lookup tables. Forwarding uses the lookup table to move an incoming packet to the correct outgoing link queue. Routing algorithms use link cost metrics such as hops or delay. Distance Vector (DV) is an intradomain adaptive routing algorithm that does not scale well. Computer Networks Distance Vector Routing 36
More slides like this


Slide #37.

Distance Vector Summary DV (originally the old ARPA algorithm) employs the Bellman-Ford shortest path algorithm and currently is used in the RIP, RIP-2, BGP, ISO IDRP and Novell IPX protocols. DV routers: • keep distances to ALL intranet routers in a distance vector which is periodically updated and transmitted to each of its neighbors. • reacts to changes in its neighbors’ distance vectors and to topology changes (i.e., nodes and/or links coming up or going down). In distance vector routing “bad news travels slowly and good news travels quickly”. Computer Networks Distance Vector Routing 37
More slides like this