（管理科学与工程专业论文）面向多任务的对等网络技术研究.pdf

国防科学技术大学研究生院硕士学位论文 摘要 目前，互联网的计算和通信环境日趋复杂。作为一种新的计算模式， p e e r - t o p e e r ( p 2 p ) 得到了广泛的应用。与c s 模式相比，p 2 p 系统中节点的角色 是对等的，同时承担服务器和客户机两个角色，节点间通过相互协作实现系统功 能。p 2 p 系统由对等、自治的节点构成，无集中控制，高度动态，自组织、自适应 能力强，避免了传统的分布式系统存在的单点失效和伸缩性差的问题。 本文研究如何进一步提高p 2 p 系统中各节点闲置能力的利用率。针对现有p 2 p 系统没有全面挖掘节点闲置能力的问题，提出了面向多任务的对等网络模型，探 索该模型所牵涉到的网络评估、网络拓扑快速构建等相关技术问题。主要取得以 下研究成果： ( 1 ) 提出了面向多任务的对等网络模型。从当前各种p 2 p 系统的研究着手， 结合p 2 p 网络评估、拓扑管理和各种网络拓扑结构快速构建等技术的研究，提出 一种面向多任务的对等网络模型，首先将所有节点以基础网络的形式组织在一起， 然后根据节点能力的差异和任务的特点，选择“合适 的节点并快速构建出适合 特定任务的应用层p 2 p 网络，以高效地处理任务。本文对提出的模型的相关支撑 技术作了详细的介绍与讨论，模型在技术上是可行的，并且能大大提高节点闲置 能力的利用率。 ( 2 ) 提出了快速构建k a d e m l i a 网络算法。各种p 2 p 网络拓扑的快速构建是 面向多任务的对等网络模型的关键技术，现有的各种p 2 p 网络拓扑各有优缺点， 各适合不同类型的任务。本文提出了一种快速构建k a d e m l i a 网络拓扑的算法，阐 述了算法思想及详细过程，最后进行了实验。实验表明：提出的算法能够在对数 的步数内构建出满意的k a d e m l i a 网络，收敛速度快。 ( 3 ) 提出了快速构建c a n 网络算法。c a n 网络是一种基于空间划分的结构 化p 2 p 网络，由于c a n 网络基于多维坐标系，且邻居关系在空间上是连续的，所 以c a n 在处理复杂查询方面具有独特的优势。受二叉树思想启发，本文提出了一 种快速构建c a n 网络拓扑的算法，阐述了算法思想及详细过程，最后进行了实验。 实验表明：提出的算法能在对数级的步数内构建出满意的c a n 网络，且平均每个 节点的新增通信开销为常数，伸缩性好。 主题词：对等计算多任务拓t l 、构建覆盖网络 第i 页 国防科学技术大学研究生院硕+ 学位论文 a b s t r a c t o v e rt h ei n t e r n e t t o d a y ，c o m p u t i n ga n dc o m m u n i c a t i o n se n v i r o n m e n t s a r e s i g n i f i c a n t l ym o r ec o m p l e xa n dc h a o t i c a san e wc o m p u t i n gm o d e l ，t h ee m e r g i n g p e e r - t o - p e e r ( p 2 p ) n e t w o r kh a sb e e nw i d e l yu s e d c o m p a r e d 们t i lt r a d i t i o n a lc sm o d e l ， e a c hp e e ri np 2 ps y s t e mh a st w or o l e s ：i tf u n c t i o n sa ss e r v e ra n dc l i e n ta tt h es a m et i m e t h ep 2 ps y s t e mf u n c t i o ni sr e a l i z e dt h r o u g hc o w o r ka n dc o o p e r a t i o na m o n gp e e r s t h e p 2 ps y s t e mi sm a d eu po fs e l f - g o v e m i n gp e e r s ，l a c k i n ga n yc e n t r a l i z e dc o n t r o l ，h i g h l y d y n a m i c ，a n da v o i d i n gt h es i n g l e - n o d e f a i l u r ea n dl o w - s c a l a b i l i t yp r o b l e m t h i sp a p e ri sd e v o t e dt ot h ei s s u e so fi m p r o v i n gt h eu t i l i z a t i o nr a t i oo fi d l i n g a b i l i t yo fp e e r s w i t ht h ee x i s t i n gp r o b l e mo fc u r r e n tp 2 ps y s t e m ，t h i sp a p e rp r e s e n t sa n e wp 2 pn e t w o r km o d e lt o w a r d sm u l t it a s k s ，a n ds t u d i e st h er e l e v a n tt e c h n o l o g yl i k e p 2 pn e t w o r ke v a l u a t i o na n dr a p i dc o n s t r u c t i o no fp 2 po v e r l a yt o p o l o g y t h em a i n c o n t r i b u t i o n sa r ea sf o l l o w s ： 1 t h i sp a p e rp r e s e n t san e wp 2 pn e t w o r km o d e lt o w a r d sm u l t it a s k s b a s e do nt h e p r e s e n tr e s e a r c ho np 2 ps y s t e m ，n e t w o r ke v a l u a t i o n ，o v e r l a yt o p o l o g ym a n a g e m e n ta n d r a p i dc o n s t r u c t i o n ，t h i sp a p e rp r e s e n t san e wp 2 pn e t w o r km o d e lt o w a r d sm u l t it a s k s i t o r g a n i z e sa l lt h ep e e r si nt h ef o r mo ff o u n d a t i o nn e t w o r k ，t h e nc h o o s e st h es u i t a b l ep e e r a c c o r d i n gt oi t sa b i l i t ya n dt h ep e c u l i a r i t yo ft h et a s k ，f i n a l l yr a p i d l yb u i l d st h e a p p l i c a t i o nl a y e rp 2 pn e t w o r kf o rt h es p e c i f i ct a s kw h i c hi sm e a n tt od e a l 、析t ht h et a s k e f f i c i e n t l y t h i sp a p e rm a k e sad e t a i l e di n t r o d u c t i o na n df u r t h e rd i s c u s s i o no nt h e s u p p o r t i n gt e c h n o l o g yo ft h ep r e s e n t e dp 2 pn e t w o r km o d e lw h i c hi st e c h n i c a l l yf e a s i b l e a n dc a nh i g h l yi m p r o v et h eu t i l i z a t i o nr a t i oo fi d l i n ga b i l i t yo f p e e r s 2 t h i sp a p e rp r o p o s e sa na l g o r i t h mf o rr a p i d l yb u i l d i n gk a d e m l i ao v e r l a y t o p o l o g y t h er a p i dc o n s t r u c t i o n o fv a r i o u sp 2 po v e r l a yt o p o l o g i e si st h ek e y t e c h n o l o g yo ft h ep r o p o s e dp 2 pn e t w o r km o d e l t h ec u r r e n tp 2 ps y s t e m sh a v et h e i r o w nm e r i t sa n dd r a w b a c k s ，a n de a c hi ss u i t a b l ef o rl i m i t e dk i n d so ft a s k s t h i sp a p e r p r o p o s e sa na l g o r i t h mf o rr a p i d l yb u i l d i n gk a d e m l i ao v e r l a yt o p o l o g y ，a n de x p a t i a t e s o nt h ep r i n c i p l eo ft h ea l g o r i t h ma n dt h ed e t a i l e de x e c u t i n gp r o c e s s a tl a s t ，i ti s d e m o n s t r a t e dt h r o u g he x t e n s i v es i m u l a t i o ne x p e r i m e n t st h a tt h ep r o p o s e da l g o r i t h mc a n c r e a t eap e r f e c tk a d e m l i ao v e r l a yt o p o l o g yi nal o g a r i t h m i cn u m b e ro fs t e p s 3 t h i sp a p e rp r o p o s e sa na l g o r i t h mf o rr a p i d l yb u i l d i n gc a no v e r l a yt o p o l o g y c a ni sas t r u c t u r e dp 2 ps y s t e m sb a s e do ns p a c ep a r t i t i o n b e c a u s ec a nu s e sav i r t u a l m u l t i - d i m e n s i o n a lc a r t e s i a nc o o r d i n a t e s p a c ea n ds p a t i a l l y c o n t i n u e si nn e i g h b o r r e l a t i o n s ，i th a si t sp e c u l i a ra d v a n t a g ei nd e a l i n gw i t hc o m p l e xq u e r y i n s p i r e db yt h e b i n a r yt r e es t r u c t u r e ，t h i sp a p e rp r o p o s e sa na l g o r i t h mf o rr a p i d l yb u i l d i n gc a no v e r l a y t o p o l o g y ，a n de x p a t i a t e so nt h ep r i n c i p l eo ft h ea l g o r i t h ma n dt h ed e t a i l e de x e c u t i n g p r o c e s s a tl a s t ，i ti sd e m o n s t r a t e dt h r o u g he x t e n s i v es i m u l a t i o ne x p e r i m e n t st h a tt h e 第i i 页 国防科学技术大学研究生院硕士学位论文 p r o p o s e da l g o r i t h mc a l lc r e a t eap e r f e c tc a no v e r l a yt o p o l o g yi nal o g a r i t h m i cn u m b e r o fs t e p s ，a n dt h ea v e r a g ei n c r e a s e dc o m m u n i c a t i o no v e r h e a do fp e e ri ss t i l lac o n s t a n t ， s ot h ep r o p o s e da l g o r i t h mh a sh i g hs c a l a b i l i t y k e yw o r d s ：p 2 p ，m u l t i t a s k ，t o p o l o g yc o n s t r u c t i o n ，o v e r l a yn e t w o r k 第i i i 页 国防科学技术大学研究生院硕+ 学位论文 表目录 表1 1 结构化p 2 p 系统和非结构化p 2 p 系统的比较8 表3 1k 桶结构3 6 国防科学技术大学研究生院硕十学位论文 图目录 图1 1c s 与p 2 p 比较3 图1 2p 2 p 系统分类7 图1 3c h o r d 原理图示1 1 图1 4p a s t r y 路由表与路由过程1 2 图2 1面向多任务的对等网络模型概念图1 6 图2 2 面向多任务的对等网络模型建模过程1 7 图2 3 基于流言协议的聚集计算算法2 0 图2 4t m a n 协议2 8 图3 1k a d e m l i a 原理图3 2 图3 2k a d e m l i a 路由过程3 4 图3 3k a d e m l i a 构建算法3 5 图3 4 异或距离小的节点的k 桶互补性强3 5 图3 5i d 长度为2 0 ，不同节点个数时的实验结果3 9 图3 6i d 长度为3 0 ，不同节点个数时的实验结果3 9 图3 7i d 长度为3 0 的无标度网络不同节点个数时的实验结果4 0 图4 1c a n 空间划分与路由过程4 2 图4 2节点加入c a n 网络4 2 图4 3 坐标空间划分过程4 4 图4 4 节点根据自己i d 负责相应区域4 5 图4 5 对图4 4 的二叉树表示形式4 5 图4 6 对图4 5 节点合并后4 6 图4 7 对图4 6 再次合并4 6 图4 8 将图4 7 映射到坐标空间4 7 图4 9 合并方法图示4 7 图4 1 0 建立c a n 网络的邻居关系4 8 图4 1 1i d 长度为6 0 b i t s 时，网络规模与选举次数关系图5 0 图4 1 2网络规模为1 0 0 0 0 时，i d 长度与选举次数关系图5 0 图4 1 3i d 长度为6 0 ，网络规模为1 0 0 0 0 时，各节点选举次数分布图5 1 第1 v 页 独创性声明 本人声明所里交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文申特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贾献均巴在论文 中作了明确的说明并表示谢意 学位论文题习： 堑囱垒丝丕鲍技釜豳垒挂盔堑窥 学位论文作者鼢么星 魄矽弘| z 月气日 学位论文版权使用授权书 本人完全了解国肪科学技术大学有关保留，使用学位论文的规定。本人授权国 防科学技术大学可以保留并向固家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阍；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可越采用影印缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 举位论文作者签名 盔塞一 作者指导教师签名：许 厶碜 月 月 乙 位 垃 卑 年 q d 皿盯硒御 2 期 期 国防科学技术大学研究生院硕士学位论文 第一章绪论帚一早珀v 匕 近年来，随着计算机技术和通信技术的快速发展，大量终端设备以多种方式 接入互联网，使互联网的规模越来越大。同时，互联网的带宽也逐步提高，网络 资源日渐丰富，服务质量不断提高。近年来出现的p 2 p 技术克服了集中服务器模 式的缺点，p 2 p 技术可扩展性好、自组织、自适应能力强、能面向大规模应用，吸 引了研究者的大量关注。本章综述了相关研究背景，详细介绍了各种p 2 p 技术， 分析了目前相关工作存在的不足，并说明了本文的主要工作和文章结构。 1 1 研究背景 计算机硬件以摩尔定律的速度快速发展，每隔1 8 个月，计算机速度提高一倍， 而价格却下降一半。家庭、学校和公司的计算机数量快速增加，性能也不断提高， 随着信息化浪潮席卷全球，这些终端设备接入互联网，把社会中的主体( 如政府、 公司、学校、个人等) 通过互联网联系起来，形成了信息化社会。网络带宽不断 提高，互联网传输的信息不再只是文本和图片，各种各样新兴的多媒体服务逐渐 成为网络服务的重要组成部分。同时，互联网中资源的数量以几何级数快速增加。 互联网为人们获取资源提供了快捷的途径，人们对资源的需求从广度和深度上也 有了更高的要求，人们也有能力为他人提供各种各样的资源。 在计算机技术快速发展推动下，资源共享由传统的集中服务器模式( 如c s 模式) 向分布式、网络化方向发展。然而，目前的网络环境由不同的硬件平台、 软件系统组成，呈现出分布式异构系统的特征。在网络的各个角落，分布着各种 各样软硬件系统的终端，这些终端具有一定的自治能力，并能够为其他终端提供 信息与服务。在不影响各终端自治性的前提下，实现各终端资源的集成与共享具 有重大的理论和实践意义【1 1 。 随着互联网中资源数量的激增和信息资源管理技术的发展，资源共享呈现以 下发展趋势【2 】：资源共享规模越来越大，共享方式由集中走向分布，参与节点对等、 自治并相互协作，系统高度动态。 资源共享的发展方向是在广域分布、动态自治的条件下，提供伸缩性强、稳 定性高的资源共享服务。然而，当前流行的基于集中服务器模式的资源共享模式 存在性能瓶颈，且未能充分利用网络中分布的大量节点的闲置资源，包括数据、 计算能力、存储空间和带宽等资源【3 1 。因此，面向大规模的资源共享，研究新型、 高效的共享模式，是目前面临的重要研究课题。 在上述背景下，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 系统的节点具有处理多种类型任务的能力，处理多种类型的任务能更 全面地利用节点各方面的能力。不同类型的任务如文件共享、分布式缓存、分布 式计算和分布式存储等分别侧重于利用计算机的文件、带宽、c p u 时间和存储空 间等资源。由于现有的各p 2 p 系统往往针对特定的任务，所以只能从某些方面利 用参与节点的闲置能力，因此，使p 2 p 系统能够面向多种类型任务，从而节点能 够同时处理多种类型任务，进而更全面地挖掘节点的闲置能力，成为提高节点闲 置能力利用率的一个非常实用有效的办法。 本文正是基于以上背景，研究面向多任务的对等网络相关技术，以提高节点 闲置能力的利用率。 1 2p 2 p 技术概述 p 2 p 是p e e rt op e e r 的缩写，字面意义为“端对端”，在最初的计算机网络通 信中，各联网设备就是以端对端方式通信的。目前，p 2 p 被赋予了新的含义，是旧 有技术新的应用模式。 1 2 1p 2 p 定义 p 2 p 是一种新的计算模式，与集中服务器模式相比，这种计算网络中节点角色 是对等的，通过相互协作实现系统功能。在p 2 p 系统中，各对等节点之间无需依 第2 页 国防科学技术大学研究生院硕士学位论文 赖集中式服务器，通过直接连接共享资源，相互服务。 自p 2 p 产生到现在，学术界对p 2 p 尚未达成一致的定义。 i b m 为p 2 p 作了如下定义：通过边缘化设备的主动协作，每个成员直接从其 他成员而不是从服务器的参与中受益，系统中的成员同时扮演服务器与客户端的 角色，用户能够意识到彼此的存在，构成一个虚拟或实际的群体【4 1 。 i n t e l 公司的p 2 p 工作组将p 2 p 定义为“通过在系统之间直接交换来共享计算 机资源和服务的系统1 5 j 。 g r a n h a m 认为p 2 p 系统必须具备以下三个条件：( 1 ) 具备服务器的能力；( 2 ) 具有独立于d n s 的寻址系统；( 3 ) 拥有处理可变连接的能力【6 】。 s h i r k e y 将p 2 p 定义为“一种利用互联网边缘的各种可用资源( 如存储空间、 计算能力、内容、带宽等) 的应用程序 【7 】。因为访问这些网络中分散的资源需要 在不稳定连接和不可预知i p 地址环境下进行，所以p 2 p 节点必须独立于d n s 系 统，拥有独立于集中服务器的自治能力。 虽然以上对p 2 p 定义的角度各有侧重，内容不尽相同，但它们都强调了p 2 p 的各个节点在责任和功能上是逻辑对等的，通过节点间协作完成任务【引。p 2 p 系统 的节点同时具有服务器和客户端角色，既为其他节点提供服务，也请求其他结点 服务。图1 1 为c s 模式与p 2 p 模式比较图，可以看出，在c s 模式中，客户机和 服务器间存在多对一的关系，因而存在性能瓶颈与单点失效问题。 c s 典型结构 客户机客户机 节 节 p 2 p 典型结构 节点 图1 1 c s 与p 2 p 比较 从技术角度来说，p 2 p 并不是新的技术，而是一种新的应用技术模式。t c p i p 作为网络通信的基础，它的设计目标就是提供网络终端间点对点方式通信，发送 方指定接收方的i p 地址，i p 层将数据报文投递到指定i p 地址对应的网络终端。随 - _ _ - _ _ _ _ _ _ - _ _ - - - - _ _ _ _ - - _ _ - _ - - - l - 一一 第3 页 国防科学技术大学研究生院硕士学何论文 着网络技术的发展，出现了c s 模式，并逐渐成为网络应用的主流。c s 模式的核 心在于把信息资源向网络的某一特定位置( 服务器) 集中，从而人们可以在特定 的网络位置访问到关于某一主题的信息资源，减轻了人们从大量网络节点中寻找 资源的麻烦。然而，c s 模式导致了一对多的局面，虽然部分满足了人们对资源的 需求，但是随着计算机技术的发展，越来越多的用户和资源加入到网络中，从而 大量资源聚集在少数服务器节点上，使服务器的负载越来越重，从而产生性能瓶 颈，不利于向客户提供高质量的服务。 p 2 p 引导网络计算模式从集中式向分布式偏移，即网络应用的核心从中央服务 器向网络边缘的终端扩散。 1 2 2p 2 p 技术应用现状 目前p 2 p 技术在许多领域都得到了广泛的应用，主要应用领域包括：文件共 享、网络存储、协同工作、分布式计算、分布式搜索、实时通信技术1 2 ，引。 ( 1 ) 文件共享。 文件共享是p 2 p 技术最为典型的应用。传统上，人们采用c s 模式进行文件 共享，资源首先上传到服务器，之后，各客户端向服务器提出下载请求，下载所 需文件。这种传统方式主要包括f t p 、w e b 等文件共享服务。由于大量客户端向服 务器请求服务，服务器就成了文件共享的性能瓶颈，并且文件资源还得首先上传 到服务器，而不能在客户端直接共享，资源的传播速度相对降低。目前，出现了 多种基于p 2 p 技术的文件共享系统，如n a p s t e r 1 0 】、f r e e n e t 1 1 】、g n u t e l l a 1 2 】、e m u l e 、 b i tt o r r e n t 等，在这些基于p 2 p 技术的文件共享系统中，每个客户端既是资源的生 产者，又是资源的消费者，p 2 p 技术充分利用了分布在网络边缘的各个网络设备资 源，通过相互协作实现文件资源在网络设备间直接传输，提高了网络带宽资源和 各客户端资源的利用率，为用户提供了高质高效的文件共享服务。 ( 2 ) 网络存储。 信息资源的爆炸性增长，对存储系统提出了越来越高的要求，传统的c s 模 式由于服务器难以应付海量资源的存储和下载请求，产生了性能瓶颈。局域存储 技术向基于互联网的文件存储系统发展成为新的趋势。p 2 p 技术允许把资源分散存 储在多个节点上，充分利用了网络边缘设备的存储能力，不仅可以减轻服务器负 担，节省大量开支，还可以提高资源存储的可靠性。节点通过一定的查询机制定 位到存储所需资源的节点后，直接与其建立连接，下载所需资源。采用这种方式 存储、共享信息资源可以充分利用网络的带宽资源和各节点的闲置能力，提高资 源的稳定性。目前代表性的文件存储共享项目有伯克利大学开发的采用t a p e s t r y 1 3 1 技术的分布式海量存储系统o c e a n s t o r e 1 4 】、r i c e 大学和微软公司联合研究的 第4 页 国防科学技术大学研究生院硕士学位论文 p a s t r y t l 5 】项目等。 ( 3 ) 协同工作。 协同工作是指多个节点利用网络中的协同计算平台互相协同，共同完成某项 任务，如科学计算、资源共享等。传统的协同应用平台大多采取c s 模式来实现 成员的协同工作，不适合进行大规模协作。采用p 2 p 技术，节点可以在不经过中 央服务器协调的情况下，直接进行通信，建立分布式协同应用环境，使得节点间 信息交互变得更加方便快捷。g r o o v e 1 6 】是基于互联网的p 2 p 协同应用软件的典型 代表，它支持用户之间即时信息传递、语音交流、文件共享和电子白板等来进行 协作，从而用户可以直接进行实时的协同工作。 ( 4 ) 分布式计算。 分布式计算研究如何充分利用网络中各种各样的计算单元共同完成大规模的 计算任务。由于单一计算单元的计算能力有限，因此需要联合多个计算单元共同 完成大规模的计算任务；另一方面，由于目前网络中大部分计算机的计算能力大 部分时间被闲置，利用网络中各节点的闲置计算能力完成大规模的计算任务是成 为迫切的需求。p 2 p 很好地满足了这一需求，合理整合网络中闲置的计算能力和资 源，在整体上形成了大规模计算能力。最著名的例子是搜索外星文明s e t i h o m e r 7 l 科学实验。 ( 5 ) 分布式搜索。 搜索引擎是目前人们在网络中检索信息资源的主要工具，目前著名的搜索引 擎如g o o g l e 、b a i d u 等都是集中式的搜索引擎。这种集中式搜索模式依赖中央服务 器，服务器先收集互联网上的信息资源，并保存到海量数据库中，从而可以通过 操作数据库向用户提供信息资源检索服务，当用户提交搜索请求时，服务器在海 量数据库内部进行搜索并返回相应结果。尽管这种机制能够很快获得搜索结果， 但不能保证搜索范围的深度与结果的时效性。由于互联网上信息资源数量巨大， 且更新时间长短不一，服务器把互联网上的信息资源收集并保存到海量数据库是 一个长时间的周期，导致了查询结果不能及时反映网络中信息资源的动态变化。 基于p 2 p 的搜索方法最大优势在于应用了对等搜索概念，不需要中央服务器就可 以对互联网进行全方位的资源搜索。p 2 p 网络中节点之间动态连接，使得资源搜索 可以在各节点直接进行，从而保证了搜索结果的实时性；此外，搜索请求在节点 间传播，搜索范围以几何级数扩散，它的搜索深度和广度是集中式搜索引擎难以 比拟的。s u n 公司开发的p 2 p 分布式搜索引擎j x t a s e a r c h 1 8 】以及m i l l e r 提出的p 2 p 分布式搜索引擎h y p e r b e e ”】是该研究领域的代表。 ( 6 ) 实时通信。 实时通信是网络技术的一个重要应用，实时通信系统为用户间的实时通信提 第5 页 国防科学技术大学研究生院硕士学位论文 供了方便，与传统的固定电话、移动电话相比，基于互联网的实时通信价格非常 低廉，吸引了大量用户。与互联网在线聊天系统、b b s 或w e b 聊天室比较，p 2 p 实时通讯软件不依赖服务器的性能和带宽，通信双方的交流完全是以点对点方式 进行的，通信双方实时知道对方是否在线。i c q 、q q 、m s n 等是典型的实时通信 系统。 1 2 3p 2 p 技术的特点 p 2 p 网络具有以下特点：节点对等、自治、网络规模大、无集中控制、动态、 自组织、自适应能力强【2 ，2 0 1 。 ( 1 ) 节点对等与自治。 网络中的每个节点既是资源提供者又是资源消费者，同时扮演着服务器和客 户机两个角色，从这种意义上来说，网络中各节点的地位是对等的。节点可以自 主决定加入或退出p 2 p 系统，自己决定共享哪些资源，这一点体现了p 2 p 系统中 节点高度的自治性。节点之间的交流也是自主和对等的。当然，对等节点的高度 自治并不妨碍之间的协作，节点之间有效协作是大规模p 2 p 系统具有很强整体功 能的重要原因。 ( 2 ) 网络规模大，无集中控制。 p 2 p 系统的节点个数一般远远大于传统的分布式系统的节点个数，且不存在集 中控制。传统的分布式计算系统一般存在集中控制节点，当网络规模非常大时， 负责集中控制功能的节点负载将会非常高，甚至过载而崩溃，因此集中控制节点 往往成为性能瓶颈，所以传统的分布式计算系统的网络规模、扩展性一般要小于 p 2 p 系统。p 2 p 系统不存在集中控制，系统中的各个节点无法获知全局信息，只能 通过节点间交互局部信息进行决策，所以p 2 p 系统通常难以全局最优的策略完成 某些任务。但无集中控制使p 2 p 系统不存在性能瓶颈，拥有较强的伸缩性，从而 保证了面向大规模应用的能力。 ( 3 ) 动态、自组织、自适应能力强。 节点的对等与自治导致了p 2 p 系统的高度动态特性。由于节点拥有自我管理 的最高权限，可以决定是否加入或退出网络，共享哪些资源，共享程度等，从而 整个网络连接和网络中资源状态随时可能发生变化，因此整个p 2 p 网络是动态的。 因为p 2 p 网络不存在集中控制，系统中的每个节点无法获知全局信息，必须通过 节点间局部信息的交互进行决策，从而p 2 p 系统的管理功能分布在各个节点上， 节点的自治以及相互协作使系统具有很强的自组织和自修复能力。自组织系统是 指系统由分布的部件构成，各部件只有局部信息，通过部件间交互局部信息，并 相互协作实现系统的全局目标【2 l ，2 2 1 。这种自组织和自修复能力使系统在恶劣条件 第6 页 国防科学技术人学研究生院硕十学位论文 下仍能正常工作，使系统中突发的错误得到修复，从而系统在整体上具有很强的 容错能力和扩展性，自适应能力强。 综合以上对p 2 p 系统特点的分析，p 2 p 系统由对等、自治的节点构成，无集 中控制，高度动态，自组织、自适应能力强，避免了传统分布式系统存在的单点 失效和伸缩性差的问题。从而p 2 p 系统能够适应恶劣的环境，容错能力强，在遭 受严重破坏时仍具有很强的自修复能力。p 2 p 系统的整体能力随着节点的加入不断 增强，各节点之间直接交互，资源利用效率高。 1 3 相关研究工作 从网络拓扑结构的角度，目前已有的p 2 p 系统分为非结构化p 2 p 系统和结构 化p 2 p 系统两大类 2 0 , 2 3 】。p 2 p 系统分类如图1 2 所示。 图1 2p 2 p 系统分类 最早出现p 2 p 系统是非结构化的，在非结构化p 2 p 系统中，资源存储在各个 节点上，当用户需要资源时，用户并不知道资源在网络中的存储位置，只能向网 络中各节点发出询问消息，常用的搜索方法为通过泛洪方式向其他节点传播查询 消息，因而资源搜索带有一定的盲目性。但由于非结构化p 2 p 系统实现相对容易， 拓扑维护比较简单，鲁棒性好，在当前p 2 p 应用中占据主要地位。 结构化p 2 p 系统通过相容哈希函数【2 4 】将资源精确放置在确定的网络位置上， 资源标识与资源存储位置之间存在确定的映射关系，从而通过相应的路由协议能 够在有限步数内查找到相应的资源。结构化p 2 p 系统以基于分布式哈希表 ( d i s t r i b u t e dh a s ht a b l e ，d h t ) 的c h o r d 2 卯、c a n t 2 6 1 、v i c e r o y 2 7 1 、p a 鲫【1 5 l 、 t a p e s t r y 0 3 1 和k a d e m l i a t 2 剐为代表。 从目前的研究现状来看，对它们的研究侧重点不同，非结构化p 2 p 系统侧重 于提高搜索效率，结构化p 2 p 系统则侧重于提高系统的鲁棒性和拓扑维护效率， 第7 页 国防科学技术大学研究生院硕士学何论文 并能够支持复杂的查询。根据资源搜索过程对维护索引的节点的依赖程度，非结 构化p 2 p 系统又可以分为集中式( c e n t r a l i z e d ) 、全分布式( d e c e n t r a l i z e d ) 和混合 式( h y b r i d ) 三种【2 9 1 。集中式p 2 p 系统，如n a p s t e r ，使用中央服务器存放所有用 户的共享资源信息，由中央服务器提供资源查询服务，用户间直接进行数据传输， 效率较高，但由于中央服务器的存在，产生了单点失效、容错性低以及可伸缩性 差等问题。全分布式p 2 p 系统中不存在中央服务器，每个节点地位相同，通过广 播方式进行资源搜索，从而避免了单点失效问题，鲁棒性和扩展性很强，但广播 方式存在效率低、网络开销大等问题【3 0 1 ，全分布式p 2 p 系统的典型代表为 f r e e n e t 1 1 】。混合式p 2 p 系统介于集中式与全分布式之间，它把能力强的节点提升 为超级节点作为局部的集中式服务器，其他节点成为超级节点的叶子节点，超级 节点保存其叶子节点共享资源的目录信息。由于对集中式和全分布式p 2 p 系统进 行了折中，混合式p 2 p 系统折衷了两者的优缺点，产生了较好的整体功能，典型 的混合式p 2 p 系统有为k a z a a f 3 1 j 。 不同拓扑结构的p 2 p 网络的系统特性各有不同，通常衡量一种p 2 p 网络的性 能指标有稳定性、可伸缩性、系统性能、资源定位效率和开销等【3 2 1 。表1 1 对比了 非结构化p 2 p 系统和结构化p 2 p 系统的优缺点。 表1 1 结构化p 2 p 系统和非结构化p 2 p 系统的比较 非结构化p 2 p 系统结构化p 2 p 系统 拓扑维护开销小大 可伸缩性较差好 资源定位效率低高 稳定性 高低 鲁棒性高低 非结构化p 2 p 网络一般具有稳定性好的特点，维护网络拓扑的开销小，能支 持复杂的查询如相似查询、范围查询等，但因为它们一般采用了类似泛洪的方式 搜索资源，从而搜索效率低，通信开销大，存在伸缩性差的问题。 结构化p 2 p 网络维护网络拓扑的开销较大，稳定性一般，但它的资源定位效 率较高，能够在有限的步数内精确地查找到资源，但由于采用了哈希方法，通过 精确匹配定位资源，所以结构化p 2 p 网络对复杂的查询如相似查询、范围查询等 支持较差。文献 3 3 3 5 提出了在结构化p 2 p 网络上支持复杂查询的相关解决办法， 通过对c h o r d 进行一些改进使之支持相似查询，对c a n 网络进行改进使之支持多 维范围查询和事件订阅分发。因为结构化p 2 p 网络中资源精确地存储在网络的特 定位置上，从而“热点 资源会带来网络中节点负载不均衡问题p 6 3 7 。 第8 页 国防科学技术人学研究生院硕士学位论文 1 3 1n a p s t e r n a p s t e r 是最早出现的p 2 p 系统之一，它的设计目标在于共享m p 3 文件。n a p s t e r 采用了目录服务器机制，它把各节点的地址和相应m p 3 文件的相关信息存储到目 录服务器，实际m p 3 文件仍存放在本地。用户查找m p 3 文件时，首先连接到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 系统仍然面临单点失效的问题， 并且存在伸缩性较差的问题。当用户数量增加，n a p s t e r 服务器的负载加重，当用 户达到1 0 5 或者更高时，系统性能会大大下降。 1 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 的节点既是客户机又是服务器，从而g n u t e l l a 在本质上 是全分布对等的。节点提供用户接口，供用户提交查询和浏览结果，从该角度看， 节点是客户端；同时，节点还能处理其他节点递交的查询请求，检索本地数据并 返回结果，所以节点也提供了类似服务器的功能。所有节点共同负责网络拓扑的 维护，保证了系统整体的动态稳定性，系统不会因为小部分节点的退出或崩溃而 停顿，从而g n u t e l l a 具有很强的抗毁性。 节点要加入系统，需要连接到g n u t e l l a 系统中的一个知名节点，如 h t t p ：g n u t e l l a h o s t s c o r n 中提供的节点列表，要加入系统的节点从知名节点获取系统 中部分节点地址列表，从中选择一个地址，与该地址所代表的节点建立连接，从 而接入g n u t e l l a 网络。节点接入系统后，通过发送p i n g 消息通知系统中的其它节 点，收到p i n g 消息的节点返回p o n g 消息，其中包含响应节点的i