BibTeX Entry

  author	= {Donnet, Benoit and Friedman, Timur and Crovella, Mark},
  title		= {Improved Algorithms for Network Topology Discovery},
  booktitle	= {Lecture Notes in Computer Science, Proceedings of Passive and Active Measurement Workshop (PAM2005)},
  month		= mar,
  year		= {2005},
  URL		= {},
  abstract	= {Topology discovery systems are starting to be introduced in the form of screen saver software that have the potential to be widely deployed. However, little consideration has been given as to how to perform large-scale topology discovery efficiently and in a network-friendly manner. In previous work, we have described how large numbers of traceroute monitors can coordinate their efforts to obtain a map of the network while reducing their impact on routers and end-systems. The key is for them to share information regarding the interfaces that they have discovered. However, such sharing introduces considerable communication overhead. In this paper, we show how we can improve the communication scaling properties through the use of Bloom filters for lossy compression of the interface list. Also, any system in which every monitor traces routes towards every destination has inherent scaling problems. We propose to divide up the monitors into clusters, each cluster focusing on a different destination list.}