Transcript Network Layer

Network Layer - BGP
CSC/ECE 573, Sections 001, 002
Fall, 2010
Acknowledgement: Material from various sources used, notably Timothy Griffin (AT&T), Battista et al (Roma Tre U)
Autonomous Systems



An autonomous system (AS) is a region of the Internet that is
administered by a single entity and that has a unified routing policy
Each autonomous system is assigned an Autonomous System
Number (ASN).
 NCSU’s campus network (AS11442)
 BellSouth Business Systems (AS5002)
…
AS numbers between 1 and 65,535 (two bytes)
–

2
Numbers greater than 64,511 are “private”
AS numbers may be requested:
–
Global asn – from your regional internet registry
–
Private asn – from your upstream ISP
(rir): ripe, arin, apnic
Interdomain and Intradomain
Routing
AS 2
AS 5
AS 1
AS 6
AS 7
AS 3
AS 4

Routing protocols for intradomain routing are called interior gateway protocols
(IGP)
– Objective: shortest path
 Routing protocols for interdomain routing are called exterior gateway protocols
(EGP)
– Objective: satisfy policy of the AS
3
Interdomain Routing


Interdomain routing is based on connectivity between autonomous systems
Interdomain routing can ignore many details of router interconnection
AS 1
AS 2
AS 3
4
Multiple Routing Protocols


Multiple routing protocols can
run on the same router
Each routing protocol updates
the routing table
RIP
Process
BGP
Process
OSPF
Process
routing
protocol
routing
protocol
routing table updates
routing
table
routing table
lookup
incoming IP
datagrams
5
IP
Forwarding
outgoing IP
datagrams
Autonomous Systems Terminology





6
local traffic
= traffic with source or
destination in AS
transit traffic
= traffic that passes through
the AS
Stub AS
= has connection to only one
AS, only carry local traffic
Multihomed AS = has connection to >1 AS,
but does not carry transit traffic
Transit AS
= has connection to >1 AS
and carries transit traffic
Stub and Transit Networks
AS 1



7
AS 1, AS 2, and AS 5 are
stub networks
AS 2 is a multi-homed stub
network
AS 3 and AS 4 are transit
networks
AS 2
AS 3
AS 4
AS 5
Selective Transit
Example:
 Transit AS 3 carries traffic
between AS 1 and AS 4 and
between AS 2 and AS 4
 But AS 3 does not carry traffic
between AS 1 and AS 2
AS 2
AS 1
AS 3

The example shows a routing
policy.
AS 4
8
Customer/Provider
AS 2
Customer/
Provider
Customer/
Provider
AS 4
Customer/
Provider
AS 6



9
AS 5
Customer/
Provider
AS 6
Customer/
Provider
AS 6
A stub network typically obtains access to the Internet through a transit
network.
Transit network that is a provider may be a customer for another
network
Customer pays provider for service
Customer/Provider and Peers
AS 1
AS 2
AS 3
Peers
Peers
Customer/
Provider
Customer/
Provider
AS 4
AS 5
Customer/Provider
AS 6
Customer/
Provider
AS 6
AS 6




10
Customer/
Provider
Transit networks can have a peer relationship
Peers provide transit between their respective customers
Peers do not provide transit between peers
Peers normally do not pay each other for service
Shortcuts through peering
AS 1
AS 2
AS 3
Peers
Peers
Customer/
Provider
Customer/
Provider
AS 4
AS 5
AS 6
Peers
Customer/Provider
Customer/
Provider
AS 6
AS 6



11
Note that peering reduces upstream traffic
Delays can be reduced through peering
But: Peering may not generate revenue
Customer/
Provider
Border Gateway Protocol (BGP)

Border Gateway Protocol is the interdomain
routing protocol for the Internet for routing
between autonomous systems

Currently in version 4 (1995)
–
–

12
Network administrators can specify routing policies
BGP is a distance vector protocol (However, routing
messages in BGP contain complete routes)
Uses TCP to transmit routing messages
Border Gateway Protocol (BGP)

An autonomous system uses BGP to advertise
its network address(es) to other AS’s

BGP helps an autonomous system with the
following:
1.
2.
3.
13
Collect information about reachable networks from
neighboring AS’s
Disseminate the information about reachable networks to
routers inside the AS and to neighboring AS’s
Picks routes if there are multiple routes available
Who uses BGP

BGP is used by:
–
–
–
–
–
Customers connected to an Internet Service Provider
(ISP)
Customers connected to several ISPs
Transit providers
ISPs that exchange traffic in an exchange point
(NAP)
Customers with very large networks
Two kinds of BGP



When several organizations join to form the Internet
they have to set up links between them
e-BGP: perform interdomain communication
i-BGP: allow BGP speakers of same AS to communicate
to each other (full mesh) (not IGP, uses IGP)
BGP interactions


Router establishes a TCP
connection (TCP port 175)
Routers exchange BGP routes
–



16
AS 1
Offer connectivity – promise to
deliver to destination
Periodically send updates
BGP is executed between two
routers
– BGP session
– BGP peers or BGP
speakers
Note: Not all autonomous
systems need to run BGP. On
many stub networks, the route
to the provider can be
statically configured
BGP Session
AS 2
BGP interactions

AS 1
The networks that are
advertised are network IP
addresses with a prefix, E.g.,
128.100.0.0/16
Prefixes reachable from AS 1
AS 2
Prefixes reachable
from AS 3
17
AS 3
BGP interactions

BGP peers advertise
reachability of IP networks
BGP Peer


18
A advertises a path to a
network (e.g., 10.0.0.0/8) to B
only if it is willing to forward
traffic going to that network
Path-Vector:
– A advertises the complete
path to the advertised
network
– Path is sent as a list of
AS’s
 this avoids loops
B
Advertise
path to 10.0.0.0/24
A
10.0.0.0/24
BGP Peer
iBGP sessions



All iBGP peers in the same
autonomous system are fully
meshed
Peer announces routes
received via eBGP to iBGP
peers
Update from
eBGP session
But: iBGP peers do not
announce routes received via
iBGP to other iBGP peers
AS A
19
Hot Potato Routing

Router R3 in autonomous
system A receives two
advertisements to network X
– Which route should it pick?
Route
to X
Route to X


20
Hot Potato Rule: Select the
iBGP peer that has the
shortest IGP route
Analogy: Get the packet out of
one’s own AS as quickly as
possible, i.e., on the shortest
path
R2
R1
Route
to X
Route
to X
R3
AS A
Hot Potato Routing
Finding the cheapest IGP
route:
 Compare the cost of the two
paths
– R3 R1
– R3 R2
according to the IGP protocol
Route
to X
Route to X
R1
21

Here: R1 has the shortest path

Add a routing table entry for
destination X
R2
Cost=6
Cost=23
R3
AS A
Hot Potato Routing can backfire!

AS1 would serve its customer (source) better by
not picking the shortest route to AS 2
 In fact, customer may have paid for a highbandwidth service!
Source
Cost=20
AS 1
Cost=5
High bandwidth network
Low bandwidth network
AS 2
Destination
22
BGP Message Types
23

Open:

Keep Alive: Handshake at regular intervals
to maintain peering session

Notification: Closes a peering session

Update:
Advertises new routes or
withdraws previously announced routes. Each
announced route is specified as a network prefix
with attribute values
Establishes a peering session
Content of Advertisements

BGP routers advertise routes

Each route consists of a network prefix and a list of attributes that
specify information about a route

Network Layer Reachability Information (NLRI)

Mandatory attributes:
ORIGIN
AS_PATH
NEXT_HOP

Many other attributes
24
ORIGIN attribute


Originating domain sends a route with ORIGIN attribute
ORIGIN attributes also specifies if the origin is internal to the AS or not
10.0.1.0/8,
ORIGIN {1}
AS 2
AS 4
10.0.1.0/8,
ORIGIN {1}
AS 1
10.0.1.0/8,
ORIGIN {1}
25
10.0.1.0/8,
ORIGIN {1}
AS 5
AS 3
10.0.1.0/8,
ORIGIN {1}
AS-PATH attributes




Each AS that propagates a route prepends its own AS number
– AS-PATH collects a path to reach the network prefix
Path information prevents routing loops from occurring
Path information also provides information on the length of a path (By
default, a shorter route is preferred)
Note: BGP aggregates routes according to CIDR rules
10.0.1.0/8,
AS-PATH {1}
AS 2
AS 4
10.0.1.0/8,
AS-PATH {4,2,1}
10.0.1.0/8,
AS-PATH {2,1}
AS 1
10.0.1.0/8,
AS-PATH {1}
26
AS 5
AS 3
10.0.1.0/8,
AS-PATH {3,1}
NEXT-HOP attributes


Each router that sends a route advertisement it includes its own IP
address in a NEXT-HOP attribute
The attribute provides information for the routing table of the receiving
router.
128.143.71.21
128.100.11.1
AS 1
AS 5
AS 3
10.0.1.0/8,
NEXT-HOP {128.100.11.1}
27
10.0.1.0/8,
NEXT-HOP {128.143.71.21}
Connecting NEXT-HOP with IGP
information
192.0.1.2
128.100.11.1/24
AS 1
eBGP
IGP router
R1
AS 3
iBGP
10.1.1.0/8,
NEXT-HOP {128.100.11.1}
10.1.1.0/8,
NEXT-HOP {128.100.11.1}
At R1:
Routing table
Dest.
Next hop
128.100.11.0/24
192.0.1.2
BGP info
28
Dest.
Next hop
10.1.1.0/8
128.100.11.1
Routing table
Dest.
Next hop
128.100.11.0/24
192.0.1.2
10.1.1.0/8
192.0.1.2
Route Selection

Router may get more than one route to an address
 Rules for selecting a route (in order of priorities):
–
–
–

Internal data structures maintained
–
–

Local Routing Information Base
Adjacent Routing Information Base – In and Out
Multiple conditions for a route to go into Loc-RIB
–
–
–
–
–
29
Preferences can be advertised as an attribute
Shorter routes are preferred
Close next-hop is preferred
Next-hop must be reachable
Only one route to each destination goes into Adj-RIB-In
If preferable over existing, goes into Loc-RIB
External route trumps all i-BGP learned routes
Contributes to main FIB
Importing and Exporting Routes







An AS may not advertise all routes, or
accept all routes that are advertised
Route policies determines which routes are
filtered
BGP does not carry policies - carries
information that allows local rules to make
policy-based inferences
AS A desires some of exported routes to be
advertised everywhere, some only in N
America
ISP announces convention (outside BGP)
that a BGP community identifier will be used
for all advertisements meant to be global,
and a different one for N America only
A attaches appropriate community attribute
tags to exported routes
No enforcement or check is possible
Control
Inbound
traffic
Change
export rules
AS A
Control
Outbound
traffic
Change
import rules
30
Importing and Exporting Routes



Import and export rules allow
control of traffic carried by AS
If an AS wants to have less
inbound traffic it should adapt its
export rules
If an AS wants to control its
inbound traffic, it adapts its import
rules
Control
Inbound
traffic
Change
export rules
AS A
Control
Outbound
traffic
Change
import rules
31
Routing Policies

Since AS 5 is a stub
network it should not
advertise routes to
networks other than
networks in AS 5
AS 3
s
er
When AS 3 learns
about the path {AS1,
AS4}, it should not
advertise the route
{AS3, AS1, AS4} to
AS 2.
s
er
Pe
Pe
AS 4

AS 6
Customer/
Provider
AS 1
AS 2
Peers
Customer/Provider
Customer/Provider
AS 5
32
Traffic Often Follows ASPATH

In many cases, packets
are routed according to
the AS-PATH
128.100.0.0/16,
AS-PATH {3,2,1}
AS 1
AS 2
AS 3
AS 5
128.100.0.0/16

However, in some
cases this is not true
(Here: AS 2 filters
routes with a long
prefix)
128.100.0.0/16,
AS-PATH {1}
AS 1
128.100.0.0/16,
AS-PATH {2, 1}
AS 2
AS 3
128.100.0.0/16
Does not
advertise /24
networks
128.100.22.0/24,
AS-PATH {4}
AS 4
128.100.22.0/24
33
128.100.0.0/16,
AS-PATH {3,2,1}
AS 5
Short AS-PATH does not mean that route is short

From AS 6’s perspective
– Path {AS2, AS1} is short
– Path {AS5, AS4, AS3,
AS1} is long
AS 1
AS 3

But the number of traversed
routers is larger when using
the shorter AS-PATH
AS 2
AS 4
AS 5
AS 6
34
BGP Table Growth
35
BGP Table Growth - 2
More Details

Many other mechanisms
–
Minimizing full mesh
– Introduce route reflectors
– Confederations

Issues with degrees of freedom
–
37
Multi-homed AS with multiple connections for stub sharing may routed
packets externally
Conclusion

BGP Issues
–
–
–
–
–
–
–
BGP is a simple protocol but it is very difficult to configure
BGP has severe stability issue due to policies  BGP is known to not
converge
As of July 2010, 35,000+ AS numbers (of available 64,510) are
consumed
Better understood in detail, but global implications not always obvious
Many quirks remains in practice
http://www.computerworld.com/s/article/9182558/Research_experiment
_disrupts_Internet_for_some
http://www.cisco.com/en/US/products/products_security_advisory0918
6a0080b4411f.shtml
Active area for innovation