A measurement framework for pin-pointing routing changes

ABSTRACT

Changes in the end-to-end path between two hosts can lead to sudden changes in the round-trip time and available bandwidth, or even the complete loss of connectivity. Determining the reason for the routing change is crucial for diagnosing and fixing the problem, and for holding a particular domain accountable for the disruption. Active measurement tools like traceroute can infer the current path between two end-points, but not where and why the path changed. Analyzing BGP data from multiple vantage points seems like a promising way to infer the root cause of routing changes. In this paper, we explain the inherent limitations of using BGP data alone and argue for a distributed approach to troubleshooting routing problems. We propose a solution where each AS continuously maintains a view of routing changes in its own network, without requiring additional support from the underlying routers. Then, we describe how to query the measurement servers along the AS-level forwarding path from the source to the destination to uncover the location and the reason for the routing change.

REFERENCES

• 1: V. Jacobson, "Traceroute." ftp://ftp.ee.lbl.gov/traceroute.tar.gz.
• 2: Zhuoqing Morley Mao , Jennifer Rexford , Jia Wang , Randy H. Katz, Towards an accurate AS-level traceroute tool, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863996]
• 3: A. McGregor and M. Luckie, "IP measurement protocol (IPMP)." Internet Draft, draft-mcgregor-ipmp-04.txt, February 2004.
• 4: J. Bennett, "The case for an Internet Measurement Protocol," November 11 2003. E-mail posting on the Internet Measurement Research Group, http://www1.ietf.org/mail-archive/working-groups/imrg/current/msg00154.html.
• 5: Nick Feamster , David G. Andersen , Hari Balakrishnan , M. Frans Kaashoek, Measuring the effects of internet path faults on reactive routing, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 6: Ratul Mahajan , Neil Spring , David Wetherall , Thomas Anderson, User-level internet path diagnosis, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 7: "Route Views." http://www.routeviews.org.
• 8: "RIPE NCC RIS." http://www.ripe.net/ripencc/ris.
• 9: Di-Fa Chang , Ramesh Govindan , John Heidemann, The Temporal and Topological Characteristics of BGP Path Changes, Proceedings of the 11th IEEE International Conference on Network Protocols, p.190, November 04-07, 2003
• 10: M. Caesar, L. Subramanian, and R. H. Katz, "Towards localizing root causes of BGP dynamics," Tech. Rep. CSD-03-1292, UC Berkeley, November 2003.
• 11: Anja Feldmann , Olaf Maennel , Z. Morley Mao , Arthur Berger , Bruce Maggs, Locating internet routing instabilities, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 12: T. G. Griffin, "What is the sound of one route flapping?." presentation at the Network Modeling and Simulation Summer Workshop, 2002.
• 13: David D. Clark , Craig Partridge , J. Christopher Ramming , John T. Wroclawski, A knowledge plane for the internet, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863957]
• 14: "A Border Gateway Protocol 4 (BGP-4)." Internet Draft draft-ietf-idr-bgp4-24.txt, work in progress, November 2003.
• 15: E. Chen and J. Stewart, "A Framework for Inter-Domain Route Aggregation," RFC 2519, IETF, February 1999.
• 16: G. Huston, "Interconnection, peering, and settlements," in Proc. INET, June 1999.
• 17: Renata Teixeira , Aman Shaikh , Tim Griffin , Jennifer Rexford, Dynamics of hot-potato routing in IP networks, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 18: Timothy G. Griffin , Gordon Wilfong, On the correctness of IBGP configuration, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 19: A. Shaikh and A. Greenberg, "OSPF monitoring: Architecture, design, and deployment experience," in Proc. USENIX/ACM NSDI, March 2004.
• 20: Nick Feamster , Jared Winick , Jennifer Rexford, A model of BGP routing for network engineering, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 21: A. Feldmann, A. Greenberg, C. Lund, N. Reingold, and J. Rexford, "NetScope: Traffic engineering for IP networks," IEEE Network Magazine, pp. 11--19, March 2000.
• 22: Craig Labovitz , Abha Ahuja , Abhijit Bose , Farnam Jahanian, Delayed Internet routing convergence, IEEE/ACM Transactions on Networking (TON), v.9 n.3, p.293-306, June 2001 [doi>10.1109/90.929852]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations

General Terms:
Design, Management, Measurement, Performance, Reliability

Keywords:
BGP, IGP, network troubleshooting, root cause analysis