论文部分内容阅读
对等（P2P）计算是近年来兴起的一种重要网络计算技术，在很多领域都有着大量的研究与应用。P2P资源定位技术是P2P计算中的基础性关键技术。P2P资源定位技术实现了P2P系统的拓扑构造、消息路由和资源搜索等基础功能，对P2P系统的可扩展性、鲁棒性和性能等都有着重要影响。与传统的分布式系统不同，P2P系统具有的规模巨大和动态性强等特点给P2P资源定位技术带来巨大挑战。根据拓扑结构，P2P系统可以分为结构化拓扑和非结构化拓扑两类。本文分别针对不同拓扑P2P系统的特点，对P2P资源定位技术及其应用展开深入研究。 分布哈希表（DHT）方法是结构化拓扑P2P系统实现资源定位的关键技术。目前很多研究都在试图提出常量度数高性能的DHT方法。与现有DHT方法使用的hypercube、de Bruijn和d-torus等拓扑相比，Kautz图拓扑具有最优网络直径等良好特性。本文首先对Kautz图的拓扑特性进行分析，证明了基于长路径路由的静态Kautz图是（1+o（1））拥塞的；然后首次基于Kautz图提出常量度数、O（logN）网络直径且（1+o（1））拥塞的DHT方法—FissionE。FissionE设计了一系列创新性的机制和算法，包括“邻居关系不变量”拓扑构造规则、Kautzhash命名算法和“局部优化”动态维护机制等，并对其进行了详细的理论分析与正确性证明。分析和模拟表明，FissionE方法具有良好的可扩展性、鲁棒性、负载平衡和性能。FissionE的平均结点度数为4，平均路由延迟小于log2N（N为系统中结点数目），动态维护开销小于3log2N，优于CAN和Koorde等同类DHT方法。 DHT方法通常只提供精确匹配的搜索能力。随着DHT方法的广泛应用，越来越多的系统对DHT方法的区间搜索能力提出了迫切需求。本文基于FissionE方法提出高效的DHT区间搜索技术—Armada。Armada针对单属性和多属性区间搜索的需求，分别提出维序命名算法Objecthash和Armadahash、区间搜索算法PIRA和MAPRA以及Balancing负载平衡机制等多个算法和机制，能够有效支持单属性和多属性区间搜索，并实现结点间负载均衡。Armada有效解决了通用架构DHT区间搜索技术中搜索延迟难以保证的难题，是第一个基于常量度数DHT的延迟有界的区间搜索技术：无论搜索区间的大小或属性值个数的多少，Armada都能确保在一定延迟（2log2N跳步）内返回所有搜索结果。Armada的平均搜索延迟小于log2N，单属性和多属性区间搜索的平均消息开销分别约为log2N+2n-2（n为返回搜索结果的结点数目）和log2N+4n-4，接近DHT区间搜索技术性能的理论下界，具有良好的性能。 Gnutella等非结构化拓扑P2P系统由于其简单性和易用性，在Internet上得到大量应用。但这些系统具有的拓扑结构非确定性和资源对象放置的随意性等特点，给资源定位技术带来了很大困难。本文针对非结构化拓扑P2P系统的特点，提出基于结点聚集的高效资源定位方法—CASP。CASP方法提出了“相似结点聚集”拓扑优化技术，能够在系统中形成主题相关的结点聚集，并提供到部分远程结点的快捷连接。CASP方法在各结点上维护压缩状态表来指导搜索请求的转发，通过搜索缓存来利用搜索请求的局部