Reference : Improved Algorithms for Network Topology Discovery
Scientific congresses and symposiums : Paper published in a book
Engineering, computing & technology : Computer science
Improved Algorithms for Network Topology Discovery
Donnet, Benoît mailto [Université Pierre et Marie Currie - Paris 6 - UPMC > LiP6 > > >]
Friedman, Timur [ > > ]
Crovella, Mark [ > > ]
International Workshop on Passive and Active Network Measurement
PAM 2005
March 2005
[en] traceroute ; Doubletree ; Bloom filters
[en] Topology discovery systems are starting to be introduced in the form of easily and widely deployed software. However, little consideration has been given as to how to perform large-scale
topology discovery efficiently and in a network-friendly manner. In prior work, we have described how large numbers of traceroute monitors can coordinate their efforts to map the network while
reducing their impact on routers and end-systems. The key is for them to share information regarding the paths they have explored. However, such sharing introduces considerable communication overhead. Here, we show how to improve the communication scaling properties through the use of Bloom filters to encode a probing stop set. Also, any system in which every monitor traces routes towards every destination has inherent scaling problems. We propose capping the number of monitors per destination, and dividing the monitors into clusters, each cluster focusing on a different destination list.

File(s) associated to this reference

Fulltext file(s):

Open access
593-donnet05improved.pdfAuthor postprint357.37 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.