论文部分内容阅读
Peer-to-Peer Systems(对等系统)作为一种新型的大规模分布式系统,正以前所未有的速度迅速发展,深刻地改变了个人计算的方式。而以Gnutella等为代表的P2P信息共享系统,凭借其庞大的用户群、海量交互数据,成为当今Internet最重要的P2P应用之一。该类全分布、非结构化的系统拥有良好的分布性、健壮性、易部署性,和对动态网络的适应性。但系统通常采用基于泛洪的广播搜索机制,引发了大量冗余的网络流量,严重阻碍了系统的可扩展性。
本论文以Gnutella协议作为P2P网络信息共享应用的研究实例,主要针对协议泛洪广播机制性能低下的突出问题,利用Gnutella网络拓扑内在属性,提出了改进的可适应性兴趣搜索算法,并对算法进行了详细的分析推导和性能测试。本论文的具体研究工作可分为以下几方面:
◇ 分析了Gnutella协议框架,主要包括数据结构、路由规则和工作原理。重点分析了Gnutella协议具有代表性的泛洪路由机制。通过泛洪广播的流量测度,量化分析了路由机制的低效性,为后续章节对搜索协议的改进、仿真实验做了良好的铺垫。
◇ 分析Gnutella网络拓扑内在的小世界(Small World)现象和兴趣簇集。详细分析了小世界现象的2个重要特征指标——簇集系数和特征路径长度,以及小世界现象在Gnutella网络中的存在。在此基础上,分析用户搜索行为引发形成的小世界兴趣簇集,为可适应性兴趣搜索算法的兴趣簇集策略提供了理论基础。
◇ 分析Gnutella网络拓扑内在的幂律(Power Law)属性。形式化验证了3条主要幂律及其对P2P网络拓扑的含义。该部分内容不仅是上一章工作的延续和补充,也为可适应性兴趣搜索算法的主干节点优先搜索策略给出了理论依据。
◇ 利用Gnutella拓扑结构内在的小世界和幂律特性,以及用户搜索社区中表现出的兴趣行为,本论文提出可适应性兴趣搜索算法,ASI(Adaptive Search with Interest),试图提高搜索质量,并减少搜索引发的流量代价。该算法包含兴趣簇集策略IBC(Interest-Based Clustering)和主干节点优先搜索策略HFS(I-Iub—First Search)两个组成部分。IBC策略能促进具有小世界特性的兴趣簇集的形成,并将搜索请求有意识转发给较有可能给出响应的那部分节点,同时也有效减少自身发出的无谓请求数。HFS策略利用节点能力的异构性,在簇集拓扑内挑选主干节点,并自组织成高度连通的主干节点簇集(hub cluster)。当查询需要扩散到其他局部簇集时,主干节点利用IBC策略积累的有关其他簇集的兴趣知识,针对性地将查询转发至相关簇集,提高了跨簇集查询的精确度。将以上两部分策略有机结合在一起组成的可适应性兴趣搜索算法,能同时改进搜索性能和搜索代价。基于可适应性兴趣搜索算法,进行了详细的性能测试。在不同网络参数条件下,进行了大量仿真试验,仿真结果表明:ASI算法表现出了良好的搜索性能,有效改进了Gnutella泛洪广播机制。
◇ 在源代码开放的JTella程序之上,利用其已有的网络功能和接口,对.JTella核心路由机制进行改进,将ASI算法实现为Java类库形式,供上层客户端程序调用。功能测试表明,其达到了最初的设计目标,并能与当前Gnutella协议兼容。
如何有效、可扩展的部署信息共享应用是当前P2P研究领域的主要课题之一。而搜索算法和路由转发机制无疑是其中的核心技术。本论文在着手改进Gnutella协议原有的泛洪广播机制时,充分考虑并利用了Gnutella网络当前的拓扑属性,从而提高了系统整体性能和可扩展性。由于泛洪广播机制在非结构化的P2P信息共享系统中的广泛使用,本论文的研究为该类系统的协议和算法设计做出了一些参考工作,具有一定的理论价值和实际应用意义。