（计算机应用技术专业论文）p2p文件系统资源定位技术研究.pdf

- c l a s s i f i e di n d e x ： u d c ： i u ll li lil l l ll l li l lli i i 18 0 8 3 0 8 ad i s s e r t a t i o nf o rt h ed e g r e eo fm e n g r e s e a r c ho nr e s o u r c el o c a t i o n t e c h n o l o g y o fp e e r - t o - - p e e rf i l es y s t e m c a n d i d a t e ：m ox i c h a n g s u p e r v i s o r ：p r o f y a n gw u a c a d e m i cd e g r e ea p p l i e df o r ：m a s t e ro fe n g i n e e r i n g s p e c i a l i t y ：c o m p u t e ra p p l i e dt e c h n o l o g y d a t eo fs u b m i s s i o n ：m a r c h ，2 010 d a t eo fo r a le x a m i n a t i o n ：m a r c h ，2 010 u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中己注明引用的内容外， 本论文不包含任何其他个人或集体己经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：习已钨昌 日期： 伽f0 年；月6 日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 日在授予学位后即可口在授予学位1 2 个月后口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：篁铅昌导师( 签字) ：刁驯 日期： 9 f d 年3 月j 6 r 日 2 0 1 0 年；月i 日 。 哈尔滨丁程大学硕士学位论文 摘要 随着社会信息化程度的加深与网络的普及，p 2 p 技术以其低廉的成本与 优异的性能，取得了越来越多的关注，发展迅猛。到目前为止，虽然很多基 于p 2 p 技术的应用相继被开发出来，但目前应用p 2 p 最成功的还是文件系统领 域。而作为p 2 p 文件系统中最重要的技术之一，资源定位技术一直是业界研 究的重点。 目前p 2 p 文件系统资源定位技术已经演化至第三代全分布式结构化的 d h t 网络。本文在已有研究工作的基础上，从安全方面对d h t 网络，尤其是 k a d e m l i a 的资源定位模型进行了研究与分析。本文的研究工作主要分为如下 两个方面： 本文的第一部分对当前k a d e m l i a 资源定位模型中存在的安全漏洞做出了 分析与归类，并详述了资源定位过程中可能遭受的各种攻击及其原理。其中 包括节点插入攻击、资源发布攻击、女巫攻击、节点屏蔽攻击、恶意路由攻 击、路由扰动攻击等。并讨论归纳了当前的安全解决方案。 第二部分在第一部分研究的基础上，提出了一个综合性的k a d e m l i a 资源 定位模型增强方案，从安全节点i d 分配、路由过程安全两个角度对当前的协 议做出了改进。经理论分析与实验验证，上述方案可以有效增强系统的安全 性，提高资源定位成功率。 综上所述，本文在对现有p 2 p 资源定位技术进行详细分析的基础上，着 重研究- r k a d e m l i a 资源定位模型的安全性问题，并通过实验与理论分析验证 了方案的可行性。 关键词：k a d e m l i a ；p 2 p 资源定位；d h t 路由攻击；安全i d 分配；不相交冗 余路由 哈尔滨工程大学硕士学位论文 a bs t r a c t w i mt h ep o p u l a r i z a t i o no fi n t e r n e t ，b yi t sl o wc o s ta n de x c e l l e n tp e r f o r m a n c e ， 一thep 2 pt e c h n o l o g yi sg e t t i n gm o r ea n dm o r ea t t e n t i o n u n t i ln o w , a l t h o u g hm a n y t y p e so fs y s t e mb a s e do np 2 ph a sb e e nd e v e l o p e d ，b u tt h em o s tp o p u l a rp 2 p a p p l i c a t i o ni ss t i l li nt h ed o m a i no fp 2 pf i l es y s t e m a so n eo ft h em o s ti m p o r t a n t t e c h n o l o g yo fp 2 pf i l es y s t e m ，t h er e s o u r c el o c a t i o nt e c h n o l o g yh a s b e e nt h ef o c a l p o i n to fr e s e a r c h e si nal o n gt i m e n o wt h ep 2 pf i l es y s t e mh a sb e e ne v o l u t i o ni n t ot m r dg e n e r a t i o n ，t h ef u l l d i s t r i b u t e ds t r u c t u r e dn e t w o r kb a s e do nd h t b a s e do nt h ep e r v i o u sr e s e a r c h r e s u l t ，i nt h i st h e s i sw ea n a l y z e dt h ek a d e m l i ar e s o u r c el o c a t i o nm o d e li nt h e a s p e c to fs e c u r i t y t h em a i nc o n t e n to ft h i st h e s i sa r ea sf o l l o w s t h ef i r s tp a r to ft h i st h e s i sa n a l y z e st h ew e a k n e s so fk a d e m l i a sr e s o u r c e l o c a t i o nm o d e l ，a n ds t u d i e sv a r i o u sk i n d so fa t t a c k st o w a r dt h ek a d e m l i an e t w o r k ， a n dc l a s s i f i e dt h e s ea t t a c k sb yt h ev u l n e r a b i l i t yt h e yu s e d 。i n c l u d i n gn o d e i n s e r t i n ga t t a c k , r e s o u r c ep u b l i s l l i n ga t t a c k , s y b i la t t a c k ，e c l i p s ea t t a c k , c h u m a t t a c k ，a n dt h ed d o sa t t a c k b a s e do nt h es t u d yo fa t t a c k s ，w ed i s c u s s e da b o u t t h es o l u t i o n sn o we x i s t e d t h es e c o n dp a r tw ep r e s e n tac o m p r e h e n s i v es o l u t i o nt ot h ek a d e m l i a r e s o u r c el o c a t i o nm o d e l i m p r o v e dt h es e c u r i t yl e v e lo ft h ep r o t o c o lf r o mt h e a s p e c to fi da s s i g n m e n ta n ds e c u r er o u t i n gt a b l e e x p e r i m e n t ss h o wt h a tt h e s o l u t i o nc a ne f f e c t i v e l yi m p r o v et h er a t i oo fl o o ku po p e r a t i o n ，a n de n h a n c et h e r e s i s t a n c et ot h er o u t i n gt a b l ep o s i t i o na t t a c k t os u m u p ，b a s e do nr e s e a r c h i n ga n ds u m m a r i z i n g t h ea n a l y s i st e c h n o l o g yo f p 2 pf i l es y s t e mr e s o u r c el o c a t i o nm o d e l ，w ef o c u s e ds t u d i e dt h ek a d e m l i ao nt h e ， 哈尔滨t 程大学硕士学位论文 目录 第1 章绪论l 1 1 课题研究背景及意义1 1 2p 2 p 文件系统简介2 1 2 1p 2 p 文件系统定义”2 1 2 3p 2 p 文件系统典型代表“2 1 3 论文研究内容4 1 4 论文组织结构5 第2 章基于d h t 的资源定位技术研究6 2 1 引言”6 2 2p 2 p 文件系统资源定位技术分类7 2 2 1 集中目录式结构7 2 2 2 分布式非结构化一7 2 2 2 分布式结构化8 2 2d h t 技术概述8 2 3k a d e m l i a 资源定位模型研究- 1 0 2 3 1 节点i d 与资源键值l o 2 3 2 距离度量1 1 2 3 3 网络结构1 2 2 - 3 4k 桶概念1 2 2 3 5 协议原语1 3 2 3 7 搜索流程1 4 2 3 8 资源发布1 5 2 5 本章小结1 6 第3 章k a d e m l i a 资源定位模型安全分析1 7 3 1 引言17 3 2k a d e m l i a 资源定位模型安全缺陷17 哈尔滨工稃大学硕士学位论文 3 2 1 节点i d 分配17 3 2 2 路由表污染1 8 3 2 3 恶意路由1 9 3 2 4 资源索引表污染1 9 3 3 攻击详述与分析- 2 0 3 3 1 节点插入攻击2 0 3 3 2 资源发布攻击2 2 3 3 3 女巫攻击2 3 3 3 4 节点屏蔽攻击2 4 3 3 5 恶意路由攻击2 5 3 3 6 路由扰动攻击2 7 3 3 7 拒绝服务攻击2 8 3 4 解决方案讨论分析2 8 3 4 1 安全节点i d 分配“2 8 3 4 2 路由过程安全3 2 3 4 3 节点信誉系统3 3 3 4 4c a p t c h a 测试”3 4 3 5 总结分析“3 5 3 6 本章小结3 6 第4 章k a d e m l i a 资源定位模型安全性增强方案3 7 4 1 引言3 7 4 2 方案概述37 4 3 安全节点i d 分配3 9 4 3 1c r y p t op u z z l e 3 9 4 3 2 实验分析4 1 4 4 路由过程安全一4 2 4 4 1 路由消息分类4 2 4 4 2 节点d 验证4 4 4 4 3 不相交冗余路由4 5 4 5 实验与分析4 7 一 哈尔滨1 二程大学硕士学位论文 第1 章绪论 1 1 课题研究背景及意义 进入新世纪以来，随着互联网技术的发展，社会信息化程度进一步加深。 在互联网用户成倍增加的同时，用户们对网络上各种应用的服务质量也提出 了更高的期望。然而在巨大的用户需求面前，传统的客户端服务器体系结构 ( c l i e n t s e r v e r ，以下简称c s 结构) 却逐渐显现出了疲态。不断增加的用户 要求更快，更多，更好的服务，服务提供商堆叠硬件，成本不断增加，已经 不堪重负。在这样的背景下，对等计算( p e e r - t o p e e r ，以下简称p 2 p ) 技术 应运而生，由其崭新的思想、低廉的成本、高质量的服务，迅速成为计算机 界关注的热点，甚至被财富杂志评为影响互联网未来发展的四项关键技术之 o 回顾发展历史，p 2 p 技术最早起源于一些实时通信( i m ) 软件，但直到 n a p s t e r 的出现，及其爆炸性的流行，p 2 p 才真正进入大众的视野。时至今日， p 2 p 技术已经融入网络应用的方方面面，出现了一大批基于p 2 p 的优秀的应 用，几乎每个互联网用户的主机中都有数款基于p 2 p 技术的软件。但p 2 p 应 用最成功的应用还是在文件共享领域，诸如b i t t o r r e n t 、e m u l e ，早己成为互 联网用户生活中不可或缺的一部分。 由于版权，隐私保护等诸多问题。p 2 p 文件共享系统从诞生的那天起就 被争议所围绕。在美国唱片工业协会的打击下，辉煌一时的n a p s t e r 被迫关 停。近年来随着一系列版权官司的失败，e m u l e 网络中的重要服务器也相继 被关停。2 0 0 9 年1 1 月l7 日，b i t t o r r e n t 领域享有盛誉的海盗湾( t h ep i r a t eb a y ) 在其官方博客上宣布永久关闭其t r a c k e r 服务器。依靠中央目录服务器进行 资源定位的传统方式已经行不通了。但是p 2 p 文件共享系统发展并没有因此 而停滞，开始转向安全性，稳定性，匿名性更好的全分布式结构化网络。p 2 p 文件系统在如此逆境中尚能一代代的更新，愈发强健。相信在其摆脱了版权 桎梏的束缚后，将会迎来更为广阔的前景。 哈尔滨工程大学硕士学位论文 1 2p 2 p 文件系统简介 1 2 1p 2 p 文件系统定义 首先需要明确的是p 2 p 网络的定义，但是关于这一点，业界并没有一个 统一的结论。按照文献【l 】，一个宽松的p 2 p 网络的定义可以如下表述： 一个分布式网络结构可以被称之为p e e r - t o p e e r ( p t o p ，p 2 p ) 网络，当 且仅当网络中的参与者共享其一部分硬件资源( 处理能力，存储容量，网络 带宽打印机等) 。这些被共享的资源对于网络提供的服务与内容是必须的： 它们可以被网络中的其他p e e r 直接访问，无需经过中间实体传递。这种网络 的参与者既是资源( 服务与内容) 的提供者，也是资源( 服务与内容) 的请 求者。 而p 2 p 文件系统，即为构建在p 2 p 网络架构基础上的，用于文件访问、 共享、分发、与交换的应用系统。而资源定位技术是p 2 p 文件系统的关键技 术之一。 1 2 3p 2 p 文件系统典型代表 在多年的p 2 p 文件系统的发展过程中，出现了众多受欢迎的系统。现选 取部分国内外具有代表性的系统，简要介绍如下： 1 、b i t t o r r e n t 自2 0 0 1 年诞生以来，b i t t o r r e n t 一直是互联网上最为流行的文件共享软 件。目前看来，b i t t o r r e n t 的下载速度也是同类系统中最快的。由于其高效及 低成本的特性，从众多l i n u x 发行版，到各种知名的网络游戏，许多大型软 件都选择采用b i t t o r r e n t 发布。据统计，截止2 0 0 9 年2 月为止，大约2 7 5 5 的互联网流量( 根据地理区域而不同) 是b i t t o r r e n t 流量【3 7 】。而在所有p 2 p 文件共享系统引起的流量之中，b i t t o r r e n t 占到了5 3 1 37 1 。 要构成一个b i t t o r r e n t 网络，必须要有一个中央目录服务器，称之为 t r a c k e r 。t r a c k e r 用于跟踪系统中所有的参与节点，收集并统计这些节点的状 态，回应客户端的查询请求，反馈资源节点信息。在b i t t o r r e n t 网络中，初 始的文件共享者需要通过工具软件对目标文件生成一个t o r r e n t 文件，此文件 即为初始种子文件( i n i t i a ls e e d ) 。下载用户通过其他途径获取到种子文件后， 2 哈尔滨工程大学硕士学位论文 即可用b i t t o r r e n t 协议的客户端开始下载。文件发布者是最初的种子节点， 当下载节点完成下载后，将自动变成种子节点，开始做种。一个下载中，种 子节点越多，下载速度越快，健康度越高。与一个种子文件关联的所有节点 ( 包括种子节点，下载节点以及t r a c k e r ) ，构成一个逻辑上的封闭实体。这个 实体在b i t t o r r e n t 网络中被称为一个t o r r e n t 。 随着海盗湾与m i n i n o v a 的相继关停，维持一个公用t r a c k e r 的风险越来 越高。目前b i t t o r r e n t 系统开始转向使用d h t 方式进行资源定位。海盗湾在 关闭t r a c k e r 的通告中认为t r a c k e r 的时代已经过去，d h t 才是b t 的未来。 在此之前，主流的客户端基本都已内置了对基于k a d e m l i a 算法的d h t 网络 的支持。主要有m z u r e u sd h t 以及m a i n l i n ed h t 两大流派。遗憾的是，虽然 基础算法相同，但由于实现上的差别，这两个网络不能相互联通，同时与 e m u l e 的k a d 网络也无法互通。 2 、e m u l e e m u l e 是当今世界上最大也是最可靠的p 2 p 文件共享网络。据统计目前 e m u l e 网络中大约有3 百万至4 百万用户，分享着4 0 亿左右的文件。但e m u l e 并不是一个全新的系统，而是e d o n k e y 2 0 0 0 ( 以下简称e d 2 k ) 网络的继承者。 e d 2 k 网络也存在一个中心索引服务器。与n a p s t e r 不同的是，任何人都 可以构建自己的服务器，因此网络中存在着大量的e d 2 k 服务器可供选择。服 务器与服务器之间也能相互通讯，交换文件资源信息。由此，e d 2 k 网络形成 了一个整体，而不是像b i t t o r r e n t 那样以各个t r a c k e r 服务器为中心的单独的 网络，这是e d 2 k 最大的优势所在。 当客户端要登录e d 2 k 网络时，需要向一个e d 2 k 服务器注册，获得一个 i d 号。同时将自己的信息及拥有的共享文件发送给该服务器，此服务器便成 为了客户端的宿主服务器。与b i t t o r r e n t 种子文件的概念不同，客户端若想 分享某个文件，只需要将此文件放入自己的共享文件夹下。系统会自动对这 个文件生成一个e d 2 ku r i ，此u r i 包含文件的哈希码，可在e d 2 k 网络中唯 一标识文件。其他客户端要下载这个文件时，只需要获得一个这样的链接即 可。宿主服务器为客户端提供资源搜索及定位服务，客户端与宿主服务器间 使用t c p 链接，服务器之间使用u d p 相互发送消息。客户端也可以对宿主 服务器之外的服务器通过u d p 发送查询请求，以获取更多的资源。 哈尔滨 _ 程大学硕士学位论文 |i ii _ _ i i i i i i i 宣宣i i i i i i i i i e m u l e 在e d 2 k 的基础上，对其作出了大量的改进。其中最重要的是在 e m u l e 中引入了d h t 网络的支持，实现了一个基于k a d e m l i a 协议的全新的 d h t 网络k a d 。由于k a d 的存在，e m u l e 实际联通了两个巨大的覆盖网络。 不仅可以通过宿主服务器构建的网络检索资源信息，还可以通过k a d 网络获 取到更多的资源。即使连不上任何服务器，e m u l e 也能继续工作。 和b i t t o r r e n t 网络的命运相似。2 0 0 7 年7 月，随着法院判决德国音乐产 业获胜，位于德国境内的e m u l e 网络中最大的服务器e d o n k e ys e r v e r 系列被 迫关停。从此e m u l e 网络中再也没有全球性的性能可靠的服务器存在了。 e m u l e 的使用者不得不开始更加依靠k a d 网络检索资源信息。 3 、m a z e m a z e 3 8 】是由北京大学网络实验室的几名研究生开发的文件共享系统。目 前已经成为中国教育网内最流行的p 2 p 文件共享系统。 与上文提到的两种典型p 2 p 应用系统一样，在m a z e 网络中，也存在一 个中心目录服务器。客户端登录时首先将尝试连接到目录服务器，连接成功 后，将本机共享的资源相关信息发送给目录服务器，目录服务器将所有客户 端发送过来的信息编制成索引，方便网络内的用户搜索。在支持目录服务器 搜索的同时，m a z e 也内置了一套类似于g n u t e l l a 的洪泛搜索机制。从而避免 了目录服务器单点失效后，整个网络依然能够继续工作。 m a z e 和其他系统相比，亮点在于在安全性方面做出了更多的考量。m a z e 使用分布式认证算法来保证用户认证的有效与安全，同时支持节点间的相互 身份认证。 1 3 论文研究内容 p 2 p 文件系统在近年内一直是业界研究的热点，作为p 2 p 文件系统最重 要的一项技术之一，资源定位技术同样也受到了诸多的关注。如上节所述， p 2 p 文件系统资源定位技术已经开始逐渐过渡到以d h t 技术作为基础的全分 布式结构化网络，d h t 算法具有广阔的应用前景。而诸多d h t 算法中，只 有k a d e m l i a 算法有被投入实际大规模应用，并且在继续发展，本文将以它作 为具体的研究对象。 目前针对d h t 网络的研究存在多种方向，其中一个方向即为进一步提高 4 哈尔滨工程大学硕十学位论文 d h t 网络的效率，诸如负载均衡，高效路由算法等；另一方面，d h t 网络 作为全分布式网络的本质，决定了其安全问题也十分突出，其安全问题一直 是业界研究的热点。而在多种安全隐患中，绝大部分都和资源定位过程有关。 本文在对多种形式的d h t 网络进行详细分析的基础上，着重研究了k a d e m l i a 定位模型在安全性方面存在的问题。包括对各种类型的攻击的分析，解决方 案的讨论以及攻击与解决方案的归纳与分类。在文章的最后，提出了个综 合性的k a d e m l i a 资源定位模型安全增强方案，并对其做出了模拟验证。 1 4 论文组织结构 本文探讨了p 2 p 文件系统资源定位的相关模型和方法，并从安全角度进 行了深入的分析。根据涉及的内容，本文分为如下几个章节： 第一章：介绍了p 2 p 文件系统的发展历史与背景，国内外研究状况，简 述了各种资源定位方法。 第二章：讨论了主流的基于d h t 技术的资源定位模型，并对其中的 k a d e m l i a 网络做出了着重分析。并在此基础上，对e m u t ek a d ，m z u r e u sd h t , 、 m a i n l i n ed h t 三个k a d e m l i a 主流实现版本进行了分析。最后，总结了其相互 之间的异同与当前的发展状况。 第三章：分析了k a d e m l i a 网络资源定位模型存在的各种安全漏洞。对与 资源定位模型相关的各种攻击，诸如节点插入攻击、资源发布攻击、节点屏 蔽攻击、女巫攻击，b o o t s t r a p 攻击、拒绝服务攻击等进行了原理阐述及分析。 然后总结了当前已知的各种安全方案，包括安全节点i d 分配，路由过程安全， 节点信誉系统等。并在最后，对各种攻击及安全漏洞做出了归类总结。 第四章：在前几章的基础上，提出了一个综合性的k a d e m l i a 资源定位模 型安全增强方案，并对其做出了模拟验证。 哈尔滨工程大学硕士学位论文 第2 章基于d h t 的资源定位技术研究 2 1 引言 在信息量庞大的互联网上，如何准确并快速地定位资源一直是网络服务 的基础性问题。在传统c s 结构的网络中，资源明确存储在网络中的少数服 务器上，客户端只需给出服务器的地址及资源在服务器上的位置两个要素， 便可确定资源的位置。诸如万维网( w b r l dw i d ew 曲) 便使用统一资源定位 符( u n i v e r s a lr e s o u r c el o c a t o r ，u r l ) 技术进行资源定位【2 1 。客户端只需要 给出访问方法( s c h e m e ) ，w e b 服务器地址( h o s t ) 、具体资源在服务器上的 绝对路径( p a t h ) 及附加一个可选的询问参数( q u e r y ) 便可明确定位个资 源在万维网中的位置，并通过此u r l 访问服务器，获取到对应的资源。 然而，在p 2 p 网络中，资源定位却并不是件容易的事。由于资源分散 在网络中众多主机之上，而且网络中的主机具有相当的随意性。某个时刻还 在网络上的主机，下一个时刻可能就离线了，对应的是离线主机持有的资源 此时由可用变成了不可用状态。因此，当客户端提出对某个资源的请求时， 往往无法知道目标的确切位置。在这种情况下，就需要提供一种机制，在网 络中搜索并定位当前可用的资源，然后再去获取资源。 如上文分析，资源定位是p 2 p 文件系统最重要的技术之一，定位算法的 设计选择直接影响到系统拓扑结构的确定、下载速度、资源发现效率与整个 网络的稳定性。随着网络规模的逐渐扩大，网络中的资源呈几何倍数增长， 如何在海量的资源中快速有效地找到并定位所需的那部分，是当前p 2 p 文件 系统研究的重点。 本章首先对当前存在的各种定位技术做了简要介绍，然后详细研究了 k a d e m l i a 网络的资源定位模型，并在最后对k a d e m l i a 网络的各种主流实现进 行了对比分析。 6 哈尔滨工程大学硕十学位论文 2 2p 2 p 文件系统资源定位技术分类 从n a p s t e r 为代表的第一代系统算起，p 2 p 文件共享系统已经经历了数 代演化，目前正在向全分布式结构化网络方向发展。总结p 2 p 文件系统的发 展历程，可以将其由使用的资源定位技术划分为集中目录式结构、全分布式 非结构化以及全分布式结构化三种类型。通过这三种类型的定位技术，也可 以将p 2 p 文件系统划归为对应的三代。 2 2 1 集中目录式结构 以n a p s t e r 为代表的第一代p 2 p 文件系统并没有放弃中心服务器的模式。 在这种结构的网络中，存在一个中心节点：资源索引服务器。顾名思义，索 引服务器只维护网络内所有资源的索引，而并不存储任何的文件。一般索引 条目包括文件名，文件大小，所在对等节点地址信息等。当客户机向索引服 务器发起查询时，服务器在索引中找到符合条件的资源，将信息反馈给客户 机。客户机得到资源信息后，再利用其中的地址信息，连接到对等节点下载 资源数据。这种机制具有传统c s 结构中心化的特点，但是不同的地方在于， c s 模式下的数据都存放在服务器上，客户端直接从服务器上下载资源。客 户端与客户端之间，也不存在直接交互的能力。 通过这种结构的设计，在保持网络拓扑结构清晰，简单的情况下，将负 载分散到了各个参与网络的对等节点上，大大减轻了对服务器端性能的要求。 从而在保持成本低廉的情况下，依然能够提供高质量的服务。 但由于中心节点的存在，网络的健壮性存在一定的隐患，若中心节点的 服务器失效，整个网络便将陷于瘫痪状态。而且同样由于中心节点的存在， 制约了网络的可扩展性。当网络规模扩大到一定程度的时候，服务器的负载 将会急剧增加，此时如果服务器的性能跟不上，则整个网络的服务质量将会 下降。 2 2 2 分布式非结构化 在n a p s t e r 之后，出现了以g n u t e l l a 为代表的第二代p 2 p 文件共享系统。 g n u t e l l a 放弃了中央目录服务器的使用，转而使用纯分布式结构，从而避免 7 哈尔滨t 程大学硕士学位论文 i i i i 宣i i i 宣萱i i i 宣i i i i i i i i i i i i i i i i i 宣青iiii i i i_- - 暑 了中央目录服务器的存在带来的各种问题。 在全分布式非结构化网络中，客户端采取洪泛( f l o o d i n g ) 与随机转发 ( r a n d o mw a l k e r ) 的机制来实现资源的定位查询。在查询过程中，对于搜索 消息引入了t t l ( t i m et ol i v e ) 递减，唯一d e s c r i p t o ri d 、接收过的消息不 再重发等机制来控制消息传播的跳数，避免产生查询风暴。 相比上一代p 2 p 网络，这种网络结构在分布式及对等性方面更为纯粹， 稳健性有所提升。但是由于其非结构化的特性，没有特定的网络拓扑结构支 持查询操作，因此无法保证资源发现的效率。虽然使用洪泛的路由查找机制 避免了中心节点失效问题。但当网络规模扩大时，大量的洪泛查询将急剧消 耗网络资源。通过减小t t l 一定程度上可以缓解大量查询对网络造成的压 力，但过小的t t l 会导致搜索消息只能在网络中的某个局部区域内传播，导 致资源存在于网络中，却无法被需要者发现的现象，搜索效率很低。 2 2 2 分布式结构化 在第二代p 2 p 网络设计中稳健性与效率互为矛盾的局面下，第三代全分 布式结构化p 2 p 网络应运而生。 全分布式结构化p 2 p 网络主要基于d h t ( d i s t r i b u t e dh a s ht a b l e ) 技术， 在保留第二代p 2 p 网络全分布式带来的稳健性优势的基础上，将整个网络按 照哈希表的思想组织了起来，形成了结构化的拓扑。由于结构化拓扑的存在， 不仅提高了资源查询效率，而且保证了查询中的确定性。代表性的基于d h t 的p 2 p 网路有c h o r d 3 1 、p a s 4 1 、t a p e s t 5 1 、c a n 【6 】以及i 跚e 砌i a 【7 】o 在d h t 网络中，资源定位过程即为路由查询过程。本文在接下来的章节 中将不再区分这两者。 2 2d h t 技术概述 如上节所述，第一代网络所使用的集中式的定位模型虽然简单有效，便 于管理，但是在可扩展性方面不如人意。第二代网络在设计过程中规避了中 心节点的设置，但由于非结构化的组织模型，造成了稳健性与效率互为矛盾 的局面。在这种形势下，第三代定位模型，全分布式结构化p 2 p 网络应运而 生。 哈尔滨工程大学硕+ 学位论文 全分布式结构化网络建立在分布式哈希表( d i s t r i b u t e dh a s ht a b l e ，以下 简称d h t ) 的基础之上。d h t 在接口形式上与普通的哈希表相同，提供两 个操作：s t o r e ( k e y , v a l u e ) 以及v a l u e = r e t r i e v e ( k e y ) 。抽象来说，d h t 提供 了分布式的 对的映射与存储功能，并可分为如下三个组件：键空间 ( k e y s p a c e ) 、键空间分割方法及延展网络。其中键空间是d h t 的基础，决 定了d h t 所能操作的空间的大小。键空间分割方法将键空间分割成较小的 块，并交由系统中的某个节点管理。而延展网络则连接这些节点，并让他们 能够借由在键空间内的任一键找到拥有该值的节点。 d a t a k e y d i s t r i b u t e d 图2 1 分布式哈希表【3 习 具体来说，在d h t 算法中，每个节点通过统一的哈希函数计算出自身的 键( 即节点的i d ) ，将物理环境中的节点映射到键空间( 即d 空间) 之中， 并以此为自身在网络上的唯一标识。由于d 空间非常庞大，节点在其中分布 相对稀疏，直接寻址效率较低。因此i d 空间被分割成较小的地址块，并交由 系统中的某个节点进行管理。这段地址空间称为节点的管理区域( z o n e ) ， z o n e 与普通哈希表中桶( b u c k e t ) 的概念类似，而网络中的资源，则对应于 桶中的项。 在d h t 中，节点按照明确的算法度量与其他节点的距离，并以此选择自 身的邻居节点，整个网络在宏观上是规则的。同时，与非结构化的网络不同， d h t 明确定义了网络中节点与资源的查找与定位方式，而不是使用洪泛进行 盲目地查找。任何发起的查询，最终都将收敛到资源持有者或者距离资源最 近的一个节点。查询与定位都具有确定性，效率也有保证。在大多数的d h t 9 哈尔滨工程大学硕士学位论文 算法中，若以, 表示网络规模，则查询的复杂度为o ( 1 0 9 n ) t 7 1 。 大多数d h t 算法中，采用稳定哈希( c o n s i s t sh a s h ) 方法来将键对应到 节点，并由此实现键空间分割。稳定哈希方法使用一个函数万( 毛，k ：) 来定义 一个抽象的概念：从关键值k 到七，的距离。每个节点被指定了一个键( 即 i d ) 。i d 为i 的节点拥有根据函数万计算，最接近i 的所有关键值。稳定散 列拥有一个基本的性质：增加或移除节点只改变邻近d 的节点所拥有的 对集合，而其他节点的则不会被改变。对比于传统的散列表，若增加或移 除一个位置，则整个键空间就必须全部更新。这种情况如果发生在分布式散 列表之中，通常会导致相关信息被从分布式散列表中的一个节点被搬到另一 个节点，造成带宽的浪费与效率的下降。考虑到p 2 p 网络的动态性，随时会 有大量的节点加入或离开网络，使用类似的方法避免键值归属的迁移是非常 重要的。 2 3 地e m l i a 资源定位模型研究 k a d e m l i a 由p e t a rm a y m o u n k o v 与d a v i dm a z i e r e s 设计。它定义了网络的 结构与节点间的通信方式，以实现全分布式结构化的p 2 p 网络系统。是一种 典型的分布式哈希表路由协议。 在现有的多个基于d h t 的p 2 p 资源定位模型中，目前只有k a d e m l i a 有 大规模的实际应用。相比于其他几种模型，k a d e m l i a 通过使用异或算法度量 节点间的距离尺度，建立了一种全新的d h t 拓扑结构，提高了路由查询速度 和查询效率。k a d e m l i a 协议可以使节点之间相互通讯的配置信息减少到最小， 同时配置信息可以随着关键字的查找而自动传播。通过使用并行的异步查找 算法来避免非活动节点带来的时间耗费，同时节点有着较高的灵活性来选择 较近的路由路径。总的来说，k a d e m l i a 和其他d h t 模型相比，存在较多优 势。这也是e m u l e 的k a d 网络与b i t t o r r e n t 的d h t 网络不约而同地选择 k a d e m l i a 作为其实现基础的原因。 2 3 1 节点i d 与资源键值 k a d e m l i a 网络中，每个节点都有一个固定b i t 位的二进制数作为标识符 ( 即节点i d ) ，节点i d 在网络上唯一标志了节点本身。同时，每个资源被抽 1 0 哈尔滨t 程大学硕十学位论文 象为一个值( v a l u e ) ，也具有一个唯一的固定长度的标识符对其进行唯一的 标志，称为键( k e y ) 。 k a d e m l i a 协议规定，节点i d 与k e y 长度相同，一般取1 6 0b i t s ，但不同 的实现中，这个长度并不确定。节点d 的生成，需要保证的是所有的节点 d 要非常均匀地分布在整个网络之中，整个网络的设计也依赖于这种均匀分 布的特性。般采取随机数方式来生成节点i d ，确保这种特性。随机生成i d 可能会导致重复i d 的情况，但由于d 空间非常大，这种情况可以忽略不计。 对于表征资源的k e y ，同样需要保证其在网络中分布的均匀性，同时还得满 足值与键之间唯一映射的关系。在p 2 p 文件系统中，最通常的使用方式是对 整个资源文件进行哈希( 诸如m d 5 ，s h a l ) ，获得对应的哈希码作为k e y 。 k a d e m l i a 协议中并没有明确规定节点d 的有效期。节点可以在多个会 话中始终保持一个i d ，也可以每次加入网络时获得一个重新分配一个i d 。 但在现实的实现之中，节点i d 往往在程序安装时生成，之后即保持不变。这 样某个节点即便多次加入或离开网络，都有一个唯一的i d 对其进行标识，便 于统计其信誉值。 2 3 2 距离度量 距离的度量是d h t 网络中最重要的基础问题之一。k a d e m l i a 网络规定， 两个节点在网络中的距离d 是两个节点i d 的异或值的逐比特二进制之和。由 此，节点间的距离只和节点自身相关，并不由物理距离或者口网络中途径的 路由器跳数来衡量。例如：网络中有两个节点a l i c e 和b o b ，其i d 分别为a ， b 。则a l i c e 和b o b 的距离为d = ax o rb 。当d 值较大时，说明两个节点间 的“距离”较远，反之说明两个节点间较近。每个网络中的节点都使用这个 通用的规则来判断其他节点距离自己的远近。在k a d e m l i a 网络中，“距离 只是一种逻辑上的度量，和实际的概念不同。使用异或运算机制，提供了一 种在k a d e m l i a 网络上进行可靠距离度量的方法。由于异或运算的非负性、对 称性、单向性、传递性以及三角不等性，从而能够保证距离与节点的一一对 应的特性。其中无方向性意味着节点a 到节点b 的距离恒等于节点b 到