Reducing BGP Update Noise

Introduction

Our goal is to develop relatively simple, implementable mechanisms to significantly reduce the update-processing load of BGP speakers in the default-free zone of the Internet. We believe that such work could have a significant impact on the scalability prospects of BGP in coming years, particularly in light of the additional processing loads envisaged for deployment of secure BGP mechanisms. The project is currently in its second phase:

• The first phase has yielded the implementation and evaluation of Path Exploration Damping (PED) in Quagga, and has been documented in various Technical Reports and a paper published in the Journal of Selected Areas of Communications (JSAC), October 2010.


• In the second, current phase we are investigating whether its possible to define more complex Path Exploration patterns in order to improve the PED algorithm and to be able to suppress more unnecessary updates. We will also determine whether it is possible to automate the choice of the Path Exploration Damping Interval (PEDI) timer for each prefix, based on the update activity of each prefix.

Background

The underlying issues with scalability of the Internet’s inter-domain routing system and the Border Gateway Protocol (BGP) contain a number of persistent themes. 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.

Early efforts to reduce the routing update load focussed on the perception at the time that this was caused by an unstable edge link that caused a route object to 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 BGP was the introduction of Route Flap Damping. Subsequent investigation has revealed that this form of edge behaviour is relatively rare and current operational advice is to disable this damping response in BGP routers.

Subsequent efforts in attempting to mitigate the BGP Update load include use of the Minimum Route Advertisement Interval (MRAI) timer to enforce a minimum period of 30 seconds between successive BGP advertisements of the same route object to the same BGP peer. It has been noted that the heterogeneous deployment of this timer in commonly deployed BGP configurations has lead to some degree of amplification of prefix instability in certain cases and extended convergence time intervals. Another recent effort is combining TCP blocking with output queue compression, so that when the output queue builds up the BGP speaker ensures that only a single entry for each route object is in the queue. Enqueuing a new route object has a side effect of removing any previously queued update that refers to the same route object.

These measures are relatively general in scope, and appear to be still somewhat ineffectual in addressing overall growth in routing protocol update processing loads.

We propose to implement output queue compression in the public domain implementation of BGP, Quagga. We then propose to implement a modified MRAI implementation that includes heuristics that identify update sequences and perform selective suppression of BGP updates in those cases where the update sequence matches the heuristics of withdrawal-triggered path exploration, and where there appears to be a match of a path exploration to route that has strong local affinity.

As part of this project we will develop and release tools to assist in data gathering and analysis, and publish interim results and papers on our website. The links above will take you to additional information.

Project Leaders
Geoff Huston
Grenville Armitage

Project Members
Mattia Rossi

This project has been made possible in part by grants from the Cisco University Research Program Fund at Community Foundation Silicon Valley.