（计算机软件与理论专业论文）基于chord的p2p查询方法的研究.pdf

郑州大学硕士论文 摘要 对等网络( p e e rt op e e r ) 是一种用于信息共享的网络架构，在这种架构中， 各节点既是网络服务提供者一服务器，又是网络服务申请者一工作站，即每台计算 机都具有相同的功能，无主从之分。 由于p 2 p 具有大规模性、动态性、分布性等特点，在这种环境中如何有效的 查询资源就成了一个十分具有挑战性的问题。目前，流行的p 2 p 中主要采用的网 络结构大致可以分为三种：集中目录式的p 2 p 系统查询，例如，n a p s t e r ，e d o n k e y ， b i t t o r r e n t ，利用通过中央服务器保存所有的索引信息的方法共享信息资源：非 结构化p 2 p 系统的资源查询，例如，g n u t e l l a 和f r e e n e t ，采用的是一种f l o o d i n g 的查询方式；结构化p 2 p 系统的资源查询，像c h o r d ，c a n ，p a s t r y 和t a p e s t r y 使 用一个分布式哈希表( d h t ) 作为系统的基础数据结构。 本文研究的是采用环形拓扑结构的c h o r d 系统，该系统提供了一个可扩展的 查找协议来满足经常有节点加入、退出的动态p 2 p 系统，它通过使用相容哈希函 数把关键字存储在c h o r d 中的相应节点上。相容哈希函数能够通过使每个节点存 储数量大概相等的关键字来平衡负载，并且使得当节点加入或退出的时候关键字 的相对移动比较小。而且每个在c h o r d 中的节点仅仅需要知道其他少数节点的路 由消息，就可以完成信息查询的任务。 通过研究现有c h o r d 算法，发现在有些情况下，节点所维护的路由表中会产 生一些冗余的信息，这样的信息减慢了在大规模网络中的资源查询速度。因此本 文提出了一种改进的方案，简单的说，就是先按照原来算法建立好节点的路由信 息表，然后从中顺序扫描，找出这些冗余的路由信息，并删除这些信息，最后根 据c h o r d 路由的特点，从这种环形拓扑结构中找出等量的新的路由信息，加入到 路由表中，来改进这种不足。经过理论分析，这种方法保持了原有路由表的规模， 在进行资源查询的时候，加快了查询的速度。但是同样也带来了一些缺陷，即在 节点建立路由表时，需要找出冗余信息，并把它删除，然后找出新的信息来代替， 这就增加了时间的损耗。 关键词：p i p 、查询资源、c h o r d 、网络拓扑、分布式哈希 基于c h o r d 的p 2 p 查询方法的研究 a b s t r a c t t h ep e e r - t o - p e e rn e t w o r k ( p e e rt op e e r ) i so n ek i n do f t h en e t w o r kc o n s t r u c t i o n u s e si ni n f o r m a t i o ns h a r i n g ，i nt h i sk i n do f c o n s t r u c t i o n , v a r i o u sn o d e sn o to n l yi st h e n e t w o r ks e r v i c ep r o v i d e r s e l w e r ，a l s oi st h en e t w o r ks e r v i c ea p p l i c a n t w o r k s t a t i o n ，n a m e l ye a c hc o m p u t e ra l lh a st h es a m ef u n c t i o n ，n o ta d v o c a t e s 劬m i t d i v i s i o n s i n c ep 2 ph a v es o m ec h a r a c t e r i s t i c s ，l a r g e s c a l e ，d y n a m i cs t a t ea n dd i s t r i b u t e e t c ，t h e nh o wt os e a r c hr e s o u r c e se f f e c t i v e l yi nt h i sk i n do f e n v i r o n m e n ti sap r o b l e m t h a th a sac h a l l e n g e c u r r e n t l y , t h em o s tp o p u l a rn e t w o r ks t r u c t u r ea d o p t e di np 2 pc a n b ed i v i d e di n t ot h r e es t l a l c t u l _ ；e ：t h ep 2 ps y s t e mw i t hc o n c e n t r a t e dc a t a l o g u e ，f o r e x a m p l e ，n a p s t e r 、e d o n k e y 、b i t t o r r e n t , w h i c hk e e p i n gt h ei n d e xi n f o r m a t i o no nt h e c e n t r a ls e v e rt os h a r et h er e s o u r c e s ；t h ep 2 ps y s t e mw i t hn o n - s t r u c t u r ef o rr e s o u r c e s s e a r c h , f o re x a m p l eg n u t e i l aa n df r e e n e t , w h i c ht a k ef l o o d i n ga st h es e a r c hm e t h o d ： t h ep 2 ps y s t e mw i t hs t r u c t u r ef o rr e s o u r c e ss e a r c h , b e i n gl i k ec h o r d ，c a n ，t h ep a s t r y a n dt a p e s t r yw h i c hu s ead i s t r i b u t eb a s ht a b l e ( d h t ) a st h ef o u n d a t i o nd a t as t r a c t u r e o f t h es y s t e m t h es t u d yo f t h i st h e s i si st h ec h o r ds y s t e ma n di t st o p o l o g yl i k er i n g ，i tp r o v i d e ao p t i m i z er o u t ea r i t h m e t i cb yu s i n gc o n s i s t e dh a s h f u r t h e rm o r e ，t h ec h o r ds y s t e m p r o v i d ea l le x p a n s i v ep r o t o c o lt ot h ed y n a m i cs t a t ep 2 ps y s t e mw h i c hu s u a l l yh a v e n o d et oj o i no re x i t ，i ts t o r et h ek e yv a l u ei nt h ec o r r e s p o n dn o d eb yu s i n gc o n s i s t e d h a s h e a c hn o d ei nc h o r ds y s t e ms t o r es o m ek e y w o r d sw h i c hq u a l i t y l l ee q u a lt o b a l a n c eb yu s i n gc o n s i s t e dh a s h ，a n dw h e nt h en o d e j o i no re x i tt h es y s t e mi t sr e l a t i v e m i g r a t i o nc o u l db es m a l l m o r e o v e re a c hn o d ei nt h ec h o r dm e r e l yn e e d st ok n o w o t h e rm i n o r i t yr o u t ei n f o r m a t i o n , c a na c c o m p l i s ht h em i s s i o nt h a ti n f o r m a t i o n i n q u i r e s a sr e s e a r c he x i s t i n gc h o r da r i t h m e t i c ，w i t ht h es o m ec o n d i t i o n , t h er o u t et a b l e m a i n t a i n sb yn o d ew i l l p r o d u c et h e i n f o r m a t i o no fs o m er e d u n d a n c i e s ，s u c h i i 郑州大学硕士论文 i n f o r m a t i o ns l o wd o w nt h es e a r c hs p e e di nt h el a r g es c a l en e t w o r k s ot h i st h e s i sp u t f o r w a r da p r o j e c tf o ri m p r o v e ，f i r s ta c c o r d i n gt ot h eo r i g i n a la l g o r i t h mt oe s t a b l i s ht h e r o u t ei n f o r m a t i o nt a b l e ，t h e nt h ep r o g r e s s i v es c a n n i n g ，d i s c o v e r st h e s er e d u n d a n c i e s r o u t ei n f o r m a t i o n ，a n dd e l e t e st h e s e i n f o r m a t i o n , f i n a l l ya c c o r d i n gt ot h e c h a r a c t e r i s t i co f t b ec h o r d , d i s c o v e r st h ei s o m e t r i cf r o mt h i sk i n do f f i n g - l i k e t o p o l o g y t h en e wr o u t ei n f o r m a t i o n , a n da d dt ot h er o u t e t a b l e ，i m p r o v e st h i sk i n do f i n s u f f i c i e n c y t h r o u g ht h ea r g u m e n t ，t h i sm e t h o dk e p to r i g i n a ls c a l eo f t h er o u t et a b l e ， s p e e d i n gt h es p e e dw h i l e st h es e a r c hr e s o u r c e s b u ti tb r o u g h ts o m eb l e m i s h e s ，w h i l e t h en o d eb u i l du pi t sr o u t et a b l e ，i th a v et of i n do u tt h er e d u n d a n c yi n f o r m a t i o na n d d e l e t e ，t h e nf i n do u ts o m en e wi n f o r m a t i o nt or e p l a c e ，t h a ti n c r e a s e de x h a u s to f t i m e k e y w o r d s ：p 2 p 、r e s o u r c el o c a t e 、c h o r d 、n e t w o r k t o p o l o g y 、d i s t r i b u t eh a s h 郑重声明 本人的学位论文是在导师指导下独立撰写并完成的，学位论文没有剽窃、抄 袭等违反学术道德、学术规范的侵权行为，否则，本人愿意承担由此产生的一切 法律责任和法律后果，特此郑重声明。 学位论文作者( 签名) ：圳吼 6 年1 1 月f 6 日 郑州大学硕士论文 1 1 研究背景和意义 第一章引言 随着互联网在全世界的普及，越来越多的机器获得了网络连接。而且与互联 网的连接方式正迅速由拨号为主向宽带为主的方式发展。几年前，使用拨号方式 上网还是一种昂贵而且缓慢的事情，今天，不仅大的机构迅速普及了专线网络连 接，很多家庭用户也开始享受高速的a d s l 等上网方式带来的便利。对于个人用 户，可以利用的带宽已经从几年前的1 0 k b p s 级提高到了1 0 m b p s 级。骨干网的带 宽也在不断提高。网络连接情况的改善使得网络应用情况也发生了变化。 在低速网络时代，网络应用以客户服务器方式为主，大型服务器处于网络 应用的核心地位。服务器端拥有庞大的计算资源和网络带宽，可以同时为许多用 户服务。个人用户只能作为访问网络的终端，不可能为他人提供服务。但是在高 速网络时代，不仅网络带宽得到了极大的提高，计算资源的价格也不断下降，性 能却在迅速提高。现在，一台普通个人计算机，计算能力和存储能力已经超过二 十年前的大型机。计算资源和网络带宽这两方面条件的改进，使得很多网络终端 也具备了一定的服务能力。 因此，许多人开始用自己的个人计算机对外提供特定形式的服务。最常见的 应用是个人f t p 服务、文件共享服务以及协同计算服务等。但是个人用户的应用 环境毕竟无法与专业的服务提供商相比。无论计算资源还是网络资源，个人用户 都不具备提供大规模服务的能力。例如，对于信息检索服务，服务器需要存储巨 大数量的文件和索引，同时还要拥有强大的计算能力以处理大量并发的请求。个 人计算机显然对这种服务是无能为力的。但是，如果把网络上数量巨大的个人计 算机作为一个整体联系起来，就可以提供任何集中式服务器无法比拟的计算资 源。基于这样的思想，许多p e e rt op e e r 的网络应用迅速兴起。 p 2 p 使得网络上的沟通变得更容易、用户可以直接共享和交互而不必借助中 间商，不用像过去那样必须连接到服务器才能浏览与下载。p 2 p 另一个重要特点 是改变了互联网以大网站为中心的格局、重返“非中心化”，并把权力交还给用 户。p 2 p 看起来似乎很新，但是正如b 2 c 、b 2 b 是将现实世界中很平常的东西移 植到互联网上一样，p 2 p 的理念也是来源于生活在现实生活中我们每天都按照 基于c h o r d 的p 2 p 查询方法的研究 p 2 p 模式面对面地或者通过电话交流和沟通。 目前p 2 p 的应用系统主要有：共享c p u 资源，如s e t i h o m e ；文件共享，如 n a p s t e r 和g n u t e l l a ；分布存储，如o c e a n s t o r e ；分布协作环境，如g r o o v e 。 p 2 p 系统具有如下一些特点： ( 1 ) 大规模( 1 a r g e s c a l e ) ：为了实现资源共享，p 2 p 系统中往往会有大量的节点。 ( 2 ) 动态性( d y n a m i c ) ：在p 2 p 系统中，节点通常是自主的，因而节点可能会频 繁的加入和离开p 2 p 网络。p 2 p 网络在不停的变化中，它的变化比i p 网络要剧 烈的多。 ( 3 ) 节点的异构性( n o d e h e t e r o g e n e i t y ) ：加入到p 2 p 网络中的节点不仅在物理特 征上( 延迟，带宽，性能等) ，而且在行为上( 共享文件数量，生命周期等) 都具有非常大的差异。 考虑至r j p 2 p 系统的特点，p 2 p 系统要解决的主要问题应该有： ( 1 ) 可扩展的：p 2 p 系统应该能较好的适应系统规模( 节点数量) 的增长。 ( 2 ) 高效的：p 2 p 系统应该能在大规模情况下仍然保持高性能。 ( 3 ) 可靠的：在p 2 p 网络频繁变化的情况下，系统应该始终具有可用性。 ( 4 ) 匿名的：由于p 2 p 系统实现了各个节点之间的资源共享，保护各个节点的隐 私成为一个重要的问题。 1 2 问题的引出 在p 2 p 网络中，每个参与的节点既是服务器又是客户端，既是信息的提供者 又是信息的消费者。p 2 p 信息检索的目的就是网络中的任意节点都可以提交检索 的请求，然后这些检索通过某种路由机制被路由到和检索相关的节点上去，存储 有和该检索相关信息的节点将会回应请求，把本地相关的内容以对等的形式直接 传送到请求节点上， 下图1 1 中的检索过程分为以下几个阶段： ( 1 ) 每个节点在加入网络的时候，会对存储在本节点上的内容进行索引，以满足 本地内容检索的目的。然后按某种预定的规则选择一些节点作为自己的邻 居，加入至i j p 2 p 。 ( 2 ) 发起者p 提出检索请求q ，并将q 发送给自己的邻居。 2 郑州大学硕士论文 ( 3 ) p 的邻居收到q 后，再按照某种策略转发给它在网络中的其它邻居节点。这样， q 就在整个网络中传播开来。 ( 4 ) 收到请求q 的节点如果存储有相应内容信息，则将对应的内容返回。 图1 1p 2 p 检索图 那么如何在一个大规模分布的环境下定位资源是个十分具有挑战性的问题。 主要讨论的问题集中在如何组建p 2 p 网络，如何选择有效的资源请求路由策略以 便以较少的消息通信开销，获得较多的相关查询结果返回，同时能够保证较好的 服务均衡性。 目前，解决这个问题的方法大致分为如下两类： 1 非结构化p 2 p 系统的资源定位 非结构化的p 2 p 网络，顾名思义，在这种结构的网络中，节点通常有不同数 目的连接从而导致网络的一种“非结构化”，即一种混乱的、非常规的网络结构。 在非结构化的p 2 p 网络中通常是没有全局的坐标空间的，信息以非全局结构的方 式储存在节点中。非结构化p 2 p 网络中的有效搜索算法依然是当今研究的主题。 典型的非结构化p 2 p 网络有g n u t e l l a 1 1 和f r e e n e t t 2 1 ，与n a p s t e 唧采用集中式的目 录服务不同，g n u t e l l a 和f r e e n e t 采用了完全分布式的策略，我们可以把它们看 成是一组对等节点间的自主组合。在g n u t e l l a 网络中，每个节点都定义了本地的 共享文件夹，它们可以根据文件名的部分或者完全匹配算法进行查找信息。查找 按照简单f l o o d i n g 方式进行，首先传播到所有相邻的节点，然后再传播到相邻节 点的相邻节点，直到达到预先确定的层次为止。f r e e n e t 虽然是对g n u t e l l a 的改 进，但它同样是采用f l o o d i n g 方式进行查找的。关于g n u t e l l a 及其后代，研究者 们已经发现：由于网络带宽的限制，f l o o d m g 并不能很好的应用于大规模网络中。 基于c h o r d 的p 2 p 查询方法的研究 特别是在p 2 p 网络中，许多节点存在于i n t e r n e t 的边缘，带宽的限制更为严重。 采用f l o o d i n g 进行查找所必须的查询流量的总数可能非常巨大，将导致网络的阻 塞，并且不能确定性的查找到存在网络中的资源。 2 结构化p 2 p 系统的资源定位 在结构化p 2 p 网络中节点间的连接是基于一些常规的结构大多数类似于一个 高维的网格结构或是一个环形结构，通常每个节点拥有与其它节点相同数目的连 接。结构化p 2 p 网络常常使用某种类型的坐标空间来存储数据。每个节点负责这 个空间的一部分，这样搜索通常被简化为查找网络中某个负责的节点。查找过程 通常是直接传递。即查找消息直接被传递给负责这些信息的节点，而不关心信息 是如何被结构化的或想要查找的信息是什么类型的。它依赖于这条查找消息达到 目标节点后会执行什么。可能是节点自己拥有这些信息或者是节点只有一个指向 储存这些信息节点的指针。然后，节点通常发送一条应答消息告知查询消息的原 发送节点在哪里可以找到想要的数据。 现今一些结构化p 2 p 系统像c a n 【4 j ，c h o r d 5 1 ，p a s t r y 6 和t a p e s t r y l 7 1 使用一个 分布式哈希表( d h t l 8 】) 作为系统的基础数据结构。 结构化p 2 p 网络通过应用一致性分布式哈希和结构化路由技术，改进了对象 查找的效率并且减少了网络内部查询流量的总数，但却不得不面临着维护d h t 路由分布数据结构的高开销问题。 目前p 2 p 系统的研究人员主要的研究方法，一方面是针对p 2 p 系统需要解决的 问题设计新的算法和策略，比如c a n 和c h o r d 关于查询算法的研究，但是这两个 算法的测试还只局限于模拟，缺乏真实系统的考验，模拟网络的真实程度影响了 算法性能的可信程度。 1 3 本文工作 如上所述，目前加入互联网的计算机急剧增加，各个用户对目前采用p 2 p 方 式进行资源查找的应用越来越广。本文主要是通过对目前的p 2 p 的发展的研究， 重点对p 2 p 的几种拓扑结构，以及资源搜索方法进行了较为全面的比对，分析， 并且针对c h o r d 这- - 种结构化的p 2 p 的资源查询算法进行了深入的理论分析，并且 在最后给出了一种理论性的改进方法，来加快查询的速度。 郑州大学硕士论文 主要工作包括： ( 1 ) 本文开始先对p 2 p 技术进行了全面的介绍，其中包括p 2 p 的概念，p 2 p 的背 景介绍，p 2 p 与c s 的比对，p 2 p 的特点以及p 2 p 的关键技术。 ( 2 ) 介绍7 p 2 p 的几种拓扑结构，及其各自的特点。 ( 3 ) 针对在上述介绍的拓扑结构上采用的几种搜索方法做一个简单的介绍。 ( 4 ) 针对c h o r d 这种结构的搜索算法进行深入的研究，详细分析了查询，节点 加入或退出时的情况。 ( 5 ) 对于研究中发现的c h o r d 的不足之处，给出了改进的方案，这种方案可以 在某些情况下保持规模不变，同时增加查询的速度。 1 4 论文组织 本文共分五章。 第一章简单介绍了本文的研究背景，以及研究的意义，论文的组织结构。 第二章介绍了p 2 p 的相关内容。 第三章介绍了相关的拓扑结构以及搜索方法。 第四章对c h o r d 进行深入的分析，给出改进的方案，并对该方案进行了论证。 第五章结束语。 基于c h o r d 的p 2 p 查询方法的研究 2 1p 2 p 定义 第二章p 2 p 1 帚一早 最近几年，对等计算( p e e r - t o p e e r ，简称p 2 p ) 迅速成为计算机界关注的热门 话题之一，财富杂志更将p 2 p 列为影响i n t e r n e t 未来的四项科技之一。 目前，在学术界、工业界对于p 2 p 没有一个统一的定义，这里列举几个常用 的定义供参考： 1 p e e r - t o - p e e ri sat y p eo fi n t e r n e tn e t w o r ka l l o w i n gag r o u po fc o m p u t e ru s c r s 、丽t ht h es a m en e t w o r k i n gp r o g r a mt oc o n n e c tw i t he a c ho t h e rf o r t h ep u r p o s e so f d i r e c t l ya c c e s s i n gf i l e sf r o mo n ea n o t h e r sh a r dd r i v e s 2 p e e r - t o p e e rn e t w o r k i n g ( p 2 p ) i sa na p p l i c a t i o nt h a tr u n so nap e r s o n a lc o m p u t e r a n ds h a r e sf i l e s 、i t ho t h e ru s e r sa c r o s st h ei n t e r a c t p 2 pn e t w o r k sw o r kb y c o n n e c t i n gi n d i v i d u a lc o m p u t e r st o g e t h e rt os h a r ef i l e si n s t e a do fh a v i n gt og o t h r o u g hac e n t r a ls e r v e r 3 p 2 p 是一种分布式网络，网络的参与者共享他们所拥有的一部分硬件资源( 处 理能力、存储能力、网络连接能力、打印机等) ，这些共享资源需要由网络 提供服务和内容，能被其它对等节点( p e e r ) 直接访问而无需经过中间实体。 在此网络中的参与者既是资源( 服务和内容) 提供者( s e r v e r ) ，又是资源( 服 务和内容) 获取者( c l i e n t ) 。 2 2p 2 p 的由来 p 2 p 并不是新概念，它可以说是互联网整体架构的基础。互联网最基本的协 议t c p n p 并没有客户机和服务器的概念，所有的设备都是平等的。在十几年前， 所有的互联网上的系统都同时具有服务器和客户机的功能。然而，由于受早期计 算机性能、资源等因素的限制，随着互联网规模的迅速扩大，大多数连接到互联 网上的普通用户并没有能力提供网络服务，从而逐步形成了以少数服务器为中心 的客户机服务器( c l i e n t s e r v e r ) 架构。w w w 的风靡，正是这一应用潮流的体现。 在客户机服务器架构下，对客户机的资源要求非常少，因而可以使用户以非常 低廉的成本方便地连接互联网，推动了互联网的快速普及。但是，随着互联网对 6 郑州大学硕士论文 人们生活的联系日益紧密和深入，人们需要更直接、更广泛的信息交流。普通用 户希望能够更全面地参与到互联网的信息交互中，而计算机和网络性能的提升也 使其具有了现实的可能性。在此背景下，p 2 p 再一次受到了广泛的关注。 将p 2 p 重新带回了网络世界的一个著名例子是n a p s t e r 。该公司成立于1 9 9 9 年，它提供服务允许音乐迷们交流m p 3 文件。它与提供免费音乐下载m p 3 c o m 的不同就是在n a p s t e r 服务器没有一首歌曲，n a p s t e r 提供了一个新的软件供音乐 迷在自己的硬盘上共享歌曲文件，搜索其他用户共享的歌曲文件，并到其他也使 用n a p s t e r 服务的用户硬盘上去下载歌曲。n a p s t e r 在短时间里吸引了5 0 0 0 万用 户。然而最终，它被五大唱片商以侵犯版权推上被告席而成为世界的焦点，并最 终倒闭。但是，n a p s t e r 的思想促使了人们认识到把p 2 p 拓展到整个互联网范围 的可能性。 另一个采用p 2 p 方式实现计算资源共享的例子是s e t l h o m e 。这是一个寻 找外星球文明的大型科研工程。为了快速处理大规模天文数据，该工程将互联网 上3 0 0 万台以上的计算机通过p 2 p 方式组织起来，充分共享这些节点的空闲计算 资源( c p u ) ，从而达到了计算能力。 事实上，网络上现有的许多服务都可以归入p 2 p 的行列。即时通信系统如 i c q 、y a h o om e s s e n g e r 、m s nm e s s e n g e r 以及o i c q ( q q ) 等都是最流行的p 2 p 应用。它们允许用户互相沟通和交换信息、交换文件。但这些系统缺少对于大量 信息共享非常重要的一些功能，如资源的搜索查找。这可能正是为什么即时通讯 出现很久但是并没有能够产生如n a p s t e r 这样的影响的原因之一。 2 3o s 与p 2 p 的简单对比 两者之间的一个简单对比 - 单点错误 可升级的能力与瓶颈 集中化管理 - 信息存放位置 - 对称与非对称的参与 - 信息孤岛 基于c h o r d 的p 2 p 查询方法的研究 下面再看一下两者的结构图比较，如图2 - ic l i e n f f s e r v e r 模式和图2 - 2p e e r t o p e e r 模式， 图2 - 2p e e r t 0 p e e r 模式 通过对比，我们可以看出在客户服务器模型中，由服务器控制和管理着客户 端与其他资源，比如数据库、文件、网络和其他客户端的关系。在客户服务器 模式的网络中，服务器是“高等公民”的角色。为了管理其“下属”，服务器被赋予 了特定的权限和功能。 2 4p 2 p 技术的特点 1 非中心化( d e c e n t r a l i z a t i o n ) ：网络中的资源和服务分散在所有节点上，信息 的传输和服务的实现都直接在节点之间进行，可以无需中间环节和服务器的 介入，避免了可能的瓶颈。p 2 p 的非中心化基本特点，带来了其在可扩展性、 健壮性等方面的优势。 2 可扩展性：在p 2 p 网络中，随着用户的加入，不仅服务的需求增加了，系统 整体的资源和服务能力也在同步地扩充，始终能较容易地满足用户的需要。 整个体系是全分布的，不存在瓶颈。理论上其可扩展性几乎可以认为是无限 的。 3 健壮性：p 2 p 架构天生具有耐攻击、高容错的优点。由于服务是分散在各个 8 郑州大学硕士论文 节点之间进行的，部分节点或网络遭到破坏对其它部分的影响很小。p 2 p 网 络一般在部分节点失效时能够自动调整整体拓扑，保持其它节点的连通性。 p 2 p 网络通常都是以自组织的方式建立起来的，并允许节点自由地加入和离 开。p 2 p 网络还能够根据网络带宽、节点数、负载等变化不断地做自适应式 的调整。 4 高性能价格比：性能优势是p 2 p 被广泛关注的一个重要原因。随着硬件技 术的发展，个人计算机的计算和存储能力以及网络带宽等性能依照摩尔定 理高速增长。采用p 2 p 架构可以有效地利用互联网中散布的大量普通节点， 将计算任务或存储资料分布到所有节点上。利用其中闲置的计算能力或存 储空间，达到高性能计算和海量存储的目的。通过利用网络中的大量空闲 资源，可以用更低的成本提供更高的计算和存储能力。 5 隐私保护：在p 2 p 网络中，由于信息的传输分散在各节点之间进行而无需经 过某个集中环节，用户的隐私信息被窃听和泄漏的可能性大大缩小。此外， 目前解决i n t e r n e t 隐私问题主要采用中继转发的技术方法，从而将通信的参 与者隐藏在众多的网络实体之中。在传统的一些匿名通信系统中，实现这一 机制依赖于某些中继服务器节点。而在p 2 p 中，所有参与者都可以提供中继 转发的功能，因而大大提高了匿名通讯的灵活性和可靠性，能够为用户提供 更好的隐私保护。 6 负载均衡：p 2 p 网络环境下由于每个节点既是服务器又是客户机，减少了对 传统c s 结构服务器计算能力、存储能力的要求，同时因为资源分布在多个 节点，更好的实现了整个网络的负载均衡。 2 5p 2 p 计算技术的应用领域 目前人们从很多不同的角度来应用p 2 p 计算技术，主要应用的角度包括：信 息资源共享、普及计算、协同工作、实时通信技术等。下面将从这几个角度分别 进行一个简单的介绍。 2 5 1 信息资源共享 信息资源共享一直是网络技术发展的重要推动力也是p 2 p 技术中最典型的应 9 基于c h o r d 的p 2 p 查询方法的研究 用。目前人们主要采用w e b 技术来实现信息资源共享，在基于w e b 的方式进行 信息资源共享时，w e b s e r v e r 需要能够对大量用户的访问提供有效的服务，w 曲 s e r v e r 经常成为这类系统的性能瓶颈所在。n a p s t e r 是提供给用户在互联网上共 享m p 3 音乐文件的p 2 p 应用，与传统的音乐共享技术不同的是n a p s t e r 把音乐文 件存储在客户节点上而不是存储在服务器节点上，中心服务器上存储的仅仅是文 件的索引信息，用户之间可以直接共享、传输音乐文件而不需要通过中心索引服 务器。采用这种方式来共享信息资源可以更加充分的利用网络中的带宽资源，从 而提高了系统数据通信的效率。目前有很多研究项目都是针对p 2 p 的文件共享 的，包括f r e e n e t 、g n u t e l l a 、f r e eh a v e n 、o h a h a 等，这些研究项目均从不同的 角度尝试解决目前网络中的信息资源共享所存在的一些问题。 2 5 2 普及计算 普及计算技术研究的是如何充分利用网络中各种各样的计算单元来共同完 成大规模的计算任务。由于单一计算单元的计算能力总是有限的，因此人们一般 采用并行技术、分布式技术将多个计算单元节点联合起来共同完成大规模的计算 任务，同时目前网络中的计算机的计算能力一直利用的不是很充分，人们期望能 够充分利用网络中的闲散计算能力来完成大规模的计算任务，这样将会使得网络 中所蕴含的海量计算能力得到更加充分的利用。p 2 p 计算技术则为普及计算技术 的发展提供了新的机遇。 s e t i h o m e 是b e r k e l e y 大学启动的普及计算的研究项目，目前大约吸引了 一百万台计算机参与研究。该项目是利用该大学的空间科学实验室开发的屏幕保 护程序来使用计算机的空闲机时，该屏幕保护程序在运行时分析在外星系文明研 究项目中所获得的无线电信号，程序运行节点从中心服务器节点下载数据后进行 计算然后再将计算结果上载到该实验室的中心服务器上，因为不是完全的p 2 p 计算模式，所以节点之间不能直接利用彼此计算的数据。 普及计算可以帮助企业完成大规模的数据处理，参与计算的计算机之间可以 直接共享计算中的中间结果。通过整合这些以前尚未使用的闲散计算能力和资源 可以将企业的计算能力相比以前得到很大的提升，同时因为利用了多个节点上的 计算能力使得计算任务可以高效廉价的完成。g r i d 是研究普及计算的典型代表， i b m 公司也启动了自组织计算计划来研究普及计算。 1 0 郑州大学硕士论文 2 5 3 协同工作 协同工作是指多个用户之间利用网络中的协同计算平台互相协同来共同完 成计算任务，共享信息资源等，计算机支持的系统工作c s c w 是协同工作的典 型研究方向之一。目前许多企业都使用协同工具来完成公司内部员工之间的通 信，但是传统的协同应用平台一般都是采用电子邮件方式的来完成工作人员之间 的协同工作，而并不能很好的完成企业与合作伙伴、客户、供应商之间的沟通与 交流。下一代的p 2 p 的解决方案试图要很好的解决这些问题，通过使用各种形式 的个人对个人，不存在中心服务器的协同工具来提供给企业一个包含项目管理等 功能的协同应用平台。通过采用p 2 p 计算技术个人和组织可以随时采用各种方式 建立在线、非在线的协同应用环境。协同工作使得在不同地点的参与者可以在一 起工作，因为采用文件直接共享的方式可以保证系统中的每个人所获得的信息总 是最新的，同时节省了采用单独服务器时对该服务器存储以及性能的要求。 一般的协同应用包括：实时通信、聊天室、好友列表、文件共享、语音通讯 等基本的功能，除了这些基本的功能，用户之间还可以共享白板，协同写作进行 视频会议等。由于协同应用的用户数量一般都比较大，数据量也比较多，采用传 统的单一中心节点服务方式很难满足这种应用，如果采用p 2 p 的计算方式可以不 再需要目前协同工作中的中心服务器，参与协同工作的两台计算机可以直接建立 联系进行协同工作。g r o o v e 是基于i n t e m e t 的p 2 p 协同应用软件的典型代表，其 用户可以直接进行实时的协同工作。 2 5 4 实时通信技术 实时通信技术是网络中重要的通信技术，成功的实时通信技术吸引了数以万 计的在线用户。目前的实时通信技术一般也采用一个中心服务器控制着用户的认 证等基本的信息，节点之问直接进行数据通信。i c q 、o i c q 、a i m 等是典型的 实时通信系统，这些系统也包含好友列表等基本功能。j a b b e r 是一个开放源码的 实时通信平台，j a b b e r 提出了一个采用x m l 表示的在不兼容的各种实时通信平 台之间进行消息交换的协议。 基于c h o r d 的p 2 p 查询方法的研究 2 5 5p 2 p 计算技术的其它应用领域 除了前面介绍的p 2 p 计算技术的几个典型的应用领域，许多公司都从不同的 角度来应用该技术。n e t 技术是微软公司提出并正在开发的一个基于i n t e r n e t 的 操作系统，该技术是围绕着以s o a px m l 通信协议的w e b 服务为主。j x t a 是 s u n 公司提出的一个p 2 p 的网络底层支撑平台，该平台允许用户在其上开发各 种p 2 p 应用。 2 6p 2 p 信息检索技术 p 2 p 系统本质上也是一个分布式系统，同时它也具备着一些区别于传统分布 式系统的特色：更强调自组织、对等、动态的特性。因此在研究p 2 p 信息检索技 术的同时，可以借鉴传统分布式信息检索( d i s t r i b u t e di n f o r m a t i o nr e t r i e v a l ，d 瓜) 的研究，并结合p 2 p 自身的特点进行设计。 1 分布式信息检索 分布式信息检索是信息检索领域的一个分支。传统意义上的d m 一般研究如 下的几个问题： 如何取得一个文本数据库的内容描述符( s i t ed e s c r i p t i o n ) 。描述符一般是文本 数据库中的词列表及它们的词频信息。 如何根据数据库内容描述符和查询的比较，对数据库进行排名( r e s o u r c e r a n k i n g ) ，决定最可能包含所需信息的数据库。对每一个查询都要执行这个 操作。 如何选择进行检索的目标数据库( r e s o u r c es e l e c t i o n ) 。 如何对目标数据库进行检索( s e a r c h i n g ) 。 如何把来自不同数据库的文档列表合并。 在这种框架下，著名的方法有g g i o s s 、c o r i 、c v v 、l a n g u a g em o d e l i n g 、 q u e r yc l u s t e r i n g 、q u e r yp r o b i n g 、q u e r y b a s e ds a m p l i n g 等，其中c o r i 与 q u e r y b a s e ds a m p l i n g 是两种效果较好的方法。这些方法的主要优点是所需要的 信息量较少，只要有各个数据库中的词频统计信息，就可以进行检索，在一定程 度上满足用户的信息需求。如果满足以下条件，检索效果可以相当不错： a ) 每个文本数据库都可以提供精确的描述符； 郑州大学硕士论文 b ) 每个文本数据库的检索结果都是可比较的； c ) 用户不要求很高的查全率。 条件a ) 是进行有效的数据库选择的前提。有的数据库可能无法提供描述符或 者不能提供精确的描述符，这时只能通过采样来决定它的描述符。 条件b ) 是d i r 中较薄弱的环节，因为只有以下条件全部满足，检索结果才是 可比较的： 目标数据库运行的检索协议全部相同； 检索协议保证在不同的数据库之间的文档权值可以互相比较； 目标数据库能够而且愿意提供文档的权值。 这些条件是很苛刻的。因此，很难对不同数据库的结果进行合理的比较。例 如第二个条件，即使同一个检索算法，在不同数据库中的检索结果很有可能是不 能比较的。元搜索引擎常用的结果合并方法是对每一个数据库的结果列表进行内 部规格化，把文档权值转换成区n 0 ，1 】内的数值，然后假设它们是可比较的，在 此基础上进行合并。这种方法简单易行，如果每个数据库的检索质量都很好，那 么混合后的结果也是相当好的；如果存在一部分低质量的检索结果，就无法得到 稳定的信息检索方法，也无法获得在分布式环境下的好的合并结果了。 条件c ) 反映了用户的期望与对d i r 方法局限性的忍受程度。用户的检索需求 是多种多样的。有的检索需求主题比较宽泛，例如t r e c2 0 0 2 q ，的t o p i c d i s t i l l a t i o n 任务，只需为用户找到一部分相关文档即可。但另一部分检索需求便 不太容易满足，例如t r e c2 0 0 2 的n a m e dp a g ef i n d i n g 及t r e c2 0 0 1 的h o m e p a g e f i n d i n g 任务。这些任务的答案通常只有一个l ，如果答案恰好在一个r e s o u r c e r a n k i n g 很低的数据库中，那么它根本不会被检索到，用户的信息需求便无法满 足。从评测角度看，r e s o u r