Traceroute-based topology inference without network coordinate estimation

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

Abstract

Underlay topology information is important to construct efficient overlay networks. To achieve end-to-end network topology inference among a group of hosts, traceroute-like tools are often used. Previously, Max-Delta has been proposed to infer a highly accurate topology with a low number of traceroutes. However, Max-Delta relies on external tools to estimate host coordinates, which incur considerable deployment overhead. In this paper, we consider novel inference schemes with no coordinate estimation. One choice is to select long paths to traceroute. That is, based on existing traceroute results, each host can estimate the distance between another host and itself. It can then select the host with the largest distance between them as the traceroute target. We call this scheme Longest-Path-First (LPF). Similarly, we can define Shortest-Path-First (SPF) inference. The intuition may indicate that LPF performs better than SPF, as longer paths often contain more underlay links and routers, and hence more undiscovered links or routers. However, our simulation results on Internet-like topologies show that SPF can achieve comparable performance with Max-Delta, while LPF performs even worse than a random inference scheme. To explain the results, we analyze the statistics of all-pairs paths between hosts. Our results show that long paths have serious overlaps on underlay links, showing much higher path stress than short paths. We also find that there exist quite a few links only appearing in short paths and seldom appearing in long paths. Therefore, with the same number of traceroutes, SPF can discover more underlay links and routers than LPF. Furthermore, as SPF prefers short paths, a traceroute in SPF sends less probing packets and consumes less network resource than that in LPF. Therefore, SPF is a highly efficient inference scheme with low deployment overhead and low measurement overhead. ©2008 IEEE.

Citation

Jin, X., Tu, W., & Chan, S. H. (2008, May). Traceroute-based topology inference without network coordinate estimation. Presented at 2008 IEEE International Conference on Communications, Beijing, China

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 2008 IEEE International Conference on Communications
• Start Date: May 19, 2008
• End Date: May 23, 2008
• Publication Date: Sep 12, 2008
• Deposit Date: Jun 9, 2025
• Publisher: Institute of Electrical and Electronics Engineers
• Peer Reviewed: Peer Reviewed
• Pages: 1615-1619
• Book Title: 2008 IEEE International Conference on Communications
• DOI: https://doi.org/10.1109/ICC.2008.312
• Public URL: https://durham-repository.worktribe.com/output/4092782