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
Hierarchical routing
scale: with 600 million
destinations:
v cant store all dests 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 Iis 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 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
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
subnethops
u 1
v 2
w2
x 3
y 3
z 2
from router A to destination subnets:
Network Layer 4-13
RIP: example
destination subnetnextrouter# hops to dest
wA 2
yB 2
zB 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 subnetnextrouter# hops to dest
wA 2
yB 2
zB 7
x 1
.. .
routing table in router D
A 5
dest nexthops
w 1
x 1
zC4
.
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 Dijkstras 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 distancesto
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 ASs.
Hierarchical
OSPF
Network Layer 4-21
Summary
v Hierarchical routing
v Intra-AS routing in the Internet
RIP
OSPF
Reviews
There are no reviews yet.