Paul Jakma's Blog

(originally published Aug 25, 2008 on blogs.sun.com – republishing here as Oracle nuked it all, but it’s been referenced in places).

Path-hunting is the tendency of BGP, when a path is withdrawn by a remote AS, to “hunt” from one path to another, before finally converging. The problem has been described elsewhere, particularly by Geoff Huston (e.g. in this ISOC column on BGP dampening). Manav Bhatia also has a nice, graphic explanation of BGP path hunting. Tony Li and Geoff Huston additionally have authored a very interesting draft on the problem, draft-li-bgp-stability – which analogises BGP convergence with wave-front propogation, where the “front” of convergence bends with differences in path-propogation times, and expands out where ASes connect with multiple others.

This problem is very similar to[5], if not a special-case of, the well-known “count to infinity” problem inherent to the Bellman-Ford distance-vector protocols. With infinity being constrained, by BGPs built-in split-horizon behaviour, to the number of simple paths in the topology.

Path Hunting overview

In short: given some converged subset of the BGP topology, with A and B connected by a set of one or more distinct paths {1, …, n}, with the time taken for a message to propogate down path x of t[x] so that the set of paths has a directly corresponding set of propogation times T = {t[0], …, t[n]}. Then for any announcement which passes through A to B, BGP will reach a “useful convergence”[1] by or within a time of:

• For an UPDATE announcing a new/updated path: minimum(T)
• For a withdrawal: maximum(T)

The latter convergence time being due to the ‘hunting’ behaviour of BGP, and indeed consistent with the well-known “Good news travels quickly, bad news travels slowly”[3] behaviour of distance-vector protocols.

E.g. imagine A announces some prefix to C, and imagine (for simplicity) that B does not re-announce paths to E or H, with simple paths between A and B of {ACB, ACDEB, ACDFGHB, ACDFGEB, ACDEGHB}. I.e.:

-A--C----------B
     \        / \
      D------E   H
       \      \ /
        F------G

So after a time of minimum(T), B will have received at least one UPDATE corresponding to a valid path and would be able to forward packets toward A for the prefix. Though the system is not converged, any further UPDATEs B receives can only cause it to select a better path, so the system is at least “usefully-converged” – it can route packets.

After a time of maximum(T), the state at each speakers will be fully converged, and B may then have the following paths in its RIB (arbitrarily making assumptions about preferences speakers may have), for whatever prefix it is, from among which B may pick its preferred path:

• From C, Path: CA
• From E, Path: EDCA
• From H, Path: HGFDCA

Note that B does not know about the ACDFGEB or ACDEGHB paths, however if the DE edge were withdrawn, E potentially could switch to G (and issue an update to B when it does so) and similarly with the FG edge and latter path. B can pick anyone of the above as its preferred path. I.e. though these paths are hidden from B, they can still come into play.

Imagine A now withdraws the prefix from C – so the connectivity to the prefix is now lost as far as the rest of the graph goes. After a time of minimum(T) B will receive at least one message (that might be a withdrawal from C, but it could just as well be an UPDATE from E as E hunts its preferred path over to G). Imagine it happens to come from the peer which it had selected as best, and results in B picking a new best path via another peer (e.g. because its a withdrawal, or an UPDATE with less favourable path-attributes). Then the next update arrives from the peer newly preferred, and so B picks again, and so on. So B’s best-path may well change between the following best-paths:

1. From E, Path EDCA
2. From H, Path HGFDCA
3. From H, Path HGEDCA
4. From E, Path EGFDCA

I.e. before B can converge on “there is no path”, it potentially will first “hunt” through various paths that are already dead[2].

Yet, B did receive a message which was triggered by As withdrawal – several in fact! If only B could use the first message to see that, as it was A which withdrew the prefix, that therefore all paths via A must be dead, then it could short-circuit the whole hunting process!

Possible Solutions

Huston and Li propose various possible changes to BGP to mitigate hunting, such as removing the MRAI timer, band-stop filtering of updates, path-exploration damping, etc, all of which are implementable without change to the BGP protocol itself. Other proposals include Brian Dickson’s second-best-backup proposal which seeks to speed up convergence by providing visibility of additional paths besides the best-path (such as the ACDFGEB path which is initially hidden to B in the example above), and also to provide a fast-path for withdrawals (this proposal requires changes to BGP). None of these proposals actually solve path-hunting, they instead try to either filter it out and/or speed it up.

Hunting can eliminated in BGP if it could be extended with mechanisms to allow BGP to recognise nodal changes in state, across paths. Other DV protocols (DSDV, AODV) solve similar problems by numbering messages/routes with a sequence-number. This sequenced-DV approach is problematic with BGP as it tends to require either that routers in an AS somehow maintain a shared counter, or that BGP must describe a more detailed router-router topology (rather than todays abstract AS-AS topology).

Some possible mechanisms that eliminate hunting:

• BGP-RCNA possible means to allow for convergence in O(minimum(T)) for all kinds of state-changes is described by Pei, Azuma, Massey and Zhang in “BGP-RCN: improving BGP convergence through root cause notification”. Speakers include an additional attribute of information with updates/withdrawals, called the “Root Cause Notification” consisting of a list of (ASN,sequence number) tuples. This allows a receiving speaker to compare announcements received via different paths and determine relative recency, so allowing it to always act on the most recent information.

  The sequence number dependency is a significant barrier to deployment.

• AS Poisoning[4]

  This is essentially a simplified version of BGP-RCN, that does away with the problematic sequence number. When withdrawing a prefix, a speaker can include information that “poisons” nodes (or even edges). E.g. if A sends some kind of “Poison: A” attribute with its withdrawal, and if that attribute will propogate along with the withdrawal, then B can conclude from the first withdrawal it receives that all paths that go via A are defunct. BGP can now converge on a prefix-withdrawn state in minimum(T). The downside being that convergence to the prefix-announced state instead occurs in maximum(T) – though it is possible that BGP can be “usefully converged” prior to that, which would be a more useful state than path-hunting.

  So we can “fix” path-hunting, and maximise withdrawal convergence without introducing any co-dependent state with only mild changes to BGP, though at some expense to announcement convergence.

A further observation to be made is that IGP routing has switched from distance-vector to link-state (or “map-distribution”) because of the same convergence limitations. Further, there are proposals for BGP security extensions which overlay a link-stateish topology onto BGP, and the BGP-RCN approach is not far from a link-state protocol either. So it is perhaps not completely unreasonable to imagine whether some kind of topological-state mechanism could be bolted onto BGP, that could be used to augment the path-selection process.

So…

Solutions to the hunting problem either are imperfect local-hueristics (which may even make convergence worse in cases where they fail), or protocol extensions with fairly significant trade-offs (either in complexity or adverse side-effects). It seems unlikely there’s any magic bullet, given the length of experience we have with Bellman-Ford/DV protocols.

—

Corrections and comments would be appreciated.

Update: Added footnote 5.

1. “Useful convergence” being where speakers all have converged on some particular state, OR are in a certain semi-converged state such that any further messages still propogating can only cause speakers to transition their routes from an existing, valid path to another valid path (this can not be the case if there are any withdrawal messages still to propogate). I.e. forwarding remains loop and blackhole free.

2. This is a problem as it means that if, outside of the subset we’re consider, B has other, less-preferred connections, then B will have to wait max(T) before it can decide there are no valid paths in this subset and start to consider paths outside of this subset.

3. Does anyone know the original source of this? (Douglas Comer, “Internetworking with TCP/IP”, Prentice-Hall, 1991, seems to quote it).

4. Described only in private correspondence, to date.

5. In the sense that the cause of the count-to-infinity problem was due to the source event of a routing update being indeterminable. Split-horizon cut-out the count-infinity problem for direct loops between neighbours, by preventing updates from propogating endlessly. The addition of a record-of-path (e.g. AS_PATH in BGP) solved count-infinity for multi-hop loops, by preventing updates from propogating along any but simple paths. The remaining problem is of updates travelling along multiple, parallel paths with different propogation times, preventing us from recognising which message received is the most recent – fixed with sequence numbers in some DV protocols. Each modification has pared down DV protocols slightly, restricting where valid information can flow and how it is recognised.