基于最大公共路径匹配的拓扑推断算法

针对存在节点动态加入和退出的网络，提出了一种基于最大公共路径匹配的拓扑推断算法.该算法根据背景流量影响对“三明治”包中两个小包进行排序重组，利用重组后的“三明治”包对节点对相似度进行计算，以提高节点对相似度的估计精度；利用TTL跳数信息选择匹配路径，按照公共路径长度匹配搜索新加入节点的插入位置，减少测量过程中所需的探测次数，提高拓扑推断的效率.仿真结果表明，该算法能提高网络拓扑结构推断的准确性和效率.

Topology Inference Based on Maximum Common Path Matching

For network with nodes joining and leaving dynamically,a topology inference algorithm based on maxi-mum 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 esti-mated 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 effi-ciency of topology inference.