Transcript An Introduction to Interdomain Routing and the Border

Interdomain Routing and The
Border Gateway Protocol (BGP)
Today’s Big Picture
Large ISP
Large ISP
Stub
Small ISP
GPRS
Stub
Stub
Large number of diverse networks
Access
Network
Internet AS Map: caida.org
Autonomous System(AS)
• Internet is not a single network
– Collection of networks controlled by
different administrations
• An autonomous system is a network
under a single administrative control
• IANA
– An AS owns unique IP prefixes
– Every AS has a unique AS number
• ASes need to inter-network themselves
to form a single virtual global network
– Need a common protocol for
communication
Who speaks Inter-AS routing?
AS2
BGP
AS1
R2
R3
R1
R
border router
internal router
 Two types of routers
 Border router (Edge)
Internal router (Core)
 Two border routers of different ASes will have a BGP session
Autonomous Systems (ASes)
 An
autonomous system is an autonomous routing
domain that has been assigned an Autonomous System
Number (ASN).
All parts within an AS remain connected.
… the administration of an AS appears to other ASes to
have a single coherent interior routing plan and presents a
consistent picture of what networks are reachable through it.
RFC 1930: Guidelines for creation, selection,
and registration of an Autonomous System
IP Address Allocation and
Assignment: Internet Registries
IANA
www.iana.org
ARIN
www.arin.org
RIPE
www.ripe.org
APNIC
www.apnic.org
Allocate to National and local registries and ISPs
Addresses assigned to customers by ISPs
RFC 2050 - Internet Registry IP Allocation Guidelines
RFC 1918 - Address Allocation for Private Internets
RFC 1518 - An Architecture for IP Address Allocation with CIDR
Whois servers (AS, IP)
• http://www.ripe.net/perl/whois
– AS2588
• http://ws.arin.net/cgibin/whois.pl
– AS701
• http://www.apnic.net/apnicbin/whois.pl
– AS4808
AS Numbers (ASNs)
ASNs are 16 bit values.
64512 through 65535 are “private”
•
•
•
•
•
•
•
•
Currently over 20,000 in use.
Genuity: 1
MIT: 3
JANET: 786
UC San Diego: 7377
AT&T: 7018, 6341, 5074, …
UUNET: 701, 702, 284, 12199, …
Sprint: 1239, 1240, 6211, 6242, …
…
ASNs represent units of routing policy
Partial View of www.cl.cam.ac.uk
(128.232.0.20) Neighborhood
AS 3356
Level 3
AS 6461
AboveNet
AS 20965
GEANT
AS 786
ja.net
AS 5459
LINX
Originates > 180 prefixes,
Including 128.232.0.0/16
AS 7
UK Defense
Research Agency
AS 1239
Sprint
AS 702
UUNET
AS 1213
HEAnet
(Irish academic
and research)
AS 4373
Online Computer
Library Center
How Many ASNs are there today?
18,217
12,940
origin
only (no
transit)
Thanks to Geoff Huston. http://bgp.potaroo.net on October 26, 2004
IP network assignment process
IETF
RIR
RIR
ISP
Announcement
IANA
ISP
Allocation
Allocation
Delegation
IANA
BGP
RIR Allocations - Current
IETF Reserved, 20.1, 8%
Multicast, 16, 6%
Assigned, 116.9, 46%
Allocated
IANA Pool, 89, 35%
RIR Pool, 14, 5%
BGP Routing Table - Current
IETF Reserved, 20.1, 8%
Multicast, 16, 6%
Advertised, 74.5, 29%
IANA Pool, 89, 35%
Assigned, 42.4, 17%
RIR Pool, 14, 5%
How many prefixes today?
179,903
Note: numbers
actually depends
point of view…
Thanks to Geoff Huston. http://bgp.potaroo.net on October 26, 2004
The Gang of Four
Link State
IGP
EGP
Vectoring
OSPF
RIP
EIGRP
BGP
BGP-4
• BGP = Border Gateway Protocol
• Is a Policy-Based routing protocol
• Is the de facto EGP of today’s global Internet
• Relatively simple protocol, but configuration is complex and the
entire world can see, and be impacted by, your mistakes.
•
1989 : BGP-1 [RFC 1105]
–
•
Replacement for EGP (1984, RFC 904)
1990 : BGP-2 [RFC 1163]
• 1991 : BGP-3 [RFC 1267]
•
1995 : BGP-4 [RFC 1771]
–
Support for Classless Interdomain Routing (CIDR)
17
The Border Gateway Protocol (BGP)
BGP =
+
RFC 1771
“optional” extensions
RFC 1997 (communities) RFC 2439 (damping) RFC 2796 (reflection) RFC3065 (confederation) …
+
routing policy configuration
languages (vendor-specific)
+
Current Best Practices in
management of Interdomain Routing
BGP was not DESIGNED.
It EVOLVED.
BGP Operations (Simplified)
Establish session on
TCP port 179
AS1
BGP session
Exchange all
active routes
AS2
Exchange incremental
updates
While connection
is ALIVE exchange
route UPDATE messages
19
Four Types of BGP Messages
• Open : Establish a peering session.
• Keep Alive : Handshake at regular intervals.
• Notification : Shuts down a peering session.
• Update : Announcing new routes or withdrawing
previously announced routes.
announcement
=
prefix + attributes values20
BGP Attributes
Value
----1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
...
255
Code
--------------------------------ORIGIN
AS_PATH
NEXT_HOP
MULTI_EXIT_DISC
LOCAL_PREF
ATOMIC_AGGREGATE
AGGREGATOR
COMMUNITY
ORIGINATOR_ID
CLUSTER_LIST
DPA
ADVERTISER
RCID_PATH / CLUSTER_ID
MP_REACH_NLRI
MP_UNREACH_NLRI
EXTENDED COMMUNITIES
Reference
--------[RFC1771]
[RFC1771]
[RFC1771]
[RFC1771]
[RFC1771]
[RFC1771]
[RFC1771]
[RFC1997]
[RFC2796]
[RFC2796]
[Chen]
[RFC1863]
[RFC1863]
[RFC2283]
[RFC2283]
[Rosen]
Most
important
attributes
reserved for development
From IANA: http://www.iana.org/assignments/bgp-parameters
Not all attributes
need to be present in
every announcement
Attributes are Used to Select Best
Routes
192.0.2.0/24
pick me!
192.0.2.0/24
pick me!
192.0.2.0/24
pick me!
192.0.2.0/24
pick me!
Given multiple
routes to the same
prefix, a BGP speaker
must pick at most
one best route
(Note: it could reject
them all!)
BGP Route Processing
Open ended programming.
Constrained only by vendor configuration language
Receive Apply Policy =
filter routes &
BGP
Updates tweak attributes
Apply Import
Policies
Based on
Attribute
Values
Best
Routes
Best Route
Selection
Best Route
Table
Apply Policy =
filter routes &
tweak attributes
Transmit
BGP
Updates
Apply Export
Policies
Install forwarding
Entries for best
Routes.
IP Forwarding Table
23
Route Selection Summary
Highest Local Preference
Enforce relationships
Shortest ASPATH
Lowest MED
i-BGP < e-BGP
traffic engineering
Lowest IGP cost
to BGP egress
Lowest router ID
Throw up hands and
break ties
BGP Routing Tables
show ip bgp
BGP table version is 111849680, local router ID is 203.62.248.4
Status codes: s suppressed, d damped, h history, * valid, > best, i - internal
Origin codes: i - IGP, e - EGP, ? - incomplete
Network
. . .
*>i192.35.25.0
*>i192.35.29.0
*>i192.35.35.0
*>i192.35.37.0
*>i192.35.39.0
*>i192.35.44.0
*>i192.35.48.0
*>i192.35.49.0
*>i192.35.50.0
*>i192.35.51.0/25
. . .
Next Hop
134.159.0.1
166.49.251.25
134.159.0.1
134.159.0.1
134.159.0.3
166.49.251.25
203.62.248.34
203.62.248.34
203.62.248.34
203.62.248.34
Metric LocPrf Weight Path
50
50
50
50
50
50
55
55
55
55
0
0
0
0
0
0
0
0
0
0
16779 1 701 703 i
5727 7018 14541 i
16779 1 701 1744 i
16779 1 3561 i
16779 1 701 80 i
5727 7018 1785 i
16779 209 7843 225 225
16779 209 7843 225 225
16779 3549 714 714 714
16779 3549 14744 14744
225 225 225 i
225 225 225 i
i
14744 14744 14744 14744 14744 14744 i
Thanks to Geoff Huston. http://www.telstra.net/ops on July 6, 2001
• Use “whois” queries to associate an ASN with “owner” (for
example, http://www.arin.net/whois/arinwhois.html)
• 7018 = AT&T Worldnet, 701 =Uunet, 3561 = Cable &
Wireless, …
AS Graphs Can Be Fun
Policy : Transit vs. Nontransit
A transit AS allows traffic with neither
source nor destination within AS to flow
across the network
AS 701
AT&T CBB
AS 701
UUnet
A nontransit AS allows
only traffic originating
from AS or traffic with
destination within AS
AS144
Bell Labs
IP traffic
27
Customers and Providers
provider
provider
customer
IP traffic
customer
Customer pays provider for access to the Internet
The “Peering” Relationship
peer
provider
peer
customer
Peers provide transit between
their respective customers
Peers do not provide transit
between peers
traffic
allowed
traffic NOT
allowed
Peers (often) do not exchange $$$
Peering Provides Shortcuts
Peering also allows connectivity between
the customers of “Tier 1” providers.
peer
provider
peer
customer
Peering Wars
Peer
• Reduces upstream
transit costs
• Can increase end-toend performance
• May be the only way to
connect your
customers to some
part of the Internet
(“Tier 1”)
Don’t Peer
• You would rather have
customers
• Peers are usually your
competition
• Peering relationships
may require periodic
renegotiation
Peering struggles are by far the most
contentious issues in the ISP world!
Peering agreements are often confidential.
Policy-Based vs. Distance-Based Routing?
Minimizing
“hop count” can
violate commercial
relationships that
constrain interdomain routing.
Host 1
Cust1
YES
ISP1
NO
ISP3
ISP2
Cust3
Host 2
Cust2
32
What is Routing Policy
• Policy refers to arbitrary preference
among a menu of available routes
(based upon routes’ attributes)
– Public description of the relationship
between external BGP peers
– Can also describe internal BGP peer
relationship
• Eg: Who are my BGP peers
• What routes are
– Originated by a peer
– Imported from each peer
Routing Policy Example
• AS1 originates
prefix “d”
• AS1 exports “d” to
AS2, AS2 imports
• AS2 exports “d” to
AS3, AS3 imports
• AS3 exports “d” to
AS5, AS5 imports
Routing Policy Example (cont)
• AS5 also imports
“d” from AS4
• Which route does it
prefer?
– Does it matter?
– Consider case
where
• AS3 = Commercial
Internet
• AS4 = Internet2
Import and Export Policies
• Inbound filtering controls outbound traffic
– filters route updates received from other peers
– filtering based on IP prefixes, AS_PATH,
community
• Outbound Filtering controls inbound traffic
– forwarding a route means others may choose to
reach the prefix through you
– not forwarding a route means others must use
another router to reach the prefix
• Attribute Manipulation
– Import: LOCAL_PREF (manipulate trust)
– Export: AS_PATH and MEDs
ASPATH Attribute
AS 1129
135.207.0.0/16
AS Path = 1755 1239 7018 6341
135.207.0.0/16
AS Path = 1239 7018 6341
AS 1239
Sprint
AS 1755
135.207.0.0/16
AS Path = 1129 1755 1239 7018 6341
Ebone
AS 12654
AS 6341
AT&T Research
RIPE NCC
RIS project
135.207.0.0/16
AS Path = 7018 6341
AS7018
135.207.0.0/16
AS Path = 6341
Global Access
135.207.0.0/16
AS Path = 3549 7018 6341
AT&T
135.207.0.0/16
AS Path = 7018 6341
AS 3549
Global Crossing
135.207.0.0/16
Prefix Originated
37
Shorter Doesn’t Always Mean Shorter
In fairness:
could you do
this “right” and
still scale?
Mr. BGP says that
path 4 1 is better
than path 3 2 1
Duh!
AS 4
AS 3
Exporting internal
state would
dramatically
increase global
instability and
amount of routing
state
AS 2
AS 1
Routing Example 1
Routing Example 2
Tweak Tweak Tweak (TE)
• For inbound traffic
– Filter outbound
routes
– Tweak attributes
on outbound routes
in the hope of
influencing your
neighbor’s best
route selection
inbound
traffic
• For outbound traffic
– Filter inbound
routes
– Tweak attributes
on inbound routes
to influence best
route selection
outbound
traffic
outbound
routes
inbound
routes
In general, an AS has more
control over outbound traffic
LOCAL PREFERENCE
Local
preference
used ONLY
in iBGP
AS 4
local pref = 80
local pref = 90
AS 3
local pref = 100
AS 2
Higher Local
preference values
are more preferred
AS 1
13.13.0.0/16
42
Implementing Backup Links with Local
Preference (Outbound Traffic)
AS 1
primary link
Set Local Pref = 100
for all routes from AS 1
backup link
AS 65000
Set Local Pref = 50
for all routes from AS 1
Forces outbound traffic to take primary link, unless link is down.
We’ll talk about inbound traffic soon …
43
Multihomed Backups
(Outbound Traffic)
AS 1
AS 3
provider
provider
primary link
backup link
Set Local Pref = 100
for all routes from AS 1
Set Local Pref = 50
for all routes from AS 3
AS 2
Forces outbound traffic to take primary link, unless link is down.
44
ASpath prepending
AS 1
AS 3
provider
provider
192.0.2.0/24
ASPATH = 2
192.0.2.0/24
ASPATH = 2 2 2 2 2 2 2 2 2 2 2 2 2 2
primary
backup
customer
AS 2
192.0.2.0/24
Padding in this way is often
used as a form of load
balancing
45
COMMUNITY Attribute to the Rescue!
AS 1
AS 3
provider
provider
AS 3: normal
customer local
pref is 100,
peer local pref is 90
192.0.2.0/24
ASPATH = 2
COMMUNITY = 3:70
192.0.2.0/24
ASPATH = 2
primary
backup
customer
AS 2
192.0.2.0/24
Customer import policy at AS 3:
If 3:90 in COMMUNITY then
set local preference to 90
If 3:80 in COMMUNITY then
set local preference to 80
If 3:70 in COMMUNITY then
set local preference to 70
46
BGP Summary
• BGP4 is the protocol used on the
Internet to exchange routing
information between providers, and
to propagate external routing
information through networks.
• Each autonomous network is called
an Autonomous System.
• ASs which inject routing information
on their own behalf have ASNs.
BGP Peering
• BGP-speaking routers peer with
each other over TCP sessions, and
exchange routes through the peering
sessions.
• Providers typically try to peer at
multiple places. Either by peering
with the same AS multiple times, or
because some ASs are multi-homed,
a typical network will have many
candidate paths to a given prefix.
The BGP Route
• The BGP route is, conceptually, a
“promise” to carry data to a section
of IP space. The route is a “bag” of
attributes.
• The section of IP space is called the
“prefix” attribute of the route.
• As a BGP route travels from AS to
AS, the ASN of each AS is stamped
on it when it leaves that AS. Called
the AS_PATH attribute, or “as-path”
in Cisco-speak.
BGP Route Attributes
• In addition to the prefix, the as-path,
and the next-hop, the BGP route has
other attributes, affectionately
known as
“knobs and twiddles” –
–
–
–
weight, rarely used - “sledgehammer”
local-pref, sometimes used - “hammer”
origin code, rarely used
MED (“metric”) - a gentle nudge