Route oracle: Where have all the packets gone?

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.