Computer Systems
Week 10b – Network Layer Routing Algorithms
Based on material and slides from
Computer Networking: A Top Down
Approach, 7th Edition – Chapter 5 Jim Kurose, Keith Ross Pearson/Addison Wesley
Lecture Objective
The objective of this lecture is to understand the conceptual aspects of network layer routing algorithms
Slide# 2 of 33
Lecture Outline
Routing vs. Forwarding – Recap
Graph Abstraction
Routing Algorithms – Classification
Link State Routing – Dijkstra’s Algorithm
Distance Vector Routing – Bellman-Ford Algorithm Hierarchical Routing
Summary
Slide# 3 of 33
Recap – Network Layers
Slide# 4 of 33
Interplay between Routing & Forwarding
routing algorithm determines end-end-path through network
forwarding table determines local forwarding at this router
Slide# 5 of 33
Graph Abstraction
graph: G = (N,E)
N = set of routers = { u, v, w, x, y, z }
E = set of links ={ (u,v), (u,x), (u,w), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }
Aside: graph abstraction is useful in other network contexts, e.g., P2P, where N is set of peers and E is set of TCP connections
Slide# 6 of 33
Graph Abstraction
cost of path (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp)
c(x,x’) = cost of link (x,x’)
e.g., c(w,z) = 5
cost could always be 1, or inversely related to bandwidth, or inversely related to congestion
Key Question: What is the least-cost path between u and z ? Routing Algorithm: Algorithm that finds that least cost path
Slide# 7 of 33
Routing Algorithm Classification
Q: 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
“Distance Vector” algorithms
Q: static or dynamic?
Static:
Routes change slowly over time
Dynamic:
Routes change more quickly
periodic update
in response to link cost changes
Slide# 8 of 33
A Link-State Algorithm
Dijkstra’s Algorithm
Net topology, link costs known to all nodes
accomplished via “link state broadcast”
all nodes have same info
Computes least cost paths from one node (“source”) to all other nodes
gives forwarding table for that node
Iterative: after k iterations, know least cost path to k destinations
Notation:
c(x,y): link cost from node x to y; = ∞ if not direct neighbors
D(v): current value of cost of path from source to dest. v
p(v): predecessor node along path from source to v
N’: set of nodes whose least cost path definitively known
Slide# 9 of 33
Dijkstra’s Algorithm
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Initialization: N’={u}
for all nodes v
if v adjacent to u then D(v) = c(u,v)
else D(v) = ∞
Loop
find w not in N’ such that D(w) is a minimum addwtoN’
update D(v) for all v adjacent to w and not in N’ : D(v) = min( D(v), D(w) + c(w,v) )
/* new cost to v is either old cost to v or known shortest path cost to w plus cost from w to v */
until all nodes in N’
Slide# 10 of 33
Dijkstra’s Algorithm – Example
D(v) D(w) D(x) D(y) D(z) Step N’ p(v) p(w) p(x) p(y) p(z)
0 u 7,u 3,u 5,u ∞ ∞ 1uw6,w 5,u11,w∞
2 uwx 6,w 3 uwxv
11,w 14,x
x
10,v 14,x 12,y
9
4 uwxvy
5uwxvyz 547
Notes:
3
8
w y2z
3
4
construct shortest path tree by tracing predecessor nodes
ties can exist (can be broken 7 arbitrarily)
u
v
Slide# 11 of 33
Dijkstra’s Algorithm – Another Example
Step N’ 0 u 1 ux 2 uxy 3 uxyv 4 uxyvw 5 uxyvwz
D(v),p(v) D(w),p(w) 2,u 5,u 2,u 4,x 2,u 3,y 3,y
D(x),p(x) D(y),p(y) D(z),p(z) 1,u ∞ ∞
2,x
∞
4,y 4,y 4,y
Slide# 12 of 33
Dijkstra’s Algorithm – Least Cost Path and Forwarding Table for Node u
Resulting shortest-path tree from u: Resulting forwarding table in u:
Slide# 13 of 33
Dijkstra’s Algorithm – Complexity
Algorithm Complexity: n nodes
Each iteration: need to check all nodes, w, not in N’
n(n+1)/2 comparisons: O(n2)
More efficient implementations possible: O(n logn)
Slide# 14 of 33
Dijkstra’s Algorithm – Oscillations
Support link cost equals amount of carried traffic.
Given these costs, find new routing…. resulting in new costs
Slide# 15 of 33
Distance-Vector (DV) Routing Algorithm
Bellman-Ford equation:
let
dx(y) := cost of least-cost path from x to y then
dx(y) = minv {c(x,v) + dv(y) }
cost from neighbor v to destination y
cost to neighbor v
min taken over all neighbors v of x
Slide# 16 of 33
Bellman-Ford – Example
Clearly, dv(z) = 5, dx(z) = 3, dw(z) = 3
B-F equation gives:
du(z) = min { c(u,v) + dv(z), c(u,x) + dx(z),
c(u,w) + dw(z) }
= min {2 + 5, 1 + 3,
5 + 3} = 4
Node achieving minimum is next-hop in shortest path, used in forwarding table.
Slide# 17 of 33
Distance Vector Algorithm
Dx(y) = estimate of least cost from x to y
x maintains distance vector Dx = [Dx(y): y є N ]
Node x:
knows cost to each neighbor v: c(x,v)
maintains its neighbors’ distance vectors. For each neighbor v, x maintains:
Dv = [Dv(y): y є N ]
Slide# 18 of 33
Distance Vector Algorithm
Key Idea:
From time-to-time, each node sends its own distance vector estimate to neighbors
When x receives new DV estimate from neighbor, it updates its own DV using B-F equation:
Dx(y) ← minv{c(x,v) + Dv(y)} for each node y ∊ N
Under minor, natural conditions, the estimate Dx(y) converge to the actual least cost dx(y)
Slide# 19 of 33
Distance Vector Algorithm
Iterative, Asynchronous:
each local iteration caused by:
local link cost change DV update message
from neighbor
Distributed:
each node notifies neighbors only when its DV changes
neighbors then notify their neighbors if necessary
Each Node:
wait for (change in local link cost or msg from neighbor)
recompute estimates
if DV to any dest has changed, notify neighbors
Slide# 20 of 33
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = 2
Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)}
= min{2+1 , 7+0} = 3
node x
table x y z
x027 x023
yz ∞ ∞ ∞ yz ∞∞∞
cost to
cost to
x y z
node y
table x y z
201 710
cost to
2 y 1 xy∞∞∞ x7z
z
201 ∞∞∞
node z table
x∞∞∞
y z
cost to
xyz
∞∞∞ 710
time
Slide# 21 of 33
from from
from
from
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = 2
cost to
x y z
x027 x023 x023
y∞∞∞ y201 y201 z∞∞∞ z710 z310
node y cost to cost to cost to table x y z x y z x y z
x∞∞∞ x027 x023 y201 y201 y201 z∞∞∞ z710 z310
Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)}
= min{2+1 , 7+0} = 3
node x cost to table x y z
cost to
xyz
2 y 1
x z
7
node z table
x∞∞∞ x027 x023
y∞∞∞ y201 y201
z710 z310 z310 time
cost to
cost to cost to
xyz
xyz xyz
Slide# 22 of 33
from from
from
from from from
from
from from
Distance Vector – Link Cost Changes
Link Cost Changes:
Node detects local link cost change Updates routing info, recalculates
distance vector
1
4y1
x
If DV changes, notify neighbors
t0 : y detects link-cost change, updates its DV, informs its neighbors.
t1 : z receives update from y, updates its table, computes new least cost to x , sends its neighbors its DV.
t2 : y receives z’s update, updates its distance table. y’s least costs do not change, so y does not send a message to z.
“Good news travels fast!”
What would happen if the link cost increases?
z 50
Slide# 23 of 33
Comparison of LS and DV Algorithms
Message Complexity
Robustness: what happens if router malfunctions?
LS:
node can advertise incorrect link cost
each node computes only its own table
DV:
DV node can advertise incorrect path cost
► each node’s table used by others
► error propagate through the network
LS: with N nodes, E links, O(NE) messages sent
DV: exchange between neighbors only
convergence time varies Speed of Convergence
LS: O(N2) algorithm requires O(NE) messages
may have oscillations
DV: convergence time varies
may be routing loops
count-to-infinity problem
Slide# 24 of 33
Hierarchical Routing
Our routing study thus far – idealization All routers identical
Network is “flat” … not true in practice
Scale: with 600 million destinations:
Can’t store all dest’s in routing tables!
Routing table exchange would swamp links!
Administrative Autonomy
Internet = network of networks
Each network admin may want to control routing in its own network
Slide# 25 of 33
Hierarchical Routing
Aggregate routers into regions, “Autonomous Systems” (AS)
Routers in same AS run same routing protocol
“intra-AS” routing protocol
routers in different AS can run different intra- AS routing protocol
Gateway Router:
At “edge” of its own AS
Has link to router in another AS
Slide# 26 of 33
Interconnected ASes
Forwarding table configured by both intra- and inter-AS routing algorithm
intra-AS sets entries for internal destinations
inter-AS & intra-AS sets entries for external destinations
Slide# 27 of 33
Inter-AS Tasks
Suppose a router (1d) in AS1 receives datagram destined outside of AS1:
router should forward packet to gateway router, but which one?
3c
3b 3a AS3
AS1 must:
1) Learn which dests are reachable through AS2, which through AS3
2) Propagate this reachability info to all routers in AS1
Job of inter-AS routing!
1c 1a
2c
2a
other networks
other networks
1b AS1
2b AS2
1d
Slide# 28 of 33
Example: Setting Forwarding Table in Router 1d
Suppose AS1 learns (via inter-AS protocol) that the subnet x is reachable via AS3 (gateway 1c), but not via AS2
inter-AS protocol propagates reachability info to all internal routers Router 1d determines from intra-AS routing info that its
interface I is on the least cost path to 1c installs forwarding table entry (x,I)
3c
3b 3a AS3
x
1c 1a
2c
2a
other networks
other networks
1b AS1
2b AS2
1d
Slide# 29 of 33
…
Example: Choosing Among Multiple ASes
Now suppose AS1 learns from inter-AS protocol that subnet x is reachable from AS3 and from AS2.
To configure forwarding table, router 1d must determine which gateway it should forward packets towards for dest x
This is also job of inter-AS routing protocol!
3c
3b 3a AS3
x
1c 1a
2c
2a
other networks
other networks
1b AS1
2b AS2
1d
?
Slide# 30 of 33
…
……
Example: Choosing Among Multiple ASes
Now suppose AS1 learns from inter-AS protocol that subnet x is reachable from AS3 and from AS2.
To configure forwarding table, router 1d must determine which gateway it should forward packets towards for dest x
This is also job of inter-AS routing protocol!
Hot Potato Routing: send packet towards closest of two routers.
Slide# 31 of 33
Summary
In this lecture, we have seen:
The two main classes of routing algorithms i.e. Link State and Distance Vector routing.
Dijkstra’s Algorithm is a Link State algorithm.
Bellman-Ford as a Distance Vector algorithm.
The importance of Hierarchical Routing.
Slide# 32 of 33
References / Links
Chapter #5: The Network Layer: Control Plane,
Computer Networking: A Top-Down Approach (7th edition) by Kurose & Ross
Slide# 33 of 33