摘要：覆盖网络技术是下一代互联网、云计算数据中心网、软件定义网络(Software-Defined Network,SDN)等研究领域的热门技术。基于网络测量的覆盖网络可基于实时网络状态数据构建,较好地适应网络的动态性。但该类方法也面临着网络状态信息不完全可测(Incompletely Measurable)的问题,即节点加入所需的全局信息难以测量或在有限的时间内难以获取足够的节点信息,导致部分节点间的网络状态信息缺失,无法顺利完成节点加入过程。为解决该问题,本文提出一种用于不完全可测网络环境的覆盖网络拓扑构造方法(Topology Construction method for Incompletely Measurable network,TCIM),基于时延构建树形拓扑结构。TCIM包含一种高精度节点加入方法和一种低复杂度节点加入方法,其中高精度节点加入算法利用时延三角形的三边关系,为节点选择合适的父节点,用于小规模或静态/低动态性条件下的节点加入;低复杂度节点加入方法在已加入的节点中,自适应选择常数个节点进行测量,选择时延最小的节点作为父节点,可用于大规模、高动态以及网络不完全可测条件下节点的加入。仿真结果表明,TCIM生成的树结构在不同的网络拓扑模型下时延伸缩比(Latency Stretch)均小于对比方法,在Waxman模型和BA模型下取得更小的拓扑维护代价,可通过合理设置TCIM中高精度节点加入和低复杂度节点加入数目构建树形覆盖网络,满足不同的拓扑维护代价和拓扑结构匹配准确度需求。

关键词：覆盖网络 拓扑构造 拓扑匹配 不完全可测 时延伸缩比 

单位：中国科学院声学研究所国家网络新媒体工程技术研究中心; 北京100190; 中国科学院大学; 北京100049