Efficient Algorithms for Large-Scale Topology Discovery

Details Efficient Algorithms for Large-Scale Topology Discovery Efficient Algorithms for Large-Scale Topology Discovery

2004-11-07

arxiv.org/abs/cs/0411013v1

Computer Science

Networking and Internet Architecture

23 pages

Scientific paper

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, the research community has not examined the problem of how to perform such measurements efficiently and in a network-friendly manner. In this paper we make two 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. We show that straightforward approaches to addressing these two kinds of redundancy must take opposite tacks, and are thus fundamentally in conflict. Our second contribution is to propose and evaluate Doubletree, an algorithm that reduces both types of redundancy simultaneously on routers and end systems. The key ideas are to exploit the tree-like structure of routes to and from a single point in order to guide when to stop probing, and 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. We then show how to enable efficient communication between monitors through the use of Bloom filters.

Affiliated with

Also associated with

No associations

Rating

Efficient Algorithms for Large-Scale Topology Discovery does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Efficient Algorithms for Large-Scale Topology Discovery, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Algorithms for Large-Scale Topology Discovery will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-109176