（计算机应用技术专业论文）p2p网络中避免集散节点形成的控制机制研究.pdf

硕士擘位论文 m a s t e r st h e s i s 中文摘要 集散节点分布在p 2 p ( p e c r - t o p c e r ) 网络中必定会降低整个p 2 p 系统的服务性能 和质量，加重了网络的脆弱性。因此，如何避免集散节点的形成及控制集散节点的 数量，成为p 2 p 网络可持续性健康发展的关键问题之一。本文首先介绍了近年来对 p 2 p 网络中的集散节点现象所进行测量的结果，说明了集散节点的存在是p 2 p 网络 的一种特性，并阐述了集散节点对p 2 p 网络所产生的各种不良影响，之后介绍了基 于抑制搭便车行为和基于拓扑控制的两类控制集散节点的方法。 由于当前对集散节点问题的研究主要集中在搭便车行为的抑制机制上，本文系 统地介绍和分析了目前已有的多种抑制机制。针对这些抑制机制存在的不足，本文 提出了一种公平效用函数以解决以往效用值计算中的非公平性问题。本效用函数同 时考察了节点对系统的绝对贡献值与节点自身的物理性能，并将绝对贡献值分为供 给值与收益值两部分，利用层次分析法建立并求解供给值、收益值与物理性能层次 结构模型，通过求解这些模型最后确立了公平效用函数。在该效用函数的基础上又 提出了一种基于金字塔等级结构模型的集散节点间接控制机制，在系统中建立金字 塔模型，用等级制度来控制访问权限，并借助等级结构建模方法确立效用值与等级 之间的转换规则，通过用户的自主设置与管理其共享文件级别的方法来控制节点所 承受的连接数量，达到了通过抑制搭便车行为来控制集散节点形成的目的。该控制 机制还能解决新用户所能享受的服务质量、对搭便车者过于严厉和惩罚的非透明性 等问题。仿真证明了本间接控制机制的有效性与优越性。 本文最后提出了一种通过控制p 2 p 网络的逻辑拓扑结构来避免集散节点形成的 控制模型，其主要是对准集散节点进行层次化处理，根据可再支撑连接数的概念在 网络中找出备份节点，将准集散节点与备份节点建立二叉树逻辑层次结构，然后再 根据p 地址差值来转发新的连接请求至备份节点，仿真实验证明了该层次结构控 制模型能有效减少网络中的集散节点数量，从而增强了网络的抗脆弱性能力，确保 了网络能持续健康的发展。 关键词：p 2 p 网络；集散节点；搭便车行为：公平效用函数；金字塔模型；层 次结构模型 硕士学位论文 m a s t e r 。st h e s i s a b s t r a c t t h ee x i s t e n c eo ft h eh u b si np e e r - t o - p e e r ( p 2 p ) n e t w o r kc o u l dg r e a t l yi n c r e a s et h e n e t w o r k sv u l n e r a b i l i t ya n db l e m i s ht h ep e r f o r m a n c ea n dt h eq u a l i t yo fp 2 p s y s t e m t h i s t h e s i sf i r s t l yi n t r o d u c e st h em e a s u r e m e n t so fh u b si np 2 pn e t w o r k si nr e c e n ty e a r sa n d g e t st ot h er e s u l tt h a tt h ee x i s t e n c eo fh u b si sac h a r a c t e r i s t i co fp 2 pn e t w o r k s i ta l s o s u m m a r i z e st w ok i n d so fc o n t r o l l i n gm e c h a n i s mf o rh u b s , t h et o p o l o g yc o n t r o la n d f r e e - r i d i n gr e s t r a i n t b e c a u s et h er e s e a r c h e sa b o u th u b sa r em a i n l yi nr e s t r a i nm e c h a n i s m so ff r e e - r i d i n g ， t h es e c o n ds e c t i o no ft h i st h e s i sp r e s e n t sa n da l s oa n a l y s e st h ep r e s e n t e dr e s t r a i n m e c h a n i s m s i no r d e rt oe l i m i n a t et h ed e f e c t i o n so ft h e s er e s t r a i nm e c h a n i s m s ，t h i st h e s i s g i v e so u taf a i ru t i l i t yf u n c t i o nb yt a k i n gi n t oa c c o u n tt h ea b s o l u t ec o n t r i b u t i o na n d p h y s i c a lp e r f o r m a n c es i m u l t a n e o u s l yw h i l ec a l c u l a t i n gt h eu t i l i t yv a l u e t h ea b s o l u t e c o n t r i b u t i o ni sd i v i d e di n t ot w op a r t , s u p p l yv a l u ea n dp r o f i tv a l u e w i t ha n a l y t i c h i e r a r c h yp r o c e s s ，w eb u i l dt h es u p p l yv a l u em o d e l ，p r o f i tv a l u em o d e la n dp h y s i c a l p e r f o r m a n c em o d e l ，a n dt h e nw es e t t l et h ef a i ru t i l i t yf u n c t i o nb yc a l c u l a t i n gt h e s e m o d e l st or e s o l v et h ep r o b l e mo fu n f a i ru t i l i t yv a l u e b u i l d i n go nt h i sr e s u l t , w ep r o d u c e a ni n d i r e c tc o n t r o l l i n gm e c h a n i s mo f h u b si np 2 pn e t w o r k sw i t hp y r a m i d a lr a n ks t r u c t u r e b a s e do nf r e e r i d i n gr e s t r a i n tm e a s u r e m e n t i nt h i sm e c h a n i s m , e a c hu s e rh a sar a n k a c c o r d i n gt oi t sc o n t r i b u t i o na n di tc a nj u s tv i s i tt h ec o r r e s p o n d i n gr a t i n gf i l e s 、析mi t s r a n ki nt h es y s t e m u s e r sc a l ls e ta n dm a n a g et h er a t i n g so ft h e i rs h a r i n gf i l e s a u t o n o m o u s l y t h er a n ks t r u c t u r ei sp y r a m i d a lt oe n a b l et h a tt h ep r o b l e mo fh u b sw o u l d b es o l v e db yu s e r ss e l f - m a n a g e m e n t t h i sc o n t r o l l i n gm e c h a n i s ma l s oc a ns o l v et h e p r o b l e m so f t h eq o so f n e wu s e l - s ，t h eo v e rs t r i c t n e s sa n dt h eu n o p e n e dp u n i s h m e n t l a s t l y , t h i st h e s i sp r e s e n t san e wm o d e lt oa v o i dg e n e r a t i n gh u b si nt h en e t w o r k sb y c o n t r o l l i n gt h el o g i c a lt o p o l o g yo fp 2 pn e t w o r k s t h i sc o n t r o l l i n gm o d e li st oh i e r a r c h i z e t h eb e c o m i n gh u b s 1 1 地b e c o m i n gh u b ss h o u l ds e a r c hi nt h en e t w o r ka n dc h o o s eo u tt w o s t a n d b yn o d e sb yu s i n gt h ec o n c e p to fr e m a i n d e rc a p a c i t yo fs u p p o r t i n g m o r e c o n n e c t i o n s t h eb e c o m i n gh u b sa n dt h es t a n d b yn o d e sm u s tb ei i l a d ei n t oab i n a r yt r e e l o g i c a l l y w h e nc o m e st h en e wr e q u e s t , t h eb e e o m - i n gh u b sc o u l dt r a n s m i tt h er e q u e s tt o o n eo ft h et w os t a n d b yn o d e sw i t ht h er u l eo fi pa d d r e s sm a 唱i n t h i sc o n t r o l l i n gm o d e l c a nc o n t r o lt h eh u b sa n da v o i dg e n e r a t i n gt h eh u b si np 2 pn e t w o r k se f f e c t i v e l y k e yw o r d s ：p 2 pn e t w o r k ；h u b ；f r e e r i d i n g ； s t r u c t u r e ；h i e r a r c h i c a l 硕士学位论文 盹s t e r st h e s i $ 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：桶煮日期：? 产月7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权 中国科学技术信息研究所将本学位论文收录到 中国学位论文全文数据库，并通 过网络向社会公众提供信息服务。 作榴：撷窟拊名：去叫 日期：扣了年6 月1 7 日日期：铂净石月当日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库一中全文发布，并可按q 章程 中的 规定享受相关权益。园塞途塞理交蜃造卮! 旦坐生i 旦= 生；旦三生筮查! 作者签名：桶寿 旧期洳产舌月7 日 导师签名： 日期： 未l 蹭 1 年6 a8 日 1 1p 2 p 概述 第1 章绪论 p 2 p ( p e e r - t o p e e r ) 是一种分布式网络，网络的参与者共享他们所拥有的一部 分硬件资源( 处理能力、存储能力、网络连接能力、打印机等) ，这些共享资源需 要由网络提供服务和内容，能被其它对等节点( 直接访问而无需经过中间实体。 在此网络中的参与者既是资源( 服务和内容) 提供者( s e r v e r ) ，又是资源( 服务和 内容) 获取者( c l i e n t ) i l j 。p 2 p 网络也称对等网络或重叠网络。 p 2 p 技术打破了传统的c l i e n t s e r w r ( c s ) 通信模式。如图1 1 所示，c s 模式以 具有强大处理能力和高带宽的高性能服务器为核心，所有客户机与服务器进行通 信，服务器为网络中的其他客户机提供处理能力及其他应用，客户对网络计算能力 和数据存储的贡献微乎其微。如果两个客户机之间要传送文件，需要先将文件传至 服务器，然后e hj l t 务器传给另一个客户机。如果服务器繁忙，文件传送将变得十分 缓慢。严重时，服务器“单点失效”，文件将无法传送，整个网络的通信将中断。 当网络节点数目大量增加时，服务器负载也随之线性增加，成为网络瓶颈，由于连 入同一服务器的客户数增多，通信效率平均而言一定会下降，并且也增加了服务器 过忙和故障的概率 2 1 。 煮明 惑箩 鲷 童毋 矗岬 图11c s 模式的网络结构图12p 2 p 模式的网络结构 相比之下，p 2 p 技术弱化了服务器的作用，没有集中式的控制，允许任意两个 对等节点之间平等的互联，节点之间通信不需要经过一个固定的服务器，在通信的 过程中不受其他节点的控制与影响，数据传输速度通常只取决于同络带宽( 如图 硕士学位论文 m a s t e r st h e s i s 1 2 ) 。p 2 p 网络的主体是网络边缘节点，即临时性的动态节点，p 2 p 技术能充分地 利用网络边缘资源，开发了每个网络节点的潜力，使得整个网络可以被用作具有海 量存储能力和巨大计算处理能力的超级计算机。同时，p 2 p 模式具有非常高的可扩 展性，当网络节点数大量增加时，随之增加的通信开销被更多的节点分担，每个节 点承担的负载并不会增加很多，并且在网络规模增大时，p 2 p 网络不需要增加额外 的设备。此外，p 2 p 技术将系统中的资源分散到了各个节点上，其所使用的分布式 散列表又将节点和数据均匀分布到了覆盖网上，因此，p 2 p 技术具有与生俱来的负 载均衡方面的优势。总体来看，p 2 p 技术提高了网络工作效率，充分利用了网络带 宽，开发了每个网络节点的潜力，并具有良好的容错性和非常高的可扩展性网。 由于在工作模式上所具有的优势和对于现代i n t e r a c t 的适应性，p 2 p 技术得到 了快速的发展，在应用领域和学术领域均获得了广泛的重视和巨大的成功，目前占 据了i n t e m e t 超过一半的带宽资源。p 2 p 技术正不断应用于文件共享系统、高性能 计算、多媒体传输、协同工作、实时通信、搜索引擎、分布式数据存取、网络游戏、 网络电视等领域【2 j 。 1 2p 2 p 网络中集散节点与搭便车行为的存在 2 0 世纪7 0 年代以来，对等网络技术得到了迅猛发展。然而，a d a r 和h u b e r m a n 于2 0 0 0 年在文献 3 q a 首次提出，根据他们对大型p 2 p 分布式文件共享系统g n u t e l l a 在2 4 小时内的流量所进行的主动测量发现：在该对等网络中接近7 0 的用户从来 不提供文件给他人共享；网络中5 0 的文件查询请求反馈结果来自于l 的用户。 而且，他们还发现搭便车行为甚至在对等网络的不同域之间也存在，因此没有一个 用户组对整个系统的贡献明显多于其他的组，志愿共享文件的节点所共享的文件也 不是其他用户所想要的资源。文献最后指出：这种少数节点为广大用户服务的现象 必定会降低整个网络系统的服务性能和质量，加重网络的脆弱性。该文献的统计结 果表明，许多节点只是想利用p 2 p 系统获取自己所需要的资源，而并不愿意为系统 中的其他用户共享下载资源或提供服务。a d a r 和h u b e r m a n 把p 2 p 网络中节点的这 种自私行为称为搭便车，把这些表现出自私行为的节点称为搭便车者。 文献f 3 1 自发表之后立即引起了研究者的广泛关注。m a t e ir i p e a n u ，i a nf o s t e r 等人在文献 4 1 中公布了他们在2 0 0 1 年期间对g n u t e l l a 文件共享系统的流量测量结 果。该文在文献【3 】的基础上做了更深入更准确的研究，主要表现在研究者所测量的 时间要更长一些，也更关注网络中各节点的连接度数与平均度数等特征。文中指出， 2 在2 0 0 1 年期间g n u t e l l a 系统中各节点平均维持3 4 个连接，但存在极少数的一部分 节点拥有的连接度数高达数千，甚至上万。另外，网络中所有节点的连接度数整体 上近似服从幂律分布。作者认为，因为部分节点所拥有的连接数过低，导致节点连 接度数的分布曲线与严格的幂律分布曲线并不完全相吻合，而是略有差异，所以只 是近似呈现幂律分布规律。节点的连接度数表示网络中与之建立连接请求的节点的 数量，该文所测量出的网络中各节点拥有连接度数的巨大差异与文献【3 仲报告的少 数节点为广大用户服务的现象具有一致性。文中认为少数连接数极高的节点会造成 系统较差的抗攻击能力。 美国a t & t 实验室的s u b h a b r a t as e n 和j i aw a n g 在文献 5 】中报告了2 0 0 2 年对 用户数量众多的c m u t e l l a ，f a s t - t r a c k 和d i r e c t c o n n e c t 三个对等网络的测量结果。 这三个不同的p 2 p 系统均表现出了与文献【3 】和文献【4 】的研究结果相类似的现象， 即极少数的热心节点响应着绝大多数的连接请求。同时，测量结果还指出这三个p 2 p 网络中均存在搭便车现象。该文的研究采集的是不同网络之间的边界路由器上的流 量数据，是一种不干扰p 2 p 网络自身行为的被动测量方法，且数据采集的时间长， 搜集的流量数据记录多，因此测量结果具有更好的统计价值。此外，该文不仅测量 了对等网络中的指令流数据( 查询请求和请求响应数据包等) ，还测量了数据流( 文 件内容) ，发现这两方面均存在上述现象。 d a n i e lh u g h e s ，g e o f fc o u l s o n 等人于2 0 0 5 年在文献【6 】中介绍了他们在2 0 0 5 年对g n u t e l l a 对等网络的测量和统计结果，并将该结果与文献【3 】中2 0 0 0 年的测量 结果进行了对比。2 0 0 0 年的数据表明，1 的热心节点提供的查询响应所占比率为 4 7 ，而在2 0 0 5 年，该比率上升至5 0 ；共享文件数为0 的节点所占的比率也由 6 6 上升至8 5 。对比结果表明，少数节点为广大用户服务的现象和搭便车现象在 5 年之后不是得到了有效缓解，反而是变得越来越严重，以至于少数热心节点的崩 溃或退出越来越容易导致整个p 2 p 网络的崩溃。 图1 3 幂律分布曲线( 扣2 3 ) 3 硕士学位论文 m a s t e r st h e s i s 上海交通大学的s h i c o n gm e n g ，c o n gs h i 等人于2 0 0 6 年在文献【7 】中公布了他 们对c m u t d l a 对等网络的测量和统计结果，依然是搭便车行为盛行，而为广大用户 服务的只是少数的热心节点。 从研究者对g n u t e l l a 、f a s t - t r a c k 、d i r e c t c o n n e c t 等大型p 2 p 系统的测量和统计 结果分析来看，比较一致的结论是目前p 2 p 网络中用户的个人行为存在类似幂律 ( p o w e r - l a w ) 分布的现象。幂律分布是指具有某个度为k 的节点数目与这个度k 之间 的关系可以用一个幂函数近似地表示：以七) = k 一，其中，五为常数。节点的度是 指一个节点拥有的连接数量。由于p 2 p 网络一般采用面向连接的路由机制，一个节 点若同时为多个节点提供信息和资源共享服务，从节点保持的连接数来度量，则一 个连接可抽象成一条边，同一个时间内保持连接的个数，就是该节点在p 2 p 网络中 的度数。幂函数曲线是一条下降相对缓慢的曲线( 如图1 3 ) ，幂律分布意味着网 络中存在一些数量少，但拥有度数值却极高的集散节点网。p 2 p 网络中用户的个人 行为存在类似幂律分布的现象就意味着网络中极少数的节点在为绝大多数节点提 供服务，即网络中存在一些数量少，但维持的连接数却极高的集散节点。由此说明 集散节点的存在是p 2 p 网络的一种特性。 1 3 集散节点对p 2 p 网络的影响 集散节点的存在，虽然在一定范围内可以提高对等网络的服务效率和健壮性， 但也会降低整个p 2 p 系统的服务性能和质量，增加网络的脆弱性。如果这种现象进 一步加剧，任一集散节点的退出就可能会导致整个对等网络的崩溃。集散节点给对 等网络带来的负面影响具体在于以下三方面【9 l ： ( 1 ) 极少数的集散节点为绝大多数的节点提供服务，这些集散节点会拥有大量 的连接，它们支撑着整个系统的运行。p 2 p 系统的用户数越多，集散节点所承担的 路由转发服务、资源下载服务等负载就越重，集散节点很可能会过载或网络拥塞。 由于在p 2 p 系统中提供服务而频繁遭受c p u 过载或网络拥塞，以致影响了节点的 其他常规服务，则这些集散节点就会退出网络，而一个集散节点的失效极可能会对 整个p 2 p 网络的服务能力产生重大影响甚至会导致整个系统无法运营。 ( 2 ) 网络中存在集散节点会导致网络抗协同攻击的能力降低，网络的脆弱性增 加。p 2 p 网络中的集散节点现象越严重，系统的抗协同攻击能力就越低，如果外界 有意对这些集散节点进行恶意攻击，后果将不堪设想。 4 项士学位论文 m a s t e r st h e s i s ( 3 ) 如果集散现象进一步加剧，p 2 p 网络将趋近于原始的c s 通信模式，集散 节点将充当服务器的角色，由于这些集散节点是用户的p c 机，其性能远不如c s 通信模式中的服务器，因而，整个p 2 p 系统的性能反而会不如原始的c s 通信模式， 这些集散节点也更易成为网络中的瓶颈。而且，一旦形成原始的c s 通信模式，p 2 p 的非中心化基本特点以及健壮性、负载均衡等方面的优势将不复存在，且个别节点 的故障或退出更容易导致整个p 2 p 应用服务系统的崩溃。 因此，如何避免集散节点的形成及控制集散节点的数量，成为p 2 p 对等网络可 持续健康发展的关键问题之一。 1 4p 2 p 网络中集散节点的控制方法 目前，对于p 2 p 网络中存在的集散节点现象主要有两类控制方法：一类是间接 的控制方法，即通过抑制搭便车行为来减轻网络中出现的集散节点现象；另一类是 通过拓扑结构控制机制来直接的达到避免集散节点形成的目的。 1 4 1 基于抑制搭便车行为的间接控制方法 搭便车者仅从p 2 p 系统中获取自己所需要的资源和服务，而不为其他节点提供 资源和服务或故意只提供不被访问的资源。这种自私的搭便车者如果过多，网络中 仅有少数的热心节点共享资源，所有的查询请求就会指向这些热心节点，则必然导 致网络中仅有少数的热心节点为广大用户服务，致使网络中的这些热心节点成为集 散节点可见，搭便车行为是p 2 p 网络中集散节点形成的一种原因。 目前，对于集散节点控制方法的研究更多的是采用抑制搭便车行为的间接控制 方法。此类控制方法主要是通过抑制搭便车行为来促使网络中各节点积极共享资 源，使得网络中的资源搜索过程的目标节点更多，选出的资源也更多，虽然发起搜 索过程的节点是按照协议中的算法筛选出最终连接的节点，但从整体来看，共享了 相同资源的各个节点成为最终连接请求所指向的节点的概率是相等的，各节点所拥 有的连接数就会相当，也就是说网络中各节点的度数均衡化了。因此，当网络中所 有的节点均为热心节点时，集散节点现象就会得到很大程度的缓解。 对于现有的搭便车行为抑制方法，我们将在第2 章给予详细的介绍和讨论。 1 4 2 基于拓扑控制的直接控制方法 此类方法是通过采用拓扑结构控制机制来实现网络中各节点的负载均衡，以达 到避免集散节点形成的目的例如，在文献【1 0 】中，作者对传统的c m u t e l l a 网络搜 5 索算法进行了改进。文中认为，目的节点a 在把资源复制给了曾经提出复制请求的 节点b 、c 后，a 就知道了b 、c 拥有此资源。当a 负载过重时，a 就可以将该资 源的复制请求转发给b 、c 。由于a 明确知道b 、c 已拥有该资源，在b 、c 节点 还有效的情况下，这必是一次有效的查找。基于此思想，他们在传统的g n u t e l l a 搜 索算法中引入了一种资源节点推荐的策略，利用了资源复制阶段的过程信息，将资 源的查找分布到网络的其他结点上。文中对该算法分析后得出了该算法在不影响提 高资源查找的效率的基础上，均衡了网络负载的结论。 文献 1 h 设计了静态环境下的三种通过虚拟服务器迁移实现结点负载均衡的方 案：( 1 ) 一对一，即让每个负载较轻的节点v 周期性地联系一个随机节点w ，如果 w 负载很重，则w 将一部分虚拟服务器转移给v ；( 2 ) 一对多，即让负载很重的节 点首先联系一个随机的“目录节点劳，从目录节点那里得知多个负载较轻的节点， 然后将自己的一部分虚拟服务器转移给这些节点；( 3 ) 多对多，每个目录节点包含 一些负载较轻和负载较重的节点信息，每个目录节点运行设计好的算法，在负载较 轻和负载较重的节点之间重新分配虚拟服务器。 g o d f r e y 等人在文献【1 2 】中对文献【l l 】中的一对多和多对多模式进行了扩展，设 计了一种动态环境下的负载平衡算法，并宣称该算法能使系统的利用率提高超过一 个数量级。 。 文献【1 3 】认为以上基于虚拟服务器的方案没有考虑用户查询的不平衡性，当查 询服从z i p f 分布时，使用虚拟服务器技术并不能降低热点文件的查询次数，热点文 件所在的节点仍容易成为重载结点，因此不能应对z i p f 查询对负载分布的影响。因 此，该文提出了一种结构化p 2 p 协议中的自适应负载均衡方法，当网络中节点负载 存在差异时，重载节点把指向自身的连接请求转移至指向局部负载视图中的轻载节 点，通过平衡重载节点和轻载节点的入度来减小节点间的负载差异。该文的实验结 果表明，在用户查询服从z i p f 分布的环境下，该方法可使系统负载达到较好的均衡。 以上文献虽未明确提出集散节点的概念，但文中所提出的负载均衡思想实质上 是集散节点的拓扑控制方法。 1 5 本文的主要研究内容及组织安排 f 2 p 网络中集散节点的存在必定会降低整个p 2 p 系统的服务性能和质量，加重 网络的脆弱性。本文致力于如何避免集散节点的形成及控制集散节点的数量，以解 决集散节点问题，保障p 2 p 网络可持续健康的发展。 6 硕士学位论文 m a s t e r st h e s i $ 本文将提出两种控制集散节点形成的方法：一是基于金字塔模型的集散节点控 制机制，属于基于抑制搭便车行为的间接控制方法；另一种是避免集散节点形成的 层次结构控制机制，属于基于拓扑控制的直接控制方法。 本文首先分析已有的多种针对p 2 p 网络中用户个人行为的抑制机制特点及其效 用函数特点，提出全新的更加公平的效用函数模型，以解决网络中各节点的硬件、 网络接入环境的差异性等问题。然后，以该效用函数为基础，在p 2 p 系统中建立金 字塔等级结构模型，激励网络的用户为系统作贡献，各节点自主控制自身承受的连 接数，以控制集散节点的形成。最后，从p 2 p 网络的逻辑拓扑结构角度出发，对集 散节点进行层次化处理，减少节点的连接数，以避免集散节点的形成。 本文的章节安排如下： 第l 章绪论，介绍p 2 p 技术的概念、特点，p 2 p 网络中集散节点存在的现象 及其影响，以及目前已有的两类控制集散节点的方法。 第2 章基于抑制搭便车行为的集散节点控制机制研究现状，阐述了搭便车行 为的影响，介绍了抑制搭便车行为的三类方法并进行了分析，指出了这些抑制机制 存在的问题。 第3 章搭便车行为抑制机制中公平效用函数的研究，针对搭便车行为的抑制 机制中效用函数的评估存在的不公平问题，利用层次分析法数学建模方法建立公平 效用函数模型，综合考察多项指标，包括节点的物理性能、网络接入环境、节点贡 献的资源数量以及节点下载的资源数量等，确立了公平效用函数。 第4 章基于金字塔模型的集散节点控制机制，结合第3 章得出的公平效用函 数，在p 2 p 系统中建立金字塔等级结构模型，根据各节点的效用值，将节点归为一 定的级别，赋予各级别的节点相应的资源访问权限，并控制每一级别的节点数量以 及节点迁移数量，以激励系统中的用户为系统作贡献。各节点能自动提升或降低所 共享的资源的访问级别，以减少或增加其连接数，调节自身的负载，避免成为集散 节点。 第5 章避免集散节点形成的层次结构控制模型，从集散节点本身和逻辑拓扑 结构角度入手，按照一定的原则挑选出备份节点，对集散节点进行层次化处理，将 集散节点与备份节点组织成二叉树逻辑结构，并将指向集散节点的连接请求转发至 备份节点，以降低集散节点的连接度数，减轻网络中的集散节点现象。 第6 章结论与展望，总结本文所做工作以及下一步需要研究的内容。 7 硕士学位论文 m a s t e r st h e s i s 第2 章基于抑制搭便车行为的集散节点控制机制研究现状 当前对于p 2 p 网络中集散节点问题的研究主要集中在如何控制用户个人行为的 研究即搭便车行为的抑制机制上。虽然目前学术界对于搭便车行为没有一个统一的 定义，但有如下共识1 9 j ：搭便车是指对等网络中的节点仅从系统中获取其它节点提 供的服务，而不为系统作贡献的行为。显然，搭便车现象违背了设计p 2 p 通信模式 的初衷，因此自a d a r 和h u b c r m a n 在2 0 0 0 年发现该现象之后。研究者已提出了一 系列的搭便车行为抑制机制，本章主要对这些抑制机制进行研究分析。 2 1 搭便车行为的影响 从第1 2 节介绍的对p 2 p 系统流量测量结果可看出：( 1 ) 各p 2 p 系统中均存在 搭便车现象，搭便车行为已成为p 2 p 网络的一种特性：( 2 ) 从2 0 0 0 年到2 0 0 6 年， 各系统中的搭便车者越来越多，搭便车现象越来越严重。 首先，过多节点的搭便车行为会致使系统中的热心节点成为集散节点，从而给 p 2 p 网络带来诸多不良影响。此外，搭便车现象过于严重会降低p 2 p 网络的生存期。 文献 1 4 1 认为如果搭便车者过多，网络中共享的总资源量就会受限制，资源数也将 增长缓慢。随着时间的推移，用户感兴趣的有价值的资源甚至会减少，从而影响系 统对用户的吸引力。当用户发现系统中自己所感兴趣的资源有限时就会退出系统。 如果共享资源较多的集散节点退出系统，系统中的资源数量会更少，其他用户就更 可能会退出系统。这种恶性循环必然最终导致p 2 p 系统的崩溃。 但是，搭便车行为也并不是一无是处，其也具有两面性，除了以上这些负面影 响外，搭便车行为也具有积极的效用【9 1 ： ( 1 ) 搭便车现象使得p 2 p 网络抗随机攻击的能力增强。由于多数节点是自私节 点，维持的连接数少，随机选择得到的节点多为这些自私节点，而这些节点对系统 的贡献小，它们的加入或退出系统对整个系统的稳定性、服务能力等的影响并不大 即使这些节点因遭受攻击而被迫崩溃退出了系统，整个p 2 p 系统的运营和服务质量 并不会受到很大程度的影响。 ( 2 ) 虽然搭便车者未主动为p 2 p 系统作贡献，但它们的加入增加了系统的用户 数量。在商业营运中，用户数量是决定整个p 2 p 系统应用是否成功的关键。并且， 系统也可从这些搭便车节点身上获取利益。例如，p 2 p 系统向其用户投递商业广告， 8 硕士学位论文 m a s t e r s1 h e s i s 在线用户越多，广告效果就越好。此外，在搭便车现象不是很严重的情况下，搭便 车可以有效提高f 2 p 网络的运行效率。 因此，如何防止多数节点只享受服务，却不提供服务的搭便车行为，是p 2 p 技 术发展亟待解决的问题之一，也是避免网络中形成集散节点的一种重要途径。为了 确保p 2 p 网络高效运行和可持续健康的发展，可以允许一定程度的搭便车行为存在， 但对过于严重的搭便车行为需要采用适当的措施进行抑制。 2 2 搭便车行为抑制机制 a d a r 和h u b e r m a n 在文献【3 】中首次提出有必要采用某种节点行为激励机制去抑 制搭便车行为，自此，抑制机制成为了p 2 p 领域的研究热点。已提出的抑制机制大 致可分为基于节点行为的激励机制、基于博弈论的方法、采用社会网络或经济模型 的控制策略3 大类【9 】。 2 2 1 激励机制 激励机制是最早提出也是最为普遍的搭便车行为抑制方法，其基本算法流程可 概括为【9 】： s t e pl 提出一个效用函数； s t e p2 每个节点定期或事件触发地计算节点的效用函数； s t e p3 节点请求发起信息查询或下载服务； s t e p4 如果节点效用函数值较高，则进行下载操作，下载后，转s t e p6 ： s t e p5 如果节点效用函数值低，拒绝下载服务，转s t e p7 ； s t e p6 节点重新计算效用函数： s t e p7 系统等待事件触发，有服务请求则跳转到s t e p3 ；如果节点为其它节点 提供了服务，则跳转至l j s t e p6 。 其中，效用函数用于评估节点对于系统的有用性。各种激励机制之间最主要的 区别在于使用的效用函数不同。 r a m a s w a m yl 和l i ul 在文献【1 4 】中指出搭便车是p 2 p 网络应用的一个挑战。 文中介绍了多数节点都不愿意提供文件以供他人访问，而只希望从系统中得到自己 需要的信息，这种自私的搭便车行为，必须通过强制的控制机制来改变。因此，文 9 硕士学位论文 m a s t e r st h e s i s 章首次提出了效用函数( u t i l i t yf u n c t i o n ) 的概念，并利用该概念来控制单个节点从 重叠网络中获得信息下载资源的能力文中提出了三个比较简单的效用函数表达 式，如式( 2 1 卜( 2 3 ) 。 u ( 忍，d = 口lu l i s t ( p 。，丁) 1 ( 2 1 ) 其中，叩乃表示节点b 在丁时刻的效用值，u l i s t ( p 。乃表示节点只在r 时刻 所共享的文件集合，口是一个比例系数。该效用函数主要考察了节点所共享的文件 数量，节点共享的文件数越多，其效用值就越高。 u ( p ，d = 。 s i z e ( f j ) ( 2 2 ) v 弓姚一( 毋刀 效用函数表达式( 2 2 ) 中，s 丘碧( c ) 是节点只在t 时刻所共享的文件e 的大小， j 切( 巧) 表示节点b 在2 时刻所共享的所有文件的总大小。也是一个比 v 弓e 【胁( 毋刀 例系数。不同于式( 2 1 ) ，此效用函数考察的是共享文件的大小，节点所共享文件的 总大小决定了节点的效用值。 u ( 曰，2 ) = r ( k + d c o u n t ( f j ，功s i z e ( 弓) - s i z e ( e )( 2 3 ) v 弓e 阻蔚( j ：，) j e d 上脚( 毋r ) 式( 2 3 ) 包括两部分；奖励值与惩罚值。奖励值评估节点对于系统的效用，而惩 罚值评估节点从系统中获取的资源量。 r ( k + d c o u n t ( c ，丁) ) s i z e ( f j ) ；是 v j i e 觇埘( 毋刀 励值部分，其中，d c o u n t ( f j ，t ) 表示从被共享开始到当前的r 时刻止，文件e 被 下载的次数，7 是一个比例系数，七是公正常量。奖励值考虑了节点共享文件的大 小以及这些文件被下载的次数。 s 切( e ) 是惩罚值部分，其中，s n e ( 5 ) w i e d l 垃( 弓，) 节点从系统中下载的文件石的大小。惩罚值就是节点b 到时刻2 为止从系统中所下 载的文件大小之和。 效用函数( 2 1 ) 评估的是节点所共享的文件数量，采用此式对共享文件数量较多 的节点有利，但对于共享文件数量少但文件很大的节点来说就不够公平。于是，效 用函数( 2 2 ) 就解决了这种非公平性，但它不能区分系统中恶意下载的节点以及那些 故意提供他人不感兴趣的资源的搭便车节点。因此，效用函数( 2 3 ) 就更先进了一步， 不仅考察了节点提供共享的文件大小和下载次数，还将节点自身的下载资源量纳为 了效用值评估因素。该文的仿真实验证明，即使是采用式( 2 1 ) 之类的十分简单的效 1 0 硕士学位论文 m a s t e r st h e s i s 用函数也能严格的控制搭便车行为、增加系统的生存期。 在文献 1 5 】中，a h s a nh a b i b 与j 0 h nc h u a n g 在流媒体的应用中使用了基于效用 函数的激励机制以抑制搭便车行为。该文提出了一种基于等级的对等点选择机制， 通过区别服务的方法激励节点之间共享合作。系统贡献者将受到在对等点的选择与 灵活性方面的奖励，因而会享受较高的服务质量。相反，而搭便车者将在这些方面 受到限制，从而也就只能享受较低的服务质量。其定义的效用函数为 瓴) = q q ( 毛) 一包c ( 而) ( 2 4 ) 其中，x j 为节点i 对系统的贡献级别，q ( 而) 函数表示具有级别而的节点f 所能享受 的流媒体服务质量，c ( 而) 表示具有级别蕾的节点f 为系统所做贡献的成本代价，口f 和抚分布定义了节点f 所能享受的服务质量与贡献消耗的权值。仿真实验与大范围 的测量研究表明，此种激励机制能向合作者提供最优的流传输性能。 文献 1 6 1 中提出了一种基于遗传算法的p 2 p 存储资源共享激励机制。依据该机 制，提供资源的节点根据遗传算法选择最优策略分配资源，以使其对系统的贡献值 最大化。由于节点在系统中享受的服务是根据其贡献值来计算的，贡献值大的节点 其可支配使用的共享存储资源就越多，因此就可从系统中获得来自其它节点更好的 服务。该机制能有效地实现p 2 p 系统中存储资源分配的公平性和效率，达到激励节 点参与共享资源，抑制节点自私行为的目的。 a n e e a u m ee ，g r a d i n a r i um 等人在文献【17 】中考虑了在p 2 p 网络中解决公平的 资源共享问题以优化资源共享的性能。文中采用了一个改进的效用函数 0 一 u o ，r ) = ib ( p , r ( t 。) ，r 。) a t ( p ，f 。) 一芝：c q ，) p a r t ( p , r ，0 ( 2 5 ) 高 磊且 式( 2 5 ) 对时间进行积分以计算节点p 这f 时刻内从网络下载的资源量，然后减 去该节点为系统所提供的下载资源量总和。文中将表现出搭便车和贪婪主义行为的 节点定义为理性主义节点，并指出系统的公平性是指系统中的节点既不是搭便车者 也不是贪婪者。仿真实验证明作者所使用的效用函数( 2 5 ) 能有效保证文件共享系统 的公平性。 文献【1 8 】提出了一种在非结构化p 2 p 网络中基于测量的分布式抑制搭便车现象 的方法。该方法的基本思路是每个对等节点监视其邻居节点，根据计算统计得到的 查询、查询响应等消息数之闾的比值确定对等网络中的搭便车主义者，并采用合适 硕士学位论文 h i a s t e r st h e s i s 的方法( 如快速降低1 1 几值，丢弃搭便车节点的查询请求，中断搭便车者的连接等) 去抑制搭便车主义者。该文所提出的抑制机制中区分了三种可能的搭便车类型：不 作贡献者、消费者以及丢弃者，并提出了相应的检测机制以使这三类搭便车者的行 为能被其邻居节点监测到该文所提出的抑制方法也属于激励机制，虽然文中未明 确提出效用函数的概念，而实质上，查询、查询响应等消息数之间的比值即可看作 是一种效用函数。 r i c h a r dt b m a , c m l e e 等人在文献【1 9 】中提出了一种基于激励机制，鼓励信 息共享和服务的协议。该协议机制根据节点的物理连接类型( 如高速光纤接入、 a d s l 或者拨号上网等) 、贡献和利用率函数等将资源分布在对等网络中的多个节点 上，取得了较高的公平性。其定义的效用函数为 兰警尘c j