Transcript No Slide Title

Border Gateway Protocol
This lecture is largely based on a BGP tutorial by T. Griffin from AT&T Research.
© J. Liebeherr, All rights reserved
1
Internet Infrastructure
Regional
Network
(Tier 2)
IXP
Backbone Network
(Tier 1)
local ISP
(Tier 3)
Regional
Network
(Tier 2)
Backbone Network
(Tier 1)
Regional
Network
(Tier 2)
local ISP
(Tier 3)
local ISP
(Tier 3)
IXP
corporate
network
IXP
Regional
Network
(Tier 2)
campus
network
2
Internet Infrastructure
• Location where a network (ISP, corporate network, or regional
network) gets access to the Internet is called a Point-ofPresence (POP).
• Locations where Tier-1 or Tier-2 networks exchange traffic
are called peering points.
– Public peering: Traffic is swapped in a specific location,
called Internet exchange points (IXPs)
– Private peering: Two networks establish a direct link to
each other.
3
IXP – Internet exchange point
• Outside:
• Inside:
4
Backbone Network of a Tier-1 Provider (USA)
5
Global Map of Tier-1 Provider
6
Review: 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).
• UofT’s campus network (AS239)
• Rogers Cable Inc. (AS812)
• Sprint (AS1239, AS1240, AS 6211, …)
• Interdomain routing is concerned with determining paths between
autonomous systems (interdomain routing)
• Routing protocols for interdomain routing are called exterior gateway
protocols (EGP)
7
Review: 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
8
Number of Autonomous Systems
9
EGP and IGP
AS 2
AS 2
EGP (e.g., BGP)
IGP (e.g., OSPF)
IGP (e.g., RIP)
• Interior Gateway Protocol
– Routing is done based on metrics
– Routing domain is one autonomous system
• Exterior Gateway Protocol
– Routing is done based on policies
– Routing domain is the entire Internet
10
EGP
• Interdomain routing is based on connectivity between autonomous systems
• Interdomain routing can ignore many details of router interconnection
AS 1
AS 2
AS 3
11
AS Graphs
AT&T North America
From: T. Griffin, BGP Tutorial
12
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
IP
Forwarding
outgoing IP
datagrams
13
Autonomous Systems Terminology
• local traffic
• transit traffic
• Stub AS
= traffic with source or destination in AS
= traffic that passes through the AS
= has connection to only one AS, only
carry local traffic
• Multihomed Stub AS = has connection to >1 AS, but does
not carry transit traffic
• Transit AS
= has connection to >1 AS and carries
transit traffic
14
Stub and Transit Networks
AS 2
AS 1
AS 4
AS 3
Settings:
• AS 1 is a multi-homed stub network
• AS 3 and AS 4 are transit networks
• AS 2 and AS 5 are is a stub networks
AS 5
15
Selective Transit
Example:
• 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
16
Customer/Provider and Peers
AS 2
Customer/
Provider
Customer/
Provider
AS 4
Customer/
Provider
AS 6
AS 5
Customer/
Provider
AS 7
Customer/
Provider
AS 8
• 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
17
Customer/Provider and Peers
AS 1
AS 2
AS 3
Peers
Peers
Customer/
Provider
Customer/
Provider
AS 4
AS 5
Customer/Provider
Customer/
Provider
AS 6
Customer/
Provider
AS 7
AS 8
•
•
•
•
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
18
Shortcuts through peering
AS 1
AS 2
AS 3
Peers
Peers
Customer/
Provider
Customer/
Provider
AS 4
AS 5
Customer/
Provider
AS 6
Peers
Customer/Provider
Customer/
Provider
AS 7
AS 8
• Note that peering reduces upstream traffic
• Delays can be reduced through peering
• But: Peering may not generate revenue
19
Border Gate Protocol (BGP)
• Border Gateway Protocol is the interdomain routing
protocol for the Internet for routing between
autonomous systems
• Currently in version 4 (1995)
– Network administrators can specify routing policies
– BGP is a path vector protocol (Like distance vector, but
routing messages in BGP contain complete routes)
• Uses TCP to transmit routing messages
20
Border Gate Protocol (BGP)
•
An autonomous system uses BGP to advertise its network
address(es) to other AS’s
•
BGP helps an AS to:
1. Learn about reachable networks from neighboring AS’s
2. Distribute the information about reachable networks to
routers inside the AS
3. Select a route if there are multiple routes to reach the
same network
21
BGP Message Types
• Open:
Establishes a peering session
• Notification:
Closes a peering session
• Keep Alive:
Handshake at regular intervals to maintain
peering session
• Update:
Announces new routes or withdraws
previously announced routes.
Each announced route is specified as a network prefix with
attribute values
22
BGP interactions
• The networks that are advertised
are network IP addresses with a
prefix, E.g., 128.100.0.0/16
AS 1
Prefixes reachable from AS 1
AS 2
Prefixes reachable
from AS 3
AS 3
23
BGP interactions
•
•
BGP is executed between two routers
– BGP session
– BGP peers or BGP speakers
Procedure:
1. Establishes TCP connection (port 175)
to BGP peer
2. Exchange all BGP routes
3. As long as connection is alive:
Periodically send incremental updates
AS 1
BGP Session
AS 2
•
Note: Not all autonomous systems need to
run BGP. On many stub networks, the route
to the provider can be statically configured
24
BGP interactions
• BGP peers advertise reachability
of IP networks
BGP Peer
• 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 AS A, …., AS X
 this avoids loops
B
Advertise
path to 10.0.0.0/24
A
BGP Peer
10.0.0.0/24
25
BGP Sessions
• External BGP session (eBGP):
Peers are in different AS’es
AS B
• Internal BGP session (iBGP)
Peers are in the same AS
eBGP session
• Note that iBGP sessions use
routes constructed by an
intradomain routing protocol to
exchange messages !
AS A
iBGP session
26
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
27
Route Reflectors
• Full mesh of iBGP routers is
difficult to maintain
• Router Reflectors (RR) present an
alternative
• All iBGP routers peer with the RR
– RR acts as a server
– Other iBGP routers become
clients
Update from
eBGP session
RR
AS A
28
Content of Advertisements
• A BGP routers route advertisement is sent in a BGP UPDATE message
• A route is announced as a Network Prefix and Attributes
• Attributes specify details about a route:
– Mandatory attributes:
ORIGIN
AS_PATH
NEXT_HOP
– many other attributes
29
ORIGIN attribute
• Originating domain sends a route with ORIGIN attribute
10.0.1.0/24,
ORIGIN {1}
AS
AS22
AS
AS44
10.0.1.0/24,
ORIGIN {1}
AS
AS11
10.0.1.0/24,
ORIGIN {1}
10.0.1.0/24,
ORIGIN {1}
AS
AS55
AS
AS33
10.0.1.0/24,
ORIGIN {1}
30
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 occuring
• 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/24,
AS-PATH {1}
AS 2
AS 4
10.0.1.0/24,
AS-PATH {4,2,1}
10.0.1.0/24,
AS-PATH {2,1}
AS 1
10.0.1.0/24,
AS-PATH {1}
AS 5
AS 3
10.0.1.0/24,
AS-PATH {3,1}
31
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/24,
NEXT-HOP {128.100.11.1}
10.0.1.0/24,
NEXT-HOP {128.143.71.21}
32
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.0.1.0/24,
NEXT-HOP {128.100.11.1}
10.0.1.0/24,
NEXT-HOP {128.100.11.1}
At R1:
Routing table
Dest.
Next hop
128.100.11.0/24
192.0.1.2
BGP info
Dest.
Next hop
10.0.1.0/24
128.100.11.1
Routing table
Dest.
Next hop
128.100.11.0/24
192.0.1.2
10.0.1.0/24
192.0.1.2
33
Route Selection
• An AS may get more than one
route to an address
• Needs to select a route
AS 1
Advertise path to
10.0.1.0/24
AS 1
Advertise path to
10.0.1.0/24
AS 3
AS 2
Advertise path to
10.0.1.0/24
Advertise path to
10.0.1.0/24
AS 4
Route Selection Criteria (in order of preference)
• Highest Local Preference
• Shortest AS-Path
• Lowest MED (multi-exit discriminator) ( called “metric” in BGP)
• Prefer iBGP over eBGP routes
• Lowest IGP cost to leave AS (“hot potato”)
• Lowest router ID ( used as tie breaker)
34
Local Preference
Advertise path to
AS 1
path10.0.0.0/24
to
AS Advertise
1
AS 2
10.0.1.0/24
Local pref
= 100
Local pref = 10
AS 1
Advertise path to
Advertise path10.0.0.0/24
to
10.0.1.0/24
AS 3
AS 3
AS 2
Advertise path to
Advertise path10.0.0.0/24
to
10.0.1.0/24
AS 1
Local pref = 80
Local pref = 50
Advertise path to
Advertise path10.0.0.0/24
to
AS
10.0.1.0/24
4
AS 4
• If there are multiple exit points from the AS, the local preference attribute
is used to select the exit point for a specific route
• Local Preference is used only for iBGP sessions
• Value is set locally
35
Hot Potato Routing
• Router R3 in autonomous system
A receives two advertisements to
AS A
– Which route should it pick?
Route
to X
Route to X
• 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
36
Hot Potato Routing
Finding the cheapest IGP route:
• Compare the cost of the two
paths
– R3 R1
– R3 R2
according to the IGP protocol
• Here: R1 has the shortest path
Route
to X
Route to X
R1
R2
Cost=6
Cost=23
• Add a routing table entry for
destination X
R3
AS A
37
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 high-bandwidth service!
Source
Cost=20
AS 1
Cost=5
High bandwidth network
Low bandwidth network
AS 2
Destination
38
Processing in BGP
BGP
updates
arrive
Filter routes
and change
attributes
Apply Import
Rules
Based on
attributes
Best entry is
entered in
IP routing
table
Filter routes
and change
attributes
Select Best
Route
Update IP
routing table
Apply Export
Rules
BGP
updates
arrive
IP routing
table
39
Importing and Exporting Routes
• An AS may not accept all routes
that are advertised
• An AS may not advertise certain
routes
• Route policies determines which
routes are filtered
• If an AS wants to have less
inbound traffic it should adapt its
export rules
• If an AS wants to control its
outbound traffic, it adapts its
import rules
Control
Inbound
traffic
Change
export rules
AS A
Control
Outbound
traffic
Change
import rules
40
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
Pe
s
er
Pe
AS 4
• When AS 3 learns
about the path {AS1,
AS4}, it should not
advertise the route
{AS3, AS1, AS4} to
AS 2.
AS 6
Customer/
Provider
AS 1
AS 2
Peers
Customer/Provider
Customer/Provider
AS 5
41
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
128.100.0.0/16,
AS-PATH {3,2,1}
AS 3
AS 5
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
42
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
43
BGP Table Growth
Source: Geoff Huston. http://www.telstra.net/ops/bgptable.html on August 8, 2001
44
BGP Table Growth
Source: bgp.potaroo.net, 2010
45
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 2005, 39,000 AS numbers (of available 64,510) are consumed
46