Route oracle: where have all the packets gone?

Abstract

Many network-management problems in large backbone networks need the answer to a seemingly simple question: where does a given IP packet, entering the network at a particular place and time, leave the network to continue on its path to the destination? Answering this question at scale and in real time is challenging for several reasons: (i) a destination IP address could match several IP prefixes, (ii) the longest-matching prefix may change over time, (iii) the number of IP prefixes and routing protocol messages is very large, and (iv) network-management applications often require answers to this question for a large number of destination IP addresses in real time. In this paper, we present an efficient algorithm for tracking prefix-match changes for ranges of IP addresses. We then present the design, implementation, and evaluation of the Route Oracle tool that answers queries about routing changes on behalf of network management applications. Our design of Route Oracle includes several performance optimizations, such as pre-processing of BGP update messages, and parallelization of query processing. Experiments with BGP measurement data from a large ISP backbone demonstrate that our system answers queries in real time and at scale.

References

1. Y. Zhu, J. Rexford, S. Sen, and A. Shaikh, "Impact of Prefix-Match Changes on IP Reachability," in Proc. Internet Measurement Conference, 2009.
2. "Packet Design Route Explorer." http://www.packetdesign.com.
3. "University of Oregon Route Views Project." http://www.routeviews.org.
4. RIPE, "RIPE Routing Information Service (RIS)." http://www.ripe.net/ris.
5. M. Caesar, L. Subramanian, and R. H. Katz, "Towards localizing root causes of BGP dynamics," tech. rep., UC Berkeley, 2003.
6. A. Feldmann, O. Maennel, Z. M. Mao, A. Berger, and B. Maggs, "Locating Internet Routing Instabilities," in Proc. ACM SIGCOMM, 2004.
7. R. Teixeira and J. Rexford, "A Measurement Framework for Pin-pointing Routing Changes," in ACM SIGCOMM Network Troubleshooting Workshop, 2004.
8. A. Broido and k. claffy, "Analysis of RouteViews BGP data: Policy atoms," in Proc. Network Resource Data Management Workshop, 2001.
9. Y. Afek, O. Ben-Shalom, and A. Bremler-Barr, "On the structure and application of BGP policy atoms," in Proc. Internet Measurement Workshop, pp. 209--214, 2002.
10. T. Bu, L. Gao, and D. Towsley, "On characterizing BGP routing table growth," Computer Networks, vol. 45, pp. 45--54, May 2004.
11. X. Meng, Z. Xu, B. Zhang, G. Huston, S. Lu, and L. Zhang, "IPv4 address allocation and BGP routing table evolution," ACM Computer Communication Review, January 2005.

Index Terms

• Computer systems organization

  • Dependable and fault-tolerant systems and networks

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Networks

  • Network components

  • Network performance evaluation

  • Network protocols

    • Network layer protocols

      • Routing protocols

  • Network types

    • Public Internet