论文部分内容阅读
P2P网络因其突显的非中心化、可扩展性、健壮性、高性价比、负载均衡、隐私保护等特点和其特殊的体系结构得以迅速发展和应用。结构化网络采用分布式哈希表(DHT)技术,由查询关键字key直接定位其在分布式系统中的储存的节点位置,主要的应用有Tapestry、Pastry、Chord等本文其中本文重点研究Chord算法。Chord是一种结构化搜索方式,通过分布式哈希表(DHT)技术,将查询的关键字Key与节点标识(id)使用相容哈希[1]散列在同一地址空间中。同时,Chord采用了路由(finger)表的查询方式,使得每个节点在只需维护少量的节点信息的同时可以进行高效的查询。Chord路由算法具有负载平衡、健壮性、可扩展性、可用性、命名的灵活性等五个方面的优点,但其相应也存在节点的异构性导致的性能瓶颈、节点加入和离开带来的低效、模糊查询技术很难应用等缺点。Chord查询算法的改进一般是通过改进路由表结构或改变路由查询的方法,即是通过改善其路由表结构或者修改其查询算法。至目前,较为典型的对Chord协议的改进方法有F-Chord算法、PNS算法(Proximity neighbor selection)、Vivaldi定位算法等。由于修改路由表结构的方法在降低平均查询跳数与时间的同时通常增加了路由表长度,使得Chord在维护时占用更多的带宽且改善效果并不理想。本文通过分析Chord在查询过程中的路由特点,提出一种基于节点信息复制和查询热点的改进算法CH-Chord,即如果将节点的复制信息储存在其后继节点的方法变为储存在节点的前驱节点中,在进行Chord查询时,查询仍然按照原本的方法进行,但只需查询找到拥有查询key对应的信息或复制信息的节点便完成查询,同时再加入对查询热点的复制,并与并行查询的方式相结合。通过这样的改进,降低了查询跳数与路由时间,减少了查询失败且没有增加带宽消耗的效果。论文最后使用仿真工具P2PSim对改进算法CH-Chord进行仿真实验,并与传统的Chord算法和改进路由表的F-Chord算法进行对比,证明该算法在减少平均查询跳数与查询时间的同时并没有增加Chord稳定时的维护消耗。并且由于CH-Chord与并行查询结合,减少了因查询发起节点与目标节点网络无法连通导致的查询失败,降低了查询失败的数量。