PowerPoint Presentation
Network Layer
All material copyright 1996-2012
J.F Kurose and K.W. Ross, All Rights Reserved
George Parisis
School of Engineering and Informatics
University of Sussex
Network Layer
4-*
introduction
virtual circuit and datagram networks
what’s inside a router
IP: Internet Protocol
datagram format
IPv4 addressing (NAT)
ICMP, IPv6
routing algorithms
link state, distance vector
hierarchical routing
routing in the Internet
RIP, OSPF
BGP
broadcast routing
Outline
Network Layer
Network Layer
4-*
IP destination address in
arriving packet’s header
routing algorithm
local forwarding table
dest address
output link
address-range 1
address-range 2
address-range 3
address-range 4
3
2
2
1
Interplay between routing, forwarding
1
2
3
routing algorithm determines
end-end-path through network
forwarding table determines
local forwarding at this router
Network Layer
Network Layer
4-*
graph: G = (N,E)
N = set of routers = { u, v, w, x, y, z }
E = set of links ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }
Graph abstraction
u
y
x
w
v
z
2
2
1
3
1
1
2
5
3
5
Network Layer
Network Layer
4-*
Graph abstraction: costs
c(x,x’) = cost of link (x,x’)
e.g., c(w,z) = 5
cost could always be 1, or
related to bandwidth or 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
u
y
x
w
v
z
2
2
1
3
1
1
2
5
3
5
Network Layer
Network Layer
4-*
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
Network Layer
Network Layer
4-*
introduction
virtual circuit and datagram networks
what’s inside a router
IP: Internet Protocol
datagram format
IPv4 addressing (NAT)
ICMP, IPv6
routing algorithms
link state, distance vector
hierarchical routing
routing in the Internet
RIP, OSPF
BGP
broadcast and multicast routing
Outline
Network Layer
Network Layer
4-*
A Link-State Routing Algorithm
Dijkstra’s algorithm
network 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 destination nodes
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 is definitively known
Network Layer
Network Layer
4-*
Dijsktra’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’
Network Layer
Network Layer
4-*
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
uw
uwx
uwxv
uwxvy
12,y
notes:
construct shortest path tree by tracing predecessor nodes
ties can exist (can be broken arbitrarily)
uwxvyz
w
v
x
u
y
z
3
4
5
3
7
4
8
2
7
9
∞
∞
7,u
3,u
5,u
∞
11,w
6,w
5,u
14,x
11,w
6,w
14,x
10,v
Network Layer
Network Layer
4-*
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
u
y
x
w
v
z
2
2
1
3
1
1
2
5
3
5
Network Layer
Network Layer
4-*
Dijkstra’s algorithm: example (2)
resulting shortest-path tree from u:
resulting forwarding table in u:
u
y
x
w
v
z
v
x
y
w
z
(u,v)
(u,x)
(u,x)
(u,x)
(u,x)
destination
link
Network Layer
Network Layer
4-*
Dijkstra’s algorithm, discussion
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(nlogn)
oscillations possible:
e.g., support link cost equals amount of carried traffic:
Network Layer
Network Layer
4-*
introduction
virtual circuit and datagram networks
what’s inside a router
IP: Internet Protocol
datagram format
IPv4 addressing (NAT)
ICMP, IPv6
routing algorithms
link state, distance vector
hierarchical routing
routing in the Internet
RIP, OSPF
BGP
broadcast and multicast routing
Outline
Network Layer
Network Layer
4-*
Distance vector algorithm
Bellman-Ford equation (dynamic programming)
let
dx(y) := cost of least-cost path from x to y
then
dx(y) = min {c(x,v) + dv(y) }
v
cost to neighbor v
min taken over all neighbors v of x
cost from neighbor v to destination y
Network Layer
Network Layer
4-*
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
node achieving minimum is next hop in shortest path, used in forwarding table
B-F equation says:
u
y
x
w
v
z
2
2
1
3
1
1
2
5
3
5
Network Layer
Network Layer
4-*
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 ]
Network Layer
Network Layer
4-*
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)
Distance vector algorithm
Network Layer
Network Layer
4-*
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 destination has changed, notify neighbors
each node:
Distance vector algorithm
Network Layer
Network Layer
4-*
x y z
x
y
z
0 2 7
∞
∞
∞
∞
∞
∞
from
cost to
from
from
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
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
3
2
node y
table
node z
table
cost to
from
x
z
y
1
2
7
Network Layer
Network Layer
4-*
x y z
x
y
z
0 2 3
from
cost to
x y z
x
y
z
0 2 7
from
cost to
x y z
x
y
z
0 2 3
from
cost to
x y z
x
y
z
0 2 3
from
cost to
x y z
x
y
z
0 2 7
from
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
∞
∞
∞
∞
∞
∞
from
cost to
from
from
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
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
3
2
node y
table
node z
table
cost to
from
x
z
y
1
2
7
Network Layer
Network Layer
4-*
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.
x
z
y
1
4
50
1
Network Layer
Network Layer
4-*
Distance vector: link cost changes
link cost changes:
node detects local link cost change
bad news travels slow – “count to infinity” problem!
44 iterations before algorithm stabilizes: see text
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)
x
z
y
1
4
50
60
Network Layer
Network Layer
4-*
Comparison of LS and DV algorithms
message complexity
LS: with n nodes, E links, O(nE) msgs sent
DV: exchange between neighbors only
convergence time varies
speed of convergence
LS: O(n2) algorithm requires O(nE) msgs
may have oscillations
DV: convergence time varies
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 thru network
Network Layer
Network Layer
4-*
Summary
routing algorithms
distance-vector
link-state
Network Layer
least-cost path to w is now clockwise. Similarly, x determines that its new least-cost
path to w is also clockwise, resulting in costs shown in Figure 4.29(b). When the
LS algorithm is run next, nodes x, y, and z all detect a zero-cost path to w in the
counterclockwise direction, and all route their traffic to the counterclockwise
routes. The next time the LS algorithm is run, x, y, and z all then route their traffic
to the clockwise routes.
What can be done to prevent such oscillations (which can occur in any algo-
rithm, not just an LS algorithm, that uses a congestion or delay-based link met-
ric)? One solution would be to mandate that link costs not depend on the amount
of traffic carried—an unacceptable solution since one goal of routing is to avoid
370 CHAPTER 4 • THE NETWORK LAYER
w
y
z x
1
0 0
0 e
1 + e
1
a. Initial routing
1
e
w
y
z x
2 + e
1 + e 1
0 0
0
b. x, y detect better path
to w, clockwise
w
y
z x
0
0 0
1 1 + e
2+ e
c. x, y, z detect better path
to w, counterclockwise
w
y
z x
2 + e
1 + e 1
0 0
0
d. x, y, z, detect better path
to w, clockwise
1 1
e
1 1
e
1 1
e
Figure 4.29 ! Oscillations with congestion-sensitive routing
least-cost path to w is now clockwise. Similarly, x determines that its new least-cost
path to w is also clockwise, resulting in costs shown in Figure 4.29(b). When the
LS algorithm is run next, nodes x, y, and z all detect a zero-cost path to w in the
counterclockwise direction, and all route their traffic to the counterclockwise
routes. The next time the LS algorithm is run, x, y, and z all then route their traffic
to the clockwise routes.
What can be done to prevent such oscillations (which can occur in any algo-
rithm, not just an LS algorithm, that uses a congestion or delay-based link met-
ric)? One solution would be to mandate that link costs not depend on the amount
of traffic carried—an unacceptable solution since one goal of routing is to avoid
370 CHAPTER 4 • THE NETWORK LAYER
w
y
z x
1
0 0
0 e
1 + e
1
a. Initial routing
1
e
w
y
z x
2 + e
1 + e 1
0 0
0
b. x, y detect better path
to w, clockwise
w
y
z x
0
0 0
1 1 + e
2+ e
c. x, y, z detect better path
to w, counterclockwise
w
y
z x
2 + e
1 + e 1
0 0
0
d. x, y, z, detect better path
to w, clockwise
1 1
e
1 1
e
1 1
e
Figure 4.29 ! Oscillations with congestion-sensitive routing