| Internet-Draft | AS Path Prepending | January 2022 |
| McBride, et al. | Expires 8 July 2022 | [Page] |
AS Path Prepending provides a tool to manipulate the BGP AS_Path attribute through prepending multiple entries of an AS. AS Path Prepending is used to deprioritize a route or alternate path. By prepending the local ASN multiple times, ASs can make advertised AS paths appear artificially longer. Excessive AS Path Prepending has caused routing issues in the internet. This document provides guidance with the use of AS Path Prepending, including alternative solutions, in order to avoid negatively affecting the internet.¶
This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.¶
Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.¶
Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."¶
This Internet-Draft will expire on 8 July 2022.¶
Copyright (c) 2022 IETF Trust and the persons identified as the document authors. All rights reserved.¶
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License.¶
The Border Gateway Protocol (BGP) [RFC4271] specifies the AS_PATH attribute which enumerates ASs a route update has traversed. If the UPDATE message is propagated over an external link, then the local AS number is prepended to the AS_PATH attribute, and the NEXT_HOP attribute is updated with an IP address of the router that should be used as a next hop to the network. If the UPDATE message is propagated over an internal link, then the AS_PATH attribute and the NEXT_HOP attribute are passed unmodified.¶
A common practice among operators is to prepend multiple entries of an AS (known as AS Path Prepending) in order to deprioritize a route or a path. This has worked well in practice but the practice is increasing, with both IPv4 and IPv6, and there are inherit risks to the global internet especially with excessive AS Path Prepending. Prepending is frequently employed in an excessive manner such that it renders routes vulnerable to disruption or misdirection. AS Path Prepending is discussed in Use of BGP Large Communities [RFC8195] and this document provides additional, and specific, guidance to operators on how to be a good internet citizen with the proper use of AS Path Prepending.¶
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119].¶
There are various reasons that AS Path Prepending is in use today including:¶
The following illustration, from Geoff Hustons Path Prepending in BGP, shows how AS Prepending is typically used:¶
+---+ +---+
+---| D |----| F |
| +---+ +---+
+---+ +---+ |
| A |---| B | |
+---+ +---+ 2x<- |
| +---+ +---+
+---| C |----| E |
+---+ +---+
¶
In the diagram above, A, B, C, D, E, and F all have a different AS. B will normally prefer the path via C to send traffic to E, as this represents the shorter AS path for B. If E were to prepend a further two instances of its own AS number when advertising its routes to C, then B will now see a different situation, where the AS Path via D represents the shorter path. Through the use of selective prepending E is able to alter the routing decision of B, even though B is not an adjacent neighbour of E. The result is that traffic from A and B will be passed via D and F to reach E, rather than via C. In this way prepending implements action at a distance where the routing decisions made by non-adjacent ASs can be influenced by selective AS Path prepending.¶
Since it is so commonly used, what is the problem with the excessive use of AS Path Prepending? Here are a few examples:¶
Care must be taken in prepending, as prepending can result in a ripple affect with multiple AS's performing the same set of prepend in the same direction can result in route leaks where the valid preferred path becomes now de-preferred.¶
<-5x <-5x <-5x
+---+ +---+ +---+ +---+
+---| D |----| F |----| H |----| J |
| +---+ +---+ +---+ +---+
+---+ +---+ | |
| A |---| B | | |
+---+ +---+ 13x<-| |
| +---+ +---+ +---+ +---+
+---| C |----| E |----| G |----| I |
+---+ +---+ +---+ +---+
¶
In the diagram above A, B, C, D, E, F G, H, I, J are all part of a different AS. B will normally prefer the path via D to send traffic to J, as this represents the preferred path to B, due to E prepending 13 instances of its own AS number when advertising routes to C. ISP J decides to prepend 5 instances of its own AS when advertising H, and ISP H decides to do the same and prepends 5 instances of its own AS when advertising to F. ISP F decides to as well prepend 5 instances of its own AS when advertising to D. B now sees 19 AS hops for prefixes coming from D to get to J which should be the preferred path compare to 18 AS hops coming from C which is now preferred. We now have a route leak to I as B now sends all of its traffic through I to reach J. This is the typical scenario where route leaks occur where providers decide to de-prefer a path, however as the same de-prefer of a path gets cascaded in the same direction, as a result, the path that should never be preferred as its as-path is very high in this case 18 AS hops ends up being the preferred path resulting in a route leak. BGP large communties along with conditional prepending, along with care being taken when prepending is performed between providers can help mitigate the adverse impacts of prepending.¶
The risk of excessive use of AS Path Prepending can be illustrated with real-world examples that have been anonymized using documentation prefixes [RFC5737] and ASs [RFC5398] . Consider the prefix 198.51.100.0/24 which is normally announced with an inordinate amount of prepending. A recent analysis revealed that 198.51.100.0/24 is announced to the world along the following AS path:¶
64496 64511 64511 64511 64511 64511 64511 64511 64511 64511 64511 64511 64511 64511 64511 64511 64511 64511 64511 64511 64511 64511 64511 64511¶
In this example, the origin AS64511 appears 23 consecutive times before being passed on to a single upstream (AS64496), which passes it on to the global internet, prepended-to-all. An attacker, wanting to intercept or manipulate traffic to this prefix, could enlist a datacenter to allow announcements of the same prefix with a fabricated AS path such as 999999 64496 64511. Here the fictional AS999999 represents the shady datacenter. This malicious route would be preferred due to the shortened AS path length and might go unnoticed by the true origin, even if route-monitoring had been implemented. Standard BGP route monitoring checks a route's origin and upstream and both would be intact in this scenario. The length of the prepending gives the attacker room to craft an AS path that would appear plausible to the casual observer, comply with origin validation mechanisms, and not be detected by off-the-shelf route monitoring.¶
In April 2010, a service provider experienced a routing leak. While analyzing the leak something peculiar was noticed. When we ranked the approximately 50,000 prefixes involved in the leak based on how many ASs accepted the leaked routes, most of the impact was constrained to Country A routes. However, two of the top five most-propagated leaked routes (listed in the table below) were Country B routes.¶
During the routing leak, nearly all of the ASs of the internet preferred the Country A leaked routes for 192.0.2.0/21 and 198.51.100.0/22 because, at the time, these two Country B prefixes were being announced to the entire internet along the following excessively prepended AS path: 64496 64500 64511 64511 64511 64511 64511 64511. Virtually any illegitimate route would be preferred over the legitimate route. In this case, the victim is all but ensuring their victimhood.¶
There was only a single upstream seen in the prepending example from above, so the prepending was achieving nothing except incurring risk. You would think such mistakes would be relatively rare, especially now, 10 years later. As it turns out, there is quite a lot of prepending-to-all going on right now and during leaks, it doesn't go well for those who make this mistake. While one can debate the merits of prepending to a subset of multiple transit providers, it is difficult to see the utility in prepending to every provider. In this configuration, the prepending is no longer shaping route propagation. It is simply incentivizing ASs to choose another origin if one were to suddenly appear whether by mistake or otherwise.¶
Based on analysis done in 2019, Excessive AS Path Prepending, out of approximately 750,000 routes in the IPv4 global routing table, nearly 60,000 BGP routes are prepended to 95% or more of hundreds of BGP sources. About 8% of the global routing table, or 1 out of every 12 BGP routes, is configured with prepends to virtually the entire internet. The 60,000 routes include entities of every stripe: governments, financial institutions, even important parts of internet infrastructure.¶
Much of the worst propagation of leaked routes during big leak events have been due to routes being prepended-to-all. AS64505 leak of April 2014 (>320,000 prefixes) was prepended-to-all. And the AS64506 leak of June 2015 (>260,000 prefixes) was also prepended-to-all. Prepended-to-all prefixes are those seen as prepended by all (or nearly all) of the ASs of the internet. In this configuration, prepending is no longer shaping route propagation but is simply incentivizing ASs to choose another origin if one were to suddenly appear whether by mistake or otherwise. The percentage of the IPv4 table that is prepended-to-all is growing at 0.5% per year. The IPv6 table is growing slower at 0.2% per year. The reasons for using prepend-to-all appears to be due to 1) the AS forgetting to remove the prepending for one of its transit providers when it is no longer needed and 2) the AS attempting to de-prioritize traffic from transit providers over settlement-free peers and 3) there are simply a lot of errors in BGP routing. Consider the prepended AS path below:¶
64496 64501 64501 64510 64510 64501 64510 64501 64501 64510 64510 64501 64501 64510¶
The prepending here involves a mix of two distinct ASNs (64501 and 64510) with the last two digits transposed.¶
Long AS Paths cause an increase in memory usage by BGP speakers. A concern about an AS Path longer than 255 is the extra complexity required to process it, because it needs to be encoded in more than one AS_SEQUENCE in the AS_PATH BGP path attribute.¶
There was an Internet-wide outage caused by a single errant routing announcement. In this incident, AS64496 announced its one prefix with an extremely long AS path. Someone entered their ASN instead of the prepend count 64496 modulo 256 = 252 prepends and when a path lengths exceeded 255, routers crashed¶
Various options, to provide path preference without needing to use AS Path Prepend, include:¶
<-5x <-5x <-5x
LP 110 +---+ +---+ +---+ +---+
+---| D |----| F |----| H |----| J |
| +---+ +---+ +---+ +---+
+---+ +---+ | |
| A |---| B | | |
+---+ +---+ 13x<-| |
| +---+ +---+ +---+ +---+
+---| C |----| E |----| G |----| I |
+---+ +---+ +---+ +---+
¶
In the diagram above A, B, C, D, E, F G, H, I, J are all part of a different AS. B will normally prefer the path via D to send traffic to J, as this represents the preferred path to B, due to E prepending 13 instances of its own AS number when advertising routes to C. ISP J decides to prepend 5 instances of its own AS when advertising to H, and ISP H decides to do the same and prepends 5 instances of its own AS when advertising to F. ISP F decides to also prepend 5 instances of its own AS when advertising to D. B now sees 19 AS hops for prefixes coming from D to get to J which should be the preferred path compare to 18 AS hops coming from C which is now preferred. We now have a route leak to I as B now sends all of its traffic through I to reach J. Route leak on B can be prevented locally within the operator domain by setting local-preference inbound, which is above as-path length in the best path selection, to higher then default 100 to 110 inbound from D, thus shielding the operator B from being influenced by the excessive prepend cascading ripple affect by F, H, J. Note that A still sees the cascading ripple affect of excess prepending, however A, or any service provider AS downstream of B, ingressing B, will be shunted to D via local-preference and the route leak is now mitigated for all downstream AS to the left of B that prefer the path through B.¶
Many of the best practices, or lack thereof, can be illustrated from the preceeding examples. Here's a summary of the best current practices when using AS Path Prepending:¶
+------------------------------------+
90| |
| X |
80| X X |
| X X |
70| X X |
| X X |
60| X X |
| X X |
50| X X |
| X X |
40| X X |
| X X |
30| X X |
| X X |
20| X XX |
| XX XX |
10| XX XXXX |
|XX XXXXXXXXXXXXXXXXX|
+------------------------------------+
5 10 15
AS Path Length in IPv4
X Axis = unique AS Paths in millions
¶
Long prepending may make a network more vulernable to route hijacking which will exist whenever there is a well connected peer that is willing to forge their AS_PATH or allows announcements with a fabricated AS path.¶
The authors would like to thank Greg Skinner, Randy Bush, Dave Farmer, Nick Hilliard, Martijn Schmidt, Michael Still, Geoff Huston and Jeffrey Haas for contributing to this document.¶