论文题目: 基于对等模式的资源定位技术研究
论文类型: 博士论文
论文专业: 计算机科学与技术
作者: 李东升
导师: 卢锡城
关键词: 对等计算,资源定位,结构化拓扑,方法,拥塞,区间搜索,维序命名,结点聚集,非结构化拓扑,数据网格,副本定位
文献来源: 国防科学技术大学
发表年度: 2005
论文摘要: 对等（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方法在各结点上维护压缩状态表来指导搜索请求的转发，通过搜索缓存来利用搜索请求的局部
论文目录:
摘要
ABSTRACT
第一章 绪论
§1.1 P2P计算概述
1.1.1 P2P计算的定义
1.1.2 P2P计算的历史
1.1.3 P2P系统的分类
1.1.4 主要应用领域
§1.2 P2P资源定位技术
1.2.1 P2P资源定位技术面临的挑战
1.2.2 P2P资源定位技术的发展
§1.3 本文工作
§1.4 论文结构
第二章 相关研究
§2.1 非结构化拓扑
2.1.1 典型系统
2.1.2 研究进展
§2.2 结构化拓扑
2.2.1 典型DHT方法
2.2.2 比较与分析
2.2.3 DHT方法研究进展
§2.3 本章小结
第三章 基于KAUTZ图的常量度数高性能DHT方法
§3.1 研究背景
§3.2 静态KAUTZ图与常量拥塞
3.2.1 静态Kautz图及其属性
3.2.2 常量拥塞
§3.3 FISSIONE方法设计
3.3.1 拓扑构造
3.3.2 资源对象的命名与发布
3.3.3 消息路由
§3.4 动态维护
3.4.1 结点加入
3.4.2 结点退出
3.4.3 并发加入和退出
3.4.4 容错路由和动态负载平衡
§3.5 理论分析
3.5.1 邻居关系不变量
3.5.2 命名算法有效性
3.5.3 路由正确性
3.5.4 性能特征
§3.6 模拟评估
§3.7 本章小结
第四章 延迟有界的DHT区间搜索技术
§4.1 研究背景
§4.2 ARMADA框架
§4.3 单属性区间搜索技术
4.3.1 单属性维序命名
4.3.2 属性值发布与区间搜索
4.3.3 负载平衡
4.3.4 算法分析
4.3.5 模拟评估
§4.4 多属性区间搜索技术
4.4.1 问题描述与定义
4.4.2 多属性维序命名
4.4.3 多属性值发布与区间搜索
4.4.4 分析与评估
§4.5 本章小结
第五章 非结构化拓扑高效P2P资源定位方法
§5.1 邻居选择
5.1.1 Bloom Filter技术
5.1.2 结点相似度
§5.2 状态表设计
5.2.1 状态表组成
5.2.2 资源搜索
5.2.3 状态表维护
§5.3 搜索缓存
§5.4 模拟评估
5.4.1 模拟环境
5.4.2 搜索延迟
5.4.3 消息开销
5.4.4 存储开销
5.4.5 更新开销
§5.5 本章小结
第六章 基于对等模式的数据网格副本定位服务
§6.1 数据网格中的副本定位问题
§6.2 相关工作
6.2.1 Globus副本目录
6.2.2 EDG副本目录
6.2.3 RLS框架
6.2.4 其它工作
§6.3 PSRL方法
6.3.1 系统结构
6.3.2 多副本定位
6.3.3 IDMT技术
6.3.4 PSRL更新
§6.4 分析与评估
6.4.1 理论分析
6.4.2 总体评估
§6.5 本章小结
第七章 总结与未来工作
致谢
攻读博士学位期间发表的主要学术论文
攻读博士学位期间参加的主要科研工作
参考文献
发布时间: 2006-09-22
参考文献
- [1].P2P网络资源定位关键技术研究[D]. 朱永琼.武汉大学2013
- [2].非结构化对等系统的资源定位技术研究[D]. 郑倩冰.国防科学技术大学2005
- [3].网格资源定位和任务调度的研究[D]. 李季.重庆大学2005
- [4].移动对等计算资源定位与分发技术研究[D]. 左克.国防科学技术大学2010
- [5].P2P资源共享系统中的资源定位研究[D]. 王淑玲.中国科学技术大学2012
- [6].基于局部网络信息的贪婪式P2P资源定位技术研究[D]. 马文明.北京邮电大学2013
- [7].非结构化对等网络资源定位技术研究[D]. 朱桂明.国防科学技术大学2010
标签：对等计算论文; 资源定位论文; 结构化拓扑论文; 方法论文; 拥塞论文; 区间搜索论文; 维序命名论文; 结点聚集论文; 非结构化拓扑论文; 数据网格论文; 副本定位论文;