（计算机软件与理论专业论文）非结构化p2p系统搜索机制的研究.pdf

郑州大学硕l ：学位论文 摘要 在文件共享应用领域，非结构化p 2 p 系统由于其简洁性和健壮性取得了巨大 的成功。但是，非结构化p 2 p 系统的扩展性问题制约了其快速发展。 本文以g n u t e l l a 为例，研究了非结构化p 2 p 系统近年柬的搜索优化技术。根 据现代g n u t e l l a 网络的特点，提出了一种有助于改进非结构化p 2 p 系统扩展性的 搜索机制初始洪泛搜索机制i i l i t i a l f l o o d 。该机制根据消息的t r l 值把搜索 过程分为两个阶段：第一个阶段采用标准的洪泛方式来传播消息，第二个阶段则 选择连接度最小的邻居节点传播消息。经实验证明，i n i t i a l f l 0 0 d 搜索机制可以大 大减少网络中的冗余消息，而消息的传播范围基本保持不变( 和标准洪泛搜索时 的相似) ，提高了资源搜索效率，有效改善了现代g n u t e l l a 网络的扩展性。 针对g n u t e l l a 网络和底层网络拓扑结构不匹配的问题，本文引入了优先邻 居节点的概念。当节点连接到g n u t e l l a 网络时，选择网络中和自身节点地理位置 较近的节点连接，可以缓解g n u t e l l a 网络层给底层基础设施带来的压力。 关键词：非结构化p 2 p 系统，搜索机制，洪泛，初始洪泛搜索，优先邻居节点 郑州人学顶i 学位论文 a b s t r a c t i nt h ef i e l do fa p p l i c a i i 帆o ff i l es h a r i n g ，u n s t n ，c t u r e dp 2 ps y s t e mh a sg a i n e d g r e a ts u c c e s sb e c a u s eo fi t ss i m p l i c i t ya n df o b u s t n e s s b u t ，b a d i ys c a l a b i l i t yo f u n s t m c t u r e dp 2 ps y s t e mr e s t r i c t e di t sr a p i dd e v e l o p m e n t i nt h i sp a p e r w es t u d i e dg n u t e l l as e a r c h j n g 叩t i m i s a t i o nt e c h n i q u e si nt h er e c e n t y e a r s b a s e do nc h a r a c t e r i s t i c so fm o d e mg n u t e l l a ，w ep m p o s e dan e ws e a r c h i n g m e c h a n i s mb e t t e rf o rs c a l a b i l j t yo fu n s t m c l u r e dp 2 p s y s t e m ：l n i t i a l f l o o d t h e s e a f c h i n gp r o c e d u r ei ni n i t i a l f l o o di sd i v i d e di n t ot w os t a g e sa c c o r d i n gt ot t l o f m e s s a g e i nt h ef i r s ts t a g e ，am e s s a g ci sp r o p o g a t e db yu s i n gt h es t a n d a r dn o o d i i l g s c h e m e 1 nt h es e c o n ds t a g c ，t h em e s s a g ep r o p a g a t i n gi so n l yc o n d u c t e dt h r o u 曲t h e n e 谵h b o rs e r v e n tw h o s ed e g r e ei st h el e a s t o u rs i m u l a t i o nr e s u l t ss h o wt h a t i n i t i a l f l o o dc o u l dg r e a l l ym i n i m i z et h en u m b e ro ff e d u n d a n tm e s s a g e sa n dr c t a i nt h e s a m em e s s a g ep r o p a g a t i n gs c o p ea st h a t0 fs t a n d a r df 1 0 0 d i n gs c h e m e i m p m v e s e a r c h i n ge f ：f i c i e n c ya n ds c a l a b i l i t yo fm o d e mg n u t e l l a w ei n t r o d u c e dt h en o l i o no fp r c f e r c n t i a ln e i g h b o rn o d ei n0 r d e rt oa d d r e s st h e m i s m a t c ho ft o p o l o g yb e 柳e c ng n u t e l l a so v e r l a yn e 咐o r ka i i dt h ei n t e m e t s e l e c t i n g t o p o 】o g i c a l l yc l o s en o d et o j o i ng n u t e h a n e t w o r kc o u l da l l e v i a t et l l ep r e s s i o no n u n d e r l y i n gi n f r a s t r u c t u f ew h e nan o d ei n i t i a t e st h ec o n n e c t i o n k e y w o r d ：u n s t r u c t u r e dp 2 ps y s t e m ，s e a r c h j n gm e c h a n i s m ，n 0 0 d i n g ，i n i t i a l f l o o ds e a r c h i n g ， p r e f e r e n t i a ln e i g h b o rn o d e i l 郑卅i 大学顺i 学位沦文 图表目录 幽21 非结构化p 2 p 系统的三种模型9 幽31g n u t e l l a 网络的模型图14 表3 一lg n u t e ll a 协议通信描述符16 幽3 2g n u t e l l a 网络的资源定位机制16 图3 3 现代g n u t e l l a 网络分层的体系结构一17 图3 4 本地索引法：【作示例2l 图4 一lp 2 p 形成的覆盖网络和底层基础设施之间的映射幽23 表4 一l 现代g n u t e l l a 网络中不同应用系统的分布24 幽4 2 现代g n u t e l l a 潮络超级节点连接度分布图25 图4 3 标准洪泛机制消息跳数和覆盖增长率29 幽44 标准洪泛机制消息跳数和冗余消息3o 图4 5 选择邻居个数为1 时所构造得f 1 0 0 d t r e e 31 表5 1 不同连接度节点在网络中所i b 的卣分比33 图5 一li n i t j a l f l 0 0 d 机制和标准洪泛机制消息覆盖范罔的比较35 幽5 2i n i t i a l f l 0 0 d 机制和标准洪泛机制冗余消息的比较36 例j 一3i n i t i a 】f 1 0 0 d 机制在不同网络中的消息覆盖率37 幽54i n i t i a l f j o o d 机制在不同潮络中的冗余消息希j 标准洪泛冗余消息的百分比37 幽5 5 网络。1 ，点火效时消息的覆盖率一38 v 1 郑重声明 本人的学位论文是在导师指导下独立撰写并完成的，学位论文没有剽窃、抄 袭等违反学术道德、学术规范的侵权行为，否则，本人愿意承担由此产生的一切 法律责任和法律后果，特此郑重声明。 学位敝慨们噜瘁 沙9 年6 月弓日 郑州人学吲 j 学位论殳 1 1 研究背景 第一章引言 就商业应用而言，对等网络( p e e r t o p e e r ，p 2 p ) 正如所有新兴技术一样尚 且羽翼未丰。它已经显示出强大的发展潜力但是也遭受了许多障碍。在理论上， p 2 p 使得人们通过网络例如i m e 功e t 交换信息更加方便了，而且需要i t 管理人员干预的程度已经降到了最低限度。传统的网络应用迫使人们通过服务器 进行通信，而p 2 p 应用允许终端用户( 对等机器) 平等地交换彼此共享的资源。 “你可以与某个人直接建立连接，就像打电话一样。”g r o o v e 网络公司的战略市 场总监a n d r e wm a h o n 说，这家公司的p 2 p 应用是u sn o t e s 的创造者r a yo z z i e 的杰作。 p 2 p 是一种分布式技术，不同于c l i e n t s e r v e r ，b r o w s e r s e r v e r 和s l a v e m a s t e r 等传统模式，它抛开了应用服务器的束缚，使得网络中的节点以一种对等的方式 共享这些节点的存储空间、处理器计算能力、网络带宽等资源。一方面节点问可 以直接进行交互，不再需要服务器作为媒介进行中转，从而使交流更赢接，效率 更高；另一方面节点不再依赖中央服务器，从而解决了因服务器能力不足而引起 的性能瓶颈问题，增强了系统的可扩展性，同时也避免了因中央服务器的失效而 导致的整个系统无法工作的可能性，使得系统的可靠性更强。p 2 p 技术最初用于 音乐文件共享，随着技术的发展逐步扩展到普通的数据文件共享、分布式计算、 通信和 办作等多个应用领域。 p 2 p 在很多方面有重要应用，文件共享就是目前最重要的一个应用。如何实 现资源的定位是文件共享的首要问题。g n u t e l l a 被认为是纯粹的非结构化p 2 p 系统 的典型代表，目前世界上使用用户最多的文件共享系统都是基于g n u t e l 】a 系统模 型发展起来的。g n u t e l l a 主要的问题是使用“洪泛”方式搜索网络节点及共享信 息，随肴网络规模的增长，不仅用于搜索的消息比率在增长，而且由每条消息产 生的潜在流量也在大幅增长。据2 0 0 1 年3 月的统计报告”，g n u t e j i a 网络中有大约 5 5 的流量屉l l j 于p i n g 和p o n g 消息包产生的，有大约3 6 的流量是由于q u e r y 消息 包j 一：j ，其r 扣包括了大最的兀余信息，严厦吞噬刚络带宽，影i l i 自网络性能，制 邦州大学坝1 ：学位论文 约了网络进一步的发展。近年来随着网络规模的不断增大，网络密集化程度也越 来越高，虽然g n u t e l l a 系统做了一些改进，但是其用于资源定位的搜索机制“洪 泛”的本性辨必会加重网络的负担。因此，进一步研究和改进g n u t e l l a 系统，特 别是改进其搜索机制，对于增强非结构化p 2 p 系统的扩展性来说仍然具有积极的 意义。 1 2 研究目标 目前非结构化p 2 p 系统在文件共享领域取得了巨大的成功。系统中每一个联 网的计算机在功能上都是相似的，既是客户机同时又是服务器，称为对等体 ( s e r v e n t ) ，没有专门的目录服务器，因此，也被认为是纯分布式p 2 p 网络系统。 其面临的主要问题是网络中对等体节点利用“洪泛”方式来搜索网络和发现共享 信息。随着联网节点的不断增多，网络规模不断扩大，通过这种“洪泛”方式定 位对等体的方法将造成网络流量急剧增加，从而导致网络中部分低带宽节点因网 络资源过载而失效，这样会使得网络被分片、查询访问只能在网络的很小一部分 进行，因此系统的可扩展性不好。所以，解决非结构化p 2 p 系统的可扩展性对该 网络的进一步发展至关重要。 1 3 本文工作 非结构化p 2 p 系统在p 2 p 文件共享系统中占有重要地位，当前许多非结构 化p 2 p 系统都是基于g n u t e l l a 系统模型发展起来的。 本文以g n u t e l l a 为例，简要概述了当前流行的一些搜索优化技术。然后针 对现代网络发展的特点和趋势，分析了影响g n u t e l l a 系统扩展性的主要原因：( 1 ) g n u t e l l a 网络拓扑结构和底层网络拓扑结构的不匹配性，( 2 ) “洪泛”方式的搜 索机制在网络中引入了过多冗余消息，( 3 ) 由于g n u t e i l a 协议中没有考虑网络节 点性能之矧的差异性，容易造成节点的网络资源过载而导致网络分片。 针肘这些原因，我们提出了些解决方案，具体如下： 爵先引入了优先邻居节点的概念。通过修改g n u t e l l a 协议，节点在加入网 络时r ，j _ 以根据应答消息中的l p 地址信息选择离自身地理位置最近的肖点连接， 使得g n u l c l l a 网络更好地匹配底层网络。 郑州人学坝1 j 学位论文 其次，对g n u t e l l a 协议中的资源搜索机制进行改进：根据消息的t r l 值把 搜索过程分为两个阶段：第一个阶段仍然采用标准的洪泛机制来传播消息，第：二 个阶段则选择连接度最小的邻居节点继续传播消息。和标准的洪泛搜索机制相 比，大大减少了网络中的冗余消息，而消息的传播范围基本保持不变。 本文的意义在于通过对g n u t e l l a 协议的改进，可以使g n u t e l l a 用户摆脱网络 过载问题的困扰，同时也提高了网络的稳定性和服务质量，有效的缓解了网络扩 展性的问题。使更多用户能够通过g n u t e l l a 网络提供便利服务，共享其它用户提 供的资源。文中的方法和结论可以为非结构化p 2 p 系统搜索机制的研究提供参 考。 1 4 论文组织 本文共分为六章，按照如下方式组织。 第一章对p 2 p 系统的研究背景、研究目标做简要介绍，同时给出本文工作 和文章的组织结构。 第一= _ 章从p 2 p 的起源入手，介绍了p 2 p 的概念、发展历程、p 2 p 文件共享 系统的分类、p 2 p 的关键技术以及主要应用。 第：二章介绍了g n u t e l l a 系统，包括协议的发展和系统模型，以及相关的搜 索优化技术。 第四章详述了g n u t e l l a 系统当前的特点和发展趋势，指出了影响g n u t e l l a 系统扩展性的主要原因，劳从g n u t e l l a 协议本身加以分析说明。然后针对这些原 因对 办议提出了改进，并提出一种新的资源搜索机制i n i t i a l f l o o d 。 第f i 章通过实验对这种新的资源搜索机制进行了模拟，并对结果进行了分 析比较。 筇穴章给出本文的总结，以及非结构化p 2 p 系统进一步发展的展望。 郑州人学倾i 。学位论文 2 1p 2 p 起源 第二章p 2 p 概述 p 2 p 应用技术在近年来得到了广泛的发展，越来越多的研究机构和团体加入 到这个新兴的应用领域。实际上，这个新兴领域所倡导的对等思想和建立i n t e r n e t 网络的初衷是完全一致的，可以说现在p 2 p 应用的兴起正象征着网络向自然的回 归。 2 1 1i n t e m e t 起源 众所周知，作为全世界最大的计算机网络，h l t e m e t 起源于美国国防部高级 研究计划局( a r e a ) 于1 9 6 8 年主持研制的计算机试验网a r p a n e t ，而建网的初 衷是用于支持军事研究，帮助那些为美国军方工作的研究人员通过计算机交换信 息。a r p ：a n e t 的设计与实现是基于这样的一种主导思想：网络要能够经得住故 障的考验并维持正常工作，当网络的一部分因受攻击而失去作用时，网络的其它 部分仍能维持运转。 上世纪八十年代，为了实现当时众多的大学、研究机构、政府部门进行电 子邮件的交换和信息资源的共享，在美国政府的帮助下美国国家科学基金( n s f ) 组建了一个由各自的局域网利用t c p l p 协议并入而成的网络，命名为n s f n e t 。 伴随着t c p l p 协议的成长，n s f n e t 在1 9 8 6 年建成后取代a r p ：a n e t 成为 i n t e m e t 的主干网。后来，人们便把使用t c p i p 支持的n s f n e t 网叫做i n t e m e t 网，即当今世界最大的计算机互连网因特网。 实际上，i n t e r n e t 就是基本的埘等式机制。i n t e m e t 最基本的协议t c p l p 没有 客户机和服务器的概念，所有的设备都是通讯平等的一端。用户可以很容易地连 接到实际的 r 算机并与之进行交互，众多对等的计算机构成庞大而稳定的嘲络， 当网络的一部分失去作用时，网络的其余部分仍能维持。这就是i n t e m e t 建立的初 衷，而这恰恰就是p 2 p 模式，可以 兑】n t e 功e f 就是以p 2 p 起源的。i n t e r n e t 的用户最 终就是通过协 义标准使用网络来共享信息。他们在技术卜是非常对等的，并且在 消赞( 读墩信息) 和q i 产( 发如信息) 之m 保持一种平衡。这种网络几乎就韪纯 郑州人学碗i 学位论文 粹的p 2 p 。但是，出于起初的参与者数量有限，再加上软件和硬件资源的局限性 使得早期i n t e m e t 巨大的潜力未能被人们充分地认识和利用。 2 1 2w e b 发展及瓶颈 随后，一个崭新的i n l e m e t 时代到来了。1 9 9 1 年，在欧洲粒子物理研究所：j ： 作的英国科学家蒂姆伯纳斯李为了高能物理研究的需要发明了万维网。万维 网的核心是w 曲浏览器和超文本标记语言( h t m l ，h y p e n e x t m a f k u p h n g u a g c ) 。 h t m l 是一种用柬创建网页的简单的计算机语言，其更核心的是 r 兀p 它是一 种协议，它告诉浏览器到哪里去寻找网页和它的元素。4 年后，美国网景公司推 出了万维网产品，顿时风靡全球。万维网在诞生后的大约1 0 年里，给全球信息 的交流和传播带来了革命性的变化，一举打开了人们获取信息的方便之门。 万维网的价值在于它使得不精通技术的用户也能够获取信息，所有用户获 取信息要做的就是简单地指向和单击。而浏览器将复杂的地址和网络特性隐藏在 用户视线之后。万维网从诞生之闩起便憧憬着创造一个共同的信息空间，使用户 川以通过它实现信息的共享，进行交流。这正体现了互联网的精神和核心价值， 但随着对w e b 的熟悉，人们开始发现，用户使用w 曲虽然可以容易地访问信息， 但却不能很容易地发行信息，w 曲的发展遇到了瓶颈。信息的消费者只要操纵一 只鼠标，便可以实现其用网目的，而信息发布者却必须要掌握h t m l 、d n s 注 册、w e b 服务器、公共网关接口( c g l ，c o m m o ng a t e w a yi n t e 仃a c e ) 和一些冗长 而乏味的缩写词和技术术语所代表的计算机技术。信息消费者和信息生产者之间 原有的平衡被打破了：大的组织特别是一些商业组织有时问和能力来掌握信息生 成的复杂性，丽个人用户则沦为纯粹的消费者。这种彳i 平衡性实质上违背了互联 网乎等的概念，也正是由于这种不平等使得信息交流、共享和协同工作等其他网 络功能的充分发挥受到一定的制约。 2 1 3 p 2 p 时代 首丌p 2 p 应用之风的最有名的计划是由美园加州大学伯克利分校，f 展的寻 找地外，k 命迹缘的科学项目s e t i h o m e 研究计划”。s e ” h o m e 项1 丰要 5 郑州人学硕i 。学位论文 是利用i n t e m e t 上p c 的闲置能力来分析世界上最大的射电望远镜获得的数据， 以帮助科学家探索外星生物。从s e l l h o m e 项目正式启动以来，已经有4 5 0 万 志愿者参加了这个项目，总处理数据量达到了1 5 t ，平均每位参与者让自己的电 脑为s e t i h o m e 工作了1 7 个半小时，这相当于使用一台p c 机工作4 8 2 0 2 3 年， 相当于使用超级计算机工作4 8 年。这个项目充分利用了分布在世界各地计算机 的力量，虽然整个计划耗资只有5 0 万美元，却拥有强大的威力。 而真正让p 2 p 家喻户晓的是2 0 0 2 年美国的一场著名官司，被告名叫n a p s t e r 。 n a d s t e r 提供一种免费软件，用户安装联网后，p c 就变成了一台m p 3 服务器， 可以实现本地m p 3 资源的全球共享，无数台这样的个人电脑交织成一个庞大的 m p 3 资源网络。此举等于砸了传统唱片商的饭碗，代表传统产业利益的美国唱 片协会( r i a a ) 和美国音乐出版协会( n n mp ：a ) 自然视之为洪水猛兽，欲置之 死地而后快。结果我们都已知道：n a p s t e r 以败诉收场。但是令r i a a 们始料不 及的是：p 2 p 就像被开启的潘多拉的宝盒，非但没有被扼杀于襁褓中，反而生生 不息地繁衍下来。n a p s t e r 与r m a 的恩怨情仇以及官司的输赢并不重要，重要 的是它丌启了一个注定影响深远的时代p 2 p 时代。 p 2 p 发展到今天，出现了很多优秀的应用软件。如国内风靡的文件下载软件 b i t c o m m e t 、e d o n k e v 等，有用于在线播放网络电视的p p l i v e 等，还有专业用于 语音通讯的软件s k y p e 。国外著名的p 2 p 软件还有l i m e w i a r 和b e a r s h a r e 等。 美国联邦通讯委员会主席、前困务卿鲍威尔之子米高鲍威尔对使用s k y p e 的软 件有这样的感受：“当我下载s k y p e 后，我便知道又一个时代过去了。当语音可 以如此清晰地通过免费软件束传送，世界无可避免要再次改变。” 2 2p 2 p 定义及特点 p 2 p 是p e e r t op e e r 的缩写，p e e r 在英语罩有“地位、能力同等者”、“同事” 和“伙伴”等意义。p 2 p 就是“伙伴对伙伴”的意思，技术上称为对等联网【3 】。 也有人认为p 2 p 中的p 是人( p e o p l e ) 的意思，事实卜，我们所处的真实生活是就 是p 2 p 的环境，人们可以和其他人直接地交流。计算机技术将我们带到了虚拟的 网络空 - 】，在网络空问我们也希望能够按照p 2 p 的方式进行交流沟通。当油网络 ， ，o q 等p 2 p 通讯软件的流行就反映r 这种网络技术的需求，所以p 2 p 在加强网络 6 郑卅1 人学顺l j 学位论文 上人与人之问的交流、文件交换、分布计算、协同工作等方面是大有前途。 通俗地讲，p 2 p 模式是直接将人们联系起来，让人们通过互联网直接交流， 真征地消除中间环节。p 2 p 可以使用户直接连接到其它的计算机上交换文件，而 不像过去那样连接到服务器去浏览和下载。p 2 p 的重要特点就是改变互联网现在 的以大网站为中心的状态，重返“非中心化”，并把网络的权力交还给用，- 。举 一个例子来说明对等交流：当某用户在寻找一个文件时，利用各大网站搜索引擎 得不到结果时，网络另一端的用户说“我有，从我的硬盘下载吧”，这就是p 2 p 方 式的交流。而p 2 p 技术的特征之一就是弱化了服务器的作用，甚至取消服务器， 任意两台p c 互为服务器，互为客户机，完全是对等的关系。 p 2 p 的目标就是人们通过p 2 p 可以共享网络上所有的文件资源、硬盘资源、 c p u 资源乃至单个计算机上所有可以共享的资源。每个人都能共享他们认为最有 价值的东西，这将使互联网的价值得到极大的提升。 技术发展到今天，p 2 p 应用系统所共享的资源的范围从文件到硬盘，从硬盘 到c p u ，共享资源的概念不断进行新的扩展，不过这种新的扩展是基于原有共 享思想新的应用形式而已。 很多研究团体都给出过p 2 p 的定义，在此，我们给出p 2 p 的一个具体定义： 所谓p 2 p ，就是消费者和生产者之间为达到一定目的而在计算机网络上进行的直 接的、双向的信息或服务的交换。在这罩p 2 p 即是英文p e e r t op e e r 的简称，其 中p e e r 是“同等的人、伙伴”的意思。p 2 p 的实质即代表了信息和服务在一个网络 对等设备与另一个网络对等设备问的流动。 p 2 p 系统具有如下一些特点： ( 1 ) 大规模( 1 a r g c s c a l e ) ：为了实现资源共享，p 2 p 系统中往往会有大量 的节点。 ( 2 ) 动态性( d v n a m i c ) ：在p 2 p 系统中，节点通常是自主的，因而节点可 能会频繁的加入或离开p 2 p 网络。p 2 p 网络处在不停的变化中，它的变化比 i n t e r n e t 要剧烈的多。 ( 3 ) 节点的异构性( n o d eh e t e r o g e n e i t y ) ：加入到p 2 p 网络中的节点不仅在 物理特孤f ：( 延迟，带宽，性能等) ，而目在行为上( 共享文件数量，在线时问 等) 部j j 有非常大的差异。 7 郑州人学坝：l 学位论殳 考虑到p 2 p 系统的特点，p 2 p 系统需要解决的主要问题应该有： ( 1 ) 扩展性：p 2 p 系统应该能较好的适应系统规模( 节点数量) 的增长。 ( 2 ) 高效性：p 2 p 系统应该能在大规模情况下仍然保持网络服务的性能。 ( 3 ) 可靠性：在p 2 p 网络频繁变化的情况下，系统应该始终具有可用性。 ( 4 ) 匿名性：由于p 2 p 系统实现了各个节点之问的资源共享，保护各个 节点的隐私成为一个重要的问题。 在本文中，我们主要针对如何提高p 2 p 系统的扩展性作了一些工作。 2 3p 2 p 文件共享系统分类 p 2 p 文件共享系统是当前i i l t e m e t 网络上主要的p 2 p 应用形式。根据p 2 p 文件 共享系统网络拓扑结构的不同，p 2 p 系统主要可以分为以下三类： 2 3 1 非结构化系统 这种系统所形成的网络是随机的，即网络中节点之间的连接是随机的、任 意的，网络中共享资源的存储位最和整个网络的拓扑结构之间没有任何关系。非 结构化p 2 p 系统发展至今可以划分为三个阶段： 第一个阶段就是以n a p s t e r 为代表的集中目录式系统：通过一个中央服务 器保存所有p 2 p 用户上传的音乐文件索引信息和文件存放具体位嚣的信息：当某 个用户需要某首曲目时，首先连接到n a p s t e 胡艮务器，在服务器进行检索，并由服 务器返回存有该文件的用户信息：再由请求者直接连到文件所有者来传输文件。 这种方式最大的隐患在中央服务器上，如果该服务器失效，整个系统都会瘫痪。 另一个问题在于安全性上，n a p s l e r 并没有提供有效的安全机制。 笫：二个阶段是以g n u t e l l a f 5 1 为代表的纯分布式系统，它和n a p s t e r 最大的区别 就是没有用来保存用户共享文件索引信息的中央服务器。所有文件存放的信息分 布在网络中各个节点上，查询文件时通过在网络中有限的洪泛方式来进行，然后 和棚有文件的节点连接进行文件的传输。这种方式虽然i ， - 以有效地找到文件的信 息，f i _ i 却会在网络中产生大量的冗余流量。 第：个阶段是以k a z z a l 6 】、g n u t e l l a 2 1 7 为代表的混合式系统，它结合了前刺， 8 郑州人学坝i j 学位论义 p 2 p 系统的优点，并引入了超级节点和叶子节点的概念。网络中叶子节点在超级 节点上翳记并在超级节点上建立路由表。超级节点是从网络中一些带宽和处理能 力高的节点中动态选择出来的。在网络中进行查询时，消息转发只局限在超级节 点之间，叶子节点只能把查询提交到自己所属的超级节点上，超级节点在本地处 理查询，然后把消息转发到相关叶子节点上或者直接转发给相邻超级节点上。这 种方式可以缩短网络查询时间，但是也引入了定的网络开销。从网络整体结构 上看，如果把超级节点和其叶子节点看作一个整体，那么由这个整体所构成的网 络仍然是一个纯分布式的非结构化p 2 p 网络，因此，对于这类系统改进的着眼点 依旧要放在纯分布式非结构化p 2 p 系统的改进上。 这三个阶段对应的p 2 p 系统模型如图2 1 所示。 s e n ，e f s u p e f p e e r 集中日录武的p 2 p 系统纯分布a 的p 2 p 系统混合| l = i = 的p 2 p 系统 2 3 2 结构化系统 图2 1 非结构化p 2 p 系统的种模型 和一i f 结构化p 2 p 系统相比，结构化p 2 p 系统的拓扑结构以及共享文件在网络 中的存储位置都能够得到有效控制。结构化p 2 p 模式是种采用纯分布式的消息 传递机制和根据关键字进行查找的定位服务，目前的主流方法是采用分布式哈希 表( d h t ) 技术，这也是目前扩展性最好的p 2 p 路由方式之一。由于d h 丁各节点并 不需要维护整个网络的信息，只在节点中存储其临近的后继节点信息，因此较少 的路【f 吉息就可以有效地实现到达目标肖点，同时又取消了洪泛算法。该模型有 效地t 少r 1 竹点信息的发送数量，人量的研究表明1 8 ”l ：这种结卡勾化p 2 p 系统 9 郑州人学顺i 学位论文 具有良好的扩展性。同时，出于冗余度以及延时的考虑，大部分d h t 总是在节点 的虚拟标识与关键字最接近的节点上复制备份冗余信息，这样也避免了单一节点 失效问题。然而由于p 2 p 网络中节点的不确定性，进出网络比较频繁，所以构造 大规模的结构化p 2 p 系统很难。 目前基于d h t 的代表性的研究项目主要包括加州大学伯克利分校的 c a n 项目和t a p e s t r y 【1 0 】项目，麻省理工学院的c h o r d 项目，以及微软研究院 的p a s t r y 【”】项目等。这些系统一般都假定节点具有相同的能力，这对于规模较小 的系统较为有效。但这种假设并不适合大规模的i n t e m e t 部署。同时基于d h t 的 拓扑维护和修复算法也比g n u t e l i a 模型和k a z a a 模型等非结构化的系统要复杂得 多，甚至在c h o r d 项目中产生了“绕路”问题。事实上，目前大量实际应用还大 都是基于非结构化p 2 p 网络拓扑和洪泛广播机制，现在大多采用d h t 方式的p 2 p 系统缺乏在i i i t e m e l 中大规模真实部署的实例，成功应用还比较少见。 2 3 3 松散结构系统 这种系统的网络结构介于非结构化网络结构和结构化网络结构之间。文件 的定位有一些索引信息能够进行提示，但是这些索引信息并没有规范，因此搜索 的效果并不理想。f r e e n e t 就是这种类型网络的典型代表。【“1 2 3 4 小结 除了本文中提到的按网络拓扑结构分类的方法之外，p 2 p 文件共享系统还可 以按照网络集中程度、网络应用类型进行分类。山于本文探讨的内容主要是非结 构化p 2 p 系统，所以笔者就不在此一一赘述了。 2 4p 2 p 关键技术及主要应用 p 2 p 应用是目前基于互联网环境技术应用的热点，它和基于传统客户机服 务器模式的应用相比具有以下优势： p 2 p 是动态的：网络中的节点动态地提供资源的，e 享和相应的服务。 郑州大学钡i 学位论文 p 2 p 是双向的：网络中建立连接的节点能够切实实现信息和服务的交换与共 享。 p 2 p 是直接的：网络中提供的服务无任何中介、等级和格式的限制，直接交 换信息和服务。 p 2 p 是平等的：生产者与消费者地位平等，角色合二为一，最大限度利用了 网络中传统意义上位于边缘地位的节点，使得网络服务最大化。 p 2 p 是及时的：无服务器参与空间分配，可提供实时的、可升级的信息。 p 2 p 是有效的：可充分利用个人计算机的硬件设备，传输信息和服务时目标 确定。 p 2 p 是廉价的：和网络提供的传统服务相比，并不需要配置昂贵的服务器组 件，但是整个网络所提供的服务能力丝毫不逊于任何网络系统。 p 2 p 是健壮的：由于网络中不存在服务器，所以不存在传统网络服务中单点 失效的问题。 2 4 1p 2 p 关键技术 p 2 p 是一种基于互联网环境的新的应用型技术，它的关键技术包括： ( 1 ) 资源定位和拓扑一致性。p 2 p 资源共享的前提就是资源的有效查找。 目前的研究主要针对非结构化p 2 p 系统。由于没有整个网络的拓扑信息，资源的 存储位置也不知道，所以目前在非结构化p 2 p 系统中主要采用洪泛式的搜索方法 和有指导性的搜索方法。p 2 p 系统需要解决的另一个重要问题是：在一个缺少集 中化服务器的动念环境下，各个节点能够维持一致的网络拓扑信息。由于p 2 p 网 络中节点的加入和离开非常频繁，传统路由扩散的方法难以解决这一问题，所以 需要一个高效的一致性信息维护机制实现一些功能。例如，当网络拓扑变化时如 何快速恢复网络的稳定性等。 ( 2 ) 内容存储。p 2 p 系统使用户间可以彼此共享资源。为了提高这种访问 成功率，即提高资源的可获得性，很多p 2 p 系统都采取了复制和缓存技术。复制 足将文件复制保存在离请求发起用户距离较近的用j 、节点中；缓存一般是把有关 的历史查l i | 信息存储在节点上，为以后的查询提供参考信息。 ( 3 ) 互操作性。数据描述和交换的协议。在应f j 层而上，如果睡个对等体 郑州人学颂卜学位论殳 分别代表两家不同的公司，而且它们已经通过互联网建立连接，那么一方的信息 就必须为另外一方所识别，所以当前互联网上关于数据描述和交换的协议，如 x m l ，s o a p ，u d d i 等都是一个完善的p 2 p 软件所要考虑的。 ( 4 ) 防火墙和网络地址转换( n a t ) 的穿越。在实际的网络通信中，对等 体节点往往是个私有网络中的节点，位于防火墙之后。这样，对等体与对等体 之间直接通信需要解决的一个关键问题是穿越防火墙和n a t 。由于防火墙会对l p 地址进行过滤，限制了墙内外的连接，而n a t 技术虽然可以使得内部网络地址映 射到外部网络地址，但要求内部网络首先发起对外连接，否则外部网络机器无法 达到内部网络。 ( 5 ) 网络安全。由于在p 2 p 网络中节点的硬盘需要被其他节点访问，节点 用户安全意识的缺乏以及p 2 p 协议和p c 操作系统的安全漏洞使得节点很容易受 到黑客攻击。节点受到攻击会造成两种后果：一是用户个人信息被剽窃，文件被 病毒感染，其他从该节点下载文件的用户也会被感染； 二是用户站点被黑客控 制成为分布式拒绝服务的发起者。在商业中，使用这种结构共享关键数据可能导 致严重的安全问题，p 2 p 中的安全问题直接决定了p 2 p 能否被大规模进行商用， 现在大多数系统并没有对p 2 p 中的安全问题做太多的工作。p 2 p 中的安全问题 包括信息的加密、用户身份的认证、恶意节点的识别和应对等。 ( 6 ) 网络服务质量( q o s ) 问题。p 2 p 网络的o o s 问题包括两个方面：( 1 ) 信息获得的q o s 问题，用户需要的信息在多个节点同时存放，如何选择一个处理 能力强、负载轻、带宽高的节点需要用户考虑。 ( 2 ) 用户共享出无用或者违法 信息，造成信息垃圾充斥网络，因此，网络应该控制用户共享的信息，提高用户 获得有用信息的效率。 除了技术之外还有其他些关键问题，如p 2 p 网络标准、资源共享版权、现 有网络带宽等问题。 2 4 2p 2 p 主要应用 典型的p 2 p 计算应用系统的同标丰要有以下几类”1 ： ( 1 ) 资源、信息，服务的共享与管理 作为蚓络系统，“共享”永远是最基本的目标，包括文件、c p u 、存储空 l2 郑州人学坝i 学位论文 间等，以文件共享最为常见。文件共享有两种基本方式：基于目录服务的文件共 享和对等式文件麸享。前者典型的例子为n a p s t e r ，后者的典型例子是g n u l e l l a 、 f r e e n e t 。以c p u 共享为目标的p 2 p 系统也不少，如s e t i h o m e 。大致的实现方式 是：网络中的成员认为自身c p u 足够空闲的情况下，与系统成员联系，下载计算 任务的代码在自身运行，计算结果返回给该成员。以存储空间为共享资源的系统 有o c e a i l s t o f c ，它是以1 a p e s 仃y 为路由和查找基础设施的p 2 p 平台，是一个适合于 全球数据存储的p 2 p 应用系统。加密的文件被分解成为互相重叠的片断存储在全 球各地。即使一些本地的节点损坏，也可以通过一组片断恢复原始的文件。 ( 2 ) 协作计算 p 2 p 协作计算系统中的协作分为两个层次：底层为应用程序之间的协作，高 层为用户行为的协作。对于特定应用：共享c p u 时钟既可实现应用程序之间的协 作；但高层用户行为之间的协作一般需借助即时通信来实现。比如时下风行的 q q 和p o p o 等。以协作为目标的p 2 p 计算系统对传统的群件是一个挑战，就应用 范围来说，前者足以覆盖后者的功能。除即时通信外，协作型对等计算系统也适 用于工业系统中，用于控制生产流水线之问的协调与决策过程，如o c u l u st e c h 、 2 4 “n k 、e n g e n i a 、i 尉m b o 等。 ( 3 ) 构建充当基层架构的互联系统 实现这一日标下的计算系统以共享和协作为基础，不少公司已推出了一些 试验性的产品。例如，用于连接不同技术平台或者把分布的设备连接成一个整体 的c y t y q s 和p r o k s j m ；通过可复用组件编程的0 p e n d e s i g n ：能在不可信的网络上 安全地传输数据的w a r e o n e a n h s ；为下一代因特网计算模型提供基层架构的 x d e g e e s 等。 从技术角度看，p 2 p 计算并未激发出任何重大的创新，而更多的是改变了人 们对冈特网的理解与认识。f 是由于这个原因，i b m 宣称p 2 p 不是一个技术概念， 而是个社会和经济现象。可以说，p 2 p 的出现与第一个浏览器m o s a i c 的产生很 类似，| i ：司样的原因，使得p 2 p 在产业界受到注视的程度远远高于学术界。从未来 看，p 2 p 很可能成为目前基于c s 模式的w e b 取代者。 l3 郑州人学顺l j 学位论殳 第三章非结构化p 2 p 系统搜索优化技术 p 2 p 系统实现共享资源的前提是发现资源。而是否具有一个高效的资源搜索 机制是检验非结构化p 2 p 系统扩展性的关键因素之一。g n u t e l l a 是非结构化p 2 p 系统的典型代表，本章首先概述了原始的g n u t e l l a 协议以及g n u t e l l a 现状，之后 介绍了当前已经应用于非结构化p 2 p 系统的和平处于研究阶段的搜索优化技术。 3 1g n u t e i l a 发展 g n u t e l l a 是非结构化p 2 p 文件共享系统的一个典型实例，同时g n u t e l l a 协议 也是非结构化p 2 p 网络的一个基础协议。目前很多流行的p 2 p 文件共享系统如 l i m e w i r e 【1 6 1 、b e a r s h a r c 和m o r d b e u s 就是使用基于g n u t e l l a 文件共享协议 为用户提供网络共享服务的。因此对g n u t e l l a 的研究可以说是研究非结构化p 2 p 系统的基石。 g n u t e l l a 是一个纯分布式p 2 p 文件共享系统，其网络中节点地位平等，当节 点发出查询请求或是连接请求时就相当于一个客户机去获耿网络服务，当节点响 应查询或是提供文件传输时就相当于一个服务器来提供网络服务。g n u t e l l a 网络 是构建在底层因特网之上的，节点连接和资源查询工作在p 2 p 网络层上，而资源 的传输则是利用底层网络协议完成的。g n u t e l l a 网络模型如图3 1 所示。 图3 1g n u t e j l a 恻络的模掣圈 3 1 1 原始g n u t e l l a 协议 g n u t e l l a 网络 底层冈特网 g n u t e l l a 竹点，术语s e r v e n t ，存g n u t e l l a 网络中能够e 享文件并搜索文件资源 郑州人学倾i ：学位论文 既可以做为客户机又可以做为服务器。每个节点都和一小部分网络节点相连，成 千上万个这样的节点就构成了g n u t e l l a 网络。下面简要概述一下g n u t e l l a 协议中转 发消息的