skip to main content
research-article
Open access

PoiRoot: investigating the root cause of interdomain path changes

Published: 27 August 2013 Publication History

Abstract

Interdomain path changes occur frequently. Because routing protocols expose insufficient information to reason about all changes, the general problem of identifying the root cause remains unsolved. In this work, we design and evaluate PoiRoot, a real-time system that allows a provider to accurately isolate the root cause (the network responsible) of path changes affecting its prefixes. First, we develop a new model describing path changes and use it to provably identify the set of all potentially responsible networks. Next, we develop a recursive algorithm that accurately isolates the root cause of any path change. We observe that the algorithm requires monitoring paths that are generally not visible using standard measurement tools. To address this limitation, we combine existing measurement tools in new ways to acquire path information required for isolating the root cause of a path change. We evaluate PoiRoot on path changes obtained through controlled Internet experiments, simulations, and "in-the-wild" measurements. We demonstrate that PoiRoot is highly accurate, works well even with partial information, and generally narrows down the root cause to a single network or two neighboring ones. On controlled experiments PoiRoot is 100% accurate, as opposed to prior work which is accurate only 61.7% of the time.

References

[1]
R. Bush, O. Maennel, M. Roughan, and S. Uhlig. Internet optometry: assessing the broken glasses in Internet reachability. In IMC, 2009.
[2]
M. Caesar, L. Subramanian, and R. H. Katz. Towards localizing root causes of BGP dynamics. Technical report, University of California, Berkeley, 2003.
[3]
K. Chen, D. R. Choffnes, R. Potharaju, Y. Chen, F. E. Bustamante, D. Pei, and Y. Zhao. Where the sidewalk ends: Extending the Internet AS graph using traceroutes from P2P users. In CoNEXT, 2009.
[4]
A. Christie. Murder on the Links. The Bodley Head, 1923.
[5]
L. Colitti. Internet Topology Discovery Using Active Probing. PhD thesis, University di Roma Tre, 2006.
[6]
A. Dhamdhere, R. Teixeira, C. Dovrolis, and C. Diot. NetDiagnoser: Troubleshooting network unreachabilities using end-to-end probes and routing data. In CoNEXT, 2007.
[7]
X. Dimitropoulos, D. Krioukov, M. Fomenkov, B. Huffaker, Y. Hyun, kc claffy, and G. Riley. As relationships: inference and validation. SIGCOMM Comput. Commun. Rev., 37(1):29--40, 2007.
[8]
N. Feamster, D. G. Andersen, H. Balakrishnan, and M. F. Kaashoek. Measuring the effects of Internet path faults on reactive routing. In SIGMETRICS, 2003.
[9]
A. Feldmann, O. Maennel, Z. M. Mao, A. Berger, and B. Maggs. Locating Internet routing instabilities. In SIGCOMM, 2004.
[10]
L. Gao. On inferring autonomous system relationships in the Internet. IEEE/ACM TON, 9(6):733--745, 2001.
[11]
P. Gill, S. Goldberg, and M. Schapira. A survey of interdomain routing policies. NANOG 56, 2012. http://www.nanog.org/meetings/nanog56/presentations/Monday/mon.general.gill.11.pdf.
[12]
T. Griffin and G. Huston. BGP wedgies. Network Working Group, RFC 4264, Nov. 2005.
[13]
T. G. Griffin, B. F. Shepherd, and G. Wilfong. The stable paths problem and interdomain routing. IEEE/ACM ToN, 10(2):232--243, 2002.
[14]
N. Gvozdiev, B. Karp, and M. Handley. LOUP: The principles and practice of intra-domain route dissemination. In NSDI, 2013.
[15]
Y. Huang, N. Feamster, A. Lakhina, and J. J. Xu. Diagnosing network disruptions with network-wide analysis. In SIGMETRICS, 2007.
[16]
E. Katz-Bassett, H. V. Madhyastha, V. K. Adhikari, C. Scott, J. Sherry, P. van Wesep, A. Krishnamurthy, and T. Anderson. Reverse traceroute. In NSDI, 2010.
[17]
E. Katz-Bassett, H. V. Madhyastha, J. P. John, A. Krishnamurthy, D. Wetherall, and T. Anderson. Studying black holes in the Internet with Hubble. In NSDI, 2008.
[18]
E. Katz-Bassett, C. Scott, D. R. Choffnes, I. Cunha, V. Valancius, N. Feamster, H. V. Madhyastha, T. Anderson, and A. Krishnamurthy. LIFEGUARD: Practical repair of persistent route failures. In SIGCOMM, 2012.
[19]
R. Krishnan, H. V. Madhyastha, S. Srinivasan, S. Jain, A. Krishnamurthy, T. Anderson, and J. Gao. Moving beyond end-to-end path information to optimize CDN performance. In IMC, 2009.
[20]
C. Labovitz, A. Ahuja, A. Bose, and F. Jahanian. Delayed Internet routing convergence. In SIGCOMM, 2000.
[21]
C. Labovitz, G. R. Malan, and F. Jahanian. Internet routing instability. IEEE/ACM TON, 6(5):515--528, 1998.
[22]
G. Linden. Make data useful. http://sites.google.com/site/glinden/Home/StanfordDataMining.2006--11--28.ppt, 2006.
[23]
H. Madhyastha, E. Katz-Bassett, T. Anderson, A. Krishnamurthy, and A. Venkataramani. iPlane Nano: Path Prediction for Peer-to-Peer Applications. In NSDI, 2009.
[24]
H. V. Madhyastha, T. Isdal, M. Piatek, C. Dixon, T. Anderson, A. Krishnamurthy, and A. Venkataramani. iPlane: An information plane for distributed services. In OSDI, 2006.
[25]
R. Mahajan, D. Wetherall, and T. Anderson. Understanding BGP misconfiguration. In SIGCOMM, 2002.
[26]
Z. M. Mao, R. Bush, T. G. Griffin, and M. Roughan. BGP beacons. In IMC, 2003.
[27]
Z. M. Mao, J. Rexford, J. Wang, and R. H. Katz. Towards an accurate AS-level traceroute tool. In SIGCOMM, 2003.
[28]
D. Meyer. RouteViews. http://www.routeviews.org.
[29]
W. Mühlbauer, A. Feldmann, O. Maennel, M. Roughan, and S. Uhlig. Building an AS-topology model that captures route diversity. In SIGCOMM, 2006.
[30]
R. Oliveira, D. Pei, W. Willinger, B. Zhang, and L. Zhang. The (in)completeness of the observed internet as-level structure. IEEE/ACM Trans. Netw., 18(1):109--122, 2010.
[31]
R. Oliveira, B. Zhang, D. Pei, and L. Zhang. Quantifying path exploration in the internet. IEEE/ACM Trans. Netw., 17(2):445--458, 2009.
[32]
D. Pei, M. Azuma, D. Massey, and L. Zhang. BGP-RCN: Improving BGP convergence through root cause notification. Computer Networks, 48(2):175--194, 2005.
[33]
Ponemon Institute. Calculating the cost of data center outages, 2011. http://www.emersonnetworkpower.com/en-US/Brands/Liebert/Documents/White%20Papers/data-center-costs_24659-R02--11.pdf.
[34]
A. Shaikh and A. Greenberg. OSPF monitoring: Architecture, design and deployment experience. In NSDI, 2004.
[35]
N. Spring, R. Mahajan, and T. Anderson. Quantifying the causes of path inflation. In SIGCOMM, 2003.
[36]
S. Stefanov. Yslow 2.0. In CSDN SD2C, 2008.
[37]
R. Teixeira and J. Rexford. A measurement framework for pin-pointing routing changes. In ACM SIGCOMM Workshop on Network Troubleshooting, 2004.
[38]
A. Toonk. BGPmon. In NANOG 45, 2009. http://www.nanog.org/meetings/nanog45/presentations/Sunday/Toonk_bgpmon_N45.pdf.
[39]
UCLA Internet topology collection. http://irl.cs.ucla.edu/topology/.
[40]
V. Valancius, N. Feamster, J. Rexford, and A. Nakao. Wide-area route control for distributed services. In ATC, 2010.
[41]
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 NSDI, 2005.
[42]
H. Yan, D. Matthews, R. Oliveira, L. Zhang, K. Burnett, and D. Massey. Bgpmon: A real-time, scalable, extensible monitoring system. In In Cybersecurity Applications and Technologies Conference for Homeland Security(CATCH, 2009.
[43]
M. Zhang, C. Zhang, V. Pai, L. Peterson, and R. Wang. PlanetSeer: Internet path failure monitoring and characterization in wide-area services. In OSDI, 2004.
[44]
Y. Zhu, B. Helsley, J. Rexford, A. Siganporia, and S. Srinivasan. Latlong: Diagnosing wide-area latency changes for cdns. IEEE Transactions on Network and Service Management, 9, 2012.

Cited By

View all
  • (2024)Locating the Root Cause of Large-scale BGP Anomaly with Routing Dependence2024 IEEE International Performance, Computing, and Communications Conference (IPCCC)10.1109/IPCCC59868.2024.10850193(1-7)Online publication date: 22-Nov-2024
  • (2021)Performance Analysis of Multipath BGPIEEE INFOCOM 2021 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)10.1109/INFOCOMWKSHPS51825.2021.9484523(1-6)Online publication date: 10-May-2021
  • (2020)Universal Path Tracing for Large-Scale Sensor NetworksIEEE/ACM Transactions on Networking10.1109/TNET.2020.296558728:2(447-460)Online publication date: Apr-2020
  • Show More Cited By

Index Terms

  1. PoiRoot: investigating the root cause of interdomain path changes

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM SIGCOMM Computer Communication Review
    ACM SIGCOMM Computer Communication Review  Volume 43, Issue 4
    October 2013
    595 pages
    ISSN:0146-4833
    DOI:10.1145/2534169
    Issue’s Table of Contents
    • cover image ACM Conferences
      SIGCOMM '13: Proceedings of the ACM SIGCOMM 2013 conference on SIGCOMM
      August 2013
      580 pages
      ISBN:9781450320566
      DOI:10.1145/2486001
    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 the author(s) 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: 27 August 2013
    Published in SIGCOMM-CCR Volume 43, Issue 4

    Check for updates

    Author Tags

    1. bgp
    2. measurement
    3. monitoring
    4. path changes
    5. root cause analysis

    Qualifiers

    • Research-article

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)173
    • Downloads (Last 6 weeks)25
    Reflects downloads up to 20 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Locating the Root Cause of Large-scale BGP Anomaly with Routing Dependence2024 IEEE International Performance, Computing, and Communications Conference (IPCCC)10.1109/IPCCC59868.2024.10850193(1-7)Online publication date: 22-Nov-2024
    • (2021)Performance Analysis of Multipath BGPIEEE INFOCOM 2021 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)10.1109/INFOCOMWKSHPS51825.2021.9484523(1-6)Online publication date: 10-May-2021
    • (2020)Universal Path Tracing for Large-Scale Sensor NetworksIEEE/ACM Transactions on Networking10.1109/TNET.2020.296558728:2(447-460)Online publication date: Apr-2020
    • (2019)Extracting Routing Events From TraceroutesIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2019.291133027:3(1000-1012)Online publication date: 15-Jul-2019
    • (2017)I-SeismographIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2017.274890225:6(3411-3426)Online publication date: 1-Dec-2017
    • (2017)Did the Super Bowl Kill the Internet?IEEE Access10.1109/ACCESS.2017.27039805(9812-9822)Online publication date: 2017
    • (2014)Identifying and Analyzing High Impact Routing Events with PathMinerProceedings of the 2014 Conference on Internet Measurement Conference10.1145/2663716.2663754(421-434)Online publication date: 5-Nov-2014
    • (2022)PoiEvent: An approach to extract the persistent and destructive routing eventsComputer Networks10.1016/j.comnet.2022.109313217(109313)Online publication date: Nov-2022
    • (2021)Identifying Networks Vulnerable to IP SpoofingIEEE Transactions on Network and Service Management10.1109/TNSM.2021.306148618:3(3170-3183)Online publication date: Sep-2021
    • (2021)A Survey of Fast-Recovery Mechanisms in Packet-Switched NetworksIEEE Communications Surveys & Tutorials10.1109/COMST.2021.306398023:2(1253-1301)Online publication date: Oct-2022
    • Show More Cited By

    View Options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Login options

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media