（计算机应用技术专业论文）基于dht的结构化p2p路由协议chord的研究.pdf

北京邮电大学硕士学位论文 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 ，、。工1 本人签名：i 生虚盘 日期：迦f q12 ：l 翌 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：互避 本人签名：$ 盔瞄 导师签名：显壁签! 日期：塑! ! ： ：! 里 基于d h t 的结构化p 2 p 路由协议c h o r d 的研究 摘要 目前对等网络面临的重要问题就是如何高效的定位网络中的资 源，基于d h t 的结构化路由算法的提出使这一问题得到了相对优化的 解决方案。 本文针对典型结构化p 2 p 路由协议c h o r d 展开研究。c h o r d 利用 分布式散列表作为查找策略的基础，具有负载平衡、可靠、可扩展性 等诸多优点。对比第一代路由算法，由于f i n g e rt a b l e ( 即查找表) 的 提出，c h o r d 大大改善了查找效率，然而当网络中存在低性能节点时， c h o r d 仍然存在一定的低效性。 针对c h o r d 的不足，通过分析c h o r d 协议的基本算法和理论，本 文提出了两种新的路由查找策略，针对查找方式及网络布局提出了以 下几方面的改进：。 ( 1 ) 针对c h o r d 协议本身的单路查找过程，采用发起点并行发起 多条查询请求，进行并行查找定位，经由不同的路由路径定 位目的节点，通过降低经由低性能节点的概率，提高资源定 位效率，降低查找延时。 ( 2 ) 在不增加节点负荷的前提下采用v i v a l d i 捎带协议，记录节 点间的物理延时，增加逻辑节点对物理延时的感知，从而在 选择查找路由时综合逻辑及物理网络状况选取最优节点，达 到降低查找时延的目的。 最后，基于p 2 p s i m 仿真平台，通过对比原始协议及改进后的协 议，说明改进的正确及有效性。仿真结果表明，改进协议一定程度上 的提高了资源定位的效率，降低了查找时延。通过仿真看出，以上各 种修改方式相辅相成，各有优势，针对不同的应用场景满足相应的应 用需求。 关键词：对等网络c h o r d 路由查找v i v a l d i 仿真 北京邮电大学硕士学位论文 r e s e a r c ho nc h o r dp r o t o c o l i ns t r u c t u r e dp 2 pn e t w o r k c u r r e n t l y ，t h ek e yp r o b l e mi np e e r - t o - p e e rn e t w o r k i sh o wt ol o c a t et h er e s o u r c e s e f f e c t i v e l y t h ep r o p o s a lo fr o u t i n ga l g o r i t h mb a s e do nd h t h a si m p r o v e di tal o t t h ep a p e rf o c u s e so nd e t a i l e dr e s e a r c hi n t o t y p i c a ls t r u c t u r a lp 2 pr o u t i n g a l g o r i t h m - c h o r d ，a n a l y s e si t sb a s i cc o n c e p t sa n dc h a r a c t e r i s t i c s o nt h i sb a s i s ，p r o p o s e s o m ei m p r o v e m e n t so nr e s o u r c e sl o o k u p ，a i m i n ga td e c r e a s i n gt h el a t e n c yo fr e s o u r c e l o c a t i o na n d o p t i m i z i n gt h el o o k u pm o d e t h ef i r s to p t i m i z a t i o nc o m e st ot h ei m p r o v e m e n to fl o o k u pm o d eo fo r i g i n a l c h o r d s i n c ec h o r di m p l e m e n t s s i n g l el o o k u pm o d e ，w h e nt h e r e a r es o m el o w e f f i c i e n c yn o d e si n t h en e t w o r k ，t h e yw i l la f f e c tt h el o o k u pe f f i c i e n c yt e r r i b l ya n d c a u s ch i g hl a t e n c y s ow ep u tf o r w a r dp a r a l l e ll o o k u pm o d e t h i sw i l ld e c r e a s et h e p r o b a b i l i t yo fr o u t i n gf r o mb a dn o d e sa n dt h e ni n c r e a s et h el o o k u pe f f i c i e n c y t h es e c o n do p t i m i z a t i o ni sa p p l y i n gv i v a l d it oc h o r d t h r o u g ht h es e n s i t i v i t yo f p h y s i c a lt o p o l o g y ，o p t i m i z et h el o o k u ps t r a t e g y i no r d e rt ov e r i f yt h ec o r r e c t n e s so ft h et h e o r ym o d i f i c a t i o n ，w eu s et h ep 2 p s i m p l a t f o r mt os i m u l a t ea n dc o m p a r et h eo r i g i n a lp r o t o c o la n dt h ea m e n d m e n tp r o t o c o l s b yt h ep a r a m e t e r so fp e r f o r m a n c e i ti n d e e dp r o v e st h a tt h ea m e n d m e n tw a y sc a n e f f e c t i v e l yi m p r o v ee f f i c i e n c yo fr e s o u r c e sl o o k u po fc h o r dp r o t o c 0 1 s i m u l a t i o n e x p e r i m e n t ss h o wt h a tt h ei m p r o v e m e n t se m p h a s i z ep a r t i c u l a r l yo nd i f f e r e n tp o i n t s ， a n ds u p p l e m e n te a c ho t h e r i no n ew o r d ，t h e s em e t h o d s 啪t oac e r t a i ne x t e n tp r o m o t e t h ee f f i c i e n c yo fr e s e a r c h i n gr e s o u r c e s k e yw o r d s ：p e e r - t o - p e e rn e t w o r k , c h o r d ，r o u t i n gl o o k u p ，v i v a l d i ，s i m u l a t i o n 北京邮电大学硕士学位论文 目录 第一章绪论1 1 1 理论背景。1 1 1 1p 2 p 技术的发展1 1 1 2i 2 p 网络技术的现状2 1 2p 2 p 网络的分类。3 1 2 1 集中式p 2 p 网络3 1 2 2 分布式p 2 p9 网络3 1 2 3 混合式p 2 p 网络。4 1 3 论文的研究内容及组织结构4 第二章p 2 p 网络中的资源定位算法6 2 1 散列函数理论基础6 2 1 1 散列函数的性质一6 2 1 2 常见的散列函数分类6 2 1 3 分布式散列表( d h t ) 简介8 2 2 基于d h t 的p 2 p 路由算法。9 2 2 1p a s t r y 9 2 2 。2t a p e s t r y 1 0 2 2 3c a l 、i 1 0 2 3c h o r d 路由协议分析。1 0 2 3 1 协议概览1 0 2 3 2 常用术语解释1 1 2 3 3 地址空间1 2 2 3 4 资源查找算法1 3 2 3 5 节点的加入退出。一1 5 2 3 6c h o r d 协议特点分析1 7 2 3 7 几种典型的对c h o r d 协议的改进1 8 2 4 本章小结1 8 第三章c h o r d 查找方式的改进1 9 3 1 改进的着眼点1 9 3 2 并行c h o r d 1 9 北京邮电大学硕士学位论文 3 2 13 p - c h o l i l 。：1 0 3 2 2h p - c h o r d 2 1 3 3v c h o r d 2 1 3 3 】【v i v a l d i 2 1 3 3 2v i v a l d i 与c h o r d 的结合2 5 3 43 p v c h o r d 2 6 3 5 本章小结一2 6 第四章协议仿真方法2 7 4 1 仿真软件的设计原理2 7 4 1 1 未来事件列表2 8 4 1 2 仿真时钟及其推进机制2 9 4 1 3 系统的状态变量2 9 4 1 4 事件进程2 9 4 1 5 随机数发生器2 9 4 1 6 仿真结果的输出和分析2 9 4 1 7 系统调度模块。3 0 4 2 网络仿真的一般步骤3 0 4 3 仿真工具的选择3 1 4 4p 2 p s i m 3 3 4 4 1p 2 p s i m 简介3 3 4 4 2p 2 p s i m 系统结构3 3 4 4 3 改进协议的仿真原理3 6 4 4 4 仿真参数说明3 6 4 5 本章小结3 7 第五章仿真结果及分析3 8 5 1 对协议代码的改进3 8 5 2 仿真及结果分析。3 9 5 2 1 仿真条件3 9 5 2 2 经典c h o r d 的仿真结果分析3 9 5 2 33 p c h o r d 的仿真及结果分析4 1 5 2 4h p c h o r d 的仿真及结果分析4 2 5 2 5v c h o r d 的仿真及结果分析。4 4 5 2 63 p v c h o r d 的仿真及结果分析4 5 5 3 本章小结4 6 v 第六章总结及展望。 6 1 前期工作总结。 6 2 预期工作展望 北京邮电大学硕士学位论文 1 1 理论背景 第一章绪论 1 1 1p 2 p 技术的发展 p 2 p 技术在近年来得到了广泛的发展，己成为i n t e r n e t 中重要的应用技术之 一，显示出了强大的发展潜力，吸引了越来越多的研究机构和团体加入到这个 研究领域。随着因特网和信息技术的发展及计算机硬件性能的更新，共享并利 用分布于世界各地的计算机上的信息和资源日益受到关注。基于对等网络的信 息定位及共享技术更是得到了广泛的关注。 对等网络( p e e r t o - p e e rn e t w o r k ，简称p 2 p ) 是一种用于不同计算机之间， 不经过中继设备直接交换数据或服务的技术。在对等网络中，每个节点的地位 都是相同的，如图1 - 1 所示，具备客户机和服务器双重特性，可以同时作为服务 使用者和服务提供者。 图1 - 1 p 2 p 网络结构示意图 对等网络并不是一个全新的概念，早在2 0 世纪7 0 年代，源于局域网中文 件共享的对等网络技术就开始出现，其典型代表是u s e n e t 和f d i o n e t 两个分 散、分布的信息交换系统。实际上，互联网的存在基础- t c p 礤协议本身并 没有客户机和服务器的概念，参与通信的设备处于平等地位。在互联网发展的 初期，p c 设备的性能很有限，另外出于对网络的易管理性和安全性的考虑，c s 模式逐渐发展成为互联网中最流行的计算模式并得到了广泛应用。到了2 0 世纪 9 0 年代末期，随着互连网技术的飞速发展和网络用户的急剧增加，c s 模式的 弊端日益显现：服务器要同时为网络中的众多客户机提供服务，极易成为性能 瓶颈；服务器的处理能力决定了系统的最大负载，可扩展性差：服务器的单点故 障会导致系统瘫痪，容错性差与此同时，p c 机的性能按照摩尔定律飞速发展， 现在充当客户机的p c 性能已经达到甚至超过了早期的大型主机，客户机在请求 北京邮电大学硕士学位论文 其它机器服务的同时也具备了向其它机器提供服务的能力。于是人们意识到是 否可以通过发掘客户机的计算能力，充分利用整个网络的计算资源；通过弱化 甚至取消服务器，消除系统瓶颈，改善系统性能这就导致了对等网络技术的 复兴。 1 1 2p 2 p 网络技术的现状 与其他网络相比，p 2 p 1 】网络具有明显的优势： ( 1 ) 分散化。网络中的资源和服务分散在所有节点上，信息的传输和服务的 实现都直接在节点之间进行，可以无需中间环节和服务器的介入，避免了可能 的瓶颈。由此带来了p 2 p 网络的健壮性及高可扩展性。 ( 2 ) 可扩展性。在p 2 p 网络中，随着用户的加入，不仅服务的需求增加了， 系统整体的资源和服务能力也在同步地扩充，始终能较容易地满足用户的需要， 整个体系是全分布的，因而摆脱了对服务器的依赖。 ( 3 ) 健壮性。p 2 p 架构具有耐攻击、高容错的优点。由于服务是分散在各个 节点之间进行的，部分节点或网络遭到破坏对其它部分的影响很小。而且p 2 p 模型一般在部分节点失效时能够自动调整整体拓扑，保持其它节点的连通性。 ( 4 ) 隐私性。在p 2 p 网络中，由于信息的传输分散在各节点之间进行，无需 经过某个集中环节，用户的隐私信息被窃听和泄漏的可能性大大缩小。 ( 5 ) 高性能。采用p 2 p 架构可以有效地利用互联网中散布的大量普通节点， 将计算任务或存储资料分布到所有节点上。利用其中闲置的计算能力或存储空 间，达到高性能计算和海量存储的目的。这与当前高性能计算机中普遍采用的 分布式计算的思想是一致的。通过利用网络中的大量空闲资源，可以用更低的 成本提供更高的计算和存储能力。 近年来，随着对等网络技术被广泛的运用到文件交换，对等计算，协同工 作，实时通信，信息检索，广域网络存储等多个领域，关于对等网络的理论研 究也成为了国内外计算机学术界关注的一个热点问题。在对等网络环境中，所 有的节点都是平等的，不存在像c s 模式中服务器这样专门提供发现服务的角 色，因此如何高效准确的实现网络资源的查找无疑是对等网络理论研究必须解 决的核心问题，因而在众多研究领域中，针对查找算法的研究具有格外重要的 意义。针对查找算法的现有研究大致可归为四类，分别是以n a p s t e r l 2 1 1 3 】为代表的 集中式查找算法；以g n u t e l l a l 4 】为代表的非结构化分布式查找算法；以c h o r d 5 】 为代表的结构化分布式查找算法和以k a z a a 6 l 为代表的混合式查找算法。与集 中式查找算法相比，分布式查找算法彻底取消了服务器的角色，更符合对等网 络的需求。结构化分布式查找算法克服了非结构化分布式查找算法使用泛洪机 制查找而导致的网络可扩展性差的弊端，具有更好的发展潜力和研究价值。 2 。o o o 。o o o o o o - o _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 北京邮电大学硕士学位论文 1 2p 2 p 网络的分类 从结构【7 l 上来区分，p 2 p 网络大致可以分为三大类，如图1 2 所示。 图1 - 2 p 2 p 网络分类图 1 2 1 集中式p 2 p 网络 集中式p 2 p 网络有一个中心服务器负责记录共享信息以及响应对信息的查 询。它采用中央服务器管理p 2 p 各节点，p 2 p 节点向中央目录服务器注册关于 自身的信息，但所有内容存储在各个节点中而并非服务器上，查询节点根据目 录服务器中信息的查询以及网络流量和延迟等信息来选择与定位其它对等节点 并直接建立连接，而不必经过中央目录服务器进行。这种形式的网络具有中心 化的特点，但它与传统意义上的c s 模式网络又有所区别。传统意义上的c s 模式采用的是服务器垄断的手段，所有资源都放到服务器上，客户端只能被动 地从服务器上得到资源信息，而且客户端之前不能交互。而集中式p 2 p 网络则 是所有资源都分别存放在提供该资源的客户机上，服务器只保留对资源的索引 信息，而且客户端与客户端可以直接进行交互。采用集中式p 2 p 形式的软件被 称为第一代p 2 p 。 集中式p 2 p 网络的优点在于有效提高了网络的可管理性，使得资源的查找 和更新相对于c s 式网络更为方便，很多流行p 2 p 应用仍然部分采用了该结构。 主要原因在于这些服务都不能摆脱统一的管理，但对中心目录服务器的依赖， 也使得它的稳定性不够强。 1 2 2 分布式p 2 p 网络 分布式p 2 p 网络也称纯p 2 p 网络它没有集中的中央目录服务器，每个用 户可以随机接入网络，并与自己相邻的一组邻居节点通过端到端连接构成一个 逻辑覆盖的网络。分布式p 2 p 网络又可分为全分布式非结构化p 2 p 网络和全分 布式结构化p 2 p 网络。 全分布式非结构化p 2 p 网络采用随机图的组织方式来形成一个松散的网络 3 北京邮电大学硕士学位论文 网络中，每个节点都是平等的地位，既是客户端又是服务器。对等节点之间的 内容查询和内容共享都是直接通过相邻节点广播接力传递，同时每个节点还会 记录搜索轨迹，以防止搜索环路的产生。纯p 2 p 网络结构解决了网络结构中心 化的问题，不需要服务器的支持，在网络规模较小的时候具有很高的查询效率， 扩展性和容错性较好。由于没有一个对等节点知道整个网络的结构，网络中的 搜索算法多采用以泛洪的方式进行，随着网络规模不断增大，会给网络带来沉 重的负荷，导致整个网络的可用性较差，另外也比较容易受到垃圾信息、甚至 是病毒的恶意攻击。 全分布式结构化p 2 p 网络的关键在于资源的定位和有效查找，它多采用分 布式散列表( d h t ) 进行节点的统一映射和管理。典型的分布式结构化拓扑如 c h o r d 、c a n 等。 1 2 3 混合式p 2 p 网络 混合式p 2 p 网络结构结合了分布式p 2 p 去中心化和集中式p 2 p 快速查找的 优势，按用户节点的能力不同( 计算能力、内存大小、连接带宽、网络滞留时 间等) 进行分类，使某些节点担任特殊的任务。区分为普通节点( 普通用户节 点) 和超级节点( 处理部分请求) 两类。普通节点不具有特殊的功能。超级节 点与其临近的若干普通节点之间构成一个自治的簇，簇内采用集中式目录结构， 已达到资源节点的快速定位；簇间则采用分布式p 2 p 结构，增强整个网络的稳 定性和健壮性。当用户发出查询请求之后，普通用户节点首先在本地所属的簇 内进行搜索，当查询结果不充分的时候，就向相邻的搜索节点发出请求，如果 查询还不充分，就继续向外快速发散，直到所有的搜索节点都被搜到。这样就 极为有效地消除纯p 2 p 结构中使用泛洪算法带来的网络拥塞、搜索迟缓等不利 影响。同时，由于每个簇中的超级节点监控着所有普通节点的行为，能确保一 些恶意的攻击行为能在网络局部得到控制，在一定程度上提高整个网络的负载 平衡。 1 3 论文的研究内容及组织结构 通过对典型p 2 p 路由算法的分析发现，如何高效地定位资源节点，降低查 找时延是制约p 2 p 系统性能的关键，同时也是p 2 p 技术发展的瓶颈之一。本文 在对经典c h o r d 协议进行详细分析论述的基础上，讨论了几种更为优化的资源 查找策略。仿真实验结果表明，两种修改方法各有侧重点，相辅相成，能够在 很大程度上提高查找资源的效率，降低查找时延 论文共分为六章，第一章介绍论文理论背景及研究内容第二章从理论上 介绍了基于d h t 的多种典型p 2 p 路由协议，特别对c h o r d 协议的基本理论及特 4 北京邮电大学硕士学位论文 性进行了着重分析，引出论文工作的着眼点。第三章针对c h o r d 协议的查找效 率问题，提出了几种改进方法，并进行了理论上的论述证明。第四章介绍了仿 真软件的设计原理和一般步骤，详细介绍用于改进协议仿真证明的工具 p 2 p s i n l 【8 j 。第五章针对协议改进的部分进行仿真试验，得出仿真结果，并对实 验数据进行分析，说明了对协议进行改进后查找效率确实得到了优化。第六章 对整篇论文作总结以及明确未来完成的工作，并对p 2 p 网络的发展做出展望。 5 北京邮电大学硕士学位论文 第二章p 2 p 网络中的资源定位算法 2 1 散列函数理论基础 散列函数 9 1 提供了一种从任何数据中创建小的数字( f i n g e r ) 的方法：它以 一个变长的报文作为输入，通过产生一个定长的散列码，即报文摘要，作为输 出。这个散列值是该报文的所有位的函数，同时提供了错误检测能力：报文中 的任何一位或多位的变化都将导致该散列值的变化。 2 1 1 散列函数的性质 所有的散列函数都具有一个共同的基本性质：如果两个散列值是不相同的 ( 根据同一个函数) ，那么这两个散列值的原始输入也是不相同的。这个特性 使散列函数具有确定性的结果。具体性质包括： ( 1 ) h ( 散列函数) 可以作用于一个任意长度的数据块。 ( 2 ) h 能产生一个固定长度的输出。 ( 3 ) 对任何给定的x ，h ( x ) 计算相对容易，无论是用硬件或者软件都能实 现。 ( 4 ) 对任何给定的码h ，寻找x 满足h ( x ) = h 在计算上是不可行的( 单向性) 。 ( 5 ) 对任何给定的数据块，寻找不等于x 的y ，使得h ( y ) = h ( x ) 在计算上是 不可行的。有时也将这一特性称为弱抗冲突。 ( 6 ) 寻找任何的( x ，y ) ，对满足h ( x ) = h ( y ) 在计算上是不可行的。有时也将 这一特性称为强抗冲突。 性质( 1 ) 到( 3 ) 要求散列函数具有实用性，性质( 4 ) 表现为单向性质， 即给定消息可以产生一个散列码，而给定散列码不可以产生对应的消息。性质 ( 5 ) 保证了一个给定的消息的散列码不能找到与之相同的另外的消息，即可用 于防止伪造。性质( 6 ) 是对已知的生日攻击方法的防御能力。 2 1 2 常见的散列函数分类 散列函数主要用于完整性校验和提高数字签名的有效性，目前已有很多方 案。这些算法都是伪随机函数，任何散列值都是等可能的。输出并不以可辨别 的方式依赖于输入；在任何输入串中单个比特的变化，都会导致输出比特串中 大约一半的比特发生变化。 2 1 2 1m d 4 报文摘要算法 目前主流的散列算法均由m d 4 演进而来，它由r o nr i v e s t 设计最早作为 r f c 在1 9 9 0 年1 0 月发表【埘 6 北京邮电大学硕士学位论文 m d 4 算法主要包括： ( 1 ) 附加填充比特。对报文进行填充，使它的长度符合一定的规范。 ( 2 ) 附加长度值。将初始报文( 填充前) 的位长度附加在步骤( 1 ) 的结 果 后( 低位字节优先) ( 3 ) 初始化m d 缓存。该缓存用来存放散列函数的中间及最终结果。 ( 4 ) 用固定长度对报文进行分组。用多个循环来处理报文分组序列。 ( 5 ) 输出。所有的分组处理完成后，最后阶段产生的输出便是结果。 m d 4 之后的散列算法步骤上基本与m d 4 一致，只在关键的步骤( 4 ) 上采 用的循环次数以及核心压缩算法有所不同。 2 1 2 2m d 5 算法 1 9 9 1 年，r i v e s t 开发出技术上趋近成熟的m d 5 1 1 】算法。它在m d 4 的基础 上增加了“安全一带子 ( s a f e t y b e l t s ) 的概念。虽然m d 5 比m d 4 稍微慢一 些，但是更为安全。这个算法很明显由四个和m d 4 设计有少许不同的步骤组成。 在m d 5 算法中，信息一摘要的大小和填充的必要条件与m d 4 完全相同。 d e nb o e r 和b o s s e l a e r s 曾发现m d 5 算法中的假冲突，但除此之外就没有其它被 发现的加密结果了。该算法以个任意长度的报文作为输入，产生一个1 2 8 位 的报文摘要作为输出。输入是按5 1 2 位的分组进行处理的。 2 1 2 3s h a - 1 算法 s h a - 1 1 2 】【1 3 j 安全散列算法是不可逆的、防冲突的，并具有良好的雪崩效应。 s h a - 1 是一个联邦信息出版号1 8 0 - 1 和1 8 0 2 ( f i p s l 8 0 1 和f i p s l 8 0 2 ) 指定的 标准，s h a - 1 序列在目前f i p s 推荐的各种方法中，是唯一实际应用的一种。 s h a - 1 还是l s o i e c l 0 1 1 8 3 指定的标准。b r u c es c h n e i e r 在1 9 9 6 年曾评价：到 目前为止还没有办法来对s h a - 1 进行密码攻击。s h a 1 可接纳一个和多个5 1 2 位6 4 字节的数据块并生成一个1 6 0 位2 0 字节的散列结果。 2 1 2 4s h a - 1 与m d 5 对比 两种算法由于均从m d 4 演进而来，具有明显的相似性，根据前述对m d 4 的特点分析，得出两者对比如下； ( 1 ) 对抗强行攻击的安全性 s h a - 1 与m d 5 最显著的区别在于，报文摘要前者比后者长3 2 位使用强 行技术，产生任何一个报文使其摘要等于给定报文摘要的难度对m d 5 是2 搦数 量级的操作，而对s h a - 1 则是2 瑚数量级的操作。此外，使用强行技术，产生 7 北京邮电大学硕十学位论文 具有相同报文摘要的两个报文的难度对m d 5 是2 “数量级的操作，而对s h a - 1 则是2 s o 数量级的操作。这样，s h a - 1 对强行攻击有更大的难度。 ( 2 ) 对密码分析的安全性 如前所述，m d 5 的设计易受代码分析的攻击，相对而言，s h a - 1 则抗受性 较强。 ( 3 ) 速度 因为两个算法都在很大程度上依赖模的2 3 2 加法，因此两者在3 2 位结构的 机器上速度均很好。s h a - 1 有更多的步骤( 8 0 对6 4 ) 且要处理1 6 0 位的缓存， 相比之下m d 5 仅处理1 2 8 位的缓存。这样在相同的硬件上，s h a - 1 的运行速度 应该比m d 5 慢。 ( 4 ) 简单性和紧凑性 两个算法均描述简单、易于实现，并且无需冗长的程序或很大的替换表。 ( 5 ) 小数在前结构与大数在前结构 m d 5 使用小数在前方案来解释以3 2 位字序列的报文，而s h a - 1 则使用大 数在前的方案。无论两种方案哪一种均没有更突出的优势。 2 1 3 分布式散列表( d h t ) 简介 分布式散列表是对等网络普遍采用的一种资源定位1 1 4 l 手段。d h 一1 5 】使用分 布式散列算法来解决结构化的分布式存储问题。分布式散列算法的核心思想是 通过将存储对象的特征( 关键字) 经过散列运算，得到键值( h a s h k e y ) 。对 象的分布存储依据键值来进行。 对存储对象的关键字进行散列运算，得到键值。这样就将所有的对象映射 到了一个具体的数值范围中。 分布式网络中的每个节点负责数值范围中的特定段落。例如，节点a 负责 存储键值从8 0 0 0 到8 9 9 9 的对象：而节点b 负责从7 0 0 0 到7 9 9 9 的对象。这样 就将对象集中分布地存储在所有的节点中。 节点可以直接存储对象本身，如文件中的一个片段；也可以存储对象的索引， 如该对象所在节点的l p 地址。 结构化的分布式资源存储问题解决后，剩下的问题就是用户如何才能找到 存储着目标信息的节点。在有着大量节点( 如1 0 0 万个) 的对等网系统中，任 何节点都不可能拥有全部的节点、键值、内容的对应关系，因此用户获得了键 值之后，如何找到该键值对应的节点就被称为d h t 的路由问题。d h t 协议必须 定义优化的查找( 路由) 算法来完成这一搜寻工作不同d h t 协议之间的区别 很大程度上就在于定义了不同的路由算法。 d h t 的应用非常简洁一a p l 简单到只有一项输入和一项输出。应用层将 8 北京邮电人学硕士学位论文 数据对象( 文件、数据块或索引) 通过散列算法获得键值，将该键值提交给d h t 后，返回结果就是键值所在节点的砰地址，如图2 - 1 结构所示。 输入输出 图2 1d h t 结构示意 基于d h t 的结构化发现算法及相应的实现技术是对等网络中最重要的研究 成果之一。随着实际网络的发展，物理网络中影响路由的一些因素开始影响对 等网络发现算法的效率。一方面，实际网络中节点之间体现出较大的差异，即 异质性。由于c s 模式在i n t e r n e t 和分布式领域十几年的应用和大量种类的电子 设备的普及，如手提电脑、移动电话或p d a 。这些设备在计算能力、存储空间 和电池容量上差别很大。另外，实际网络被路由器和交换机分割成不同的自治 区域，体现出严密的层次性。 另一方面，网络波动的程度严重影响发现算法的效率。网络波动包括节点 的加入、退出、失败、迁移、并发加入过程、网络分割等。d h t 的发现算法如 c h o r d l l 6 1 、p a s t r y l l 刀、c a n 1 引、t a p e s t r y 1 9 l 等都是考虑网络波动的最差情况下的 设计与实现。由于每个节点的度数尽量保持最小，这样需要响应的成员关系变 化的维护可以比较小，从而可以快速恢复网络波动造成的影响。但是每个节点 仅有少量路由状态的代价是发现算法的高延时，因为每一次查找需要联系多个 节点，在稳定的网络中这种思路是不必要的。 同时，作为一种资源组织与发现技术必然要支持复杂的查询，如多关键字、 内容查询等。尽管信息检索和数据挖掘领域提供了大量成熟的语义查询技术， 由于d h t 精确关键字映射的特性阻碍了d h t 在复杂查询方面的应用。 2 2 基于d h t 的p 2 p 路由算法 2 2 1p a s t r y p a s t r y 网络中每个节点拥有一个1 2 8 位的节点标识符，用于标识该节点在标 识符环( i d e n t i f i e rc i r c l e ) 中的位置p a s t r y 维护每个节点的路由信息表，该表 9 北京邮电大学硕士学位论文 的组织基于共享地址前缀的长度。目前m i c r o s o f t 公司已经发布了基于p a s t r y 的 软件包s i m p a s t r y v i s p a s t r y r i c e 大学也在p a s t r y 的基础之上发布了f r e e p a s t r y 软件包。 2 2 2t a p e s t r y t a p e s t r y 提供了一个分布式容错查找和路由基础平台。在此平台基础之上可 以开发各种p 2 p 应用( o c e a n s t o r e 2 0 l f l 0 是此平台上的一个应用) 。t a p e s t r y 的思 想来源于p l a x t o n 2 1 l 。在p l a x t o n 中，节点使用自己所知道的邻近节点表，按照 目的i d 来逐步传递消息。如一条可能的消息传递路径可能是：4 - * * 3 4 * 2 3 4 1 2 3 4 。其中号表示通配符。该路径从右向左解析，即消息先传递到节点i d 为 4 的节点，再分别依次传递到节点3 、2 和1 。t a p e s t r y 基于p l a x t o n 的思想，加 入了容错机制，从而可适应p 2 p 的动态变化的特点。 2 2 3c a n c a n 的独特之处在于采用多维的标识符空间来实现分布式h a s h 算法。网络 中每一个节点在每一维标识符空间中均保存与自己( 逻辑上或者物理上) 相连 的节点的信息。标识符空间中的每一个i d 代表一个节点，该节点存储一对相应 的( k e y ，v a l u e ) 。其中k e y 通过h a s h 运算映射为节点对应的i d ( n o d ei d ) 。当需 要查询时，只需采用相同的方法对查询的关键字k e y 进行h a s h 运算，得到一个 节点i d ( n o d ei d ) 。从该节点即可找到存储与关键字对应的内容( v a l u e ) 。 2 3c h o r d 路由协议分析 2 3 1 协议概览 基于d h t 的c h o r d 协议是由麻省理工学院和加州大学伯克利分校共同设计 的一种p 2 p 路由协议。协议的具体含义就是对象是如何找到它所依附的节点的、 新节点是如何加入系统，以及系统在动态变化的过程如何恢复到理想状态。在 不失一般性情况下，我们假定底层网络是可靠的、对称的( 即节点a 可路由b ， b 也可路由a ) 和传递的( 节点a 可路由节点b ，节点b 可路由节点c ，那么a 可 路由c ) 。 p 2 p 系统和其应用系统是没有集中控制或分层管理的，所有节点都运行相同 的软件。分析目前的p 2 p 系统，会发现一系列的功能：冗余储存、匿名访问、 查找、鉴别等。这些功能中的核心操作是有效的对象定位。 使用c h o r d 协议非常简单：指定一个对象( o b j e c t ) ，协议就把对象映射到 相应的节点。在基于c h o r d 协议的应用中，节点负责存储与对象联系的对象。 c h o r d 使用分布哈希函数把对象分配到相应的节点上，节点分摊差不多相同的对 象，同时在节点的加入和离去时仅需要移动较少的对象，可见哈希函数能使系 1 0 北京邮电大学硕士学位论文 统的负载平衡。 以前的哈希函数是建立在每个节点知道系统其它节点前提下，所以该方法 不能扩展到具有众多节点的系统中。相反地，在c h o r d 系统中，节点并不需要 知道所有的节点，仅需要保存少数几个节点的路由信息，由于路由表是按某种 规律分布的，一个节点可根据其路由表与其它节点通信及进行查询。系统( n 个节点) 在稳定状态下，每个节点保留只需o ( 1 0 9 ，n ) 节点的相关信息，通过 o ( 1 0 9 ：n ) 次消息转发就可完成查询请求。另外，系统在节点的加入与离去时， 保证路由信息与系统的变化保持同步。 c h o r d 节点需要大约o ( 1 0 9 ，价有效节点路由信息，可见，当部分路由信 息失效时，系统的查询效率将适度下降。由于网络中的节点可以随时地加入或 离开，维护路由信息一致性是很困难的，在实际应用中，每个节点都必须保持 其路由信息的正确性，来保证其查询路由的正确性，c h o r d 协议为我们提供了一 个简单的算法来维持动态信息的一致性。c h o r d 协议的核心是提供一种分布式计 算：使用某种哈希算法把对象空间映射到它所依附的节点空间。c h o r d 协议用一 致性哈希散列函数吲【2 3 l ( c o n s i s t e n th a s h i n g ) 把对象集分配到对应节点集。 2 3 2 常用术语解释 关键值( k e y ) ：是一个经过一致性哈希函数计算的m 位标示值，它可以 与所需要查找的文件或者i p 地址等建立一对一的联系( k e y v a l u e ) ，在c h o r d 系统中所查找的就是这种关键值，然后再通过上面建立的对应联系来反馈真正 所需要的数据。 关键值数据对( k e y v a l u e ) ：指的是上面提到过的关键值与所需的文件等 数据所建立的联系。系统通过查找关键值所在节点，而取得相应数据。 节点值( n o d e ) ：一个经过一致性哈希函数计算的m 位标示值，它是分配 给每个节点或者应用程序的，在其上存放了相应的关键值和关键值数据对。 后继节点( s u c c e s s o r ( k ) ) ：一般称为某个值的后继节点，是指一个节点的 节点值是等于其中存储的关键值，