Routing - I

Important concepts: link state

based routing, distance vector
based routing
In the middle of Intersection …
 Two Strategies …
 Strategy One:  Strategy Two:
– You have a map, – You don’t have a map,
which gives you a all you know is the road
complete picture of signs telling you the
where you are, and distance from here, i.e.,
where you are, to next
possible routes,
adjacent town
distances to get to
– Also suppose you ask
destination X
around, from the people
from the neighbor town,
you know (according to
them) how far it is from
here to the destination
 Routing
Routing protocol
Goal: determine “good” 5
path 3
(sequence of routers) thru B C 5
2
network from source to A 2
3
1 F
dest.
Graph abstraction for 1 2
routing algorithms: D E
1
 graph nodes are
routers  “good” path:
 graph edges are – typically means
physical links minimum cost path
– link cost: delay, $ – other def’s possible
cost, or congestion
level
 Routing Algorithm Classification
Global or decentralized Static or dynamic?
information? Static:
Global:  routes change slowly
 all routers have complete over time
topology, link cost info Dynamic:
 “link state” algorithms  routes change more

Decentralized: quickly
 router knows physically- – periodic update
connected neighbors, link – in response to link
costs to neighbors cost changes
 iterative process of
computation, exchange of
info with neighbors
 “distance vector”
algorithms
 A Link State Routing Algorithm

Dijkstra’s algorithm Notation:

 net topology, link costs  c(i,j): link cost from node
known to all nodes i to j. cost infinite if not
– accomplished via “link direct neighbors
state broadcast”  D(v): current value of
– all nodes have same cost of path from source
info to dest. V
 computes least cost  p(v): predecessor node
paths from one node along path from source
(‘source”) to all other to v, that is next v
nodes
 N: set of nodes whose
– gives routing table for
that node least cost path
definitively known
 iterative: after k
iterations, know least
 Dijkstra’s Algorithm
1 Initialization:
2 N = {A}
3 for all nodes v
4 if v adjacent to A
5 then D(v) = c(A,v)
6 else D(v) = infty
7
8 Loop
9 find w not in N such that D(w) is a minimum
10 add w to N
11 update D(v) for all v adjacent to w and not in N:
12 D(v) = min( D(v), D(w) + c(w,v) )
13 /* new cost to v is either old cost to v or known
14 shortest path cost to w plus cost from w to v */
15 until all nodes in N
 Dijkstra’s Algorithm: An Example
Step start N D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F)
0 A 2,A 5,A 1,A infinity infinity
1 AD 2,A 4,D 2,D infinity
2 ADE 2,A 3,E 4,E
3 ADEB 3,E 4,E
4 ADEBC 4,E
5 ADEBCF

5
3
B C 5
2
A 2 1 F
3
1 2
D E
1
 Dijkstra’s Algorithm: Discussion
Algorithm complexity: n nodes
 each iteration: need to check all nodes, w, not in
N
 n*(n+1)/2 comparisons: O(n**2)
 more efficient implementations possible:
O(nlogn)
Oscillations possible:
A A A
 1e.g., link cost
1+e = amount
2+e 0 of carried
0 traffic2+e A
2+e 0
D B D 1+e1 B D
0 0 0 0 B D 1+e1 B
0 e 0 0 1 1+e 0 e
1
C C C C
1
e
… recompute … recompute … recompute
initially
routing
 Distance Vector Algorithm
Overview
 Each router starts with a distance table
consisting of the value “0” for itself and the
value “infinity” for every other destination
 Each router will transmit its distance vector to
each of its neighbors whenever the
information changes (as well as when a link to
a neighbor first comes up)
 Each router saves the most recently received
distance vector from each of its neighbors, and
calculate its own distance vector, based on
minimizing the cost to each destination
 Distance Vector Algorithm
iterative:
Distance Table data
 continues until no
nodes exchange info. structure
 self-terminating: no
 each node has its own
“signal” to stop  row for each possible
destination
asynchronous:  column for each directly-
 nodes need not
attached neighbor to node
exchange info/iterate
in lock step!
 example: in node X, for dest. Y
via neighbor Z:
distributed: distance from X to
 each node X = Y, via Z as next hop
D (Y,Z)
communicates only Z
= c(X,Z) + minw{D (Y,w)}
with directly-
attached neighbors
 Distance Table: An Example

1 cost to destination via

B C E
7 D () A B D
A 8 2
1 A 1 14 5
E D
2
B 7 8 5

destination
E D
D (C,D) = c(E,D) + minw {D (C,w)}
= 2+2 = 4 C 6 9 4
E D
D (A,D) = c(E,D) + min {D (A,w)}
w D 4 11 2
= 2+3 = 5 loop!
E B
D (A,B) = c(E,B) + minw{D (A,w)}
= 8+6 = 14
loop!
 Distance Table Gives Routing
Table
cost to destination via
E Outgoing link
D () A B D to use, cost

A 1 14 5 A A,1

B 7 8 5 B D,5
destination

destination
C 6 9 4 C D,4

D 4 11 2 D D,4

Distance table Routing table

 Distance Routing: Overview
Iterative, Each node:
asynchronous: each
local iteration caused by:
 local link cost change
wait for (change in local link
 message from neighbor:
cost of msg from neighbor)
its least cost path
change from neighbor
Distributed: recompute distance table
 each node notifies
neighbors only when its
least cost path to any if least cost path to any dest
destination changes has changed, notify
– neighbors then notify neighbors
their neighbors if
necessary
 Distance Vector Algorithm
At all nodes, X:
1 Initialization:
2 for all adjacent nodes v:
3 D X(*,v) = infty /* the * operator means "for all rows" */
X
4 D (v,v) = c(X,v)
5 for all destinations, y
X
6 send min D (y,w) to each neighbor /* w over all X's neighbors */
w
 Distance Vector Algorithm:
8loop Cont’d
9 wait (until I see a link cost change to neighbor V
10 or until I receive update from neighbor V)
11
12 if (c(X,V) changes by d)
13 /* change cost to all dest's via neighbor v by d */
14 /* note: d could be positive or negative */
15 for all destinations y: D X(y,V) = DX(y,V) + d
16
17 else if (update received from V wrt destination Y)
18 /* shortest path from V to some Y has changed */
19 /* V has sent a new value for its min w DV(Y,w) */
20 /* call this received new value is "newval" */
21 for the single destination y: D X(Y,V) = c(X,V) + newval
22
X
23 if we have a new minw D (Y,w)for any destination Y
X
24 send new value of min w D (Y,w) to all neighbors
25
26 forever
 Distance Vector Algorithm:
Example

Y
2 1
X Z
7
 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
 Distance Vector Algorithm: Link Cost
Changes
Link cost changes:
1
 node detects local link cost Y
change 4 1
 updates distance table (line 15) X Z
50
 if cost change in least cost path,
notify neighbors (lines 23,24)
algorithm
terminates
“good
news
travels
fast”
Count to infinity: Another
Example

A B C
1 1
 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

algorithm
continues
on!
 Distance Vector: Position
Reverse
If Z routes through Y to get to X :
60
 Z tells Y its (Z’s) distance to X is infinite (so Y
Y won’t route to X via Z) 4 1
 will this completely solve count to infinity X Z
problem? 50

algorithm
terminates
 Comparison of LS and DV
Algorithm
Message complexity Robustness: what
 LS: with n nodes, E links, happens if router
O(nE) msgs sent each malfunctions?
 DV: exchange between LS:
neighbors only
– node can advertise
– convergence time
incorrect link cost
varies
– each node computes
Speed of Convergence only its own table
 LS: O(n**2) algorithm DV:
requires O(nE) msgs – DV node can advertise
– may have oscillations incorrect path cost
 DV: convergence time – each node’s table used
varies by others
– may be routing loops o error propagate thru
– count-to-infinity network
 Summary

 LS and DV are representative

 There are other type of routing
algorithms, especially in circuit
switching world, e.g., hot potato
algorithm
 Most of the internet routing protocols
(think OSPF, BGP etc.) are based on
these fundamental algorithms we
introduced just now