[SOLVED] algorithm Network Layer

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 whats 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 packets header

routing algorithm

local forwarding table
dest address outputlink

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 whats 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
Dijkstras 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

Dijsktras Algorithm
1Initialization:
2N = {u}
3for all nodes v
4if v adjacent to u
5then D(v) = c(u,v)
6else D(v) =
7
8 Loop
9 find w not in N such that D(w) is a minimum
10add w to N
11update 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 */
15until all nodes in N

Network Layer 4-10

w 3

4

v

x

u

5

3
7 4

y
8

z
2

7
9

Dijkstras 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,w6,w 5,u

14,x11,w6,w uwx
uwxv 14,x10,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

Dijkstras 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

Dijkstras 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

Dijkstras 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 whats 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 maintainsdistance vector Dx = [Dx(y): y N ]
v node x:

knows cost to each neighbor v: c(x,v)
maintains its neighborsdistance 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

02 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

02 3

fr
om

cost to

x y z

x
y
z

02 7

fr
om

cost to

x y z

x
y
z

02 3

fr
om

cost to

x y z

x
y
z

02 3
fr

om

cost to
x y z

x
y
z

02 7

fr
om

cost to

20 1
7 1 0

20 1
31 0

2 0 1
31 0

20 1

31 0

20 1

31 0

time

x y z

x
y
z

02 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 zs update, updates its distance table.ys least costs
do not change, so ydoes 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 (Zs) distance to X is infinite (so Y wont
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 nodes table used by
others

error propagate thru
network

Network Layer 4-25

Summary

v routing algorithms
distance-vector
link-state