RFC 4264

RFC 4264: BGP Wedgies 🎀

• Network Working Group 💖
• Request for Comments: 4264
• Category: Informational 🌸
• Authors: T. Griffin (University of Cambridge) and G. Huston (APNIC) 👑
• Date: November 2005 📅
• Obsoletes / Updates: the title block lists neither, so this one doesn't replace or change any other RFC 🦋

Part 1 of 2 💅

Status of This Memo ✨

okay so this memo is for information only, so it's giving "FYI, internet friends" vibes. It is NOT an Internet standard of any kind 🙈 Anyone can share it freely, no limits.

Copyright Notice

© The Internet Society (2005). Mine? Nope, theirs 💜

Abstract

okay so the big assumption is that BGP (the Border Gateway Protocol) is a tool that hands out reachability info in a way that makes forwarding paths come out the same every single time 🧚 In this doc we're spotlighting a class of BGP setups where there's more than one possible result, and where some forwarding states that aren't the intended one are still totally stable. Also, when BGP settles down, it might pick its stable state in a non-deterministic way 😭 These stable-but-unintended BGP states are called "BGP Wedgies" 🍓

Table of Contents

1. Introduction ....................................................2
2. Describing BGP Routing Policy ...................................2
3. BGP Wedgies .....................................................3
4. Multi-Party BGP Wedgies .........................................6
5. BGP and Determinism .............................................7
6. Security Considerations .........................................8
7. References ......................................................9
   7.1. Normative References .......................................9
   7.2. Informative References .....................................9

1. Introduction ✨

okay so BGP [RFC1771] is commonly assumed to be a reachability tool that creates forwarding paths in a deterministic way. This doc is a "problem statement" memo 💅 It describes a group of BGP configs with more than one stable forwarding state. One of those states is the intended one, and the rest are unintended. When BGP is picking which stable forwarding state to land on, it might do that non-deterministically in these cases 👀

Those stable-but-unintended BGP states are called "BGP Wedgies" 💖

2. Describing BGP Routing Policy 🦋

BGP routing policies basically come from each network admin trying to optimize their spot in terms of cost, performance, and reliability. It's giving main character energy 👑

For cost, the local network's default policy often prefers routes learned from a customer over routes learned from some kind of peering exchange 💸 Same vibe here: the local network often prefers routes from a peer or a customer over routes from a directly connected upstream transit provider. These preferences can be set with a local preference configuration setting, where local preference overrides the AS path length metric of basic BGP operation 🔥

For reliability in the inter-domain routing world, a service provider often makes deals with two or more upstream transit providers. It passes routes to all of them and receives traffic from all sources 🌈 If the path to one upstream fails, traffic switches to the other links, and once that path is recovered, traffic should switch back ✨

When there are multiple upstream providers, it's also super common to rank them, so one connection is the preferred, or "primary", connection and the others are less preferred, or "backup", connections 💜 The idea is that backup connections only carry traffic for as long as the primary connection is down 🫶

You can express this primary/backup policy with local AS path prepending, where the AS path gets artificially made longer toward the backup providers by adding extra copies of the local AS 🍓 This isn't a deterministic selection algorithm, though, because the primary provider might also use AS path prepending toward its backup upstream. In some cases, the path through the backup provider can still end up being the shortest AS path 😭

There's also a different approach that uses BGP communities [RFC1997] 🧚 The provider publishes a set of community values, and the client uses them to pick the provider's local preference setting. The client can tag a route as "backup only" toward the backup provider and as "primary preferred' toward the primary provider, assuming both providers support community values with those meanings 💅 Here, local preference overrides the AS path length metric, so a route marked "backup only" only gets selected when there's no other source for that route 🌸

3. BGP Wedgies 💖

okay so the richness of local policy expression you get from communities, mixed with how a distance vector protocol like BGP behaves, means some configs have more than one "solution," or more than one stable BGP state 🔥 Figure 1 shows an example of this:

    +----+peer                peer+----+
    |AS 3|------------------------|AS 4|
    +----+                        +----+
      |provider             provider|
      |                             |
      |                             |
      |customer                     |
    +----+                          |
    |AS 2|                          |
    +----+                          |
      |provider                     |
      |                             |
      |                             |
      |customer             customer|
      +---------------+  +----------+
        backup service|  |primary service
                     +----+
                     |AS 1|
                     +----+

                              Figure 1

Here's the tea ☕ AS1 marks its advertisement of prefixes to AS2 as "backup only," and its advertisement to AS4 as "primary." AS4 advertises AS1's prefixes to AS3. AS3 hears that from AS4 across the peering link and picks AS1's prefixes with the path "AS4, AS1." AS3 then advertises those prefixes to AS2. AS2 now hears two paths to AS1's prefixes: the direct one to AS1, and the one via "AS3, AS4, AS1." AS2 prefers the longer path, because the directly connected routes are marked "backup only," and AS2's local preference decision favors the AS3 advertisement over the AS1 advertisement 😭

This is the intended outcome of AS1's policy settings 🎀 In the "normal" state, no traffic goes from AS2 to AS1 over the backup link. Instead, AS2 reaches AS1 through a path that goes through AS3 and AS4 and uses the primary link to AS1 ✨

That intended outcome holds as long as AS1 announces its routes on the primary path to AS4 before it announces its backup routes to AS2 🫶

Now, if the AS1-AS4 path breaks and causes a BGP session failure between AS1 and AS4, AS4 withdraws its advertisement of AS1's routes to AS3, and AS3 sends a withdrawal to AS2 🙈 AS2 then selects the backup path to AS1, advertises that path to AS3, and AS3 advertises it to AS4. Again, this is all part of the intended primary/backup behavior, so all traffic to AS1 goes over the backup path 💅

Here's where it gets messy 💀 When connectivity between AS4 and AS1 comes back, the BGP state does NOT go back to the original state. AS4 learns the primary path to AS1 and re-advertises it to AS3 with the path "AS4, AS1." AS3 has the default preference of favoring customer-advertised routes over peer routes, so it keeps preferring the "AS2, AS1" path, and it doesn't pass any updates along to AS2 😭 Even after the AS4-to-AS1 circuit is restored, traffic from AS3 to AS1 and from AS2 to AS1 keeps reaching AS1 over the backup path, even though the primary path through AS4 is back in service 🥺

The only way to get the intended forwarding state back is for AS1 to deliberately bring down its eBGP session with AS2, even though it's carrying traffic. That makes BGP state revert to the intended configuration 🔥

It's also very common for an AS to try to balance incoming traffic across several providers using that same primary/backup mechanism 🌈 For some prefixes, one link is the primary and the others are backups, while for other prefixes, a different link is the primary. Figure 2 shows an example:

    +----+peer                  peer+----+
    |AS 3|--------------------------|AS 4|
    +----+                          +----+
      |provider               provider|
      |                               |
      |                       customer|
      |customer                       |
    +----+                          +----+
    |AS 2|                          |AS 5|
    +----+                          +----+
      |provider               provider|
      |                               |
      |                               |
      |customer               customer|
      +-----------------+  +----------+
                        |  |
 backup (192.0.2.0/25)  |  |primary service (192.0.2.0/25)
primary (192.0.2.128/25)|  |backup service (192.0.2.128/25)
                       +----+
                       |AS 1|
                       +----+

                              Figure 2

The intended configuration sends all incoming traffic for addresses in 192.0.2.0/25 over the link from AS5, and all incoming traffic for addresses in 192.0.2.128/25 from AS2 🦋

In this case, if the link between AS3 and AS4 gets reset, AS3 learns both routes from AS2, and AS4 learns both routes from AS5 🍓 Because those customer routes are preferred over peer routes, once the AS3-AS4 link is restored, neither AS3 nor AS4 changes how it routes AS1's routes. The situation is now wedged, meaning there's no eBGP peering you can reset to flip BGP back to the intended state. This is an instance of a BGP Wedgie 💀

The way out is for AS1 to withdraw the backup advertisements on both paths, run for an interval without any backup, and then re-advertise the backup prefix advertisements 🫶 The length of that interval can't be easily determined in advance. It has to be long enough for AS2 and AS5 to learn about an alternate path to AS1. Once that's happened, the backup routes can be re-advertised 🧚

4. Multi-Party BGP Wedgies ✨

okay so this gets even messier when three or more parties are providing upstream transit to one AS 😭 Here's the setup:

    +----+ peer              peer +----+
    |AS 3|------------------------|AS 4|
    +----+                        +----+
     ||provider             provider|
     |+----------------+            |
     |                 |            |
     |customer         |customer    |
    +----+peer   peer+----+         |
    |AS 2|-----------|AS 5|         |
    +----+           +----+         |
      |provider  provider|          |
      |                  |          |
      |                  |          |
      |customer  customer|  customer|
      +---------------+  |+---------+
        backup service|  ||primary service
                     +----+
                     |AS 1|
                     +----+

                              Figure 3

so the intended vibe is that AS2 and AS5 are both backup providers for AS1, and AS4 is the primary 💅 Then the link between AS1 and AS4 breaks and comes back. AS3 keeps sending traffic to AS1 through AS2 or AS5, and now we have a problem 🙈 Resetting the link between AS2 and AS1 alone won't fix it, because the BGP best route to AS1 switches over to AS5, and AS2 and AS3 start learning their path to AS1 through AS5. Iconic chaos, honestly.

What AS1 sees is incoming traffic arriving on the backup link from AS2. If it resets that connection, the traffic doesn't go back to the primary path. It just gets moved over to AS5 instead 💀 The fix is to reset the link to AS2 and the link to AS5 at the same time. Not intuitive at all, ngl, because at any moment only one of those links is carrying backup traffic, but both BGP sessions have to go down together before the intended primary and backup state can come back. Main character plot twist 🦋

5. BGP and Determinism 🔮

okay, real talk: BGP doesn't behave deterministically in every case. That means there's both intended and unintended non-determinism in it 🌸 For example, the default final tie break in some BGP implementations is to prefer the longest-lived route. If you want determinism at that last step, you'd need a comparison with a predictable outcome, like comparing router identifiers. This kind of non-determinism is called "intended" here, since the policy interactions are, to some extent, predictable for network admins 🎀

Then there's the "unintended non-determinism" 👀 BGP can produce these outcomes when policies interact in ways nobody expected. These aren't misconfigurations in the usual sense, because every policy can look totally rational on its own. But when they interact across multiple routing entities, they can cause unintended results, and BGP can land in a state with those results in a non-deterministic way ✨

Unintended non-determinism wouldn't be such a big deal if every stable routing state matched the policy writer's intent. Unfortunately, that's not guaranteed. The examples above show that BGP can have multiple stable states from one configuration, and some of them don't match what the policy writer wanted 😭 These cases can be described as a form of "route pinning", where the route gets pinned to a non-preferred path.

The challenge for network admins is keeping the intended state in place. In some situations, the only way to get there is a deliberate service disruption: withdrawing the routes that carry traffic, then re-advertising routes in a specific order to induce the intended BGP state. The catch is that understanding why BGP settled into an unintended state takes knowledge of remote networks' BGP policy configuration. There just isn't enough local information for any single network administrator to find the root cause of the unintended state, and there isn't enough to let one admin work through the steps to get back to the intended routing state on their own 🫶

It's reasonable to expect interconnection density to keep going up, and policy-based preference settings for learned and re-advertised routes to get more expressive. So the number of unintended but stable BGP states will probably grow too, and it'll get harder for operators to figure out ahead of time which sequence of route withdrawals and re-advertisements they'd need 😩

Whether this could eventually push the BGP routing system to a point where no network can reliably direct traffic deterministically is, at this stage, speculation 🔭 BGP Wedgies show that a complex enough interconnection topology, combined with a policy language expressive enough, can lead to several stable BGP states instead of one intended state. As topology complexity goes up, it's not possible to predict deterministically which state BGP will converge to. It's kind of a paradox: traffic engineering demands seem to need more expressive policy routing, running over denser interconnection, while still behaving deterministically. That may not be sustainable for BGP-based routing systems 🌈

6. Security Considerations 🔐

Okay, this section is serious, so bestie, please read it carefully 🥺 BGP is a relaying protocol: route information gets received, processed, and forwarded. BGP has no specific mechanism to stop a forwarding agent from modifying that information without authorization. Routing information can be changed or deleted, or false information can be inserted, without the originator or any of the recipients knowing about it 😱

This memo doesn't propose any changes to the BGP protocol, and it doesn't propose any changes to how BGP is deployed. So it doesn't add any new factors to the security and integrity of inter-domain routing 🧚

This memo shows that when you try to create policy-based outcomes for path selection on incoming traffic, you can end up with configurations that have multiple stable outcomes instead of just one. On top of that, for some of those multiple outcomes, the BGP selection of a particular one isn't deterministic 💜

This kind of behaviour may be exploitable by a hostile third party. A common theme in BGP Wedgies is this: starting from an intended or desired forwarding state, losing and then restoring an eBGP peering connection can flip the network's forwarding configuration into an unintended and possibly undesired state. Getting the BGP forwarding configuration back to the intended or desired state may take significant administrative effort, based on BGP state and configuration knowledge that might not be available locally. If a hostile third party can deliberately reset the BGP session and cause the initial conditions that lead to an unintended forwarding state, the effects of that state can last far longer than the temporary connectivity interruption that triggered it 💀 If those effects are significant, including higher cost, reduced available bandwidth, increased latency, or degraded service reliability, then disrupting a BGP session could be a really attractive attack vector for a hostile party 🚨

7. References 📚

7.1. Normative References

[RFC1771]  Rekhter, Y. and T. Li, "A Border Gateway Protocol 4
           (BGP-4)", RFC 1771, March 1995.

7.2. Informative References

[RFC1997]  Chandrasekeran, R., Traina, P., and T. Li, "BGP
           Communities Attribute", RFC 1997, August 1996.

Authors' Addresses 🎀

Tim G. Griffin Computer Laboratory University of Cambridge

EMail: Timothy.Griffin@cl.cam.ac.uk

Geoff Huston Asia Pacific Network Information Centre

EMail: gih@apnic.net

Full Copyright Statement 📜

Copyright (C) The Internet Society (2005).

This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights.

This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

Intellectual Property 🔏

The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79.

Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr.

The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org.

Acknowledgement 💖

Funding for the RFC Editor function is currently provided by the Internet Society.