PowerPoint Presentation
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-*
introduction
virtual circuit and datagram networks
what’s inside a router
IP: Internet Protocol
datagram format
IPv4 addressing (NAT)
ICMP, IPv6
routing algorithms
link state, distance vector
hierarchical routing
routing in the Internet
RIP, OSPF
BGP
broadcast routing
Outline
Network Layer
Network Layer
4-*
Internet inter-AS routing: BGP
BGP (Border Gateway Protocol): the de facto inter-domain routing protocol
“glue that holds the Internet together”
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.
allows subnet to advertise its existence to rest of Internet: “I am here”
Network Layer
Network Layer
4-*
BGP basics
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
other
networks
other
networks
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
3b
3c
3a
1c
1a
1d
1b
AS1
2a
2c
2b
BGP
message
Network Layer
Network Layer
4-*
BGP basics: distributing path information
AS3
AS2
AS1
other
networks
other
networks
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
when router learns of new prefix, it creates entry for prefix in its forwarding table.
eBGP session
iBGP session
3b
3a
1c
1a
1d
1b
2a
2c
2b
Network Layer
Network Layer
4-*
Path attributes and BGP routes
advertised prefix includes BGP attributes
prefix + attributes = “route”
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.
gateway router receiving route advertisement uses import policy to accept/decline
e.g., never route through AS x
policy-based routing
Network Layer
Network Layer
4-*
BGP route selection
router may learn about more than 1 route to destination AS, selects route based on:
local preference value attribute: policy decision
shortest AS-PATH
closest NEXT-HOP router: hot potato routing
additional criteria
Network Layer
Putting it Altogether:
How Does an Entry Get Into a Router’s Forwarding Table?
Answer is complicated!
Ties together hierarchical routing with BGP and OSPF.
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
Router becomes aware of prefix
Router determines output port for prefix
Router enters prefix-port in forwarding table
How does entry get in forwarding table?
*
Router becomes aware of prefix
AS3
AS2
other
networks
other
networks
BGP message contains “routes”
“route” is a prefix and attributes: AS-PATH, NEXT-HOP,…
Example: route:
Prefix:138.16.64/22 ; AS-PATH: AS3 AS131 ; NEXT-HOP: 201.44.13.125
3b
3c
3a
1c
1a
1d
1b
AS1
2a
2c
2b
BGP
message
*
Router may receive multiple routes
AS3
AS2
other
networks
other
networks
Router may receive multiple routes for same prefix
Has to select one route
3b
3c
3a
1c
1a
1d
1b
AS1
2a
2c
2b
BGP
message
*
Router selects route based on shortest AS-PATH
Select best BGP route to prefix
Example:
AS2 AS17 to 138.16.64/22
AS3 AS131 AS201 to 138.16.64/22
What if there is a tie? We’ll come back to that!
select
*
Find best intra-route to BGP route
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.
Example:
AS-PATH: AS2 AS17 ; NEXT-HOP: 111.99.86.55
Router uses OSPF to find shortest path from 1c to 111.99.86.55
111.99.86.55
3b
3c
3a
1c
1a
1d
1b
AS1
2a
2c
2b
AS3
AS2
other
networks
other
networks
*
Router identifies port for route
Identifies port along the OSPF shortest path
Adds prefix-port entry to its forwarding table:
(138.16.64/22 , port 4)
router
port
1
2
3
4
3b
3c
3a
1c
1a
1d
1b
AS1
2a
2c
2b
AS3
AS2
other
networks
other
networks
Hot Potato Routing
Suppose there two or more best inter-routes.
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 AS131 since it is closer
3b
3c
3a
1c
1a
1d
1b
AS1
2a
2c
2b
AS3
AS2
other
networks
other
networks
Summary
Router becomes aware of prefix
via BGP route advertisements from other routers
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
Enter prefix-port entry in forwarding table
How does entry get in forwarding table?
Network Layer
4-*
BGP routing policy
A,B,C are provider networks
X,W,Y are customer (of provider networks)
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
Network Layer
4-*
BGP routing policy (2)
A advertises path AW to B
B advertises path BAW to X
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
Network Layer
4-*
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
Network Layer
4-*
introduction
virtual circuit and datagram networks
what’s inside a router
IP: Internet Protocol
datagram format
IPv4 addressing (NAT)
ICMP, IPv6
routing algorithms
link state, distance vector
hierarchical routing
routing in the Internet
RIP, OSPF
BGP
broadcast routing
Outline
Network Layer
Network Layer
4-*
Broadcast routing
deliver packets from source to all other nodes
source duplication is inefficient:
source duplication: how does source determine recipient addresses?
R1
R2
R3
R4
R1
R2
R3
R4
source
duplication
in-network
duplication
duplicate
creation/transmission
duplicate
duplicate
Network Layer
Network Layer
4-*
In-network duplication
flooding: when node receives broadcast packet, sends copy to all neighbors
problems: cycles & broadcast storm
controlled flooding: node only broadcasts pkt if it hasn’t broadcast same packet before
node keeps track of packet ids already broadcast
or reverse path forwarding (RPF): only forward packet if it arrived on shortest path between node and source
spanning tree:
no redundant packets received by any node
Network Layer
Reverse Path Forwarding
Network Layer
4-*
Some redundant packets
Network Layer
Network Layer
4-*
Spanning tree
first construct a spanning tree
nodes then forward/make copies only along spanning tree
A
B
G
D
E
c
F
A
B
G
D
E
c
F
(a) broadcast initiated at A
(b) broadcast initiated at D
Network Layer
Network Layer
4-*
1
2
3
4
5
stepwise construction of spanning tree (center: E)
(b) constructed spanning tree
Spanning tree: creation
center node – rendezvous
each node sends unicast join message to center node
message forwarded until it arrives at a node already belonging to spanning tree
A
B
G
D
E
c
F
A
B
G
D
E
c
F
Network Layer
Network Layer
4-*
Introduction
virtual circuit and datagram networks
what’s inside a router
IP: Internet Protocol
datagram format, IPv4 addressing, ICMP, IPv6
routing algorithms
link state, distance vector, hierarchical routing
routing in the Internet
RIP, OSPF, BGP
broadcast routing
Network Layer: done!
understand principles behind network layer services:
network layer service models, forwarding versus routing how a router works, routing (path selection), broadcast, multicast
instantiation, implementation in the Internet
Network Layer
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