Routing Algorithms: Suggested Reading
Routing Algorithms: Suggested Reading
Routing Algorithms: Suggested Reading
Suggested Reading:
Bertsekas and Gallager: 5.1 (5.1.1, 5.1.2), 5.2.3 (on Bellman-Ford and
Dijkstra’s)
Kurose and Rose (2001 Edition): 4.1, 4.2, 4.3, 4.4
Also http://www.stanford.edu/class/cs224a: routing protocol
Outline
Flooding
Distributed Bellman Ford Algorithm
Dijkstra’s Shortest Path First Algorithm
Problem
1 1 4
R1 R2 R4 R6
2 2 3
2
R7 3
R5 2
R3 4 B
R8
Routing Metrics
Metrics
¾ Link state: up or down (stability)
¾ Delay to send an average size packet (Make high speed links
attractive, but closeness counts)
¾ Bandwidth
¾ Link utilization
For simplicity, our examples assume that the cost for the path is
additive.
Example network
In this simple case, solution is clear from inspection
1 1 4
R1 R2 R4 R6
2 2 3
2
R7 3
R5 2
R3 4 B
R8
Flooding
Routers forward packets to all ports
except the ingress port.
R1
Advantages:
Simple.
Every destination in the network is reachable.
Disadvantages:
Some routers receive a packet multiple times.
Packets can go round in loops forever.
Inefficient.
Spanning Trees
Find the lowest cost route from each of
(R1, …, R7) to R8 (the same as from R8 to the rest for this case)
1 1 4
R1 R2 R4 R6
2 2 3
2
R7 3
R5 2
R3 4
R8
A Spanning Tree
1 1 4
R1 R2 R4 R6
3
2 2
2
2
R7 3
R5
4
R3 R8
If all weights are positive, algorithm terminates in N-1 steps, where N is the
no. of nodes in the network.
∞ ∞ ∞ 4 2
1 1
R1 R2 R4 R6
3
2 2
2 3
2 R7
2 3
4 R5
4 R8
R3
Bellman-Ford Algorithm
6 4 6 2
1 1 4
R1 R2 R4 R6
3
2 3
2 2 2
4 2 R7 3
R5
4
R3 R8
Solution
5 4 5 2
R1 1 R2 1 R4 R6
2 3
2 2
4 R7 3
R5 2
R3 4 R8
Routing Table for R8
Destination Next Hop
R1 R5
R2 R5
R3 R3
R4 R5
R5 R5
R6 R6
R7 R7
Distributed Bellman-Ford
Let N(i) be a set of neighbors of node i:
Questions:
1. How long can the algorithm take to run?
2. How do we know that the algorithm always
converges?
3. What happens when link costs change, or when
routers/links fail?
A Problem with Bellman-Ford
“Bad news travels slowly”
1 1 1
R1 R2 R3 R4
R6
Step 3: S = {R8 , R5 , R6},
R5
C = {R3 , R7 , R2 , R4 }. R8
Step 4: S = {R8 , R5 , R6 , R7 }, R6
C = {R3 , R2 , R4}. R7
R5
R8
Dijkstra’s SPF Algorithm
Step 8 : S = {R8 , R5 , R6 , R7 , R2 , R1 , R4 },
C = {}.
1 1
R1 R2 R4 R6
2
R7 3
R5 2
4 R8
R3