A Network-Positioning Algorithm Based On Node-Clustering

The large-scale network systems are running and are employed within the all world scope, for example, peer-to-peer file share system, overlay network multicast and distributed content hosting services. These large-scale Internet applications can benefit from some routing selection methods and neighbor node selection algorithms. This is because the metrics of network performance have inpect on the large-scale network service systems, like the latency and bandwidth. How to measure these metrics efficently is userful to improve the performance of these large-scale network services. In the real Internet, unfortunately, measurement explicitly is impractical because the measurement of large number of end-to-end connection is too time-consuming and too costly, which may bring high overhead. To resolve this problem, we can predict network distance instead of measuring in the real network, which will reduce the overhead for measurement greatly. Some methods for predicting network distance have already been proposed. Among these methods, network coordinate methods are proved to be simple and useful. Network coordinates can indicate the positions of hosts in the network, and in some sense can indicate the topology of the network as a result.This paper presents a network positioning algorithm based on node-clustering, called Dumpling, which contains two core mechanisms: The nodes clustering and network coordinate holistically moving. Dumpling aims at accelerating the speed of error converge, reducing the numbers of explicit measurement and easing the situation of system fluctuation. We not only analyzed the Dumpling's performance from the perspective of theoretics, but also simulated experiments to verify that Dumpling can achieve the above three goals。In the end, we devised a simulant experiment to test the combination of Dumpling's two mechanisms. The result shows Dumpling can also get better efficiency in the circumstances of true network topology. Dumpling is a distributed algorithm for network positioning, which has the advantages of less overhead for computation and communication. Dumpling can also be applied easily into Internet applications.