（计算机应用技术专业论文）基于p2p的分布式搜索技术研究与实现.pdf

摘要 基于p 2 p 的分布式搜索技术研究与实现 作者简介：张颖卓，男，1 9 8 3 年8 月生，师从成都理工大学罗省贤教授，2 0 0 8 年6 月毕业于成都理工大学计算机应用技术专业，获得工学硕士学位。 摘要 随着p 2 p 网络的飞速发展，p 2 p 技术已经逐渐成为当今i t 技术领域研究与应用 的热点。p 2 p 网络的资源具有极大的分散性，资源分布在许多节点上；p 2 p 网络中的 节点可以自由地加入或退出，使p 2 p 网络的资源处于不断的动态变化之中，这些都增 加了p 2 p 搜索技术的难度。研究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 网络拓扑结构的影响，传统的全分布式非结构化 网络在搜索过程中会产生大量的消息冗余，给网络造成很大的压力，制约了搜索效 率。为了解决p 2 p 网络中的搜索问题，文本根据小世界现象的启示，对现有的分布 式结构化c h o r d 网络拓扑结构进行了改进，提出了一种分和式双环结构的网络拓扑 结构，增加了内环网中的超级节点，并在此基础上对c h o r d 搜索算法进行了扩展， 设计了种基于d h t 技术的，按照目标资源流行性热门度进行网络路由的n c h o r d 搜索算法。该算法根据小世界现象规律，对系统中的流行性热门数据进行归纳提取， 把存储有这些资源且经常在线的节点作为内环网中的超级节点，并为超级节点构造 详细的路由索引表。节点在执行查询时，首先查询路由索引表，由于这部分热门数 据承担了系统中绝大部分查询要求，所以大部分查询都在很少的几个逻辑跳数内完 成了查询。实验表明，n c h o r d 算法在搜索过程中显著地减少了路由跳数、降低系统 开销。 最后，本文在以上研究内容的基础上，设计和实现了文件搜索系统，该系统提 供了网络节点管理、流行性热门资源分类、文件共享、文件搜索和下载等功能。 关键词：p 2 p ，分布式搜索，d h t ，小世界现象，n c h o r d 成都理1 人学硕+ 学位论文 r e s e a r c ho fd i s t r i b u t e ds e a r c h1 e c h n o l o g yb a s e do np 2 p i n t m d u c t i o no f t h ea u t h o r ：z h a n gy i n g z h u o ，m a l e w a sb o mi na u g u e s t ，1 9 8 3w h o s e t u t o rw a sp r o f e s s o rl u os h e n g x i a n h eg r a d u a t e df r o mc h e n g d uu n i v e r s i t yo f 1 e c l m o l o g yi nc o m p u t e ra p p l i c a t i o n1 、c c l m 0 1 0 9 ym a j o ra n dw a sg r a n t e dt h em a s t e r d e g r e ei nj u n e ，2 0 0 8 a b s t r a c t a st h ef a s td e v e l o p m e n to fp 2 p 、v c b ，p 2 pt e c h n o l o g yh a sb e c o m et h eh o ts p o to f 叫a y si 丁t e c h n o l o g yr e s e a r c ha n da p p l i c a t i o n t h er e s o u r c eo fp 2 p w e b i sd e c e n t r a l i z e d ， w h i c hs p r e a d si nm a l l yn o d e s t h en o d e si np 2 p 、v e bc a ne n t e ra n de x i tm o r ef r e e l y ， w h i c hm a k e sm er e s o u r c eo fp 2 pw e bs t a y si nac h a n g i n gm o b i l es t a t u s a na b o v e i n c r e a s e dm ed i m c u l t yo fp 2 ps e a r c h i n gt e c h n o l o g y r e s e a r c h i n gt h es e a r c h i n g t e c h n o l o g yo fp 2 pw e b c a nn o to n l ys o l v et h es e a r c h i n gp r o b l e mi np 2 pw e b ，b u ts o l v e t h cp r o b l e mo f d i s t r i b u t e ds t o r ea i l dc a i c u l a t i o n n l e r e f o r ei ti sm e a n i n g f u l t or c s e a r c ht h e s e a r c h i n gt e c h n o l o g yo fp 2 pw e b t h i sp a p e r6 r s t l yi n d u c e dt h ec h a r a c t e r i s t i co fp 2 p ，c o m p a r e dp 2 pm o d ea n dc s m o d e ，l h e nr e s e a r c h e df o u rs t r u c t u r e so fp 2 pn e tt o p o l o g y o nt h eb a s i so fr e s e a r c h i n g m a i nc a l c u l a t i n gm e t h o do fp 2 p ，t h ed i s t r i b u t e ds e a r c hc a l c u l a t i n gm e m o do fp 2 p 、v a s f o c u s e di n t h ee s s e n c ea 1 1 df u n c t i o no fp 2 ps e a r c h i n gc a l c u l a t i n gm e t h o di si n n u e n c e db yp 2 p n e tt o p o i o g y 1 、h et i a d i l i o n a ld e c e n t r a l i z e du n s t r u c t u r e d t 叩o l o g yp r o d u c e s a l a r g e q u a n t i t yo fu s e l e s se x t mi n f 0 蛐a t i o nd u r i n gs e a r c h i n gp r o c e s s ，w h i c hg i v e st h ew e b m u c hp r e s s u r ea n dr e s t r i c t st h ee 塌c i e n c yo fs e a r c h i n g t os o l v et h ep m b l e m so fp 2 p s e a r c h i n g ，t h i sp a p e rc o m b i n e dw i t ht h es m a l lw o r l dp r o p e r t y ，i m p r o v e dt h et m d i t i o n a l d c c e n t r a l i z e ds t n l c t u r e dt o p o l o g ya n dp r o v i d e dan c tt o p o l o g yo fd o u b l e “n gs t m c t u r e o nt h eb a s i so ft 王l i s ，a ne x t e n s i o no fd h tt e c h n o l o g yo fc h o r ds e a r c h i n gc a l c u l a t i n g m e t h o dw a sg i v e n a l s o ，ac a l c u l a t i n gn c h o r dm e t h o do fn e tr o u t i n gw h i c bb a s e do nt h e p o p u l a rh o ta i mr e t o u r c ew a sg i v e n t h i sc a l c u l a t i n gm e t h o di sb a s e do ns m a l lw o f l d p r o p e n y ，a n a l y z e st h ep o p u l a rd a t ai nt h es y s t e m ，u s e st h en o d et 1 1 a ts t o r e dt h e s er e s o u r c e a n du s u a l l yo n l i n ea st h es u p e rn o d ei ni n s i d er i n g ，a n dc o n s t m c td e t a i l e dr o u t i n gi n d e x t a b l ef o rs u p e rn o d e d u r i n gt h ep r o c e s so fn o d es e a r c h i n g ，f j r s t l yt oc h e c kt h er o u t i n g i n d e xt a b l e b e c a u s et h o s ep a n so fh o td a t ah a v em o s to ft i l ec h e c k i n gr e q u i r e m e n t si n i i 一 垒! 墨! ! 壁 t h es y s t e m ，m o s to ft h ec h e c k i n gf j n i s h e s 谢t h i naf e wn u m b e r so fh o p t h ee x p e 而i l e n t s h o w e dt h a tn c h o r dc a l c u l a t i n gm e t h o dc a nd e c r e a s et h ej u m p i n gn u m b e r s d u “n gt h e p r o c e s so fs e a r c h i n ga n dd e c r e a s et h ec o s to fs y s t e m o nt h eb a s i so ft h i s ，a ne x t e n s i o no fc h o r ds e a r c h i n gc a l c u l a t i n gm e t h o dw a sg i v e n a l s o ，ac a 】c u l “n gm e t h o do fu s i n gp o p u l a rh o td e g r e eo 九a r g e tr e s o u r c et on e tr o u t i n g w a sg i v e n t h ee x p e r i m e n ts h o w c dt h a tn c h o r dc a l c u l a t i n gm e t h o dc a n 印p r a r e n t l y d e c r e a s et h ej u m p i n gn u m b e r sd u r i n gt h ep r o c e s so fs e a r c h i n g i nt h ee n d ，t h ea u t h o r u s e dn c h o r ds e a r c h i n gc a i c u i a t i r 增m e t h o dt od e v e i o pas y s t e mo f d o c u m e n t s e a r c h j n g k q n v o r d s ：p 2 p ，d i s t r i b u l e ds e a r c h ，d h t ，s m a l j w o r l dp r o p e r t y ，n c h o r d i j j 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得盛壑理王太堂或其他教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示谢意。 学位论文作者签名：召弋氧卓 力蹰年 口舌月 j 日 学位论文版权使用授权书 本学位论文作者完全了解盛叠堡王去堂有关保留、使用学位论文的规定，有 权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权盛壑理王太堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：我氯牟 学位论文作者导师签名： 了省贸 洳口留年 d 6只 l 日 第l 章绪论 1 1 引言 第l 章绪论 2 0 世纪9 0 年代以来，以i n t e m e t 为代表的信息技术的迅猛发展使人类社会大步 迈入了网络时代。p 2 p 是p e e r - t o - p e e r 的缩写，意为对等网络。近几年来，计算机对等 网技术的迅猛发展引起了人们的注意。引发p 2 p 革命的当推美国的n a p s t e r 【”，2 0 0 0 年7 月份的一场官司将n a p s t e r 的声望推到顶点，用户数也在短短一年内激增至4 0 0 0 万，成为互联网史上一大奇迹。 p 2 p 所包含的技术就是使互联网上的电脑能够进行数据交换，但数据是存储在每 台电脑里，而不是存储在既昂贵又容易受到攻击的服务器里。网络成员可以在网络数 据库罩自由搜索、更新、回答和传送数据。所有人都共享了他们认为最有价值的东西， 这将使互联网上信息的价值得到极大的提升。 在p 2 p 网络中，不存在中心服务器，所有的节点既是客户机，既享用其他节点提 供的服务，同时又充当服务器，为其他节点提供服务。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 2 论文选题及其研究意义 p 2 p 并非一种新技术，而是原有技术新的应用模式，但在互联网迅速普及的条件 下，p 2 p 的应用显现出了前所未有的威力。对等系统在2 0 0 0 年开始流行，并不断有 成都理j ：大学硕士学位论文 崭新的发展。英特尔公司的首席技术官p a t r i c kg e l s i n g e r 认为，对等系统对互联网的 重要性将可以和浏览器相匹敌。 月前，p 2 p 应用最重要的领域是即时通信和文件共享。我们所熟知的q q 、p p l 1 v e 、m s nm e s s e n g e r 、b t 下载、迅雷下载，都是p 2 p 技术的具体应用。人们 意识到，对等系统不仅可以让成千上万的人共享信息资源和即时沟通，而目还可以 有许多其他重要的应用：分布式计算、数据共享、共享带宽、智能代理等。如今， 越来越多的人开始认真地思考如何利用p 2 p 的应用来提高工作效率或者改善自己的 生活。 p 2 p 模式的变化经历了集中式、分布式和混合式三个阶段口l 。从学术意义上讲， p 2 p 网络的资源存在形式决定了p 2 p 的搜索技术和现有的搜索技术有很大的不同。p 2 p 网络的资源具有极大的分散性，资源分布在许多节点上：p 2 p 网络中的节点可以自由 地加入或退出，使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 搜索技术研究现状 由于p 2 p 蕴含着巨大的技术潜力和商业价值，许多学术机构、大公司先后投入到 对p 2 p 技术的研究之中。要想充分地利用p 2 p 网络上的资源，首先要有效地发现需要 的资源，即在p 2 p 网络中进行搜索。目前p 2 p 研究的一个主要问题就是搜索问题i l ”。 p 2 p 搜索问题现在主要从两方面来研究：一是从p 2 p 网络的拓扑体系结构入手， 二是对搜索采用的算法进行研究，目的都是为了快速而准确地发现节点上的资源。 根据祸合度，目前国内外的p 2 p 网络的拓扑体系结构主要分为两大类：非结构化 拓扑与结构化拓扑。而根据分散度，又可以划分为：集中式拓扑、全分布式非结构化 拓扑、全分布式结构化拓扑、半分布式拓扑四类。 集中式拓扑结构以n a p s t e r 为代表，它实质上并非是纯粹的p 2 p 系统，而是通过 一个中央索引服务器来进行管理，容易出现网络瓶颈和单点失效。 全分布式非结构化拓扑模型，典型的代表是g n u t e l la 【3 】，该结构中不存在集中式 的目录服务器，并且文件的发布和网络拓扑松散相关。资源的搜索信息分布到各个节 点上，较多采用泛洪算法，浪费网络带宽，易造成网络拥塞，而且查询的范围不易控 制，可扩展性较差。 第】章绪论 全分布式结构化拓扑模型采用分布式哈希表( 例s t r i b u t e dh a s ht a b l e ，简称d h t ) 结构，使用分布式哈希表索引对资源和节点进行搜索。代表有c h o r d 、t 印e s t r y 、c a n 和p a s t r v 。d h t 类结构最大的问题是d h t 的维护机制较为复杂，尤其是结点频繁加 入退出造成的网络波动会增加d h t 的维护代价。 半分布式拓扑结构吸取了中心化结构和全分布式非结构化拓扑的优点，选择性能 较高( 处理、存储、带宽等方面性能) 的节点作为超级节点，k a z a a 【4 1 是该网络模型的 典型代表，但是陔模型对超级节点依赖性大，易于受到攻击，容错性也受到影响。 目前，p 2 p 搜索算法可分为集中式和分布式两类，而分布式搜索算法可再分为无 结构、有结构和半结构三种。集中式搜索方法中，所有p 2 p 节点都与己知地址的p 2 p 目录服务器相连，服务器负责对p 2 p 网络中的共享文件进行索引和查询，服务器集中 存放对等节点的地址信息和所保存数据的信息。当节点加入或离开该系统时，p 2 p 节 点服务器会随之更新系统索引表。分御式搜索方法的两个主要组成分支是无结构和有 结构方法，它们各有优劣。无结构算法在文件共享领域得到了成功应用，得到了千力i 用户认可。它的网络拓扑并不依据预先定义好的拓扑来构造严格结构的网络，因而无 法保证搜索性能，只能尽力而为。从另一角度看，无结构的网络拓扑也有一系列优势： 适应节点异构性，支持复杂形式的索引和搜索命令，以及适应节点频繁加入与离开。 结构化算法意味着文件的分布和网络拓扑紧密相关，文件并不是分布在随机的节点 上，而是按照确切的地址分布在网络中。在松散结构化p 2 p 网络中，每个节点都分配 有虚拟的逻辑地址，但整个系统仍然是松散的网络结构，文件的分布根据索引分配到 相近地址的节点上。 综上所述，国内外现有的p 2 p 搜索技术可分为以下四类：( 1 ) 集中式p 2 p 网络的搜 索技术；( 2 ) 结构化p 2 p 网络的搜索技术；( 3 ) 非结构化p 2 p 网络的搜索技术：( 4 ) 混合 式p 2 p 网络的搜索技术。这四种搜索技术各有特点，因此它们都应用在不同的领域中。 1 4 论文研究内容与创新点 本文对基于p 2 p 的分布式搜索算法进行了深入研究，在传统的c h o r d 算法基础上， 提出了一种改进的基于分布式散列表d h t ( d i s t 曲u t e dh a s ht a b l e ) 技术的分布式结 构化n c h o r d 搜索算法，并对该算法的性能进行了实验分析，最后应用浚算法实现了 一个文件搜索系统。 1 4 1 论文研究内容 本文主要研究的是基于p 2 p 的分布式搜索算法以及p 2 p 网络的各种拓扑结构。具 体研究内容如下： 1 ) 研究了p 2 p 的概念、特性以及具体应用，分析比较了p 2 p 与传统c s 网络模 型的优缺点： 成都理i ：人学硕士学位论文 2 ) 研究了p 2 p 的网络拓扑结构，包括集中式拓扑、全分布式非结构化拓扑、全 分布式结构化拓扑以及半分布式拓扑四种结构，比较了四种p 2 p 网络拓扑结构的综合 性能： 3 ) 研究了p 2 p 的搜索算法，分析这些算法的优缺点，重点研究了分布式p 2 p 网 络的搜索算法，包括以下几科算法： ( 1 ) 集中式的n a p s t e r 搜索算法； ( 2 ) 分布式结构化搜索算法，包括c h o r d 算法和c a n 算法； ( 3 ) 分布式非结构化搜索算法，包括泛洪算法、随机游走算法、本地索引算法 和移动a g e n t 算法； ( 4 ) 混合式搜索算法； 4 ) 深入研究了分布式结构化的c h o r d 网络模型及其算法，提出了一种基于c h o r d 网络模型的n c h o r d 双环改进网络结构模型； 5 ) 基于流行性热门度的n c h o r d 查询算法。针对传统的d h t 方法中的路由问题， 本文考虑p 2 p 网络中呈现的若干规律，结合小世界现象规律，提出了一种按照流行性 热门度进行网络路由的搜索算法。该算法对系统中的流行性热门数据进行归纳提取， 把存储有这些资源且经常在线的节点作为内环网中的超级节点，并为超级节点构造详 细的路由索引表。节点在执行查询时，首先查询路由索引表，由于这部分热门数据承 担了系统中绝大部分查询要求，所以大部分查询都在很少的几个逻辑跳数内完成了查 询； 6 ) 采用面向对象的方法，设计并实现了一个文件搜索系统。该系统由多个模块 组成，可以在网络中共享文件，并对文件进行搜索和下载。良好的模块设计使得系统 的可扩展性强，便于二次开发。 1 4 2 论文创新点 本文对基于p 2 p 的分布式搜索技术进行了深入研究，提出了一种改进的基于分布 式散列表( d h t ) 技术的分布式结构化n c h o r d 搜索算法，并应用该算法设计和实现 了一个文件搜索系统。具体技术如下： ( 1 ) 改进了c h o r d 网络拓扑结构，对影响搜索性能的网络拓扑因素进行了深入分 析，对传统的c h o r d 网络拓扑结构进行了改进，提出了一种双环结构的n c h o r d 网络 拓扑； ( 2 ) 针对n c h o r d 网络拓扑模型，结合c h o r d 搜索算法，提出了一种改进了的 n c h o r d 搜索算法。该算法利用网络中节点的历史在线率以及节点所共享资源的流行 性热门度进行路由搜索，可以快速的查找到目标资源。 第2 章p 2 p 概述 2 1p 2 p 的起源 第2 章p 2 p 概述 p 2 p 起源于最初的联网通讯模式，比如在同一座建筑物内通过局域网互联p c ，通 过m o d e m 远程拨号互联几座不同建筑物。其中建立在t c p i p 协议之上的通讯模式构 成了今日互联网的基础。从这个角度来说，p 2 p 作为一种计算模式，从上个世纪7 0 年代网络产生以来就已经存在了，只不过当时的网络带宽和传播速度限制了这种计算 模式的发展。9 0 年代未，随着高速互联网的普及、个人计算机计算能力和存储能力的 提升，p 2 p 技术重新登上历史舞台并且带来了一场技术上的革命，同时也给人们的生 活带来了极大的便利。 2 2p 2 p 的概念 p 2 p 是p e e r t o - p e e r 的缩写，p e e r 在英语罩有“同等者”、“同事”和“伙伴”等 意义1 6 l 。这样一一来，p 2 p 也就可以理解为“伙伴对伙伴”的意思，或称为对等联网。 目前人们认为p 2 p 对加强网络上人际交流、文件交换、分布式计算等方面大有前途。 p 2 p 的原意是一种通信模式，在这种通信模式中，每一部分具有相同的功能，任 意一个部分都可以开始一次通信。现在对p 2 p 概念进行了扩展，i b m 公司为p 2 p 作 了如下定义：p 2 p 系统由若干互联协作的计算机构成，且至少具有如下特征之一： 系统依存于边缘化( 非中央式服务器) 设备的主动协作，每个成员直接从其他成员而不 是从服务器的参与中受益；系统中成员同时扮演服务器与客户端的角色；系统应用的 用户能够意识到彼此的存在，构成一个虚拟或实际的群体。 简单地说，p 2 p 直接将人们联系起来，让人们通过互联网直接交互。p 2 p 使得网 络上的沟通变得更容易更直接，真正地消除了中间商。p 2 p 就是使一个用户可以直接 连接到其他用户的计算机交换文件，而不是像过去那样连接到服务器去浏览与下载。 p 2 p 另一个重要特点是改变互联网现在的以大网站为中心的状态、重返“非中心化”， 并把权力交还给用户。p 2 p 看起来似乎很新，但p 2 p 并不是什么新技术，在现实生活 中我们每天都按照p 2 p 模式面对面地或者通过电话交流和沟通p j 。 2 3p 2 p 的特- 性 与其它网络相比，p 2 p 具有以下特性哪： ( 1 ) 非中心性 成都理1 ：大学硕十学位论文 网络中的资源和服务分散在所有节点上，信息的传输和服务的实现都直接在节点 之间进行，l u 以无需中间环节和服务器的介入，避免了可能的瓶颈。 ( 2 ) 可扩展性 p 2 p 的分散化带来的一个直接的好处就是提升了系统的可扩展性。在p 2 p 网络中， 随着片j 户的加入，4 i 仅服务的需求增加了，系统整体的资源和服务能力也在同步地扩 充，始终能较容易地满足用户的需要。 ( 3 ) 匿名性 p 2 p 中一个很重要的特性就是匿名性。匿名性的一个重要日标就是让用户在使用 系统的时候不必受各种法律问题的约束，进一步的目标就是保证审查机构无法对数字 内容进行审查。 ( 4 ) 自组织性 在p 2 p 系统中，由于可扩展性、支持容错、资源不断地连接断开以及拥有的开销 等原因，使系统具有一定的自组织特性是必要的。 ( 5 ) 健壮性 p 2 p 架构天生具有耐攻击、高容错的优点。由于服务是分散在各个节点之间进行 的，部分节点或网络遭到破坏对其它部分的影响很小。而且p 2 p 模型般在部分节点 失效时能够自动调整整体拓扑，保持其它节点的连通性。 ( 6 ) 高性能性 性能优势是p 2 p 被广泛关注的个重要原因。采用p 2 p 架构可以有效地利用瓦联 网中散布的大量普通节点，将计算任务或存储资料分布到所有节点上。利用其中闲置 的计算能力或存储空间，达到高性能计算和海量存储的目的。 2 4p 2 p 模式与c s 模式的比较 目前较流行的计算模式之一是c s ( c l i e n t s e r v e r ，客户端朋日务器) 模式，c s 模 式下客户端之间要进行数掘交换必须经过服务器。c l i e n t 和s e r v e r 常常分别处在相距 较远的两台计算机上，c l i e n t 程序的任务是将用户的要求提交给s e r v e r 程序，再将 s e r v e r 程序返回的结果以特定的形式显示给用户；s e r v e r 程序的任务是接收客户程序 提出的服务请求，进行相应的处理，再将结果返回给客户程序。图2 一i 是一个典型的 c s 模式的体系结构。 c s 结构具有以下一些特点b 1 0 1 ： ( 1 ) 集中计算方式，信息和数据都保存在服务器端，只有服务器具有控制能力， 客户端基本上只是一个高性能的i o 设备。 ( 2 ) 服务器及网络的带宽决定了网络的性能，每台服务器所能提供的信息数量受 到自身存储空间的限制。 第2 章p 2 p 概述 ( 】c 】1 i 图2 一lc s 模式网络结构图 ( 3 ) u r l 用来表示信息资源的地址，但是u r l 很少能直接体现所定位信息的内 容，甚至不能直接连接到具体的内容上。 ( 4 ) 被发布信息的分布与生存期十分稳定。服务器只发柿机器所有者想公之于众 的信息，这些信息将会在该服务器上稳定的保存一段时间，并且该服务器也不间断地 运行在刚络上。 ( 5 ) 被发布信息的存储与管理比较集中，互联网上所有可以公开访问的信息基本 上都保存在服务器上，服务器根据适当的算法和规则管理本地信息，j 畦答客户端的访 问请求或进行计算。 p 2 p 模式是非中心结构，如图2 2 ，它与c s 模式有明显的差别，它具有以下一 些特点【5 j ： 图2 2p 2 p 模式网络结构 成都理i 人学硕士学位论文 ( 1 ) 每个对等点具有相同的地位，既可以请求服务也可以提供服务，同时扮演着 c s 模式中的服务器和客户端两个角色。 ( 2 ) p 2 p 技术可以使得非互联网的用户很容易的加入到系统中。 ( 3 ) p 2 p 模式的网络中，每一个对等体可以充分利用网络上其他对等体的信息资 源，如处理器周期、高速缓存和磁稀空间等。 ( 4 ) p 2 p 技术是基于内容寻址的方式，这里的内容不仅包括信息的内容，还包括 空闲机时、存储空间等。p 2 p 网络中，用户直接输入要索取的信息的内容，而不是信 息的地址。 ( 5 ) p 2 p 中的每一个对等体通常没有固定的i p 地址，且可常常从网络上断丌。 ( 6 ) 信息的存储及发布具有随意性，缺乏集中管理。 通过上面的比较，可以看出p 2 p 模式相对于c s 模式的一些主要优点【9 】： ( 1 ) p 2 p 模式最主要的优点就是资源的赢利用率。在p 2 p 网络上，闲散资源有机 会得到利用，所有节点的资源总和构成了整个网络的资源，整个网络可以被用作具有 海量存储能力和巨大计算处理能力的超级计算机。c s 模式下，即使客户端有大量的 闲散资源，如果没有得到服务器的响应，资源也无法被利用，资源利用率比较低下。 ( 2 ) 随着客户端节点的增加，c s 模式下服务器的负担越来越重，并逐渐形成系统 的瓶颈，旦服务器崩溃，整个网络也随之瘫痪。而在p 2 p 网络中，每个对等体都是 一个活动的参与者，网络中每个节点的地位都是对等的，每个节点既充当服务器，为 其它节点提供服务，同时也充当客户端，享用其它节点提供的服务。对等点越多，网 络性能越好，网络随着规模的增大而越趋稳固。 ( 3 ) p 2 p 基于内容的寻址方式处于一个更高的语义层次，因为用户在信息搜索时 只需指定具有实际意义的信息标识而不是物理地址。这将刨造一个更加精炼的信息仓 库和一个更加统一的信息标识方法。 ( 4 ) 信息在网络设备节点间直接流动，高速及时，降低中转服务成本。 p 2 p 也有不足。首先，p 2 p 不易管理，而对c ，s 网络，只需在中央服务器进行管 理。其次，p 2 p 网络中数据的安全性难以保障，因此在安全策略、备份策略等方面， p 2 p 的实现要复杂些。另外，对等点可以随意地加入或退出，会造成网络带宽和信 息存在的不稳定l “。表2 1 给出了p 2 p 与c s 性能的比较。 表2 1p 2 p 网络与c ，s 网络的性能比较 性能比较 p 2 pc i s 数据发布好差 数据接收 d 好 数据互动性好差 数据及时性好差 8 第2 章p 2 p 概述 表2 1p 2 p 网络与c s 网络的性能比较( 续表) 数据安全性差好 数据更新 好 著 数据质餐 d 好 数据覆盖率和数量差好 数据成本控制好差 数据管理方便性差好 可扩展性好差 2 5p 2 p 的应用 与传统的分布式系统相比，p 2 p 技术具有无可比拟的优势，因此p 2 p 技术具有广 阔的应用前景。目前p 2 p 的应用主要有以下几个方面0 ，】3 1 “】： ( 1 ) 对等计算 对等计算研究的是如何充分地把网络中多台计算机暂时不用的计算能力结合起 来，使用积累的能力执行超级计算机的任务。任何需要大量数据处理的行业都可从对 等计算中获利，如天气预报、动画制作、基因组的研究、安全加密等。就本质而言， 对等计算就是网络上c p u 资源的共享。 ( 2 ) 搜索引擎 基于p 2 p 的搜索引擎的出现，为互联网的信息搜索提供了全新的解决之道。与目 前使用的其他各类搜索引擎相比，p 2 p 最大优势在于应用先进的对等搜索理念，可不 通过给定的中央服务器，也可不受信息文档格式和宿主设备的限制，对互联网络进行 全方位的搜索。同时搜索深度也是传统搜索引擎所难以比拟的，其搜索范围可在短时 间内以几何级数迅速增长。 ( 3 ) 协同工作 通过采用p 2 p 技术，可以去掉目前协同工作系统中的中央服务器，参与协同工作 的计算机直接建立连接，个人和组织可以随时采用多种方式建立在线、非在线的协同 应用环境，使得人们在互联网上进行实时信息交流变得更方便和容易。 ( 4 ) 即时通信 所谓即时通信，其实就是指的诸如m s n 、腾迅q q 等被称为在线聊天的工具。 p 2 p 的即时通信软件不仅可以随时知晓对方在线与否，而且通信双方的交流完全是点 对点进行，不依赖服务器的性能和带宽。 ( 5 ) 文件共享和下载 传统的w e b 方式中，要实现文件交换需要w e b 服务器的大力参与，通过将文 件上传到某个特定的网站，用户再到浚网站搜索需要的文件，然后下载。这就要求 w e b 服务器能够对大量用户的访问提供有效的服务，成为w e b 应用的瓶颈之一。而 9 成都理= 人学硕士学位论文 p 2 p 技术可以使用户利用基于p 2 p 的网络协议，直接从含有所需文件的对等节点下载 该文件。应用实例有国外的n a p s t e r ，g n u t e l l a 和f r e e n e t ，国内的有北大天网m a z e 、 迅雷等。 ( 6 ) 流媒体技术 传统的分布式多媒体系统一股是基于c s 模式，服务器以单播的方式和每个用户 建立连接，由_ 】二流媒体服务具有高宽带、持续时间长等特点，随着用户数量的增加， 服务器的带宽很快被消耗完，所以以前的网络电视经常出现断断续续，需要不断的进 行数据缓冲。由于p 2 p 网络本身的可扩展性，基于p 2 p 方式的流媒体技术很好地解决 了传统流媒体带宽不足的问题。应用实例有：沸点、p p l i v e 、q q l i v e 、p p s t r e a m 、s o p c a s t 等。 1 0 第3 章p 2 p 网络拓扑结构研究 第3 章p 2 p 网络拓扑结构研究 拓扑结构是指分布式系统中各个计算单元之间的物理或逻辑的互联关系，节点之 间的拓扑结构一直是确定系统类型的重要依据。p 2 p 系统主要采用非集巾式的拓扑结 构，根据结构关系n 丁以将p 2 p 系统细分为叫种结构的拓扑形式：中心化拓扑网络、全 分布式非结构化拓扑网络、伞分布式结构化拓扑网络以及半分御式拓扑网络。 3 1 中心化拓扑网络 中心化拓扑网络最大的优点是维护简单，发现效率高。由于资源的发现依赖中心 化的目录系统，发现算法灵活、高效并能够实现复杂查询。最大的问题与传统c s 结 构类似，容易造成单点故障，访问的“热点”现象和法律等相关问题，这是第一代p 2 p 网络采用的结构模式，经典案例就是著名的m p 3 共享软件n a p s t e r 。 在n a p s t e r 模型中，一群高性能的中央服务器保存着网络中所有活动对等计算机 共享资源的目录信息。当需要查询某个文件时，对等机会向一台中央服务器发出文件 查询请求。中央服务器进行相应的检索和查询后，会返回符合查询要求的对等机地址 信息列表。查询发起对等机接收到应答后，会根据网络流量和延迟等信息进行选择和 合适的对等机建立连接，并丌始文件传输。n a p s t e r 的工作原理如图3 一l 所示。 图3 1n a p s t e r 网络的拓扑结构 采用n a p s t e r 结构的中心化拓扑网络结构也存在一些问题，主要表现为【6 】： ( 1 ) 中央服务器的瘫痪容易导致整个网络的崩馈，可靠性和安全性较低； ( 2 ) 随着网络规模的扩大，对中央索引服务器进行维护和更新的费用将急剧增加， 所需成本过高； 成都理1 1 人学硕士学位论文 ( 3 ) 中央服务器的存在引起共享资源在版权问题上的纠纷，并因此被攻击为非纯 粹意义上的p 2 p 网络模型。 综合上述优缺点，对小型网络而言，中心化网络模型在管理和控制方面占一定优 势。但鉴于其存在的种种缺陷，该模型并f i 适合大型的网络应用。 3 2 全分布式非结构化的p 2 p 网络 全分布式非结构化刚络采用了随机图的组织方式，结点度数服从p o w e r l a w i ”1 规 律，从而能够较快发现目的结点，而对网络的动态变化体现r 较好的容错能力，因此 具有较好的可用性，同时可以支持复杂查询，如带有规则表达式的多关键词查询，模 糊查询等，采用这种拓扑结构最典型的案例便是g n u t e l l a 【3 ，如图3 2 所示。 l 甥黔? j ”m 孥嚣节! ：妒蜉一蜕蠢晶 。淼嚣攀絮鬻明ib e i n e p ”i c h o “q 9b 鼋啼 ：焉蹴；薹蒜避暑篙”、州“f f m my o m p u t ert oo m e n ，一， 一“”“：彳m 一”nm m 、1 图3 2g n u t e l l a 网络的拓扑结构 g n u t e l l a 是一个p 2 p 文件共享系统，它和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 网络具有以下特点1 6 l ： ( 1 ) 不存在中央服务器，完全依赖于网络中的交互式个人成员而独立存在； ( 2 ) 在浚网络模型中，每一个联网计算机在功能上都是对等的，既是客户机同时 又是服务器，所以被称为对等机。 发现的准确性和可扩展性是非结构化网络面临的两个重要问题。目前对此类结构 的研究主要集中于改进发现算法和复制策略以提高发现的准确率和性能。 3 3 全分布式结构化的p 2 p 网络 在这类网络中，不存在中心化的目录服务器，冈此属于全分布式的p 2 p 网络。这 种类型的网络结构，采用分布式散列表【”】( d i s t r i b u t e d h a s h t a b l e ，简称d h t ) 的全 第3 章p 2 p 网络拓扑结构研究 分布式结构化拓扑网络。分布式散列表实际上是一个由广域范围大量结点共同维护的 巨大散列表。散列表被分割成不连续的块，每个结点被分配给一个属于自己的散列块， 并成为这个散列块的管理者。 d h t 结构能够自适应结点的动态加入与退出，有着良好的可扩展性、鲁棒性、结 点i d 分配的均匀性和自组织能力。最经典的案例是t 印e s t r y 、c h o r d 【”】、c a n 【2 q 和 p a s t r v 旧。 这里主要介绍一下具有代表性的c h o r d 网络模型【2 3 】，如图3 3 。该网络模型诞生 于美国的麻省理工学院，它的目标是提供适合于p 2 p 环境的分布式资源发现服务，它 通过使用d h t 技术使得发现指定对象只需要维护o ( 1 0 9 n ) 长度的路由表。在d h t 技 术中，网络节点按照一定的方式分配一个唯一节点标识符( n o d e ，i d ) ，资源对象通 过散列运算产生一个唯一的资源标识符( o b i e c t ，i d ) ，且浚资源将存储在节点i d 与 之相等或者相近的节点上。需要查找该资源时，采用同样的方法可定位到存储该资源 的结点。因此，c h o r d 的主要贡献