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
Internet inter-AS routing: BGP
v BGP (Border Gateway Protocol): the de facto
inter-domain routing protocol
§ “glue that holds the Internet together”
v BGP provides each AS a means to:
§ eBGP: obtain subnet reachability information
from neighboring ASs.
§ iBGP: propagate reachability information to all
AS-internal routers.
§ determine “good” routes to other networks based
on reachability information and policy.
v allows subnet to advertise its existence to
rest of Internet: “I am here”
Network Layer 4-4
BGP basics
v when AS3 advertises a prefix to AS1:
§ AS3 promises it will forward datagrams towards that prefix
§ AS3 can aggregate prefixes in its advertisement
AS3
AS2
3b
3c
3a
AS1
1c
1a
1d
1b
2a
2c
2b
other
networks
other
networks
v BGP session: two BGP routers (“peers”) exchange BGP
messages:
§ advertising paths to different destination network prefixes (“path
vector” protocol)
§ exchanged over semi-permanent TCP connections
BGP
message
Network Layer 4-5
BGP basics: distributing path
information
AS3
AS2
3b
3a
AS1
1c
1a
1d
1b
2a
2c
2b
other
networks
other
networks
v using eBGP session between 3a and 1c, AS3 sends
prefix reachability info to AS1.
§ 1c can then use iBGP do distribute new prefix info to all
routers in AS1
§ 1b can then re-advertise new reachability info to AS2 over
1b-to-2a eBGP session
v when router learns of new prefix, it creates entry for
prefix in its forwarding table.
eBGP session
iBGP session
Network Layer 4-6
Path attributes and BGP
routes
v advertised prefix includes BGP attributes
§ prefix + attributes = “route”
v two important attributes:
§ AS-PATH: contains ASs through which prefix
advertisement has passed: e.g., AS 67, AS 17
• Prevent loops
§ NEXT-HOP: indicates specific internal-AS router to
next-hop AS.
v gateway router receiving route advertisement
uses import policy to accept/decline
§ e.g., never route through AS x
§ policy-based routing
Network Layer 4-7
BGP route selection
v router may learn about more than 1 route to
destination AS, selects route based on:
1. local preference value attribute: policy decision
2. shortest AS-PATH
3. closest NEXT-HOP router: hot potato routing
4. additional criteria
Putting it Altogether:
How Does an Entry Get Into a
Router’s Forwarding Table?
v Answer is complicated!
v Ties together hierarchical routing (Section
4.5.3) with BGP (4.6.3) and OSPF (4.6.2).
v Provides nice overview of BGP!
1
2 3
Dest IP
routing algorithms
local forwarding table
prefix output port
138.16.64/22
124.12/16
212/8
…………..
3
2
4
…
How does entry get in forwarding
table?
entry
Assume prefix is
in another AS.
High-level overview
1. Router becomes aware of prefix
2. Router determines output port for prefix
3. Router enters prefix-port in forwarding table
How does entry get in forwarding
table?
Router becomes aware of
prefix
AS3
AS2
3b
3c
3a
AS1
1c
1a
1d
1b
2a
2c
2b
other
networks
other
networks
BGP
message
v BGP message contains “routes”
v “route” is a prefix and attributes: AS-PATH, NEXT-HOP,
…
v Example: route:
v Prefix:138.16.64/22 ; AS-PATH: AS3 AS131 ;
NEXT-HOP: 201.44.13.125
Router may receive multiple
routes
AS3
AS2
3b
3c
3a
AS1
1c
1a
1d
1b
2a
2c
2b
other
networks
other
networks
BGP
message
v Router may receive multiple routes for same
prefix
v Has to select one route
v Router selects route based on shortest AS-
PATH
Select best BGP route to
prefix
v Example:
v AS2 AS17 to 138.16.64/22
v AS3 AS131 AS201 to 138.16.64/22
v What if there is a tie? We’ll come back to
that!
select
Find best intra-route to BGP
route
v Use selected route’s NEXT-HOP attribute
§ Route’s NEXT-HOP attribute is the IP address of the
router interface that begins the AS PATH.
v Example:
v AS-PATH: AS2 AS17 ; NEXT-HOP: 111.99.86.55
v Router uses OSPF to find shortest path from 1c
to 111.99.86.55
AS3
AS2
3b
3c
3a
AS1
1c
1a
1d
1b
2a
2c
2b
other
networks
other
networks
111.99.86.55
Router identifies port for route
v Identifies port along the OSPF shortest path
v Adds prefix-port entry to its forwarding table:
§ (138.16.64/22 , port 4)
AS3
AS2
3b
3c
3a
AS1
1c
1a
1d
1b
2a
2c
2b
other
networks
other
networks
router
port
1
2 3
4
Hot Potato Routing
v Suppose there two or more best inter-routes.
v Then choose route with closest NEXT-HOP
§ Use OSPF to determine which gateway is closest
§ Q: From 1c, chose AS3 AS131 or AS2 AS17?
§ A: route AS3 AS201 since it is closer
AS3
AS2
3b
3c
3a
AS1
1c
1a
1d
1b
2a
2c
2b
other
networks
other
networks
Summary
1. Router becomes aware of prefix
§ via BGP route advertisements from other routers
2. Determine router output port for prefix
§ Use BGP route selection to find best inter-AS
route
§ Use OSPF to find best intra-AS route leading to
best inter-AS route
§ Router identifies router port for that best route
3. Enter prefix-port entry in forwarding table
How does entry get in forwarding
table?
Network Layer 4-18
BGP routing policy
v A,B,C are provider networks
v X,W,Y are customer (of provider networks)
v X is dual-homed: attached to two networks
§ X does not want to route from B via X to C
§ .. so X will not advertise to B a route to C
A
B
C
W
X
Y
legend:
customer
network:
provider
network
Network Layer 4-19
BGP routing policy (2)
v A advertises path AW to B
v B advertises path BAW to X
v Should B advertise path BAW to C?
§ No way! B gets no “revenue” for routing CBAW since neither W
nor C are B’s customers
§ B wants to force C to route to w via A
§ B wants to route only to/from its customers!
A
B
C
W
X
Y
legend:
customer
network:
provider
network
Network Layer 4-20
Why different Intra-, Inter-AS
routing ?
policy:
v inter-AS: admin wants control over how its traffic
routed, who routes through its net.
v intra-AS: single admin, so no policy decisions
needed
scale:
v hierarchical routing saves table size, reduced
update traffic
performance:
v intra-AS: can focus on performance
v inter-AS: policy may dominate over performance
Network Layer 4-21
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-22
R1
R2
R3 R4
source
duplication
R1
R2
R3 R4
in-network
duplication
duplicate
creation/transmission duplicate
duplicate
Broadcast routing
v deliver packets from source to all other nodes
v source duplication is inefficient:
v source duplication: how does source determine
recipient addresses?
Network Layer 4-23
In-network duplication
v flooding: when node receives broadcast
packet, sends copy to all neighbors
§ problems: cycles & broadcast storm
v controlled flooding: node only broadcasts pkt
if it hasn’t broadcast same packet before
§ node keeps track of packet ids already
broadcasted
§ or reverse path forwarding (RPF): only forward
packet if it arrived on shortest path between node
and source
v spanning tree:
§ no redundant packets received by any node
Reverse Path Forwarding
Network Layer 4-24
packet is duplicated and forwarded to all the node’s neighbors (except the node from
which the packet has just been received). The Gnutella protocol, discussed in Chap-
ter 2, uses sequence-number-controlled flooding to broadcast queries in its overlay
network. (In Gnutella, message duplication and forwarding is performed at the
application layer rather than at the network layer.)
A second approach to controlled flooding is known as reverse path forwarding
(RPF) [Dalal 1978], also sometimes referred to as reverse path broadcast (RPB). The
idea behind RPF is simple, yet elegant. When a router receives a broadcast packet
with a given source address, it transmits the packet on all of its outgoing links (except
the one on which it was received) only if the packet arrived on the link that is on its
own shortest unicast path back to the source. Otherwise, the router simply discards
the incoming packet without forwarding it on any of its outgoing links. Such a packet
can be dropped because the router knows it either will receive or has already received
a copy of this packet on the link that is on its own shortest path back to the sender.
(You might want to convince yourself that this will, in fact, happen and that looping
and broadcast storms will not occur.) Note that RPF does not use unicast routing to
actually deliver a packet to a destination, nor does it require that a router know the
complete shortest path from itself to the source. RPF need only know the next neigh-
bor on its unicast shortest path to the sender; it uses this neighbor’s identity only to
determine whether or not to flood a received broadcast packet.
Figure 4.44 illustrates RPF. Suppose that the links drawn with thick lines repre-
sent the least-cost paths from the receivers to the source (A). Node A initially broad-
casts a source-A packet to nodes C and B. Node B will forward the source-A packet
it has received from A (since A is on its least-cost path to A) to both C and D. B will
ignore (drop, without forwarding) any source-A packets it receives from any other
402 CHAPTER 4 • THE NETWORK LAYER
A
B
D
G
C
F E
Key:
pkt will be forwarded
pkt not forwarded beyond receiving router
Figure 4.44 ! Reverse path forwarding
v Some redundant packets
Network Layer 4-25
A
B
G
D
E
c
F
A
B
G
D
E
c
F
(a) broadcast initiated at A (b) broadcast initiated at D
Spanning tree
v first construct a spanning tree
v nodes then forward/make copies only along
spanning tree
Network Layer 4-26
A
B
G
D
E
c
F
1
2
3
4
5
(a) stepwise construction of
spanning tree (center: E)
A
B
G
D
E
c
F
(b) constructed spanning
tree
Spanning tree: creation
v center node
v each node sends unicast join message to
center node
§ message forwarded until it arrives at a node
already belonging to spanning tree
Network Layer 4-27
4.1 introduction
4.2 virtual circuit and
datagram networks
4.3 what’s inside a router
4.4 IP: Internet Protocol
§ datagram format, IPv4
addressing, ICMP, IPv6
4.5 routing algorithms
§ link state, distance
vector, hierarchical
routing
4.6 routing in the Internet
§ RIP, OSPF, BGP
4.7 broadcast and
multicast routing
Network Layer: done!
v understand principles behind network layer services:
§ network layer service models, forwarding versus
routing how a router works, routing (path selection),
broadcast, multicast
v instantiation, implementation in the Internet