research-article

Revisiting BGP churn growth

Authors:

Ahmed Elmokashfi,

Amogh DhamdhereAuthors Info & Claims

ACM SIGCOMM Computer Communication Review, Volume 44, Issue 1

Pages 5 - 12

https://doi.org/10.1145/2567561.2567563

Published: 31 December 2013 Publication History

Abstract

In the mid 2000s there was some concern in the research and operational communities over the scalability of BGP, the Internet's interdomain routing protocol. The focus was on update churn (the number of routing protocol messages that are exchanged when the network undergoes routing changes) and whether churn was growing too fast for routers to handle. Recent work somewhat allayed those fears, showing that update churn grows slowly in IPv4, but the question of routing scalability has re-emerged with IPv6.

In this work, we develop a model that expresses BGP churn in terms of four measurable properties of the routing system. We show why the number of updates normalized by the size of the topology is constant, and why routing dynamics are qualitatively similar in IPv4 and IPv6. We also show that the exponential growth of IPv6 churn is entirely expected, as the underlying IPv6 topology is also growing exponentially.

References

[1]

S. Agarwal, C.-N. Chuah, S. Bhattacharyya, and C. Diot. Impact of BGP Dynamics on Router CPU Utilization. In Proc. Passive and Active Measurement Conference, 2004.

[2]

A. Broido and k. claffy. Analysis of RouteViews BGP data: policy atoms. In Network Resource Data Management Workshop, Santa Barbara, CA, May 2001.

[3]

L. Cittadini, W. Muhlbauer, S. Uhlig, R. Bush, P. Francois, and O. Maennel. Evolution of Internet address space deaggregation: Myths and reality. IEEE Journal on Selected Areas in Communications, 28(8), 2010.

Digital Library

[4]

A. Dhamdhere and C. Dovrolis. Twelve years in the evolution of the Internet ecosystem. IEEE/ACM Transactions on Networking, 19(5), Oct. 2011.

Digital Library

[5]

A. Dhamdhere, M. Luckie, B. Huffaker, A. Elmokashfi, E. Aben, and K. Claffy. Measuring the Deployment of IPv6: Topology, Routing and Performance. In Proc. of ACM SIGCOMM IMC, Nov 2012.

Digital Library

[6]

A. Elmokashfi, A. Kvalbein, and C. Dovrolis. On the Scalability of BGP: the roles of topology growth and update rate-limiting. In Proc. ACM CoNEXT, Dec 2008.

Digital Library

[7]

A. Elmokashfi, A. Kvalbein, and C. Dovrolis. BGP churn evolution: A perspective from the core. IEEE/ACM Transactions on Networking, 20(2), April 2012.

Digital Library

[8]

T. Griffin and G. Wilfong. An Analysis of BGP Convergence Properties. In Proc. ACM SIGCOMM, 1999.

Digital Library

[9]

M. Hollander and D. A. Wolfe. Nonparametric statistical methods. Wiley, second edition, 1999.

[10]

G. Huston. The BGP instability report. http://bgpupdates.potaroo.net/.

[11]

G. Huston. BGP in 2009 (and a bit of 2010). Presentation at ARIN XXV meeting, 2010.

[12]

G. Huston. The BGP World is Flat, Nov. 2011. http://www.potaroo.net/ispcol/2011--12/flat.html.

[13]

G. Huston and G. Armitage. Projecting future IPv4 router requirements from trends in dynamic BGP behaviour. In Proc. ATNAC, Australia, Dec 2006.

[14]

C. Labovitz, A. Ahuja, A. Bose, and F. Jahanian. Delayed Internet Routing Convergence. IEEE/ACM Transactions on Networking, 9(3), June 2001.

Digital Library

[15]

C. Labovitz, G. R. Malan, and F. Jahanian. Origins of Internet routing instability. In Proc. IEEE INFOCOM, 1999.

[16]

J. Li, M. Guidero, Z. Wu, E. Purpus, and T. Ehrenkranz. BGP routing dynamics revisited. Computer Communications Review, apr 2007.

Digital Library

[17]

D. Meyer, L. Zhang, and K. Fall. Report from the IAB workshop on routing and addressing. RFC 4984, 2007.

[18]

R. Oliveira, R. Izhak-Ratzin, B. Zhang, and L. Zhang. Measurement of highly active prefixes in BGP. In Proc. IEEE GLOBECOMM, 2005.

[19]

R. Oliveira, B. Zhang, D. Pei, R. Izhak-Ratzin, and L. Zhang. Quantifying Path Exploration in the Internet. In Proc. ACM SIGCOMM IMC, 2006.

Digital Library

[20]

N. Valler, M. Butkiewicz, B. Prakash, and M. Faloutsos. Non-binary information propagation: Modeling BGP routing churn. In Proc. IEEE INFOCOM Compter Communications Workshop, 2011.

[21]

J. Wu, Z. M. Mao, J. Rexford, and J. Wang. Finding a needle in a haystack: pinpointing significant BGP routing changes in an IP network. In Proc. USENIX NSDI, 2005.

Digital Library

[22]

B. Zhang, V. Kambhampati, M. Lad, D. Massey, and L. Zhang. Identifying BGP routing table transfers. In Proc. ACM SIGCOMM workshop on Mining network data, 2005.

Digital Library

[23]

X. Zhao, D. Massey, M. Lad, and L. Zhang. On/Off Model: A New Tool to Understand BGP Update Burst. University of California, Los Angeles technical report, 2004.

[24]

X. Zhao, B. Zhang, D. Massey, A. Terzis, and L. Zhang. The impact of link failure location on routing dynamics: A formal analysis. In Proc. ACM SIGCOMM Asia Workshop, 2005.

Cited By

Del Fiore JPersico VMerindol PPelsser CPescape A(2021)The Art of Detecting Forwarding DetoursIEEE Transactions on Network and Service Management10.1109/TNSM.2021.306215118:3(3619-3632)Online publication date: Sep-2021
https://doi.org/10.1109/TNSM.2021.3062151
Demianiuk VKogan KNikolenko S(2021)Approximate Packet Classifiers With Controlled AccuracyIEEE/ACM Transactions on Networking10.1109/TNET.2021.305694829:3(1141-1154)Online publication date: Jun-2021
https://doi.org/10.1109/TNET.2021.3056948
Matcharashvili TPrangishvili A(2020)Quantifying regularity of the Internet Interdomain Routing based on Border Gateway Protocol (BGP) data bases2020 International Conference on Electrical, Communication, and Computer Engineering (ICECCE)10.1109/ICECCE49384.2020.9179264(1-5)Online publication date: Jun-2020
https://doi.org/10.1109/ICECCE49384.2020.9179264
Show More Cited By

Index Terms

Revisiting BGP churn growth
1. Networks
  1. Network protocols
    1. Network layer protocols
      1. Routing protocols

Recommendations

BGP routing dynamics revisited

Understanding BGP routing dynamics is critical to the solid growth and maintenance of the Internet routing infrastructure. However, while the most extensive study on BGP dynamics is nearly a decade old, many factors that could affect BGP dynamics have ...
BGP churn evolution: a perspective from the core

The scalability limitations of BGP have been a major concern lately. An important aspect of this issue is the rate of routing updates (churn) that BGP routers must process. This paper presents an analysis of the evolution of churn in four networks at ...
Neighbor-specific BGP: more flexible routing policies while improving global stability
SIGMETRICS '09

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGCOMM Computer Communication Review

ACM SIGCOMM Computer Communication Review Volume 44, Issue 1

January 2014

61 pages

ISSN:0146-4833

DOI:10.1145/2567561

Editors:
Konstantina Papagiannaki
Telefonica Research, Barcelona, Spain
,
Sharad Agarwal
Microsoft Research, USA
,
Katerina Argyraki
EPFL, Switzerland
,
Hitesh Ballani
Microsoft Research Cambridge, UK
,
Fabián Bustamante
Northwestern University, USA
,
Joseph Camp
SMU, USA
,
Augustin Chaintreau
Columbia University, USA
,
Nikolaos Laoutaris
Telefonica Research, Spain
,
Marco Mellia
Politecnico di Torino, Italy
,
Bhaskaran Raman
IIT Bombay, India
,
Renata Teixeira
LIP6, France
,
Jia Wang
AT&T Research, USA
,
Matteo Varvello
Bell Labs/Alcatel Lucent, Holmdel, NJ, USA

Issue’s Table of Contents

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or 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. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 December 2013

Published in SIGCOMM-CCR Volume 44, Issue 1

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
243
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)1

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Del Fiore JPersico VMerindol PPelsser CPescape A(2021)The Art of Detecting Forwarding DetoursIEEE Transactions on Network and Service Management10.1109/TNSM.2021.306215118:3(3619-3632)Online publication date: Sep-2021
https://doi.org/10.1109/TNSM.2021.3062151
Demianiuk VKogan KNikolenko S(2021)Approximate Packet Classifiers With Controlled AccuracyIEEE/ACM Transactions on Networking10.1109/TNET.2021.305694829:3(1141-1154)Online publication date: Jun-2021
https://doi.org/10.1109/TNET.2021.3056948
Matcharashvili TPrangishvili A(2020)Quantifying regularity of the Internet Interdomain Routing based on Border Gateway Protocol (BGP) data bases2020 International Conference on Electrical, Communication, and Computer Engineering (ICECCE)10.1109/ICECCE49384.2020.9179264(1-5)Online publication date: Jun-2020
https://doi.org/10.1109/ICECCE49384.2020.9179264
Matcharashvili TElmokashfi APrangishvili A(2020)Analysis of the regularity of the Internet Interdomain Routing dynamicsPhysica A: Statistical Mechanics and its Applications10.1016/j.physa.2020.124142(124142)Online publication date: Jan-2020
https://doi.org/10.1016/j.physa.2020.124142
Devikar RPatil DPrakash V(2020)A hybrid computing approach to improve convergence time for scalable networkSādhanā10.1007/s12046-020-01454-745:1Online publication date: 3-Sep-2020
https://doi.org/10.1007/s12046-020-01454-7
Németh FChiesa MRétvári GMohaisen AZhang Z(2019)Normal forms for match-action programsProceedings of the 15th International Conference on Emerging Networking Experiments And Technologies10.1145/3359989.3365417(44-50)Online publication date: 3-Dec-2019
https://dl.acm.org/doi/10.1145/3359989.3365417
Jia SLuckie MHuffaker BElmokashfi AAben EClaffy KDhamdhere A(2019)Tracking the Deployment of IPv6: Topology, Routing and PerformanceComputer Networks10.1016/j.comnet.2019.106947(106947)Online publication date: Oct-2019
https://doi.org/10.1016/j.comnet.2019.106947
Hauweele DQuoitin BPelsser CBush R(2018)What do parrots and BGP routers have in common?ACM SIGCOMM Computer Communication Review10.1145/3243157.324315946:3(1-6)Online publication date: 27-Jul-2018
https://dl.acm.org/doi/10.1145/3243157.3243159
Kitabatake TFontugne REsaki H(2018)BLT: A taxonomy and classification tool for mining BGP update messagesIEEE INFOCOM 2018 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)10.1109/INFCOMW.2018.8406955(409-414)Online publication date: Apr-2018
https://doi.org/10.1109/INFCOMW.2018.8406955
Zhang MLi JBrooks S(2017)I-SeismographIEEE/ACM Transactions on Networking10.1109/TNET.2017.274890225:6(3411-3426)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.1109/TNET.2017.2748902
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents