论文部分内容阅读
近年来,结构化P2P系统以其低跳数的资源定位、路由确定性及平衡负载特性,成为学术界的研究热点。结构化系统都可以看作是由各种静态拓扑扩展而来,因此其基础结构始终面临着拓扑维护及拓扑参数优化的问题,并最终决定系统运作性能。而静态拓扑在P2P动态环境下的平滑嵌入要面临拓扑维护开销控制、拓扑虚拟化及优化网络直径等多个难题,本文以此为研究对象,定义和完善拓扑参数体系,从拓扑角度设计新的维护简单、性能优越的结构化P2P系统,并取得了一定的研究进展,主要贡献包括:
(1)提出了适用于动态P2P环境的概率平衡树的拓扑形式,不遵循层次的完全平衡,只遵循层次的概率均等,使树出现不平衡状态的可能性很小。节点位置转变为局部信息,使得新节点加入排除了对全局平衡信息的需求,在分布式环境下具有很好的可扩展性。
(2)提出了基于匹配路径和概率平衡树的结构化P2P系统MPPBTree。以概率平衡trie树作为拓扑组织形式,以很高的概率实现常数度数O(d)下的网络直径下界O(log/N);通过随机接入方法实现节点加入,避免了平衡树的高额维护成本;用过载转移方法提供细粒度的负载转移支持。与同类其它P2P系统相比,MPPBTree以相对较低的维护成本和较强的数据负载平衡机制,达到了较高的路由效率和查询灵活性。
(3)提出了新的常数度数静态拓扑结构HL<,2>D<,2>图,HL<,2>D<,2>图结合de Bruijn图D(2,D)和2维Hypercube连接,是一个拓扑参数优化、性能优越的静态拓扑结构,在最长路径路由下,具有常数度数、对数直径、常量拥塞和容错绕路的性质。
(4)提出了基于HL<,2>D<,2>图的常数度数且常量拥塞的DHT P2P系统VHL<,2>D<,2>。VHL<,2>D<,2>结合de Bruijn链接和hyper链接进行查询路由,使用hyper链接进行容错路由,采用2步长的倾向性随机游走实现动态维护时的待分裂域选择,保证了全局流量及域面积均衡化。VHL<,2>D<,2>也实现了O(d)度数下的优化网络直径O(logN);与其它常数度数P2P系统相比,VHL<,2>D<,2>拥有更小的网络直径、更快的新节点定位过程及较强的容错路由能力。
(5)提出了P2P拓扑参数抽样统计方法和评价策略。首先提出一种基于信息熵的P2P拓扑参数抽样统计随机测度方法,定义链接熵以表征节点链接的总体分布,然后针对常数度数网络,以链接熵为抽样测度基准,提出四种可操作性较强的抽样方案,以VHL<,2>D<,2>拓扑为实例对象,考察了不同抽样策略对拓扑参数的抽样性能并作了简要分析。