计算机与现代化

• 网络与通信 • 上一篇    下一篇

一种不完全可测环境下的覆盖网络构造方法

  

  1. (1.中国科学院声学研究所国家网络新媒体工程技术研究中心,北京100190; 2.中国科学院大学,北京100049)
  • 收稿日期:2019-04-12 出版日期:2020-02-13 发布日期:2020-02-13
  • 基金资助:
    中国科学院战略性科技先导专项基金资助项目(XDC02010701)

A Topology Construction Method for Incompletely Measurable Networks

  1. (1. National Network New Media Engineering Technology Research Center, Institute of Acoustics, Chinese Academy of Sciences,
    Beijing 100190, China; 2. University of Chinese Academy of Sciences, Beijing 100049, China)
  • Received:2019-04-12 Online:2020-02-13 Published:2020-02-13

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

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

Abstract: Overlay network technology is popular in the research fields of next-generation Internet, the data center network of cloud, and software-defined network. The measurement-based overlay network construction technology can utilize the real-time network state data by active measurement techniques, which is benefit for the overlay network to adapt to the dynamics of network. However, the measurement-based overlay network construction methods also face the incompletely measurable problem, i.e., the global network status information required to be measured when the node joining cannot be completely measurable or it is difficult to get enough node information in a limited time, resulting in the failure of the node joining process. To solve this problem, this paper proposes a Topology Construction method for Incompletely Measurable (TCIM) networks. TCIM includes a high-precision node joining method and a low-complexity node joining method to construct a tree topology based on latency. In TCIM, the high-precision node joining algorithm uses the edge relationships of the latency triangle to select a suitable parent node for the node to join under small-scale or static/low-dynamic conditions; the low-complexity node joining method select constant number of nodes which have joined in the overlay network to measure and select the node with the smallest latency as the parent node, which can be used for large-scale, high-dynamic and network incomplete measurable conditions. The simulation results show that the tree-based overlay structure generated by TCIM has lower latency stretch comparing with state-of-art methods underdifferent network topology models, and TCIM has smaller topology maintenance cost in the Waxman and the BA graph model.

Key words: overlay network, topology construction, topology match, incompletely measurable, latency stretch

中图分类号: