（管理科学与工程专业论文）P2P网络逻辑拓扑优化和结点组管理策略研究.pdf

r ( 3 ) 针对本文提出的模型，构造了群组内部和群组之间的下载方 式最多优先和最少优先，来确定组内和组外的资源块的分布。然 后，根据组内最多优先下轳嗓则并利用新结点分析出f r e er i d e r 结 点，来达到提高资源的可用性和资源分布均匀化的目的。 ( 4 ) 对所提出的基于群组模型进行仿真，并与b i t t o r r e n t 模型进 行比较，证明群组模型的可行性和良好的结点满意度。 关键词：非结构化p 2 p 网络系统；文件共享群；f r e e r i d e r ：l o n g t a i l ： 群组；逻辑拓扑结构 l i i ! l ii i l li iii iii iiil 17 3 618 4 t h el o gic a lt o p o l o g yo p ti z a t10 na n dp e e r sm a n a g e m e n t s t r a t e g ys t u d yinp 2 pn e t w o r k a b s t r a c t 4 莎 p e e r - t o p e e rt e c h n o l o g yi so n eo fi m p o r t a n tn e t w o r kt e c h n o l o g i e si n r e c e n t y e a r s i tp r o v i d e s ap o w e r f u lr e s o u r c es h a r i n gc a p a b i l i t ya n d r o b u s t n e s sa n db r i n g sah u g ec o n v e n i e n c et om a n yi n t e r n e tu s e r s h o w e v e r , d i f f e r e n t r e s o u r c e sh a v ed i f f e r e n tp o p u l a r i t ya sw e l la s f r e e r i d i n gb e h a v i o rb e c o m ei n c r e a s i n g l ys e r i o u si np e e rn e t w o r k ，w h i c h m a k e st h ed i s t r i b u t i o no fr e s o u r c e sh a sb e c o m ev e r yu n e v e n a n du s e r s o f t e nu n l i m i t e d l yw a i tf o ra na b s e n c eb l o c ki np 2 ps y s t e m t h i sa b o v ep h e n o m e n o ni sc a l l e db l p ( b l o c kl e e c h e rp r o b l e m ) t h i sp a p e ra r g u e st h a tag o o do v e r l a yt o p o l o g yi sa ni m p o r t a n tw a yt o i m p r o v et h eb l pp r o b l e m t h e r e f o r e ，w ep r o p o s e dag r o u p b a s e dp 2 p f i l e s h a r i n gm o d e lf o rt h i sp r o b l e m s i m i l a rt ob i o l o g i c a lc e l l d i v i s i o n s t r u c t u r e ，t h em o d e lm a i n l yc o n s t r u c tag r o u ps t r u c t u r et h a t ”n a t u r a l l y u n d e r s t a n d si n f o r m a t i o nb e t w e e ng r o u p s ，a n da c c o r d i n gt oi n t e r g r o u p m e s s a g e s a n dd a t at r a n s m i s s i o nf u r t h e re n h a n c e st h e c o n n e c t i v i t y b e t w e e ng r o u p st oa c h i e v et h ep u r p o s eo fi m p r o v i n gt h ea v a i l a b i l i t yo f i n r e s o u r c e s t h em a i n l yc o n t e n t so ft h i sp a p e ra sf o l l o w s ： ( 1 ) a n a l y s i st h eb l pp h e n o m e n o na n di t sc a u s e si np 2 pn e t w o r k ， a n ds u m m a r i z e dt h ee x i s t i n gl i t e r a t u r et os o l v ea b o v et h eb l p p r o b l e m 、 f r e e - r i d i n gp h e n o m e n o na th o m ea n da b r o a d ( 2 ) t h i sp a p e r s u m m a r i z e sp 2 p o v e r l a y n e t w o r k t o p o l o g y c h a r a c t e r i s t i c sa n dp r o p o s e sg r o u p - b a s e dp 2 p f i l e s h a r i n gm o d e l i nt h e m o d e l ，n o d e sa r ed i v i d e di n t o s e v e r a lg r o u p s ，a n d u t i l i z i n gg r o u p c o n n e c t i v i t y , p r o p o s e sas e l f - a d j u s t i n gm e t h o dt od e t e r m i n et h en u m b e r o fg r o u pm e m b e r s ( 3 ) t h i sp a p e rp r e s e n t st w on e wd o w n l o a dw a y s - 一t h em o r et h ef i r s t a n dr a r e s t - f i r s tf o r i n g r o u p a n db e t w e e ng r o u p st od e t e r m i n et h e 目录 摘要l a b s t r a c t 1li 目录v 第1 章绪论1 1 1 引言1 1 2 论文所做的工作2 1 3 论文的组织安排2 第2 章p 2 p 技术概述4 2 1p 2 p 技术的定义和特点4 2 1 1 什么是p 2 p 网络4 2 1 2p 2 p 网络技术的特点5 2 2p 2 p 技术的主要应用6 2 3p 2 p 网络的结构类型8 2 4b l p 现象产生的原因及资源分布统计1 0 2 4 1 搭便车( f r e er i d e r ) 现象1 1 2 4 2 幂分布中的长尾现象12 2 5 资源可用性的国内外研究现状1 3 2 6 本章小结15 第3 章基于群组的拓扑理论基础与机制的研究16 3 1 基于群组的拓扑模型1 6 3 2 覆盖网的理论基础17 3 3 群组的建立1 8 3 3 1 群组的概念18 3 3 2 结点的加入19 3 3 3 群组的建立和分裂19 3 4 群组的收缩2 2 3 5 本章小结2 4 第4 章基于群组模型的执行机制与资源分配2 5 4 1 基于群组的动态结点算法2 5 4 1 1 结点的加入2 5 4 1 2 结点的退出2 6 4 1 3 结点的失效2 7 4 2 基于群组的各种表2 7 4 3 基于群组的消息格式2 8 4 4 基于群组模型的执行机制2 8 4 4 1 群组内的执行机制与下载原则2 9 4 4 2 块表的同步3 1 4 4 3 群组之间的执行机制3 1 4 4 4 加强组之间的联系3 2 4 5f r e er i d e r 的发现和处理3 3 4 6 本章小结3 3 v 第5 章p 2 p 文件共享系统中基于群组的仿真模型研究。3 5 5 1 基本概念3 5 5 2p 2 p 文件共享系统中群组的评估3 5 5 3 基于群组的模型仿真3 9 5 3 1 设计目标3 9 5 3 2 基于群组模型的实现3 9 5 4 本章小结4 8 第6 章总结与展望4 9 6 1 总结4 9 6 2 展望4 9 参考文献5 1 附录1 攻读硕士期间发表的论文。5 6 附录2 攻读硕士期间参加的课题和项目5 7 致谢5 8 独创性声明5 9 1 1 引言 第1 章绪论 p 2 p 网络( p e e r - t o - p e e rn e t w o r k ，又称对等网络) 目前已发展成i n t e r n e t 上最重要的应用之一，吸引了学术界对其进行广泛研究。其中，p 2 p 文件共享系 统是p 2 p 网络中典型应用之一。p 2 p 文件共享系统具有动态性、扩展性、自组织性、 复杂性和负载均衡等特点。这些特点使得网络中的每个理性参与结点受到极少约 束，从而在很多情况下最大化自身网络效用，造成了非常严重的f r e er i d i n g u 问题。早在2 0 0 0 年，a d a r 等人【2 】首次表明，g n u t e l l a 网络中各个结点无论在提供 信息共享和网络维护方面都存在着极大的差异，大约7 0 的结点没有共享文件， 只有不到1 0 的结点乐于上传文件。在分析m a z e 3 j 系统时发现，在测量期间，大 约有7 0 的用户从不上传文件，1 0 的用户只共享文件，2 0 的用户既上传了文件 也下载了文件，而从不上传文件的用户的下载量占了总下载量的7 0 以上。2 0 0 3 年h s v a n u n d 等人【4 】的研究发现，在g n u t e l l a o 6 【5 】的系统中，4 2 的用户是f r e e r i d e r s 。文献 2 ，6 】在对系统进行分析时认为，系统中存在大量f r e er i d e r ，许多 结点加入p 2 p 网络的初衷是为了从对等网络中获取其他结点提供的服务，而不愿 意自己上传文件为别人提供服务。同时，作为一个为各种网络结点服务的系统， 在p 2 p 文件共享系统中，大量非热门且有价值资源和少量的热门资源应享有同等 的生存地位。两者都是能满足用户在p 2 p 文件共享系统中按需检索得到的条目， 都值得收录。也是由于资源的热门程度不同，热门资源往往比冷门资源有更多的 来源，而冷门资源由于本身的来源较少，就更容易缺失资源。所以，许多希望获 得有价值资源的用户往往由于f r e er i d e r 的存在或本身资源来源不多而导致的 来源短缺而处于b l p ( b l o c kl e e c h e rp r o b l e m ) 【_ 7 】状态，即用户无限等待已经不存 在于目前覆盖网中的资源块。如何使资源不那么稀缺，如何提高资源的可用性是 本文的目的之一，但首先第一步要做的便是需要了解资源分布情况，这样才能进 一步管理和分配资源。 p 2 p 覆盖网是各类p 2 p 应用的载体，覆盖网拓扑结构的特性是影响p 2 p 应用服 务质量最重要的因素之一，根据应用的需求和特点，调整和优化覆盖网的拓扑结 构，能够有效提高应用性能。为了保证应用系统的高可用性，即网络资源在需要 时即可使用，本文旨在构造一种基于群组的资源分布模型，该模型在群组内部， 每个结点记录各个块下载的次数，并优先下载次数最多的块，来确定组内块的分 布。在群组之间，通过搜索其他组的块的情况，优先把其他组中稀缺的块下载到 本组全部结点中，以备其他组来本组查找，达到块全局均匀化的目的，使得资源 的可用性大大提高。仿真分析表明，该群组模型能够有效地从全局角度进行资源 分配，并能根据结点的下载原则有效地识另u f r e er i d e r 结点，使群组中合作的结 点具有较高的结点满意度。 本文得到国家自然科学基金项目“超级非结构化( s u p e r p e e r ) p 2 p 网络动态 层次优化机制研究( 6 0 6 7 3 1 7 9 ) 和浙江省自然科学基金重点项目“自组织网络 中动态层次管理模型与信息处理算法研究( z 1 0 6 7 2 7 ) ”的支持。 1 2 论文所做的工作 ( 1 ) 分析了p 2 p 网络及p 2 p 文件共享系统的特点，应用和资源分布的统计特性。 ( 2 ) 分析了p 2 p 网络中的b l p 现象及其产生原因，总结了现有的国内外文献对于 b l p ，f r e er i d e r 现象所采用的机制及其特点。 ( 3 ) 总结p 2 p 覆盖网拓扑结构的特性，针对割点问题，提出了基于群组的p 2 p 共享 模型，保证群组间的连通性，并进一步提出根据下载文件大小和加入群组速 度的确定群组组成员数的方法。 ( 4 ) 提出了基于群组的模型实现机制，构造了群组内部和群组之间的下载方式， 并利用新结点分析出f r e er i d e r 结点，提高资源的可用性。 ( 5 ) 对所提出的基于群组的p 2 p 共享模型进行仿真，证明模型的可行性。 j 1 3 论文的组织安排 论文共分六章，各章的内容安排如下： 第一章为绪论，概括地介绍了本文的研究背景和p 2 p 的特点，以及本文的主 要研究内容和组织结构。 第二章介绍t p 2 p 的定义、特点、应用、分类、b l p 现象，并进一步分析其产 2 lllllfl一 生原因搭便车行为与长尾现象，总结了现有的针对b l p 问题和f r e er i d e r 行 为的解决方法及其特点。 第三章介绍了覆盖网的基础理论，提出基于群组p 2 p 文件共享模型，保证群 组间的连通性，并进一步提出根据下载文件的大小与加入群组速度的自动调节群 组组成员数的方法。 第四章提出了基于群组模型的执行机制，构造了各种消息格式与执行所用的 表，介绍了群组内部和群组之间的下载原则与同步机制，并利用该原则分析出 f r e er i d e r 结点，群组间联系并确定全局的最稀缺资源，提高资源的可用性。 第五章对本文提出的群组模型构造了仿真实验环境，通过仿真实验来检测和 分析它的性能。 第六章对本文进行总结并进一步展望未来。 第2 章p 2 p 技术概述 近年来，i n t e r n e t 得到了飞速的发展，并逐步成为人类现代工作和生活中不 可缺少的重要组成部分。从上世纪末开始，p 2 p 技术模式迅速在i n t e r n e t 上兴起， 短短数年间已经发展出众多广受用户欢迎的应用，成为i n t e r n e t 上最重要的应用 模式之一。同时，p 2 p 技术也受到了工业界和学术界的普遍关注，成为信息服务 与技术研究领域的热点。 2 1 p 2 p 技术的定义和特点 2 1 1 什么是p 2 p 网络 因特网是最大的计算机网络，同样，它自诞生以来一直存在着集中式和分布 式两种不同的工作方式。客户服务器模式( c l i e n t s e r v e r 模式，简称c s ) 是 i n t e r n e t 上最传统，最成熟的集中式工作模式，许多重要的因特网应用协议( 如 h t t p 、f t p 、s m t p 等) 采用了这一模式。在这种集中式的模式下，服务器将一直 运行，被动地等待客户的主动接入，客户将请求发给服务器，服务器返回给客户 所要的信息。客户服务器模式在因特网的最初阶段工作得非常好，然而，随着 因特网在规模上不断膨胀，在功能上不断扩展，服务器的负担越来越重，客户 服务器模式的低效率与难以扩展的缺陷暴露出来，它不再能适应需要极高效率与 巨大规模的现代因特网。 当传统的客户服务器模式不再能适应现代因特网需求的时候，人们将目光 重新放回到长久被忽视的分布式系统上，对等模式( p e e r - t o - p e e rm o d e ，简称p 2 p ) 正是在这种情况下受到重视并很快成为研究热点。对等模式的本质思想在于打破 传统的客户服务器模式，让一切网络成员享有自由、平等、互联的功能，不再 有客户、服务器之分，任何两个网络结点之间都能共享文件、传递消息。所以结 点分布式地自组织成一个整体的网络，因此，它能够极大程度地提高网络效率， 充分利用网络带宽，开发每个网络结点的潜力。图2 1 反映出从c s 到p 2 p 的转 变，p e e r s 之间的逻辑连接构建在物理连接的基础上。 4 lllliiillilllilliillilliiliiilliillilll 图2 - 1 从c s 到p z p ( 实线表示物理连接，虚线表示逻辑连接) 2 1 2p 2 p 网络技术的特点 从以上的定义中本文也可以总结出p 2 p 网络技术的一些特点： ( 1 ) 自由：在p 2 p 网络中，对等结点执行什么操作、采取什么样的行为、与其 毋 他结点交换哪些信息，由其本身自由决定，而不受限于其他网络结点。一方面， 由于信息的传输分散在各结点之间进行而无需经过某个中间环节，用户的隐私信 息被窃听和泄漏的可能性大大缩小。另一方面，由于采用分布式散列表的p 2 p 网 蕞 络特有的匿名性，保护了发布者的信息，使得用户能够更加自由，没有后顾之忧 地参与到网络中来。多 ( 2 ) 平等：平等是p 2 p 网络最重要的特性。平等意味着在一个系统中，虽然能 力不尽相同( 即结点间的“异构性 ( h e t e r o g e n e i t y ) ) ，但所有成员在功能、地位 上都是平等的，没有谁拥有特权，没有谁能控制或限制其他结点。就网络组织方 式而已，平等指的是打破传统的客户n 务器模式，取消服务器这一特权结点的 存在，让所有网络成员之间平等地交流信息。网络中的资源和服务分散在所有结 点上，信息传输和服务的实现都直接在结点之间进行。平等性是p 2 p 网络的工作 基础，p 2 p 网络对网络带宽的高效利用、对网络结点潜力的充分开发以及可扩展 性等，都是基于平等性的。 ( 3 ) 互联：互联的本质原因是p 2 p 在应用层构建了覆盖网络( o v e r l a y n e t w o r k ) 。封装下面的三层，让p 2 p 网络的研究者和开发者不必关心下面三层是 如何工作的，而仅仅去考虑应用层覆盖网络的工作情况，将精力集中于覆盖网络 的设计、优化上。但有时由于应用层建立的覆盖网与底层实际的物理网络的工作 情况不可能完全相同，如图2 2 中，覆盖网上的一条逻辑连线a e 对应物理网上三 条物理连接：a c ，c d 和d e 。所以在实际工作中仍要兼顾网络底层，尽可能地减少 两者之间的差异。p 2 p 网络中任意两个对等结点间都可以建立连接，这是覆盖网 上的一条逻辑连接，它通常对应物理网上的一条i p 路径( 或者说是传输层的一个 t c p 连接) 。在c s 模式下客户只能和服务器建立一条p e e r - t o - p e e r 的连接。互联 性源于平等性，它也是p 2 p 网络高效率、高可扩展性的重要基础。 p 2 p 覆盖网 底层物理层 图2 2p 2 p 覆盖网和底层物理网络不一致( 虚线表示逻辑连接，实线表示物理连接) 2 2p 2 p 技术的主要应用 p 2 p 技术提供了在各种应用领域中管理资源的一种可选方式。本节将重点给 出使用p 2 p 网络来管理多种类型资源的主要应用。这些资源即是文件、多媒体、 信息、存储等。 1 文件共享 可以说p 2 p 文件共享的需求是直接引发 p 2 p 技术的产生与开发的热潮。用户 可以直接与p 2 p 网络中任意结点进行文件的交换，而不是通过服务器。p 2 p 系统自 动发现最新的文件列表，用户可以检索复制共享的文件，而发布者无需担, 心p 2 p 所引发的各种安全问题。p 2 p 文件共享系统从最初的n a p s t e r 8 1 、g n u t e l l a 【9 】、 k a z a a 、f a s t t r a c k 、e d o n k e y 发展到现在的b i t t o r r e n t 、t h u n d e r 、m a z e 、e m u l e 等，几乎每一个系统都得到了广泛的应用。目前基于p 2 p 文件共享系统的通信量 6 lliiillllillllillllillllll-iilllliiltiillli卜 已经占据了网络中绝大部分的流量，它使得数据大规模地快速分发成为可能，并 有效地克服了传统c s ( c 1 i e n t s e r v e r ) 或b s ( b r o w s e r s e r v e r ) 结构所带来的带 宽瓶颈和单点故障问题。p 2 p 文件共享技术是p 2 p 应用的主流和重点，仍然具有很 大的应用空间。 2 多媒体传输 p 2 p 技术适应了多媒体传输对网络带宽的巨大需求，因为所需要的大量带宽 被所有共享多媒体文件的用户分担，并且用户之间互相提供数据流量，所有当用 户数急剧增加时，通常发生的情况是：用户越多，传输越好。p 2 p 多媒体传输最 突出地表现在网络语音传输和网络电视，现在国内有不少p 2 p 网络电视软件，如 p p l i v e ，a n y s e e ，q q 直播等，其中一些也相当流行。 3 实时通信 如今实时通信软件功能不仅包括最基本的文件传送，还包括声音、视频、在 线游戏等，它们对传输率、时延的高要求，注定选择用于用户间直接建立连接的 p 2 p 方式。最常见的实时通信软件如q q ，m s n ，j a b b e r 等，颇受大家的欢迎。 4 协同工作 p 2 p 技术的出现，使得互联网上任意两台计算机都可以建立实时的联系，从 而建立了一个安全、共享的虚拟空间，供人们进行各种各样的活动，这些活动可 以是同时进行，也可以是交互进行。因此基于p 2 p 技术的协调工作受到了极大的 重视，目前最典型的协同工作项目是g r o o v e 1 0 1 虚拟办公室。 5 分布式数据存储 在网络上将存储对象分散化存放，而不像现在放于专用服务器。这样减轻了 服务器负担，增加了数据的可靠性和传输速度，典型的p 2 p 分布式数据存储系统 女 i c f s ，p a s t 等等。 6 p 2 p 搜索引擎 p 2 p 搜索引擎是指能想百度、g o o g l e 刃f f 样包罗万象、基于w e b 的通用搜索引擎。 p 2 p 技术使用户能够深度搜索文档，而且无需通过w e b 服务器，也不受信息文档格 式和宿主设备的限制。可以说，p 2 p 为互联网的信息搜索提供了全新的解决之道， 被很多人认为是第三代搜索引擎的开发技术。 7 2 3p 2 p 网络的结构类型 p 2 p 系统的拓扑结构是指覆盖网中结点之间互连的方式，是p 2 p 系统的重要特 征，p 2 p 的研究一直随拓扑结构变化而不断发展。因此，目前国内外研究者通常 根据拓扑结构对p 2 p 系统进行分类。 第一类，中心式p 2 p 网络，它是c s 和p 2 p 两种模式的混合。 在第一代p 2 p 网络中，n a p s t e r 是其中最典型的代表。但它是朴素的，留下了 许多缺陷。在后起的混合式p 2 p 系统中都采用了一些增强机制来提高网络的效率， 女h b i t t o r r e n t 提高文件分片机制，限定用户在下载的同时必须上传以杜绝自私结 点的存在，这些都提高了网络的工作效率，当然也增加了网络的复杂性。但是无 论是：n a p s t e r ：还是b i t t o r r e n t ，都是星型的拓扑结构，服务器仍然是整个网络的核 心，存在单点失效和带宽瓶颈的问题。其结构拓扑如图2 3 表示。 图2 - 3 星型结构n a p s t e r 、b i t t o r r e n t 第二类，无结构p 2 p 网络，它以分布、松散的结构来组织网络，故称“无结 构”。 在纯粹的p 2 p 网络中，结点分布于世界各地，没有任何中心单元，所以网络 没有单点失效问题。任何一个结点的退出或者出现故障，都不会造成显著影响， 且具有幂律模型的特点。在纯粹p 2 p n 络中，最具典型的是g n u t e l l a 1 1 。1 4 】。由于 g n u t e l l a 采用了泛洪( f l o o d i n g ) 的查询方式，这使得搜索直径变得不可控，因此 其他研究者采用有限的t t l ，随机漫步或有选择转发算法来提高无结构p 2 p 网络 的搜索效率。更进一步，k a z a a 1 5 1 和e d o n k e y 采用超级结点来构建双层的的p 2 p 网络，而作为其核心的超级结点层自组织成无结构网络，且由于超级结点很少， 往往采用泛洪的方式路由，因此，超级结点的拓扑结构也属于无结构的p 2 p 网络。 其结构拓扑图如2 4 表示。而本文所提出的基于群组的模型也可以归属为这一类 8 lllilllillililililillililililiiillllllll 型，因为群组之间的查询也是采取泛洪的方式。 ( 1 )( 2 ) 图2 4 ( 1 ) 随机图结构g n u t e l l a 、f r e e n e t n 6 1 ( 2 ) 双层结构k a z a a 、e d o n k e y e m u l e 第三类，结构化p 2 p 网络，它以准确、严格的结构来组织网络，并能高效地 定位结点和数据。 结构化p 2 p 网络的最大特点在于它们都有一个严格的覆盖网络拓扑结构，且 都使用分布式散列表( d h t ) 来将结点、数据对象映射到覆盖网中，且每个结点都 有一个路由表来保存数据和结点的信息。常用的结构化覆盖网如图2 5 所示，有 带弦环的拓扑结构，如c h o r d 1 7 】，所有结点都被组织在一个环上，其功能是取得 当前结点的前驱和后继；如t a p e s t r y 1 8 1 ，p a s t r y 1 9 1 等的超立方体的拓扑结构， 每层维护匹配n o d e i d 不同长度前缀的结点：而基于跳表( s k i p l is t ) 的s k i p n e t 2 0 1 模型提供结点路由、对象语义两方面的局限性，这是以前的结构化p 2 p 网络都没 有做到的。当然，结构化p 2 p 网络也有其缺点，即对于结点的失效处理。因为网 络的动态性和不确定性，很多情况是结点突然离开了，而其他结点并不立刻了解 结点的离开，所以网络路径失效了。处理失效的方法，通常是周期性地联系路由 表的邻居，看是否可达，如果不可达，再进行路由表修复。这也是结构化p 2 p 系统 最大的开销所在。 0 0 0 o o l ( 2 ) 图2 5 ( 1 ) 带弦环结构c h o r d 。( 2 ) 超立方体结构- t a p e s t r y ，p a s t r y ，s n 代表超级结 点，l 代表叶子结点( 3 ) 跳表结构s k i p n e t 9 第四类，混合式p 2 p 系统，它最初的目标是在不同服务中将p 2 p 和客户端一服 务器体制合并，但目前已经被扩展到了更大范围的组合。 j x t a 2 1 1 本身的含义是将东西并排放置，意思是相互连接或强调它们之间的 不同。它定义- f p 2 p 应用的一个协议通用集合，采用角色分离的机制，其目的是 降低重叠网的管理开销。b r o c a d e l 2 2 1 是一种混合重叠网协议，利用d h t 重叠网构 造“超级结点”层。其关键点是超级结点的选择及d h t 的映射问题。s h a r k 2 3 】是 一种基于d h t 的进行关键字搜索的方案，查询最初在网络的结构化部分进行转发， 以达到目标的非结构化子网。之后，它们被广播到提供匹配项目的兴趣结点集合。 o m i c r o n 2 4 】引入一种双重身份机制来处理对等结点能力和用户行为的异构性。这 种机制将每个结点的贡献于其资源能力相适应，并通过为承担某种角色的对等结 点提供合适的奖励，以最大化效率。o c e a n s t o r e 2 5 l 是构建于t a p e s t r y 之上的p 2 p 存储系统，它利用b l o o m 过滤器【2 6 l 对于热门请求能快速回答和允许错误回答的特 点提升t a p e s t r y 的路由性能。p i e r 27 】是构建于c a n 之上的一个分布式查询引擎， 是基于流行项目的低开销搜索。该技术识别并仅将稀有项目发布至i j d h t 中，而流 行项目则采用泛洪技术或g n u e ll a 网络定位。 混合系统一方面增加了系统的复杂性，因为它们是多种方法的组合：另一方 面，混合模型显示出对环境条件的高度适应性。通常地，设计时考虑了这些条件， 且它们体现一定场景优势，性能得到极大的提高。很明显混合模式是能解决大规 模动态地、异构地p 2 p 系统的一种有效的手段。本文所提出的基于群组模型与双 层模型一样是基于g n u t e l l a 上的群组，是改善性能的无结构网络，通过改善资源 的副本数和分布，来提高下载的效率。 2 4b l p 现象产生的原因及资源分布统计 b l p 现象是指用户常常无限等待某个已不存在于网络中的资源块的情景，即 是一种网络资源的可用性得到不到满足的现象。可用性是指网络资源在被需要时 即可用。产生这种现状的原因主要有以下两个方面：一是f r e er i d e r 行为在p 2 p 网络中日趋严重。二是经统计发现，文件共享中的文件资源总体符合幂分布中的 z i p f 定律的特征。 。这个定律是美国语言学家z i p f 在1 9 3 2 年发现的，即经常被使用的词汇只占词汇总量很少一部分。 l o 2 4 1 搭便车( f r e er id e r ) 现象 f r e er i d e r 行为在p 2 p 网络中日趋严重，它对网络的健壮性、可用性等都产 生了重大的负面影响。早在2 0 0 0 年，a d a r 2 对用户数量超过百万的大型p 2 p 网络 g n u t e ll a 一天的流量进行了测量，并把对等网络结点的只享受信息资源服务而不 为系统作贡献的行为称为搭便车( f r e er i d i n g ) 。存在搭便车行为的结点称为搭 便车者( f r e er i d e r ) 。而s a r o i u 1 3 1 进一步发现，在g n u t e l l a 中，有超过5 0 的用 户连接时间低于1 小时，不到1 0 的用户连接时间高于6 小时。就共享文件数而言， g n u t e l l a 中约有2 5 的用户从不共享任何文件，约7 5 的用户共享文件低于1 0 0 个， 只有7 的用户共享文件数超过i 0 0 0 个。由此可见，对等结点的f r e er i d i n g 行为 虽然它的目的是为了节约自身资源，但对于网络的高效工作是不利的。而行为主 要表现在以下两个方面：一是在线时间短，用户根据需要，自愿地加入p 2 p 系统， 随后又在任意时间离开，很多用户只在自己有需求的时候加入系统，下载完成便 立刻退出，表现的形式就是长时间离线。在一些情况下，表现为很多结点频繁地 进入或离开系统，造成系统中可提供资源的服务质量产生剧烈变化，使系统的服 务质量明显降低，大大减少了系统资源的可用性。二是贡献的带宽低，许多用户 在利用p 2 p 网络下载文件时往往提供很少的带宽或不提供带宽。这种做法不但影 响t p 2 p 系统资源的平衡，而且降低了网络的性能。由于大部分的下载请求被定 向到这些少量结点，使得这些结点实际上成为集中式的服务器，但是这些结点并 不会像真正的服务器那样长期留在系统里，一旦它们离去，那么资源又将变得稀 少，不利于系统的发展。图2 6 表示了搭便车现象对网络吞吐率的影响 z 8 】。 对等麓珞中搭缆职嚣点所占比铡 图2 6 搭便车者比率对网络吞吐率的影响心砌 l l ，弘 口? 2 4 2 幂分布中的长尾现象 幂分布【2 9 。3 1 】在数学上是一种双曲线，其表达式为：p ( k ) c k 一，其中卿， 为常数。但在自然界和人类社会中这种分布广泛存在，其现实的主要表现为少量 个体作出大量贡献。长尾现象是指统计学中幂分布特征的形象化表达，表示事物 的分布近似地服从幂分布具有很长尾部的特性。如图2 7 表现为2 0 的产品受到了 8 0 的人的欢迎，而8 0 的产品只受蛰j 2 0 的喜爱。在i n t e r n e t 中，存在着8 0 的维 基条目只由2 0 w i k i 贡献的人；8 0 的互联网流量来自2 0 的用户；8 0 的音乐下载 来源于2 0 的曲目等等。在p 2 p 网络中，这些状况仍然存在。研究发现，p 2 p 网络 无论在网络拓扑结构还是资源传输特性方面与幂分布都有直接的相关性，在目前 的统计分析中已经发现在许多p 2 p 文件共享系统中的资源的传输特性具有明显的 长尾分布形式，s a r o i u 1 3 】通过爬行工具测量g n u t e l l a 网络，表明g n u t e l l a 的资源 查询分布符合z i p f 分布，表明了某个共享资源受欢迎程度越高，则查询越多，当 网络因子小于3 时，g n u t e l l a 系统的容错性比较好。在文献 3 2 】中也表明了在 b i t t o r r e n t 网络中，长尾现象十分明显，副本数量少于1 0 0 的文件占全部文件数 量的9 6 ，而超过1 0 0 的部分不足4 ，资源严重缺乏。张云飞等人【3 3 】在国内某骨 干网运营商的核心路由器上对p 2 p 流量进行了测量，他们的测量结果表明，2 0 7 的p e e r s 传输了9 0 的p 2 p 流量，2 3 的p e e r s 传输了5 0 的p 2 p 流量，而且p 2 p 流量 在不同p e e r s 间的分布服从重尾分布。但是，在目前的p 2 p 文件共享系统中往往忽 视了数量占大多数的有价值的冷门资源以及用户对于资源文件需求的差异性，忽 视了冷门资源同热门资源一样的平等性，忽视了冷门资源同样具有重要的价值， 使得冷门越冷，热门越热。因此，没有对冷门资源有相应的资源预留措施，使得 原来就少的冷门资源变得更少。 1 2 lll【ii_j 图2 7p 2 p 中的长尾现象 2 5 资源可用性的国内外研究现状 长尾现象与f r e er i d e r 共同存在的直接结果就是资源数量变少，资源可用性 变差。由于系统中共享的文件数量减少，最后只能提供一些热门资源的服务。所 以对于大量的由于用户兴趣差异性造成的请求，系统因为不能提供相应的服务而 会使大量用户离开。如果高连接的结点又再离开系统，那么系统性能会变更差， 甚至导致系统崩溃。 许多国内外的研究和应用从不同的角度来提高资源的可用性。总的来说，可 以分为三类：一是采用激励的方式；二是采用增加副本的方式；三是通过构造拓 扑模型提高查找效率的方式。 在p 2 p 系统中，为了让理性的用户能贡献自己的带宽，往往采用激励机制 b i t t o r r e n t 3 4 】采用了t i t - f o r - t a t 的方法，即在用户上传时，使用“报恩 的 方法，对方给我的下载速度越快，我给他上传的速度也越快。e m u l e 和e d o n k e y 同样采取直接互惠的方式，但并不是采用一次下载的短暂性激励，它考虑了对 等结点的历史记录并进行积分排队，提供差异服务。但是，统计表明大约只有 3 的用户会上传给曾经传过的用户，因此f r e er i d i n g 行为还是很容易产生。可 见，基于互惠模式的激励方式只能在p 2 p 文件共享的局部、热门资源和短时间有 效，缺乏整个系统的扩展性和覆盖性。文献 7 采用了一种g q b i t s t o r e 的方法，即 让结点通过第二次拍卖的方式贡献自己的资源为大家存储所需的块，以缓解 b l p i d 3 题。m a z e 3 s 采用积分制度，依据积分的不同提供差异服务。这是一种基 于市场机制的虚拟货币类积分激励机制。用户可以通过奉献来提高自己的积分， 系统通过积分来提供差异性服务。但是在积分激励过程中，很难辨别是否存在 合谋欺骗现象，如两个或多个账号长期频繁虚假交易，共同骗取积分。l a n d a 等人【3 6 】提出了p l e d g e r o u t e 的积分累计机制，根据结点对覆盖网络的贡献计算 出相应的分值。这个系统可以抵御三种不同类型的攻击，并采用激励机制对贡 献度越多的用户保证更好的服务。 为了能提高冷门资源的可用性，数据复制是常用的方式之一。在无结构p 2 p 网络中，有三种常用的复制策略：宿主复制【37 j ( o w n e rr e p l i c a t i o n ) 、随机复制 ( r a n d o mr e p l i c a t i o n ) 和路径复制( p a t hr e p l i c a t i o n ) 。在宿主复制方法中，结 点保持成功查询所获取数据的副本，然后该结点便可以作为服务提供者为其他结 点提供数据服务。因此，系统中数据副本的数量与该数据被访问的频率基本成正 比关系。在随机复制方法中，数据副本按照一定的概率随机选取结点部署副本。 随机复制需要了解覆盖网络结构，而p 2 p 系统中结点仅仅知道其邻居结点信息， 因此，随机复制在大部分情况下不容易实现。路径复制是指在搜索成功之后沿消 息转发路径逆向沿途复制。f r e e n e t l 3 8 】是采用路径复制的典型系统。f r e e n e t 通 过大量路径复制和l r u 文件副本淘汰使具有相近i d 值的文件所在结点聚集，形成 基于i d 的路由方向感。以上的复制策略采用的是边访问、边淘汰、边复制的模式 增加热点数据副本在系统中的分布“密度”，提高热点数据的查询效率。但是， 相应地，热点数据的大量副本会占用不经常被访问数据的存储空间，使得冷门的 数据的可用性降低。文献 3 9 】与上述的依据数据副本数量分配来优化数据副本部 署的传统方法不同，它是根据覆盖网络特征，区别发现结点的不同“地位 ，根 据流行程度对数据进行位置交换，主动改变覆盖网络中的数据位置配置结构，提 高每次消息转发的效率，从而提高p 2 p 网络的性能。 p 2 p 覆盖网拓扑技术【4 0 】的研究对提高互联网应用效率和可用性具有基础性 作用和意义。在非结构化p 2 p 网络中，为了减少泛洪流量，k a z a a 、g n u t e l l a o 6 等采用了双层结构，即引入超级结点( s u p e r n o d e ) 来提高网络的效率和可用性。 刘云浩 4 1 1 等提出了d l m 模型来保证超级结点和叶子结点的最佳比例，并且能动态 地将生命周期较长和能力强的结点分配为超级结点，而时间短和能力弱的结点指 定为叶子结点。s i n g h 等人【4 2 】提