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
