一种基于测量的启发式网络拓扑匹配优化算法  

A Measurement-Based Heuristic Topology Matching Optimization Algorithm

作　　者：廖怡 盛益强[1] 王劲林[1] LIAO Yi;SHENG Yi-Qiang;WANG Jin-Lin(National Network New Media Engineering Research Center,Institute of Acoustics,Chinese Academy of Sciences,Beijing 100190;University of Chinese Academy of Sciences,Beijing 100049)

机构地区：[1]中国科学院声学研究所国家网络新媒体工程技术研究中心,北京100190 [2]中国科学院大学,北京100049

出　　处：《计算机学报》2018年第9期2044-2059,共16页Chinese Journal of Computers

基　　金：中国科学院先导专项基金(XDA06040602;XDA06040501);国家科技重大专项"新一代宽带无线移动通信网"(2017ZX03001019)资助~~

摘　　要：在复杂多变的网络环境下,覆盖网络与物理网络之间普遍存在着拓扑不匹配问题.拓扑不匹配问题会给网络造成不必要的压力,影响系统的效率和可扩展性等.缓解拓扑不匹配问题有助于提高网络寻址效率、减少冗余流量、降低端到端时延.随着计算机和通信技术的不断发展,互联网的规模不断增大,网络节点的地理位置分布范围扩大、移动性增强,极大地增加了网络的动态性,尤其是节点的频繁加入、退出和失效,严重地加剧了大规模网络中覆盖网络与物理网络的不匹配问题.为了缓解该问题,该文提出了一种基于测量的启发式拓扑匹配优化算法(Measurement-based Heuristic Topology Matching Optimization Algorithm,MHTMOA),该算法包括了节点加入、退出和失效算法,用于维护一个或者多个树形覆盖网络.该算法的主要优点在于:(1)通过网络测量技术获取底层物理网络中节点间的跳数信息,简单地利用跳数三角形的边长关系,就可有效地将相近节点逐渐地汇聚;(2)允许对跳数进行粗粒度的比较,并通过三角不等式违反(Triangle Inequality Violation,TIV)感知以及启发式规则选择邻居节点,每个节点最终可获得一个准确度较高的邻居节点集合;(3)在节点频繁加入、退出和失效的场景下,节点之间也能保持高一致性的近邻关系.除了传统的时延伸缩比(Latency Stretch,LS)外,该文还定义了全局拓扑匹配比(Global Topological Matching Ratio,GTMR)和局部邻居节点准确率(Local Neighborhood Accuracy,LNA)这两个量化指标,以便更精确地衡量拓扑一致性.评价结果表明,相较于现有算法,提议算法的GTMR和LNA提升显著,LS降幅可达53%,从而更好地缓解了拓扑不匹配问题.Topology mismatch between the overlay network and the underlying network is a critical problem in the complex and unstable network environment.The topology mismatch problem means that the virtual link between two nodes in the overlay network is not consistent with the physical link in the underlying network.It will impose an extraordinary amount of redundant traffic and affects both the scalability and the efficiency for Internet service.Resolving the mismatch problem is the key to improving the efficiency of addressing,eliminating redundant traffic,and reducing the end-to-end delay.With the continuous development of computer and communication technologies,the Internet grows into a large scale by magnitude,the geographical locations of the network nodes are widely distributed and the mobility of nodes and the dynamics of networks are greatly increased.The mismatch problem is becoming increasingly serious in environments where the dynamic network nodes join,leave or fail frequently.In order to solve the above problem,many researchers have investigated the overlay construction approaches.Some of them tried to get location information in the underlying network.When a new node joining in the overlay network,the neighbors would be selected according to the location information.However,most approaches are with fatal drawbacks.On the one hand,most of the existing approaches were lack of considering the hop as a major metric with its impact on construction,maintenance and evaluation to reflect the topological similarity and difference between global matching and local matching.On the other hand,few existing approaches took full advantages of the heuristic rules based on the Triangle Inequality Violation(TIV)by considering the topological consistency.In this paper,we propose a Measurement-based Heuristic Topology Matching Optimization Algorithm(MHTMOA)to alleviate the topology mismatch problem more effectively.The proposed MHTMOA includes nodes joining,leaving and failure processing methods to maintain one or more tree-ba

关 键 词：拓扑不匹配 覆盖网络 物理网络 网络测量 三角不等式违反 时延伸缩比 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]