Border Gateway Protocol
- NTIA & Fed Activity
- Root Servers
- - .us
- - -.kids.us
- - .gov
- - .edu
- - .mil
- - .xxx
- IP Numbers
- - IPv6
- AntiCybersquatter Consumer Protection Act
- Gripe Sites
- Truth in Domain Names
- Route Selection
- Hot Potato Routing
- Internal Routing
- BGP Security
When networks interconnect, they agree to announce routes to each other utilizing the Border Gateway Protocol (BGP). This is known as "interdomain interconnection."
There are two parts to BGP: (a) route announcements by the traffic receiving network and (b) route selection by the traffic sending network.
A receiving network announces which destinations (which ASNs) it provides a route to, and how many hops (a.k.a. "AS path length") it takes to get there. [GAO, 2006, p. 7] . If it does not announce routes, then there is no path through that network to that particular destination. The route announcement information does not relay information about capacity or quality of service. The route announcement may include localization information (i.e., MEDS, that the network would prefer to receive traffic destined for New York City at the interconnection point closes to New York City).
Routes that are within the receiving network's domain are OnNet and generally fall under peering. A receiving network can also announce routes to destinations that can be reached through the provider interconnecting with third party networks; these are OffNet and fall under transit.
The sending network listens to announcements and compiles a routing table. The routing table will contain list of known routes, blocks of IP addresses associated with each route, and cost metrics associated with each route. Some information comes from BGP announces; some the sending network adds to the table.
Based on the information in the routing table, the sending network will decide which route to use when sending traffic. The sending network looks in its routing table to see which networks provide a route to, for example, the destination address 18.104.22.168 and how many networks the packets have to go through. Based on that information, the router will select a route to send the packets off to, sending them off to the next hop, which will them do the same look up and make similar decisions, until the packets reach their destination.
- Network BAR (ASN 5) announces that it has routes to ASN 5 (itself) and ASN 7, ASN 8, and ASN 9 through ASN 8.
- Network FOO (ASN 4) hears BAR. FOO wants to send traffic to ASN 9. FOO hears that BAR provides a route to ASN 9 through ASN 8. FOO sends the traffic to BAR, the next hop.
- BAR now does exactly the same routing look up, to see what the best route would be to deliver the traffic to ASN 9*
* Note that a "Route Flap" can occur when FOO and BAR keep sending the traffic back and forth because their routing tables tell them that the other is the "best route" to the destination ASN 9.
If there is a choice of routes (if different networks are announcing routes to a destination), how does a sending network decide which route to utilize? A sending network will select which route to send traffic to based on the following criteria in the following order:
- Highest Local Preference
- Lowest AS Path Length
- Lowest Origin Type
- Lowest MED
- eBGP learned over iBGP learned
- Lowest IGP cost to border router
- Closest egress point (hot potato routing)
- Lowest Router ID (tie breaker)
The sending network will engage in a certain degree of filtering of possible routes, removing prefixes that for instance your customer does not actually own, configuration mistakes, or routes involved in attacks. Almost every peering policy calls on a peering partner to filter routes. An announcing network will also filter out ASNs that it does not want to announce.,
Where there are alternative paths, there might be good business reasons for selecting one route over another. The sending network might select a customer's route over a free route (after all the customer is paying). The sending network might select a settlement free route over a route where it is the transit-customer. The sending network can assign "local preferences" to different routes so that route selection is made based on this criteria. For instance, the sending network assign values as follows:
- 90-99 customers
- 80-89 peers
- 70-79 transit providers
Route with the highest score takes the prize.
AS Path Length
When BAR announces that it has a route to ASN 9 through ASN 8, it is announcing a route and a path length. In this case the path length is 2 (two AS hops). If FOO was directly interconnected with ASN 9, ASN 9 would also be announcing a route to ASN 9 with a path length of 1. Under normal circumstances, FOO will listen to both BGP announcements, compare the path lengths, and send the traffic along the route with the shortest path length. In this case, FOOS would select to send the traffic directly to ASN 9 instead of sending it through BAR.
An announcing network can manipulate AS Path Length by making it appear that a route is longer than it is. An announcing network can prepend ASNs to its announcements to extend the AS Path Length. For example, in the example above, BAR made the announcement "ASN 8 ASN 9" - that it is a two hop route to ASN 9. If it makes the announcement "ASN 8 ASN 8 ASN 9," it now makes it seem like ASN 9 is three hops away, and influences the routing decisions of the sending network. BGP Best Path Selection and Manipulation, CISCO (2014)
NOTE: With the evolution of the Internet ecosystem and CDN's directly connecting to large BIAS providers at IXPs, one would anticipate that AS Path lengths would be shortening. An AS Path would include the large BIAS provider and the CDN if directly connected, or it could be the BIAS provider, an intermediary transit provider, and a CDN if indirectly connected.
- Mirjam Kuhne, Update on AS Path Lengths Over Time, RIPE NCC Sept. 10, 2012 ("the number of AS hops for IPv4 networks is fairly stable at 4.3 hops over the last three years, indicating that the new ASes seem to be contributing to an increased density of the Internet rather than topological expansion.")
- Mirjam Kuhne, Interesting Graph - AS Path Lengths Over Time RIPE NCC Oct. 2010
Multiple Exit Discriminator (MEDs)
BAR can also announce MEDs. Basically BAR is announcing a localization preference that BAR wants traffic destined for a destination to be delivered near that destination (a.k.a. cold potato routing).
Simply because a receiving network announces MEDs does not mean that the sending network has to honor it. Generally the sending network will honor MEDs when the two networks have an interconnection contract with terms that specify provisions concerning MEDs.
"NSFNET introduced a complexity into the Internet, which the existing network protocols could not handle. Up to the NSFNET, the Internet consisted basically of the ARPAnet, with client networks stubbed off the ARPAnet backbone. I.e., the hierarchy between so-called Autonomous Systems (AS) was linear, with no loops/meshes, with the Exterior Gateway Protocol (EGP) used for for inter-AS routing carrying the AS Number of the routing neighbor. This made it impossible to detect loops in an environment where two or more separate national backbones with multiple interconnections exist, specifically the ARPAnet and the NSFNET. I defined that I needed an additional "previous" AS Number for the inter-AS routing to allow supporting a meshed Internet with many administrations for its components. Meetings with various constituents did not get us anywhere, and I needed it quickly, rather then creating a multi-year research project. In the end, Yakov Rekhter (IBM/NSFNET) and Kirk Lougheed (Cisco) designed a superset of what I needed on three napkins alongside an IETF meeting that included not just the "previous" AS Number but all previous AS numbers that an IP network number route had encountered since its origin. This protocol was called the Border Gateway Protocol (BGP) and versions of it are in use to this day to hold the Internet together. BGP used the Transmission Control Protocol (TCP) to make itself reliable. Use of TCP as well as general "not invented here" caused great problems with the rest of the Internet community, which we somewhat ignored as we had a pressing need, and soon with NSFNET, Cisco and gated implementations at hand, the Internet community did not have much of a choice. Eventually and after long arguments, BGP got adopted by the IETF." [Braun]
"An AS is a connected group of one or more IP prefixes run by one or more network operators which has a SINGLE and CLEARLY DEFINED routing policy." IETF RFC 1930.
"An Autonomous System is a connected group of IP networks that adhere to a single unique routing policy that differs from the routing policies of your network's border peers." ARIN
Autonomous System: "A group of routers under a single administration." Service Provider Interconnection for Internet Protocol Best Effort Service, Network Reliability and Interoperability Council V, Focus Group 4: Interoperability, Sec. 1.2.2
Autonomous System Number
"An ASN is a globally unique number used to identify an Autonomous System. An ASN enables an AS to exchange exterior routing information with neighboring ASes." ARIN
"An AS has a globally unique number (sometimes referred to as an ASN, or Autonomous System Number) associated with it; this number is used in both the exchange of exterior routing information (between neighboring ASes), and as an identifier of the AS itself." IETF RFC 1930.
Hot / Cold Potato Routing
"Hot Potato Routing" is an interconnection policy between peers where one network hands off traffic to another network at the closest exchange point. If both networks follow Hot Potato Routing and if traffic levels are relatively balanced, then each network will relatively equally bare the cost of carrying the traffic. [NRIC Sec. 1.2.2 ("A form of inter-domain routing in which a packet destined for a neighboring ISP is sent via the nearest interconnect to that ISP. ")]
The history of "Hot Potato Routing" has its routes back to Paul Baran. Thus, "Hot Potato Routing" was not so much a part of an interconnection / settlement scheme as much as a protocol to ensure reliability and resiliency. [Roberts, Computer Science Museum p. 14 1988]
Content Delivery Networks generally engage in "Cold Potato Routing," holding onto traffic for as long as possible and handing it off as close to the eyeballs as possible, seeking to manage quality of service and defray the transit costs of the receiving networks.
In order to route traffic internally, networks use
- Internal Gateway Protocol
- Intermediate System to Intermediate System (IS-IS)
- Large BIASs tend to use IS-IS
- Open Shortest Path First (OSPF)
BGP, like so many things in the Internet, is built on trust. An independent network announces through BGP routes that it can deliver - and other networks accept that announcement without verification. This can lead to unfortunate situations, both malicious and accidental. There was a time in the late 1990s when a guy in a garage announced that he was the best route to UUNET, and suddenly all of UUNET's traffic was attempting to get through this poor guys garage. In another incident, Pakistan decided that it was offended by a video on YouTube and attempted to blackhole YouTube. Unfortunately the blackhole sent all routes into the blackhole, and was announced out to the Internet. Soon every network believed that the blackhole was the path to YouTube. A different variation is known as the man-in-the middle attack, when someone intentionally announces that they are the route to some place, in order to capture, monitor or manipulate that traffic.
This has led to efforts to improve the security of BGP, and verify that when someone announces a route, they actually are making a valid announcement. BGP Security efforts would use a public resource key infrastructure (RPKI).
- NIST Special Publication 800-54 Border Gateway Protocol (BGP),, NIST 7/18/2007
- Special Publication 800-54 Draft Version 2, Border Gateway Protocol Security, NIST 6/5/2007
- Draft Special Publication 800-54, Border Gateway Protocol Security NIST announces the release of draft SP 800-54, Border Gateway Protocol Security. This document introduces the Border Gateway Protocol (BGP), explains its importance to the Internet, and provides a set of best practices that can help in protecting BGP. Best practices described here are intended to be implementable on nearly all currently available BGP routers without requiring installation of new protocols. To improve the security of BGP routers, a series of recommendations are made. NIST requests public comments on SP 800-54 by November 30, 2006. Please submit comments to email@example.com with "Comments SP800-54" in the subject line
- US DHS Secure Protocols for the Routing Infrastructure (SPRI)
- Sparta, Inc. (2006, Sept) Secure Protocols for the Routing Infrastructure (SPRI) Initiative: A Road Map (First Draft)
- Internet Infrastructure: DHS Faces Challenges in Developing a Joint Public/Private Recovery Plan, GAO Report 06-672, p 7 (June 2006)
- p. 7 "The Border Gateway Protocol—a protocol for routing packets between autonomous systems. This protocol is used by routers located at network nodes to direct traffic across the Internet. Typically, routers that use this protocol maintain a routing table that lists all feasible paths to a particular network. They also determine metrics associated with each path (such as cost, stability, and speed), so that the best available path can be chosen. This protocol is important because if a certain path becomes unavailable, the system will send data over the next best path."
- Sharon Goldberg, Why Is It Taking So Long to Secure Internet Routing? 12 Acmqueue 1 (2014),
- BGPlay (route visualization tool)
- AS Ranks by CAIDA
- BGP Inspect MERIT
- BGP Case Studies, IP Routing, CISCO
- DRAGON: Distributed Route Aggregation on the Global Network
- Hurricane Electric BGP Toolkit
- Cyclops at UCLA ("Cyclops is a network audit tool for service providers and enterprise networks, providing a mechanism to compare the observed behavior of the network and its intended behavior. Cyclops is able to detect several forms of route hijack attacks, i.e. when Internet routes are maliciously diverted from their original state. Recent incidents such as the Youtube hijack in Feb'08 show that route hijacking is currently a real threat in the Internet. ")
- CIDR Report (stats on AS networks, BGP)
- Route Views