（计算机应用技术专业论文）gnutella网络中树结构搜索机制的研究.pdf

g n u t e a 网络中树结构搜索机制的研究 摘要 g n u t e l l a 网络是分布p 2 p 模式的典型代表，由于它具有完全分布式和高度动 态性的特点，可以有效消除单点瓶颈、节点快速定位以及获取有效信息，增强 了网络的鲁棒性。并且没有像结构化p 2 p 网络没有考虑到网络的实时性与动态 性而导致存在着高延迟、低效率的缺点。然而，由于g n u t e l l a 采用洪泛式( f 1 0 0 d i n 曲 搜索机制，容易在网络中产生以指数级增长的冗余消息，致使查询速度慢效率 低下，网络扩展性能不强。因此提高搜索效率，改进g n u t e l l a 网络搜索机制成为 主要研究目的之一。 本文以改进g n u t e l l a 的搜索机制作为论题。首先对洪泛式搜索机制进行展开 性探讨，详细分析此搜索机制的特征与不足。针对洪泛式搜索机制的不足，本 文提出了一种基于树结构的g n u t e u a t r e e 搜索树搜索机制。本机制的主要思想 是在搜索过程中动态的构造出搜索树，来减少消息的重复传送，达到提高网络 搜索效率、降低代价、减少冗余消息。根据这一思想，本文详细阐述了 g n u t e l l a t r e e 机制的存储方法和g n u t e l l a t r e e 搜索树的构造算法，并提出一种 g n u t e l l a t r e e 自适应算法( a d a p t i v eg n u t e l l a t r e ea l g o r i t h m ，简称a g t a ) ，旨 在控制节点的加入和退出对己构造的树的影响，以保证g n u t e l l a t r e e 搜索树的 鲁棒性。最后将通过仿真实验验证该搜索机制和控制算法的有效性，显示了在 搜索效率的提高，消息冗余量的减少和节点频繁流动造成网络动态变化的适应 方面都有显著的改进效果。 关键词：g n u t e | | a ，- 洪泛式搜索，g n u t e i i a t r e e ，a g t a g n u t e l l a 网络中树结构搜索机制的研究 a b s t r a c t g n u t e 儿al sar 印f e s e n t a t l v eo fd e c e n t r a l i z e dp 2 pn e t w o r k b e c a u s e0 fi t sc h a r a c t e r 0 fe t i r e l yd i s t r i b u t e da n dh i g h l yd y n a m i c ，j tc a ne f f c c t i v e l ya v o i di s o l a t i o nn o d e s b o t t l e n e c k ，i n t e l l i g e n t l yf j n d i n gp e e r s ，a c q u i r ev a l i di n f o m a t i o na n dm a k en e t w o r k m u c hm o r em b u s t a n dg n u t e l l ah a v e n ts u c hh i 曲d e l a ya i l dl o we f f i c i e n c y w e a k n e s sw h i c hc a u s e d b yt h es t r u c t u r e dp 2 pn e t w o r kf o rw i t h o u tc o n s i d e r i n g r e a l 一t i m e 锄dd y n a m i co ft h en e t w o r k w h i l en o o d j n gi su s e dt ob m a d c a s tq u e r y a c r o s sg n u t e l l an e t w o r k s ，i tg e n e r a t e se x p o e n t i a l l yi n c r c a s i n gr e d u n d a n tm e s s a g e s ， s ot h a ts e a r c h i n ge 佑d e n c yi sd e c r e a s e dr a p i d l y ，t h eg r o w t ha n ds c a l a b i l i t yo fp 2 p s y s t e mi sh i n d e r e d s o “i so n eo f t h em a l l l l ys t u d yo ng n u t e an e t w o r kt h a ti m p r o v i n g s e a r c he m c j e n c ya n dm e n d i n gt h es e a r c hm e c h a n i s mo fg n u t e l l an e 何o r k n i sp a p e r t a k e se f f j c j e n c yi m p r o v e m e n t0 fn o o d i n ga st o p i c ，t h e nm a k e sa n e x t e n s i b i l i t yd i s c u s s i o no ni t ，a n dm a i n l ya n a l y z e st h ec h a r a c t e r i s t i ca n dd e f i c i e n c yo f t h i sm e c h a n i s m ，a n di n t m d u c e si t ss t o r a g em e c h a n i s ma n daa l g o n t h mo fg n u t e l l a t r e e c o n s t m c t a t t e m p tt oe n h a n c et h es e a r c h i n ge f f i c i e n c y ，t or e d u c et h ec o s ta n dt h e r e d u n d a n c y ，an c wt e d l n i q u ec a l l e dg n u t e l l a - 7 1 1 ei sp r e s e n t e d t h ei d e ao ft h i s m e c h a n i s mi st h a tc o n s t m c td y n a m i c a l i ys e a r c h t r e ei nt h ec o u r s eo fs e a r c h i n g i n f o 皿a t i o n an e wa d a p t i v eg n u t e l l a - t r e ea l g o r i t h m ( a g t a ) i sg i v e n ，w h l c hi su s e d t oc o n t m l t h el o s s o fg n u t e 儿an e ts e a r c ha dn e i sj n s t a b l l i t yb f o u 曲1w i t hp e e re x l t i n go rj o j n i n g a n dm e a n w h i l e ，t h ee x p e r i m e n ts h o w st h a tg n u t e l l a t r e ea n da g l ai sa v a i l a b l e ， a n di tc o u l di n c r e a s en o o d i n ge f f i c i e n c y ，r e d u c er c d u n d a n tm e s s a g e s ，a n da d j u s ti t s e l f t ot h ed y n a m i cc h a n g eo fp 2 ps y s t e m c a u s i n gb yc o n s t a n tp e e r a 玎i v a l sa n d d e d a r t u r e s k e y w o r d s ：g n u t e l l a ，f l o o d i n g ，g n u t e l l a - t r e e ，a g t a 3 g n u i e l l a 网络中树结构搜索机制的研究 1 1 论文研究背景 第一章绪论 随着信息技术的高速发展，从而推动了计算模式不断地更新。从中央计算 模式、客户机服务器时代的c s 计算模式、电子商务时代的b ，s 网络计算模式， 到现在的s e r v e n t 计算模式，已经发生了巨大变化。 计算机模式的变化以螺旋方式发展。在计算机应用初期，中央计算模式占 据绝对主导地位，它的特点是维护简单，但弊端是终端用户对资源和数据几乎 没有控制权。随着p c 机和网络计算的广泛应用，c l i e n t s e r v e r 模式( 简称d s ) 受到用户的推崇，虽然它在把控制权交给最终用户的同时，仍然保持了对后台 数据和资源的集中控制与管理。但c 幅有部署繁琐、更新难度高等缺点。随着 商用计算的全球化、协作化、个性化，决定了必将采用全新的基于i n t e m e t 的 b r o w s e s e r v e r ( 简称b s ) 计算模式。通过b s 计算模式，企业能够实现全球化、 高效率的协作和个性化的服务。b s 的缺点主要是受制于h t m l 的限制，无法 像c s 那样使用丰富的效果来展示数掘，用户体验比较难以保证。另外，稳定 的客户端朋务器连接，也是必要条件，网络中断将是b s 无法运行。 在目前互联网分布式的环境下，传统的网络应用模式把资源集中在少效节 点的特性已日渐成为其处理数据访问的瓶颈，这就需要复杂的负载平衡和强大 的容错技术来保证数据访问的连续性与可靠性。如果在网络计算环境中，每台 计算机既可以作服务器，也可以作客户机，每台计算机通过相互协作，从而使 整个网络拥有超强的计算能力，这就是对等机模式。s e r v e n t r 对等机) 一词起源于 s e e r 和a i e n t ，由两词的并构组成，代表它既具有s e r v e r 的功能，又可扮演 c l i e n t 的角色。 p 2 p 网络( p e e r t o p e e r ，简称p 2 p ) 【2 j 是当日0s e r v e n t 模式中研究的热点技 术。n a p s t e r ，g n u t e l l a 等等p 2 p 产品的应用引起了人们对p 2 p 技术前所未有的 热切关注。p e e r t o p e e r ( p 2 p1 是种分布式网络，网络的参与者共享他们所拥有 的一部分硬件资源( 处理能力、存储能力、网络连接能力、打印机等) ，这些 共享资源需要由网络提供服务和内容，能破其它对等节点( p e c n 直接访问而无需 经过中间实体1 3 】o 在此网络中的参与者既足资源( 服务和内容) 提供者( s e e r ) ， 又是资源( 服务和内容) 获取者( c l i e n t ) 。它打破了传统的节点式信息服务模 式，消除了服务器和客户的区别，系统中每个节点都具有平等的地位，可直接 进行文件共亨与交换，共同分担负载，极大地提高了系统资源的利用率，满足 人们快速交换大容量数捷：的需求。 7 g n u i e l l a 网络中树结构搜索机制的研究 p e e r t o p e e r 在分布计算、协同工作、信息共享、文件交换、搜索引擎等领 域均有很好的应用前景。1 9 9 9 年的s e 耵 h o m e l 4 颂目便是一个以资源共享为 基础的协同计算的成功典范。该项目把分布于世界各地的2 0 0 万台个人电脑组 成计算机阵列，搜索射电天文望远镜信号中的外星文明迹象。同时，p 2 p 在电子 商务领域有光明的前景，i n t e r b i n d 公司日前将p 2 p 技术和b 2 b 的商务模式结合 起来，为b 2 b 商务公司开发p 2 p 网络和分布式计算软件，在这种商业经营模式 下，买主与卖主直接联系，能够有效地利用资源，并减少客户机朋艮务器网络所 必需的管理。p 2 p 技术的另一个优势是开发出强大的搜索工具，使用户能够深度 搜索文档，而且这种搜索无需通过w e b 服务器，也可以不受信息文档格式和宿 主设备的限制，可达到传统目录式搜索引擎( 只能搜索到2 0 _ 3 0 的网络资源) 无可比拟的深度( 理论上将包括网络上的所有丌放的信息资源) ，比如由d i 西t a l 公司开发的全新搜索引擎p a d a n g o 采用p 2 p 搜索理念来对互联网络进行全方位 的搜索将搜索引擎技术提升到一个新的层次。 p e e r t o p e e r 技术中的g n u t e l l a l 5 】模型是现在应用最广泛的纯p 2 p 【6 】非结构化 拓扑结构。近年来，由于g n u t c l l a 网络具有以下的优势，故基于g 眦t e l l a 通信协 议【7 】的g n u t c l l a 网络得以非常迅速的发展。 1 与其他文件共享的系统( 例如n a p s t e r ) 不同，g n u t e l l a 开放协议保证网络不 需要有很强的关联，允许即时改进提高。而且，任何人都可以开发g i l u t e l l a 兼容软件，事实上开发者已经互相竞争并且导致一个不断改进的g n u t e l l a 网 络的出现。结果是出现了一个经常改变和完善自身的文件共享环境。 2 任何人可以利用g n u t e l l a 网络非常容易的分享信息。一个人只需要把他希望 共享的文件放在硬盘的一个目录下，然后利用g n u t e l l a 网络共享出去。因为 g n u t c l l a 网络的灵活性和流行，用户可以自由地分享并且发现一系列大量的 资源。 3 g n u t c l l a 允许用户与其他g n u t e l l a 节点直接联系，不经过中间节点，或者巾 心，或者认证机构。 4 任何孤立的g n u t e l l a 节点失败后可以在网络上被迅速并且自动恢复。 1 2 国内研究现状 目前p 2 p 是一个较为热门的研究课题，国内也有部分相关的研究报告，但 是集中在结构化p 2 p 网络，如巴气n ，t a p e s t r y ，c h o r d ，p a s t r y 等的研究上面， 对非结构化g n u t e l l a 的研究并不多见。 在对g n u t e l l a 网络的研究方面，朱凌付出很多的努力，并取得了很大的成绩， g n u t e i l a 网络中树结构搜亲机制的研究 她的毕业论文基于g p a i h t r c e 的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 p a t h t r e e 【8 】搜索的理 论，为本文的研究提供了理论基础。 1 3 研究目标 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 网络的搜索机制进行研究，同样以提高g n u t e l l a 网络的搜索效率为目的 作了一些尝试，在g p a t h t r e e 搜索的基础上进行了改进，探求出一种快速搜索 机制，并提出了a g t a 算法，提高搜索机制的鲁棒性。并且在同时，通过一系 列的模拟实验，证明方法的有效性。 1 4 文章组织 本文的组织结构如下所示： 第一章绪论 首先介绍本文从事的研究工作的背景、意义和国内研究现状，然后介绍本文 的主要工作和组织结构。 第二章p 2 p 网络概述 首先介绍p 2 p 网络的发展历程、概念、技术特点和模式；然后介绍p 2 p 网 络的主要应用。 第三章g n u t e 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 网络的查询机制，分析其由于网络异构 延迟，消息控制机制和频繁的节点流动对搜索效率造成的各种影响， 第四章g n u i e l l a t r e e 搜索 提出通过建立g n u t e l l a t r e e 搜索树束优化g n u t e l l a 网络的搜索效率，介绍 g n u t e l l a t r e e 搜索的基本思想、实现步骤和存储方法，并提出了a g t a 算法柬 提高g n u t e l l a t r e e 搜索的鲁棒性。 第血市仿真实验与总结 通过实验对比g n u t e i l a t r e e 搜索机制和洪泛式搜索机制柬验证改进的网络 的查询机制有效。件。 、 第】带总结与展望 9 g n u t e l i a 网络中树结构搜索机制的研究 总结目前成果，进行展望，介绍要继续开展的工作及可能突破的技术。 1 5 创新点 当前，p 2 p 方面的研究大多集中在结构化p 2 p 网络【9 j 的一些算法分析上面， 对非结构化p 2 p 的研究还比较贫乏。本文以分布p 2 p 模式的典型代表非结 构化g n u t e l l a 为研究的主线。朱凌提出了g p a t h t r e e 搜索法来改进g n u t e l l a 网 络的传统搜索机制。本文在此方法的指导下，改进g p a t i l t r e e 搜索法，提出一 种基于树结构的g n u t e l l a - t i e e 搜索机制，给出了g n u t e l l a t r e e 搜索树的构造算 法和存储方法，并提出a g l l a 算法用于控制节点频繁流动造成对已构造的树的 影响，使g n u t e l l a 1 r e e 搜索机制具有鲁棒性。 1 0 g n u t e l l a 网络巾树绱构搜秦机制的研究 2 1p 2 p 网络的综述 第二章p 2 p 网络概述 p e e r t o p e e r ( p 2 p ) 是一种分布式网络，网络的参与者共享他们所拥有的一部 分硬件资源( 处理能力、存储能力、网络连接能力、打印机等) ，这些共享资 源需要由网络提供服务和内容，能被其它对等节点( p e e r ) 直接访问而无需经过中 间实体【3 l on a p s t e r 【1 0 l ，g n u t e l l a ，b i t t o 盯e n t 等p 2 p 产品的应用掀起了一阵对p 2 p 技术热切关注的高潮。 回顾互联网发展的历史，不难发现，它最基本的协议t c p ，i p 原先并没有客 户机和服务器的概念，所有的设备都是通讯的平等的一端。所以，p 2 p 其实是互 联网整体架构的基础，而一i 是什么新概念。早在十年前，所有的互联网上的系 统都同时扮演服务器和客户机两个角色。之后发展起来的一些在t c p i p 协议之 上的软件确实采用了客户机朋艮务器的架构：b r o w s e r 浏览器和w e b 服务器，邮 件客户端和邮件服务器，而在服务器之问仍然是处于对等联网的地位。p 2 p 把人 们重新带回到“平等而无中心化”的网络罩，将人们直接联系起柬，直接共享 直接交互，使网络上的一切沟通都变得简单而又容易。 将网络应用的核心从中央服务器向网络边缘的终端发备扩散就是p 2 p 技术 的核心思想。任何接连上网络的高性能计算机，p c 机，手机，甚至p d a 等等都 可以作为p 2 p 网络的终端设备，随时满足人们对数据交换存储和快速传输、高 性能计算等的迫切的需求。p 2 p 技术的主要特征是弱化服务器作用，甚至取消服 务器，使分确式系统q j 的各个节点逻辑对等，这种技术出现的f 1 的就是希望能 够充分利用网络中所蕴含的潜在资源。传统的c s 结构容易引发单点失效、性 能瓶颈和网络拥塞等问题，而p 2 p 技术则能很好地避免类似问题的发生，因为 在c s 结构中，网络对中央服务器的依赖程度柏当的高。与c s 模型不同，p 2 p 模型中每个节点既可以是服务( 或者资源) 的提供者，也可以是使j r i j 者，充其 量就是提供的服务( 或资源) 的类型不同。 2 2p 2 p 的应用研究 p 2 p 引导嘲络计算模式从集中式向分椰式偏移，也就是说网络应用的核心从 中央服务器向网络边缘的终端设备扩散，这使人们在i n t e m e t 上的共享行为破提 到了一个更高的层次，使人们以更主动深刻的方式参与到网络中去。因此p 2 p 的应用研究也集中伍共享、搜索上。在此方而，p 2 p 应用主要体现在以下几个力 面： g n u i e i l a 网络中树结构搜索机制的研究 2 2 1p 2 p 分布式存储 p 2 p 分布式存储系统是一个用于对等网络的数据存储系统，它可以提供高效 率的、鲁棒的和负载平衡的文件存取功能。这些研究包括：0 c c a n s t o r e ，f a r s i t e 等。其中，基于超级点结构的半分布式p 2 p 应用如硒z z a 【、b i t t o r r e n t 等也是 属于分布式存储的范畴，并且用户数量急剧增加。 2 2 2 对等计算 加入对等网络的节点除了可以共享存储能力之外，还可以共享c p u 处理能 力。目前已经有了一些基于对等网络的计算能力共享系统。比如s 即 h o m e 。 目前s e t i h o m e 采用的仍然是类似于n a p s t e r 的集中式目录策略。这种计算能 力共享系统可以用于进行基因数据库检索和密码破解等需要大规模计算能力的 应用。 2 2 3 搜索引擎 搜索引擎一直是被关注的热点，人们希望用户能够通过搜索引擎深度搜索 文档，无需通过w 曲服务器，也不受信息文档格式和宿主设备的限制，而p 2 p 技术正好可以利用自身的优势开发出这样一种强大的搜索工具，它可以达到传 统目录式搜索引擎( 只能搜索到2 0 3 0 的网络资源) 无可比拟的深度( 理论上将 包括网络上的所有开放的信息资源1 。目前，p 2 p 技术在互联网信息搜索领域中 所展露的优势已初见端倪。 2 2 4p 2 p 应用层组播 应用层组播，就是在应用层实现组播功能而不需要网络层的支持。这样就 可以避免出现由于网络层迟迟不能部署对组播的支持而使组播应用难以进行的 情况。应用层组播需要在参加的应用节点之间实现一个可扩展的，支持容错能 力的重叠网络，而基于d h t 的发现机制正好为应用层组播的实现提供了良好的 基础平台。 2 3p 2 p 网络模式 p 2 p 模式根据是否有中央服务器的区别束划分可以分为集中式( c e n t r a l i z e d p 2 p ) 、分布式( d e c e n t r a l i z e dp 2 p ) 和混合式( h y b r i dp 2 p ) 三个不同模式。 g n u i e l l a 网络中树结构搜索机制的研究 2 3 1 集中p 2 p 模式 集中式p 2 p ( c e n l r a l i z e dp 2 p ) 【1 3 】在交换数掘或文件时一般是通过中央服务器进 行目录管理的。由于资源的发现依赖中心化的目录系统，发现算法灵活高效并 能够实现复杂查询。最大的问题与传统客户机朋艮务器结构类似，容易造成单点 故障，访问的“热点”现象和法律等相关问题，这是第一代p 2 p 网络采用的结 构模式，拓扑结构见图2 1 ，经典案例就足著名的m p 3 共亨软件n a p s t e r 【3 】。 n a p s t e r 是最早出现的p 2 p 系统之一，并在短期内迅速成长起来。n a p s t e r 实质上 并非是纯粹的p 2 p 系统，它通过一个中央服务器保存所有n a p s t e r 用户上传的音 乐文件索引和存放位置的信息。当某个用户需要某个音乐文件时，首先连接到 n a p s t e r 服务器，在服务器进行检索，并由服务器返回存有该文件的用户信息； 再由请求者直接连到文件的所有者传输文件。 图2 1 集中式p 2 p 拓扑结构( c e n t r a l i z e dt o p o l o g y ) 在n a p s t e r 模型中，一群高性能的中央服务器保存着网络中所有活动对等计 算机共享资源的目录信息。当需要查询某个文件时，对等机会向一台中央服务 器发出文件查询请求。中央服务器进行相应的检索和查询后，会返回符合查询 要求的对等机地址信息列表。查询发起对等机接收到应答后，会根据网络流量 和延迟等信息进行选择，和合适的对等机建立连接，并丌始文件传输。n a p s t e r 的工作原理如图2 2 所示。 索引服务器 图2 - 2 n a p s t e r 的1 作原理 n a d s t e r c i l e n t 量喜 惴卜 缈， 船妒 g n u t e l l a 网络中树结构搜索机制的研究 集中式p 2 p 模式的优点是： 1 结构简单，便于维护； 2 资源检索响应比较快； 3 管理维护整个网络消耗的网络带宽较低。 但是集中目录式p 2 p 模式还存在很多问题，主要表现为： 1 服务器承担所有的检索工作，负载过重不完全符合p 2 p 的原则； 2 中央服务器的瘫痪容易导致整个网络的崩溃，可靠性和安全性较低： 3 中央服务器的存在引起共享资源在版权问题上的纠纷，这也是直接导致 n a 口s t e r 破产的原因； 4 缺乏有效的强制共享机制，资源可用性差。 集中式p 2 p 可提供中心服务器目录检索、管理服务和标准的点到点通信， 具有高效的检索和低效的交换服务的特点。集中式p 2 p 对小型网络而言在管理 和控制方面占有一定的优势，但对大型网络并不适合【蜘。 2 3 2 分布p 2 p 模式 - b p s t e r 这并不是一种彻底的p 2 p 的结构，中央服务器群的性能和组织方式 影响了系统的性能和可扩展性。并且因为中央服务器的存在引起的版权纠纷导 致了它的破产。因此发展到是一种基于f 1 0 0 d i n g 的分布式索引算法，代表系统 是g n u t e l l a 。与n a p s t e r 网络不同，它不存在中枢目录服务器，或者说把所有机 器都变成了服务器，这就是第二代p 2 p 一一分布p 2 p 模式( d e c c t r a l i z e d p 2 p v l 3 】【。下图2 3 为分布p 2 p 模式的拓扑结构【1 3 】。 图2 3 分却p 2 p 拓扑结构( d e c e n t r a l i z e dt o p o l o g y ) 在g n u t e l l a 中，没有中央服务器，每个节点都是对等的。系统中有这样三类 消息，成员关系消息( p i n g ，p o n 曲，查询消息( q u e 吼r e s p o n s e ) ，文件下载消息 ( g e t p u s h ) 。g n u t e l l an e 抑o r k 的建立依靠成员关系消息。当一个节点加入到 g n u t e l l a 中时，它广播一个p i n g 消息，告诉其它节点它的存在。当某个节点接 1 4 g n u t e l l a 网络中树结构搜索机制的研究 受到p i n g 消息时，它一边返回p o n g 消息给新节点，一边f o n v a r d 这个p i n g 消息 给其它节点，同时在本地节点列表中记录新节点的信息。新节点根据收到的p o n g 消息获得一张节点列表。 当一个节点发送查询时，它将q u e r v 请求f l o o d 到所有本地节点列表中的 节点，其它节点收到q u e r y 后，在本地查看是否有符合该请求的查询，有的话 将文件信息r e s p o n s e 给请求节点。查看同时也刚样地将q u e r y 请求f l o o d 出去， 直到t 1 l ( t i m e t o 1 i v e ) 值减少到l 。从而q u e r y 就这样在g n u t e l l a 网络中散播 丌束。 这种结构的优势就在于没有中央服务器，能较好的处理动态节点加入和退 出，以及节点故障问题。但是这种f 1 0 0 d 的方法产生了大量的消息，占用了大量 的网络带宽，影响了系统的性能【1 5 】。 在分布式p 2 p 中，对等机通过与相邻对等机之问的连接遍历整个网络体 系。每个对等机在功能上都是相似的，并没有专门的服务器，而对等机必须依 靠它们所在的分布网络来查找文件和定位其他对等机【1 4 】。 分布式p 2 p 模式的优点是： 1 所有的节点都参与服务，不存在中央服务器，避免了服务器性能瓶颈； 2 部分节点受到攻击对服务影响不大； 3 搜索结果比较及时，有效性比较强。 分靠p 2 p 网络模式的缺点主要表现在以下方面： 1 _ 搜索请求遍历整个p 2 p 网络需要很多跳，完整的获得搜索结果延迟比较大； 2 随着网络规模的扩大，通过扩散方式定位对等点及查询信息的方法将会造成 网络丌销成指数级增加； 3 纯分布的p 2 p 模式很难被企业所利用，囚为它缺少对例络上的用户节点数 以及对他们提供的资源的一个总体把握； 4 安全性不高，易遭受恶意攻击，如攻击者发送垃圾鹰询信息，造成网络拥塞。 这种无中心、纯分布式系统的特点是：它不再是简单的点到点通信，而是 更高效、更复杂的网络通信；c d o n k e y 【”】和e m u l e 等软件引入了强制共享机 制，在一定程度上避免了第一代p 2 p 纯个人服务器管理带束的随意性和低效率 【1 4 1 2 3 3 混合p 2 p 模式 混合p 2 p 模式( h y b n dp 2 p ) 是介丁二c e n t m l i z e dp 2 p 和d e c e n t r a l i z e dp 2 p 之问， 从h y b r i dp 2 p 的字面上就可以看是，它是一个混合的结果。鉴于集中式p 2 p 具 g n u t c a 网络中树结构搜索机制的研究 有网络资源的快速检索能力，但是其中心化的模式易遭到直接的攻击；而分布 式p 2 p 解决了抗攻击问题，却又存在缺乏快速搜索和可扩展性的不足，混合式 p 2 p 便结合了集中式和分布式p 2 p 的优点，进一步优化其设计思想和处理能力。 它在分布p 2 p 模式的基础上，将用户节点按能力进行分类，使某些节点担任特 殊的任务1 1 4 】。 下图是混合p 2 p 模式的拓扑结构【1 3 j ： 图2 4 混合p 2 p 模式( h y b r i dt o p o l o g y c e n t r a l i z e d + d e c e m r a l i z e d ) k a z a a 模型是p 2 p 混合模型的典型代表，它在分布式p 2 p 模型基础上引入了 超级节点的概念，综合了集中式p 2 p 快速查找和分布式p 2 p 去中心化的优势。 k a z a a 模型将节点按能力不同( 计算能力、内存大小、连接带宽、网络滞留时间 等1 区分为普通节点和搜索节点两类( 也有的进一步分为三类节点，其思想本质相 同1 。其中搜索节点与其临近的若干普通节点之间构成一个自治的簇，簇内采用 基于集中目录式的p 2 p 模式，而整个p 2 p 网络中各个不同的簇之问再通过分布 式p 2 p 的模式将搜索节点相连起来，甚至也可以在各个搜索节点之间再次选取 性能最优的节点，或者另外引入一新的性能最优的节点作为索引节点来保存整 个网络中可以利用的搜索节点信息，并且负责维护整个网络的结构。 由于普通节点的文件搜索先在本地所属的簇内进行，只有查询结果不充分 的时候，再通过搜索节点之问进行有限的泛洪。这样就极为有效地消除分稚式 p 2 p 结构中使用泛洪算法带来的网络拥塞、搜索迟缓等不利影响。同时，由于每 个簇中的搜索节点监控着所有普通节点的行为，这也能确保一些恶意的攻击行 为能在网络局部得到控制，并且超级节点的存在也能在一定程度上提高整个网 络的负载平衡。 2 4 小结 本章主要是对p 2 p 发展历程做了一个回顾，介绍了p 2 p 的主要的网络模式 和当前的主要应用。虽然早在3 0 多年前，就已经有人提出过相似的理念，p 2 p g n u t e l l a 网络中树1 构搜索机制的研究 并非是一个全新的概念，可以说是一个历史的回归，但是它相对于因特网束说， 仍处于一个“新生”时期，它还需要一个比较稳健的成长过程，通过本章可以 从中了解p 2 p 的起源、应用方向和发展前景，为下文进行的p 2 p 研究奠定了基 础。 g n u i e l l a 网络中树结构搜索机制的研究 第三章g n u t e n a 网络 3 1g n u t e l i a 网络概述 2 0 0 0 年3 月1 4 日，a o l 的n u l l s o f t 部门发放一个丌放源码的n a d s t e r 的克隆 软件，这个能寻找和下载任何种类计算机文件的软件被命名为g n u t e l l a 。各种第 三方组织很快就开始对g n u t e l l a 进行克隆，丌发自己的客户版本。这些克隆的版 本都与n u l l s o f t 设计的g n u t e l l a 协议的相兼容，因此能彼此互相通讯并且和原先 + n u l l s o f t 的客户端通讯。当人开始运行这些克隆的未被授权的客户端软件后，一 个互相兼容的g n u t c l l a 应用网络开始增长并且用g n u t e l l a 协议约定的无中心的交 流方式。这个网络，在过去的2 0 0 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 网络上。在 g n u t e l l a 网络上，一个用户可以同时连接其他几台计算机，信息同时可能从很多 来源接收。g 叫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 兼容软件的用户。g n u t e l l a 是份联网协议，它定义了在一个完全分散 的网络环境下计算机彼此交流的方式【7 j 。 3 2g 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 已经在主机量达到上万级别的规模上 运行，任何人只需要把他希望共享的文件放在硬盘的一个目录下，然后利用 g n u t e l l a 刚络共享出去，用户之l 、b j 便可以自由地分享，共享的文件数量已经达到 数十万。 本文所介绍的足g n u t e l l a 协议的o 4 版本n 在这个版本里定义了对等机 ( s e r v e n t ) 通过网络通讯的方式，它包括定义了通过对等机进行数据通讯的描述符 号集和内部对等机相互交互的规则集。但是在本协议中并没有介绍一个对等机 如何得到另一个对等机的地址的描述，即对节点的定位机制进行闸述。 g n u t e l l a 通信协议主要包括赶种类型的消息，分别是p i n g ，p o n g ，o u e r y ， o u e r y h j t 和p u s h ，年r 关定义内容如表3 1 下： g n u t e i l a 网络中树结构搜索机制的研究 指令说明 p i n g 指令用于激活发现网络上的对等机。一个对等机收到一个p i n g 的 描述符表示希望回应一个或多个p o n g 描述符。 p o n g 指令用于回应p i n g 。包括一个被连接的g n u t e l l a 对等机的地址和他 能提供的数据供共享的信息。 q u e r y 指令首要的分布式网络检索机制。一个对等机收到一个q u e f y 描述 符后，如果在自己的数据集中发现一个匹配的数据将回应一个 q u e r y h i t 。 q u e r y h i t 指令用于回应q u e r y 。这个描述符提供足够的信息来获取匹配 q u e r y 请求的数据。 p u s h 指令一个用于允许防火墙中的客户端向网络提供基于文件的数据 文件的机制。 表3 1g n u t e l l a 通信协议消息 在g n u t e l l a 网络中，对等机节点利用p i n g 和p o n g 进行主机动态发现，在查 询数据的时候使用q u e r y 和q u e t y h i t ，p u s h 则用于穿越防火墙的主机和文件探 测。 一旦一个对等机节点成功连接到网络上，他与其它对等机通过发送和接收 g n u t e l l a 协议描述符。每一个描述符前都有一个以下字节结构的描述符头，如下 所示： 消息头字段 d e s c n p t o r b v t e o f f 毫c to g n u t e l l a 网络中树结构搜未机制的研究 消息内容描述 d e s c r i p i o ri d1 6 个字节的字符串唯一标示网络的描述符号。 ( 网络描述符) p a v l o a d 0 x 0 0 = p i n g d e s c r i p t o r0 x 0 1 = p o n g ( 负载描述符)o x 4 0 = p u s h o x 8 0 = q u e r y o x 8 1 = q u e r y h i t 、 m 描述字符在删除自口在g n u t e l l a 网络中向前传递的次数。每个 ( 生存期)客户端在将包向前传递d h 将n l 减一。当t t l 等于1 ，描 述符将不再被向l ； 传递。 h o p s作为一个描述符向前传递，头部的t r l 和h o p s 字必须满足 ( 描述符被向前以下条件： 传递的次数) t t u o ) = t t u i ) + h o p s ( i ) p a y l o a dk n 舀h表示紧接着头部后面的描述符部分的长度。下一个描述符头 ( 负载长度)部的地址应为从此描述符头部末地址加上p a y l o a dl e n g t h 字 节数后的地址，也就是没有间隔或保留字在g n u t e l l a 的数据 流中。 表3 2 消息头字段 并且消息中的内容遵循如下规定： 1 所有结构内字符次序都是在低位在后，除非另作说明。 2 所有结构中的i p 地址都是i p 4 格式。 其中，t r l 是网络中唯一的描述过期的机制。对等机应该仔细检查收到的 描述符的订l 区并在必要时减少它的值。p a y l o a dk n g t h 区是对等机查找输入流 中下一个描述钓的唯一可靠方式。6 n u t e l l a 协议不提供一个“监视”字符串或任 何其它的描述符同步的方式。因此，对等机应该严格保证每一个收到的描述符 的p a y l o a dk n g i h 区的有效性( 至少为固定长度的描述符) 。 3 3g n u t e l l a 的工作机制 但是在上面的协议中并没有包括一个对等机如何得到另一个对等机的地址 的描述，在此对节点的定位机制进行阐述，并简币介绍一fg n u t e l l a 网络的消恩 奄询机制和消息控制机制。 g i e l l a 网络中树结构搜索机制的研究 3 3 1 节点定位机制 在p 2 p 网络中，没有一个对等机知道整个网络的结构或者组成网络的每个 p 2 p 点的身份。每一个对等机要完成自己的任务，就必须发现其它对等机( 即知 道其它对等机的地址) ，并与其进行交互。在g n u t e l l a 网络由许多对等机组成， 这些对等机在功能上很类似，没有专门的目录服务器，对等机必须使用它们所在 的网络来定位其它对等机。g n u t e 儿a 网络的节点定位采用了网络模型。 网络模型p 2 p 应用程序由一些( 通常是动念的) p 2 p 点组成。没有一个p 2 p 点知道整个网络的结构或者组成网络的每个p 2 p 点的身份，但是p 2 p 点知道直 接与它们通信的p 2 p 点。在许多环境中为了完成任务( 包括支持分布式查询、 分布式消息传递，甚至包括认证和授权行为) ，对等机必须进行合作。因为涉及 通信量的多少，像文件传输这样需要大流量的网络操作通常在对等机间直接发 生，而不是通过对等机的网络1 1s - 。 如图3 1 ，当对等机p 希望知道网络中另一个对等机的位置时，它就需要 其它对等机合作。首先它发出一个查询请求传递给其邻节点。这些邻节点尝试 着能否满足这个请求。如果这些邻节点不能完全满足这个请求，就将请求传递 给它们的邻节点，以此类推直到满足这个要求。当一个对等机要加入网络，先 要找到愿意接受它为邻居的另一个对等机。但是，如果对等机本身还不是网络 的一部分时，它如何找到网络中的另一个对等机呢? 一个可能的解决方案是向 这个对等机提供一个对等机列表。当一台新对等机首先通过访问某特殊站点提 供的“主机缓存服务”( h o s tc a c h es e n ，i c e s ) 机制来得到一台活动对等机地址， 通过与它建立个连接将