Route oracle: Where have all the packets gone?

Yaping Zhu, Jennifer L. Rexford, Subhabrata Sen, Aman Shaikh

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)19-24
Number of pages6
JournalPerformance Evaluation Review
Issue number4
StatePublished - Mar 2010

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Route oracle: Where have all the packets gone?'. Together they form a unique fingerprint.

Cite this