An Empirical Characterization of Anycast Convergence Time
Authors: 
Bernhard Degen, Mattijs Jonker, 
Roland van Rijswijk-Deij, Raffaele SommeseAuthors Info & Claims
Pages 23 - 30
Abstract
BGP convergence time is an important aspect of Internet operations and research alike. As an example, traffic steering during DDoS attacks necessitates swift topological changes. Problems surrounding delayed convergence are widely documented. However, little is known about real-world convergence times, especially in an anycast setting. This leads many BGP measurement studies to coarsely estimate the convergence time. In this work, we study BGP convergence using a global anycast testbed. The methodology we present combines two probing methods to measure routing stability from an end-user perspective. We find that 80% of the Internet converges within approximately 10 seconds but also that there is a long tail of networks that are slow to update.
References
[1]
Ruwaifa Anwar, Haseeb Niaz, David Choffnes, Ítalo Cunha, Phillipa Gill, and Ethan Katz-Bassett. 2015. Investigating Interdomain Routing Policies in the Wild. In Proceedings of the 2015 Internet Measurement Conference (IMC '15). Association for Computing Machinery, New York, NY, USA, 71--77. https://doi.org/10.1145/2815675.2815712
[2]
Leandro M. Bertholdo, Sandro L. A. Ferreira, João M. Ceron, Lisandro Zambenedetti Granville, Ralph Holz, and Roland van Rijswijk-Deij. 2022. On the Asymmetry of Internet eXchange Points -Why Should IXPs and CDNs Care?. In 2022 18th International Conference on Network and Service Management (CNSM). IEEE, Thessaloniki, Greece, 73--81. https://doi.org/10.23919/CNSM55787.2022.9964817
[3]
Henry Birge-Lee, Yixin Sun, Anne Edmundson, Jennifer Rexford, and Prateek Mittal. 2018. Bamboozling Certificate Authorities with BGP. In 27th USENIX Security Symposium (USENIX Security 18). USENIX, Baltimore, MD, USA, 833--849.
[4]
Center for Applied Internet Data Analysis (CAIDA). 2006. Archipelago (Ark) Measurement Infrastructure. https://www.caida.org/projects/ark/.
[5]
Ricardo Bennesby da Silva and Edjard Souza Mota. 2017. A Survey on Approaches to Reduce BGP Interdomain Routing Convergence Delay on the Internet. IEEE Communications Surveys & Tutorials 19, 4 (2017), 2949--2984. https://doi.org/10.1109/COMST.2017.2722380
[6]
Wouter B. de Vries, Ricardo de O. Schmidt, Wes Hardaker, John Heidemann, Pieter-Tjerk de Boer, and Aiko Pras. 2017. Broad and Load-Aware Anycast Mapping with Verfploeter. In Proceedings of the 2017 Internet Measurement Conference (IMC '17). Association for Computing Machinery, New York, NY, USA, 477--488. https://doi.org/10.1145/3131365.3131371
[7]
Bernhard Degen, Mattijs Jonker, Roland van Rijswijk-Deij, and Raffaele Sommese. 2024. An Empirical Characterization of Anycast Convergence Time. https://doi.org/10.5281/zenodo.11617187
[8]
J. Durand, I. Pepelnjak, and G. Doering. 2015. BGP Operations and Security. RFC 7454. IETF.
[9]
Emile Aben. 2014. Propagation of Longer-than-/24 IPv4 Prefixes. https://labs.ripe.net/author/emileaben/propagation-of-longer-than-24-ipv4-prefixes/.
[10]
Alex Fabrikant, Umar Syed, and Jennifer Rexford. 2011. There's Something about MRAI: Timing Diversity Can Exponentially Worsen BGP Convergence. In 2011 Proceedings IEEE INFOCOM. IEEE, Shanghai, China, 2975--2983. https://doi.org/10.1109/INFCOM.2011.5935139
[11]
Xun Fan and John Heidemann. 2010. Selecting Representative IP Addresses for Internet Topology Studies. In Proceedings of the 10th ACM SIGCOMM Conference on Internet Measurement (IMC '10). Association for Computing Machinery, New York, NY, USA, 411--423. https://doi.org/10.1145/1879141.1879195
[12]
Osvaldo Fonseca, Ítalo Cunha, Elverton Fazzion, Wagner Meira, Brivaldo Alves da Silva, Ronaldo A. Ferreira, and Ethan Katz-Bassett. 2021. Identifying Networks Vulnerable to IP Spoofing. IEEE Transactions on Network and Service Management 18, 3 (Sept. 2021), 3170--3183. https://doi.org/10.1109/TNSM.2021.3061486
[13]
Alberto García-Martínez and Marcelo Bagnulo. 2019. Measuring BGP Route Propagation Times. IEEE Communications Letters 23, 12 (Dec. 2019), 2432--2436. https://doi.org/10.1109/LCOMM.2019.2945964
[14]
Caitlin Gray, Clemens Mosig, Randy Bush, Cristel Pelsser, Matthew Roughan, Thomas C. Schmidt, and Matthias Wahlisch. 2020. BGP Beacons, Network Tomography, and Bayesian Computation to Locate Route Flap Damping. In Proceedings of the ACM Internet Measurement Conference (IMC '20). Association for Computing Machinery, New York, NY, USA, 492--505. https://doi.org/10.1145/3419394.3423624
[15]
Enrico Gregori, Alessandro Improta, Luciano Lenzini, Lorenzo Rossi, and Luca Sani. 2012. On the Incompleteness of the AS-level Graph: A Novel Methodology for BGP Route Collector Placement. In Proceedings of the 2012 Internet Measurement Conference (IMC '12). Association for Computing Machinery, New York, NY, USA, 253--264. https://doi.org/10.1145/2398776.2398803
[16]
Craig Labovitz, Abha Ahuja, Abhijit Bose, and Farnam Jahanian. 2000. Delayed Internet Routing Convergence. In Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM '00). Association for Computing Machinery, New York, NY, USA, 175--187. https://doi.org/10.1145/347059.347428
[17]
Zhuoqing Morley Mao, Ramesh Govindan, George Varghese, and Randy H. Katz. 2002. Route Flap Damping Exacerbates Internet Routing Convergence. In Proceedings of the 2002 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM '02). Association for Computing Machinery, New York, NY, USA, 221--233. https://doi.org/10.1145/633025.633047
[18]
Y. Rekhter, T. Li, and S. Hares. 2006. A Border Gateway Protocol 4 (BGP-4). RFC 4271. IETF.
[19]
RIPE Network Coordination Center. 2024. Routing Information Service (RIS). https://www.ripe.net/analyse/internet-measurements/routing-information-service-ris/.
[20]
A. S. M. Rizvi, Leandro Bertholdo, João Ceron, and John Heidemann. 2022. Anycast Agility: Network Playbooks to Fight DDoS. In 31st USENIX Security Symposium (USENIX Security 22). USENIX, Boston, MA, USA, 4201--4218.
[21]
RouteViews project. 2024. University of Oregon RouteViews Project. https://www.routeviews.org/routeviews/.
[22]
Jared M. Smith, Kyle Birkeland, Tyler McDaniel, and Max Schuchard. 2020. Withdrawing the BGP Re-Routing Curtain: Understanding the Security Impact of BGP Poisoning through Real-World Measurements. In Proceedings 2020 Network and Distributed System Security Symposium. Internet Society, San Diego, CA, USA. https://doi.org/10.14722/ndss.2020.24240
[23]
Raffaele Sommese, Gautam Akiwate, Mattijs Jonker, Giovane CM Moura, Marco Davids, Roland van Rijswijk-Deij, Geoffrey M. Voelker, Stefan Savage, K. C. Claffy, and Anna Sperotto. 2021. Characterization of Anycast Adoption in the DNS Authoritative Infrastructure. In Proceedings of the 2021 Network Traffic Measurement and Analysis Conference (TMA '21). IFIP, Virtual event.
[24]
Florian Streibelt, Franziska Lichtblau, Robert Beverly, Anja Feldmann, Cristel Pelsser, Georgios Smaragdakis, and Randy Bush. 2018. BGP Communities: Even More Worms in the Routing Can. In Proceedings of the Internet Measurement Conference 2018 (IMC '18). Association for Computing Machinery, New York, NY, USA, 279--292. https://doi.org/10.1145/3278532.3278557
[25]
C. Villamizar, R. Chandra, and R. Govindan. 1998. BGP Route Flap Damping. RFC 2439. IETF.
[26]
Gerry Wan, Liz Izhikevich, David Adrian, Katsunari Yoshioka, Ralph Holz, Christian Rossow, and Zakir Durumeric. 2020. On the Origin of Scanning: The Impact of Location on Internet-Wide Scans. In Proceedings of the ACM Internet Measurement Conference (IMC '20). Association for Computing Machinery, New York, NY, USA, 662--679. https://doi.org/10.1145/3419394.3424214
[27]
Feng Wang, Zhuoqing Morley Mao, Jia Wang, Lixin Gao, and Randy Bush. 2006. A Measurement Study on the Impact of Routing Events on End-to-End Internet Path Performance. In Proceedings of the 2006 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM '06). Association for Computing Machinery, New York, NY, USA, 375--386. https://doi.org/10.1145/1159913.1159956
[28]
Xiao Zhang, Tanmoy Sen, Zheyuan Zhang, Tim April, Balakrishnan Chandrasekaran, David Choffnes, Bruce M. Maggs, Haiying Shen, Ramesh K. Sitaraman, and Xiaowei Yang. 2021. AnyOpt: Predicting and Optimizing IP Anycast Performance. In Proceedings of the 2021 ACM SIGCOMM 2021 Conference (SIGCOMM '21). Association for Computing Machinery, New York, NY, USA, 447--462. https://doi.org/10.1145/3452296.3472935
Recommendations
Non-asymptotic superlinear convergence of standard quasi-Newton methods
AbstractIn this paper, we study and prove the non-asymptotic superlinear convergence rate of the Broyden class of quasi-Newton algorithms which includes the Davidon–Fletcher–Powell (DFP) method and the Broyden–Fletcher–Goldfarb–Shanno (BFGS) method. The ...
Epi-convergence: The Moreau Envelope and Generalized Linear-Quadratic Functions
This work explores the class of generalized linear-quadratic functions, constructed using maximally monotone symmetric linear relations. Calculus rules and properties of the Moreau envelope for this class of functions are developed. In finite dimensions,...
On the semilocal convergence of inexact Newton methods in Banach spaces
We provide two types of semilocal convergence theorems for approximating a solution of an equation in a Banach space setting using an inexact Newton method [I.K. Argyros, Relation between forcing sequences and inexact Newton iterates in Banach spaces, ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2024
110 pages
ISBN:9798400707230
DOI:10.1145/3673422
Copyright © 2024 Owner/Author.
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
- Internet Society: Internet Society
- SIGCOMM: ACM Special Interest Group on Data Communication
In-Cooperation
- IRTF: Internet Research Task Force
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 20 July 2024
Check for updates
Qualifiers
- Short-paper
- Research
- Refereed limited
Conference
ANRW '24
Sponsor:
- Internet Society
- SIGCOMM
Acceptance Rates
Overall Acceptance Rate 34 of 58 submissions, 59%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 97Total Downloads
- Downloads (Last 12 months)97
- Downloads (Last 6 weeks)24
Reflects downloads up to 18 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in