《论文基于对等模式的资源定位技术研究》由会员分享，可在线阅读，更多相关《论文基于对等模式的资源定位技术研究（5页珍藏版）》请在金锄头文库上搜索。
1、3论文题目论文题目：基于对等模式的资源定位技术研究中中 文文 摘摘 要要对等（P2P）计算是近年来兴起的一种重要网络计算技术，在很多领域都有着大量的研究与应用。资源定位是 P2P 系统中的基础性关键技术，对 P2P 系统的可扩展性、鲁棒性和性能等都有着重要影响。与传统的分布式系统不同，P2P 系统具有的规模巨大和动态性强等特点给资源定位技术带来巨大挑战。根据拓扑结构，P2P 系统可以分为结构化拓扑和非结构化拓扑两类。本文分别针对不同拓扑 P2P 系统的特点，对 P2P 资源定位技术及其应用展开深入研究。分布哈希表（DHT）方法是结构化拓扑 P2P 系统实现资源定位的关键技术。目前很多研究都在试
2、图提出常量度数高性能的 DHT 方法。与现有 DHT 方法使用的 hypercube、de Bruijn 和 d-torus 等拓扑相比，Kautz 图拓扑具有最优网络直径等良好特性。本文首先对Kautz 图的拓扑特性进行分析，证明了基于长路径路由的静态 Kautz 图是(1o(1)拥塞的；然后首次基于 Kautz 图提出常量度数、O(logN)网络直径且(1+o(1)拥塞的 DHT 方法FissionE。本文提出了一系列创新性的机制和算法，包括“邻居关系不变量”拓扑构造机制、Kautz_hash 命名算法和“局部优化”动态维护机制等，以有效优化 FissionE 拓扑，提高FissionE
3、方法的定位性能。文章对这些机制和算法进行了详细的理论分析与正确性证明。分析和实验表明，FissionE 方法具有良好的可扩展性、鲁棒性、负载平衡和性能。FissionE 的平均结点度数为 4，平均路由延迟小于 log2N（N 为系统中结点数目） ，动态维护开销小于3log2N，优于 CAN 和 Koorde 等同类 DHT 方法。FissionE 的提出表明对于常量度数、常量拥塞的 DHT 方法, 其网络直径可以是 O(logN)的, 优于国际学者 2004 年在重要学术期刊IEEE Journal on Selected Areas in Communications论文中猜想的下界 (N1
4、/d)。DHT 方法通常只提供精确匹配的搜索能力。随着 DHT 方法的广泛应用，越来越多的P2P 系统对 DHT 方法的高效区间搜索能力提出了迫切需求。但目前通用架构 DHT 区间搜索技术面临搜索延迟难以保证的难题。针对这一难题，本文基于 FissionE 方法，提出延迟有界的高性能 DHT 区间搜索技术Armada。Armada 无需对 FissionE 架构进行任何修改，能够支持高效的单属性和多属性区间搜索。为实现 Armada 单属性区间搜索，本文首先提出基于分区树的单属性维序命名算法 Single_hash，使得属性值接近的资源对象能够获得相近的标识，以发布到相同或相关的结点上；然后提
5、出基于前向路由树的单属性区间搜索算法 PIRA，实现了区间搜索路径与底层 FissionE 拓扑的高效匹配，以有效降低区间搜索延迟，减少搜索消息开销。在此基础上，本文提出基于多值分区树的多属性维序命名算法 Multiple_hash，设计多属性区间搜索算法 MAPRA，实现了延迟有界的多属性区间搜索。针对资源对象属性值分布不均等问题，本文提出基于属性值概率分布的 POBM 机制，可有效改善 Armada 的负载平4衡特性。Armada 有效解决了通用架构 DHT 区间搜索延迟难以保证的难题，是国际上首个基于常量度数 DHT 方法的延迟有界的区间搜索技术。无论搜索区间的大小或属性值个数的多少，A
6、rmada 都能确保在一定延迟（2log2N 跳步）内返回所有区间搜索结果。理论分析和实验表明，Armada 的平均搜索延迟小于 log2N，单属性和多属性区间搜索的平均消息开销分别约为 log2N + 2n 2（n 为返回搜索结果的结点数目）和 log2N + 4n 4，分别接近 DHT 区间搜索的延迟和消息开销的理论下界，具有良好的性能。类 Gnutella 的非结构化拓扑 P2P 系统由于其简单性和易用性，在 Internet 上得到大量应用。但这些系统具有的拓扑结构非确定性和资源对象放置的随意性等特点，给资源定位技术带来了很大困难。本文针对非结构化拓扑 P2P 系统的特点，提出基于结点
7、聚集的高效资源定位方法CASP。CASP 方法采用“相似结点聚集”的拓扑优化技术，能够在系统中形成主题相关的结点聚集，并提供到部分远程结点的快捷连接。CASP 方法在各结点上维护压缩状态表来指导搜索请求的转发，通过搜索缓存来利用搜索请求的局部性。分析和模拟表明，与受限泛洪、随机转发和 Neurogrid 等方法相比，CASP 方法通过维护少量的状态信息，能够在保持较低搜索延迟的同时，显著降低资源搜索的消息开销，从而提高类 Gnutella 的非结构化拓扑 P2P 系统的可扩展性和性能。副本定位服务是数据网格系统的核心组成部分，其功能是根据系统或应用需求有效地定位数据的一个或多个副本。如何提高副
8、本定位服务的可扩展性和自适应性，是大规模数据网格系统面临的重要难题。本文将 P2P 资源定位技术应用到数据网格的副本定位服务中，提出基于对等模式的自适应副本定位方法PSRL。PSRL 方法采用宿主结点来维护数据全部副本位置的索引信息（即副本目录） ，并根据宿主结点的加入或退出，将副本目录信息动态地均衡分布到各宿主结点上。本文提出基于 FissionE 的 FMRL 技术和基于轻索引的 IDMT 技术等技术来组织 PSRL 宿主结点和副本目录，并对两种技术进行详细的分析和比较。为提高PSRL 的容错能力，本文提出自适应的复制机制，可根据宿主结点变化动态地备份副本目录信息。分析和实验表明，PSRL
9、 方法可支持单副本和多副本定位，具有良好的可扩展性、自适应性、鲁棒性、负载平衡和实用性，能够高效提供可扩展自适应的副本定位服务。本文提出的多项技术已成功应用于虚拟计算环境的分布式资源信息服务、内存共享和数 据副本管理等组件中。关键词：对等计算 资源定位 结构化拓扑 DHT 方法 Kautz 图 拥塞 区间搜索 维序命名 非结构化拓扑 结点聚集 数据网格 副本定位Research on Resource Location in Peer-to-Peer Systems5ABSTRACTIn recent years, peer-to-peer (P2P) computing has become
10、 a popular network computing paradigm. Researches and applications of peer-to-peer computing have spread into many fields. Resource location is an important basic service in peer-to-peer systems, and it has very important influence on the scalability, robustness and performance of peer-to-peer syste
11、ms. Compared with other distributed systems, peer-to-peer systems exhibit some special characteristics, such as large-scale, dynamic, and heterogeneity, which have brought many challenging problems for peer-to-peer resource location technique. According to their topologies, peer-to-peer systems can
12、be divided into two categories: unstructured topology and structured topology. Based on characteristics of different topologies, this thesis deeply studies peer-to-peer resource location technique and its applications.Distributed hash table (DHT) scheme is the core technique to locate resources in s
13、tructured peer-to-peer systems. Currently many researches have concentrated on constant degree and high performance DHT schemes. Compared with the hypercube, the de Bruijn or the d-torus topology that used in existing DHT schemes, the Kautz graph has optimal diameter and other better properties. Thi
14、s thesis analyzes the properties of the Kautz graph, and proves that the Kautz graph with long path routing is (1+o(1)-congestion-free. Then this thesis proposes FissionE, the first effective DHT scheme based on the Kautz graph. FissionE is a novel constant degree, O(logN) diameter and (1+o(1)-conge
15、stion-free DHT scheme. Some novel algorithms and mechanisms are proposed, such as neighborhood invariant topology rule, Kautz_hash naming algorithm, and local optimum self-stabilization mechanism, to optimize the FissionE topology and improve the performance of FissionE, and they have been carefully
16、 investigated by the theoretical analysis and formal correctness proofs. Analysis and experiments show that FissionE can achieve good scalability, robustness, load balance and high performance. The average degree of FissionE is 4, the average routing delay is less than log2N (N is the number of peers in the system), and the maintenance cost is less than 3log2N. FissionE can achieve better performance than the related DHT scheme such as CAN and Koorde. FissionE shows th
