常量度P2P系统中复杂搜索技术研究

论文摘要

近年来,基于对等结构（Peer-To-Peer,P2P）的分布式系统在互联网上广泛的流行起来,成为了当前占据Internet主要流量的应用之一。基于分布哈希表（Distribute Hash Table,DHT）的结构化系统是P2P系统的重要组成部分,系统中的各个节点通过某种规则相互链接,形成具有一定拓扑结构的网络,具有较高的查询效率。常量度P2P系统作为一种新型的结构化系统,具有邻居节点个数为常数而查询效率为O（LogN）的特性。常量度P2P系统能有效地减小系统维护开销,简化系统结构,但同时也面临着容错、数据负载平衡、路由负载平衡等方面的问题。如何解决常量度系统所面临的这些问题,是一个值得深入研究的课题。此外,由于P2P系统中往往具有着巨大的节点规模和节点在地理上广泛分布的特点,因此在大规模P2P环境下的资源搜索面临着两个重要的性能指标:搜索效率和网络负载。高效的搜索有利于减小搜索的延时,提高用户的满意度;而较低的网络负载有利于减轻网络流量,减小营运商的成本。特别是在P2P环境下进行复杂搜索时,面临着搜索效率和消息开销的性能折衷问题:优化其中一个往往使得另一个表现出较差的性能。进行复杂搜索时,如何在保持搜索效率的同时减小网络的消息开销将对网格系统、服务组合等应用具有现实的推动作用。针对上述问题,本文首先拓展了CCC[1]网络结构,为每个节点增加3个邻居节点,从而形成新的常量度P2P重叠网络,它在负载平衡、路由效率等方面表现出新的特性。在该系统的基础上,本文围绕复杂搜索中的区间搜索和Top-K搜索两个问题展开研究,提出了针对这两个问题的搜索算法,对算法进行的理论分析和实验模拟表明这两种算法具有较高搜索效率和较低的网络负载。论文的主要贡献主要包括:（1）本文在CCC（Cube-Connected-Cycle）网络结构的基础上,提出了一种新的常量度P2P网络—Cactus。该系统中每个节点的邻居节点数为6,而在节点规模不超过d×2d的情况下,查询效率为O（d）,其中d是CCC网络的维度。本文阐述了Cactus的拓扑构造、路由算法以及容错机制,并对相关实验及其结果进行了分析。实验表明Cactus在查询效率、负载平衡、容错性等方面均不逊于现有的常量度数的P2P系统。特别是与已有的容错算法相比,在节点非正常离开系统的情况下,Cactus采用了“反馈式”容错算法,使节点恢复邻居关系的消息个数从log2N减小到3logN,时间开销从logN减小到2步,从而使得系统具有较强的容错能力。（2）本文在Cactus常量度系统基础上,设计了一种Smart-Broadcast算法。该算法根据被搜索区间的范围,动态建立一棵虚拟搜索树。该搜索树的结构与Cactus系统的底层拓扑结构相匹配,并使得被搜索的节点都聚集在根节点附近,从而使得单值区间搜索的消息开销为O（d）,而平均路由开销不超过O（d）+（1+3/d）m,其中m是被搜索区间内所有映射到的节点。本文描述了Smart-Broadcast算法,并在该算法的基础上设计了多属性区间搜索算法。对算法进行理论分析和模拟实验证实Smart-Broadcast算法在大规模节点的情况下,具有较小的消息开销和路由开销。（3）本文在Cactus系统和区间搜索算法的基础上,提出了一种Top-K搜索算法—IES（Iterative Estimate Range-size）。算法根据资源属性,将资源看作是m维空间中的点,而Top-K搜索就转换为在m维空间中搜索距离查询点最近的k个点。该算法根据Agrawal发现的资源密集现象,在m维空间中确定搜索区间大小,并利用Cactus的多区间搜索算法,迭代地在多个区间中搜索资源,使得算法同时保持了高效和低负载的特点。本文证明了算法的正确性并分析了它的性能。分析和实验表明,该算法在高属性维度、低查询维度的情况下,具有较好的查询效率和较低的网络负载。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 P2P 计算概述
• 1.1.1 P2P 系统的发展历史
• 1.1.2 P2P 系统的特点
• 1.1.3 P2P 系统的分类
• 1.2 结构化P2P 面临的挑战
• 1.2.1 容错性
• 1.2.2 系统维护开销
• 1.2.3 复杂搜索
• 1.3 本文工作
• 1.4 论文结构
• 第二章 相关研究工作
• 2.1 完全分布式P2P 系统的研究现状
• 2.1.1 非结构化P2P 系统
• 2.1.2 结构化P2P 系统
• 2.2 常量度P2P 系统
• 2.2.1 问题描述
• 2.2.2 相关工作
• 2.3 区间搜索技术
• 2.3.1 问题描述
• 2.3.2 相关工作
• 2.4 P2P 环境下Top-K 搜索技术
• 2.4.1 问题描述
• 2.4.2 相关工作
• 第三章 基于CCC 结构的常量度系统
• 3.1 Cactus 系统结构与路由算法
• 3.1.1 系统结构
• 3.1.2 路由算法
• 3.2 节点的自适应性
• 3.2.1 节点加入
• 3.2.2 节点退出
• 3.3 容错算法
• 3.3.1 反馈式容错算法
• 3.3.2 叶节点抢占算法
• 3.4 性能评价
• 3.4.1 平均路由长度
• 3.4.2 数据负载平衡
• 3.4.3 路由负载
• 3.4.4 容错性
• 3.5 小结
• 第四章 区间搜索技术研究
• 4.1 单值区间搜索算法
• 4.1.1 单属性值映射与发布
• 4.1.2 动态搜索树
• 4.1.3 单区间搜索算法
• 4.2 多属性区间搜索算法
• 4.2.1 多属性值映射与发布
• 4.2.2 多属性区间搜索算法
• 4.3 算法分析
• 4.4 模拟实验
• 4.4.1 不同策略的比较
• 4.4.2 与其他系统的路由开销比较
• 4.4.3 与其他系统的消息开销比较
• 4.5 小结
• 第五章 Top-K 搜索技术研究
• 5.1 基于区间查询的Top-K 搜索
• 5.1.1 基于区间查询的简单Top-K 搜索算法
• 5.1.2 IES（Iterative Estimate Range-size）搜索算法
• 5.2 IES 算法在Cactus 系统中的实现
• 5.3 算法正确性与性能分析
• 5.3.1 算法正确性
• 5.3.2 性能分析
• 5.4 系统评价
• 5.4.1 资源密集度与网络开销
• 5.4.2 属性个数与网络开销
• 5.4.3 系统规模与网络开销
• 5.4.4 查询效率
• 5.5 小结
• 结束语
• 致谢
• 参考文献
• 缩略语表
• 作者在学期间取得的学术成果
• 作者在学期间参加的科研工作