Shortest Path Algorithm: - Dijkstra's - Bellman-Ford

Shortest Path Algorithm
Packet Switching 1
2
3
1
4
6
5
8
5
2
3
3
6
5
8
2
2
3
3
1
1 4
2
1
1
1
7
Dijkstras Algorithm
Bellman-Ford Algorithm
Packet Switching 2
2
3
1
4
6
5
5
2
3
5
2 3
1
2
1
1
Reduced graph
Dijkstras Algorithm
Packet Switching 3
2 3
1
4
6
5
D
4
= 1
D
2
= 2 D
3
= 5
T = { 1 }
2 3
1
4
6
5
D
4
= 1
D
2
= 2 D
3
= 4
T = { 1, 4 }
D
5
= 2
2 3
1
4
6
5
D
4
= 1
D
2
= 2 D
3
= 4
T = { 1, 2, 4 }
D
5
= 2
2 3
1
4
6
5
D
4
= 1
D
2
= 2
D
3
= 3
T = { 1, 2, 4, 5 }
D
5
= 2
D
6
= 4
Packet Switching 4
Dijkstras Algorithm (cont)
T
D
Node
2 3 4 5 6
1 2 5 1
1, 4 2 4 1 2
1, 4, 2 2 4 1 2
1, 4, 2, 5 2 3 1 2 4
2 3 1 2 4 1, 4, 2, 5, 3
1, 4, 2, 5, 3, 6 2 3 1 2 4
Dijkstras Algorithm (cont)
w(i, j) = link cost, L(n) = path cost from node s to n
1. [Initialization]
T = {s}
L(n) = w(s, n) for n s
2. [Get next node]
Find x T such that L(x) = min L(j)
Add x to T
3. [Update Least-Cost Paths]
L(n) = min [ L(n), L(x) + w(x, n) ] for all n T
Go to step 2
Packet Switching 5
jT
Bellman-Ford Algorithm
Packet Switching 6
2 3
1
4
6
5
D
(1)
2
= 2 D
(1)
3
= 5
D
(1)
4
= 1
h = 1
2 3
1
4
6
5
D
(2)
2
= 2
D
(2)
3
= 4
D
(2)
4
= 1
h = 2
D
(2)
6
= 10
D
(2)
5
= 2
2 3
1
4
6
5
D
(3)
2
= 2
D
(3)
3
= 3
D
(3)
4
= 1
h = 3
D
(3)
6
= 4
D
(3)
5
= 2
Packet Switching 7
Bellman-Ford Algorithm (cont)
h
D
Node
2 3 4 5 6
1 2 5 1
2 2 4 1 2 10
3 2 3 1 2 4
4 2 3 1 2 4
0 Source = 1
Bellman-Ford Algorithm (cont)
L
h
(n) = path cost from s to n w/ no more than h links
1. [Initialization]
L
0
(n) = , for all n s
L
h
(s) = 0, for all h
2. [Update]
For each successive h 0
For each n s, compute
L
h+1
(n) = min [ L
h
(j) + w(j, n) ]
Packet Switching 8
j
s
j
n
<= h links
link
Comparisons
Packet Switching 9
S D

S D
x
x
x
L
h
(x, D)
L(n) = min [ L(n), L(x) + w (x, n) ]
Dijkstras
(Link State)
Bellman-Ford
(Distance Vector)

Routing in ARPANET
First generation(RIP), 1969
Adaptive Routing is adopted
Use Bellman-Ford algorithm Distance Vector
Estimated link delay is simply the queue length
for that link
Every 128ms, each node exchanges its delay
vector (routing table) with all its neighbors
Information about a change in network condition
would gradually ripple through the network
Packet Switching 10
Routing in ARPANET (cont)
Each node i maintains
d
i j
= current estimate of min delay from i to j
s
i j
= next node in the current min-delay route from i to j
Node k updates its vectors as follows
d
k j
= Min [ l
k i
+ d
i j
]
i A
s
k j
= i using i that minimizes the expression above
where
A = set of neighbor nodes for k
l
k i
= current estimate of delay from k to i
Packet Switching 11
k i
j
Major shortcomings of RIP
It did not consider line speed, merely queue
length. Higher capacity links were not given
the favored status
Queue length is an artificial measure of delay
The algorithm was not very accurate. It
responded slowly to congestion and delay
increases.
Packet Switching 12
Second generation, 1979
Using Dijkstras algorithm
Link State Routing Protocol
OSPF: Open Shortest Path First protocol
The delay is measured directly
Every 10 seconds, the node computes the
average delay on each outgoing link
Information of changes in delay is sent to all
others nodes using flooding
Packet Switching 13
Packet Switching 14
Third generation, 1987
Problem
The correlation between the reported values (delay)
and those actually experienced after rerouting
Conclusion
Under heavy load, the goal of routing should be to
give the average route a good path instead of
attempting to give all routes the best path
Solution
Also consider the average utilization of links
Revised cost function:
delay-based metric under light loads
capacity-based metric under heavy loads
Packet Switching 15
Calculate Link Costs
1. Measure the avg. delay over the last 10 sec
2. Using the single-server queuing model
(M/G/1), the measured delay is transformed
into an estimate of link utilization
3. Average the link utilization r (n+1) with the
previous estimate of utilization U(n)
U(n+1) = 0.5 * r (n+1) + 0.5 * U(n)
4. The link cost is set as a function of average
utilization
Packet Switching 16
ARPANET Delay Metrics (3
rd
)
Packet Switching 17
D
e
l
a
y

(
h
o
p
s
)

Estimated utilization
Theoretical
queueing delay
0.9 0.7
Metric for satellite link
Metric for
terrestrial link
0.8 0.6 0.4 0.5 0.3 0.1 0.2 1.0 0.0
1
2
3
4
5
0
ARPANET Delay Metrics (3
rd
)
1. Delay is normalized to the value achieved on
an idle line
2. The cost value is kept at the minimum value
until a given level of utilization is reached
Reducing routing overhead at low traffic levels
3. Above a certain level of utilization, the cost
level is allowed to rise to a maximum value that
is equal to three times the minimum value
To dictate that traffic should not be routed
around a heavily utilized line by more than two
additional hops
Packet Switching 18

Shortest Path Algorithm: - Dijkstra's - Bellman-Ford

Uploaded by

Copyright:

Available Formats

Shortest Path Algorithm: - Dijkstra's - Bellman-Ford

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Shortest Path Algorithm: - Dijkstra's - Bellman-Ford

Uploaded by

Copyright:

Available Formats

Shortest Path Algorithm

You might also like