高阶Chord：一种新型P2P查找策略

论文题目: 高阶Chord：一种新型P2P查找策略

论文类型: 硕士论文

论文专业: 计算机应用技术

作者: 温忠智

导师: 吕光宏

关键词: 查找算法,高阶,仿真

文献来源: 四川大学

发表年度: 2005

论文摘要: 近几年来对P2P 的研究迅速升温,各方面的应用层出不穷。特别是它提供无穷的存储空间以及不受限制的传输容量,这是传统中央服务器所无可企及的。P2P 网络中的节点既是服务使用者,也是服务提供者。节点之间通过分布、对等的算法实现协作和共享。这样,整个网络应用的核心从中央服务器向网络边缘的终端设备扩散。目前因特网以网站为中心的状态终将彻底改变,人们将会以更主动的方式参与到网络活动中去。从C/S 模式到P2P 模式的发展,Internet 上的共享行为被提升到了一个更高的层次。这对我们解决很多难题都是一个良好契机,在分布计算、协同工作、搜索引擎、文件交换等方面有着广泛的应用前景。所有这些P2P 应用面临的最核心问题就是如何在没有中心节点的情况下完成资源的查找,并且能保证查找过程的高效性、可靠性、可伸缩性。目前的方案主要分成两类:洪泛算法(Flooding)类和基于分布式哈希表(DHT)的方法。Flooding 算法以Gnutella 为代表。Gnutella 曾经有过不少用户,但是人们很快就发现随着网络规模的增长,四处广播的数据报很快就会把网络带宽耗尽。虽然在Flooding 基础上也有很多文章提出各种控制广播流量的算法,但是终究很难应付随节点数目增长而呈指数增长的系统开销。所以目前很多研究都集中在基于DHT 的方法上。利用DHT 实现的查找算法比较多,比较知名的包括最早的Plaxton 算法及其变种Tapstry,微软提出的Pastry,伯克立和AT&T 提出的CAN 等等。特别是MIT 提出的Chord 算法在网络节点变化剧烈的环境中仍然具有较好的性能。这一点非常重要,因为现实中P2P网络的节点自治性必然导致网络结构频繁变动。在这些恶劣条件下能保持较高的查询效率才是最重要的。

论文目录:

摘要

Abstract

第1章 绪论

1.1 背景

1.1.1 P2P 网络的发展

1.1.2 P2P 网络的现状

1.2 P2P 网络中的资源查找

1.3 本文所作的工作

第2章 P2P 网络中的资源定位

2.1 洪泛算法

2.1.1 Gnutella

2.1.1.1 Gnutella 的报文结构

2.1.1.2 Gnutella 的路由规则

2.1.1.3 Gnutella 的运行情况

2.2 基于DHT 的算法

2.2.1 Tapestry

2.2.2 Pastry

2.2.3 CAN

2.2.4 Chord

2.2.4.1 Chord 的地址空间

2.2.4.2 Chord 的查找过程

2.2.4.3 节点的加入和离开

2.3 本章小结

第3章 新的资源查找策略:高阶Chord

3.1 Chord 的性能瓶颈

3.2 对Chord 的查询消息路由的分析

3.2.1 节点饱和假设

3.2.2 路由表结构

3.2.3 未取模前的successor 序列

3.2.4 取模后的环形结构

3.2.5 Chord 的路由效率

3.3 新的查找策略

3.3.1 三阶Chord 路由表结构

3.3.2 三阶Chord 的路由表指针模型

3.3.3 三阶Chord 的性能

3.3.4 k 阶Chord 的性能

3.4 本章小结

第4章 新算法的仿真

4.1 仿真软件设计原理

4.1.1 未来事件列表

4.1.2 仿真时钟及其推进机制

4.1.3 系统的状态变量

4.1.4 事件进程

4.1.5 随机数发生器

4.1.6 仿真结果的输出和分析

4.1.7 系统调度模块

4.2 网络仿真的一般步骤

4.3 仿真的实现

4.3.1 p2psim 的结构

4.3.2 高阶Chord 仿真程序

4.3.2.1 ChorFinger 类的构造函数

4.3.2.2 初始化处理ChorFinger::initstate()

4.3.2.3 路由表维护ChorFinger::fix_fingers()

4.3.2.4 稳定化处理ChordFinger::stabilized()

4.3.2.5 节点离开处理ChordFinger::oracle_node_died()

4.3.2.6 节点加入处理ChordFinger::oracle_node_joined()

4.4 仿真条件设置

第5章 结果分析

5.1 模拟查询次数和成功率

5.2 平均查询时间

5.3 10%分位时间

5.4 中位线时间

5.5 90%分位时间

5.6 小结

第6章 结论和展望

参考文献

攻读学位期间发表的学术论文

申明

致谢

发布时间: 2005-10-17

参考文献

• [1].基于Chord的P2P搜索模型研究与改进[D]. 李杨.西安电子科技大学2011
• [2].P2P网络中Chord搜索算法的改进与实现[D]. 解哲.吉林大学2008
• [3].基于Chord算法的结构化P2P网络改进研究[D]. 王挺.陕西师范大学2015
• [4].P2P网络中Chord算法的改进研究[D]. 曹磊.陕西师范大学2013
• [5].基于Chord查找算法的P2P系统研究[D]. 赵丽敏.北京交通大学2014
• [6].P2P网络Chord资源定位算法改进[D]. 吴晓亮.华中科技大学2012
• [7].结构化P2P网络Chord协议的研究与改进[D]. 王庆民.东北大学2010
• [8].基于改进Chord协议的P2P系统研究[D]. 袁赟.湖南大学2010
• [9].P2P网络Chord算法研究与改进[D]. 李志鹏.北京邮电大学2009
• [10].P2P网络Chord协议的分析与研究[D]. 汪发宝.西南交通大学2010

相关论文

• [1].一种改进的Chord查询策略[D]. 严由慧.暨南大学2007
• [2].基于Chord的P2P查询方法的研究[D]. 刘冰.郑州大学2006
• [3].P2P网络路由算法的研究及Chord协议算法的改进[D]. 孙珊珊.吉林大学2007
• [4].对等网中Chord协议及算法的研究及改进[D]. 徐乾.哈尔滨工程大学2007
• [5].Chord网络的搜索方法研究[D]. 董晓刚.山东师范大学2007
• [6].DR-Chord：一种高效的双环Chord协议的研究[D]. 于少山.新疆大学2007
• [7].基于Chord协议的P2P网络模型及其搜索技术研究[D]. 李红玉.广西大学2007
• [8].基于Chord的P2P模型在VoIP中的应用研究[D]. 汤剑君.华中师范大学2006
• [9].基于结构化节点ID的Chord协议研究及应用[D]. 王占民.北京邮电大学2006
• [10].对等网络Chord查找算法改进方案的研究与应用[D]. 杨科伟.北京邮电大学2006

标签：查找算法论文;  高阶论文;  仿真论文;