Reference : Deployment of an Algorithm for Large-Scale Topology Discovery
Scientific journals : Article
Engineering, computing & technology : Computer science
http://hdl.handle.net/2268/106982
Deployment of an Algorithm for Large-Scale Topology Discovery
English
Donnet, Benoît mailto [Université Pierre et Marie Currie - Paris 6 - UPMC > Laboratoire d'Informatique Paris 6 - LiP6 > NPA > >]
Raoult, Philippe [> > > >]
Friedman, Timur [> > > >]
Crovella, Mark [> > > >]
Dec-2006
IEEE Journal on Selected Areas In Communications
IEEE
24
12
2210--2220
Yes (verified by ORBi)
International
0733-8716
[en] Doubletree ; Implementation
[en] Topology discovery systems are starting to be in- troduced in the form of easily and widely deployed software. Unfortunately, the research community has not examined the problem of how to perform such measurements efficiently and in a network-friendly manner. This paper describes several contributions towards that end. These were first presented in the proceedings of ACM SIGMETRICS 2005. 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 propose two metrics focusing on redundancy in probing and show that both are important. We also propose and evaluate Doubletree, an algorithm that strongly reduces redundancy while maintaining nearly the same level of node and link coverage. 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. Following the SIGMETRICS work, we implemented Doubletree, and deployed it in a real network environment. This paper describes that implementation, as well as preliminary favorable results.
http://hdl.handle.net/2268/106982

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
689-Doubletree-DC.pdfAuthor preprint296.63 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.