On the placement of traceroute-like topology discovery instrumentation

An accurate map of the Internet is very important for studying the network’s internal structure andnetwork management. The main approach to map the Internet is to collect information from a set of sources byusing traceroute-like probes. In a typical mapping project, active measurement sources are relatively scarcewhile traceroute destinations are plentiful, which makes the sampled graphs quite different from the originalones. So, in the case that the number of sources is fixed, it becomes very important to determine how to placethese sources such that the sampled graphs can be closer to the original ones. In this paper, we investigate therelationship between the placement of traceroute sources and their sampled result. Based on the relationship, wepropose a method on how to place the traceroute sources. We show that the graph sampled from sourcesselected using our method is more accurate than the ones randomly selected. We also validate our conclusionusing the raw trace data of skitter[2] project.