COMP 3234B
Computer and Communication Networks
2nd semester 2020-2021
Network Layer (III)
Prof. C Wu
Department of Computer Science The University of Hong Kong
Roadmap
Network layer
Principles behind network-layer services (ILO1) forwarding vs. routing
network service models
Router (ILO1)
IP (ILO2,5) DHCP
NAT ICMP(ILO2)
Routing algorithms (ILO3)
Routing in the Internet (ILO2,3)
application
transport
network
network
link
physical
Internet network layer
Network layer
Transport layer: TCP, UDP
IP protocol
• addressing conventions • datagram format
• packet handling conventions
Routing protocols
• path selection • RIP, OSPF, BGP
forwarding table
ICMP protocol
• error reporting • router “signaling”
Link layer
physical layer
Routing protocols
Decide the good paths (aka routes) taken by datagrams from sending host to receiving host, through the network of routers
decide the forwarding tables at routers
path: sequence of routers that datagrams traverse, going from source host to destination host
“good”: least “cost”, “fastest”, “least congested”
routing algorithm components in every router interact in the control plane
4.1
•
OVERVIEW OF NETWORK LAYER
309
Routing Algorithm
Routing algorithm
control plane
data plane
Control plane Data plane
Local forwarding table
header
0100
0110
0111
1001
output
3 2 2 1
Values in arriving packet’s header
values in arriving packet header
1101
1 2
3
0111
1 32
routing: a “top-10” networking problem
Figure 4.2 ♦ Routing algorithms determine values in forward tables
tables. In this example, a routing algorithm runs in each and every router and both
Graph abstraction of the network
Graph abstraction
Undirected graph: G = (N,E)
N = set of nodes (routers) = { u, v, w, x, y, z }
source router 5
destination router
w 5
1 z
E = set of edges (links) ={ (u,v), (u,x), (v,x), (v,w), (x,w), u (x,y), (w,y), (w,z), (y,z) }
Link cost: the value associated with a link (related to bandwidth, congestion, physical length, delay, etc.)
c(x1, x2) = cost of link (x1, x2), e.g., c(w,z) = 5 c(x1, x2) = ∞ if (x1, x2) does not belong to E
1
2 x
3 1
2
v
3
Path: a sequence of nodes, (x1, x2, x3,…, xp)
Cost of path (x1, x2, x3,…, xp): c(x1,x2) + c(x2,x3) + … + c(xp-1,xp)
Routing algorithm
Given a set of routers with links connecting the routers, finds a least-cost path from source router to destination router
(finds the shortest path when link costs represent length)
y 2 What’s the least-cost
path between u and z ?
Routing algorithm classification
Centralized or decentralized routing algorithm Centralized:
algorithm input: complete global knowledge about the network, including node connectivity (topology), link costs
carried out at each router link-state (LS) algorithms
Decentralized:
source router 5
destination router
u 2 v 3 w 5
2 3
1 x
1 z y 2
1
with (local) knowledge of connectivity to neighbor routers, link costs to neighbors
algorithm carried out at each router by iterative process of computation and exchange of information with neighbor
distance-vector (DV) algorithms
Link-state routing algorithm
Dijkstra’s algorithm
Input: network topology, link costs of all links Output: least-cost paths from one node
(“source router”) to all other nodes (routers)
derives forwarding table for that router
Iterative algorithm executed at one node: after k iterations, the source derives least-cost paths to k destinations with the smallest path costs
source router
5
v 3 w 5
231z x 1 y 2
u
1
2
each node broadcasts its identity and costs of neighboring links to all other nodes in the network (“link state broadcast”)
=>all nodes have same and complete view of the network
Dijkstra’s algorithm
1 Initialization:
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 destination v
p(v): predecessor node along the current least-cost path from source to v
N’: set of nodes whose least-cost path already known
2 3 4 5 6 7 8 9 10 11
12 13 14 15
N’={u}
for all nodes i
if i is a neighbor of u
then D(i) = c(u,i), p(i) = u
else D(i) = ∞
Loop
find j not in N’ such that D(j) is a minimum add j to N’
source router
5 v3w5
231z x1y2
update D(i) for each neighbor i of j and not in
N’: u2
D(i) = min( D(i), D(j) + c(j,i) ); update p(i)
/*newcosttoiiseitheroldcosttoiorknown 1 least path cost to j plus cost from j to i */
untilN’=N
# of loops=
# of nodes in the network excluding the source
An example of Dijkstra’s algorithm
Example
source router
u2 1
5 v3w5
231z x1y2
Step N’
D(v),p(v) D(w),p(w) D(x),p(x)
D(y),p(y) D(z),p(z)
2,u 5,u 1,u ∞ ∞
u
ux2,u4,x 2,x∞
0
1
2
3 uxyv 3,y
4,y 4,y
uxy 2,u 3,y
4 uxyvw 4,y
5 uxyvwz
An example of Dijkstra’s algorithm (cont’d)
Resulting least-cost-path tree from u:
vw u
z xy
Resulting forwarding table in u:
destination
xv
y w z
link
(u,v) (u,x)
(u,x) (u,x)
(u,x)
next-hop node along the least-cost path towards the destination
Discussions on Dijkstra’s algorithm
Algorithm complexity
with n nodes (routers excluding the source)
each iteration: need to check all nodes, w, not in N’ n(n+1)/2 comparisons: O(n2)
more efficient implementations possible: O(nlogn)
Discussions on Dijkstra’s algorithm (cont’d)
Potential problem: routing oscillations Example scenario:
link cost = amount of carried traffic (reflecting delay on the link)
link costs could be asymmetric: c(u,v)=c(v,u) only if traffic on both directions is the same
node D originates a unit of traffic destined to A; node B originates a unit of traffic destined to A; node C originates traffic of amount e to A.
Possible solution: have each router run the algorithm at different times
1 A 1+e D 0 0 B
0 C e 11
e
initially
(new costs shown after initial routing)
2+e A 0 D 1+e1 B
0 C 0 given these costs,
find new routing…. resulting in new costs
0 A 2+e D 0 0 B
1 C 1+e given these costs,
find new routing…. resulting in new costs
2+e A 0 D 1+e1 B
0 C 0 given these costs,
find new routing…. resulting in new costs
Distance-vector routing algorithm
u2 1
5 v3w5
231z x1y2
Bellman-Ford algorithm
Input: connectivity/link costs to neighbors Output: least-cost paths from each node to all
other nodes
derives forwarding table for each router
Iterative, asynchronous, distributed algorithm executed
by all nodes together:
each node receives updates from neighbors, recomputes,
and distributes its new calculation result to neighbors
algorithm terminates (least-cost path from each node to each other node derived) when no more update is exchanged between neighbors
each node updates information to neighbors only
Bellman-Ford equation
Bellman-Ford equation
Define an important relationship among the costs of least-cost paths
dx(y) := cost of least-cost path from x to y Then
dx(y) = minv {c(x,v) + dv(y) }
where min is taken over all neighbors v of x
v1
x
1
y v2
Bellman-Ford equation (cont’d)
Example
dv(z) = 5, dx(z) = 3, dw(z) = 3 Bellman-Ford equation says:
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 that achieves minimum is next hop in the least-cost path
➜ decides the entry in u’s forwarding table
u2 1
5 v3w5
231z x1y2
Bellman-Ford algorithm basics
Dx(y) = estimate of least path cost from x to y Node x maintains
cost to each neighbor v: c(x,v) distance vector Dx = [Dx(y): y є N ] its neighbors’ distance vectors
For each neighbor v, x maintains Dv = [Dv(y): y є N ] Basic idea of Bellman-Ford algorithm
From time-to-time, each node sends its updated distance vector (DV) to neighbors
When a node x receives new DV estimate from neighbor v, it updates
its own DV using Bellman-Ford equation:
Dx(y) ← minv{c(x,v) + Dv(y)} for each node y N
all nodes continue to exchange their DVs in an asynchronous fashion; each least cost estimate Dx(y) converges to the actual least cost dx(y)
Bellman-Ford algorithm
At each node, x:
1 Initialization:
2 3 4 5 6 7 8 9 10 11 w) 12 13 14 15 16
17 18 19
for all destinations y in N: Dx(y) = c(x,y)
for each neighbor w
Dw(y) = ∞ for all destinations y in N for each neighbor w
send distance vector Dx = [Dx(y): y є N ] to w
Loop
wait (until I see a link cost change to some neighbor w or until I receive a distance vector from some neighbor
for each y in N:
Dx(y) = minv {c(x,v) + Dv(y) }
if Dx(y) changed for any destination y
send distance vector Dx = [Dx(y): y є N ] to all neighbors forever
Each node:
wait for (change in local link cost or msg from neighbor)
recompute estimates
if DV to any dest has changed, notify neighbors
An example of Bellman-Ford algorithm
Example
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
node z table
cost to xyz
xy 0 2 7
cost to xyz
xy 2 0 1 z710
cost to xyz
x027 y201
z710 cost to
xyz
x027 y201 z310
node y table
z∞∞∞ ∞∞∞
cost to xyz
x∞∞∞
y201
z∞∞∞
cost to xyz
x∞∞∞
yz ∞ ∞ ∞ 710
time
02
3
x
2y1 7
z
from from from
from
from
from
An example of Bellman-Ford algorithm (cont’d)
node x table
cost to cost to cost to xyz xyz xyz
x027 x023 x023 y∞∞∞ yz 2 0 1 yz201
z∞∞∞ 710 310
cost to cost to xyz xyz
node y table
cost to xyz
node z table
cost to
xyz xyz
x∞∞∞ x027
y201 y201 z∞∞∞ z710
x023 y201
z310 cost to
cost to xyz
x027 x023 y201 y201
z310 z310
time
x∞∞∞
yz ∞ ∞ ∞ 710
x
2y1 7
z
from from from
from
from
from
from from from
Discussions on Bellman-Ford algorithm I
Link cost change: scenario 1
At time t0, x and y detect the link-cost change (4→1), updates their DV, and inform neighbors.
1y
41 50
x
z
DV table evolution
node x table
cost to xyz
x y z
0 4152 401
510
node y table
cost to xyz
x y z
014 5 401
510
node z table
cost to xyz
x y z
045
401 510
t0 t1 t2
time
1y
41 50
x
z
from from from
DV table evolution
node x table
cost to xyz
x y z
0 4152 401
510
cost to xyz
x y z
012
101 510
node y table
x y z
cost to xyz
014 5 401
510
cost to xyz
x y z
012
101 510
node z table
cost to xyz
cost to xyz
x y z
x y z
045
401 510
012
101 210
t0 t1 t2
time
1y
41 50
x
z
from from from
from from from
DV table evolution
node x table
node y table
cost to xyz
cost to xyz
x y z
x y z
0 4152 401
510
012
101 510
cost to xyz
x y z
012
101 210
cost to xyz
cost to xyz
x y z
x y z
014 5 401
510
012
101 510
cost to xyz
x y z
012
101 210
node z table
x y z
cost to xyz
045
401 510
cost to xyz
x y z
012
101 210
cost to xyz
x y z
012
101 210
time
t0 t1 t2
1y
41 50
x
z
from from from
from from from
from from from
Discussions on Bellman-Ford algorithm I (cont’d)
Link cost change: scenario 1
At time t0, x and y detect the link-cost change (4→1), updates their
DV, and inform neighbors.
At time t1, z receives the updates, computes a new least cost to x (5->2) and informs its neighbors.
At time t2, x and y receive z’s update and update their DV tables. x and y’s least costs do not change and hence do not send any further message to z.
Good news travels fast!
1y
41 50
x
z
Discussions on Bellman-Ford algorithm II
Link cost change: scenario 2
At time t0, x and y detect the link-cost change (4→60), update their DV, and notify neighbors
60 y
41 50
x
z
Dx(y)=min{c(x,y)+ Dy(y), c(x,z)+ Dz(y)} =min{60+0,50+1}=51
Dy(x)=min{c(y,x)+ Dx(x), c(y,z)+ Dz(x)} =min{60+0,1+5}=6
node x table
cost to xyz
x y z
50
401 510
045
51
node y table
cost to xyz
x y z
064 5 401
510
node z table
cost to xyz
x y z
045
401 510
t0 t1 t2 t3 t4 time
60 y
41 50
x
z
from from from
Dz(x)=min{c(z,x)+ Dx(x), c(z,y)+ Dy(x)} =min{50+0,1+6}=7
node x table
cost to xyz
x y z
51 50 045
401 510
cost to
xyz
x y z
0 51 50
601 510
node y table
x y z
cost to xyz
064 5 401
510
cost to xyz
x y z
0 51 50
601 510
node z table
cost to xyz
x y z
045
401 510
cost to xyz
x y z
0 51 50 601 710
t0 t1 t2 t3 t4 time
60 y
41 50
x
z
from from from
from from from
Dy(x)=min{c(y,x)+ Dx(x), c(y,z)+ Dz(x)} =min{60+0,1+7}=8
cost to xyz
x y z
cost to xyz
x y z
cost to xyz
x y z
node x table
cost to xyz
x y z
51 50 045
401 510
cost to
xyz
x y z
0 51 50
601 510
0 51 50
601 710
node y table
x y z
cost to xyz
064 5 401
510
cost to xyz
x y z
0 51 50
601 510
0 51 50
801 710
node z table
cost to xyz
x y z
045
401 510
cost to xyz
x y z
0 51 50 601 710
0 51 50 601 710
t0 t1 t2 t3 t4 time
60 y
41 50
x
z
from from from
from from from
from from from
Dz(x)=min{c(z,x)+ Dx(x), c(z,y)+ Dy(x)} =min{50+0,1+8}=9
cost to xyz
x y z
cost to xyz
x y z
cost to xyz
x y z
node x table
cost to xyz
x y z
51 50 045
401 510
cost to
xyz
x y z
0 51 50
601 510
0 51 50
601 710
node y table
x y z
cost to xyz
064 5 401
510
cost to xyz
x y z
0 51 50
601 510
0 51 50
801 710
node z table
cost to xyz
x y z
045
401 510
cost to xyz
x y z
0 51 50 601 710
0 51 50 601 710
cost to xyz
x y z
0 51 50
801 710
cost to xyz
x y z
0 51 50
801 710
cost to xyz
x y z
0 51 50 801 910
t0 t1 t2 t3 t4 time
60 y
41 50
x
z
from from from
from from from
from from from
from from from
Dy(x)=min{c(y,x)+ Dx(x), c(y,z)+ Dz(x)} =min{60+0,1+9}=10
cost to xyz
x y z
cost to xyz
x y z
cost to xyz
x y z
node x table
cost to xyz
x y z
51 50 045
401 510
cost to
xyz
x y z
0 51 50
601 510
cost to xyz
x y z
0 51 50
801 710
cost to xyz
x y z
0 51 50
801 910
0 51 50
601 710
node y table
x y z
cost to xyz
064 5 401
510
cost to xyz
x y z
0 51 50
601 510
cost to xyz
x y z
0 51 50
801 710
cost to xyz
x y z
0 51 50
10 0 1 910
0 51 50
801 710
….
node z table
cost to xyz
x y z
045
401 510
cost to xyz
x y z
0 51 50 601 710
cost to xyz
x y z
0 51 50 801 910
cost to xyz
x y z
0 51 50 801 910
0 51 50 601 710
t0 t1 t2 t3 t4 time
60 y
41 50
x
z
from from from
from from from
from from from
from from from
from from from
Discussions on Bellman-Ford algorithm II (cont’d)
Link cost change: scenario 2
At time t0, x and y detect the link-cost change (4→60), update their DV, and notify neighbors
At time t1, z receives updated DVs, computes a new least cost to x of Dz(x) = min {50+0, 1+6} = 7, and informs neighbors of its new DV
At time t2, y receives z’s update, recomputes Dy(x) = 8, and sends it to neighbors
At time t3, z receives y’s update, recomputes Dz(x) = 9, and sends it to neighbors
…
44 iterations before algorithm terminates!
Bad news travels slowly
=> “count to infinity” problem!
The problem in this scenario can be avoided by poisoned reverse: If Z routes through Y to get to X, Z tells Y its (Z’s) distance to X is
infinite (so Y won’t route to X via Z)
60 y
41 50
x
z
But it does not solve general count-to-infinity problem
Poisoned reverse
50
xyz xyz xyz xyz xyz xyz
node y table
cost to x 05150 x05150
y 6001 y5101 z ∞10 z5010
cost to xyz xyz xyz xyz xyz xyz
cost to
xyz xyz xyz xyz xyz xyz
60
y
z
4 x
1
node x table
x 5150 x 05150 x 05150 x 05150 x 05150 x y045yyyyy
cost to
05150 5101
cost to
cost to
cost to
cost to
cost to
4 0 1 6 0 1 z 5 1 0 z 5 1 0
6 0 1 z 7 1 0
60 0 1 z 7 1 0
60 0 1 z 50 1 0
z 50 1 0 cost to
cost to x045
cost to x 05150
cost to x 05150
x 05150 y 5101 z 5010
y 46 0 1 z510
y 601 z 510
y 6001 z ∞10
node z table
xy045 xy 05150 xy 05150 401 601 601 z510 z 710 z 710
cost to cost to
cost to
cost to
cost to
xy 05150 xy05150 xy 05150 6001 60 0 1 51 0 1
z 5010 z5010 z 50 1 0
t0t1t2t3t4t5 z routes to x through y; suppose it tells y that Dz(x) = ∞ in next round
from from from
from from from
from from from
from from from
from from from
from from from
Comparison of LS and DV algorithms
Message complexity
LS: with n nodes, E links, O(nE) msgs DV: exchange between neighbors only; convergence time varies
Convergence
LS: O(n2)algorithm requires O(nE) msgs;
may have oscillations
DV: convergence time varies;
may existing routing loops (count-to-infinity problem)
Both algorithms used in routing protocols in the Internet
LS algorithms used in OSPF, IS-IS. DV algorithms used in RIP, IGRP.
Required reading:
Computer Networking: A Top Down Approach (7th Edition) Ch 5.2
Acknowledgement:
Some materials are extracted from the slides created by Prof. Jim F. Kurose and Prof. Keith W. Ross for the textbook.