PowerPoint Presentation
Computer Systems
Week 10b – Network Layer Routing Algorithms
Based on material and slides from
Computer Networking: A Top Down
Approach, 7th
Edition – Chapter 5
,
Pearson/
Slide# 2 of 33
Lecture Objective
The objective of this lecture is to understand the
conceptual aspects of network layer routing
algorithms
Slide# 3 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# 4 of 33
Recap – Network Layers
Slide# 5 of 33
Interplay between Routing & Forwarding
routing algorithm determines
end-end-path through network
forwarding table determines
local forwarding at this router
Slide# 6 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# 7 of 33
Graph Abstraction
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
cost of path (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp)
Key Question: What is the least-cost path between u and z ?
Routing Algorithm: Algorithm that finds that least cost path
Slide# 8 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# 9 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# 10 of 33
Dijkstra’s Algorithm
1 Initialization:
2 N’ = {u}
3 for all nodes v
4 if v adjacent to u
5 then D(v) = c(u,v)
6 else D(v) = ∞
7
8 Loop
9 find w not in N’ such that D(w) is a minimum
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’
Slide# 11 of 33
Dijkstra’s Algorithm – Example
Step N’
D(v)
p(v)
0
1
2
3
4
5
D(w)
p(w)
D(x)
p(x)
D(y)
p(y)
D(z)
p(z)
u ∞ ∞ 7,u 3,u 5,u
uw ∞ 11,w 6,w 5,u
14,x 11,w 6,wuwx
uwxv 14,x 10,v
uwxvy 12,y
uwxvyz
Notes:
construct shortest path tree
by tracing predecessor nodes
ties can exist (can be broken
arbitrarily)
w3
4
v
x
u
5
3
7 4
y
8
z
2
7
9
Slide# 12 of 33
Dijkstra’s Algorithm – Another Example
Step
0
1
2
3
4
5
N’
u
ux
uxy
uxyv
uxyvw
uxyvwz
D(v),p(v)
2,u
2,u
2,u
D(w),p(w)
5,u
4,x
3,y
3,y
D(x),p(x)
1,u
D(y),p(y)
∞
2,x
D(z),p(z)
∞
∞
4,y
4,y
4,y
Slide# 13 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# 14 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# 15 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# 16 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 to neighbor v
min taken over all neighbors v of x
cost from neighbor v to destination y
Slide# 17 of 33
Bellman-Ford – Example
Clearly, dv(z) = 5, dx(z) = 3, dw(z) = 3
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
B-F equation gives:
Node achieving minimum is next-hop in shortest path,
used in forwarding table.
Slide# 18 of 33
Distance Vector Algorithm
D
x
(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# 19 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:
D
x
(y) ← min
v
{c(x,v) + D
v
(y)} for each node y ∊ N
Under minor, natural conditions, the estimate D
x
(y)
converge to the actual least cost d
x
(y)
Slide# 20 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
wait for (change in local link
cost or msg from neighbor)
recompute estimates
if DV to any dest has
changed, notify neighbors
Each Node:
Slide# 21 of 33
x y z
x
y
z
0 2 7
∞ ∞ ∞
∞ ∞ ∞
fr
o
m
cost to
fr
o
m
fr
o
m
x y z
x
y
z
0
x y z
x
y
z
∞ ∞
∞ ∞ ∞
cost to
x y z
x
y
z
∞ ∞ ∞
7 1 0
cost to
∞
2 0 1
∞ ∞ ∞
2 0 1
7 1 0
time
x z
12
7
y
node x
table
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)}
= min{2+0 , 7+1} = 2
32
node y
table
node z
table
cost to
fr
o
m
Dx(z) = min{c(x,y) +
Dy(z), c(x,z) + Dz(z)}
= min{2+1 , 7+0} = 3
Slide# 22 of 33
x y z
x
y
z
0 2 3
fr
o
m
cost to
x y z
x
y
z
0 2 7
fr
o
m
cost to
x y z
x
y
z
0 2 3
fr
o
m
cost to
x y z
x
y
z
0 2 3
fr
o
m
cost to
x y z
x
y
z
0 2 7
fr
o
m
cost to
2 0 1
7 1 0
2 0 1
3 1 0
2 0 1
3 1 0
2 0 1
3 1 0
2 0 1
3 1 0
time
x y z
x
y
z
0 2 7
∞ ∞ ∞
∞ ∞ ∞
fr
o
m
cost to
fr
o
m
fr
o
m
x y z
x
y
z
0
x y z
x
y
z
∞ ∞
∞ ∞ ∞
cost to
x y z
x
y
z
∞ ∞ ∞
7 1 0
cost to
∞
2 0 1
∞ ∞ ∞
2 0 1
7 1 0
time
x z
12
7
y
node x
table
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
32
node y
table
node z
table
cost to
fr
o
m
Slide# 23 of 33
Distance Vector – Link Cost Changes
Link Cost Changes:
Node detects local link cost change
Updates routing info, recalculates
distance vector
If DV changes, notify neighbors
“Good news travels fast!”
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.
What would happen if the link cost
increases?
x z
14
50
y
1
Slide# 24 of 33
Comparison of LS and DV Algorithms
Message Complexity
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
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
Slide# 25 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# 26 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# 27 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# 28 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?
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!
AS3
AS2
3b
3c
3a
AS1
1c
1a
1d
1b
2a
2c
2b
other
networks
other
networks
Slide# 29 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)
AS3
AS2
3b
3c
3a
AS1
1c
1a
1d
1b
2a
2c
2b
other
networks
other
networks
x…
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!
AS3
AS2
3b
3c
3a
AS1
1c
1a
1d
1b
2a
2c
2b
other
networks
other
networks
x …
…
…
?
Slide# 31 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# 32 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# 33 of 33
References / Links
Chapter #5: The Network Layer: Control Plane,
Computer Networking: A Top-Down Approach (7th
edition)
by Kurose & 1
Slide 2
Slide 3
Slide 4
Slide 5
Slide 6
Slide 7
Slide 8
Slide 9
Slide 10
Slide 11
Slide 12
Slide 13
Slide 14
Slide 15
Slide 16
Slide 17
Slide 18
Slide 19
Slide 20
Slide 21
Slide 22
Slide 23
Slide 24
Slide 25
Slide 26
Slide 27
Slide 28
Slide 29
Slide 30
Slide 31
Slide 32
Slide 33