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 184.108.40.206 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 CDNs 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. ")] [AT&T Ex Parte with Commission Pai, The Internet Interconnection Ecosystem, Slide 13, June 26, 2014. ("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. "Hot Potato Routing" for Baran 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," (a.k.a. "Best Exit 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. [AT&T Ex Parte with Commission Pai, The Internet Interconnection Ecosystem, Slide 14, June 26, 2014 (diagraming cold potato routing).]
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.
Types of attacks:
- Black Hole / Spoofing (falsely announcing that network owns or controls AS)
- Dan Goodin, Russian-controlled telecom hijacks financial services’ Internet traffic, Ars Technica April 27, 2017("Normally, the network traffic bound for MasterCard, Visa, and the other affected companies passes through services providers that the companies hire and authorize. Using BGP routing tables, the authorized providers "announce" their ownership of the large blocks of IP addresses belonging to the client companies. On Wednesday afternoon at around 3:36pm Pacific time, however, Rostelecom suddenly announced its control of the blocks. As a result, traffic flowing into the affected networks started passing through Rostelecom's routers.")
- Declan Mccullagh, How Pakistan knocked YouTube offline (and how to make sure it never happens again) CNET Feb. 25, 2008
- Greg Sandoval, YouTube blames Pakistan network for 2-hour outage, CNET Feb. 24, 2008
- Man-in-the-middle attack
- Spoofing certificates in order to intercept or manipulate 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).
- Information Technology Laboratory :: Robust Inter Domain Routing Project "NIST is working with industry to design, standardize and foster deployment of technologies to improve the security and resilience of Internet Routing "
- NCCoE Secure Inter-Domain Routing [RFC :: Information Sharing :: Best Practice] The NCCoE recently released a draft of the NIST Special Publication (SP) 1800-14 Protecting the Integrity of Internet Routing: Border Gateway Protocol (BGP) Route Origin Validation and is requesting your feedback. The project's public comment period will close on October 15, 2018
- SBIR Phase II Project - Cryptographic Acceleration for Border Gateway Protocol Security (BGPSEC) 2015 award
- Special Publication 800-54 Border Gateway Protocol (BGP), 800-54 NIST 7/18/2007 [RFC :: Information Sharing :: Best Practice]
- 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
- Science and Technology Directorate :: Cybersecurity Projects :: Application of Network Measurement Science :: Predict, Assess Risk, Identify (and Mitigate) Disruptive Internet-scale Network Events Deepening Our Understanding of Internet Outages, DHS Science & Technology Blog Sept. 4, 2018 " One example of a NIDE we are studying is Border Gateway Protocol (BGP) hijacking. BGP routes traffic across the internet, and all networks connected to the internet rely on BGP to reach other networks. Researchers will measure BGP and examine connectivity issues caused by BGP hijacking. BGP hijacking occurs when a malicious attacker uses false network routing information to distort the internet’s common routing system. Incidents of these hijackings have blocked or derailed internet access for millions of people at a time."
- 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."
- FCC CSRIC Reports:
- WG4 – BGP Security Best Practices (pdf)
- WG6 – Secure BGP Deployment (pdf)
- Service Provider Interconnection for Internet Protocol Best Effort Service, Network Reliability and Interoperability Council V, Focus Group 4: Interoperability, Sec. 1.2.2
- FCC CSRIC Best Practices
- 9-5-0524: Network Operators and Service Providers Should Operate a Route Database
- 9-7-0409: Routing Resiliency
- 9-7-0437: Route Aggregation
- 9-7-0438: CIDR Use
- 9-7-0520: Route Policy
- 9-7-8526: Recover from Interior Routing Table Corruption
- 9-7-8042: BGP Validation
- 9-7-8043: Prevent BGP Poisoning
- 9-7-8045: Protect Interior Routing Tables
- 9-7-8050: MPLS Configuration Security
- 9-8-8525: Recovery from BGP Poisoning
- 9-8-8531: Recovery from MPLS misconfiguration
- 9-8-8654-8658: Routing Integrity
- National Science Foundation
- Award Abstract #1117052 TC: Small: Collaborative Research: Towards a Formal Framework for Analyzing and Implementing Secure Routing Protocols CNS Division Of Computer and Network Systems 2011 Investigator(s): Boon Thau Loo
- Award Abstract #0721736 Collaborative Research: NETS-NBD: RIDR: Towards Robust Inter-Domain Routing: Measurements, Models, and Deployable Tools CNS Division Of Computer and Network Systems Investigator(s): Christos Faloutsos 2007
- Award Abstract #0753492 Collaborative Research: CT-ISG: Mitigating Exploits of the Current Interdomain Routing Infrastructure Investigator(s): Aaron Jaggard 2007 NSF CNS Division Of Computer and Network Systems
- Award Abstract #0520326 NeTS-NBD: Internet Routing Forensics -- A Framework for Understanding, Monitoring and Detecting Abnormal Border Gateway Protocol Events Investigator Jun Li 2005 NSF CNS Division of Computer and Network Systems
- Award Abstract #0334108 STI: Towards more Secure Inter-Domain Routing Investigator Aviel Rubin OAC Office of Advanced Cyberinfrastructure (OAC) 2003
- Award Abstract #0221453 NSF Collaborative Research: Beyond BGP: Flexible and Scalable Interdomain Routing (BGGP) Investigator Lixia Zhang 2002
Statistics | Assessment | Forensics
Network interconnection arrangements are announced through BGP. Organizations that listen to these announcements can develop a relatively accurate picture of who interconnects with whom and whether the arrangement is transit or peering. Because these are routing announcements, the organizations can detect what routes are announced, but not the financial terms of the arrangements.
- Geoff Huston - BGP Table Growth
- Looking Glass,
- Trace Route
- Internet Atlas
- 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
- Craig Timberg, The Long Life of a Quick Fix, Wash Post, May 31, 2015
- Sharon Goldberg, Why Is It Taking So Long to Secure Internet Routing? 12 Acmqueue 1 (2014),