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