Target sampling based on routing behavior analysis in network topology measurement

In order to investigate the insufficiency of target sampling in current network topology measurement practice and the distortion of measurement models, a sort of target sampling methods based on routing behavior analysis were presented, namely, the uniform random sampling as a benchmark method, the minimum cover sampling as an optimal method, the last-hop sampling for the path diversity, and the bisection sampling for the destination prefix diversity. Experiments based on real measurement data show that a half of topology information can be missed in the traditional '1 per/24' random sampling, of which 10% of missed information is caused by the path diversity and the rest is caused by destination prefix diversity. The minimum cover sampling is robust to the routing dynamics and performs better than the uniform random sampling at the long-term practice.