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
Hierarchical routing
scale: with 600 million
destinations:
v can’t store all dest’s in
routing tables!
v routing table exchange
would swamp links!
administrative
autonomy
v internet = network of
networks
v each network admin may
want to control routing in
its own network
our routing study thus far – idealization
v all routers identical
v network “flat”
… not true in practice
Network Layer 4-4
v aggregate routers
into regions,
“autonomous
systems” (AS)
v routers in same AS
run same routing
protocol
§ “intra-AS” routing
protocol
§ routers in different
AS can run different
intra-AS routing
protocol
gateway router:
v at “edge” of its own AS
v has link to router in
another AS
Hierarchical routing
Network Layer 4-5
3b
1d
3a
1c
2a AS3
AS1
AS2
1a
2c
2b
1b
Intra-AS
Routing
algorithm
Inter-AS
Routing
algorithm
Forwarding
table
3c
Interconnected ASes
v forwarding table
configured by both intra-
and inter-AS routing
algorithm
§ intra-AS sets entries
for internal dests
§ inter-AS & intra-AS
sets entries for
external dests
Network Layer 4-6
Inter-AS tasks
v suppose router in AS1
receives datagram
destined outside of
AS1:
§ router should forward
packet to gateway
router, but which
one?
AS1 must:
1. learn which dests are
reachable through
AS2, which through
AS3
2. propagate this
reachability info to all
routers in AS1
job of inter-AS routing!
AS3
AS2
3b
3c
3a
AS1
1c
1a
1d
1b
2a
2c
2b
other
networks
other
networks
Network Layer 4-7
Example: setting forwarding table in router
1d
v 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
v 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)
AS3
AS2
3b
3c
3a
AS1
1c
1a
1d
1b
2a
2c
2b
other
networks
other
networks
x …
Network Layer 4-8
Example: choosing among multiple ASes
v now suppose AS1 learns from inter-AS protocol that
subnet x is reachable from AS3 and from AS2.
v to configure forwarding table, router 1d must determine
which gateway it should forward packets towards for
dest x
§ this is also job of inter-AS routing protocol!
AS3
AS2
3b
3c
3a
AS1
1c
1a
1d
1b
2a
2c
2b
other
networks
other
networks
x …
?
Network Layer 4-9
learn from inter-AS
protocol that subnet
x is reachable via
multiple gateways
use routing info
from intra-AS
protocol to determine
costs of least-cost
paths to each
of the gateways
hot potato routing:
choose the gateway
that has the
smallest least cost
determine from
forwarding table the
interface I that leads
to least-cost gateway.
Enter (x,I) in
forwarding table
Example: choosing among multiple ASes
v now suppose AS1 learns from inter-AS protocol that
subnet x is reachable from AS3 and from AS2.
v 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!
v hot potato routing: send packet towards closest of two
routers.
Network Layer 4-10
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
Outline
Network Layer 4-11
Intra-AS Routing
v also known as interior gateway protocols
(IGP)
v most common intra-AS routing protocols:
§ RIP: Routing Information Protocol
§ OSPF: Open Shortest Path First
§ IGRP: Interior Gateway Routing Protocol
(Cisco proprietary)
Network Layer 4-12
RIP (Routing Information Protocol)
v included in BSD-UNIX distribution in 1982
v 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)
D C
B A
u v
w
x
y
z
subnet hops
u 1
v 2
w 2
x 3
y 3
z 2
from router A to destination subnets:
Network Layer 4-13
RIP: example
destination subnet next router # hops to dest
w A 2
y B 2
z B 7
x — 1
…. …. ….
routing table in router D
w x y
z
A
C
D B
Network Layer 4-14
w x y
z
A
C
D B
destination subnet next router # hops to dest
w A 2
y B 2
z B 7
x — 1
…. …. ….
routing table in router D
A 5
dest next hops
w – 1
x – 1
z C 4
…. … …
A-to-D advertisement
RIP: example
Network Layer 4-15
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)
§ poison reverse used to prevent ping-pong loops
(infinite distance = 16 hops)
Network Layer 4-16
RIP table processing
v RIP routing tables managed by application-
level process called route-d (daemon)
v advertisements sent in UDP packets,
periodically repeated
physical
link
network forwarding
(IP) table
transport
(UDP)
routed
physical
link
network
(IP)
transprt
(UDP)
routed
forwarding
table
Network Layer 4-17
OSPF (Open Shortest Path First)
v “open”: publicly available
v uses link state algorithm
§ LS packet dissemination
§ topology map at each node
§ route computation using Dijkstra’s algorithm
v OSPF advertisement carries one entry per
neighbour
v advertisements flooded to entire AS
§ carried in OSPF messages directly over IP (rather
than TCP or UDP
Network Layer 4-18
OSPF “advanced” features (not in
RIP)
v security: all OSPF messages authenticated (to
prevent malicious intrusion)
v multiple same-cost paths allowed (only one path
in RIP)
v for each link, multiple cost metrics for different
TOS (e.g., satellite link cost set “low” for best
effort ToS; high for real time ToS)
v hierarchical OSPF in large domains.
Network Layer 4-19
Hierarchical OSPF
boundary router
backbone router
area 1
area 2
area 3
backbone
area
border
routers
internal
routers
Network Layer 4-20
v two-level hierarchy: local area, backbone.
§ link-state advertisements only in area
§ each node has detailed area topology
v area border routers: “summarize” distances to
nets in own area, advertise to other Area Border
routers.
v backbone routers: run OSPF routing limited to
backbone.
v boundary routers: connect to other AS’s.
Hierarchical
OSPF
Network Layer 4-21
Summary
v Hierarchical routing
v Intra-AS routing in the Internet
§ RIP
§ OSPF