Network Layer Part II & III

Routing Algorithms

Refer to Chapter 4 of the textbook

Interplay between routing, forwarding

routing algorithm determines

routing algorithm
end-end-path through network
forwarding table determines
local forwarding table
dest address
local forwarding at this router
output
address-range 1 3 link
address-range 2 2
address-range 3 2
address-range 4 1

IP destination address in
arriving packet’s header
1
3 2

Network Layer 4-2

Graph abstraction
5
3
v w 5
2
u 2 1 z
3
1 2
x 1
y
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) }

Network Layer 4-3

Graph abstraction: costs
5
c(x,x’) = cost of link (x,x’)
3 e.g., c(w,z) = 5
v w 5
2
u cost could always be 1, or
2
3
1 z inversely related to bandwidth,
1 2 or inversely related to
x 1
y
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-4

Routing algorithm classification

Q: global or decentralized Q: static or dynamic?

information?
static:
global:  routes change slowly over
 all routers have complete
topology, link cost info
time
 “ link state” algorithms dynamic:
 routes change more
decentralized:
 router knows physically- quickly
connected neighbors, link costs  periodic update
to neighbors  in response to link cost
 iterative process of computation, changes
exchange of info with neighbors
 “ distance vector” algorithms

Network Layer 4-5

A Link-State Routing Algorithm

Dijkstra’s algorithm notation:

 net topology, link costs  c(x,y): link cost from
known to all nodes node x to y; = ∞ if not
 accomplished via “ link direct neighbors
state broadcast”  D(v): current value of
 all nodes have same info cost of path from source to
 computes least cost paths dest. v
from one node (“source” )  p(v): predecessor node
to all other nodes along path from source to
 gives forwarding table for v
that node  N': set of nodes whose
 iterative: after k iterations, least cost path definitively
know least cost path to k known
destinations
Network Layer 4-6
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-7

Dijkstra’s algorithm: example
D(v) D(w) D(x) D(y) D(z)
Step N' p(v) p(w) p(x) p(y) p(z)
0 u 7,u 3,u 5,u ∞ ∞
1 uw 6,w 5,u 11,w ∞ e.g ., D(v)  min( D(v), D( w)  c( w, v))
2 uwx 6,w 11,w 14,x  min{7,3  3}  6
3 uwxv 10,v 14,x
4 uwxvy 12,y
5 uwxvyz x
9

notes: 5 7
4
 construct shortest path tree by
tracing predecessor nodes 8
 ties can exist (can be broken u
3 w y z
arbitrarily) 2
3
7 4
v
Network Layer 4-8
Dijkstra’s algorithm: example

x resulting forwarding
9
table in u:
5 7
4 destination link
8 (u,w)
v
3 w z x (u,x)
u y
2
y (u,w)
3
4 w (u,w)
7
z (u,w)
v

Network Layer 4-9

 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., suppose link cost equals amount of carried traffic:

1
A 1+e A A A
2+e 0 0 2+e 2+e 0
D 0 0 B D 1+e 1 B D B D 1+e 1 B
0 0
0 e 0 0
1
C C 0 1
C 1+e C 0
1
e
given these costs, given these costs, given these costs,
initially find new routing…. find new routing…. find new routing….
resulting in new costs resulting in new costs resulting in new costs
Network Layer 4-10
Distance vector algorithm
Bellman-Ford equation (dynamic programming)

let
dx(y) := cost of least-cost path from x to y
then
dx(y) = min
v {c(x,v) + dv(y) }
cost from neighbor v to destination y
cost to neighbor v

min taken over all neighbors v of x

Network Layer 4-11
Bellman-Ford example
5
3
clearly, dv(z) = 5, dx(z) = 3, dw(z) = 3
v w 5
2
u 2 1 z B-F equation says:
3
1 2 du(z) = min { c(u,v) + dv(z),
x 1
y
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
Network Layer 4-12
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 4-13

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:
Dx(y) ← minv{c(x,v) + Dv(y)} for each node y ∊ N

Network Layer 4-14

Distance vector algorithm
iterative, asynchronous: each node:
each local iteration caused
by:
 local link cost change wait for (change in local link
cost or msg from neighbor)
 DV update message from
neighbor
distributed: recompute estimates
 each node notifies
neighbors only when its
DV changes if DV to any dest has
 neighbors then notify their changed, notify neighbors
neighbors if necessary

Network Layer 4-15

 Dx(z) = min{c(x,y) +
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)}
= min{2+0 , 7+1} = 2 Dy(z), c(x,z) + Dz(z)}
= min{2+1 , 7+0} = 3
node x cost to cost to
table x y z x y z
x 0 2 7 x 0 2 3

from
y ∞∞ ∞ y 2 0 1
from

z ∞∞ ∞ z 7 1 0

node y cost to
table x y z y
2 1
x ∞ ∞ ∞
x z
from

y 2 0 1 7
z ∞∞ ∞

node z cost to
table x y z
x ∞∞ ∞
from

y ∞∞ ∞
z 7 1 0
time
Network Layer 4-16
 Dx(z) = min{c(x,y) +
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)}
= min{2+0 , 7+1} = 2 Dy(z), c(x,z) + Dz(z)}
= min{2+1 , 7+0} = 3
node x cost to cost to cost to
table x y z x y z x y z
x 0 2 7 x 0 2 3 x 0 2 3

from
y ∞∞ ∞ y 2 0 1
from

y 2 0 1

from
z ∞∞ ∞ z 7 1 0 z 3 1 0
node y cost to cost to cost to
table x y z x y z x y z y
2 1
x ∞ ∞ ∞ x 0 2 7 x 0 2 3 x z
from

y 2 0 1 y 2 0 1 7
from

y 2 0 1

from
z ∞∞ ∞ z 7 1 0 z 3 1 0

node z cost to cost to cost to

table x y z x y z x y z

x ∞∞ ∞ x 0 2 7 x 0 2 3
from

from

y 2 0 1 y 2 0 1
from

y ∞∞ ∞
z 7 1 0 z 3 1 0 z 3 1 0
time
Network Layer 4-17
Distance Vector: Link Cost Changes

Link cost changes: 1

Y
4 1
• Node detects local link cost change
X Z
• Updates the distance table 50

• If cost change in least cost path, notify neighbors

algorithm
terminates
“good
news
travels
fast”

18
Distance Vector: Link Cost Changes
Link cost changes: 60
Y
• Good news travels fast 4 1
• Bad news travels slow - “count to X Z
50
infinity” problem!

algorithm
continues
on!

19
Comparison of LS and DV algorithms

message complexity robustness: what happens if

 LS: with n nodes, E links, O(nE) router malfunctions?
msgs sent LS:
 DV: exchange between neighbors  node can advertise incorrect
only link cost
 convergence time varies  each node computes only its
own table
speed of convergence DV:
 LS: O(n2) algorithm requires
O(nE) msgs  DV node can advertise
incorrect path cost
 may have oscillations
 each node’s table used by
 DV: convergence time varies others
 may be routing loops • error propagate thru
 count-to-infinity problem network

Network Layer 4-20

Hierarchical routing
our routing study thus far - idealization
 all routers identical
 network “ flat”

… not true in practice

scale: with 600 million administrative autonomy

destinations:  internet = network of
 can’t store all dest’s in networks
routing tables!  each network admin may
 routing table exchange want to control routing in its
would swamp links! own network

Network Layer 4-21

Hierarchical routing
 collect routers into  routers in same AS run
regions, “ autonomous same routing protocol
systems” (AS)  “ intra-AS” routing
 Each AS within an ISP protocol
 ISP may consist of one  routers in different AS
or more ASes can run different intra-
AS routing protocol
gateway router:
 at “ edge” of its own AS
 has link to router in another
AS

Network Layer 4-22

Interconnected ASes

3c
3a 2c
3b 2a
AS3 2b
1c AS2
1a 1b AS1
1d  forwarding table
configured by both intra-
and inter-AS routing
Intra-AS Inter-AS algorithm
Routing Routing
algorithm algorithm  intra-AS sets entries
Forwarding
for internal dests
table  inter-AS & intra-AS
sets entries for external
dests
Network Layer 4-23
 Inter-AS tasks
 suppose router in AS1 AS1 must:
receives datagram 1. learn which dests are
destined outside of AS1: reachable through AS2,
 router should forward which through AS3
packet to gateway 2. propagate this
router, but which one? reachability info to all
routers in AS1
job of inter-AS routing!

3c
3a
3b
AS3 2c other
1c 2a networks
other 1a 2b
networks 1b AS2
AS1 1d

Network Layer 4-24

 Example: setting forwarding table in router 1d
 suppose AS1 learns (via inter-AS protocol) that subnet x
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)

3c … x
3a
3b
AS3 2c other
1c 2a networks
other 1a 2b
networks 1b AS2
AS1 1d

Network Layer 4-25

 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
towards which gateway it should forward packets for dest x
 this is also job of inter-AS routing protocol!
 hot potato routing: send packet towards closest of two
routers.

use routing info determine from

learn from inter-AS hot potato routing: forwarding table the
from intra-AS
protocol that subnet choose the gateway interface I that leads
protocol to determine
x is reachable via that has the to least-cost gateway.
costs of least-cost
multiple gateways smallest least cost Enter (x,I) in
paths to each
of the gateways forwarding table

Network Layer 4-26

Intra-AS Routing
 also known as interior gateway protocols (IGP)
 most common intra-AS routing protocols:
 RIP: Routing Information Protocol
 OSPF: Open Shortest Path First

Network Layer 4-27

 RIP ( Routing Information Protocol)
 included in BSD-UNIX distribution in 1982
 distance vector algorithm
 distance metric: # hops (max = 15 hops), each link has cost 1
 DVs exchanged with neighbors every 30 sec in response message (aka advertisement)
 each advertisement: list of up to 25 destination subnets (in IP addressing sense)

from router A to destination subnets:

u v subnet hops
w u 1
A B
v 2
w 2
x x 3
z C D y 3
y z 2
Network Layer 4-28
RIP: example

z
w x y
A D B

C
routing table in router D
destination subnet next router # hops to dest
w A 2
y B 2
z B 7
x -- 1
…. …. ....
Network Layer 4-29
RIP: example
A-to-D advertisement
dest next hops
w - 1
x - 1
z C 4
…. … ... z
w x y
A D B

C
routing table in router D
destination subnet next router # hops to dest
w A 2
y B 2
A 5
z B 7
x -- 1
…. …. ....
Network Layer 4-30
RIP: link failure, recovery
if no advertisement heard after 180 sec -->
neighbor/link declared dead
 routes via neighbor invalidated
 new advertisements sent to neighbors
 neighbors in turn send out new advertisements (if tables
changed)
 link failure info propagates to entire net

Network Layer 4-31

RIP table processing

 RIP routing tables managed by application-level

process called route-d (daemon)
 advertisements sent in UDP packets, periodically
repeated
routed routed

transport transprt
(UDP) (UDP)
network forwarding forwarding network
(IP) table table (IP)
link link
physical physical

Network Layer 4-32

OSPF (Open Shortest Path First)

 “ open” : publicly available

 uses link state algorithm
 LS packet dissemination
 topology map at each node
 route computation using Dijkstra’s algorithm
 OSPF advertisement carries one entry per neighbor

Network Layer 4-33

 Internet inter-AS routing: BGP
 BGP session: two BGP routers (“ peers” ) exchange BGP
messages:
 advertising paths to different destination network prefixes (“ path vector”
protocol)

 when AS3 advertises a prefix to AS1:

 AS3 promises it will forward datagrams towards that prefix
 AS3 can aggregate prefixes in its advertisement

3c
BGP
3a message
3b
AS3 2c other
1c 2a networks
other 1a 2b
networks 1b AS2
AS1 1d

Network Layer 4-34

Why different Intra-, Inter-AS routing ?
policy:
 inter-AS: admin wants control over how its traffic
routed, who routes through its net.
 intra-AS: single admin, so no policy decisions needed
scale:
 hierarchical routing saves table size, reduced update
traffic
performance:
 intra-AS: can focus on performance
 inter-AS: policy may dominate over performance

Network Layer 4-35

 Unicast, Broadcast, and Multicast
Key:
Unicast transfer

 Unicast Broadcast transfer

Multicast transfer
 One-to-one
 Destination – unique receiver
host address
 Broadcast
 One-to-all
 Destination – address of network
 Multicast
 One-to-many
 Multicast group must be
identified
 Destination – address of group
 Broadcast routing
 deliver packets from source to all other nodes
 source duplication is inefficient:
duplicate
duplicate R1 creation/transmission R1
duplicate
R2 R2

R3 R4 R3 R4

source in-network
duplication duplication

 source duplication: how does source determine

recipient addresses?
Network Layer 4-37
 In-network duplication
 flooding: when node receives broadcast packet, sends
copy to all neighbors S
 problems: cycles & broadcast storm R1 R2 R3

R5 R4
 controlled flooding: node only broadcasts pkt if it hasn’t
broadcast same packet before
 node keeps track of packet ids already broadacsted
 or reverse path forwarding (RPF):
• only forward packet if it arrived on shortest path between node and
source
 Spanning tree
Network Layer 4-38
Spanning tree
 first construct a spanning tree
 nodes then forward/make copies only along
spanning tree

A A

B B
c c

D D
F E F E

G G
(a) broadcast initiated at A (b) broadcast initiated at D

Network Layer 4-39

Spanning tree: creation
 center node
 each node sends unicast join message to center
node
 message forwarded until it arrives at a node already
belonging to spanning tree

A A
3
B B
c c
4
2
D D
F E F E
1 5
G G
(a) stepwise construction of (b) constructed spanning
spanning tree (center: E) tree
Network Layer 4-40
Multicast Routing
Internet Group Management Protocol (IGMP)

 IETF standard for managing multicast groups

 IGMP allows a host to communicate with local multicast router
 Using IGMP, a host can dynamically
 join a multicast group
 leave a multicast group
 IGMP is part of IP
 IGMP Messages
 Four types of messages
 Joining a group
 membership report
 Leaving a group
 leave report
 Maintenance
 query
 membership report
IGMP Message Format
 IGMP: Joining a Group
 An application process sends group id to IGMP module within host
 Host sends a membership report message if this is the first entry for
this group
 Local routers adds this group if it was not in database of active
groups, and propagates appropriate messages to other routers
 IGMP: Leaving a Group
 If no process is interested in
a specific group, host sends
a leave report
 Router cannot immediately
purge group
 there may be other
interested hosts
 Router sends a special
query message
 purge group if no
response within a
response time
 IGMP: Membership Monitoring
 Imagine only one host
for a group, and the host
died
 router will never
receive leave
message!
 Router periodically
sends general query
message
 Router expects reponse
for each group
 Hosts delay response to
reduce traffic
 IGMP: Delayed Response
 Too much (unnecessary) traffic if every host responds
 response is delayed
 Hosts wait a random time between zero and maximum
response time
 maintains a timer for each group
 If it sees another response while waiting (responses are
broadcast), it does NOT send response (cancels its
timer)
IP multicast routing
 Purpose: share a Group information among
routers, to implement a better routing for data
distribution
 Distribution tree structure
 Source tree vs shared tree
Source distribution tree
Shared distribution tree
Source tree characteristics
 Source tree
 More memory O (G x S ) in routers
 optimal path from source to receiver, minimizes delay
 good for
 small number of senders, many receivers such as Radio
broadcasting application
Shared tree characteristics
 Shared tree
 less memory O (G) in routers
 Sub-optimal path from source to receiver, may
introduce extra delay (source to root)
 May have duplicate data transfer (possible duplication
of a path from source to root and a path from root to
receivers)
 Good for
 Many senders with low bandwidth
 environment such as most part of the shared tree is
identical to the source tree
Conclusion
 In network layer, we have discussed
 IP address, subnet, forwarding table, and NAT
 Link state and distance vector routing algorithms
 Intra-AS routing and Inter-AS routing
 Broadcast and Multicast

Network Layer 4-54