Transcript BGP

A Whirlwind Tour of
Interdomain Routing
Aaron Wagner
[email protected]
EE 122 Class
February 9, 2001
Overview
• What I hope you will learn in the next half-hour:
– What interdomain routing is and how it came to be
– What BGP is and how it works
– BGP’s strengths and weaknesses
2
The Need for Routing Domains
• Prior to 1982, the Internet used a single routing protocol
(GGP).
• This architecture had disadvantages:
– Wasteful to store complete routing table in every router
– Routing traffic became excessive as the Internet grew
• In 1982, the Internet split into “Autonomous Systems”
(AS’s) or “Routing Domains”: collections of routers and
hosts under common administration.
• An AS uses an intradomain (RIP, OSPF) protocol of its
choice for routing within the AS.
• A common interdomain (EGP, then BGP) protocol is used
for routing between AS’s.
3
Challenges of Interdomain Routing
• “Link costs” cannot be compared between different AS’s.
– How to avoid routing loops?
• The scale of the problem is larger than the intradomain
one:
– Larger routing tables
– Routers separated by greater distances: higher delays and lower
reliability for messages passed
• Different AS’s may have conflicting routing objectives…
… due to prior business agreements.
… due to different approaches to the speed vs. reliability tradeoff.
4
Border Gateway Protocol (BGP): Overview
• BGP is the currently-deployed interdomain routing
protocol.
– First introduced in 1989. Many modifications since.
• BGP is a path-vector protocol: route
announcements include the complete list of AS’s
to reach the destination (AS-path).
– Makes loop suppression very simple
– Avoids comparisons of metrics between different AS’s
5
BGP Operation: A High-Level Example
UCB
AS 25
128.32/16 25
CALREN
AS 11537
128.32/16 25
128.32/16
128.32/16 X 556 11537 25
128.32/16 11537 25
AS X
128.32/16 556 11537 25
Abilene
AS 556
128.32/16 556 11537 25
128.32/16 11537 25
6
BGP Operation: Messaging
• Each AS has one or more BGP speakers.
– Speakers learn of internal routes through the intradomain routing
protocol.
– Speakers inform BGP speakers in neighboring domains of local
destinations.
– Other routers in the domain can send traffic destined outside the
domain to a speaker: they do not need a complete routing table.
• BGP speakers exchange entire routing table only once.
Thereafter, updates (announcements and withdrawals)
• BGP speakers communicate using TCP (port 179)
(+) Keeps retransmission and reordering of updates out of protocol
(–) Routing updates “back off” during congestion
• Speakers send “keep-alive” messages at regular intervals.
7
BGP Operation: A Low-Level Example
BGP Speakers
R1
d R2 B
e R2 B C
Other Routers
Data Link
BGP Session
de R2 B C
AS A
R2
d R4
R4
d R4
e R3 C
d R2 B
R3
de R3
R2 C
B
e
d
AS B
AS C
8
BGP Operation: Choosing Routes
• Each AS defines a mapping from routes to nonnegative
numbers: speakers use it to choose routes.
• The number to which a route is assigned is called its
“local-preference.”
• When a BGP speaker receives two routes to a destination:
– It chooses the one with higher local-preference, if possible.
– Otherwise, it chooses the one with shorter AS-path, if possible.
…
– Ties are broken using the IP address of the next-hop router.
• A speaker may advertise at most one route per destination
to other speakers, so the last step always breaks a tie.
9
BGP Operation: Choosing Routes
• Sample mapping from routes to local-preferences:
If 556 is in AS-Path, return 200.
Else if destination is 128.32/16 and
AS-Path does not contain 556, return
150.
Otherwise, return 100.
• BGP speakers can be programmed to exclude
certain routes from consideration.
– Examples:
• CALREN excludes routes from UCB with destinations other
than 128.32/16, 169.229/16, and 136.152/16.
10
(Non)convergence of BGP
• We say a routing protocol converges if routers
settle on a set of routes and no new routing
updates are sent.
• One can prove that distance-vector and link-state
routing protocols will always converge.
• It was recently discovered (1996) that BGP does
not necessarily converge.
11
Key Points
• The Internet is too large for a flat routing architecture.
• So, the Internet is split into Autonomous Systems (AS’s)
– Routing problem separated into inter- and intradomain routing.
• Interdomain routing presents unique challenges over
intradomain.
• The current interdomain routing protocol is the Border
Gateway Protocol (BGP), a path-vector protocol.
• Unlike other routing protocols, BGP does not necessarily
converge.
Buzzwords: Interdomain Routing, BGP, BGP Speakers, AS, AS Path,
Local Preference, Path Vector Routing Protocol.
12
Extra Slides
13
Interdomain Routing by the numbers
Statistics on the Internet at Large Statistics on one BGP Speaker
Number of
18633
registered AS’s
Number of IP
About 89
addresses “assigned” million
Average AS size
(IP addresses)
About
4780
From rs.arin.net and www.netsizer.com, 9/23/00
Number of routes
stored
Average ASpath length
About
91000
4.3
Maximum ASpath length
10
From www.telstra.net/ops/bgptable.html, 9/23/00
14
When does a network become an AS?
•
To receive an AS number, a network must
– Be multi-homed (i.e. have more than one connection
to the rest of the network)
– Be capable of running BGP
– Pay 500 USD
There is no minimum network size to become an AS.
•
Example: a small company with a single provider
is considered part of the provider’s AS.
15
Nonconvergence of BGP: An Example
1
0
2
3
• Consider an internet with 4 AS’s,
• Focus on a destination d in AS 0.
• AS 1 will accept routes 10 and
120 to d, but prefers 120.
• AS 2 will accept routes 20 and
230 to d, but prefers 230.
• AS 3 will accept routes 30 and
310 to d, but prefers 310.
16
Nonconvergence of BGP: An Example
1
1
1
d230
d20
0
2
0
3
2
1
d30
0
3
1
d20
0
0
3
3
1
d10
2
2
2
d310
…
0
3
2
3
17
Classless InterDomain Routing (1991)
•
A temporary solution to two immediate dangers:
1. Class-B address space exhaustion
–
–
–
•
•
Class-A allows 16,777,216 hosts: “too large”
Class-C allows 255 hosts: “too small”
Class-B allows 65,536 hosts: “just right”
Only 16384 class-B network numbers available
Last Class-B address would have been assigned in March
1994.
2. Routing table explosion
•
Idea: assign multiple consecutive Class-C
addresses in place of Class-B and aggregate.
18
CIDR: An Example
197.8.2/24
197.8.0/24
AS W
197.8.0/24 W
197.8.0/22 Y W X
197.8.1/24 X
197.8.3/24
197.8.1/24
AS X
AS Z
AS Y
Assign IP addresses to maximize aggregation.
19
CIDR, cont.
• Imperfect technique: old addresses, multihoming, changing
providers, etc.
20
From www.telstra.net/ops/bgptable.html, 9/23/00
References
http://rs.arin.net/regserv/asnguide.htm
http://www.netsizer.com
http://telstra.net/ops/bgptable.html
Labovitz, C., Malan, G., Jahanian, F. “Origins of Internet routing instability.” Proceedings of INFOCOM'99: Conference on
Computer Communications, Piscataway, NJ, USA: IEEE, 1999. p.218-26 vol.1.
Labovitz, C., Malan, G., Jahanian, F. “Internet routing instability.” IEEE/ACM Transactions on Networking, vol.6, (no.5),
IEEE; ACM, Oct. 1998. p.515-28.
Labovitz, C., Ahuja, A., Jahanian, F. “Experimental study of Internet stability and backbone failures.” Proceedings of the
29th Annual International Symposium on Fault-Tolerant Computing, June 1999, Los Alamitos, CA: IEEE Comput.
Soc, 1999. p.278-85.
Varadhan, K. Govindan, R. Estrin, D. “Persistent route oscillations in inter-domain routing.” Computer Networks, vol.32,
(no.1), Elsevier, Jan. 2000.
Griffin, T., Wilfong, G. “An analysis of BGP convergence properties.” Computer Communication Review, vol.29, (no.4),
Oct. 1999. p.277-88.
Griffin, T., Shepherd, F.B.; Wilfong, G. “Policy disputes in path-vector protocols.” Proceedings Seventh International
Conference on Network Protocols (ICNP'99), 1999. p.21-30.
Griffin, T., Wilfong, G. “A safe path vector protocol.” Proceedings of IEEE INFOCOM 2000. Piscataway, NJ, USA: IEEE,
2000. p.490-9 vol.2.
Gao, L., Rexford, J. “Stable Internet routing without global coordination.” Performance Evaluation Review, vol.28, (no.1),
June 2000. p.307-17.
Stewart III, J. BGP-4: Inter-Domain Routing in the Internet. Reading, MA. Addison-Wesley, 1999.
Black, U. IP Routing Protocols. Upper Saddle River, NJ. Prentice-Hall, 2000.
Huitema, C. Routing in the Internet.2nd ed. Upper Saddle River, NJ. Prentice-Hall, 2000.
21
BGP Traffic: Status
Number of
Updates
Received by a
Speaker at
MAE-EAST,
3/03/00 to
9/17/00
22