Abstract

There is a growing interest in discovery of internet topology at the interface level. A new generation of highly distributed measurement systems is currently being deployed. Unfortunately, prior to this thesis, the research community has not examined the problem of how to perform such measurements efficiently and in a network-friendly manner.

In this thesis, we make several contributions toward that end. First, we show that standard topology discovery methods (e.g., skitter) are quite inefficient, repeatedly probing the same interfaces. This is a concern, because when scaled up, such methods will generate so much traffic that they will begin to resemble DDoS attacks. We measure two kinds of redundancy in probing (intra- and inter-monitor) and show that both kinds are important. As it is not unusual for a route tracing monitor to operate in isolation, we next propose and evaluate strategies for reducing redundancy within a single monitor. The key idea to these strategies is to start probing far from the monitor and work backwards. Our results show that our algorithms can decrease probing redundancy at the cost of a small reduction in node and link discovery. We third propose and evaluate Doubletree, a cooperative algorithm that reduces both types of redundancy simultaneously on routers and end systems. The key ideas are (i) to exploit the tree-like structure of routes to and from a single point in order to guide when to stop probing, and (ii) to probe each path by starting near its midpoint. Our results show that Doubletree can reduce both types of measurement load on the network dramatically, while permitting discovery of nearly the same set of nodes and links. In addition, we provide and evaluate an implementation of Doubletree into a tool called traceroute@home. Fourth, we provide several improvements to Doubletree in order to reduce the communication cost, the load on destinations and increase the coverage.

Finally, we also provide a generalization of Bloom filters, called retouched Bloom filters, that permits false negatives in addition to false positives and allows a trade-off between the two. We further show how to lower the overall error rate, expressing it as a combination of the false positive rate and the false negative rate.