Guaranteeing BGP stability with a few extra paths

Rachit Agarwal, Virajith Jalaparti, Matthew Caesar, P. Brighten Godfrey

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Policy autonomy exercised by Autonomous Systems (ASes) on the Internet can result in persistent oscillations in Border Gateway Protocol, the Internet's inter-domain routing protocol. Current solutions either rely on globally consistent policy assignments, or require significant deviations from locally assigned policies, resulting in significant loss of autonomy of ASes. In this paper, we take a different approach that guarantees stability with less restrictive policies. Namely, we propose multipath routing to find a better trade-off between AS policy autonomy and system stability. We design an algorithm, STABLE PATH(S) ASSIGNMENT (SPA), that provably detects persistent oscillations and eliminates these oscillations by assigning multiple paths to some ASes in the network. Such an assignment allows each AS to use its most-preferred available path, while requiring very few ASes to carry transit traffic along additional paths in order to break oscillations. We design a distributed protocol for SPA and present tight bounds on the number of paths assigned to the ASes in the network. Using simulations on the AS graph, we show that in presence of oscillations, SPA assigns at most two paths to any AS in the network (in 99.9% of the instances), with an extremely small fraction of ASes assigned the extra path.

Original languageEnglish (US)
Title of host publicationICDCS 2010 - 2010 International Conference on Distributed Computing Systems
Number of pages10
StatePublished - 2010
Event30th IEEE International Conference on Distributed Computing Systems, ICDCS 2010 - Genova, Italy
Duration: Jun 21 2010Jun 25 2010

Publication series

NameProceedings - International Conference on Distributed Computing Systems


Other30th IEEE International Conference on Distributed Computing Systems, ICDCS 2010


  • Algorithms
  • Border gateway protocol
  • Internetworking
  • Routing

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Guaranteeing BGP stability with a few extra paths'. Together they form a unique fingerprint.

Cite this