BGP Add-Paths : The Scaling/Performance Tradeoffs

Fri, 03/26/2010 - 11:54 by Virginie Van den Schrieck


Internet Service Providers design their network with resiliency in mind, having multiple paths towards external IP subnets available at the borders of their network. However, with the current internal Border Gateway Protocol, BGP routers and route reflectors only propagate their (unique) best path over their iBGP sessions. As a result, at the BGP router level, path diversity is poor. Such lack of path diversity can lead to MED oscillations, prevents an efficient use of multipath BGP and does not allow for a fast and local recovery upon nexthop failure. Advertising multiple paths over iBGP sessions with BGP Add-Paths solves those issues, depending on the way the additional paths are selected. In this paper, we analyze the various options for the selection mode of the paths to be advertised. We show that these modes differently fulfill the needs of Add-Paths applications such as fast recovery upon failure and MED oscillation avoidance, and at different costs. We also show in our analysis that the costs and benefits bound with these modes depend on the connectivity of the AS where it is deployed. To support the analysis, we developed a tool allowing to measure the scaling of these modes in a given network. We illustrate the utilization of this tool on synthetic Internet topologies, and provide some recommendations for the choice of an Add-Paths selection mode.

Virginie Van den Schrieck, Pierre Francois and Olivier Bonaventure
IEEE Journal on Selected Areas in Communications, 28(8):1299 - 1307, October 2010.
BGP, Path Diversity, Route Reflection, Routing, Routing oscillations, Routing protocols
Full text
pdf   (585.58 KB)
Cite it
See here

IEEE Copyright Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

ACM Copyright Notice: Copyright 1999 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page or intial screen of the document. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept., ACM Inc., fax +1 (212) 869-0481, or

Springer-Verlag LNCS Copyright Notice: The copyright of these contributions has been transferred to Springer-Verlag Berlin Heidelberg New York. The copyright transfer covers the exclusive right to reproduce and distribute the contribution, including reprints, translations, photographic reproductions, microform, electronic form (offline, online), or any other reproductions of similar nature. Online available from Springer-Verlag LNCS series.


add-paths-jsac.pdf585.58 KB