Transcript Intro to Routing Algorithms

14:
Intro to Routing Algorithms
Last Modified:
3/26/2016 7:50:26 AM
4: Network Layer
4a-1
Routing
 IP Routing – each router is supposed to
send each IP datagram one step closer to
its destination
 How do they do that?

Static Routing
• Hierarchical Routing – in ideal world would that be
enough?
Well its not an ideal world

Dynamic Routing
• Routers communicate amongst themselves to
determine good routes (ICMP redirect is a simple
example of this)
• Before we cover specific routing protocols we will
cover principles of dynamic routing protocols
4: Network Layer
4a-2
Routing Algorithm classification:
Static or Dynamic?
Choice 1: Static or dynamic?
Static:
 routes manually defined
 change slowly over time or only one possible route
 Appropriate in some circumstances, but obvious
drawbacks (routes added/removed? sharing load?)
 Not much more to say?
Dynamic:
 Routes learned by communicating with other routers
 routes change more quickly
 periodic update
 in response to link cost changes
4: Network Layer
4a-3
Routing Algorithm classification:
Global or decentralized?
Choice 2, if dynamic: global or decentralized
information?
Global:
 all routers have complete topology, link cost info
 “link state” algorithms
Decentralized:
 router knows physically-connected neighbors, link
costs to neighbors
 iterative process of computation, exchange of info
with neighbors (gossip)
 “distance vector” algorithms
4: Network Layer
4a-4
Roadmap
 Details of Link State
 Details of Distance Vector
 Comparison
4: Network Layer
4a-5
Routing
Routing protocol
5
Goal: determine “good” path
(sequence of routers) thru
network from source to dest.
Graph abstraction for
routing algorithms:
 graph nodes are
routers
 graph edges are
physical links

link cost: delay, $ cost,
or congestion level
2
A
B
2
1
D
3
C
3
1
5
F
1
E
2
 “good” path:
 typically means minimum
cost path
 other definitions
possible
4: Network Layer
4a-6
Global Dynamic Routing
See the big picture; Find the best Route
What algorithm do you use?
5
2
3
B
A
2
1
D
C
F
1
3
1
5
E
2
4: Network Layer
4a-7
A Link-State Routing Algorithm
Dijkstra’s algorithm
 Know complete network topology with link costs for
each link is known to all nodes
 accomplished via “link state broadcast”
 In theory, all nodes have same info
 Based on info from all other nodes, each node
individually computes least cost paths from one
node (“source”) to all other nodes
 gives routing table for that node
 iterative: after k iterations, know least cost path to
k dest.’s
4: Network Layer
4a-8
Link State Algorithm:
Some Notation
Notation:
 c(i,j): link cost from node i to j. cost
infinite if not direct neighbors
 D(v): current value of cost of path from
source to dest. V
 n(v): next hop from this source to v along
the least cost path
 N: set of nodes whose least cost path
definitively known
4: Network Layer
4a-9
Dijsktra’s Algorithm
1 Initialization – know c(I,j) to start:
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 (optional?)
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
4: Network Layer 4a-10
Dijkstra’s algorithm: example
Step
0
1
2
3
4
5
start N
A
AD
ADE
ADEB
ADEBC
ADEBCF
D(B),n(B) D(C),n(C) D(D),n(D) D(E),n(E) D(F),n(F)
2,B
1,A
5,C
infinity
infinity
2,B
4,D
2,D
infinity
2,B
3,D
4,D
3,D
4,D
4,D
5
2
A
B
2
1
D
3
C
3
1
5
F
1
E
2
4: Network Layer 4a-11
Dijkstra’s Algorithm gives routing
table
A
Outgoing Link
A
n(A) = A
B
n(B) = B
C
n (C)= D
D
n(D) = D
E
n(E) = D
F
n(F) = D
4: Network Layer 4a-12
Complexity of Link State
Algorithm complexity: n nodes
 each iteration



Find next w not in N such that D(w) is a minimum
Then for that w, check its best path to other
destinations
=> n*(n+1)/2 comparisons: O(n2)
 more efficient implementations possible using a
heap: O(nlogn)
4: Network Layer 4a-13
Distance Vector Routing Algorithm
distributed:
 each node communicates only with directly-
attached neighbors
iterative:
 continues until no nodes exchange info.
 self-terminating: no “signal” to stop
asynchronous:
 nodes need not exchange info/iterate in lock
step!
4: Network Layer 4a-14
Distance Vector Routing Algorithm
Distance Table data structure
 each node has its own row for
each possible destination
 column for each directlyattached neighbor to node
 example: in node X, for dest. Y
via neighbor Z:
X
D (Y,Z)
Column only for each neighbor
X
cost to destination via
D ()
Z
Y
Dx(Y,Z)
distance from X to
= Y, via Z as next hop
Z
= c(X,Z) + minw{D (Y,w)}
Rows for each possible dest !
4: Network Layer 4a-15
Example: Distance Table for E
Column only for each neighbor
7
A
C
E
D
2
D (row, col)
E
E
cost to destination via
D ()
A
B
D
A
1
14
5
B
7
8
5
2
8
1
E
B
1
D
D (C,D) = c(E,D) + minw {D (C,w)}
C 6
9
4
= 2+2 = 4
E
D
D 4 11
2
D (A,D) = c(E,D) + minw {D (A,w)}
= 2+3 = 5 Loop back through E!
Rows for each possible dest !
E
B
c(E,B)
+
min
{D
(A,w)}
D (A,B) =
w
= 8+6 = 14 Loop back through E!
4: Network Layer 4a-16
Distance table gives routing table
E
cost to destination via
= least cost
Outgoing link
to use, cost
D ()
A
B
D
A
1
14
5
A
A,1
B
7
8
5
B
D,5
C
6
9
4
C
D,4
D
4
11
2
D
D,2
Distance table
Routing table
4: Network Layer 4a-17
Distance Vector Routing: overview
Iterative, asynchronous:
each local iteration caused
by:
 local link cost change
 message from neighbor: its
least cost path change
from neighbor
Distributed:
 each node notifies
neighbors only when its
least cost path to any
destination changes

neighbors then notify
their neighbors if
necessary
Each node:
wait for (change in local link
cost of msg from neighbor)
recompute distance table
if least cost path to any dest
has changed, notify
neighbors
4: Network Layer 4a-18
Distance Vector Algorithm:
At all nodes, X:
1 Initialization (don’t start knowing link costs for all links in graph):
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
Then in steady state…
4: Network Layer 4a-19
Distance Vector Algorithm (cont.):
8 loop
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) = D X(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
23 if we have a new minw DX(Y,w)for any destination Y
24
send new value of min w D X(Y,w) to all neighbors
25
4: Network Layer
26 forever
4a-20
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)}
= min{2+0 , 7+1} = 2
node x table
cost to
x y z
from
from
x ∞ ∞ ∞
y 2 0 1
z ∞∞ ∞
node z table
cost to
x y z
x ∞∞ ∞
y ∞∞ ∞
z 71 0
from
from
x 0 2 7
y ∞∞ ∞
z ∞∞ ∞
node y table
cost to
x y z
cost to
x y z
x 0 2 3
y 2 0 1
z 7 1 0
Dx(z) = min{c(x,y) +
Dy(z), c(x,z) + Dz(z)}
= min{2+1 , 7+0} = 3
X hears news from Y and Z
x
2
y
7
1
z
To start just know directly
connected links…tell neighbors
time
Network Layer
4-21
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)}
= min{2+0 , 7+1} = 2
node x table
cost to
x y z
x ∞∞ ∞
y ∞∞ ∞
z 71 0
from
from
from
from
x 0 2 7
y 2 0 1
z 7 1 0
cost to
x y z
x 0 2 7
y 2 0 1
z 3 1 0
x 0 2 3
y 2 0 1
z 3 1 0
cost to
x y z
x 0 2 3
y 2 0 1
z 3 1 0
cost to
x y z
from
from
from
x ∞ ∞ ∞
y 2 0 1
z ∞∞ ∞
node z table
cost to
x y z
x 0 2 3
y 2 0 1
z 7 1 0
cost to
x y z
cost to
x y z
from
from
x 0 2 7
y ∞∞ ∞
z ∞∞ ∞
node y table
cost to
x y z
cost to
x y z
Dx(z) = min{c(x,y) +
Dy(z), c(x,z) + Dz(z)}
= min{2+1 , 7+0} = 3
x 0 2 3
y 2 0 1
z 3 1 0
time
x
2
y
1
7
z
In steady
state, when
have good
news tell
neighbor
Network Layer
4-22
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)
“good
news
travels
fast”
1
X
4
Y
50
1
Z
algorithm
terminates
Anyone see
a problem?
4: Network Layer 4a-23
Distance Vector: link cost changes
Link cost changes:
 good news travels fast
 bad news travels slow -
“count to infinity” problem!
60
X
4
Y
50
1
Z
algorithm
continues
on!
4: Network Layer 4a-24
Distance Vector: poisoned reverse
If Z routes through Y to get to X :
 Originally, Z tells Y its (Z’s) distance to
X is infinite (so Y won’t route to X via
Z)
 In end, Y tells Z infinity
 will this completely solve count to
infinity problem?
60
X
4
Y
50
1
Z
algorithm
terminates
4: Network Layer 4a-25
Bigger Loops and Poison Reverse
E
D
D (A,D) = c(E,D) + min {D (A,w)}
w
= 2+2 +1 = 5
Loop back through E! Poison reverse will fix this
D tells E infinity because D’s route to A through E
E
7
A
1
B
C
2
8
1
E
D
2
B
D (A,B) = c(E,B) + minw{D (A,w)}
= 8+6 = 14
Loop back through E! Poison reverse will not fix this
B’s route to A is through E but B doesn’t know that
so does not tell E infinity
B’s route is through C so no poison reverse
E will try to send through B
A
7
B
1
2
8
50
E
C
2
D
4: Network Layer 4a-26
Count to Infinity Example with
Bigger Loop
B will learn bad news
C will have told B infinity because its route to A is
through B, so B won’t reroute through C
E however will have told B about a good route to A
through D (cost 6)
B will choose that route instead and advertise it as
the new best to C (cost 6+8 = 14); it will be worse
than the old one it advertised to C (old cost = 1)
C will propagate this updated “best” route to D
(cost 15)
D will propagate this new “best” route to E (cost
17)
E will update the “best” route to B (cost 19)
Last time it advertised cost 6 to B
It will loop around adding 13 each time (cost of
loop)
Will continue until cost E advertises to B is bigger
than 500
A
1
1
B
C
2
8
E
A
500
D
2
B
1
2
8
E
C
2
D
4: Network Layer 4a-27
Comparison of LS and DV algorithms
Message complexity
 LS: nodes send info on
directly connections to all
other nodes

More, smaller messages
 DV: nodes send info on best
paths to all destinations to
neighbors

Fewer, larger messages
Speed of Convergence
 LS: O(n2) algorithm
 DV: convergence time varies


may be routing loops
count-to-infinity problem
Robustness: what happens
if router malfunctions?
LS:


DV:


node can advertise
incorrect link cost
each node computes only
its own table
DV node can advertise
incorrect path cost
each node’s table used by
others
• error propagate thru
network
4: Network Layer 4a-28
Oscillations
 Assume:
Link cost = amount of carried traffic
Link cost is not symmetric
B and D sending 1 unit of traffic; C send e units of traffic



 Initially start with slightly unbalanced routes
 Everyone goes with least loaded, making them most loaded
for next time, so everyone switches
 Herding effect!
 Can happen with any routing protocol that uses dynamic load
info
A
A
A
1 A
D
1
1+e
0
0 0
C
e
e
B
1
Initially start with
almost equal routes
2+e
0
D 1+e 1 B
0
0
C
… B and C go
clockwise to A
0
D
1
2+e
0 0
C
B
1+e
2+e
0
D 1+e 1 B
e
0
C
… B, C and D go … B,C,D go
counterclockwise clockwise
4: Network Layer 4a-29
Preventing Oscillations
 Avoid link costs based on experienced load

But want to be able to route around heavily
loaded links…
 Avoid “herding” effect
 Avoid
all routers recomputing at the same time
 Not enough to start them computing at a
different time because will synchronize over
time as send updates
 Deliberately introduce randomization into time
between when receive an update and when
compute a new route
4: Network Layer 4a-30
Outtakes
4: Network Layer 4a-31
Distance Vector Algorithm: example
To start just know directly connected links…tell neighbors
X
2
Y
7
1
Z
X hears news from Y and Z
Y
X
D (Z,Y) = c(X,Y) + minw {D (Z,w)}
= 2+1 = 3
Z
X
D (Y,Z) = c(X,Z) + minw{D (Y,w)}
= 7+1 = 8
4: Network Layer 4a-32
Distance Vector Algorithm: example
In steady state, when have good news tell neighbor
X
2
Y
7
1
Z
4: Network Layer 4a-33
 In distance vector algorithms, the installation of a looping route
slows down the convergence of the algorithm. Virtually all of the
modifications that have been made to distance vector routing
since 1969 (e.g., split horizon, poison reverse, etc., etc.) have
the same goal, to reduce the number of looping routes that are
installed, and hence to decrease the convergence time.
 In link state algorithms, the convergence time is completely
unaffected by the installation of looping routes. Hence you don't
usually see loop- suppression techniques being combined with
link state routing. While forwarding loops are possible during the
transients, these are not regarded as much of a problem. It is
possible to combine loop-suppression techniques with link state
routing, it just has never been regarded as worth the trouble.
 With either kind of routing algorithm, TTL is used as a loop
detection procedure in order to catch the case where something
goes wrong.
4: Network Layer 4a-34
DUAL
 Loop-free routing algorithm that performs a





“diffused” computation of a routing table
Researched and developed at SRI International by
Dr. J.J. Garcia-Luna-Aceves
No need for route hold down
http://www.cisco.com/univercd/cc/td/doc/cisintw
k/ito_doc/en_igrp.htm
Enhanced IGRP integrates the capabilities of linkstate protocols into distance vector protocols
DUAL enables EIGRP routers to determine
whether a path advertised by a neighbor is looped
or loop-free, and allows a router running EIGRP to
find alternate paths without waiting on updates
from other routers
4: Network Layer
4a-35
 J.J. Garcia-Luna-Aceves. Loop-Free
Routing Using Diffusing Computations.
IEEE/ACM Trans. Networking, 1:130-141, February 1993.
4: Network Layer 4a-36