The ISP Column An occasional column on things Internet
	Other Formats:

Damping BGP
June 2007

The topic of the scalability of the Internet’s routing system has been one that has achieved elevated attention in recent months, and that’s not counting the five articles in this column in the past 12 months! One of its fascinating aspects is that the routing system appears to be one that has no natural constraints. Adding another prefix in the global routing table, or generating another protocol update, are actions that happen without any particular cost, penalty or constraint. So it’s little wonder that from time to time we ponder whether the growth trends in routing exceed our ability to throw ever more capable technology at routing.

But of course this is not just a passing fad. The underlying issues with routing scalability are persistent themes that have been around for many years. These themes relate to the overall stability of the routing protocol and the performance of the packet forwarding subsystem when dealing with ever larger routing domains, finer granularity of information and ever denser levels of element interconnection.

The study of scalability of routing breaks into the classic subtopics of memory, processing and bandwidth. The larger the routing system grows the larger the required search space in order to perform the correct lookup operation for packet forwarding, inferring a requirement for larger memory for forwarding lookups. The combination of a larger routing space and a denser set of interconnections also increases the memory requirements for the operation of the routing protocol itself. The combination of the absolute size of the routing space and the level of dynamic update, or stability, have processing implications. The higher the level of dynamic changes in the routing state, then the greater the processing requirement that is imposed on each routing element. If the processing element can fall behind in processing the update load then there are implications in terms of the accuracy of the routing state, and potential implications in increased memory demands to hold the backlogged queues of unprocessed updates. And because routing is a distributed protocol, the greater the size of the routing space, the more densely interconnected the network and, more importantly, the greater the level of dynamic change, then the larger the amount of generated routing traffic and, by implication the higher the bandwidth demands for routing itself. So as the routing system grows so does the demands for additional memory processing capacity and bandwidth.

Of the three, bandwidth is perhaps the lesser of these scalability concerns, leaving memory and processing loads as consistent themes in studies of the routing system over many years.

One of the early observations relating to processing load was that it appears that a relatively small number of route objects were the subject of a large number of routing updates. The commonly observed behaviour at the time was that a route object would be announced, then withdrawn, then announced again, and so on for extended periods of time, and often at quite high frequency. A response to this type of load in the internet’s inter-domain routing protocol, the Border Gateway Protocol (BGP) was the introduction of BGP Route Flap Damping. In this article I’d like to take a closer look at Route Flap Damping and see if there are other approaches to damping that may alleviate some aspects of BGP scaling pressure.

BGP Route Flap Damping

BGP Route Flap Damping (RFD) was first presented to the IETF BGP Working Group in October 1993, and documented as a Proposed Standard in November 1998 in RFC2439. BGP Route Flap Damping was seen as an effective approach to mitigating the effectives of link instability at the periphery of the network.

The motivation for this approach was the observation that many of the circuits used in the periphery of the network were analogue circuits over copper conductors, and such circuits often had a marginal failure mode where the circuit would be established, then lose synchronization, then re-establish itself, and so on. If such a circuit was carrying a BGP routing session then each time the circuit failed both ends of the circuit would effectively withdraw those routes that were being carried across the circuit. When the circuit was re-established, then the routes would be re-announced once more. An unstable circuit was capable of generating an endless sequence of withdrawals and announces. In itself this is perhaps a source of irritation rather than a major routing issue. However there is a second factor, namely that BGP supports a flat routing space, and routing announcements and withdrawals are propagated as far as possible across the entire routing space. If an address prefix was being announced from behind an unstable circuit, and generating a routing update once a second, then the total update load imposed on the network is in effect the number BGP speakers in the entire network processing an update every second. As the network grows in size, then the total load imposed by such unstable circuits also grows in size, and, presumably, the number of unstable circuits would also grow in size, and the processing-based scaling properties of the routing system becomes a source of significant concern.

The objective of the RFD technique is to reduce the BGP processing load through the selective suppression of BGP updates that are considered to be reflective of persistent unstable network states. The concern that was being addressed in this approach was that a “BGP implementation may tend to fail due to high routing update volume.” [RFC2439] This was seen as a cause of peer session failure, thereby further adding to the processing load imposed on other routers which “may cause failures in other instances of the same implementation or other implementations with a similar weakness.” [RFC2439]

The general concept was that each time an address prefix was announced or withdrawn by a BGP peer a penalty score was applied to the prefix. If the penalty score then exceeded the damping threshold then this BGP peers’ prefix advertisement was “damped” and not considered for selection as a local best path. While damped, further announcements or withdrawals of this prefix by the BGP peer continue to incur additional penalty scores. This penalty score decays over time using an exponential decay model, and when the penalty score decays below a re-announcement threshold, the prefix and associated path is once more considered as a candidate prefix for selection as a local best path.

The original intent of route flap damping was to damp down the effect of rapid routing oscillations by damping the noisy prefix for an extended period of time (between 30 minutes and 1 hour in a typical flap damping configuration), and the major anticipated benefit was to reduce the BGP update load on routers and mitigate the issue of router crashes.

It’s a fine theory, but in practice over the past decade of scaling BGP, RFD has been largely ineffectual!

What Causes Route Instability?

Subsequent investigation of the dynamic characteristics of BGP has revealed that many of the route flap behaviours that could trigger a flap damping response were not generally caused by sustained link instability, or by any other persistent operational abnormality in the network’s circuitry.

In the majority of cases it appears that the update sequences that trigger flap damping are the outcome of entirely normal operation of BGP. A route withdrawal causes a distance vector protocol like BGP to embark on a “path hunt” where the withdrawal will trigger a number of successive updates until either a stable path is found or the prefix is withdrawn (Fig 1).

This path hunt behaviour is exacerbated by variance in the Minimum Route Advertisement Interval (MRAI) Timer (the amount of time a BGP speaker will wait before passing on successive route updates for the same prefix) across various BGP implementations. This variance in timers causes withdrawals and updates to pass through different network paths at different speeds, generating a number of transient intermediate routing states until the routing state ultimately converges.

In RFD the successive updates associated with these intermediate state transitions each incur a flap damping penalty, so that a single initial event can generate an update sequence that can cause a route to the damped for an hour or more.

In the operational community RFD was seen as a measure that did little to remove potential harmful routing pathologies from the network, while at the same time RFD was a seen as a source of disruption to overall reachability in the network. Current operational notes on RFD discourage its use in large scale production networks that support the public Internet [RIPE-378].


Fig 1 – BGP Path Hunting

BGP and Route Update Processing

Is turning off RFD harmful? What has changed in the past decade or more that alters the picture of BGP route updates and the impact of intense update load on routers?

A naive model of a BGP speaker is as an input queue of pending updates that have been received from a BGP peer that are yet to be processed, a BGP processor, and an output queue of updates that are to be sent to a BGP peer that reflect changes in the local best path state (Fig 2).


Fig 2 – BGP Processing Model

The concern that appeared to motivate the desire for RFD was that if a BGP speaker has many peers, then the input queues could grow at a faster rate than the local BGP processor could process them. For example, assuming that the BGP speakers all take the same amount of time to process a single update request, then a BGP speaker with three peers, all of whom are generating updates at their maximal processing rate, will receive an input stream of updates that represent a processing load three times the maximal processing rate for the local BGP instance, and queue buildup will be an inevitable outcome.

In such a model all updates on the input queue have already been acknowledged by the underlying BGP TCP transport protocol, so that if the local processor drops the update message prior to processing it, then the local routing state will have fallen out of synch with the BGP peer’s routing state, and there is the distinct possibility of loop formation or black hole routing in the network’s routing state. The implication is that with finite memory available for queues within the BGP engine, a high update rate causes the potential for loss of routing information.

This naïve model of BGP behaviour is not one that is in general use. A more commonly implemented approach is to effectively remove the input queue from the BGP model and couple the TCP transport state with the local processing rate, such that the BGP processor throttles the TCP session to prevent input queue buildup, thereby applying back pressure to the BGP peer holding the output queue. Normally this would just shift the problem of queue buildup and memory use pressure back to the BGP peer. However, the BGP peer may also apply update compression to its local output queue. This update compression can be seen as a queue management regime that removes preceding queued updates that refer to the same prefix as that being enqueued, so that at any point in time any given prefix occurs in the output queue at most once [Fig 3].


Fig 3 – TCP Rate-Controlled input to BGP

These measures can combine to significantly improve the dynamic behaviour of BGP under load. By coupling the transport flow control to the BGP processor throughput the local buildup of acknowledged but unprocessed updates, and the associated risk of queue drop through memory exhaustion, is avoided, and by performing output queue compression redundant BGP updates are removed before they are transmitted.

Within such an implementation model of BGP the precise nature of the underlying problem that RFD was intended to address becomes somewhat harder to define. As the BGP update rate increases local BGP speakers apply back pressure to their peers to slow the incoming update rate to match the local processing capability, avoiding local dropping of updates due to memory exhaustion. As the back pressure increases BGP speakers build up their output queues, at which point highly active prefixes trigger output queue compression.

This appears to further reinforce the perspective that BGP Route Flap Damping is of marginal value, and the extended outages triggered by a prefix damping event are more of a burden to the integrity of the network than the problem that flap damping was intended to alleviate.

Route Update Profile

So if the BGP problem space is shifting, then what is it shifting to? What do route updates look like these days? A recent study looked at the BGP updates over the month of April 2007 based on an observation point adjacent to AS 4637.

During that month a single eBGP peering session received 1,341,520 BGP update messages, reflecting 3,523,906 individual prefix updates and 627,538 individual prefix withdrawals. Considering that there were an average of some 215,000 individual prefixes in the BGP routing table across the month, that’s an average of around 19 updates for every prefix in the month, assuming a uniform distribution of updates across the entire routing domain.

Of course, the distribution of updates is not uniform, and most of the network is highly stable. Half of these 210,000 prefixes had less than 10 routing updates across the month, and only 20,000 prefixes had more than 40 updates for the month. In other words, this is a very skewed distribution, with 10% of announced prefixes being responsible for 53% of all routing updates, and the busiest 1% of prefixes responsible for 24% of the routing updates for the month [Fig4]


Figure 4 – Update Distribution

On the face of it, this represents a pretty compelling argument for some form of selective route damping. It can’t be the case that more than a million routing updates actually reflect true underlying changes in topology of the network, given that these one million updates only refer to 2,000 prefixes. It would certainly be intuitive to guess that the overall majority of these routing updates represent intermediate routing states that are heading towards converged routing outcomes. Perhaps a deeper inspection of what is behind these busy prefixes is called for in order to understand what form of route flap damping would be effective here.

So what is the “typical” profile of BGP updates? Well “typical” is a tough question, but here I’d like to report on the profile of what happened in April 2007, BGP Update-wise, in my corner of the network.

The first step is to look at what kinds of updates one can expect from a single peer in BGP. The following table classifies the types of BGP updates of interest here.

Code	Description
AA+	Announcement of an already announced prefix with a longer AS Path (update to longer path)
AA-	Announcement of an announced prefix with a shorter AS Path (update to shorter path)
AA0	Announcement of an announced prefix with a different path of the same length (update to a different AS Path of same length)
AA*	Announcement of an announced prefix with the same path but different attributes (update of attributes)
AA	Announcement of an announced prefix with no change in path or attributes (possible BGP error or data collection error)
WA+	Announcement of a withdrawn prefix, with longer AS Path
WA-	Announcement of a withdrawn prefix, with shorter AS Path
WA0	Announcement of a withdrawn prefix, with different AS Path of the same length
WA*	Announcement of a withdrawn prefix with the same AS Path, but different attributes
WA	Announcement of a withdrawn prefix with the same AS Path and same attributes
AW	Withdrawal of an announced prefix
WW	Withdrawal of a withdrawn prefix (possible BGP error or a data collection error)

So what did BGP look like for the April 2007 data? The following table classifies all the updates according to this taxonomy.

Code	Count
AA+	607,093
AA-	555,609
AA0	594,029
AA*	782,404
AA	195,707
WA+	238,141
WA-	190,328
WA0	51,780
WA*	30,797
WA	77,440
AW	627,538
WW	0

The interesting numbers here are those associated with BGP path hunting following a withdrawal, which are likely to be associated with the 607,093 AA+ updates and the 627,538 AW updates. But the population of these update types alone is not enough on its own to justify a conclusion that over 1.2 million updates are associated with path hunting as a precursor to prefix withdrawal events. The other salient factor that needs to be examined is the time distribution of updates, as the path hunting condition is associated with a rapid burst of updates.

In looking at the time distribution of updates for the same prefix, ([Fig-5], [Fig-6] and [Fig-7]) there are some prominent peaks. The operation of the 30 second MRAI timer appears to be very prominent, and 934,391 updates occurred precisely 30 seconds after the previous update for the same prefix, and a total 1,636,093 updates for the same prefix occurred within 31 seconds of the previous update. That’s the equivalent to 39% of the entire BGP update activity for the month. There are further local peaks at 30 second intervals at 60, 90 and all the way through to 240 seconds. Almost half of the BGP update activity occurs in a closely coupled manner [Fig-5].

There are also smaller local peaks at 30 minute and 1 hour intervals [Fig-6]. It is likely that these correspond to Route Flap Damping outcomes, where the damping period is typically one of these two values. Interestingly, there are also local peaks at 1, 2 and 3 day intervals [Fig-7]. This is unlikely to be an artefact of Route Flap Damping, and is more likely to be the outcome of some form of time-managed traffic system that performs routing changes on a regular 24 hour basis.


Fig 5 – Time Distribution of Updates (Seconds)


Fig 6 – Time Distribution of Updates (Minutes)


Fig 7 – Time Distribution of Updates (Hours)

Another way of looking at this time distribution of updates is to construct update “sequences” where a pair of updates is considered to be part of the same sequence if it refers to the same prefix and is received within 65 seconds (or slightly longer than two MRAI Timer intervals) of any previous update for the same prefix. Only 28% of the updates for the month are not part of any sequence, while 26% of updates are part of a coupled update pair, and 46% of updates are part of sequences of 3 or more updates. Interestingly enough, changing the timer as to what defines a sequence does not alter the profile greatly. Extending the sequence timer to 125 seconds (or four MRAI Timer intervals) produces the outcome that 54% of updates are part of sequences of 3 or more updates, while reducing the sequence timer to 35 seconds produces the outcome that 36% of all updates are part of sequences of 3 or more updates [Fig-8].


Fig 8 – Update Sequence Length Distribution (using 35 second interval timer)

Update Damping

The approaches to flap damping to date have tended to look at flap damping as a persistent condition that lasts for hours or longer, and are an outcome of a strongly persistent announcement and withdrawal characteristics that are assumed to be associated with some form of cyclical behaviour of an underlying circuit. This now appears to be well wide of the mark in terms of capturing the profile of what appears to be redundant BGP updates that reflect transitory routing states that are not in any converged state.

The question this prompts is whether there is any value in looking at BGP update patterns in the micro view rather than the macro? Can we identify, on the fly, update sequences that are highly likely to correlate to the BGP behaviour of path hunting to a withdrawal and damp the intermediate path hunting states and simply propagate the resultant converged state? This was part of the intent of the MRAI timer, but rather than simply apply a uniform damping interval to update propagation, can we devise a selective algorithm that attempt to pinpoint routing transitions that are strongly associated with BGP path hunting?

There are a number of observations here that appear to point to some value in considering this approach:

• A BGP update generator may perform "update compression” by removing an already queued update when a further update that refers to the same prefix is generated. Thus, when using the MRAI timer, only the most recent state for each prefix is passed to the BGP peers, and any intermediate state that occurred during the MRAI-imposed quiescent time is suppressed.

• Convergence in BGP appears to take longer than a single MRAI timer interval. As noted in the sequencing profile for updates, some 36% of all sequences take more than two MRAI timer intervals, or more than 60 seconds, to complete.

• Path hunting in BGP is commonly represented as an update sequence of the form {AA+}* AW, i.e. a sequence of lengthening AS path lengths followed by a withdrawal.

• Suppression of updates that lengthen the AS Path length of a prefix does not implicitly create any risks of routing loop formation during the suppression period. If the peer had already selected a different path as the best path, then the update to a longer path would have no impact on the previous selection. If the peer was using the path advertised by this BGP speaker as its best path, then the suppression may cause the peer to continue to use this out-of-date path, but would not cause a path loop, as if the peer was listed on the longer path then the peer would already have a shorter path, and this update would not alter the peer’s forwarding state.

So the profile of update sequences that appear to be effective targets for some form of local suppression are those that lengthen the AS Path, and possibly also those updates that do not change the AS Path Length, and are also part of a sequence of time-clustered updates for the same prefix.

One approach to Update Damping is to delay the processing an update if the update represents a lengthening of the AS Path for an already announced prefix, selecting the AA+ updates. Furthermore, the updates that are of interest here are those that occur during BGP path hunting, so the length of time of the suppression should not be minutes or hours, but slightly over one MRAI time interval, or 35 seconds. If no further updates for this prefix are generated in this suppression interval, then the update is processed at the end of the suppression time, otherwise the suppressed update is replaced by its successor update.

How effective would this form of Update Damping be in the context of the BGP Update data set we’ve been examining here?

The algorithm used to implement this damping response is to suppress the processing all AA+ updates by up to 35 seconds. If a further update for this prefix occurs during this suppression interval, then the suppressed update is ignored and the successor update is processed in stead. If this update represents a further lengthening of the AS Path then it, too, is suppressed for 35 seconds. There are 607,093 AA+ updates in this set of suppressed updates, or some 15% of the total update load for the month. Update Damping would result in not processing 371,943 updates, or some 9.5% of the total update load. This result also indicates that 61% of all AA+ updates are followed by a subsequent update for the same prefix within one MRAI time interval.

Decreasing the sensitivity of the suppression parameters to a little over 2 MRAI intervals, or 65 seconds, increases the number of unprocessed updates to 418,805, or an additional 1%, so it appears that a damping sensitivity of a single MRAI interval represents a suitable point of compromise between maximising the number of damped BGP events without making the BGP convergence process significantly slower.

Of these damped updates, how many are actually path hunt updates? Some 96,135 of these damped updates are immediately followed by a withdrawal within the 35 second suppression period, and a further 36,691 damped updates are followed by another suppressed AA+ update.

This approach could be extended in a number of directions. One approach is to regard any update that does not reduce the AS Path length or withdraw the prefix as being a candidate for update damping. In this case some 845,290 updates would be damped or 21% of all updates. Of these update just under one quarter, or 208,007 of these damped updates are followed by a withdrawal within one MRAI interval, and a further 474,234 of these damped updates are followed by an update with an AS path of the same or greater length. The implication being that update damping removes around one fifth of the total BGP update volume without reducing the time to convergence for route withdrawal, nor the time for propagation of more preferred routing paths.

Using this latter form of Update Damping, over the month the average prefix update rate per second falls from 1.60 prefix updates per second to 1.22 prefix updates per second [Fig-9], with 0.38 damped updates per second on average [Fig-10].


Fig 9 – Average Updates per second – Difference between undamped and damped


Fig 10 – Average Damped Updates per second

The average peak update rate per hour falls from 355 to 290 prefix updates per second using Update Damping [Fig-11], an average reduction of 65 updates per second on the hourly peaks [Fig-12].


Fig11 – Hourly Peak Updates per second – Difference between undamped and damped


Fig 12 – Hourly Peak Damped Updates per second

Some Observations

Of course this is not the first, and will by no means be the last, suggestion on how to make marginal improvements in BGP. However, it’s the process that lies behind making this suggestion is the major topic of interest here, where the steps are to gather relevant data, examine the data for properties, patterns and relationships, and then test various hypotheses about how these patterns may be exploited by testing the data. If it still looks plausible then the subsequent exercise is about gathering more data, performing more analysis, simulations and then possibly undertaking some experimentation.

On a more general note, this work highlights an important aspect of BGP behaviour. The original assumption with the deployment of BGP was that external events exacerbated potential problems in the routing protocol, and the most extreme was persistent instability in the network that caused continual load to be imposed on the routing system. Route Flap Damping was a response to alter the behaviour of BGP to cope with pathologically broken network conditions. Further experience with BGP now reveals a somewhat different picture, where it is the operation of the protocol itself that causes relatively simple single root cause events to be amplified into extended event sequences across the entire network. This is a by-product of the very nature of BGP as a distance vector protocol, and is further amplified by the divergence in propagation times of events across the network due to the differences in processing capability, bandwidth, relative load and differences in the implementation of MRAI timers across various BGP implementations.

What it tends to suggest is that one of the most productive efforts to reduce the processing loads associated with BGP are efforts directed at attempting to protect BGP from the worst aspects of its own behaviour!

Disclaimer

The above views do not necessarily represent the views of the Asia Pacific Network Information Centre.

About the Author

GEOFF HUSTON holds a B.Sc. and a M.Sc. from the Australian National University. He has been closely involved with the development of the Internet for many years, particularly within Australia, where he was responsible for the initial build of the Internet within the Australian academic and research sector. He is author of a number of Internet-related books, and is currently the Chief Scientist at APNIC, the Regional Internet Registry serving the Asia Pacific region. He was a member of the Internet Architecture Board from 1999 until 2005, and served on the Board of the Internet Society from 1992 until 2001.

www.potaroo.net