Scalable and efficient end-to-end network topology inference

Jin, Xing; Tu, Wanqing; Chan, S. H.Gary

Abstract

We consider using tools like traceroute to infer the underlay topology among a group of hosts. Traditional Max-Delta inference relies on a central server and is not scalable. In this paper, we investigate a distributed inference scheme to support scalable inference. In our scheme, each host joins an overlay tree before conducting traceroute. 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. Furthermore, we propose several techniques to reduce the measurement cost, including (a) integrating the Doubletree algorithm to reduce measurement redundancy; (b) setting up a lookup table for routers to reduce traceroute size, and (c) conducting topology abstraction and reducing the computing frequency to reduce computational overhead. In our scheme, the computation loads for target selection are distributed to all the hosts instead of a single server, and the consumption of edge bandwidth at a host is hence limited. We have done simulations on Internet-like topologies and conducted measurements on PlanetLab. The results show that the constructed tree has a low diameter. Furthermore, the proposed improvements can efficiently reduce measurement redundancy, computational overhead and bandwidth consumption. © 2008 IEEE.

Citation

Jin, X., Tu, W., & Chan, S. H. (2008). Scalable and efficient end-to-end network topology inference. IEEE Transactions on Parallel and Distributed Systems, 19(6), 837-850. https://doi.org/10.1109/TPDS.2007.70771

• Journal Article Type: Article
• Online Publication Date: Jun 30, 2008
• Publication Date: Jun 1, 2008
• Deposit Date: Jun 5, 2025
• Journal: IEEE Transactions on Parallel and Distributed Systems
• Print ISSN: 1045-9219
• Electronic ISSN: 1558-2183
• Publisher: Institute of Electrical and Electronics Engineers
• Peer Reviewed: Peer Reviewed
• Volume: 19
• Issue: 6
• Pages: 837-850
• DOI: https://doi.org/10.1109/TPDS.2007.70771
• Public URL: https://durham-repository.worktribe.com/output/4089623