More Web Proxy on the site http://driver.im/

research-article

BGP Beacons, Network Tomography, and Bayesian Computation to Locate Route Flap Damping

Authors:

Cristel Pelsser,

Matthew Roughan,

Thomas C. Schmidt,

Matthias WahlischAuthors Info & Claims

IMC '20: Proceedings of the ACM Internet Measurement Conference

Pages 492 - 505

https://doi.org/10.1145/3419394.3423624

Published: 27 October 2020 Publication History

Abstract

Pinpointing autonomous systems which deploy specific inter-domain techniques such as Route Flap Damping (RFD) or Route Origin Validation (ROV) remains a challenge today. Previous approaches to detect per-AS behavior often relied on heuristics derived from passive and active measurements. Those heuristics, however, often lacked accuracy or imposed tight restrictions on the measurement methods.

We introduce an algorithmic framework for network tomography, BeCAUSe, which implements Bayesian Computation for Autonomous Systems. Using our original combination of active probing and stochastic simulation, we present the first study to expose the deployment of RFD. In contrast to the expectation of the Internet community, we find that at least 9% of measured ASs enable RFD, most using deprecated vendor default configuration parameters. To illustrate the power of computational Bayesian methods we compare BeCAUSe with three RFD heuristics. Thereafter we successfully apply a generalization of the Bayesian method to a second challenge, measuring deployment of ROV.

Supplementary Material

MP4 File (imc_final_both.mp4)

Presentation of the paper: "BGP Beacons, Network Tomography, and Bayesian Computation to Locate Route Flap Damping"

Download
129.87 MB

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 Proc. of ACM IMC. ACM, New York, NY, USA, 71--77.

Digital Library

[2]

P. Barford, N. Duffield, A. Ron, and J. Sommers. 2009. Network Performance Anomaly Detection and Localization. In Prof. of IEEE INFOCOM. IEEE Press, Piscataway, NJ, USA, 1377--1385.

[3]

A. Batsakis, T. Malik, and A. Terzis. 2005. Practical Passive Lossy Link Inference. In Proc. of PAM (LNCS, Vol. 3431). Springer-Verlag, Berlin, Heidelberg, 362--367.

[4]

Steve Brooks, Andrew Gelman, Galin Jones, and Xiao-Li Meng (Eds.). 2011. Handbook of Markov Chain Monte Carlo. CRC Press, Boca Raton, FL, USA.

[5]

Randy Bush, Cristel Pelsser, Mirjam Kuhne, Olaf Maennel, Pradosh Mohapatra, Keyur Patel, and Rob Evans. 2013. RIPE Routing Working Group Recommendations on Route Flap Damping. RIPE Document ripe-580. RIPE.

[6]

R. Cáceres, N.G. Duffield, J. Horowitz, and D. Towsley. 1999. Multicast-based inference of network-internal loss characteristics. IEEE Trans. in Information Theory 45, 7 (1999), 2462--2480.

Digital Library

[7]

Matthew Caesar, Lakshminarayanan Subramanian, and Randy H. Katz. 2003. Towards Localizing Root Causes of BGP Dynamics. Technical Report UCB/CSD-03-1292. EECS Department, University of California, Berkeley. http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/6364.html

[8]

Rui Castro, Mark Coates, Gang Liang, Robert Nowak, and Bin Yu. 2004. Network Tomography: Recent Developments. Statist. Sci. 19, 3 (2004), 499--517.

[9]

Di-Fa Chang, Ramesh Govindan, and John Heidemann. 2004. Locating BGP Missing Routes Using Multiple Perspectives. In Proc. of the ACM SIGCOMM Workshop on Network Troubleshooting: Research, Theory and Operations Practice Meet Malfunctioning Reality (NetT). ACM, New York, NY, USA, 301--306.

Digital Library

[10]

Shinyoung Cho, Rishab Nithyanand, Abbas Razaghpanah, and Phillipa Gill. 2017. A Churn for the Better: Localizing Censorship using Network-level Path Churn and Network Tomography. In Proc. of ACM CoNext. ACM, New York, NY, USA, 81--87.

Digital Library

[11]

Cloudflare. 2020. Is BGP safe yet? https://isbgpsafeyet.com/.

[12]

M. Coates and R. Nowak. 2000. Network loss inference using unicast end-to-end measurements. In Proc. of ITC Specialist Seminar on IP Traffic Measurement, Modeling and Managemen. Monterey, CA, 28-1-28-9. Preprint https://hdl.handle.net/1911/19810.

[13]

Simon Duane, A.D. Kennedy, Brian J. Pendleton, and Duncan Roweth. 1987. Hybrid Monte Carlo. Physics Letters B 195, 2 (1987), 216 - 222.

[14]

N. Duffield. 2006. Network Tomography of Binary Network Performance Characteristics. IEEE Transactions on Information Theory 52, 12 (2006), 5373--5388.

Digital Library

[15]

N.G. Duffield, J. Horowitz, F. Lo Presti, and D. Towsley. 2002. Multicast topology inference from measured end-to-end loss. IEEE Transactions in Information Theory 48, 1 (2002), 26--45.

Digital Library

[16]

N.G. Duffield, F. Lo Presti, V. Paxson, and D. Towsley. 2001. Inferring link loss using striped unicast probes. In Proc. of IEEE Infocom. IEEE Press, Piscataway, NJ, USA, 22--26.

[17]

J. Durand, I. Pepelnjak, and G. Doering. 2015. BGP Operations and Security. RFC 7454. IETF.

[18]

Anja Feldmann, Olaf Maennel, Z. Morley Mao, Arthur Berger, and Bruce Maggs. 2004. Locating Internet Routing Instabilities. In Proc. of ACM SIGCOMM. ACM, New York, NY, USA, 205--218.

Digital Library

[19]

Romain Fontugne, Esteban Bautista, Colin Petrie, Yutaro Nomura, Patrice Abry, Paulo Gonçalves, Kensuke Fukuda, and Emile Aben. 2019. BGP Zombies: An Analysis of Beacons Stuck Routes. In Proc. of PAM Conf. (LNCS, Vol. 11419). Springer, Berlin Heidelberg, 197--209.

Digital Library

[20]

D. Ghita, H. Nguyen, M. Kurant, K. Argyraki, and P. Thiran. 2010. Netscope: Practical Network Loss Tomography. In Proc. of IEEE INFOCOM. IEEE Press, Piscataway, NJ, USA, 1--9.

[21]

Yossi Gilad, Avichai Cohen, Amir Herzberg, Michael Schapira, and Haya Shulman. 2017. Are We There Yet? On RPKI's Deployment and Security. In Proc. of NDSS. ISOC, Reston, USA, 15.

[22]

W. K. Hastings. 1970. Monte Carlo Sampling Methods Using Markov Chains and Their Applications. Biometrika 57, 1 (1970), 97--109.

[23]

IIT-CNR. 2020. Isolario Project. https://www.isolario.it/.

[24]

Zhuoqing Morley Mao, Ramesh Govindan, George Varghese, and Randy H. Katz. 2002. Route Flap Damping Exacerbates Internet Routing Convergence. In Proc. of ACM SIGCOMM. ACM, New York, NY, USA, 221--233.

[25]

Nicholas Metropolis and S. Ulam. 1949. The Monte Carlo Method. J. Amer. Statist. Assoc. 44, 247 (1949), 335--341. http://www.jstor.org/stable/2280232

[26]

P. Mohapatra, J. Scudder, D. Ward, R. Bush, and R. Austein. 2013. BGP Prefix Origin Validation. RFC 6811. IETF.

[27]

W. Mühlbauer, A. Feldmann, O. Maennel, M. Roughan, and S. Uhlig. 2006. Building an AS-topology model that captures route diversity. In Proc. of ACM SIGCOMM. ACM, New York, NY, USA, 195--206.

[28]

H.X. Nguyen and P. Thiran. 2007. The Boolean Solution to the Congested IP Link Location Problem: Theory and Practice. In Proc. of IEEE INFOCOM. IEEE Press, Piscataway, NJ, USA, 2117--2125.

[29]

Venkata N. Padmanabhan, Lili Qiu, and Helen J. Wang. 2002. Passive network tomography using Bayesian inference. In Proc. of ACM Internet Measurement Workshop. ACM, New York, NY, USA, 93--94.

[30]

Cristel Pelsser, Olaf Maennel, Pradosh Mohapatra, Randy Bush, and Keyur Patel. 2011. Route Flap Damping Made Usable. In Proc. of PAM Conf. (LNCS, Vol. 6579). Springer, Berlin Heidelberg, 143--152.

[31]

Y. Rekhter, T. Li, and S. Hares. 2006. A Border Gateway Protocol 4 (BGP-4). RFC 4271. IETF.

[32]

Andreas Reuter, Randy Bush, Italo Cunha, Ethan Katz-Bassett, Thomas C. Schmidt, and Matthias Wählisch. 2018. Towards a Rigorous Methodology for Measuring Adoption of RPKI Route Validation and Filtering. ACM Sigcomm Computer Communication Review 48, 1 (January 2018), 19--27.

Digital Library

[33]

RIPE 2020. Routing Information Service (RIS). http://www.ripe.net/projects/ris/rawdata.html

[34]

RIPE NCC. 2020. Current RIS Routing Beacons. https://www.ripe.net/analyse/internet-measurements/routing-information-service-ris/current-ris-routing-beacons.

[35]

Christian P. Robert and George Casella. 2005. Monte Carlo Statistical Methods (Springer Texts in Statistics). Springer-Verlag New York, Inc., Secaucus, NJ, USA.

[36]

Matthew Roughan, Walter Willinger, Olaf Maennel, Debbie Perouli, and Randy Bush. 2011. 10 Lessons from 10 Years of Measuring and Modeling the Internet's Autonomous Systems. IEEE Journal on Selected Areas in Communications 29, 9 (2011), 1810--1821.

[37]

Brandon Schlinker, Todd Arnold, Italo Cunha, and Ethan Katz-Bassett. 2019. PEERING: Virtualizing BGP at the Edge for Research. In Proc. of ACM CoNEXT. ACM, New York, NY, USA, 51--67.

Digital Library

[38]

Philip Smith and Christian Panigl. 2006. RIPE Routing-WG Recommendation For Coordinated Route-flap Damping Parameters. RIPE Document ripe-378. RIPE.

[39]

Joel Sommers, Paul Barford, Nick Duffield, and Amos Ron. 2007. Accurate and Efficient SLA Compliance Monitoring. In Proc. of ACM SIGCOMM (Kyoto, Japan). Association for Computing Machinery, New York, NY, USA, 109--120. https://doi.org/10.1145/1282380.1282394

Digital Library

[40]

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. ACM, New York, NY, USA, 279--292.

Digital Library

[41]

Cecilia Testart, Philipp Richter, Alistair King, Alberto Dainotti, and David Clark. 2020. To Filter or Not to Filter: Measuring the Benefits of Registering in the RPKI Today. In Proc. of PAM Conf. (LNCS, Vol. 12048). Springer, Berlin Heidelberg, 71--87.

[42]

University of Oregon. 2017. Route Views Project. http://www.routeviews.org/.

[43]

C. Villamizar, R. Chandra, and R. Govindan. 1998. BGP Route Flap Damping. RFC 2439. IETF.

Cited By

Degen BJonker Mvan Rijswijk-Deij RSommese R(2024)An Empirical Characterization of Anycast Convergence TimeProceedings of the 2024 Applied Networking Research Workshop10.1145/3673422.3674890(23-30)Online publication date: 23-Jul-2024
https://dl.acm.org/doi/10.1145/3673422.3674890
Rodday NCunha ÍBush RKatz-Bassett ERodosek GSchmidt TWählisch M(2024)The Resource Public Key Infrastructure (RPKI): A Survey on Measurements and Future ProspectsIEEE Transactions on Network and Service Management10.1109/TNSM.2023.332745521:2(2353-2373)Online publication date: Apr-2024
https://doi.org/10.1109/TNSM.2023.3327455
He JLi YZhang HAn CWang J(2024)ROV-GD: Improving the Measurement of ROV Deployment Using Graph Difference2024 IEEE Symposium on Computers and Communications (ISCC)10.1109/ISCC61673.2024.10733564(1-7)Online publication date: 26-Jun-2024
https://doi.org/10.1109/ISCC61673.2024.10733564
Show More Cited By

Index Terms

BGP Beacons, Network Tomography, and Bayesian Computation to Locate Route Flap Damping
1. Mathematics of computing
  1. Probability and statistics
    1. Probabilistic inference problems
      1. Bayesian computation
2. Networks
  1. Network protocols
    1. Network layer protocols
      1. Routing protocols
  2. Network types
    1. Public Internet

Recommendations

Route flap damping exacerbates internet routing convergence
Proceedings of the 2002 SIGCOMM conference

Route flap damping is considered to be a widely deployed mechanism in core routers that limits the widespread propagation of unstable BGP routing information. Originally designed to suppress route changes caused by link flaps, flap damping attempts to ...
Route flap damping exacerbates internet routing convergence
SIGCOMM '02: Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications

Route flap damping is considered to be a widely deployed mechanism in core routers that limits the widespread propagation of unstable BGP routing information. Originally designed to suppress route changes caused by link flaps, flap damping attempts to ...
Towards detecting BGP route hijacking using the RPKI
SIGCOMM '12: Proceedings of the ACM SIGCOMM 2012 conference on Applications, technologies, architectures, and protocols for computer communication

Prefix hijacking has always been a big concern in the Internet. Some events made it into the international world-news, but most of them remain unreported or even unnoticed. The scale of the problem can only be estimated.

The Resource Publication ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

IMC '20: Proceedings of the ACM Internet Measurement Conference

October 2020

751 pages

ISBN:9781450381383

DOI:10.1145/3419394

Copyright © 2020 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 October 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

Australian Research Council Centre of Excellence for Mathematical and Statistical Frontiers
Bundesministerium für Bildung und Forschung

Conference

IMC '20

Sponsor:

IMC '20: ACM Internet Measurement Conference

October 27 - 29, 2020

Virtual Event, USA

Acceptance Rates

IMC '20 Paper Acceptance Rate 53 of 216 submissions, 25%;

Overall Acceptance Rate 277 of 1,083 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
434
Total Downloads

Downloads (Last 12 months)52
Downloads (Last 6 weeks)3

Reflects downloads up to 07 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Degen BJonker Mvan Rijswijk-Deij RSommese R(2024)An Empirical Characterization of Anycast Convergence TimeProceedings of the 2024 Applied Networking Research Workshop10.1145/3673422.3674890(23-30)Online publication date: 23-Jul-2024
https://dl.acm.org/doi/10.1145/3673422.3674890
Rodday NCunha ÍBush RKatz-Bassett ERodosek GSchmidt TWählisch M(2024)The Resource Public Key Infrastructure (RPKI): A Survey on Measurements and Future ProspectsIEEE Transactions on Network and Service Management10.1109/TNSM.2023.332745521:2(2353-2373)Online publication date: Apr-2024
https://doi.org/10.1109/TNSM.2023.3327455
He JLi YZhang HAn CWang J(2024)ROV-GD: Improving the Measurement of ROV Deployment Using Graph Difference2024 IEEE Symposium on Computers and Communications (ISCC)10.1109/ISCC61673.2024.10733564(1-7)Online publication date: 26-Jun-2024
https://doi.org/10.1109/ISCC61673.2024.10733564
Feng WLiu KSun SCheng BZhang W(2024) Seraph: Towards secure and efficient multi-controller authentication with -threshold signature in multi-domain SDWAN Journal of Network and Computer Applications10.1016/j.jnca.2024.103920229(103920)Online publication date: Sep-2024
https://doi.org/10.1016/j.jnca.2024.103920
Liu YChen JChen S(2024)TriNT: A Framework for ROV Identification Based on TripletInformation Security Practice and Experience10.1007/978-981-97-9053-1_2(20-32)Online publication date: 25-Oct-2024
https://doi.org/10.1007/978-981-97-9053-1_2
Sermpezis PPrehn LKostoglou SFlores MVakali AAben E(2023)Bias in Internet Measurement Platforms2023 7th Network Traffic Measurement and Analysis Conference (TMA)10.23919/TMA58422.2023.10198985(1-10)Online publication date: 26-Jun-2023
https://doi.org/10.23919/TMA58422.2023.10198985
Li XZhou TCai ZSu J(2023)Realizing Fine-Grained Inference of AS Path With a Generative Measurable ProcessIEEE/ACM Transactions on Networking10.1109/TNET.2023.327056531:6(3112-3127)Online publication date: Dec-2023
https://doi.org/10.1109/TNET.2023.3270565
He JLi YZhang HWang MAn CWang J(2023)Be Careful of Your Neighbors: Injected Sub-Prefix Hijacking Invisible to Public MonitorsICC 2023 - IEEE International Conference on Communications10.1109/ICC45041.2023.10278923(3774-3780)Online publication date: 28-May-2023
https://doi.org/10.1109/ICC45041.2023.10278923
Sediqi KPrehn LGasser O(2022)Hyper-specific prefixesACM SIGCOMM Computer Communication Review10.1145/3544912.354491652:2(20-34)Online publication date: 20-Jun-2022
https://dl.acm.org/doi/10.1145/3544912.3544916
Xue LMarina MLi GZheng K(2022)PAINT: Path Aware Iterative Network Tomography for Link Metric Inference2022 IEEE 30th International Conference on Network Protocols (ICNP)10.1109/ICNP55882.2022.9940432(1-12)Online publication date: 30-Oct-2022
https://doi.org/10.1109/ICNP55882.2022.9940432
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 Table of Contents