Topology inference based on maximum common path matching

For network with nodes joining and leaving dynamically, a topology inference algorithm based on maximum common path matching is proposed. In this algorithm, in order to improve the estimating precision of similarity metric, two small packets of sandwich probes are rearranged in accordance with cross-traffic effects, and the similarity metric is estimated according to the new rearranged sandwich probes. The new joined nodes are directly added into the existing topology by matching the length of common path. By using the information of TTL hop count to select match path, the efficiency of topology inference is improved. The simulating results show that this algorithm can effectively improve the accuracy and efficiency of topology inference.