论文部分内容阅读
P2P网络的应用越来越多地受到了人们的关注。现在,P2P网络面临的关键问题就是如何准确快速并且全面地定位共享资源。不同的P2P网络采用的拓扑结构也各不相同,它们的查询效率也各不一样。本文分析了一种完全分布式结构化拓扑结构网络模型—Chord模型。Chord模型采用了一致性哈希算法,以分布式散列表为查找策略。在Chord模型中,每个节点只需维护O(logN)条节点路由信息便可快速地定位共享资源。Chord算法在很多方面体现出了一定的优势,如:很好的负载均衡、高可靠性、高可扩展性等。但是,由于哈希算法的使用,Chord算法不支持多关键字查询,因此也不能全面地定位到共享资源。针对Chord算法的不足,本文提出了一种改进Chord算法。在改进的Chord算法中,放弃了通过一致性哈希算法得到共享资源标识的机制,采用了Bloom Filter算法来获取资源标识,但是仍然使用一致性哈希函数来获得节点标识。各个节点和资源不是按照各自标识的大小顺时针排列在Chord环上。在本文中,首先把Chord环分段,其次把各个节点和资源根据标识中1bit的个数映射到Chord环中的不同段内,然后按照整数标识的大小,由小到大顺时针地排列在Chord环的段内。当查找共享资源时,首先跳转到对应的Chord环段内,然后根据资源标识的最长后缀匹配进行查找。为了更加快速地定位到共享资源,每个节点存储了更多节点的路由信息。首先,论文假设改进Chord算法中各个节点都存在,不存在的节点标志为虚拟节点,虚拟节点只负责路由信息的转发。各个节点根据自身的二进制向量标识就可推测出自己的路由表信息。路由表信息获取机制是通过自身的二进制向量标识,交换二进制向量标识中高位的0bit和低位的1bit。改进Chord模型不仅仅支持多关键字查询,本文还理论证明了改进Chord算法的最大查询跳数为m–2+1,平均查询跳数为m/2+1,其中m为二进制标识的长度,远远地优于标准Chord算法。最后,对改进Chord算法进行了仿真验证。主要从以下四个方面进行了评估:平均查询跳数、平均查询时延、Bloom Filter错判率和查询时节点的覆盖率。仿真结果与理论相一致,在允许一定错判率的情况下,改进Chord算法明显优于标准Chord算法。