（计算机应用技术专业论文）p2p网络模型下搜索机制的研究与实现.pdf

南京邮电大学硕士研究生学位论文 摘要 摘要 对等网( p e e r - t o p e e r , p 2 p ) 技术是一种构筑在现有因特网基础之上、以文件共享为初 始目的而产生的一种覆盖网技术，目前该技术已被广泛应用于对等计算、协同工作、资源 搜索与共享等很多领域，并引起了很多业界人士的关注。 p 2 p 资源搜索机制作为各种p 2 p 技术应用的基础已成为当前研究的热点，但现有的p 2 p 资源搜索机制普遍存在着以下问题：忽视底层网络状况对资源搜索造成的影响；缺乏对节 点( p e e r ) 间异质性的考虑；资源提供者负载分配不均：网络状态信息的维护开销巨大等等， 从而在一定程度上影响了资源搜索的质量和效率。本文的主要贡献是，通过对p 2 p 网络模 型下资源搜索机制的研究，在分布式哈希表( d i s t r i b u t e dh a s ht a b l e ，d h t ) 思想的基础上，提 出了一种复式c a p ( d u a lc h o r da n dp a s t r y , 简称“复式c a p ) 模型，该模型充分考虑了 底层网络状况及节点间的异质性对资源搜索造成的不良影响，依照地理区域( 或网段) 、 节点性能( 处理能力、带宽) 以及节点行为方式( 在线时间) 的不同将网络分层、节点分 类，同时根据各层网络的特点使处于不同层次上的节点分别维护不同大小的路由表、采用 不同的路由方式，并以选取多个稳定对等体共同作为共享资源载体的方式，采用一种新的 “十字链表”结构来记录所有存储了同一共享资源的稳定对等体信息，合理分配访问量， 最后通过建立相应的数学模型进行分析，证明了该搜索机制在搜索效率、负载平衡、健壮 性以及可扩展性等方面都比以往的搜索机制有了显著提高。 关键词：p 2 p 资源搜索d h t 分层网络节点异质性 南京邮电大学硕士研究生学位论文a b s t r a c t a b s t r a c t t h et e c h n o l o g yo fp e e r - t o p e e r ( p 2 p ) n e t w o r ki sak i n do ft e c h n o l o g ya b o u tt h eo v e r l a y n e t w o r k sw h i c hi sc o n s t r u c t e do nt h eb a s i so ft h ei n t e m e tn o w , a n di t so r i g i n a lp u r p o s ei sf i l e s h a r i n g a tp r e s e n t ，p 2 ph a sb e e nw i d e l yu s e di nt h ea r e ao fd i s t r i b u t e d c o m p u t i n g ， c o l l a b o r a t i o n ，r e s o u r c es e a r c h i n g & s h a r i n ga n ds oo n ，m o r ea n dm o r ep e o p l eb e g i nt op a y a t t e n t i o nt oi t a st h eb a s i so fa l lk i n d so fp 2 pa p p l i c a t i o n ，t h et e c h n o l o g yo fp 2 pr e s o u r c es e a r c h i n gh a s b e c o m i n gar e s e a r c hh o t s p o tn o w , b u tt h e r ea l s ou b i q u i t ym a n yp r o b l e m ss u c ha s ：i g n o r et h e s t a t e ：o fb o r o mn e t w o r k s ；l a c ko fc o n s i d e r a t i o na b o u tt h ep e e r s h e t e r o g e n e i t y ；u n b a l a n c e dl o a d o fr e s o u r c ep r o v i d e r s ；g r e a tc o s ti nm a i n t a i n i n gs t a t u si n f o r m a t i o na b o u tn e t w o r k se t c ，a l la b o v e i n f l u e n c et h eq u a l i t ya n de f f i c i e n c yo fr e s o u r c es e a r c h i n gi ns o m ed e g r e e t h em a i nc o n t r i b u t i o n o ft h et h e s i si s ：d om u c hr e s e a r c hi nr e s o u r c es e a r c h i n gm e c h a n i s mo np 2 p n e t w o r k ，d e s i g na n d i m p l e m e n tar e s o u r c es e a r c h i n gm o d e ln a m e dd u a lc a p ( c h o r da n dp a s t r y , c a p ) w h i c hi sb a s e d o nt h ei d e ao fd i s t r i b u t e dh a s ht a b l e t h ed u a lc a pm o d e lf u l l yc o n s i d e r e st h eb o r o mn e t w o r k s a n da l s ot h eb a di n f l u e n c eb r o u g h tb yt h ep e e r s h e t e r o g e n e i t y , s oi td e l a m i n a t en e t w o r ka n d c l a s s i f i e sp e e r sa c c o r d i n gt og e o g r a p h i cd i s t r i c t ，p e e r s p e r f o r m a n c ea n dp e e r s b e h a v i o ni nd u a l c a p m o d e l ，p e e r st h a tb e l o n gt od i f f e r e n tn e t w o r kl a y e rm a i n t a i nd i f f e r e n tr o u t i n gt a b l ea n dt a k e d i f f e r e n t r o u t i n gs t r a t e g y m a n ys t a b l ep e e r sa r ep i c k e d o u tt os t o r e s h a r i n gr e s o u r c e c o o p e r a t i v e l y , a n da l li n f o r m a t i o na b o u tt h es t a b l ep e e r sw h i c hs t o r et h es a m es h a r i n gr e s o u r c ei s r e c o r d e di ns o m ec r o s sl i n kl i s t si no r d e rt ob a l a n c et h er e s o u r c ep r o v i d e r sl o a d 。a tl a s t ，a m a t h e m a t i c a lm o d e li sb u i l tt od e m o n s t r a t et h ed u a lc a pr e s o u r c es e a r c h i n gm e c h a n i s mi sb e t t e r t h a nc h o r da n dp a s t r yi n r e s p e c to fs e a r c h i n ge f f i c i e n c y , b a l a n c i n gl o a d ，r o b u s t n e s sa n d e x p a n s i b i l i t y k e yw o r d s ：p 2 pr e s o u r c es e a r c h i n gd h tl a y e r e dn e t w o r k p e e r sh e t e r o g e n e i t y i l 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：二学日期：j 业 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：翟 盘盈 导师签名： j 主鲻圣日期：删 南京邮电大学硕士研究生学位论文 绪论 绪论 近年来，一种称为对等网( p e e r t o p e e rn e t w o r k ) 的新型大规模分布式系统迅速发展 起来，并很快取代w e b 成为i n t e m e t 上占用带宽最多的应用系统：它改变了传统的c s 模式集 中存储和处理资源的方法，将网络边缘的资源有效地组织起来，消除中间环节，使资源请 求者和资源提供者之间能够直接相互交换信息。 目前，p 2 p 技术已在对等计算、协同工作、资源搜索与共享等很多领域都得到了广泛 应用，并引起了许多业界人士的关注。资源搜索机制作为各种p 2 p 技术应用的基础已成为 当前p 2 p 研究的一个热点，从最初n a p s t e r 采用的集中目录式搜索机制，到后来g n u t e l l a 采用 的泛洪请求式搜索机制，再到现在p a s t r y 、c h o r d 、c a n 等采用的文件路由式搜索机制，无 论在健壮性、可扩展性还是负载均衡等方面都有了显著改善，p 2 p 网络也从最初的非结构 化网络发展成为结构化网络。 本文的重点是结构化p 2 p 网络中的文件路由式搜索机制，研究目的是针对现有的结构 化p 2 p 资源搜索机制普遍存在的忽视底层网络状况、缺乏对节点间异质性的考虑、资源提 供者负载分配不均以及网络状态信息的维护开销巨大等问题，设计并实现一种稳定、可靠、 高效的新型资源搜索机制。 本文内容组织如下： 第一章：对p 2 p 技术进行综合概述，包括多种定义方式、网络拓扑模型分类、与现有c s 模 式的比较及应用现状等； 第二章：对p 2 p 网络中的三种基本资源搜索机制进行详细的介绍与分析： 第三章：特别针对结构化p 2 p 网络，深入分析以c h o r d 和p a s t r y 为代表的d h t 搜索模型，并 在综合考虑各种因素的基础上提出一种复式c a p 资源搜索模型； 第四章：系统阐述复式c a p 资源搜索机制的实现过程，包括基本概念、基本操作以及具体 的实现策略； 第五章：对复式c a p 资源搜索机制建立数学模型，通过分析推理证明该资源搜索机制在搜 索效率、负载平衡、健壮性以及可扩展性等方面都比原c h o r d 系统和原p a s t r y 系统 有了显著提高。 第六章：总结本文所做的工作，展望未来p 2 p 资源搜索机制的发展前景。 v 南京邮电大学硕士研究生学位论文 第一章p 2 p 概述 第一章p 2 p 概述 自2 0 0 0 年开始，款名为n a p s t e r 的p 2 p 网络音乐文件共享软件在网络上广为流行， 吸引了广大网上音乐爱好者的注意力，在短短几个月内就吸引了成千上力的用户，原因在 于该款软件采用了不同于以往c s 模式的文件共享方式，所有共享的音乐文件都由用户提 供，不但种类繁多，下载自由而且也较少出现下载速度缓慢的问题。n a p s t e r 巧妙的 p 2 p 文件共享方式和短时间内急剧增长的用户数量给人们留下了深刻印象，也对互联网传统的 c s 模式提出了挑战，启发并引导越来越多的人们投入对p 2 p 相关领域的研究与开发中。 因此，可以说n a p s t e r 是当今互联网上p 2 p 技术兴起的导火索。 本章中，首先在1 1 节对p 2 p 的定义进行了阐述，并指出p 2 p 技术的思想并非是一种 全新的技术思想，而是早在互联网产生之初就已存在，只是现在以一个新的概念被重新提 出而已；在1 2 节，介绍了p 2 p 的分类及其各自所具备的特点；在1 3 节，针对两种网络 应用模式：p 2 p 模式和c s 模式进行了系统的分析比较，总结得出了其各自的优缺点；最 后，在1 4 节，介绍了p 2 p 的应用现状，探讨了在各个领域p 2 p 技术所发挥的巨大作用、 发展潜力以及现在所面临的困难。 1 1p 2 p 的定义 p 2 p 是p e e r - t o p e e r 的缩写，p e e r 在英语里有“( 地位、能力等) 同等者”、“同事和 “伙伴”等意义，因此p 2 p 网络又称为对等联网或对等网络，网络中的节点称为对等节点 或对等体，用p e e r 表示。 目前，学术界、工业界对p 2 p 还没有形成标准的定义，常见的定义方式有如下几种： 定义1 ：p 2 p 是一种运行于个人计算机上的应用程序，它通过互联网连接和其他用户共享文 件。p 2 p 通过连接彼此的计算机实现资源共享，而没有一个统一的服务器。 定义2 ：p 2 p 是一种互联网络，它允许一组计算机用户用一种同样的程序彼此相连，实现共 享磁盘上文件的目的。 定义3 ：p 2 p 是一种分布式网络，网络的参与者共享他们所拥有的一部分硬件资源，包括处 理能力、存储能力、网络连接、打印机等，这些共享资源需要由网络提供服务，能被其它 对等节点直接访问而无需经过中间实体，在此网络中的参与者既是资源( 服务和内容) 提供 者( s e r v e r ) ，又是资源获取者( c l i e n t ) 。 塑室塑皇奎堂堡主竺壅生兰垡笙兰 翌二兰! 坚塑堕 定义4 ：i b m 对p 2 p 的定义【1 1 如下：p 2 p 系统由若干互联协作的计算机构成，且至少具有 如下特征之一： 系统依存于边缘化( 非中央式服务器) 设备的主动协作，每个成员直接从其他成员 而不是从服务器的参与中受益； 系统中成员同时扮演服务器与客户端的角色； 系统应用的用户能够意识到彼此的存在，构成一个虚拟或实际的群体； 可见，在p 2 p 网络中，服务器与客户端之间的概念差别已变得模糊甚至已经消失，所 有成员共享网络资源并协同合作为其他成员提供服务，即p 2 p 弱化了服务器的概念，系统 中的各个节点不再区分服务器与客户端的角色，每个节点既可以请求服务，也可以提供服 务。因此，p 2 p 中的对等概念是指网络中物理节点在逻辑地位上的对等，而非处理能力的 对等。 简单的说，p 2 p 技术主要就是指由硬件形成网络连接后的信息控制技术，其主要代表 形式是在应用层上基于p 2 p 网络协议的客户端软件，例如n a p s t e r l 2 1 ，k a z a a ，e m u l e ， b i t c o m e t 3 】等。 其实，p 2 p 不仅仅是一种技术，更重要的是一种思想，一种“以人为本”的思想，这 种思想早在互联网产生之初就已存在。早期的网络比现在的网络更加开放和自由【4 1 ，就通 常意义而言，当时网络上的任意两台计算机都可以给对方发送网络数据包，网络就是人们 进行资源共享和协同工作的场所，后来随着计算机技术的缓慢发展与人们实际需求的快速 增长，要购置一台性能较高的计算机对大多数人来说都是难以实现的，因此网络中便出现 了少数成本昂贵的大型服务器，用来为大多数的终端用户提供服务，从而形成了现在以c s 模式为主的网络。尽管人们一般把当前的互联网看成是c s 模式的，但这并不代表其中就 没有p 2 p 的影子，比如网络中的邮件服务器( s m t p ) 、网络新闻服务器( n n t p ) 和域名服务 器( d n s ) 等，它们其实都运行于点对点网络中，以邮件服务器为例：为了发送、路由和接 收电子邮件，多台电子邮件服务器之间就需要直接的相互作用，因此可以被看成是p 2 p 网 络。 1 2p 2 p 网络模型 对p 2 p 的分类，目前尚不统一，一些学者认为像n a p s t e r t 2 】这类带有服务器的网络结构 不属于p 2 p 网络；另外一部分人则认为虽然带有服务器，但此处服务器的功能已在很大程 度上被弱化，资源共享不再自始至终都完全依赖于集中服务器，而且每个终端都同时具有 南京邮电大学硕士研究生学位论文 第章p 2 p 概述 请求服务与提供服务的功能，故可以将其视为广义的p 2 p 网络。根据目前p 2 p 的发展以及 在1 1 节中对p 2 p 定义的概述，本文认为第二种观点更为合理，故在此根据拓扑结构的不 同将p 2 p 网络模型划分为以下三种： 中心化模型 纯分布式模型 混合式模型 下面将对这几种不同的p 2 p 网络模型进行逐一介绍。 1 2 1 中心化模型 中心化p 2 p 网络模型的拓扑结构如图1 1 所示： 图1 1 中心化p 2 p 网络模型 图中，实线表示所有节点与集中目录服务器的连接，虚线表示任意两个普通节点间的连接。 在该类型的p 2 p 网络中，所有节点都与一个特殊节点相连，这个特殊节点称为集中目录服 务器，主要功能有：对网络进行集中式管理( 比如节点的登入和退出) ：记录所有节点上 共享资源的索引信息并向对这些信息发出查询请求的节点作出应答，但实际共享资源的传 输则直接发生在资源请求者与资源提供者之间。可见，集中目录服务器的功能相对于c s 模式网络中的服务器而言己被大幅度弱化，因此，中心化p 2 p 也可以认为是c s 模式向p 2 p 模式过渡的中间体。 由于中心化p 2 p 网络模型中存在一个中心节点，即目录服务器，上面记录着关于所有 节点上共享资源的索引信息，故当网络中任意一个节点要搜索某种共享资源时，只需将请 求发给该目录服务器就可以得知该资源在网络中的存储情况，然后就可以直接与拥有该资 源的节点建立连接并下载。因此，中心化p 2 p 网络模型具有非常突出的优点：便于管理， 南京邮电大学硕士研究生学位论文第一章p 2 p 概述 查询速度快；但是，它同样也存在一个致命的弱点：单点失败! 中心目录服务器在网络中 所承担的责任，决定了它必须具有较高的性能，包括处理器速度、内存及硬盘空间、带宽、 稳定性等，也就是说，一旦中心目录服务器在某些方面出现问题或遭到破坏，将导致整个 网络的瘫痪：此外，随着网络用户数量的剧增，中心目录服务器的负载也变得越来越大， 从而导致该网络模型在可扩展性方面受到了很大限制，因此只适合组建小规模的p 2 p 网络。 1 2 2 纯分布式模型 纯分布式p 2 p 网络模型的拓扑结构如图1 2 所示： 图1 2 纯分布式p 2 p 网络模型 在该类p 2 p 网络中，服务器的概念已完完全全不再存在，所有节点的功能都是相似的，即 逻辑地位都是对等的；各个节点之间以随机的、分散式的方式连接，每一个节点都可以通 过与相邻节点间的连接遍历整个网络，也就是说，一个孤立的节点只要与该p 2 p 网络内的 任意一个节点建立连接就可以加入网络并向其他节点请求服务或提供服务。以上两点真正 突显出了p 2 p 的本质，因此，如果说中心化p 2 p 是c s 模式向p 2 p 模式过渡的中间体的话， 那么纯分布式p 2 p 就可以认为是真正意义上的( 纯) p 2 p 了。 。 可见，纯分布式p 2 p 网络模型已消除了单点失败的问题，但是，这种随机的、分散式 的结构特点也给网络管理和资源定位带来了困难。在纯分布式p 2 p 网络中，常用的一种资 源搜索机制就是泛洪请求式搜索机制( 见2 2 节) ，它主要利用纯分布式p 2 p 网络模型中“每 个节点都可以通过与相邻节点间的连接遍历整个网络 的思想，在邻居节点间层层转发搜 索请求，直到满足一定的终止条件为止，可见这种带有盲目性的搜索机制是不适合大型网 络的，否则它所产生的网络流量将是不可估计的，因此也就限制了网络的可扩展性，针对 这一点，目前在纯分布式p 2 p 中已提出了一种新的基于分布式哈希表( d i s t r i b u t e dh a s h t a b l e ，d h t ) 的文件路由式搜索机制，其思想是通过对网络中的节点和资源建立一定的对 应关系，在进行资源搜索时按照此对应关系进行查找，从而避免了搜索的盲目性，大大提 4 南京邮电大学硕士研究生学位论文第一章p 2 p 概述 高了搜索的质量和效率。 1 2 3 混合式模型 混合式p 2 p 网络引入了超级节点的概念，其拓扑结构如图1 3 所示： 图1 3 混合式p 2 p 网络模型 混合式拓扑结构的p 2 p 网络实质上就是将整个p 2 p 网络划分成多个子集，每个子集都 是一个小型p 2 p 网络且采用中心化拓扑结构，子集中的集中目录服务器称为超级节点，所 有超级节点之间以纯分布式拓扑结构连接。超级节点一般由子集中性能较高的节点承担， 主要负责本子集内的信息查询以及将搜索请求转发给其它子集的超级节点。 相比于前两种p 2 p 网络模型，混合式p 2 p 网络就是将中心化p 2 p 和纯分布式p 2 p 合二 为一的一种网络模型。在这种模型中，子集的划分强有力的减弱了单点失败给整个网络造 成的不良影响，而且通过在每个子集中选出一个超级节点再以纯分布式连接的方式，也大 大减小了纯分布式网络的规模，有效的控制了因搜索请求的盲目性转发而带来的网络流量 的增加。 1 3p 2 p 模式与c s 模式的比较 对于中心化p 2 p ，由于所谓的“服务器”概念仍然没有完全消除，但相比于c s 模式 中的“服务器”又有很大不同，因此本文在前面将其归为广义的p 2 p 网络，并将它认为是 由c s 模式向p 2 p 模式过渡的中间体。在本节，主要针对( 纯) p 2 p 模式和c s 模式加以 比较，以明确当前对p 2 p 研究的重要性。 p 2 p 模式与c s 模式是两种截然不同的网络模式，但这并非说两者是相互排斥，互不 南京部电太学硕士研究生学位论文 第一章p 2 p 概述 相容的，实际上，在当前的互联网中，这两种网络模式都有所采用。下面就针对几个主要 的方面，对p 2 p 模式与c s 模式加以比较。 p 2 p 模式与c $ 模式瑷直观的比较如图14 所示： 蕈 毋 “”尊 。虿k 。 赢m c l i e n t 图1 4p 2 p 模式与c s 模式的比较 首先，从体系结构来看，p 2 p 模式采用无中心式结构，没有中心节点负责一致性控制、 任务调度、决策仲裁等工作，主要以各个节点之问的充分合作来完成各项工作，突显了p 2 p 网络的自治性：在c s 模式中体系结构则为中心化结构，系统由一个中心节点( 服务器) 来负责对网络进行统一的管理和维护。 其次，从资源利用方式来看，p 2 p 模式充分挖掘并利用网络边缘的资源，如存储能力、 计算能力和信息资源等，不但丰富了网络内容，而且使网络中的各种闲置资源被有效的组 织在一起加以充分利用；在c s 模式中网络资源的获得主要来自中心服务器客户端只 能从服务器上申请并得到服务，而无法将自身的资源有效的直接的供其它节点利用，从而 形成t n 务器的超负荷运行与客户端大量的( 存储计算) 能力被闲置的鲜明对比。 最后，从节点在网络中承担的角色来看 等是指网络中各个节点的逻辑地位是相同的 p 2 p 模式是一种对等的网络模式，所谓的对 任何一个节点都具有向其它节点申请服务和 提供服务的功能，换言之，每个节点既是客户端又是服务器；在c s 模式中，服务器和客 户端是两种截然不同的角色，相应的功能也是存在巨大差异的服务器主要负责管理和维 护整个网络，并向所有的客户端提供瓷源和服务，而客户端则只能向服务器提出申请然后 得到相应的资源或服务。 通过以上分析比较可以看出，p 2 p 模式与c s 模式相比具有以下优点： 健壮性方面，在p 2 p 模式中，由于资源是分散在各个节点上的，服务的提供也是通过 各个节点之间的协同合作来完成的，无需中心服务器来控制因此它不存在像c s 模 式中的“致命点”现象，部分节点遭到破坏并不会给网络的其他部分带来严重的不良 影响。 6 m 料-j l 默 m l 曼 南京邮电大学硕士研究生学位论文 第一章p 2 p 概述 可扩展性方面，在p 2 p 模式中，随着节点用户的加入，尽管服务的需求增加了，但系 统整体的资源和服务能力也在同步地扩充，从而能够较容易的满足用户的需要，因此 p 2 p 模式削弱( 或消除) 了c s 模式中网络的规模受限于中心服务器性能的现象，相 对于c s 模式具有较强的可扩展性。 负载均衡方面，在p 2 p 模式中，所有节点的逻辑地位都是均等的，每个节点不但能够 向其它节点请求服务和资源，而且还能为其它节点提供服务和资源，所有的节点已不 再区分客户端与服务器角色，因此，p 2 p 模式中不存在像c s 模式中服务器的超负荷 运行与客户端资源被闲置形成鲜明对比的情况。 性价比方面，随着硬件技术的发展，个人计算机的存储计算能力和网络带宽等性能都 在不断得到改善，在p 2 p 模式中，主要的资源利用方式是挖掘网络边缘的资源( 包括 存储计算能力、带宽、信息资源等) ，并将其整合到一起加以充分利用，共同协作为 网络提供各种服务，以达到高性能计算和海量存储的目的。也就是说，p 2 p 模式通过 利用网络边缘节点上的大量空闲资源，以更低的成本来提供在c s 模式中只有高性能 设备( 服务器) 才具备的存储和计算能力。 隐私保护方面，在p 2 p 模式中，信息的传输已无需像c s 模式中要经过某个集中环节， 而是分散在各个节点之间，所有的节点都可以像c s 模式中的服务器一样具有中继转 发的功能，因而有效的提高了匿名通讯的灵活性和可靠性，使得隐私信息被窃听和泄 漏的可能性大大缩小。 1 4p 2 p 的应用现状 随着p 2 p 技术的发展，越来越多的领域都开始了对p 2 p 的研究与应用，但是无论如何， p 2 p 技术至今还是一项很不成熟的技术，在未来的发展中还面临着一系列难以解决的问题， 下面我们就从p 2 p 技术的应用领域和当前面临的困难两个方面来进行介绍。 1 4 1 应用领域 不同于以往的c s 模式，在p 2 p 模式的网络中，它允许i n t e r a c t 用户直接连接到其它 用户的计算机进行资源共享，而不需要连接到服务器上浏览与下载，由于消除了中间环节， p 2 p 技术使得网络上的沟通变得更加容易和直接。这些特点促使p 2 p 网络在对等计算f 5 1 、 协同工作【6 】及资源搜索和共享7 1 等方面都得到了广泛应用。 对等计算 7 南京邮电大学硕士研究生学位论文第一章p 2 p 概述 通过众多计算机来完成超级计算机的功能，一直是科学家梦寐以求的事情。采用p 2 p 技术的对等计算，正是把网络中的众多计算机暂时不用的计算能力连结起来，使用积累的 能力执行超级计算机的任务。任何需要大量数据处理的行业都可从对等计算中获利，如天 气预报、动画制作、基因组的研究等，有了对等计算之后，就会大大减少对昂贵的超级计 算机的需求。例如：s e t i h o m e t 8 1 。 协同工作 公司机构的日益分散，给员工和客户提供轻松、方便的消息和协作的工具变得日益重 要。p 2 p 技术的出现，使得互联网上任意两台p c 都可建立实时的联系，建立了这样一个 安全、共享的虚拟空间，人们可以进行各种各样的活动，这些活动可以是同时进行，也可 以交互进行。例如：g r o o v e 9 1 、s k y p e 1 0 1 。 搜索引擎 当前c s 模式的搜索覆盖面狭窄，即使使用强大的搜索引擎( j t n g o o g l e ，百度，a s kj e e v e s 等) 也难以到达网络的边缘，因此它难以充分利用互联网为数众多的客户端资源，而p 2 p 技 术的提出则在此方面有了很大改善，它使用户能够深度搜索文档，搜索目标不仅包括传统 的w w w f j 务器，还包括网络上不计其数的个人电脑。传统的搜索引擎只能搜索到2 0 一3 0 的网络资源，而运用p 2 p 技术的搜索引擎在理论上则可以搜索到网络上所有开放的信息资 源。此外，在j x t as e a r c h 中还认为采用p 2 p 的搜索技术可以有效的跟踪数据的更新速度 【l l 】【12 1 、提高访问的有效性以及检索的效率。例如：i n f r a s e a r c h 1 3 1 、p a n d a n g o 1 4 1 。 文件共享 在传统的w e b 方式中，要实现文件交换需要服务器的大力参与，通过将文件上传到 某个特定的网站，用户再到某个网站搜索需要的文件，然后下载，这种方式的不便之处不 言而喻。此外，电子邮件虽然方便了个人间文件的传递问题，但是却无法解决大范围的文 件交换，p 2 p 使大范围的文件交换成为可能。例如：n a p s t e r t 2 1 ，e d o n k e y , b i t c o m e t 3 1 。 总之，p 2 p 技术不仅为个人用户提供了前所未有的自由和便利，同时也试图有效地整 合互联网的潜在资源，将基于网页的互联网转变成动态存取、自由交互的海量信息网络， 它的应用己逐渐渗透到各个领域，并以其极大的优势吸引了业界目光。 1 4 2 当前面临的难题 资源定位和分布式路由 在p 2 p 网络中，对等节点之间如何进行准确的资源定位，如何形成自组织结构，这是 堕室墅皇查堂堡主至窒竺兰垡堡奎 笙二皇! 竺塑堕 p 2 p 技术中最核心的问题，同时也是p 2 p 系统所面临的晟大挑战。由于p 2 p 网络是一个动 态的环境，用户可以随时加入，也可以随时退出，网络中的资源在地理位置上是非常分散 的，而且部分节点并没有永久的地址，这种动态特性使得资源发现和节点定位机制变得异 常复杂、难以维护。目前已有很多学术机构和技术公司在如火如荼的开展这方面的研究， 并且取得了丰硕的理论成果，但是由于缺乏对实际应用的支持，并没有成为大规模的应用。 网络带宽 p 2 p 在网络带宽方面的问题可分为两个部分：吞噬网络带宽问题和对称网络带宽问题。 p 2 p 使网络变得空前活跃，越来越多的用户开始参与到p 2 p 网络并在彼此之间传送文件， 特别是一些大体积的m p 3 文件、视频文件等，这将大量吞噬网络带宽，网络带宽较窄便成 为了p 2 p 应用难以逾越的障碍；对称带宽问题则是指在p 2 p 网络中，许多p 2 p 应用程序都 是既运行客户端又运行服务器端的应用程序，所以既占用下行带宽又占用上行带宽，而且 两者的比例很有可能会达到持平的状态，而在传统的c s 模式网络中，由于客户端只占用 少量的上行带宽，因此大多数i s p 提供的都是非对称的带宽通道，这在很大程度上影响了 p 2 p 的发展。 版权问题 在服务器环境中，对访问数据的用户进行验证和授权是一件简单的事情，数据、验证 服务和权限管理都集中在服务器上，而p 2 p 分散了内容的分发，正如n a p s t e r 一样，大多 数p 2 p 服务都将可能和知识产权发生冲突。尽管美国唱片协会等一些组织正在寻找一种新 的方式来保护知识产权，但是，每一个提供文件共享服务的p 2 p 公司都不得不认真审视p 2 p 网络面临的版权问题。 管理困难 。p 2 p 网络的精髓在于其”乌托邦”式的管理方式，这种方式给了用户更多的自由，但这 也使整个网络陷入了“无政府主义的困境。比较难办的事情之一就是控制用户的行为， 问题在于p 2 p 网络中没有存储有关用户行为信息的集中点，没有中心授权机构，所以要确 保所有用户的行为都符合规范是件非常困难的事情。可以想象，缺乏管理的p 2 p 网络将会 成为病毒、色情内容以及非法交易的温床。 标准问题 关于p 2 p 的标准问题，首先是w e b 标准操作过程对p 2 p 的影响，目前w e b 是网络上的 主要使用模式，网络所采用的底层基本架构、技术和基于网络服务器所使用的协议等w e b 标准操作过程都非常有利于w e b 应用的开展，这些w e b 标准操作过程被i s p 和许多公司所 使用，它们都希望用户通过网络浏览器使用它们的服务，但是，p 2 p 阿络却与w e b 不同， 9 南京邮电大学硕士研究生学位论文 第一章p 2 p 概述 可以说它是另一种截然不同的应用模式，因此，它的发展对已有的w e b 标准提出了一种挑 战；其次是p 2 p 内部的各种标准之争，目前，大多数p 2 p 应用软件都是彼此不兼容的，原 因在于它们来自于不同的开发者，应用不同的编程语言、不同的平台以及不同的规范开发， 因此，为了对p 2 p 的各种应用制定一种统一的标准或规范，i n t e l 和s u n 等公司都在致力于 p 2 p 标准的统一，并力图成为p 2 p 未来的引领者。 1 0 南京邮电大学硕士研究生学位论文第二章p 2 p 资源搜索机制 第二章p 2 p 资源搜索机制 资源定位问题是p 2 p 网络的核心问题之一，也是p 2 p 网络当前研究的热点。对基于p 2 p 的资源共享网络来讲，服务提供者的边缘化特点解决了服务器性能和带宽的瓶颈问题，但 同时也将影响系统性能的关键要素转移到了对资源的发布、搜索和获取上，因此本章就p 2 p 网络中的基本搜索机制：集中目录式搜索机制、泛洪请求式搜索机制和文件路由式搜索机 制作了详细介绍，现有的其它各种搜索机制均可认为是在此三者基础上的改进或扩充。 2 1 集中目录式搜索机制 集中目录式搜索机制，顾名思义，就是由网络中的一个节点来集中保存和维护一份网 络上所有节点的共享资源目录，以供其它节点查询和使用。在2 1 1 节将具体介绍它的思 想原理，并在2 1 2 节举例分析，最后在2 1 3 节介绍其优缺点。 2 1 1 原理 在集中目录式搜索机制中，利用一个称为“集中目录服务器 的中心节点来为其它节 点提供共享资源的信息索引服务，网络中任何一个节点发布共享资源时只需将所发布资源 的概要信息以及节点本身的信息登记到集中目录服务器上即可，其它节点在搜索该资源 时，首先到集中目录服务器上查看有无相关记录，若无，返回查询失败的应答信息，若有， 则根据目录中所记录的相应节点的信息与该节点建立网络连接，直接进行资源传输。 2 1 2n a p s t e r 最初的p 2 p 音乐共享软件n a p s t e r 【2 1 采用的就是集中目录式搜索机制，它的结构如图2 1 所示： 南京邮电大学碗研究生学位论文第二章p 2 p 资源搜索机制 图2 1n a p s t e r 结构 n a p s t e r 是最早的p 2 p 实用系统，目的是为广大的音乐爱好者提供一个丰富、自由而且 免费的两络音乐共享平台，参与系统的是大量个人计算机用户，每个用户都可以将自己愿 意共享的文件发布出来，同时也可以下载其他用户发布的共享文件。 在n a p s t e r 的实现中，需要解决的核心问题是必须知道哪些节点上有哪些文件列为共 享，这样当用户提出文件搜索请求时才可以得到正确的匹配结果。因此，为了解决上述问 题，n a p s t e r 使用了一个中心服务器，称为目录服务器，用于存放所有文件的元数据信息( 文 件标题和一些简单的描述信息) 以及存放这些文件的节点i p 地址。节点加入系统时，首 先要连接到目录服务器并报告自身地址及共享的文件列表；当用户需要某个文件时就向目 录服务器提交搜索请求，目录服务器返回符合搜索请求的所有文件的存放地址；用户根据 对应的地址直接从共享文件的存放节点上下载该文件。由于在整个过程中，目录服务器只 提供索引服务，而不承担文件存储和下载服务，因此它支持上万节点同时在线。 n a p s t e r 在发布后迅速流行起来，很快成为增长最快的p 2 p 网络应用系统它第一次验 证了p 2 p 思想在广域网范围内的可行性。然而，随着n a p s t e r 用户群体的不断壮大，它自 身所存在的问题也不断突显出来，比如系统的健壮性( 单点失败) 、可扩展性等，并最终 因涉及到音乐文件的版权问题而被告上法庭。 2 1 3 优点和缺点 通过对p 2 p 音乐共享软件n a p s t e r 的举例分析，可以总结得出集中目录式搜索机制具 有以下优点和缺点： 优点一：查询速度快 由于目录服务器记录了网络上所有已发布的共享资源信息及其发布者的情况，囡此， 1 2 南京邮电大学硕士研究生学位论文 第二章p 2 p 资源搜索机制 当一个节点要搜索某种资源时，只需向该目录服务器发送一个查询请求即可，同时还由于 目录服务器并不参与共享资源的实际存储与传输，故可以迅速处理收到的请求并返回相应 的答复，保证了一定的查询效率。 优点二：产生的网络流量少 网络中的节点在进行共享资源的搜索时，搜索请求具有明确的接收目标，不会在网络 上被盲目的转发，减少了不必要的网络流量的产生。 优点三：易于管理 集中目录式搜索机制不受网络拓扑结构变化的影响，无需维护网络拓扑信息，并且中 心节点“目录服务器 能够很好的的对网络中的共享资源进行集中管理，有效控制不法内 容在网络中的扩散行为。 缺点一：健壮性差 要增强网络的健壮性，首先就要避免网络结构中“致命点”的存在，而在采用集中目 录式搜索机制时，集中目录服务器恰恰就成为了一个“致命点”，一旦其遭到不法的攻击 或出现其他意外情况，整个网络的资源共享将陷入瘫痪状态。 缺点二：可扩展性差 在集中目录式搜索机制中，目录服务器所实现的功能虽然比c s 模式中真正意义上的 服务器所实现的功能要少的多，但是性能极限还是存在的，所以，p 2 p 网络规模的扩大在 一定程度要受限于集中目录服务器性能的高低，也就是在可扩展性方面还存在着不足。 缺点三：负载不均衡 集中目录式搜索机制中，目录服务器所承受的负载相对于其它普通节点而言仍然要高 出很多，当其不堪重负时，将会对整个网络产生严重的不良影响。 2 2 泛洪请求式搜索机制 不同于集中目录式搜索机制，泛洪请求式搜索机制在网络中不设置任何特殊节点，信 息查询请求以“泛洪”的方式在网络中传播。下面将在2 2 1 节讲述泛洪请求式搜索机制 的思想原理，并在2 2 2 节举例分析，最后在2 2 3 节总结得出其优缺点。 2 2 1 原理 在泛洪请求式搜索机制中，没有设置任何特殊的节点来负责记录共享资源的相关信息， 所有节点都同属于一种角色；每一个节点都是通过与邻居节点的连接来遍历整个网络。当 1 3 塑塞苎皇查兰堡主里墨兰! 些丝兰堡三苎垦! 塞翌塑塑垫型 网络中的某个节点要搜索某种资源时，该节点首先将搜索请求转发给自己的所有( 或部分) 邻居节点当邻居节点收到该请求后对自己的共享资源列表进行查询，若有相关资源存在， 就按原路返回应答消息，若无，则继续将该搜索请求再转发给自己的所有( 或部分) 邻居 节点，如此继续下去，直到达到一定的终止条件为止。 22 2g n u t e l l a g n u t e l l a 1 那q 是继n a p s t e r 之后的另一款p 2 p 资源共享软件，其结构如图2 2 所示 喜裔絮 # 目胪 n o 十 图2 2g n u t e l l a 结构图 g n u t e l l a 由美国在线a o l ( a m e r i c ao n l i n e ) 公司的n u l l s o f l 部门开发，作为n a p s t e r 的开放源代码代替方案发布。g n u t e l l a 的创始者创建了一种类似于但又似乎完全不同于 n a p s t e r 的系统，相似之处在于都以文件共享为目的，不同之处在于它们采用完全不同的搜 索镱略。 g n u t e l l a 中不再设置中心目录服务嚣，而是使用纯粹的对等结构，每个节点都记录了 一组其邻居节点的i p 地址且都可以通过与邻居节点的连接遍历整个网络。当节点加入 网络时，首先要了解周围邻居节点的路由等情况并作记录：节点要搜索某种资源时，预先 并不知道该资源的存放位置，首先按规定的格式生成搜索请求，为防止搜索请求在网络中 无限制的转发，通常为该搜索请求设置一个生命周期值t t l ( t i m et ol i v e ) ；然后资源 请求者根据自己记录的邻居节点情况将搜索请求转发给邻居节点_ 丌l 值减l ；接收到搜 索请求的邻居节点查看自己的共享文件列表以确定是否拥有该资源，若有，返回应答消息， 若没有查看t t l 值t t l 不为0 ，继续将请求转发给自己的邻居节点，t t l 等于0 ，则终 止转发；资源请求者收到应答消息后根据消息中的节点信息，与该节点建立连接传输共 享文件。 1 4 一一一淞 襄掌 雾 。箩吨簟蕊。謦 雨京邮电大学硕士研究生学位论文第二章p 2 p 资源搜索机制 在g n u t