Routing:
Distance Vector Algorithm
Networking
CS 3470, Section 1
Review
So how is routing different from forwarding?
Routing
Network as a Graph
5
3
B C
2 5
A 2 1 F
3
1 2
D E
1
The basic problem of routing is to find the
lowest-cost path between any two nodes
Where the cost of a path equals the sum of the costs
of all the edges that make up the path
Routing
Routing protocols need to be both dynamic
and distributed
Deal with node and link failures, changing link
costs, and scalability
4
Distributed Routing Algorithms
Two standard distributed routing algorithms
Link state routing
Distance vector routing
What link state routing protocol did we
discuss last time?
5
Link State vs Distance Vector
Both assume that
The address of each neighbor is known
The cost of reaching each neighbor is known
Both find global information
By exchanging routing info among neighbors
Differ in info exchanged and route computation
LS: tells every other node its distance to neighbors
DV: tells neighbors its distance to every other node
6
Distance Vector Routing
A router tells neighbors its distance to every
router
Communication between neighbors only
Each router maintains a distance table
A row for each possible destination
A column for each neighbor
DX(Y,Z) : distance from X to Y via Z
7
Distance Vector Routing
Given a distance table we can find the
shortest distance to a destination
i.e., the smallest value in the row corresponding
to the destination.
A list of <destination, shortest distance>
tuples is called a distance vector
Current least cost to each destination
Exchanged between neighbors
Based on Bellman-Ford algorithm
Computes “shortest paths”
8
Distance Table: Example
Distance table at router E
cost to destination via
E
D () A B D
A 1 14 5
B 1 C
7
B 7 8 5
A 8 2
1
E D C 6 9 4
2
D 4 11 2
If E were to advertise its distance vector, it
would send <A,1>,<B,5>,<C,4>,<D,2>
9
Distance Table to Routing Table
cost to destination via Outgoing link
E
D () A B D to use, cost
A A A,1
1 14 5
B B D,5
7 8 5
C C D,4
6 9 4
D D D,2
4 11 2
Distance table Routing table
10
Distance Vector Routing
Algorithm
Now the real question…
How do we compute this distance table?
That’s where we use Bellman-Ford algorithm.
11
Distance Vector Routing
Algorithm
iterative: Distance Table data
continues until no nodes structure
exchange info. each node has its own
self-terminating: no “signal” to row for each possible destination
stop column for each directly-attached
asynchronous: neighbor to node
example: in node X, for dest. Y
nodes need not exchange
via neighbor Z:
info/iterate in lock step!
distributed: distance from X to
X = Y, via Z as next hop
each node talks only with D (Y,Z)
directly-attached neighbors Z
= c(X,Z) + minw{D (Y,w)}
12
Distance Vector Routing: Overview
Each node:
Iterative, asynchronous:
each iteration caused by:
local link cost change wait for (change in local link
cost or msg from neighbor)
message from neighbor: its
least cost path change from
neighbor
recompute distance table
Distributed:
each node notifies neighbors
only when its least cost path to if least cost path to any dest
any destination changes has changed, notify
neighbors then notify their neighbors
neighbors if necessary
13
Distance Vector Algorithm: Example
Y
2 1
X Z X Z
7 D (Y,Z) = c(X,Z) + minw {D (Y,w)}
= 7+1 = 8
X Y
D (Z,Y) = c(X,Y) + minw {D (Z,w)}
= 2+1 = 3
14
Distance Vector Algorithm:
Example
Y
2 1
X Z
7
15
Distance Vector Algorithm:
Example
Y
2 1
X Z
7
16
Convergence of DV Routing
router detects local link cost change 1
updates distance table Y
4 1
if cost change in least cost path, notify X Z
neighbors 50
“good algorithm
terminates
news
travels
fast”
17
Problems with DV Routing
Link cost changes:
good news travels fast
60
bad news travels slow Y
“count to infinity” problem! 4 1
X Z
50
algorithm
continues
on!
18
Fixes to Count-to-Infinity Problem
Split horizon
A router never advertises the cost of a destination
to a neighbor
If this neighbor is the next hop to that destination
Split horizon with poisonous reverse
If X routes traffic to Z via Y, then
X tells Y that its distance to Z is infinity
Instead of not telling anything at all
Accelerates convergence
19
Split Horizon with Poisoned Reverse
60
If Z routes through Y to get to X : Y
Z tells Y its (Z’s) distance to X is infinite (so 4 1
Y won’t route to X via Z) X Z
50
algorithm
terminates
20
Count-to-Infinity Problem
X Y Z
What happens when the link Y to Z goes down?
All three routers X, Y, and W together count to
infinity.
Split horizon solution works only when two
routers are involved in a loop.
21
Count-to-Infinity Problem
X Y Z
To completely eliminate the problem, a router
some how need to figure out the complete path
to a destination.
Obvious solution is to pass on the path
information along with the distance vector.
This path vector approach is used in BGP.
22
Link State vs Distance Vector
Tells everyone about Tells neighbors about
neighbors everyone
Controlled flooding to Exchanges distance vectors
exchange link state with neighbors
Dijkstra’s algorithm Bellman-Ford algorithm
Each router computes its own Each router’s table is used by
table others
May have oscillations May have routing loops
23
RIP
RIP == Routing
Information Protocol 0 8 16 31
Command Version Must be zero
RIP is a distance vector Family of net 1 Address of net 1
implementation Address of net 1
(network_address,
distance) Distance to net 1
pairs
Family of net 2 Address of net 2
Instead of advertising
Address of net 2
costs to the next
router, RIP advertises Distance to net 2
the cost to the next
network.
