A new power law in topology discovery based on shortest-path

Recently, the characteristics of traceroute probe have been widely studied in the field of Internet topology discovery, which helps researchers to understand the role of Traceroute tool better, such as sampling bias, marginal utility and so on. In this paper, we study three raw datasets of traceroute probe of different platforms and observe an interesting phenomenon: in the process of one probe, every two of three parameters (i.e. the number of discovered nodes, the number of discovered links and the number of vantage points) have a very strong power-law relationship without considering the distribution of sources and destinations. We call this Trace Power Law and validate its existence in both IP and AS level. As far as we know, it is the first time to discover this characteristic, which, we believe, should be of value for better understanding and use of traceroute. The main contribution of our work lies in two aspects: first, we find a new feature of traceroute sampling and validate it in real datasets and simulated experiments; second, based on what we find, an application is given to predict the numbers of nodes and links detected in one probe.