学位论文 > 优秀研究生学位论文题录展示

基于Chord查找算法的P2P系统研究

作　者: 赵丽敏
导　师: 沈鸿
学　校: 北京交通大学
专　业: 计算机科学与技术
关键词: Chord 物理拓扑 Counting Bloom Filter 蚂蚁优化算法 双向查找
分类号: TP393.02
类　型: 硕士论文
年　份: 2014年
下　载: 8次
引　用: 0次
阅　读: 论文下载
 

内容摘要


Peer-to-Peer：简称P2P)技术的核心思想是所有参与的节点在地位上是平等的,各节点在享受来自其它节点服务的同时也向其它节点提供服务。换而言之该技术并不区分客户机和服务器,各个节点不只是客户机还是服务器,这种模式使互联网中的资源被广泛发掘和利用,已经在各个领域得到了广泛应用。P2P系统的最大挑战是在没有中心服务器的情况下,高效的查询和资源定位。目前这方面的研究都集中在结构化的路由算法上,其中Chord算法因简单易实施,良好的鲁棒性和扩展性等优点成为国内外研究的热点。本文首先对P2P网络的理论基础进行简要概述,简单分析P2P网络的四种拓扑结构,并介绍了它们的经典模型Napster、Gnutella和KaZaa,然后介绍全分布式结构化拓扑下基于分布式哈希(DHT)技术的四种经典资源查找算法,并着重描述了Chord查找算法。传统Chord查找算法的一个明显的缺点,是没有考虑P2P网络的物理拓扑结构,以致其查找过程的网络延迟较大。除此之外,存储空间的问题也很少被考虑。为弥补这些缺陷,本文的研究工作如下：1.针对传统Chord物理拓扑和逻辑拓扑不匹配的问题,结合蚂蚁优化算法和双向查找技术的优点,我们提出了一种基于蚂蚁优化算法的双向查找Chord算法。首先,利用蚂蚁优化算法建立Chord环,解决物理拓扑和逻辑拓扑不匹配的问题,在此基础上,使用双向查找方法,进一步加快查找速度。实验结果表明,该算法比传统的Chord算法有更高的查找效率。2.针对物理拓扑和逻辑拓扑不匹配以及空间复杂度的问题,结合Counting Bloom Filter技术和基于位置查找算法的优点,我们提出一种基于Counting Bloom Filter和物理拓扑的Chord查找算法。首先,Counting Bloom Filter用于数据存储,以减少空间复杂度,然后,用基于物理拓扑的方法,解决物理拓扑和逻辑拓扑不匹配的问题,进一步加快资源定位的速度。实验结果表明,该算法能够进一步节省存储空间并提高查找效率。3.在路径长度、存储空间、查找跳数方面,将三种方法进行对比,验证两种改进方法各自的优缺点。

全文目录


致谢  5-6
摘要  6-7
ABSTRACT  7-12
1 引言  12-22
  1.1 研究背景与意义  12-13
  1.2 P2P网络的研究现状  13-19
    1.2.1 中心化拓扑  14-15
    1.2.2 全分布式非结构化拓扑  15-16
    1.2.3 全分布式结构化拓扑  16-17
    1.2.4 半分布式拓扑  17-18
    1.2.5 四种P2P拓扑结构的比较  18-19
  1.3 论文的主要工作  19-21
  1.4 本章小结  21-22
2 基于DHT的算法研究  22-31
  2.1 CAN  22-23
  2.2 Tapestry  23-24
  2.3 Pastry  24
  2.4 Chord  24-30
    2.4.1 标识符空间  24-25
    2.4.2 路由表  25-26
    2.4.3 路由查找  26-27
    2.4.4 节点的加入和退出  27-28
    2.4.5 国内外研究现状  28-29
    2.4.6 Chord算法存在的问题  29-30
  2.5 本章小结  30-31
3 基于蚂蚁优化算法的双向查找Chord算法  31-42
  3.1 蚂蚁优化算法  31-34
    3.1.1 蚂蚁算法的基本思想  31-33
    3.1.2 蚂蚁优化算法生成Chord环的过程  33-34
  3.2 向资源定位  34-39
    3.2.1 向资源定位算法的基本思想  34-35
    3.2.2 向路由表的构建  35
    3.2.3 向查找过程  35-39
  3.3 实验结果展示  39-41
    3.3.1 路径长度  39
    3.3.2 存储空间  39-40
    3.3.3 查找跳数  40-41
  3.4 本章小结  41-42
4 基于Counting Bloom Filter和物理拓扑的Chord算法  42-56
  4.1 Bloom Filter  42-45
    4.1.1 Bloom Filter集合表示  42-43
    4.1.2 Bloom Filter元素插入  43
    4.1.3 Bloom Filter元素查询  43
    4.1.4 假阳性(False Positive)  43-45
  4.2 Counting Bloom Filter  45-47
    4.2.1 Counting Bloom Filter核心思想  45-46
    4.2.2 Counting Bloom Filter元素表示  46-47
  4.3 基于物理拓扑的Chord算法  47-51
    4.3.1 基本思想  47-48
    4.3.2 相关术语  48-49
    4.3.3 资源定位  49-50
    4.3.4 Chord的维护  50-51
  4.4 实验结果展示  51-55
    4.4.1 路径长度  52-53
    4.4.2 存储空间  53-54
    4.4.3 查找跳数  54-55
  4.5 本章小结  55-56
5 实验结果展示  56-59
  5.1 路径长度  56-57
  5.2 存储空间  57
  5.3 查找跳数  57-58
  5.4 本章小结  58-59
6 结论与展望  59-61
  6.1 研究工作总结  59
  6.2 有待改进的问题  59-60
  6.3 今后工作展望  60-61
参考文献  61-64
作者简历  64-66
学位论文数据集  66

相似论文

  1. P2P数据副本问题的研究与实现,TP393.02
  2. 基于物理拓扑感知的Chord算法研究,TP393.02
  3. 结构化P2P网络资源搜索算法研究,TP393.02
  4. 面向空间矢量数据的P2P索引网络路由机制的研究,TP393.02
  5. 基于Chord和Bloom Filter的网格信息服务研究,TP393.09
  6. 结构化对等网络的搜索机制研究,TP393.02
  7. 基于P2P模式的普适服务发现策略的研究,TP393.02
  8. 大规模混合层次化P2P网络仿真,TP393.02
  9. 基于Chord的对等网拓扑结构及搜索算法研究,TP393.02
  10. P2P系统中资源搜索定位机制的研究,TP393.02
  11. 战场环境下基于P2P的上下文搜索研究,TP393.02
  12. 网络拓扑发现技术研究,TP393.02
  13. 基于P2P的异构即时通讯系统的研究与实现,TP393.09
  14. 基于P2P机制的网格资源查找模型—层次式Chord环,TP393.02
  15. 基于P2P-SIP的VoIP关键技术研究,TN916.2
  16. 基于P2P网络的矢量地理数据组织与索引技术的研究,P208
  17. P2P网络中资源搜索算法的研究,TP393.02
  18. 基于P2P的物联网信息发现服务的研究,TN929.5
  19. 基于chord的查找算法的研究和改进,TP393.02
  20. 基于IMS的P2P网络电视系统架构的研究,TN949.292
  21. 结构化P2P覆盖网设计与搜索机制研究,TP393.02

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机的应用 > 计算机网络 > 一般性问题 > 计算机网络结构与设计
© 2012 www.xueweilunwen.com