Transcript Distributed Bellman

Chapter 4
Distributed Bellman-Ford Routing
Professor Rick Han
University of Colorado at Boulder
[email protected]
Announcements
• Reminder: Programming assignment #1 is due
Feb. 19
• Homework #2 available on Web site, due
Feb. 26
• Hand back HW #1 next week
• OH cancelled yesterday, send me email to
meet
• Next, more on IP routing, …
Prof. Rick Han, University of
Colorado at Boulder
Recap of Previous Lecture
• ARP
• IP Forwarding Tables
•
Destination and Output Port
•
•
•
Distributed algorithm to create Forwarding Tables
Calculate shortest path to each node
Distance Vector (RIP)
A
• Presentation should
6
1
have been better by
3
2
F
me, textbook, etc.
1
E
• IP Routing
4
C
B
9
Prof. Rick Han, University of
Colorado at Boulder
1
D
Bellman-Ford Equation
• Distance vector & RIP based on distributed
implementation of Bellman-Ford algorithm
• Bellman-Ford equation:
•
•
•
Label routers i=A, B, C, …
Let D(i,j) = distance for best route from i to remote j
Let d(i,j) = distance from router i to neighbor j
• Set to infinity if i=j or i and j not immediate
A
neighbors
6
1
3
4
B
1
9
CProf. Rick Han, University of D
Colorado at Boulder
2
E
1
F
Bellman-Ford Equation (2)
• Bellman-Ford equation:
•
•
D(i,j) = min {d(i,k) + D(k,j)} for all i<>j
k
neighbors
Ex. D(B,F) = min {d(B,k) + D(k,F)}
k=A,C,E
A
6
1
3
4
B
1
9
CProf. Rick Han, University of D
Colorado at Boulder
2
E
1
F
Bellman-Ford Algorithm
• Bellman-Ford equation:
•
D(i,j) = min {d(i,k) + D(k,j)} for all i<>j
k neighbors
• Bellman-Ford Algorithm solves B-F Equation:
•
To calculate D(i,j), node i only needs d(i,k)’s and
D(k,j)’s from neighbors
• Problem: don’t know D(k,j)’s
• Solution:
•
•
For each node i, first find shortest distance path from i
to j using one link, D(i,j)[1]
Shortest distance path using two or fewer links,
D(i,j)[2], must depend on the shortest distance path
using one link, namely D(i,j)[2] = min {d(i,j) + D(i,j)[1]}
Prof. Rick Han, University of
Colorado at Boulder
Bellman-Ford Algorithm (2)
• Key observation:
•
By induction, the best (h+1 or fewer)-hop path
between nodes i and j must be arise from an i-toneighbor link connected with a (h or fewer)-hop path
from neighbor to j :
•
D(i,j)[h+1] = min {d(i,k) + D(k,j)[h]}
• Bellman-Ford Algorithm:
•
•
D(i,j)[h+1] = min {d(i,k) + D(k,j)[h]} for all i<>j, h=0,1, …
k neighbors
Iterate h=0,1,2, … until reach diameter DM of graph
•
•
•
•
D(i,j)[DM] is the originally desired B-F solution D(i,j) !
At each h, calculate D(i,j)[h+1] for all i<>j
At h=0, D(i,j)[0] = {0 for i=j, infinity otherwise}
Prof. Rick Han, University of
D(i,i)[h] = link cost
on which
dist. vector is sent - 1
Colorado
at Boulder
Bellman-Ford Algorithm Example
• Suppose C wants to find shortest path to
each destination
• First, calculate shortest one-link paths
from each node: easy, D(i,j)[1]=d(i,j)
– D(C,B)[1], D(C,D)[1], and
– D(B,A)[1], D(B,E)[1],
D(B,C)[1], and
– D(D,E)[1], D(D,C)[1], and
– D(A,B)[1], D(A,E)[1],
D(A,F)[1], and
3
– D(E,A)[1], D(E,B)[1],
D(E,D)[1], D(E,F)[1], and
B
– D(F,A)[1], D(F,E)[1] 4
A
6
1
1
9
CProf. Rick Han, University of D
Colorado at Boulder
2
E
1
F
Bellman-Ford Algorithm Example (2)
• Second, calculate shortest 2-or-fewer hop
paths from each node:
• Example: for node C to F
D(C,F)[2] = min (d(C,k) + D(k,F)[1]) for all j
k neighbors
= min {d(C,B) + D(B,F)[1], d(C,D) + D(D,F)[1]}
• No one-link path from B
to F, so D(B,F)[1] is
infinity, same for
3
D(D,F)[1]
A
6
1
1
• Calculate D(i,j)[2] 4for
all other combinations 9
CProf. Rick Han, University of
of i<>j
Colorado at Boulder
B
2
E
1
D
F
Bellman-Ford Algorithm Example (3)
• Third, calculate shortest 3-or-fewer hop paths
from each node:
• Example: for node C to F
D(C,F)[3] = min {d(C,B) + D(B,F)[2], d(C,D) + D(D,F)[2]}
• No more unknowns:
• D(B,F)[2] is known by now and was calculated in the last
iteration, = min{d(B,k) + D(k,F)[1]}
• D(D,F)[2] is also known
A
• Since diameter = 3,
we’re done and have
found all shortest 4
distance paths D(i,j)
6
1
3
B
1
9
CProf. Rick Han, University of D
Colorado at Boulder
2
E
1
F
Distributed Bellman-Ford
Algorithm
• Bellman-Ford Algorithm:
•
D(i,j)[h+1] = min {d(i,k) + D(k,j)[h]} for all i<>j, h=0,1, …
k neighbors
• One way to implement in a real network:
•
•
•
Flood d(i,j) first to every router in the network
Calculate B-F Algorithm in each router
Drawbacks:
• Generates lots of overhead
• Requires much computation on each router
• Duplication of many of calculations on each router
• Consider an alternative to distribute
Prof. Rick Han, University of
calculations
Colorado at Boulder
Distributed Bellman-Ford
Algorithm (2)
• Bellman-Ford Algorithm:
•
D(i,j)[h+1] = min {d(i,k) + D(k,j)[h]} for all i<>j, h=0,1, …
k neighbors
• Key observations:
1. We had to calculate D(i,j)[h] for each node i in the
graph, at each step h in the iteration
2. At every iteration h, we only needed information
about the h-1 or fewer hop paths to calculate
D(i,j)[h]
Prof. Rick Han, University of
Colorado at Boulder
Distributed Bellman-Ford
Algorithm (3)
• Therefore, in a real network,
•
•
Physically distribute the calculation of D(i,j)[h] to
router i only, and
• No duplication
• Less calculation
Exchange the results of your D(i,j)[h] with
neighboring routers at each iteration h
• Less overhead
• Satisfies condition that D(i,j)[h] only needs info
on h-1 or less hop paths.
• At iteration h, d(i,j) within radius h-1 will be
propagated to all routers within radius h-1
Prof. Rick Han, University of
Colorado at Boulder
Distributed Bellman-Ford
Algorithm (4)
• In practice, convergence will eventually occur
even if different routers are slow to propagate
or calculate their D(i,j)[h] and/or d(i,j)
•
Bertsekas and Gallagher proved this, in the absence
of topology changes
• Distributed routing algorithm where each router
only performs a small but sufficient part of the
overall B-F algorithm
• Node i calculates and sends D(i,j)[h] to its
neighbors – this is a distance vector
•
Distributed Bellman-Ford Algorithm = Distance
Rick Han, University of
Vector AlgorithmProf.Colorado
at Boulder
Distance Table
• Bellman-Ford Algorithm:
•
D(i,j)[h+1] = min {d(i,k) + D(k,j)[h]} for all i<>j, h=0,1, …
k neighbors
• Each router i must maintain a “distance table”:
•
Must store d(i,k), D(k,j)[h] for each neighbor k and
destination j
Costs D(k,j)[h]
Destinations j
j1
j2
Neighbors k
k1
k2
D(k1,j1)[h]
…
…
…
Prof. Rick Han, University of
Colorado at Boulder
k3
…
…
Distance Table (2)
• In reality, each cell in distance table stores
d(i,k) + D(k,j)[h], not just D(k,j)[h]
•
•
Must store d(i,k) or receive it within a neighbor’s
distance vector advertisement
If d(i,k) is a hop, then d(i,j)=1 always, so no need to
store
Costs D(k,j)[h]
Destinations j
j1
j2
Neighbors k
k1
k2
d(i,k1) + D(k1,j1)[h] …
…
…
Prof. Rick Han, University of
Colorado at Boulder
k3
…
…
Routing Table
• Easy to derive a Routing Table from a distance
table: choose the minimum distance in the row
Costs D(k,j)[h]
Neighbors k
Destinations j
k1
k2
k3
j1
d(i,k1) + D(k1,j1)[h]
…
…
j2
…
…
…
Routing Table At Router i
Destinations j
j1
j2
Outgoing link/port
k2
k3
Prof. Rick Han, University of
Colorado at Boulder
Cost
Routing Information Protocol (RIP)
• RIP is a specific realization of the distance
vector or distributed Bellman-Ford routing
algorithm
• Distance vectors are carried over UDP over IP
• RIP uses hop count as its shortest path metric,
so d(i,j)=1
• Distance vectors are sent every 30 seconds
• When a routing table changes, a router can send
triggered updates to neighbors before 30 sec
•
Can lead to network storms, so limit rate: wait 5
seconds between sending new routing update and the
update that caused
routing
table
to change
Prof. Rick
Han, University
of
Colorado at Boulder
Alternative Shortest Path Calc.
• Compute a shortest path tree
• Observation:
•
shortest path to nodes further from the root must
go through a branch of the shortest path tree closer
to the root
• Strategy: expand outwards, calculating the
shortest path tree from the root
A
6
1
3
4
B
1
9
CProf. Rick Han, University of D
Colorado at Boulder
2
E
1
F