Neighbor-specific BGP: More flexible routing policies while improving global stability

Yi Wang, Michael Schapira, Jennifer L. Rexford

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

25 Scopus citations

Abstract

The Border Gateway Protocol (BGP) offers network administrators considerable flexibility in controlling how traffic flows through their networks. However, the interaction between routing policies in different Autonomous Systems (ASes) can lead to protocol oscillation. The best-known sufficient conditions of BGP global routing stability impose restrictions on the kinds of local routing policies individual ASes can safely implement. In this paper, we present neighbor-specific BGP (NS-BGP), a modest extension to BGP that enables a much wider range of local policies without compromising global stability. Whereas a conventional BGP-speaking router selects a single "best" route (for each destination prefix), NS-BGP allows a router to customize the route selection on behalf of each neighbor. For example, one neighbor may prefer the shortest route, another the most secure route, and yet another the least expensive route. Surprisingly, we prove that the much more flexible NS-BGP is guaranteed to be stable under much less restrictive conditions on how routers "rank" the candidate routes. We also show that it is safe to deploy NS-BGP incrementally, as a routing system with a partial deployment of NS-BGP is guaranteed to be stable, even in the presence of failure and other topology changes. In addition to our theoretical results, we also describe how NS-BGP can be deployed by individual ASes independently without changes to the BGP message format or collaboration from neighboring ASes.

Original languageEnglish (US)
Title of host publicationSIGMETRICS/Performance'09 - Proceedings of the 11th International Joint Conference on Measurement and Modeling of Computer Systems
Pages217-228
Number of pages12
Edition1
DOIs
StatePublished - Nov 23 2009
Event11th International Joint Conference on Measurement and Modeling of Computer Systems, SIGMETRICS/Performance'09 - Seattle, WA, United States
Duration: Jun 15 2009Jun 19 2009

Publication series

NameSIGMETRICS/Performance'09 - Proceedings of the 11th International Joint Conference on Measurement and Modeling of Computer Systems
Number1
Volume37

Other

Other11th International Joint Conference on Measurement and Modeling of Computer Systems, SIGMETRICS/Performance'09
CountryUnited States
CitySeattle, WA
Period6/15/096/19/09

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Hardware and Architecture

Keywords

  • Algorithm
  • C.2.2 [computer-communication networks]: Network protocols
  • Design
  • Theory

Fingerprint Dive into the research topics of 'Neighbor-specific BGP: More flexible routing policies while improving global stability'. Together they form a unique fingerprint.

  • Cite this

    Wang, Y., Schapira, M., & Rexford, J. L. (2009). Neighbor-specific BGP: More flexible routing policies while improving global stability. In SIGMETRICS/Performance'09 - Proceedings of the 11th International Joint Conference on Measurement and Modeling of Computer Systems (1 ed., pp. 217-228). [1555375] (SIGMETRICS/Performance'09 - Proceedings of the 11th International Joint Conference on Measurement and Modeling of Computer Systems; Vol. 37, No. 1). https://doi.org/10.1145/1555349.1555375