支持多关键字查询的改进Chord算法

来源 :重庆大学 | 被引量 : 0次 | 上传用户:milo999
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
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算法。
其他文献
随着信息化时代的来临,互联网中各种结构化(如web页面)以及半结构化(如电子邮件,XML网页)文本数据规模呈现指数级增长并伴着信息存储技术的飞速发展而累积了海量的文本数据。海量文
随着XML数据库的蓬勃发展,XML文档存储、索引、查询的研究成为热点。由于XML数据具有分支结构多,数据冗长的特点,这给数据的存储和查询带来了极大的不便。因此,如何对XML文档进行
作为下一代Web发展的蓝图,语义Web是目前互联网技术中研究的热点。本体在语义Web体系结构中,位于从文档描述到知识推理的转折层,是语义Web实现的核心技术。随着对本体研究的深入
随着计算机和网络技术的飞速发展,越来越多的人们开始在网络上搜索他们所需要的信息。然而,在网络上,许多的广告和不相关的链接嵌入在所需的信息中,使有用信息很难从无用信息中分
目前人们对信道中传输的语音质量、编码率要求日益增加,同时对语音实时传输的需求愈发强烈。尤其在某些实时性要求比较高的场合,如海底、太空等传输环境,更迫切需要减少语音信号
非刚性图像配准问题是计算机视觉和模式识别领域一个很基本也很重要的研究内容,而基于特征点的非刚性图像配准方法在医学图像、军事自动目标识别、卫星图像和数据编辑分析等
近年来,语义网被愈来愈多的关注,而语义推理一直都是语义网的核心问题,当前已经开发出了多个推理机,但其在查询推理性能上无法完全满足工业界应用。相比较语义查询,关系型数据库发
随着近些年计算机和计算机网络规模的迅猛发展与普及,互联互通科学技术的进步,网络终端的成本逐步下降,而计算能力、存储能力和网络带宽迅速增长,为对等网络(Peer-to-Peer,简称P2P)
随着“云计算”和“物联网”概念的出现和应用,网络计算技术不断向物理世界延伸和拓展。这些具有规模化网络资源和多样化服务特点的互联网新型应用的出现,要求必须研究新型网络
学位