A delay-guiding source selection method in network topology discovery

The mapping of the Internet topological structure is indeed of great importance for a better understanding of the network's internal structure, network management, etc. Current explorations still mainly rely on the extensive use of the traceroute tool from a given set of sources to a given set of destinations. However, the deployment of dedicated measurement infrastructures on sources is often quite costly and too many sources may impose heavy burden on the network. And there is a diminishing-returns effect concerning sources. In addition, when using different sets of sources with the same size, the overall coverage of the sampled network may vary significantly. As a result, it is very important for a network topology discovery project to select a limited set of sources to detect more nodes and edges. In this paper, aiming to maximize the numbers of nodes and edges discovered when deploying a limited set of sources, we propose a novel delay-guiding method. This method for the first time uses the underlying physical link delay between the source and a small number of landmarks as the metric to make source selection decisions. It incurs little extra traffic to the network because only the delay from the sources to a small number of landmarks is needed, which makes it very practical in real network topology discovery. We also compare our method with other known methods on both real datasets and synthetic datasets. The results show that our method is significantly more effective than the existing methods.