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-2
v introduction
v virtual circuit and datagram networks
v what’s inside a router
v IP: Internet Protocol
§ datagram format
§ IPv4 addressing (NAT)
§ ICMP, IPv6
v routing algorithms
§ link state, distance vector
§ hierarchical routing
v routing in the Internet
§ RIP, OSPF
§ BGP
v broadcast routing
Outline
Network Layer 4-3
1
2 3
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
routing algorithm determines
end-end-path through network
forwarding table determines
local forwarding at this router
Network Layer 4-4
u
y x
w v
z
2
2
1
3
1
1
2
5
3
5
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
Network Layer 4-5
Graph abstraction: costs
u
y x
w v
z
2
2
1
3
1
1
2
5
3
5 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
Network Layer 4-6
Routing algorithm classification
Q: global or decentralized
information?
global:
v all routers have complete
topology, link cost info
v “link state” algorithms
decentralized:
v router knows physically-
connected neighbors, link
costs to neighbors
v iterative process of
computation, exchange of
info with neighbors
v “distance vector”
algorithms
Q: static or dynamic?
static:
v routes change slowly
over time
dynamic:
v routes change more
quickly
§ periodic update
§ in response to link
cost changes
Network Layer 4-7
v introduction
v virtual circuit and datagram networks
v what’s inside a router
v IP: Internet Protocol
§ datagram format
§ IPv4 addressing (NAT)
§ ICMP, IPv6
v routing algorithms
§ link state, distance vector
§ hierarchical routing
v routing in the Internet
§ RIP, OSPF
§ BGP
v broadcast and multicast routing
Outline
Network Layer 4-8
A Link-State Routing Algorithm
Dijkstra’s algorithm
v network topology, link costs
known to all nodes
§ accomplished via “link state
broadcast”
§ all nodes have same info
v computes least cost paths
from one node (“source”)
to all other nodes
§ gives forwarding table for
that node
v iterative: after k iterations,
know least cost path to k
destination nodes
notation:
v c(x,y): link cost from node x to
y; = ∞ if not direct neighbors
v D(v): current value of cost of
path from source to dest. v
v p(v): predecessor node along
path from source to v
v N’: set of nodes whose least
cost path is definitively known
Network Layer 4-9
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 4-10
w 3
4
v
x
u
5
3
7 4
y
8
z
2
7
9
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,w uwx
uwxv 14,x 10,v
uwxvy 12,y
notes:
v construct shortest path tree
by tracing predecessor
nodes
v ties can exist (can be broken
arbitrarily)
uwxvyz
Network Layer 4-11
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 4-12
Dijkstra’s algorithm: example (2)
u
y x
w v
z
resulting shortest-path tree from u:
v
x
y
w
z
(u,v)
(u,x)
(u,x)
(u,x)
(u,x)
destination link
resulting forwarding table in u:
Network Layer 4-13
Dijkstra’s algorithm, discussion
algorithm complexity: n nodes
v each iteration: need to check all nodes, w, not in
N’
v n(n+1)/2 comparisons: O(n2)
v more efficient implementations possible: O(nlogn)
oscillations possible:
v e.g., support link cost equals amount of carried
traffic: A
D
C
B
1 1+e
e 0
e
1 1
0 0
initially
A
D
C
B
given these costs,
find new routing….
resulting in new costs
2+e 0
0 0
1+e 1
A
D
C
B
given these costs,
find new routing….
resulting in new costs
0 2+e
1+e 1
0 0
A
D
C
B
given these costs,
find new routing….
resulting in new costs
2+e 0
0 0
1+e 1
Network Layer 4-14
v introduction
v virtual circuit and datagram networks
v what’s inside a router
v IP: Internet Protocol
§ datagram format
§ IPv4 addressing (NAT)
§ ICMP, IPv6
v routing algorithms
§ link state, distance vector
§ hierarchical routing
v routing in the Internet
§ RIP, OSPF
§ BGP
v broadcast and multicast routing
Outline
Network Layer 4-15
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 4-16
Bellman-Ford example
u
y x
w v
z
2
2
1
3
1
1
2
5
3
5
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:
Network Layer 4-17
Distance vector algorithm
v Dx(y) = estimate of least cost from x to y
§ x maintains distance vector Dx = [Dx(y): y є N ]
v 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 4-18
key idea:
v from time-to-time, each node sends its own distance
vector estimate to neighbors
v 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
v under minor, natural conditions, the estimate
Dx(y) converge to the actual least cost dx(y)
Distance vector algorithm
Network Layer 4-19
iterative, asynchronous:
each local iteration caused
by:
v local link cost change
v DV update message from
neighbor
distributed:
v 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 4-20
x y z
x
y
z
0 2 7
∞ ∞ ∞
∞ ∞ ∞
fr
om
cost to
fr
om
fr
om
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
1 2
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
3 2
node y
table
node z
table
cost to
fr
om
Network Layer 4-21
x y z
x
y
z
0 2 3
fr
om
cost to
x y z
x
y
z
0 2 7
fr
om
cost to
x y z
x
y
z
0 2 3
fr
om
cost to
x y z
x
y
z
0 2 3
fr
om
cost to
x y z
x
y
z
0 2 7
fr
om
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
om
cost to
fr
om
fr
om
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
1 2
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
3 2
node y
table
node z
table
cost to
fr
om
Network Layer 4-22
Distance vector: link cost changes
link cost changes:
v node detects local link cost change
v updates routing info, recalculates
distance vector
v if DV changes, notify neighbors
“good
news
travels
fast”
x z
1 4
50
y
1
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.
Network Layer 4-23
Distance vector: link cost changes
link cost changes:
v node detects local link cost
change
v bad news travels slow – “count
to infinity” problem!
v 44 iterations before algorithm
stabilizes: see text
x z
1 4
50
y
60
poisoned reverse:
v 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)
Network Layer 4-24
Comparison of LS and DV algorithms
message complexity
v LS: with n nodes, E links,
O(nE) msgs sent
v DV: exchange between
neighbors only
§ convergence time varies
speed of convergence
v LS: O(n2) algorithm requires
O(nE) msgs
§ may have oscillations
v 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 4-25
Summary
v routing algorithms
§ distance-vector
§ link-state