Cybertelecom
Cybertelecom
Federal Internet Law & Policy
An Educational Project

Border Gateway Protocol

Dont be a FOOL; The Law is Not DIY
Internet Addresses
- DNS
- History
- NTIA & Fed Activity
- ICANN
- Root Servers
- ccTLDs
- - .us
- - -.kids.us
- gTLDs
- - .gov
- - .edu
- - .mil
- - .xxx
- WHOIS
- WGIG
- ENUM
- IP Numbers
- - IPv6
- BGP
- NATs
- Ports
- Security
- Trademark
- AntiCybersquatter Consumer Protection Act
- Gripe Sites
- Truth in Domain Names
Telephone Addresses

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.

Announcements

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.

Route Selection

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 192.104.54.5 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.

* 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.

Alternative Routes

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:

Filtering

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.,

Local Preference

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:

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.

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.

 

 

History

"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]

Definitions

Autonomous System

"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.  

Internal Routing

In order to route traffic internally, networks use

BGP Security

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).

Government Activity

Papers

Links