【作者】 李丁丁；

【导师】 陈浩；

【作者基本信息】 湖南大学 ， 计算机应用， 2008， 硕士

【摘要】 大规模的网络服务应用系统已经在全世界的范围内得到运行和使用,例如:P2P文件共享系统、覆盖网络多播系统以及内容分发服务系统。这些大规模的网络应用系统能够从一些性能较好的路由选择算法以及邻居结点选择算法中获益。这是因为延迟和带宽等网络性能参数与大规模网络应用密切相关,测量这些网络性能参数值将对这些算法性能的提高有帮助。然而,在真实的网络环境下,由于大规模网络应用存在数量巨大的端到端连接,如果对每一个连接都进行测量,则会带来巨大的物理开销和时间消耗。为了解决这个问题,可以通过一定的算法来预测端到端的网络距离,而不用在真实的网络环境里进行测量,这样可以极大的减小网络开销。当前已经出现了一些网络定位算法来预测网络结点间的距离,在这些算法当中已经证明了网络坐标是简单并且实用的。网络坐标能够表示出网络中某个主机的位置,并且从某种意义上来说,还能够表示网络的拓扑结构。本文提出了一种基于结点聚类的网络定位算法——Dumpling算法。该算法包括了两个核心机制:结点聚类机制和整体坐标移动机制。Dumpling算法致力于在更短的时间内对虚拟坐标空间中的误差进行收敛;在更少的显式测量内收敛更多的系统误差;尽量避免虚拟坐标系统的波动现象给带来的定位精度的影响。除了从理论上分析了Dumpling的优势外,本论文还经过仿真实验表明,Dumpling可以较好的达到上述三个目标,并且在最后的Dumpling整体性能测试中,表明Dumpling在真实的网络拓扑下,也能达到一定的效果。Dumpling是一个分布式的虚拟网络坐标定位系统,具有计算量少、通信开销低等优势,还能够与具体应用程序相结合。更多还原

【Abstract】 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.更多还原