A Distributed Approach to End-to-End Network Topology Inference
Lists
Only you see this
Abstract
To construct an efficient overlay network, the information of underlay is important. However, the inference of an underlay topology is not easy. We consider using end-to-end measurement tools such as traceroute to infer the underlay topology among a group of hosts. 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, Max-Delta relies on a central server to collect traceroute results and to select paths for hosts to measure. It is hence not scalable to large groups. In this paper, we investigate a distributed version of Max-Delta scheme in order to support scalable inference. In our scheme, each host joins an overlay tree before conducting traceroutes. A host then independently selects paths to traceroute and exchanges traceroute results with others through the overlay tree. As a result, each host can maintain a partially discovered topology. We have studied two key issues in the scheme, i.e., how to construct a low-diameter overlay tree and how to reduce bandwidth consumption in measurements. As compared to Max-Delta, our scheme is fully distributed and scalable. In the scheme, each host computes its own traceroute targets, and the computational loads are distributed to all the hosts instead of a single server. Furthermore, each host only exchanges data with a few other hosts and does not need to set up connections with all the other hosts. Simulation results show that the constructed tree has a low diameter and can support quick data exchange among hosts, and that the use of a lookup table for routers can significantly reduce bandwidth consumption in data exchange.
BibTeX
@inproceedings{jin2007distributed,
author = {Xing Jin and Qiuyan Xia and Shueng-Han Gary Chan},
title = {{A Distributed Approach to End-to-End Network Topology Inference}},
booktitle = {ICC},
year = {2007},
url = {https://openreview.net/forum?id=IONZmHriyr},
}Loading related content...