On Destination Set in IP-Level Topology Measurement

We present a thorough investigation of four issues with the destination set in IP-level topology measurement. (1) To evaluate the completeness of the destination set, we measured by brute force and found that a half of edges will be missed by the uniform random selection (URS) method which was adopted by well-known CAIDA´ skitter. (2) Two potential reasons for edge missing, the short-term routing dynamics and the subnetting technique, were investigated with the last-hop selection method and the bisection selection method respectively. And the results showed that the subnetting technique is the main reason. (3) To select destinations efficiently, we presented the minimum cover selection (MCS) method which performed better than the URS method on 75% of networks over three months. (4) Finally, to investigate the bias of topology characterization, we measured a destination set larger than before and discovered a Chinese topology whose size is 5 times as large as that discovered by skitter. The comparison between characteristics of skitter´s topology and ours indicated that the small destination set trends to miss the information on marginal networks.