Improving the Efficiency of End-to-End Network Topology Inference

Jin Xiao, W.-p.k. Yiu, S.-h. Gary Chan

Abstract

We consider inferring the underlay topology among a group of hosts by traceroute-like end-to-end measurement tools. Since pair-wise traceroutes among hosts take a long time and generate much network traffic, Max-Delta has been proposed to infer a highly accurate topology with a low number of traceroutes. However, there is still high measurement redundancy in Max-Delta. That is, a router may be repeatedly visited in different traceroutes. In this paper, we integrate a previously proposed Doubletree algorithm into Max-Delta to reduce such redundancy. We study two key issues in the integration, i.e., the selection of h (a parameter of Doubletree) and the distribution of the global stop set of Doubletree. We have conducted extensive simulations on Internet-like topologies to evaluate the proposed scheme. The results show that Doubletree can significantly reduce the measurement redundancy and the bandwidth consumption in Max-Delta while introducing a small penalty in the measurement accuracy.
BibTeX
@inproceedings{xiao2007improving,
  author = {Jin Xiao and W.-P.K. Yiu and S.-H. Gary Chan},
  title = {{Improving the Efficiency of End-to-End Network Topology Inference}},
  booktitle = {ICC},
  year = {2007},
  url = {https://openreview.net/forum?id=JyhbVxRH3y},
}

Loading related content...

Figure