（计算机应用技术专业论文）基于路由信息表的p2p信息检索机制研究.pdf

大连理工大学硕士学位论文 摘要 近年来随着许多p 2 p 系统的出现，p 2 p 技术逐渐成为人们研究的热点。p 2 p 技术目 前主要应用在文件共享、分布式计算、协作系统、电子商务和以p 2 p 为基础的深度搜索 引擎等方面。其中，信息共享是最常见的一种应用。 在p 2 p 共享系统中，每个节点既可以将本地资源共享出来与其它节点分享，又可以 从其它节点获取资源，实现了服务器与客户端的两位一体。然而，现有的信息检索机制 存在着种种不足：基于结构化p 2 p 网络的检索效率很高，但是由于构造过于严格，难以 在i n t e r a e t 上普及，而且仅能支持粗粒度的文件共享；非结构化p 2 p 网络实现简单，是 p 2 p 文件共享系统的主要实现方式，但是由于搜索的盲目性，其检索效率又普遍比较低 本文在深入研究p 2 p 信息检索技术的基础上，重点研究了基于非结构化p 2 p 网络的 信息检索技术。针对现有p 2 p 检索的路由盲目性问题，论文给出了能够适应网络可扩展 性的路由查询机制。该机制在检索过程中根据各节点的响应顺序，将每一条查询路径上 的回复节点信息分别保存在与它相邻的两个回复节点的路由信息表中，并据此为以后的 检索提供路由。在没有路由信息可用的情况下，将选择原始邻居节点进行路由，以利用 原始拓扑结构的特点。最后用实验结果证明了本文算法的有效性。 由于用户一般对前几个检索结果比较感兴趣，并且各响应节嚏将检索结果直接返回 给请求节点，增加了请求节点的负载。针对这两点，本文利用路由信息表检索机制，采 用t o p - k 查询对检索结果进行处理。在返回检索结果时根据查询条件只返回匹配度最高 的t o pk 个文档，如果符合查询条件的不足k 个，则只返回符合条件的查询结果，这样 降低了网络开销，减轻了请求节点的负担。最后通过性能分析和仿真实验证明了它的实 用性和准确性。 关键词：p 2 p 网络；相似度；路由信息表；查询结果 大连理工大学硕士学位论文 r o u t et a b l eb a s e di n f o r m a t i o nr e t r i e v a lm e c h a n i s mr e s e a r c hi n p e e r - t o p e e rn e t w o r k a b s t r a c t h lr e c e n ty e a r s ，a l o n g 、丽t l lt h ee m 盯咎：1 1 o fm a n yp 2 ps y s t e m s ，t h ep 2 pt e c h n i q u e b e c o m e st h er e s e a r c h f u lh o t s p o t n o wt h ep 2 pt e c h n i q u ei sm a i n l ya p p l i e di nf i l e - s h a r i n g , d i s t r i b u t e dc a l c u l a t i o n , c o o p e r a t i n gs y s t 锄，e l e c t r o n i cc o m m e r c 圮a n ds e a r c he n g i n e o n eo f t h em o s tp o p u l a rp 2 pa p p l i c a t i o ni st h ef i l e - s h a r i n gs y s t e m i nap 2 pf i l e - s h a r i n gs y s t e m e a c hp e e rp e r f o r m sa sb o t has e r 、惯a n dac l i e n t , w h i c h m e a n st h a tt h e yc 锄g e tr e s o u r c e sf o r mr e m o t es i t e s ，m e a n w h i l e ，t h e ya r ea l s op r o v i d i n gl o c a l n 踟u r i 瑚f o ro t h e rp e e r s h o w e r v e r , e x i s t i n gp 2 ps e a r c h i n gm e c h a n i s m sa g eu s u a l l y d i s s a t i s f i e d f o re x a m p l e ，s t r u c t u r e dp 2 ps y s t e m sa r ee f f i c i e n tb u tl a c ko fa c t u a li m p l e m e n t s o nt h ei n t e m e t , b e c a u s eo ft l l e i rc o m p l i c a t e ds t r u c t u r e s a n di t 啪o n l ys u p p o r tt h e f i l e - s h a r i n go fc o a r s eg r a n u l a r i t y u n s t r u c t u r e dp 2 ps y s t e m sc a l lb ei m p l e m e n t e ds i m p l ya n d t h e ya r em o r ep o p u l a r b u tt h e ya r ei n e f f i c i e n tb e c a u s eo f t h eb l i n dr o u t i n g f r o mv a r i o u sp e r s p e c t i v e s ，o u rw o r kf o c u s e so nh o wt oi m p r o v ei n f o r m a t i o nr e t r i e v a l e f f i c i e n to fu n s t r u c t u r e dp 2 pf i l e - s h a r i n gs y s t e m s i nt h i sp a p e r , ar o u t i n gs t r a t e g yt h a to a n a d a p tt ot h ee x t e n s i o no fn e t w o r ki sp r o p o s e dt oa t t a c kt h ep r o b l e mo fb l i n dr o m i n gi np 2 p s e a r c h d u r i n gt h ec o n r s eo fs e a r c h i n g , t h ei n f o r m a t i o no fe v e r yr e p l y i n gn o d ei ss a v e di n m u t et a b l e so fi t st w on e i g h b o r h o o dn o d e sr e s p e c t i v e l ya c c o r d i n gt ot h er e s p o n d i n go r d e r , a n dw h i c hw i l lb eu s e dt og u i d et h ef o l l o w i n gr o u t i n g i n i t i a ln e i g h b o r h o o dn o d ei sc h o s e nt o r o u t ei nc a s eo f n oi n f o r m a t i o na v a i l a b l e ，w h i c hm a k e su s eo f t h ec h a r a c t e r i s t i c so f t h ei n i t i a l t o p o l o g y a tl a s t ，a u t h o rp r e s e n t e dad e s i r a b l ee x p e r i m e n t a lr e s u l t , a n dp m v e dt h ev a l i d i t ya n d e f f i c i e n c yo f t h ea l g o r i t h m b e c a u s em a n yu s e r sa r eu s u a l l yi n t e r e s t e di nt h et o ps e v e r a lr e s u l t s ，a n de v e r ya n s w e r e d p e e r sr e t b r ut h er e s u l t st ot h er e q u e s tp e e rs t r a i g h t l y , t h er e q u e s tp e e r sl o a di si n c r e a s e d s t a n d i n go nt h i sp o i n t ，b a s i n go nt h er o u t i n gt a b l e ，t h i sp a p e ra d o p t st h et o p - kq u e r yt o p r o c e s s t h e r e s u l t s d u r i n gr e t u r n i n gt h er e s u l t s ，t h ea n s w e r e dp e e rr e t u r n s t h et o p - k d o c u m e n t st ot h er e q u e s tp e e r , a c c o r d i n gt ot h eq u e r yc o n d i t i o n i ft h en u m b e ro fs a t i s f i e d r e s u l t si sf a l ls h o r to fk , t h ea n s w e r e dp e e rm e r e l yr e t u n l $ t h es a t i s f i e dr e s u l t s i nt h i sw a y , i t b a nr e d u c et h en e t w o r ks p e n d i n ga n dl i g h t e nt h er e q u e s tp e e r sl o a d a tt h ee n do ft h i sp a r t ， t h ee x p e r i m e n t a lr e s u l t sm a n i f e s tt h a tt h i ss t r a t e g yi sp r a c t i c a la n dp r e c i s e k e yw o r d s ：p e e r - t o - p e e rn e t w o r k ；s i m i l a r i t y ；r o u t et a b l e ；q u e r yr e s u l t s 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意 作者签名：垒丝盎日期：丝z ：1 2 ：墟 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名 导师签名 卫也搔 蕴够彻 2 2 d 年尘月旦日 大连理工大学硕士学位论文 1绪论 1 1p 2 p 概述 1 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 2 p 技术并不是一种新兴的技术，2 0 世纪7 0 年代中期，源于局域网的文件共享p 2 p 技术就 开始流行起来了。目前大家所关注的p 2 p 技术，是旧有技术的新的模式。首开p 2 p 之风 最有名的计划是美国柏克利大学开展的寻找外星生命的s e t i h o m e 研究计划。1 9 9 9 年， s e t i h o m e 开始使用p 2 p 计算方法来分析星际间无线电信号，寻找宇宙中可能存在的 其他外星文明证据。p 2 p 技术串联所有参与研究计划者闲置的电脑来执行庞大复杂的运 算，然后把结果传到s e t i h o m e 总部。也正是s e t l h o m e 计划推动了最近的p 2 p 技 术热潮。2 0 0 0 年用于共享m p 3 音乐的n a p s t e r 软件与美国唱片界的一场官司将p 2 p 技 术重新带回人们的视线。之后，各种基于p 2 p 的应用风起云涌，p 2 p 技术也成了计算机 研究的热点技术，各个领域的计算机专家都开始了对p 2 p 技术及其应用的研究。 1 1 2p 2 p 网络的概念 p 2 p 目前还没有被人们广泛接受的定义，m m 为p 2 p 下了如下定义。 p 2 p 系统由若干互联协作的计算机构成，且至少具有如下特性之一：系统依存于边 缘化( 非中央式服务器) 设备的主动协作，每个成员直接从其他成员而不是从服务器的参 与中受益；系统中的成员同时扮演服务器与客户端的角色，相互之间可以共享资源，并 且可以任意地加入和离开网络；系统应用的用户能够意识到彼此的存在，构成一个虚拟 的或实际的群体。 简单地说，p 2 p 直接将人们联系起来，让人们通过互联网直接交互信息，p 2 p 使得 网络上的沟通变得更容易，更直接地共享和交互，真正地消除中间商。p 2 p 技术就是用 户可以直接连接到其他用户的计算机进行交换文件，而不是像过去那样连接到服务器去 浏览与下载。p 2 p 另一个重要特点是改变互联网现在的以大网站为中心的状态，重返“非 中心化”，并把权力交还给用户。p 2 p 看起来似乎很新，但是正如b 2 c 、b 2 b 是将现实 世界中很平常的东西移植到互联网上一样，p 2 p 并不是什么新东西，在现实生活中我们 每天都按照p 2 p 模式面对面地或者通过电话交流和沟通。 基于路由信息表的p 2 p 信息检索机制研究 即使从网络上看，p 2 p 也不是新概念，p 2 p 是互联网整体架构的基础。互联网最基 本的协议t c p i p 并没有客户机和服务器的功能。当然，后来发展的那些架构在t c p i p 之上的软件的确采用了客户机服务器的结构；浏览器和w c b 服务器，邮件客户端和邮 件服务器。但是，对于服务器来说，它们之间仍然是对等联网的。以电子邮件为例，互 联网上并没有一个巨大的、唯一的邮件服务器处理所有的电子邮件，而是对等联网的邮 件服务器相互协作把电子邮件传送到相应的服务器上去。另外用户之间的电子邮件则一 直是对等的联络渠道。在前些年，互联网的发展至少从表面上远离了p 2 p ，互联网上绝 大部分的节点也不能和其他节点直接地交流。n a p s t e r 唤醒了深藏在互联网背后的对等 联网理念。n a p s t e r 的文件共享目录功能在局域网中是常见的，但是n a p s t e r 的成功促使 人们认识到把这种“对等联网”理念拓展到整个互联网范围的可能性。 事实上，网络上现有的很多服务都可以归入p 2 p 的行列。即时讯息系统比如i c q 、 a o li n s t a n tm e s s a g e 、微软的m s nm e s s e n g e r 以及国内的o i c q 是最流行的p 2 p 应用。 它们允许用户互相沟通、交换信息和交换文件，但用户之间的信息交流不是直接的，需 要有位于中心的服务器来协调，而且这些系统并没有诸如搜索这种对于大量信息共享非 常重要的功能。这个特征的缺乏可能正是为什么即时讯息出现很久，但是并没有能够产 生如n a p s t e r 这样巨大的影响的原因之一。 1 1 3p 2 p 网络的特点 与其他网络模型相比，p 2 p 具有以下几个特点。 ( 1 ) 分散化 网络中的资源和服务分散在所有节点上，信息的传输和服务的实现都直接在节点之 间进行，可以无需中间环节和服务器的介入，避免了可能的瓶颈。即使是在混合p 2 p 中， 虽然在查找资源、定位服务或安全检验等环节需要集中式服务器的参与，但主要的信息 交换最终仍然在节点中间直接完成。这样就大大降低了对集中式服务器的资源和性能的 要求。分散化是p 2 p 的基本特点，由此带来了其在可扩展性、健壮性等方面的优势。 ( 2 ) 可扩展性 在p 2 p 网络中，随着用户的加入，不仅服务的需求增加了，系统整体的资源和服务 能力也在同步地扩充，始终能较容易地满足用户的需要。即使在诸如n a p s t e r 等混合型 架构中，由于大部分处理直接在节点之间进行，大大减少了对服务器的依赖，因而能够 方便地扩展到数百万个以上的用户。而对于纯p 2 p 来说，整个体系是完全分布的，不存 在瓶颈。理论上其可扩展性几乎可以认为是无限的。 ( 3 ) 健壮性 大连理工大学硕士学位论文 在互联网上随时可能出现异常现象，网络中断、网络拥塞、节点失效等各种异常事 件都会给系统的稳定性和服务持续性带来影响。而p 2 p 架构则天生具有耐攻击、高容错 的优点。由于服务是分散在各个节点之间进行的，部分节点或网络遭到破坏对其它部分 影响很小。而且p 2 p 模型一般在部分节点失效时能够自动调整整体拓扑，保持其它节点 的连通性。事实上，p 2 p 网络通常都是以自组织的方式建立起来的，并允许节点自由地 加入和离开。一些p 2 p 模型还能够根据网络带宽、节点数、负载等变化不断地做自适应 式的调整。 ( 4 ) 隐私性 随着互联网的普及和计算存储能力飞速增长，收集隐私信息正在变得越来越容易。 隐私的保护作为网络安全性的一个方面越来越被大家所关注。在p 2 p 网络中，由于信息 的传输分散在各个节点之间进行而无需经过某个集中环节，用户的隐私信息被窃听和泄 漏的可能性大大缩小。此外，目前解决i n t e m e t 隐私问题主要采用中继转发技术，从而 将通信的参与者隐藏在众多的网络实体之中。在传统的一些匿名通信系统中，实现这一 机制依赖于某些中继服务器节点。而在p 2 p 中，所有参与者都可以提供中继转发的功能， 因而大大提高了匿名通讯的灵活性和可靠性，能够为用户提供更好的隐私保护。 ( 5 ) 高性能 性能优势是p 2 p 被广泛关注的一个重要原因。随着硬件技术的发展，个人计算机的 计算和存储能力以及网络带宽等性能依照摩尔定理高速增长。而在目前的互联网上，这 些普通用户拥有的节点只是以客户机的方式连接到网络中，仅仅作为信息和服务的消费 者，游离于互联网的边缘。对于这些边际节点的能力来说，存在极大的浪费。采用p 2 p 架构可以有效地利用互联网中散布的大量普通节点，将计算任务或存储资料分布到所有 节点上。利用其中闲置的计算能力或存储空间，达到高性能计算和海量存储的目的。这 与当前高性能计算机中普遍采用的分布式计算的思想是一致的。但通过利用网络中的大 量空闲资源，可以用更低的成本提供更高的计算和存储能力。 1 1 4p 2 p 网络与传统网络的对比 在p 2 p 网络中，弱化了服务器的功能，甚至取消服务器，任意两台p c 机互为服务 器客户机，即使只有一个对等点存在，网络也是处于活动状态的，节点所有者可以随 意地将自己的信息发布到网络上。p 2 p 技术将导致信息数据成本资源向所有用户的计算 机均匀分布，即“边缘化”趋势。 首先，c s ( c l i e n t s e v e r ，客户端服务器) 模式下的因特网是完全依赖于中心服务器 的，没有服务器的p 2 p 不足之处在于不易管理，而对c s 网络，只需要在中心点进行管 基于路由信息表的p 2 p 信息检索机制研究 理，从而带来的不足就是p 2 p 网络中数据的安全性难于保证p 2 p 技术与c s 技术性能 比较如表1 1 所示。 表1 1p 2 p 网络和传统网络的性能比较 t a b 1 1p e r f o r m a n c ec o m p a x i s o nb d h o p 2 pn e t w o r ka n dt r a d i t i o n a ln e t w o r k 在传统的c s 模式中，客户端之问要进行文件交换必须经过服务器，随着节点的增 加，服务器的负担越来越重，并逐渐形成系统瓶颈，一旦服务器崩溃，整个网络也随之 瘫痪。而在p 2 p 网络中每个节点的地位都是对等的，每个节点既可以充当服务器，为其 他节点提供服务，同时也充当客户端，享用其他节点提供的服务。同时，由于每个节点 在工作时都在向网络贡献资源( 存储空间、c p u 周期等) ，因此对等点越多，网络的性能 就越好。 其次，c s 模式下的因特网完全依赖于中心点服务器，没有服务器就根本无法 工作，网络也就毫无意义可言。而在p 2 p 网络中，每个节点都可以被看作是服务器，可 以随意地将自己的信息发布到网络上，以供其他节点交换共享。 最后，在c s 模式下即使客户端有大量的闲置资源，如果没有得到服务器的响应资 源也无法被利用，资源利用率比较低下。而在p 2 p 网络中，一切闲散资源都有机会得到 利用，具有很高的资源利用率。c s 模式与p 2 p 模式的对比如图1 1 和图1 2 所示。 一4 大连理工大学硕士学位论文 客户机客户机 客户机 图1 1 传统网络的工作模式 f i g 1 1w o r k n l o ( j e o f t h e u a d i f i o n a ln e t w o r k 节点节点 图1 2p 2 p 网络的工作模式 f i g 1 2 w o r km o d eo f t h ep 2 pn e t w o r k 1 2 p 2 p 的应用 作为一种新型的网络应用体系结构，p 2 p 网络的应用发展迅速，己经在众多领域获 得成功应用，并且应用的数量和领域还在迅速发展中。 ( 1 ) 内容共享应用 p 2 p 网络赋予普通网络节点以个性化的方式共享内容的功能，是p 2 p 发展最早也是 最成功的应用。典型的内容共享系统包括n a p s t e r i “、k a z a a 【2 1 、m o r p h e u s t 2 l 和g n u t e l l a 3 l 基于路由信息表的i 2 1 信息检索机制研究 等。p 2 p 内容共享应用己经成为互联网上的主流应用之一。从用户数量上来看，欧美比 较流行的p 2 p 内容共享软件k a z z a 和m o r p h e u s 的用户数以亿级别计算，超过所有网络 用户的一半以上，同时在线用户超过百万。从带宽消耗来看，许多i s p 主干带宽的5 0 0 , 4 以上被p 2 p 内容共享占用，而且还在持续增长中。 p 2 p 内容共享除了需要提高其服务质量之外，同时还存在网络带宽消耗大、难以实 现可扩展的内容搜索等技术问题，而版权、管理等非技术性问题也制约了内容共享系统 的发展。 ( 2 ) 内容发布应用 内容发布应用是p 2 p 网络的重要应用领域。传统的基于c $ 模式的内容发布应用的 服务能力的提高单纯依靠服务器集群、镜像服务器数量的增加，成本非常高昂，难于适 应用户需求的动态变化。p 2 p 网络利用普通节点的存储和带宽能力，有效减少对内容发 布服务器的压力，实现动态可扩展的内容发布服务。一些大型软件己经采用p 2 p 技术成 功完成大规模的发布【4 】。 ( 3 ) 内容存储应用 在基于p 2 p 的分布存储应用中，参与节点组成一个分布存储系统，每个节点都将自 己的部分内容存储到其它节点上，也为其它节点提供存储服务。基于p 2 p 的分布存储应 用的核心问题是数据定位算法，以及与之相关的数据复制、数据缓存、数据更新、访问 控制等关键技术。典型的分布存储应用研究包括p a s t 5 1 、o c e a n s t o r d 6 1 等。 ( 4 ) 协同工作应用 协同工作是指多个用户利用网络中的协同计算平台，互相协同来共同完成计算任 务，共享信息资源等。利用p 2 p 计算技术，个人和组织可以随时采用各种方式建立在线、 非在线的协同应用环境。p 2 p 技术的出现，使得互联网上任意两台p c 都可能建立实时 的联系，构建一个安全、共享的虚拟空间，让处于不同地理位置的人们共同完成某个项 目或任务，而且p 2 p 能够较好的支持无线移动设备以及a d - h o c 网络。比较著名的p 2 p 协作系统包括g r o o v e 、m a g i 等。 即时通信应用是一种简单的协同工作应用，参与节点之间可以实现直接的即时通 信。q q 、m s n 、a i m 等是典型的即时通信系统，这些系统都吸引了大量用户。j a b b e r 是一个开放源码的实时通信平台，提出了一个采用x m l 表示的，在不兼容的各种实时 通信平台之间进行消息交换的协议。 ( 5 ) 分布计算应用 p 2 p 网络可以聚合i n t e r n e t 边缘大量计算机的空闲计算能力，得到可与昂贵的超级 计算机相比拟的性能。p 2 p 分布计算比较著名的项目有s e t i h o m e 、g e n o m e h o m e 、 6 大连理工大学硕士学位论文 f o l d i n g a o m e 和d i s t r i b u t e d n e t 等等。p 2 p 计算适用于一些可并行化，计算量大但计算 单元之间通信量小的计算任务。需要解决的问题包括任务的分解算法、计算结果的验证、 引入商业模式激发用户参与的兴趣等。 ( 6 ) 无线移动网络应用 移动自治网络与p 2 p 网络有很多相似之处：动态网络特征，节点随时加入和退出网 络：多跳特性，节点之问的通信可以是多跳连接；分布控制特性，节点同时充当客户端 和服务器的角色。p 2 p 网络的自组织技术、路由协议、容错通信都可以应用到移动自治 网络领域，提高移动节点的流量控制、负载均衡、近似路由等特性当前p 2 p 技术与无 线网络技术的交叉应用已经成为研究热点i ”。 1 3p 2 p 技术面临的问题 p 2 p 系统本质上也是一个分布式系统，但是较之传统分布式系统更强调自组织、对 等、动态。p 2 p 系统的这些特性使其面临以下的技术问题【”。 ( 1 ) 网络拓扑结构 拓扑结构是指分布式系统中各个计算单元之间的物理或逻辑的互联关系。节点之间 的拓扑结构一直是确定系统类型的重要依据。目前互连网络中广泛使用集中式、层次式 等拓扑结构。i n t c r n c t 本身是世界上最大的非集中式的互联网络，但是九十年代所建立 的一些网络应用系统却是完全集中式的系统，很多w e b 应用都是运行在集中式的服务 器系统上。集中式拓扑结构系统目前面临着过量存储负载、d o s 攻击等一些难以解决的 问题。层次式拓扑结构是一种应用比较广泛的分布式拓扑结构，d n s 系统是其最典型的 应用。p 2 p 系统一般要构造一个非集中式的拓扑结构，在构造过程中需要解决系统中所 包含的大量节点如何命名、组织以及确定节点的加入、离开方式、出错恢复等问题。 ( 2 ) 资源定位和路由机制 在典型的p 2 p 网络中数据资源分布在各个独立的节点上，如何高效地索引、查找、 定位以及访问这些数据信息资源是另一个需要关注的重要问题，在分布式系统中这些问 题同样也是正在研究的热点问题。u r l 是目前在w e b 上使用最普遍的信息定位策略， d n s 则提供了一套层次式的查找机制。一般来说，在p 2 p 共享应用中所采用的检索方 式是利用关键字来查询自己所需的信息资源，同时人们也期望能够将数据资源的索引信 息存放在系统中的每一个节点上。路由机制是指节点之间通信的消息传递路径，合适的 路由机制可以充分的利用网络带宽资源并使系统具有很好的容错性、可扩展性。目前， 很多系统中的路由机制都是和这些系统的逻辑拓扑结构紧密相关的。在数据的访问过程 中则期望能够采用流水、并行或者选择传输路径的方式来加快数据的访问速度。 基于路由信息表的p 2 p 信息检索机制研究 ( 3 ) 异构网络环境的互操作性和扩展性 p 2 p 网络连接了各种自治资源和系统，它需要考虑如何屏蔽操作系统、网络协议的 异构性和复杂性，使分布在网络上的不同机器能够相互传递消息协同工作。p 2 p 网络形 成的初期，计算规模较小。随着大量计算单元的不断加入，系统的资源规模也随之扩大。 因此需要考虑在资源规模不断扩大、应用不断增长的情况下系统的可扩展性，不降低网 络的整体性能。 ( 4 ) 元数据组织与表示 p 2 p 网络面向的是异构网络与操作系统，需要在这些系统之阃交换数据资源，但是 因为这些系统的数据表示并不都是完全相同的，这就需要一个能够在多个系统之间确定 一个通用的元数据表示方案。关于元数据的组织包括数据资源的表示、消息通信协议等， 很多系统都支持s o a p 或者x m l - r p c 等协议。 ( 5 ) p 2 p 网络的支撑技术 i n t e r n c t 技术的发展使得连入互联网络中的设备不再局限于计算机，在p 2 p 的计算 环境中要求任何设备都可以在任何地点很容易地加入到这个环境中。所谓的计算设备既 包括有线设备也包括无线设备，这样就需要很多网络传输的支撑技术来支持各种不同设 备连入整个p 2 p 网络。 ( 6 ) 安全问题 安全问题是一直伴随着互联网发展的重要问题，安全问题包括很多相关的问题，比 如应该防止他人控制整个系统、增加恶意信息等，同时系统应能够保证系统中信息资源 的正确性。在p 2 p 系统中，系统安全同样面临着巨大的挑战。p 2 p 系统需要在没有中心 节点的情况下，提供身份的认证，授权以及数据信息的安全存储、数字签名、加密、安 全传输等工具，同时p 2 p 系统要有能力抵抗过量存储负载、d o s 攻击等攻击行为。 1 4 论文的主要工作及组织结构 非结构化p 2 p 系统在p 2 p 文件共享系统中占有重要地位，当前存在许多非结构化 p 2 p 系统环境下的信息检索机制。 本文在深入研究各种p 2 p 信息检索技术的基础上，针对现有p 2 p 检索的路由盲目性 问题，给了一种能够适应网络可扩展性的路由查询机制。该机制在检索过程中根据各节 点的响应顺序，将每一条查询路径上的回复节点信息分别保存在与它相邻的两个回复节 点的路由信息表中，并据此为以后的检索提供路由。在没有路由信息可用的情况下，将 选择原始邻居节点进行路由，以利用原始拓扑结构的特点。 8 一 大连理工大学硕士学位论文 然后，本文又对信息检索结构进行了优化处理。由于用户一般对前几个检索结果比 较感兴趣，并且各响应节点将检索结果直接返回给请求节点，增加了请求节点的负载。 针对这两点，本文利用给出的路由信息表机制，采用t o p - k 查询对检索结果进行处理。 在返回检索结果时根据查询条件只返回匹配度最高的t o pk 个文档，如果符合查询条件 的文档不足k 个，则只返回符合条件的查询结果，这样降低了网络开销，减轻了请求节 点的负担。 本文的意义在于通过对非结构化p 2 p 环境下信息检索机制的改进，可以减少网络传 输中的信息量，缩小检索的覆盖范围，实现较小代价下的检索成功率。希望能为p 2 p 信 息检索研究提供一些有益的借鉴。 全文共分为四章，文章结构及各章主要内容组织如下： 第一章：本文的绪论。本章介绍了p 2 p 网络的概念、特点、应用以及p 2 p 技术面临 的问题，并对本文所作的研究工作进行了概要的介绍。 第二章：介绍了目前常见的p 2 p 信息检索系统以及它们的特点并研究与分析了非结 构化p 2 p 环境下的信息检索机制，比较了它们各自的优缺点。 第三章：针对目前信息检索机制中存在的不足，给出了一种有效的信息检索机制， 并用实验证明了它的有效性。 第四章：为了减轻请求节点的负担，对信息检索结构进行了优化处理，并通过实验 对这种机制进行了模拟，对结果进行了分析。 最后是本文的研究总结和展望。本章主要是针对前面章节的研究工作给出一个总 结，同时给出了需要进一步研究的方面。 一9 基于路由信息表的p 2 p 信息检索机制研究 2 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 网络模型加以介绍，并描述四种p 2 p 网络模型中 的一些典型系统，重点描述它们所采用的搜索机制以及现有机制存在的不足。 2 1 集中式p 2 p 网络 集中式p 2 p 网络是基于一台或多台中央索引服务器的，中央索引服务器负责协调或 调度单独的注册节点上的资源。一般地，中央服务器维持着p 2 p 网络中节点的资源的中 央目录，并协调节点间的交互。有时候中央服务器也作为发配者分配任务给合适的节点。 中央服务器仅提供目录服务，系统的关键功能( 如文件下载或分布式计算) 则由分布 的单独的节点完成。因此，这类系统不是纯p 2 p 系统，而是混合的p 2 p 系统。n a p s t e r ， s e t i h o m e 和b i t t o r r e n t 0 都是典型的集中式p 2 p 网络。 集中式拓扑的一个重要的优点是简单。因为资源发现可以由中央目录来实现，所以 它非常灵活和高效。尽管如此集中式拓扑可能会发生单点失效、网络热点、诉讼等其他 问题。这很容易导致技术失效或成为恶意攻击的目标，如果服务器因为某些原因失效， 则p 2 p 网络可能全面崩溃。 下面介绍典型的集中式p 2 p 网络的代表n a p s t e r 。 1 9 9 9 年1 月，美国东北大学的肖恩范宁设计了n a p s t e r 的第一版本，用于朋友之 间的r a p 3 文件的共享。1 9 9 9 年5 月，n a p s t e r 公司成立。在以后相当短的时期里，n a p s t e r 获得了巨大的成功，为数百万的终端用户建立了以交换音乐文件为目的的文件共享网 络。至2 0 0 0 年1 月，n a p s t e r 用户达到1 0 0 万；同年1 1 月，n a p s t e r 用户已经超过了2 3 0 0 万；至2 0 0 1 年2 月，n a p s t e r 用户增长一倍多，达到了5 0 0 0 万。 n a p s t e r 工作方式不同于客户机服务器模式，它没有将音乐文件存储在服务器上， 而是由一台中央服务器存放音乐文件的索引信息。用户在中央服务器上注册自己提供共 享的文件信息及本节点的位置信息等。需要音乐文件的用户首先到中央服务器上进行信 息查找，若系统中有节点共享了所请求的文件，则可根据中央服务器上提供的信息直接 到拥有文件的节点去下载，连接和下载过程中不需要中央服务器介入，如图2 1 所示， 这就是典型的集中式的p 2 p 系统。 大连理工大学硕士学位论文 + 一一 图2 1n a p s t e r 的搜索模型 f i g 2 1 s e a r c h i n gi nn a l 镕t e r 这个架构的问题是当数据量( 索引量) 非常大时，服务器的存储能力和运算能力会难 以满足需求，查询响应时间会比较长。这一问题当然可以通过提升服务器的性能来解决， 但是代价在所难免。由于其用户增长迅猛，系统也面临扩展性的问题。 随着n a p s t e r 的成功，其他的p 2 p 文件共享系统开始出现了，如g n u t e l l a ，f r e e n e t i “j 等。加州大学伯克利分校的研究人员开发了s e t i h o m e 项目，使用一个屏保程序占用 大约1 0 0 万台c p u 的空闲时间，分析寻求外太空生命过程中射电望远镜所产生的数据。 2 2 非结构化p 2 p 网络 在非结构化p 2 p 网络中，没有中央目录。当一个新的节点加入到网络中时，它自由 地连接其他节点( 如随机选择某些节点作为邻居) 。如果节点要发布某些资源，通常是它 局部地存储这些资源。分散的非结构化拓扑非常适合由高度自治的节点组成的环境，来 自许多不同组织的用户互相之间共享资源，陌生人也不愿意为其他人提供更多附加的服 务。c - n u t e l l a 、f r e e n e t 、m o j on a t i o n 和n u r e c l g r i d 是典型的分散的非结构化p 2 p 网络。 非结构化p 2 p 网络因其简单和可用性，在互联网上广泛配置，并占据主导地位。如 果发生节点或者网络失效，这类系统容错性好。当随机失效经常发生时，幂律属性能解 释g n u t e l l a 网络的稳定的和可恢复的结构。非结构化p 2 p 网络适合节点的动态性，也支 持r i c h 搜索，如规则表达的关键字搜索和范围搜索( r a n g es e a r c h ) 等。 但是非结构化p 2 p 网络只能提供资源发现的不可靠的保证。某些搜索会失败，即使 请求的资源事实上是存在的，搜索效率也不能保证。在这样的网络中缺乏有效的搜索机 制，只能采用泛洪或类似泛洪的盲目搜索方式，导致在网络中产生过度的流量，同样影 基于路由信息表的i 2 1 信息检索机f ! 研究 响了系统的可扩展性，因此目前这些搜索技术通常是效率低的。下面介绍两个非结构化 p 2 p 网络模型的代表。 ( 1 ) 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 ”( g n u t e l l a - l i k e ) 的非结构化p 2 p 网络系统。g n u t e l l a 的协议规范在文献【1 2 】中有详细的描述。简言之，g n u t e l l a 是一个用于文档共享的p 2 p 网络系统，它通过将搜索请求同时转发给与自己连接的所有邻居节点进行文档的搜索 ( 如图2 2 所示) 。收到搜索请求的节点在本地进行查找，若找到所请求文件则沿着搜索 路径反向返回搜索成功的信息，把本节点的相关信息如口地址、端口等发回。请求者 收到这些信息后就可以与目的节点建立连接下载文件。若在当前节点未找到所需文件则 把请求进一步转发到与当前节点有连接的所有节点。消息可转发的次数受到刀z 参数的 限制，以此来避免过多的网络流量。 - - - 一 图2 26 n u t e l l a 的泛洪搜索模型 f i g 2 2f l o o d i n gs e a r c hm o d e li ng n u t e n a 对于大量分布在系统中的热门文档，g n u t e l l a 的工作方式比较有效。但对于分布在 系统中少量节点上的稀有文档，g n u t e l l a 只能通过设置较大的t t l 值才能有效的找到， 但这又会产生大量的网络流量。r i t t e r 通过对g n u t e l l a 的搜索协议进行分析发现，对于 一个包含1 8 个字节的搜索请求，如果将它同时转发给8 个邻居节点并且将力见也设为 8 ，那么仅仅文档的定位就将产生约1 2 g 字节的总流量。 为了提高g n u t e l l a 的可扩展性，人们纷纷提出了各种改进的g n u t e l l a 协议。m o h r 提出了对g n u t e l l a 协议进行扩展，除了原有的关键字搜索之外，增加了通过文档内容哈 大连理工大学硕士学位论文 希值进行搜索的方式，可以减少系统中有着不同名字的相同文档对搜索性能的影响。 t h a d a n i 提出在g n u t e l l a 的搜索请求中同时包含元数据和关键字可以提高搜索的精度。 r o h r s 提出通过在相邻节点之间交换各自保存文档的关键字的方案来降低搜索的盲目 性，提高g n u t d l a 的可扩展性。 l v 等在文献【1 3 】中提出通过利用g n u t e l l a 网络中的异质性，限制发往带宽较小节点 的搜索请求数量，同时增加发往带宽较大节点的搜索请求数量来提高c m u t e l l a 的可扩展 性。s r i p a n i d k u l c h a i 通过研究g n u t e l l a 中搜索字符串的分布规律，发现它们遵循z i p f 分 布，进而提出并通过实验验证，在系统节点中缓存那些最常被搜索的查询结果可以大大 降低网络上由泛洪引发的流量，提高系统的可扩展性。此外，s i n g l a 等还提出了u l t r a p e e r s 的改进方案，该方案选择g n u t o l l a 网络中有着较高带宽和计算能力的节点担当超级节点 的角色。关于提高g n u t c l l a 可扩展性的最新进展来自文献 1 4 1 ，c h a w a t h e 等通过对 g n u t e l l a 的设计增加了流量控制、动态拓扑调整、以及用随机步搜索替代泛洪搜索等改 进提出了一种新的非结构化p 2 p 网络g i a ，并验证了它相对于g - n u t e l l a 三至五个数量级 系统容量的提高。 l v 等在文献【1 5 】中通过模拟实验验证了非结构化p 2 p