（计算机软件与理论专业论文）基于p2p网络的搜索算法的研究.pdf

摘要 摘要 随着i i l t e m e t 的发展和用户的不断增多，对等网络作为一种新的网络应用模式受到 了国际上广泛的关注，越来越多的专家、学者投身到对等网络的研究和探讨当中，取得 了一系列的研究成果，但是大多研究成果都集中在有结构对等网络方面，对无结构对等 网络的研究还很少。根据p e e r - t o p e e rw o 艏n g 研o u pc o m m i t t e e 的定义，p 2 p 在商业上 的应用主要是文件共享、边界服务、分布式计算，但文件共享是目前最重要的一个应用。 g n m e l l a 网络模型被认为是最纯粹的p 2 p 系统的代表，但是g n u t e l l a 网络的主要问题是 使用“洪泛”方式搜索网络节点以及共享信息，随着网络规模的增长，搜索消息的比率以 及每一条消息产生的潜在流量也在大幅增长。 为了避免由洪泛搜索引起的大量网络流量问题，人们提出了很多基于统计的搜索方 法，其思想是节点根据某些统计信息和启发式算法，选择部分邻居节点进行查询的转发， 而不是像洪泛机制那样将查询发送到所有的邻居节点。然而这种方法只对部分节点进行 资源查找，忽略了大量有用的节点。本文针对以上问题，借鉴网络路由的思想，提出了 路由表查找法。使用路由表指示查找的方向，从而保证各节点存储路由表的空间大小与 其邻居节点数量成正比，而不是与共享文件的多少成正比，减少了网络中的数据流量。 采用了动态路由的方法来更新网络的变化存储到路由表中，为动态路由提供信息。 关键字：对等网络渤u t e l l a 洪泛搜索路由表查找法 ab s t r a c t a l o n gw i t ht h ed e v e l o p m e n to ft h ei n t e r n e ta n di t si n c r e a s i n gu s e rn u m b e r , p e e r - t o - p e e r ( p 2 p ) n e t w o r ki sa t t r a c t i n gm o r ea n dm o r ea t t e n t i o n i nt h ew o r l d 嬲an e wn e t w o r k a p p l i c a t i o nm o d e a ni n c r e a s i n gn u m b e ro fs p e c i a l i s t sh a v ee m e r g e di n t ot h es t u d yo fi ta n d h a v eg o tm a n yc o n t r i b u t i o n s h o w e v e r il,ther e s e a r c ho nu n s t r u c t u r e dp 2 pn e t w o r kss t i lf e w w h i l em o s to ft h ea t t e n t i o nw a sf o c u s e do ns t r u c t u r e dp 2 pn e t w o r k a c c o r d i n gt ot 1 1 e d e f i n i t i o no fp e e r - t o - p e e rw o r k i n gg r o u pc o m m i t t e e ，p 2 pc a nb eu s e di nt h ef i l es h a r i n g ， d i s t r i b u t e dc o m p u f i n ga n ds oo n g n u t e l l an e t w o r k sm o d e l i st h er e p r e s e n t a t i v eo fp u r ep 2 p s y s t e m s b u tt h ep e e r sa n di t ss h a r e df i l e sa r es e a r c h e da n df o u n db yf l o o d i n gi ng n u t e l l a w h e nn e w p e e r sj o i n i n gt h ep 2 pn e t , t h en u m b e ro fs e a r c h i n gm e s s a g e sa sw e l la st h el a t e n c y f l u xg e n e r a t e db ye v e r ym e s s a g ei si n c r e a s i n g t oa v o i dal a r g ev o l u m eo fu n n e c e s s a r yn e t w o r kt r a f f i ci n c u r r e db yt h ef l o o d i n g b a s e d s e a r c h ，m a n yi m p r o v e ds t a f f s t i c s - b a s e ds e a r c hm e c h a n i s m sh a v eb e e np r o p o s e d i n s t e a do f f l o o d i n gt oa l li m m e d i a t eo v e r l a yn e i g h b o r s ap e e rs e l e c t so n l yas u b s e to fi t sn e i g h b o r st o q u e r yb a s e do ns o m es t a t i s t i c si n f o r m a t i o na n dh e u r i s t i ca l g o r i t h i n s n e v e r t h e l e s s t h e s e s e a r c hm e c h a n i s m so n l yf i n ds o m es p e c i a lp e e r sa n ds e a r c hf i l e si nt h o s ep e e r ss ot h a tm a n y a v a i l a b l ep e e r sa r ei g n o r e d t h et h e s i sr e s e a r c h e st h o s ep o i n t sa n di m p o r t st h ed y n a m i cr o u t e i d e a , a n du s e sm e t h o d st oi n i t i a t i v e l yg e tt h en e t w o r kc h a n g e sa n ds t o r et h o s ei nt h er o u t e t a b l e b yu s i n gr o u t et a b l e ，t h ei n d e xs i z ei sp r o p o r t i o n a lt ot h en u m b e ro fn e i g h b o r s ，r a t h e r t h a nt ot h en u m b e ro fd o c u m e n t s k e yw o r d s ：p e e r - t o - p e e rn e t w o r k , g n u t e l l a , f l o o d i n g , s e a r c h ，r o u t et a b l es e a r c h i n g m e t h o d 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得江南大学或其它教育机构的学位或证书而使用过的材料 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意 签 名：氡遣密日 y i 一 期：渺彦- 2 - , v 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规 定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致 保密的学位论文在解密后也遵守此规定 签名： 导师签名： 期：伽、厂 第一章绪论 第一章绪论 1 1 研究背景 随着i n t e r n e t 的广泛普及，网络带宽的大幅增加和个人计算机数量的不断增多，对 等网络【1 】日益成为研究和应用的一个热点【2 。l 。 在传统的以服务器为中心的网络中，进行资源搜索存在着很多的问题f 4 】：( 1 ) 服务 器必须有强大的计算能力和完善的配套设施，并要保持长时间的在线状态；( 2 ) 服务 器中必有保存海量资源信息，以提供给大量的用户使用。但由于多方面的限制使得它的 资源信息远不如i n t e r a c t 所拥有的丰富；( 3 ) 服务器维护工作极其庞大；( 4 ) 服务器 的负载是有一定量的，随着访问服务器的用户数量的不断增加，网络会越来越慢甚至于 有可能形成网络的单点瓶颈【硒】。 对等网络中没有了服务器的概念，在这种网络中，所有节点都是对等的( 称为对等 点) ，各节点具有相同的责任和能力，并协同完成任务。每个节点既可以是服务者的提 供者，也可以是服务的请求者同。对等点之间逻辑上直接互连，共享信息资源、处理器 资源、存储资源甚至高速缓存资源，无须依赖集中式服务器就可以完成。所有节点都不 需要固定d 地址，不需要保持长时间的在线，用户可以极大限度地享受网络所带来的 便利。总之，对等网络很大程度上提高了整个网络资源的利用率，同时为用户提供了更 加自然、直接的交流方式，从而提高了效率。 正因为对等网络具有非集中控制、自组织、自适应和良好的可扩展性等优点，使得 很多研究机构和商业公司开始关注对等网络的研究，其中包括m i c r o s o f t 、i n t e l 、s u n 和 h p 等一些极具影响力的大公司，并由i n t e l 发起成立了对等网络工作组，以推动对等网 络进一步发展。s u n 公司主导的j x t a 8 】工程也是对等网络研究领域的一个重要组成部 分。b e r k e l e y ，m i t 等国外著名科研机构也成立了各自的研究小组进行相关研究，但尚 未有重要突破性的成果报道。 目前，基于对等网络的资源搜索研究已经取得了一些成果，其代表一- n a p s t e r | 引的 惊人成功，就展现了对等网络在资源共享领域中的巨大潜力。但是，随着网络的进一步 普及和发展，愈来愈多的计算机将加入对等网络，从而扩大对等网络的规模。而网络规 模的扩大和节点的多样性将使得对等网络的性质变得更为复杂，目前的搜索算法只能搜 索到很少一部分的资源，所以如何高效地查找到对等网络的共享资源将更加困难，因此 迫切要求有更优化的资源搜索算法出现。 1 2 国内外研究现状 近几年来，对等网络的发展非常迅速，很多大型公司、著名高校及研究机构都积极 参与到对等网络的研究及开发中，尤其是美国政府在这方面投入了大量的科研资金， m i c r o s o f t 在下一版本的w i n d o w s 中将通过家庭网络向导将多台计算机以对等网络的方 江南大学硕士学位论文 式连接起来【l 们。目前针对搜索共享资源主要研究方向有两个：一个是针对结构化对等网 络平台的研究，目的是将整个的i n t e r n e t 网作为对等网络的平台。主要是通过基于有结 构的对等网络的理论模型，设计数据的搜索及存储。二是针对非结构化对等网络搜索资 源问题的研究。由于在非结构化对等网络中，各节点以完全自组织的方式进行连接，网 络本身对资源的位置没有任何管理也不会向用户的查询提供任何保障，因此这就使得用 户发现和搜索共享资源问题变得相当困难。目前国内对非结构化对等网络的研究还有很 多的不足。本文重点研究了非结构化对等网络的资源搜索算法，在对各种已有算法分析 比较的基础之上，提出了基于动态路由的无结构对等网络搜索算法。 以下为结构化和非结构化对等网络的典型搜索算法及它们的研究现状： 第一，c h o r d n l 是结构化对等网络搜索算法的代表，c h o r d 是由m i t 提出的，它提 供一个适合于对等网络环境的分布式资源发现服务。该算法通过维护相邻节点的路由表 来进行信息资源的定位和查找。通过使用分布式h a s h 路由表技术使得查找指定对象只 需要维护l o g n 长度的路由表，但仍存在命名冲突，消息的传递效率不高及可扩展性差 的问题。现有的搜索算法还有t a p e s t r y 1 2 】，p a s t r y 1 3 1 和c a n 1 4 1 都属于有结构对等网络。 第二，g n u t e l l a ”。1 6 】是非结构化对等网络搜索算法的代表，g n u t e l l a 中采用了洪泛【l 】 式搜索策略。为了能够搜索到网络中的资源，每个节点都维护一些邻居节点的信息，以 便通过广播形式将查询信息发送出去，并利用消息生命期( m ) 来控制查询的规模。 这种方法虽然可以有效地搜索到需要的信息，但是却会在网络中产生大量的数据流量， 其中包括了大量的数据冗余。研究表明：大多数的查询结果是由网络中少量的节点提供 的【1 7 4 引。在此基础上，b e v e r l yy a n g 和h e c t o rg a r c i a m o l i n a 提出了迭代深入方法、广度 优先搜索1 1 7 】；黄道颖等研究了可选择的查询分配方法，使用多路平等查询机制进行查询 【1 8 1 ；v a n ak a l o g e r a k i 等提出了一个智能的搜索机制【1 9 】；e c o h e n 等提出预先复制其他节 点的共享文件，在网络中形成高度的冗余，提高查询效果的方法【2 l 】；b y a n g 等研究了 将智能化选择网络节点和提高节点冗余这两种机制结合起来的方法1 2 0 l ；l a d a m i c 等和 a c r e s p o 等研究了网络节点建立索引的方法1 2 2 氆】；l a d a m i c 等和黄道颖等利用网络的 幂规律和小群体的特点提高查询性能的方法【2 2 1 2 4 - 2 s 1 。 1 3 问题的提出 在非结构化的p 2 p 系统中，文件的放置( p l a c e m e n t ) 是随机的，与网络的拓扑没有 什么联系。当源节点要请求一个对象时，就发送查询到它的邻居节点。如果收到查询的 节点能够提供请求的对象，就会沿着查询的路径返回一个响应消息给源节点。如果收到 查询的节点没有该对象，就会转发查询给它的邻居。现在最流行的查询操作是将查询盲 洪泛( b l i n d - f l o o d i n g ) 到网络中，如g n u t e l l a ，k a z a a ( 在超级节点间) 就是采用这种 方法进行查询的。查询消息被一再地广播和转播，直到满足某些标准。这样能够保证查 询在短时间内可以洪泛到尽可能多的节点。但是洪泛机制会引起大量的网络流量，而且 很大部分是不必要的【2 6 j 。文献l z 通过对三个最流行的p 2 p 系统( f a s t t r a c k ，g n u t e l l a 和 2 第一章绪论 d i r e c tc o n n e c t ) 进行测量，得出了p 2 p 流量已经占据互联网流量的最大比例的结论。效 率低的洪泛搜索技术降低了非结构化p 2 p 网络的可扩展性。 为了避免由洪泛搜索引起的大量的不必要的流量问题，人们为改善非结构化p 2 p 系 统的搜索算法做了很多努力。一个典型的途径是采用统计的方法，即节点基于某些统计 信息和启发式算法，来选择它的部分邻居节点进行查询的转发，以此代替洪泛所有的邻 居节点。这种方法虽然可以显著地减少流量，但同时也忽略了网络中大量有效的节点， 减小了查询的覆盖范围，所以查询可能要经过更长的路径才能找到对象，或者是根本就 得不到满足，即使该对象确实存在于网络当中。另一个方法，如本地索引法，为节点建 立的索引大小与共享文件的大小成正比，直接导致了索引空间过大。本文针对这些问题， 根据g n u t e l l a 协议的特点，结合了t c p i p 中动态路由的思想，对现有的搜索方法进行 了改进。 1 4 论文结构 本文由5 章组成，各章的主要内容安排如下： 第l 章为绪论，分别介绍了课题研究的背景，对等网络国内外的研究现状，在最后 介绍了本文的章节安排。 第2 章是p 2 p 网络概述。作为技术论述了p 2 p 的技术起源、定义、特点及应用，并 将p 2 p 网络与传统的c s 网络进行了比较分析。 第3 章是p 2 p 系统中资源的搜索算法。首先介绍了p 2 p 网络的特性，并介绍了目前 三类系统中已有的搜索方法。对现有的几种典型的基于g n u t e l l a 网络的资源查找的机制 按照资源查找方式不同，分类进行了论述和分析总结。 第4 章是改进的p 2 p 资源搜索方法。本章是本文的核心，根据网络路由的思想，在 每个对等节点上建立路由表，将网络中的特征点作为路由表的默认值。并采用了两种路 由表法动态获取网络中的变化。并对试验的评价标准进行了分析，提出了评价标准，对 两种路由表法进行了试验，最后进行了分析比较试验结果得出结论。 第5 章为总结与展望。在这一章里，主要是对本文进行了回顾总结，并对以后的工 作和方向进行了展望。 3 江南大学硕士学位论文 2 1 p 2 p 技术的由来 第二章p 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 t 2 8 l 研究计划。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 i 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 技术及其应用领域的研究。 2 2p 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 具有以下特点： 1 ) 分散化( d e c e n t r a l i z a t i o n ) 网络中资源和服务分散在所有节点上，信息的传输和服务的实现都直接在节点之间 进行，可以无需中间环节和服务器的介入，避免了可能的瓶颈。即使是在混合p 2 p 中， 虽然在查找资源、定位服务或安全检验等环节需要集中式服务器的参与，但主要的信息 4 第二章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 r a c t 隐私问题主要采用中继转发技术，从而将 通信的参与者隐藏在众多的网络实体之中。在传统的一些匿名通信系统中，实现这一机 制依赖于某些中继服务器节点。而在p 2 p 中，所有参与者都可以提供中继转发的功能， 因而大大提高了匿名通讯的灵活性和可靠性，能够为用户提供更好地隐私保护。 5 )高性能 性能优势是p 2 p 被广泛关注的一个重要原因。随着硬件技术地发展，个人计算机的 计算和存储能力以及网络带宽等性能依照摩尔定理高速增长。而在目前的互联网上，这 些普通用户拥有的节点只是以客户机的方式连接到网络中，仅仅作为信息和服务的消费 者。采用p 2 p 架构可以有效地利用互联网中散布的大量普通节点，将计算任务或存储资 料分布到所有节点上。利用其中闲置的计算能力或存储空间，达到高性能计算和海量存 储的目的。 5 江南大学硕士学位论文 2 3 p 2 p 模式与传统模式的比较 c l i c a t c l i e n tp c 图1 1c s 模式的网络结构图1 2p 2 p 模式的网络结构 f i g 1 1c sm o d e l n e t w o r k f i g 1 2p 2 pm o d e ln e t w o r k 传统的c s 网络模式，服务器与客户机扮演着不同的角色，每个客户机都连接到服 务器上，服务器为客户机提供资源，客户机处于网络的边缘( 如图1 1 所示) 。而p 2 p 模式中，每个机器同时扮演着服务器和客户机的角色，在网络中他们都具有同等的地位 ( 如图1 2 所示) 。 与传统的c s 模式相比p 2 p 模式有明显的优点： 1 ) 资源利用率高。这也是p 2 p 最主要的优点。 2 ) 随着节点的增多网络会越稳定，不存在瓶颈问题。 3 ) 信息在对等节点间直接交换，高速，降低中转成本。 4 ) 基于内容的寻址方式处于一个更高的语义层。 当然p 2 p 也有许多不足之处。首先p 2 p 缺乏管理机制，不像在c s 模式中只需要在 中心点进行管理。其次p 2 p 网络中数据的安全性难以保证。另外还存在吞噬网络带宽问 题，版权问题。还有就是目前还没有制定出一致的p 2 p 标准，这对p 2 p 技术进一步发展 也是一个障碍。 2 4p 2 p 技术的应用 p 2 p 技术有着广泛的应用前景，目前主要应用在以下方面： 1 ) 文件共享 p 2 p 技术使得任意两台相连的计算机间共享文档、多媒体和其他文件成为可能。 n a p s t e r 和g n u t e l l a 就是将p 2 p 文件共享技术投入应用的最好例子。还有电驴、b t 等比 较流行的文件下载工具。 2 ) 分布式计算 就是将原来需要超型计算机来计算的大型任务进行分块，并通过系统控制中心地调 度软件进行调度和管理，分发给普通计算机来执行具体运算操作，完成后返回给控制中 心。自1 9 9 9 年起，美国柏克利大学的s e t i h o m e 研究计划就一直在使用p 2 p 计算方 6 第二章p 2 p 网络综述 法来分析星际间无线电信号，也正是s e t i h o m e 计划推动了最近的p 2 p 技术热潮。 3 ) 协作系统 它是另一种类型的p 2 p 网络：一群一起工作的用户相互之间共享着不同的因特网资 源，但他们通过协同工作完成一项共同任务。和文件共享不同，协作系统中的一个用户 可在同一时刻将个信息多点传送到若干个用户。美国l o t u s 公司创办的g r o o v e n e t w o r k 【2 9 1 就是最为著名的p 2 p 协作系统应用研究组织之一。它是运用中继服务器来完 成p 2 p 多点传送。 4 ) 电子商务 基于p 2 p 技术的直接性和易扩展性，该模式很适用于用户之间的商品交换。目前主 要可用于金融服务、电子商务集市、广告行销、口电话、购物行为分析等方面。 5 ) 以p 2 p 为基础的深度搜索引擎 p 2 p 技术使用户能够尝试搜索文档，而且这种搜索无需通过w e b 服务器中转，也可 以不受信息文档格式和宿主设备的限制，可达到传统目录式搜索引擎( 只能搜索到 2 0 一3 0 的网络资源) 无可比拟的深度。 除了以上几种应用外，还有一些无法预见或无法定论归类的应用模式。现在人们对 p 2 p 的认识还很不完整，随着研究的深入，p 2 p 技术会在更广泛的领域内得到应用。 2 5 本章小结 本章对近年来研究热点p 2 p 网络进行了介绍，介绍了它的技术起源、定义、特点及 p 2 p 的应用。p 2 p 网络中把每个节点都平等看待，节点既充当服务器角色又充当客户端 角色，这是它的技术核心思想，也是它与传统的c s 模式网络的主要区别。采用这种思 想，有效地聚合了网络中巨大的硬件和软件资源，使网络中每个节点都得到了充分地利 用。这正是p 2 p 网络所具有的优势，也因此引起了人们的极大的研究兴趣。p 2 p 网络的 提出，是对传统网络的一种挑战，有人预测它将成为下一代新的网络模式。以下我们正 是基于此进行研究。 7 江南大学硕士学位论文 第三章p 2 p 系统中资源的搜索算法 检索技术，在信息爆炸的今天，已不可或缺。计算机检索，简言之，就是通过计算 机进行分析查检寻找数据信息。 检索技术产生于2 0 世纪5 0 年代，进行2 1 世纪，随着计算机技术的不断进步、信 息量的巨大膨胀，检索技术飞速发展。传统检索技术，可以提高人工选择信息的效率， 节省大量时间。现代检索技术，除了进一步提高人工检索效率，更朝着智能化、海量化 等各方面全方位发展。在传统检索技术基础上发展起来的智能检索，如信息挖掘、自动 标记、自动分类、摘要、聚类检索等技术对信息进行自动而非人工挖掘，进一步解放了 人力，促进了人类工作方式的更新变革。 目前信息检索技术正向两个方向发展：一是传统信息检索向全文文本、多媒休、多 载体、多原理等新型信息检索的发展，在深度上提高管理和组织信息的能力，如探索自 动抽词、自动索引、自动检索、自动文摘、自动分类、自动翻译等；二是信息资源的网 络化和分布化，面向i n t e m e t 中浩瀚无垠的资源，在广度上提高信息管理和组织能力。 信息检索技术目前主要应用于两大领域，一种是因特网搜索引擎，g o o g l e 是这类搜索引 擎的典型；另一种是企业级搜索引擎。 p 2 p 的搜索是在一个分布式的网络中进行信息的查找与检索，由于p 2 p 系统的一些 自身的特性，使得p 2 p 搜索相对于传统的信息检索有许多不同之处，同时也使得p 2 p 搜索面临许多挑战。 3 1p 2 p 网络搜索的特性 p 2 p 网络是基于网络基础设施之上的一个逻辑层，其特性为其搜索算法的设计提出 了新的问题和挑战，主要有以下几点： 1 ) 动态变化的网络拓扑结构 动态变化的网络拓扑结构是p 2 p 网络的一个显著特点。p 2 p 网络的精髓是给予用户 极大的自由。它弱化了集中服务器的功能，重视网络中所有个体的作用，每个对等点随 时都可以进入或退出网络，它们仅仅关注于自己的行为。在它们短暂的活动期间，尝试 完成自己的任务，任务一旦完成，它们可能就会退出。p 2 p 网络的自组织特性( a d h o e ) 使得很难预测和定位网络中的节点资源，传统的口层路由算法已经不适合p 2 p 路由的 要求。这使得在p 2 p 系统中精确地进行资源的查找和搜索面临着巨大的挑战。 2 ) 按需请求的特性 文件共享系统的需要直接引发了p 2 p 网络技术热潮，同时也成为p 2 p 系统中最主要 的应用之一。p 2 p 技术的文件共享系统是基于内容寻址的方式，用户只有在需要的时候 系统才进行文件的查找，很少考虑网络带宽、系统负载和历史查询记录。大多数的传统 口层路由网络中的主机是通过无周期性交换路由信息，得到所有其它主机的路由。但彼 8 第三章p 2 p 系统中资源的搜索算法 此交换的路由信息可能并不需要，这些无用的信息浪费了网络资源。使得p 2 p 网络可能 因过多的消息传播而造成网络的拥塞或系统的不可扩展。 3 ) 无集中控制的系统 对等节点之间作为对等实体连接，而不是借助于任何已建立的网络基础设施或集中 管理。这样的系统结构把网络的控制功能分散配置到各个对等节点中，网络的建立和调 整是通过各个节点的有机配合实现的，这使路由选择已经从本质上脱离了传统网络的集 中控制机制。没有一个节点具有全局的拓扑信息，每个节点只根据本身已知的一部分拓 扑信息进行路由和信息地转发。 4 ) 应用层上的路由 无论是i n t e r n e t 早期的简单五类地址分类，还是为了降低路由规模增长速度的无类 域间路由地址结构以及i p v 6 地址，从本质上讲，整个p 地址空间仍然是一种层次结构， 节点利用最长地址的前缀匹配自救进行路由查找。但p 2 p 网络路由是基于应用层之上， 并不一定采用类似d 地址的层次结构路由，一般情况下，p 2 p 网络运用自己的节点标示 策略实现系统的路由，如c h o r d 、t a p e s t r y 等。或者采用一种洪泛的方式在整个系统中 进行漫搜索。不管采用何种策略其一般都没有考虑系统底层的网络拓扑。 5 ) 双向链路传输方式 p 2 p 网络中每个节点既是客户机，同时又是服务器，系统的流量表现为双向传输特 性，与诸如w e b 之类的现在应用不同，这些应用的特点是下行数据传输量远远大于上 行数据传输量。t c p 传输运用确认报文进行数据的差错恢复，研究表明在双向传输情况 下会产生确认报文丢失，从而引起系统吞吐量降低，因此在路由设计过程中必须考虑路 由控制信息报文的数量，避免带宽浪费和性能降低。 由此可以看出，良好的p 2 p 网络路由算法需要满足以下基本要求：不依赖集中控制 的分布式实现，避免过量的报文信息；每个节点均与一定数量的节点保持邻接关系，以 进行路由地选择；节点之间通过多个节点传递消息来完成通信；任何两个节点的消息通 信的路由跳数( h o p s ) 尽量维持在一个的数量级，避免传播路径过长；一定数量节点的 失效不会影响系统的可用性；各个节点都能够维持一致的网络拓扑信息；节点可以很容 易( 传递消息的数量少) 地加入和离开系统，并满足一定的可扩展性；网络在分割后能 提供良好的恢复策略使系统从错误中恢复来提高系统的健壮性。由此，p 2 p 网络路由算 法应该考虑节点的命名、定位、加入、离开以及节点之间的邻接关系，系统容错性等。 3 2 三类系统目前的资源搜索策略 p 2 p 网络地出现为分布式计算技术甚至整个互联网的发展提供新的契机，人们在不 同的领域应用该技术并从不同的角度对其进行研究。如何能使p 2 p 系统具有更好的性 能，并使p 2 p 技术在更广泛的领域中得到大规模的应用，这是所有研究的目的。 p 2 p 网络由分布在不同区域的若干对等点组成，各对等点之间通过路由传递报文， 它的资源搜索同当前集中式系统有很大不同。系统中的资源数据分布在不同的节点上， 资源地发布和组织没有统一的模式。而且节点可以自由地加入和离开，使系统中的资源 9 江南大学硕士学位论文 对象也呈现出动态特性。为了提高效率和获得高可靠性，p 2 p 网络需要合理的查询技术， 充分利用对等点的分布式处理和数据的冗余来优化查询。p 2 p 网络资源搜索机制大都是 建立在网络逻辑拓扑结构特点基础上。目前应用的系统所采用的逻辑拓扑结构类型因为 不同的设计，具体的结构也不尽相同，这直接影响了系统中的消息路由机制，同时路由 的效率也影响了资源搜索机制。当用户提交了一个查询，消息报文如何在网络上传递和 复制，决定了系统查询请求以何种方式依次传递给资源发布者( p u b l i s h e r ) 以及查询消 息的通信代价。资源数据和索引结构的分布也和网络逻辑拓扑结构紧密相关，如非完全 分布的p 2 p 系统n a p s t e r 用服务器来建立中心索引来进行查询。基于d h t 技术的p 2 p 网络都采用一定的算法把文件与一定的节点连接起来，查找时根据文件和节点的关系进 行路由，这种方法保证了只要文件在网络中存在就可以找到。而完全分布的p 2 p 网络如 g n u t e l l a ，每个节点都存储自己的资源数据，请求的搜索在网络中使用洪泛机制进行。 显然网络拓扑结构的不同导致了不同的资源搜索模型。下面我们分别介绍目前已有的 p 2 p 系统的资源查找策略。 3 2 1 非完全分布式p 2 p 系统 非完全分布式p 2 p 网络又称为混合模式的p 2 p 系统，在这种模式中采用一个核心实 体专门提供服务，所有的节点都向核心实体提交请求信息进行查找，而不向其它节点提 出请求。对等节点通过核心实体来完成资源的定位通讯信息，但核心实体并不参与对等 节点之间的实际通信，它只负责把请求节点和目标节点联系起来，而真正的文件传送是 在源请求节点和目标节点之间直接进行的。该类p 2 p 网络的典型代表是n a p s t e r 。 n a p s t e r 是一个众所周知的p 2 p 系统。该系统是一个音乐文件交换系统，它由运行 客户端软件的注册用户和一个维护中心目录的服务器构成。其中服务器包含： ( 1 ) 所有网络上文件的源数据( 文件名，产生的时间等) 的索引。 ( 2 ) 注册用户的连接信息表( d 地址，连接速度等) 。 ( 3 ) 文件列表包含每个用户拥有的和在网络上共享的文件。 每个客户端在启动时，首先要在中心服务器上注册，也就是客户端先连接到中心服 务器上，然后给中心数据库发送一个它所维护的文件列表。当服务器从用户接收到一个 查询的时候，它在自己保存的索引表中查找相匹配的文件，如果找到就返回拥有这个文 件的用户列表。然后用户和拥有这个文件的实体建立直接的连接，并且下载文件。n a p s t e r 的中心数据库负责储存网络上可用的文件列表和这些可用文件的拥有者，实际的文件则 存储在客户端。n a p s t e r 是应用层，是基于点到点t c p 连接之上的c l i e n t s e r v e r 模式的协 议。它利用在节点之间发送消息来完成各种操作，其中n a p s t e r 消息的一般格式如下： 【l e n g t h t y p e 】 d a t a 】 其中： l e n g t h( 1 6 一b i t 整数) ： d a t a 】的长度( 用字节表示) t e( 1 6 b i t 整数) ：0 0 e r r o r ；0 1 - l o g i nr e q u e s t e d ；0 3 - 1 0 9 i na c c e p t e d ；0 5 a u t o u p g r a d e ；6 4 - n o t i f i c a t i o no fs h a r ef i l e ；6 6 r e m o v ef i l e ；c 8 - s e a r c hr e q u e s t ；c 9 s e a r c hr e s p o n s e ； 1 0 第三章p 2 p 系统中资源的搜索算法 2 0 3 一g e tr e q u e s t = 2 0 4 - d o w n l o a da c k ：2 5 8 - w h o i sq u e r y ；2 5 c w h o i sr e s u l t d a t a ：实际传送的数据 n a p s t e r 具体需要三个步骤来完成资源的定位： ( b ) ( a ) 妒妒 图3 i ( a ) 连接；( b ) 请求与响应； ( c ) 下载文件 f i s 3 1 ( a ) c o n n e c t i o n ；( b ) q u e r ya n dq u e r y h i t ；( c ) d o w n l o a d i n g 各节点使用p u s h 消息将自己的文件列表等信息上传到中心服务器，如图3 1 ( a ) ； 各节点上的用户向服务器提交查询消息( 如文件名，作者等) ，服务器返回相 关的查询结果，如图3 1 ( b ) ； 根据服务器返回来的消息选择目标节点进行文件下载，如图3 1 ( c ) 。 3 2 2 分布式结构化p 2 p 系统 分布式结构化p 2 p 系统没有中央目录服务器，但是结构化的。这里的结构指的是系 统对p 2 p 网络拓扑和文件放置都精确地加以控制，仔细地将文件索引分布在参与的节点 中。这种系统支持分布式哈希表( d i s t r i b u t e dh a s ht a b l e ，d h t ) i j o j 功能，如c h o r d ， p a s t r y ，t a p e s t r y ，k a d e m l i a 等。d h t 系统中，文件与k e y 相关联。k e y 为一定长度( 如 1 2 8 位) 的位串，通过哈希文件名而得；节点的标识符通过哈希口地址获得，并与k e y 具有相同的地址空间。每个节点为哈希桶，负责存储一定范围的k e y 。d h t 系统有一个 基本的操作l o o k u p ( k e y ) 。给定k e y ，l o o k u p ( k e y ) 返回存储k e y 的节点的p 地址。 该操作允许节点基于k e y 放置和获得文件，因而支持类似于哈希表的功能。查找文件时， 直接将查询消息逐步地路由到拥有所需文件的节点上。d h t 系统已经成为许多大规模 分布式系统的构建基础，如分布式文件系统、应用层组播和事件通知服务等。 这种拓扑的优点是易于扩展，查询效率高，支持稀少文件的查询；缺点是对节点的 不断加入和离开需要频繁地做些额外的工作，不能有效地支持多样化查询。 江南大学硕士学位论文 3 2 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 是一个完全分布的p 2 p 网络，使用i p 作为下层网络服务。g n u t e l l a 协议定 义了对等点之间工作于t c p 协议之上的应用层通讯协议，包括在对等点之间通讯描述 符集( 服务原语集) 和相应的通信规则集。本文所介绍的是g n u t e l l a 协议的0 4 版本1 2 5 1 ， 在这个版本中定义了对等机通过网络通讯的方式，它定义了包括通过对等机进行数据通 讯的描述符号集合内部的对等机相互的规则集。g n u t e l l a 通信协议主要包括四种类型的 消息，分别是p i n g 、p o n g 、q u e r y 、q u e r y h i t 和p u s h ，相关内容如表3 1 所示： 表3 1g n u t e l l a 协议通信表述符 t a b l e3 1g n u t e l l ap r o t o c o lm e s s a g ed e s c r i p t i o n 描述符描述 用于在c m u t e l l a 网络中主动发现对等机。一个收到p i n g 消息的对等机 p i n g 会向发送方响应一个或多个p o n g 消息 用于对p i n g 消息的响应。它包括一个相连的g n u t e l l a 对等机的地址和 p 0 n g 有关该节点能提供给网络共享的信息 搜索g n u t e l l a 分布式网络的主要机制，一个收到q u e r y 消息的对等机， q u e r y如果其