A method for placing traceroute-like topology discovery instrumentation

An accurate map of the Internet is very important for studying the network¿s internal structure and network management. The main approach to map the Internet is to collect information from a set of sources by using traceroute-like probes. In a typical mapping project, active measurement sources are relatively scarce while traceroute destinations are plentiful, which makes the sampled graph quite different from the original one. So, it becomes very important to determine how to place these sources such that the sampled graph can be closer to the original one, especially in the case that the number of sources is limited. In this paper, we investigate the relationship between the placement of traceroute sources and their sampled result, which, to our knowledge, has not been systematically studied before. Based on the relationship, we propose a method on how to place the traceroute sources. We show that the graph sampled from sources selected by our method is more accurate than the ones randomly selected. We also validate our conclusion using the raw trace data of skitter project.