【作者】 任浩；

【导师】 王志英；

【作者基本信息】 国防科学技术大学 ， 计算机科学与技术， 2007， 博士

【摘要】 P2P计算是近年来兴起的一种重要的网络计算技术,它不依赖中心服务器,而是利用所有参与节点的计算能力和网络带宽构建的应用体系,具有鲁棒性好,可扩展性强,易于部署等特点。目前,P2P计算已经发展成Internet上最重要的应用模式之一,并成为近年来的研究热点。P2P覆盖网拓扑的特性是影响P2P系统服务质量的关键因素。首先,P2P系统具有强动态性,为保证应用稳定可靠,不会因节点的随意离开导致系统崩溃或服务质量明显下降,要求覆盖网拓扑具有良好的弹性,没有明显的缺陷。其次,资源搜索是P2P系统中最重要的操作,提高资源搜索效率能够显著改善系统的性能和可扩展性,而覆盖网的拓扑结构对资源搜索具有全方位的影响,拓扑优化是提高搜索效率的主要手段之一。因此,本文以提高系统可靠性和资源搜索效率为目标,对P2P环境下拓扑优化技术进行了深入研究。本文贡献如下:提出了一种P2P环境下被动式分布式割点发现算法,该算法仅依靠局部信息,可使P2P覆盖网中的每个节点自主判断自己是否为割点,并采取相应措施来消除对覆盖网连通性的危害。通过理论分析和模拟实验证明,该算法具有准确率高、开销低、自适应性强等优点。在静态网络中,它能够发现所有的割点,且普通节点被误判为割点的几率极低。在动态环境下,也能获得非常高的准确率。提出了一种P2P环境下分布式点割集发现和消除算法。该算法通过节点巧妙地计算其邻居间点不相交道路的情况,判定自己是否是割点或发现其所属的2点割,并采取修补措施来消除其对覆盖网的不利影响。实验证明,该算法准确率高,割集消除对提高覆盖网可靠性的效果显著。提出了一种基于连接选择的覆盖网拓扑优化算法ILS。ILS算法利用P2P文件共享应用呈现的基于兴趣的局部性特征,提出了节点间兴趣相似度评价模型和连接价值评价模型,通过动态自适应地在覆盖网中增加同兴趣节点间连接,删除低价值连接的方法,构成兴趣聚集。实验证明,ILS能使搜索在小范围内获得高成功率,显著缩短搜索响应时间,降低通信开销,与其它算法相比具有显著优势。提出了一种基于超立方体结构的P2P数据网格信息服务模型及拓扑优化算法。该算法能够用最多O(logN)的代价完成基于关键字的查找,并通过追踪访问的热点和调换节点位置,使得彼此访问量最大的节点在覆盖网中始终距离最近。分析和模拟证明,这种信息服务组织模式充分利用了数据网格的特点,能够有效保证服务性能和系统可扩展性,而自适应换位算法能大幅提高资源搜索效率。更多还原

【Abstract】 Peer-to-peer (P2P), an emerging model that relies primarily on computing power and bandwidth of participating peers instead of centralized infrastructures, is scalable, robust, and can be easily deployed. P2P computing is a promising architecture for distributed services over the Internet, and become the hottest topic of network computing in recent years.The topology of a P2P overlay network is the most important character which influences the performance of a P2P system. First, as a P2P system is highly dynamic, the resilience of overlay network is of great importance, so as to make sure that the system will not crash due to the peers’ leaving, and is not vulnerable to any attacks. Second, search is the most important operation in P2P environments. The efficiency of searching would determine the performance and scalability of a P2P system. The topology optimization is one of the major approaches for improving search efficiency. In order to improve the system’s reliability and search efficiency, we study the topology optimization in depth. The major contributions of this research are as follows.We propose a distributed cut vertex discovery and neutralization algorithm in P2P environment, which depends on local knowledge to enable every single node be able to determine whether it is a cut vertex or not, and adapt effective methods to clear up its badness to the network. We prove the correctness of this algorithm and evaluate the performance of our design through trace driven simulations. Our design is self adaptive, high veracity and with minimal overhead, and it can discover all cut vertices with very small proportion of the peers wrongly treated as cut vertex in static network. It is also highly accurate in active networks.We propose a distributed mechanism which efficiently detects the vertex cutset with 1 or 2 vertices and neutralize them into normal nodes, by smartly counting the number of disjoint paths between the neighbors of the selected peers. We evaluate the performance of our design through trace driven simulations. The results show that our algorithm greatly improves the reliability of an overlay network upon the failure of vertex cutset.We also propose a topology optimization algorithm ILS by link selection in Gnutella-like systems, to address the search efficiency problem by exploiting the principle of interest-based locality. We prove a model to evaluate the similarity of peers and value of the connections. Peers build new connections with others which have similar interests and disconnect those with minimal values. Our simulation study shows that ILS can significantly reduce the reply path lengths, achieving high search success rate, as well as reducing the total communication cost in unstructured P2P systems.We propose a novel model for Data Grid Information Service using a deterministic P2P based hypercube topology, which realizes the keyword-based searching in the cost of O(logN). Furthermore, we propose a transposition algorithm to optimize the overlay network’s topology according to the access statistics between peers, making the peers neighbors when they often visit each other. The simulation and analysis shows that our approach could sufficiently utilize the special character of Date Grid Information Service, and guarantee the QoS and scalability of the system effectively. Also, the transposition algorithm significantly improves search efficiency.更多还原