论文部分内容阅读
P2P技术是自上世纪末兴起的一种网络计算技术,强调所有节点具有对等的功能,与传统分布式计算技术(如C/S、B/S等)相比更能充分利用和发挥网络边缘、闲散资源的能力,从而引起了从工业界、学术界到普通网络用户的广泛关注。常数度P2P系统采用第三代结构化P2P技术,常量级的节点度数保证了系统在实现高效路由的同时具备稳定性强、控制信息少、网络负载小等优点,在近几年逐渐成为P2P领域的后起之秀和研究热点。然而,由于作为系统拓扑基准的各种常数度图定义相对严格,现有相关研究多集中于系统设计、构建与维护,针对上层应用的优化与支持研究相对较少,这很大程度制约了常数度P2P的应用与发展。本文将对常数度P2P系统的负载均衡与拓扑优化技术展开深入研究,针对尚未解决的以下四个关键问题提出解决方案:如何构建均衡的拓扑。所有DHT方法中均包括ID分配方法来为新加入节点选择合适的ID。作为实现与维护DHT overlay的基础,理想的ID分配方法有利于系统负载均衡,保证ID在命名空间的均匀性。然而,常数度图de Bruijn与Kautz的移位路由特性决定了不能采用已有方法进行ID分配,而且为实现正确与高效路由,常数度P2P系统必须保证拓扑中节点ID长度尽量相同。本文提出基于Routing Forest结构的一种常数度DHT ID分配方法。利用该结构中非叶节点聚合拓扑局部均衡信息,通过参考该信息,新加入节点采用一种ID二次分配算法选择合适的ID以保证全局节点均衡,从而有机地结合了常数度拓扑结构特点,利用较低的消息开销与节点加入开销保证了最优的拓扑直径,控制拓扑中ID长度差在2以内,达到了良好的拓扑均衡效果,并且可以方便地扩展为DHT构建、维护及负载均衡技术。如何实现数据负载的均衡。负载均衡是避免个别节点存储过载成为系统瓶颈,确保系统发挥其性能的重要保证,然而,已有方法或者不能动态适应不同的负载分布,或者平衡开销过大,或者不能满足常数度P2P对均衡拓扑的要求。针对该问题,本文结合常数度P2P的特点提出基于路由信息统计的负载均衡算法。其基本思想是通过路由过程进行信息统计,并结合虚拟节点与负载重定向技术实现负载均衡。具体包括:1)在节点加入过程中统计得出系统中节点平均能力,将强能力节点划分为相应数量的虚拟节点,并基于反向生成树将各虚拟节点快速均匀地加入系统,从而利用低开销保证了节点负责空间的大小正比于其能力;2)在数据加入过程中依据路由路径中所有节点的负载信息确定数据对象是否需要及如何重定向存储,并针对热点数据提供了构造新加入路由路径的方法,从而利用少量消息开销实现了不同数据分布下各节点轻载或具有相同的负载率。实验表明,该算法的节点加入开销小于虚拟节点技术,而且利用更少量的数据重定向及消息开销实现了比多散列技术更好的均衡效果。如何使系统支持以区间查询为主的复杂查询。越来越多的应用要求结构化P2P系统不再仅限于关键字查询,而且能够提供各种复杂查询能力。数据局部性是支持结构化P2P复杂查询的重要条件,然而特殊的节点命名与路由方式使得沿用经典构建方法的常数度P2P系统数据局部性不佳,导致复杂查询的消息开销与节点占用率过大。针对这一问题,本文从P2P的逻辑构建过程进一步分析数据局部性,然后在不改变底层DHT拓扑结构的前提下,从改善数据局部性出发提出一种通用的面向高效复杂查询的常数度P2P构建优化方法,通过在数据层与DHT overlay间添加嵌入变换逻辑层,将拓扑结构信息引入构建过程以改善数据局部性。同时为验证该技术的有效性,采用此技术重构第一个基于Kautz图的DHT——FissionE,并在此基础上设计了相应的数据节点匹配、资源重分配、区间查询及局部性维护等算法。分析与实验结果表明,该方法可以在不改变底层DHT或增加类前缀哈希树(PHT)的新逻辑层次的基础上确保数据在P2P系统中分布的局部性,有效优化复杂查询,达到减少复杂查询节点交互开销、提高常数度P2P系统查询效率的目的。如何构建延迟匹配的常数度P2P拓扑。延迟匹配技术通过使overlay与物理网络尽量匹配以减少节点通信开销和路由延迟。然而,由于常数度图的特殊标识与路由方式等原因,已有的各种匹配技术并不能直接用于常数度P2P系统。针对该问题,本文提出面向延迟匹配的层次化拓扑构建方法CO-FissionE。在CO-FissionE中,节点首先聚类成簇并组成低层FissionE overlay,然后由“下界重合”规则确定高层的簇间链接以保证高效的簇间通信。该规则同时限定了簇间邻居的最大值,因此选取常数度拓扑作为簇间overlay便能够确保各节点度数仍为常数量级。同时,针对内部存在层次化结构的簇,提出子簇融合方法以高效构建符合其延迟特点的层次化结构。其思想在于一定程度上放松簇中高层拓扑的均衡要求以减少重定向节点的数量,同时有效利用已加入节点信息来引导未加入节点。理论分析与实验表明CO-FissionE通过有限开销有效地实现了与底层网络的延迟匹配,降低了查询开销,而且子簇融合方法能够在保证簇内部延迟匹配的同时大大提高融合效率。CO-FissionE方案既保留了原有FissionE常数度拓扑在逻辑路由上的优点,又增强了数据通信的本地性,提高了系统的管理与路由效率,而且其思想可以应用到其他常数度P2P或者结合其他优化技术。