【作者】 姜义；

【导师】 尤晋元；

【作者基本信息】 上海交通大学 ， 计算机软件与理论， 2007， 博士

【摘要】 在互联网发展日新月异的今天,对等网络系统扮演了越来越重要的角色。但是对等网络系统在被广泛应用的同时也占用了大量的互联网带宽。统计数据说明,目前互联网上的网络流量中有相当大的部分属于对等网络应用所产生的流量。进一步地研究发现,对等网络系统产生这么多网络流量的一个原因就是对等网络中有很多信息的传递是没有经过优化地。而使这些信息以非优化的形式传递的一个主要原因就是对等网络覆盖网和其下的物理网络之间的不匹配。简单的说就是覆盖网络对物理网络不敏感。本文对结构化对等网络覆盖网和非结构化对等网络覆盖网的网络敏感问题,以及与其紧密联系的网络坐标系统进行了研究。本文的主要贡献和创新点为:1.针对Vivaldi网络坐标系统的平均相对误差较小但是在计算较近节点之间的距离时误差较大的缺点,提出了通过对计算出的网络节点之间的距离进行补偿的方法来减小Vivaldi在计算较近节点之间距离的误差。减小了这个误差,也就提高了从一系列候选节点当中选择出最近邻节点的能力。实验证明,补偿后的Vivaldi在保持了原来平均相对误差较小的特点的情况下,提高了选择最近节点的能力。本文首先研究网络坐标系统的原因是网络坐标系统赋予了具有网络坐标的节点感知其在网络空间中的相对位置的能力,任意两个节点可以通过计算它们在网络坐标系统上的距离进一步判断它们在真实的物理网络上的延迟大小。2.针对非结构化对等网络覆盖网的网络敏感问题,提出了通过基于网络坐标系统的随机散步粒子群节点聚类算法来进行覆盖网络优化的方法。在研究对等网络覆盖网的网络敏感问题时的一个难点是如何设计一个分布式的算法来优化覆盖网络。本文通过粒子群算法来解决这个难题。这个算法的特点是使用虚拟的粒子代表节点在网络空间中运动,运动的方向通过粒子群算法来确定。通过计算出来的粒子运动向量来选择粒子在网络空间中的下一个运动目标。粒子在每访问一个节点时,都会使用适应度函数来计算它所经过的这个节点作为它代表的节点的邻居的可能性。在经过一定时间地运行后大部分的节点都可以找到合适的邻居。3.针对结构化对等网络覆盖网的网络敏感问题,提出了基于网络坐标系统的网络敏感的路由选择和网络敏感的路由表构建两种技术。对于结构化对等网络覆盖网具有固定的结构且路由表中的条目需要按照一定规则指向其它的节点的特点,首先在Chord覆盖网络中通过设计双向的路由表,在路由时将下一跳候选节点的数量由一变为二,并从中选取延迟较小者来降低路由延迟。对于网络敏感的路由表构建技术,本文在以异或距离作为覆盖网络中节点标号距离的异或网络上进行了研究。利用将下一跳的目标定义为包含目标节点的更小的子树的方式,使得路由表中的每一个条目可以在一个较大范围内选择任意一个符合条件节点。由于路由表中的每个条目都可在一个更大的范围内选择,因此可以选择更接近的节点加入路由表。经过理论分析和实验证明,在优化路由表的基础上结构化覆盖网络可以在保持原有路由时间复杂性的基础上降低路由时间。同时使得异或覆盖网络上的任意两个节点之间的路由延迟保持在一个较低的水平。而且这个路由延迟的期望值在一定程度上与覆盖网络的规模无关。更多还原

【Abstract】 Recently, peer-to-peer network applications play an important role in todays Internet. While the peer-to-peer technologies are widely used, the peer-to-peer applications occupied a large part of the Internet traffics according to the statistics. After further researching, it was found that one of the reason that caused those traffics is the non-optimization of the routing in peer-to-peer network. And this is because of that the overlay network is not match to the physical network underneath. That is to say the overlay network is not network-aware. This dissertation focused on some of the key technologies that make the peer-to-peer overlay network network-aware. Main contributions and creative points of this dissertation are as following.1. Considering the fact that there is an high relative error in computing the distance to near peers in Vivaldi while the average relative error remains low, a repaired Vivaldi is proposed. In the repaired Vivaldi, the relative error in computing the distance to near peers is decreased. The experiments show that the ability of choosing the nearest peer among neighbors is also improved in repaired Vivaldi with only little expense in the average relative error and relative rank loss rate. The reason why we dig into network coordinates system firstly is that most of the algorithms in this dissertation were make use of the network coordinates system. With the help of network coordinates system, any peer can aware of its relative position in Internet and can estimate the network latency to the other peer without probing.2. A new particle swarm based network nodes clustering algorithm is proposed in this dissertation. One of the difficulties of clustering the network nodes is how to cluster them distributively. The particle swarm algorithm solve the problem easily as the particles in network space exploring and exploiting the space independently. While particles flying they communicate and exchange the best fitness they found. So the particle swarm can find a better fitness quickly. The proposed algorithm is based on the facts that the network clustering algorithm is a algorithm that each node find a better cluster they belong to. So applying the particle swarm algorithm in network node clustering problem, we can cluster the network distributively.3. For structured peer-to-peer network overlay, reorganize the well organized nodes into a network-aware overlay is too difficult. In this dissertation, we propose a dual direction routing algorithm for Chord and a network proximity aware routing table protocol for more optimal routing. The dual direction routing algorithm for Chord can route the message in clockwise direction and counter clockwise direction too. Thus the average path length reduced to half of the original. Additionally, due to each of the step can be chosen from two candidate nodes, the expected forward latency reduced too. This paper also investigates the proximity routing table construction in a XOR metric based overlay network. In this overlay network, Nodes in the overlay network can be viewed as leafs, items in a routing table can be viewed as the pointers to the trees non-overlapped. So the routing table entries can be pointed to any node in the corresponding tree. Thus there are more candidate for the entry. The routing table entry can be optimized by choose one of the nearest node.更多还原