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

Topology Inference Based on Maximum Common Path Matching

作　　者：姜守达[1] 尹文涛[1] 杨京礼[1] 魏长安[1] 

机构地区：[1]哈尔滨工业大学自动化测试与控制系,黑龙江哈尔滨150080

出　　处：《电子学报》2016年第9期2189-2196,共8页Acta Electronica Sinica

基　　金：国家自然科学基金(No.61501135)

摘　　要：针对存在节点动态加入和退出的网络,提出了一种基于最大公共路径匹配的拓扑推断算法.该算法根据背景流量影响对"三明治"包中两个小包进行排序重组,利用重组后的"三明治"包对节点对相似度进行计算,以提高节点对相似度的估计精度;利用TTL跳数信息选择匹配路径,按照公共路径长度匹配搜索新加入节点的插入位置,减少测量过程中所需的探测次数,提高拓扑推断的效率.仿真结果表明,该算法能提高网络拓扑结构推断的准确性和效率.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 newrearranged sandwich probes. The newjoined 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 showthat this algorithm can effectively improve the accuracy and efficiency of topology inference.

关 键 词：网络测量 网络层析成像 拓扑推测 最大公共路径匹配 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]