（应用数学专业论文）优化的点对点文件交换系统optimizationpeer的原理与设计.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：区基日期：型：璺塑 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名： 虚坠 导师签名：压鱼妊日期：k 兰! ：1 2 矽 山东大学硕十学付论文 摘要 p 2 p 是p e e r - t o p e e r 的缩写，其中p e e r 是“同等的人、伙伴”的意思。国内一般 将p 2 p 直译成“端对端”或者“点对点”，又可称为对等网，是一种新的分布式计算 模式。在这种模式下，服务器与客户机的界限消失了，网络上的所有节点都可以“平 等”地共享其他节点的计算资源。 p 2 p 系统是一种分布式系统，系统中的每个节点都是对等的，既向其他节点 提供服务，又向其他节点索取服务。在p 2 p 系统中，节点之间直接交换的可以是 文件、消息、存储空间和c p u 周期等，系统中的节点是动态的，可以随时加入或 退出。 随着计算机技术和网络技术的发展，渐渐形成了一种从集中的单机系统转向 分布式系统的趋势，p 2 p 越来越受到学术界和工业界的重视。p 2 p 系统具有非集 中化、可扩展性、可用性、自适应性、负载均衡、匿名性等特点，主要的应用领 域包括：文件交换、对等计算、协同工作、即时通讯、搜索引擎、网络游戏、基 于i i l t e m e t 的文件存储系统和操作系统等。p 2 p 技术尚未成熟，许多问题有待深入 研究。本文的研究对象就是p 2 p 系统的一个重要分支文件交换系统。 本文提出了一个优化的p 2 p 文件交换系统模型，吸纳了各种先进思想，综合 了现有多个系统的优点，有力提升了系统的整体性能，本文的主要贡献有： 一、系统介绍了p 2 p 的基础知识，归纳出p 2 p 文件交换系统的4 大主要研究 问题，分别介绍了各个问题的研究状况，分析了现有技术的优缺点，总结出影响 p 2 p 文件交换系统效率的4 个主要因素，即网络结构、查询方式、路由选择和文 件传输方式。 二、提出了一个优化的p 2 p 文件交换系统模型o p t i m i z a t i o n p e e r ，从以下几个 方面提高了系统性能： ( 1 ) 提出一种基于偏好的超节点网络模型，充分体现幂规律和小世界特征，提 出了偏好相似度的概念和计算公式，并给出了动态自调整网络的实现策略； ( 2 ) 采用分布式广度优先( d b f s ) 方法处理超节点间的消息转发问题，给出 了d b f s 的算法，分析了该算法的时间、空间复杂度和效用；并给出了进一步优 化查询机制的3 条规则。 ( 3 ) 利用元数据自动抽取和增量更新技术，在超节点上以x m l 格式存储了共 享文件的众多特征信息，可以支持基于x q u e r y 的高效复杂查询。 ( 4 ) 通过并行多点下载技术大幅度提高了文件传输效率。 三、详细论述了在p 2 p 环境中进行并行多点下载的实现策略，提出了下载节 3 山东大学硕十学位论文 点的优化选择和数据完整性判断的方法，给出了下载程序的详细算法。通过实验 评估了并行多点传输技术对下载效率的提升情况( 加速比) ，并分析了影响下载效 率的因素。 下面概要介绍一下本文的特色之处。 网络结构模型是构建p 2 p 系统的基础，与系统所提供的功能和整体性能直接 相关。研究表明，p 2 p 网络拓扑图遵循两个规律幂规律和小世界特征，主要 表现在网络中少数节点的“度”较高，以及网络拓扑具有高聚集度两个方面。根 据这两个规律，我们提出了一种“基于偏好的超节点网络模型”，即将网络中的节 点按兴趣偏好划分为若干个簇，同一簇中的节点偏好相似，每个簇中有一个超节 点( s u p e r - p e e r ) ，各节点直接连接到本簇的超节点上，向它发送资源索引和查询 消息，超节点负责资源的搜索，并能将消息转发到其他簇的超节点上。这种网络 模型使大部分查询能够在本簇内完成，大大提高了查询效率，同时兼备了分布式 搜索的自治性、负载平衡和健壮性。 本文研究的一个重点内容是基于偏好的簇划分方法。我们按某种标准，将p 2 p 网络中共享的文件分为n 个类别，文件的全体看作具有n 个元素的集合u 。定义 某个节点a 的偏好f ( a ) 或某个簇x 的偏好f ( ) ( ) 为u 的一个子集，提出“偏好相 似度”的概念，定义其计算公式为 d ( a x 1 ：n u m ( f ( a ) n f ( x ) ) n u m ( f ( a ) u f ( x ) ) 其中n u m ( s ) 表示集合s 中的元素个数。这样，我们就可利用该公式来计算节 点与簇的偏好相似度，从而将相似度高的节点划分到一起了。 在超节点之间的消息转发方面，我们采用了分布式广度优先( d b f s ) 的方法。 即将超节点构成的网络看作一张无向图，每个超节点收集2 跳( h o p ) 范围内的节点 信息，得到小范围内的网络拓扑，这样在转发查询消息时，超节点可构造b f s 生 成树，然后广度优先遍历即可。此种方法可以在一定范围内保证每个节点能且只 能收到一次查询消息，不会产生冗余。为了进一步提高查询效率，我们又给出了 暂存相关索引，迭代深入和有向宽度优先3 条优化规则。 o p t i m i z a t i o n p e e r 还采用了基于元数据的结构化查询技术，通过程序将共享文 件的元数据提取出来，以x m l 格式集成到超节点上，这样就可以根据元数据， 在p 2 p 网络中更精确地查找所需的文件。可以选用x m l 的查询语言x q u e r y 进行 复杂查询，对某些本身带有丰富元数据的文件( 如r a p 3 、w o r d 等) ，可以大大提 高查全率和查准率。在这部分中，我们还提出了一种简洁的元数据增量更新的方 法。 为了弥补基于偏好的超节点网络无法同时顾及节点物理位置的不足之处，尽 4 山东大学硕十学何论文 可能提高文件下载效率，o p t i m i z a t i o n p e e r 采用了并行多点下载的技术。该技术使 请求节点能够从多个源节点同时下载一个文件的不同部分，然后拼装成完整的文 件，使下载效率成倍提高。而且该技术使下载节点可以动态选择高速源节点，避 免了下载过程中源节点出现故障后任务无法完成的缺陷。本文详细论述了在 o p t i m i z a t i o n p e e r 中进行并行多点下载的实现策略，提出了利用m d 5 算法确保数 据完整性的思路，给出了超节点网络中任意两点间距离的估算公式，从而实现了 下载源节点的优选。我们编程实现了下载模块，实验证明该技术可以实现并行下 载中接近线性的加速比，我们还分析了影响下载效率的各个因素。 本文的写作是沿着“如何构造一个优化的系统”这条主线进行的，各种先进 思想和先进技术在基于偏好的超节点网络这一总体架构下取长补短，相互配合， 构成一个有机的整体。系统表现出来的最突出的特点就是整体性能的优化和高效， 这也是o p t i m i z a t i o n p e e r 这个名字中的殷切期望。 关键词：对等网；文件交换系统；超节点；偏好相似度；分布式广度优先；元数 据；并行多点下载 5 山东大学硕十学伊论文 a b s t r a ( 、t p 2 pi st h ea b b r e v i a t i o no fp e e r - t o p e e r , w h i c hi san e wd i s t r i b u t e dc o m p u t i n g m o d e l i nt h i sm o d e l ，p e e r sc a l ls h a r ec o m p u t i n gr e s o u r c e so f o t h e r se q u a l l y p 2 ps y s t e mi sak i n do fd i s t r i b u t c c ls y s t e m , i nw h i c he v e r yp e e rb o t lp r o v i d e s s e r v i c e st oo t h e r sa n dg e t ss e r v i c e sf r o mo t h e r s t h er e s o u r c e st h a ta r ee x c h a n g e dm a y b ef i l e s ，m e s s a g e s ，s t o r a g e sa n dc p uc i r c l e s ap 2 ps y s t e mi sd y n a m i c ，a n de a c hp e e r c a n l o g i n o r l o g o u t i t a t a n y m o m e n t w i mt h ed e v e l o p m e n to fn e t w o r kt e c h n o l o g y , p 2 ph a sb e c o m eah o tt o p i ci n c o m p u t e rs c i e n c e ，a n ds o m es o f t w a r eb a s e do np 2 ph a sb e e nd e v e l o p e db ys o m e c o m p a n i e s t h ec h a r a c t e r i s t i c so fp 2 ps y s t e m si n c l u d ed e c e n t r a l i z a t i o n , s c a l a b i l i t y , r o b u s t n e s s ，a v a i l a b i l i t y , a d a p t a t i o n , l o a db a l a n c ea n da n o n y m i t y t h ea p p l i c a t i o n so f p 2 pi n c l u d ef i l e s h a r i n g ，p 2 pc o m p u t i n g ，c o o p e r a t i n g ，i n s t a n tm e s s a g e s ，s e a r c h i n g e n g i n e s ，n e t w o r kg a m e s ，e t c p 2 pi sn o tm a t u r e ，a n dal o to f p r o b l e m sn e e dt ob es o l v e d t h et o p i co ft h i sp a p e ri sp 2 pf i l e s h a r i n gs y s t e m ，w h i c hi st h em o s ti m p o r t a n t a p p l i c a t i o no f p 2 p i nt h i s p a p e r , w ep r o p o s e a l le f f i c i e n tp = 2 p f i l e - s h a r i n gs y s t e m n a m e d o p t i m i z a t i o n p e e r , w h i c h i n c l u d e s s o m e a d v a n c e d t e c h n o l o g i e s o u r c o n t r i b u t i o n s i n c l u d e ： 1 w ei n l r o d u c et h eb a s i ck n o w l e d g eo fp 2 pa n da m l m a 妇t h e4m a i nr e s e a r c hi s s u e s a b o u tp 2 p w ea n a l y z et h ea d v a n t a g e sa n ds h o r t c o m i n 挚o f c t a r e n tp 2 ps y s t e m s 9a n ds i n l lu p t h e4m a i ne l e m e n t sw h i c hi n f l u e n c et h ee f f i c i e n c yo fp 2 pf f i e - s h a r i n gs y s t e m s t h e ya r e n e t w o r k t o p o l o g y , m o d e o f q u e r y , m e s s a g e m u t i n g a n d t h e m o d e o f f i l e - d o w n l o a d i n g 2 w ep r o p o s ea ne f f i c i e n tp 2 pf f i e - s l 搬i n gs y s t e mm o d e ln a m e do p a m i z a t i o n p e e r , w h o s ee f f i c i e n c yi si m p r o v e df r o mt h ef o l l o w i n g4 硒p e 瞅 ( 1 ) w ep r o p o s e dap 2 pn e t w o r kb a s e do ni l i t e n e s t s , w h i c he m b o d i e st h ep o w e r l a wa n d t h ec h a r a c t e r i s t i co f s m a l lw o r l d w ep r o v i d et h ed e f i n i t i o na n df o r m u l aa b o u t 妇d e g r e eo f s i m i l # u d eo f i n t e r e s t s ( d s i ) i na d d i t i o n , w ep r o v i d es o m ep o l i c i e sa b o u tt h ed y n a m i cn e t w o r k ( 2 ) w e 峨t h em e t h o do f d i s t r i b u t e d b r e a t hf i r s ts e a r c h ( d b f s ) t op r o c e s st h ep r o b l e m o f m e s s a g e s 协m s m i m i 唱a d d i t i o n a l l y , w ep r o v i d e3p o l i c i e sa b o u tm u t i n gb e t t e r ( 3 ) u s i n gt h et e c h n o l o g i e so fa b s t r a c t i n ga n di n t e g r a t i n gr e c t a - d a t a , o p t i m i z a t i o n p e e r s t o r e sm e t a - d a t ao fs h a r e df i l e so i ls u p e r - p e e r si nx m ls c h e m a , 8 0i ts u p l x 姚t h ec o m p l e x q u e r yb a s e d o nx q u e r y ( 4 ) t h ee f f i c i e n c yo ff i l et r a n s m i t t i n gi sm u c hi m p r o v e db yu s i n gt h et e c h n o l o g yo f 6 山东大学硕七学位论文 p a r a l l e lm u l t i - p o i n td o w n l o a d i n g 3 w ee l u c i d a t et h ei m p l e m e n t a t i o no f t h em u l t i - p o i n td e w n l o a d i n gm o d u l ea n dp r o v i d e m e t h o d so f j u d g i n gd a t ai n t e g r i t ya n d c h o o s i n gb e s ts o u r e cp e e r s i na d d i t i o n , w ee v a l u a t em e e f f i c i e n c yo f o u rs y s t e mt h r o u g he x p e r i m e n t s i nt h ef o l l o w i n g ，w ew i l lb r i e f l yi n t r o d u c et h ec h a r a c t e r i s t i cp a r t so f t h i sp a p e r t h en e t w o r kt o p o l o g yi st h eb a s eo fap 2 ps y s t e m ，a n di ti sd i r e c t l yr e l a t e dt ot h e f u n c t i o na n dt h ew h o l ep e r f o r m a n c eo f t h es y s t e m r e s e a r c h e si n c o m et h a tt h en e t w o r k t o p o l o g yo f ap 2 pn e t w o r ko b e y st h ep o w e r l a wa n dt h ec h a r a c t e r i s t i co f s m a l lw o r l d , w l f i c h s h o w st h ed e g r e e so f af e w i x x ! r sa r ch i g ha n dp e e r sl e a nt oc o n g r e g a t ei n t os o m ec l u s t e r s w e p r o p o s eap 2 pn e t w o r kb o 。s c do ni n t e r e s t s , w h i c he m b o d i e st h eb o t hl a w s i n 蛳恐嘶d n p p 盯 a l lp e e r sa r ec l u s t e r e db a s e do ns i m i l a ri n t e r e s t s i ne a c hc l u s t e ra g - r ei sas u p e r - p e e r , o nw h i c h i n d e x e so fp e e r si nt h i sc l u s t e ra r es t o r e d s u p e r - p e e r st a k ec h a r g eo ft h ew o r ko fn 鞠u h 瑚 s e a r c h i n g t h eq u e r i e si nt h i sn e t w o r k 黜e f f i c i e n t , a n dt h es y s t e mi sa l s ow i t ht h er o b u s t n e s s o f d i s t r i b u t e ds e a r c h i n g a ni m p o r t a n tp o i n to ft h i sp a p e ri st h em e t h o do fp e e r sc l u s t e r i n gb a s e do r i n t e r e s t s w ep a r t i t i o nf i l e si nt h es y s t e mi n t o 疗c l a s s e sa c c o r d i n gt os o m es t a n d a r d s t h ew h o l eo ff i l e si sr e g a r d e da sas e tut h a ti n c l u d e s 撑e l e m e n t s w er e g a r dt h e i n t e r e s t so fa p e e ra o rac l u s t e rxa sas u b s e to fu ，a n dw ep r o v i d et h ed e f i n i t i o no f t h ed e g r e eo f s i m i l i t u d eo f i n t e r e s t s ，w h o s ec o m p u t i n gf o m m l ai sa sf o l l o w s ： d ( a x ) ：n u m ( f ( a ) n f ( x ) )7 n u m ( f ( a ) u f ( x ) ) ( n o t e ：a b o v en u m ( s ) i n d i c a t e st h en u m b e ro fe l e m e n t si ns e ts ，a n df ( y ) i n d i c a t e st h ei n t e r e s t so fac l u s t e ry o rap e e ry ) t h e r e f o r e ，w ec a l l u s e t h i s f o r m u l a t oc o m p m e t h e d s i b e t w e e n p a e r a n d c l u s t e r , a n d w e c a n c l u s t e r t h e p e e r s w i t h h i g h d s i t o g e t h e r a b o u tt h er e u n n go f q u e r ym e s s a g e sw i t h i ns u p e r - p e e r , w ea d o p tt h em e t h o do f d b f s w er e g a r dt h en e t w o r kc o m p o s e do fs u p e r - p e e r sa sag r a p h e a c hs u p e r - p e e rc o l l e c t st h e i n f o r m a t i o no fn e i g h b o r i n gs u p e r - p e e r sw i t h i n2 h o p sa n dg e t st h et o p o l o g yo fn e t w o r ki n s m a l ls c o p e t h e r e f o r e , as u p e r - p e e ri sa b l et oc o b s i i a l c tab f s s p a n n i n g - t r e e ，w h i c hi n s u r e s e a c hs u p e r - p e e rr 。c e i v 嚣q u e r y i n gm e s s a g eo n l yo n c eo nas c a l e i no r d e rt oe n h a n c et h e q u e r y i n ge f f i c i e n c ym o r e , w ea d d i t i o n a l l yp r o v i d e3o t h e ro p t i m i z i n gp o l i c i e s o p t m i z a t i o n p e e ru s e st h et e c h n o l o g i e so f e x w a c t i n g , i n t e g r a t i n ga n dq u e r y i n gm e t a d a t a t h e s em e t a - d a t ao fs h a r e dt i e s 黜i n t e g r a t e di nx m ls c h e m ao ns u p e r - p e e r s s ou s e f sc a n q u e r yf i l e sw i t hx q u e r y t os o m ef i l e sw i t hr i c hm e t a - d e t a , s u c ha sm p 3a n dm sw o r df i l e s , 7 山东大学硕十学何论文 b h ep r e c i s i o ni nq u e r yi si m p r o v e dal o t i nt h i sp a r t , w ea l s op r o v i d eak i n do f c o n c i s em e t h o d t h a ti su s e dt oi n c r e m e n t a lu p d a t em e t e - d a t ao ns u p e r - p e e r s i no r d g xt om a k eu pt h es h o r t a g et h a tt h en e t w o r kb a s e do ni n t e r e s t sc a nn o tc o n s i d e rf i r s t t h ep h y s i c a lp o s i t i o no f p e e r s , o p a m i z a a o n p e e ra d o p 挺t h et e c h n o l o g yo f p a f a l l e lm u l t i - p o i n t d o w r f l o a d i n g t h i st e c h n o l o g ye n a b l e sap e e rt od o w n l o a dd i f f e r e n tp a r t so f 恤s 出l l ef i l e si n m a n ys 0 1 r o ：p e e r ss y n c h r o n o u s l y , a n dt h e na s s e m b l et h e mt oaw h o l ef i l e t h et c c h n o l o g y m a k e st h ee f f i c i e n c yo f d o w n l o a d i n gf i l e se n h a n c e db ys e v e r a lt i m e s w ep r o p o s et h ei d e ao f i i l s u 时i 培t h ed a t ai n t e g r i t yw i t hm d 5 ，a n dp r o v i d et h ef o r m u l a st h a ta r eu s e dt oc a l c u l a t et h e d i s t f l n c eb e t w e e na n yt w op e e r si np 2 pn e t w o r kw i t hs u p e r - p e e r w ep r o g r a mt oi m p l e m e n t f l a i s m o d u l e t h e e x p e r i m e n t s p r o v e t h a t o u r t e c h n o l o g i e sr e a l i z e a l i n e a r r a t e o f s p e e d u p d u r i n g t h ep r o c e s so f d o w r a o a , l i r 】gf i l e s t h i sp a p e ri sw r i t t e na l o n gt h et h r e a dh o wt ob u i l da l le f f i c i e n tp 2 ps y s t e m k i n d so f a d v a n c e dt e c h n o l o g i e sc o o p e r a t ei nh a r m o n yi nt h ef r a m e v o r ko ft h en e t w o r kb a s e do n i n t e r e s t sa n db e c o m eaw h o l e t h e s et e c h n o l o g i e sm a k eo u rs y s t e mv e r ye f f i c i e n t t h en 锄e o p t i m i z a t i o n p e e ri m p l i e st h em o s to u i s t a l l d i n gc h a r a c t e ro f t h i ss y s t e m k e y w o r d s ：p 2 p ；i n f o r m a i t o n - s h a r i n gs y s t e m ； m d f - p o i n td o w n l o a d i n g 8 山东大学硕十学付论文 1 1 研究背景 第1 章绪论 p 2 p 是p e e r - t o p e e r 的缩写，中文可称为对等网。 随着计算机技术和网络技术的发展，渐渐形成了一种从集中的单机系统转向 分布式系统的趋势。p 2 p 将人们直接联系起来，让人们通过互联网直接交互。p 2 p 使得网络上的沟通变得更容易、更直接共享和交互，真正地消除中间商。p 2 p 使 人们可以直接连接到其他用户的计算机交换信息、文件，而不是像过去那样连接 到服务器去浏览与下载。p 2 p 改变了互联网现在的以大网站为中心的状态、重返“非 中心化”，并把权力交还给用户。p 2 p 技术在加强网络上人的交流、文件交换、分 布式计算等方面前景广阔，而由于该技术尚未成熟，其中有许多问题有待深入研 究，现有系统也有待进一步改善。本文的研究对象就是p 2 p 应用系统的一个重要 分支文件交换系统。 1 2 研究意义 因为p 2 p 文件交换系统通过众多的p e e r 分散了共享数据的主要代价磁盘 存储空间、网络传输带宽等，所以它们可以在没有昂贵的高性能服务器的情况下 很好地工作。但是，由于众多p e e r 彼此分散，相隔遥远且难以协调，导致p 2 p 系 统的效率相比集中系统大打折扣，所以如何构造一个优化的、高效的系统就成为 研究的一个重要内容。下面，我们分析一下影响p 2 p 文件交换系统效率的各个因 素。 根据集中管理程度的不同，可以将p 2 p 系统划分为3 种类型。n a p s t e r 1 是世 界上最早的p 2 p 信息文件共享系统，它属于有核心服务器的混合p 2 p 结构，所有 节点都向该服务器发出查询。这种系统的突出优点是查询效率高，缺点是核心服 务器容易成为整个系统的瓶颈；g n u t e l l a 2 属于纯p 2 p 系统，系统中的所有节点 都具有完全相同的角色，查询消息在节点之间转发。这种结构消除了核心服务器 的瓶颈，但缺点是造成了查询的低效率，而且网络中的一些低能力的节点会影响 系统的整体性能；k a z a a 3 等系统采用了一种具有超节点的p 2 p 网络结构【4 】。超 节点( s u p e r - p e e r ) 是根据某些原则选出的能力较强的节点，它们具备各个节点子 集中核心服务器的功能，同时超节点之间也互相连接，在整个覆盖网络中转发消 息。由于超节点网络综合了前两种p 2 p 结构的优点，所以它有潜力兼备集中式搜 索的高效率和分布搜索的自治性、负载平衡和健壮性。 9 山东大学硕十学位论文 查询( 或称搜索) 是p 2 p 系统的关键技术之一。在现在的大部分p 2 p 网络中， 搜索采用泛洪( f l o o d i n g ) 的方法。一个节点向所有邻居节点广播查询消息，邻居 节点再向自己的邻居节点广播，这个过程不断进行下去。为了限制搜索的范围， 消息被设置一个初始的t t l ( t i m e - t o 1 i v e ) 值。消息每经过一个节点，t t l 值减1 。 当t i l 值为0 时，搜索过程中止。这种方法的健壮性很好，但有个严重的问题， 就是会产生大量的冗余消息，给网络造成沉重的负担。 另一方面，在实际使用的p 2 p 文件交换系统中，大多数查询都是利用关键字 与共享文件的文件名匹配来进行的，由于文件名并不能准确地反映出该文件的内 容特征，所以这些p 2 p 系统的查准率和查全率都不很理想；另外，在文件交换系 统中，一个查询可能会返回多个结果，如何在这些结果中选择代价最低的进行数 据传输也是一个值得研究的问题。文 5 - 8 】讨论了与查询有关的一些问题。 由于p 2 p 系统中共享的经常是音乐、视频等容量较大的文件，所以如何将文 件高效下载也是一个值得考虑的问题。b i t t o r r e n t ( b t ) 9 是一种流行的文件下载工 具，可以支持文件从不同源节点到同一个目的节点的多点下载。但使用b t 时必 须依赖额外的w e b 服务器发布t o r r e n t 文件，b t 本身并不支持查询功能，而且b t 是根据t o r r e n t 文件中的t r a c k e r 的u r l 来定位源文件的，并不能找到t r a c k e r 链之 外的共享文件。 从上面的叙述中可以看出，网络结构、查询方式、路由选择、文件传输方式 等是影响p 2 p 系统整体效率的主要因素。本文在研究现有多个系统的基础上，分 析总结它们的优缺点，综合各自的长处，提出了一个优化的p 2 p 文件交换系统模 型，力图从以上各个方面全面提高系统效率，达到方便、高效共享文件的目的。 1 3 本文的贡献和组织 本文提出了一个优化的p 2 p 文件交换系统模型，吸纳了各种先进思想，综合 了现有多个系统的优点，有力提升了系统的整体性能，本文的主要贡献有： 一、系统介绍了p 2 p 的基础知识。归纳出p 2 p 文件交换系统的4 个主要研究 问题，分别介绍了各个问题的研究状况，分析了现有技术的优缺点，总结出影响 p 2 p 文件交换系统效率的4 个主要因素。 二、提出了一个优化的p 2 p 文件交换系统模型o p t i m i z a t i o n p e e r ，从以下几个 方面提高了系统性能： ( 1 ) 提出一种基于偏好的超节点网络模型，充分体现幂规律和小世界特征，提 出了偏好相似度的概念和计算方法，并给出了动态自调整网络的实现策略； ( 2 ) 采用分布式广度优先方法( d b f s ) 处理超节点间的消息转发问题，给出 山东大学硕十学何论文 了d b f s 的算法，分析了该算法的时间、空日j 复杂度和效用；并给出了进一步优 化查询机制的3 条规贝i j 。 ( 3 ) 利用元数据自动抽取和增量更新技术，在超节点上以x m l 格式存储了共 享文件的众多特征信息，可以支持基于x q u e r y 的高效复杂查询。 ( 4 ) 通过并行多点下载技术大幅度提高文件传输效率。 三、详细论述了在p 2 p 环境中进行并行多点下载的实现策略，提出了下载节 点的优化选择和数据完整性判断的方法，给出了下载程序的详细算法。通过实验 评估了并行多点传输技术对下载效率的提升情况( 加速比) ，并分析了影响下载效 率的因素。 本文组织结构如下： 第一章介绍本文的研究背景、研究意义、贡献和组织； 第二章概述p 2 p 的发展历史、定义、特点和应用领域； 第三章总结出p 2 p 文件交换系统的4 大主要研究问题，即网络结构、搜索技 术、文件传输方式和安全问题，并逐一阐述各个问题目前的研究状况。 第四章提出了高效p 2 p 文件交换系统模型o p t i m i z a t i o n p e e r ，从系统架构、消 息转发机制、元数据集成与查询、并行多点下载机制4 个方面深入阐述了该系统 的原理与设计思想。 第五章详细论述了o p t i m i z a t i o n p e e r 系统中的并行多点下载技术，并给出了实 验分析。 第六章是本文的总结。 山东大学硕十学付论文 2 1p 2 p 的发展历史 第2 章p 2 p 系统概述 1 9 9 9 年，当时年仅1 8 岁的肖恩范宁( s h a 啪f a n n i n g ) 建立了n a p s t e r ，一个供 大家交换m p 3 音乐的软件平台。用户可以免费下载安装该软件，使用该软件可以 很方便地搜索到其他用户计算机里存储的m p 3 文件，并可以免费下载到自己的电 脑中，当然也可以将自己拥有的m p 3 文件共享给其他用户。这种基于p 2 p 技术的 服务普遍受到了人们的欢迎，服务推广的当年，注册用户就突破了3 0 万，其鼎盛 时期更达到5 0 0 0 多万用户，可以共享近2 0 0 万首免费的m p 3 音乐文件。 n a p s t e r 在受到人们关注的同时，也受到了各大唱片公司的关注。由于n a p s t e r 的发展直接影响到了传统音像行业的财政收入，a o l 时代华纳、索尼、贝塔斯曼、 e m i 、环宇等各大唱片公司毫不犹豫地将n a p s t e r 推上了法庭。2 0 0 1 年2 月，美国 联邦法院做出裁决，要求n a p s t e r 音乐网站停止侵害版权的行为。2 0 0 1 年7 月， n a p s t e r 终于关闭了其音乐交换服务。峰回路转，世事多变。2 0 0 2 年5 月，德国传 媒巨子贝塔斯曼集团将n a p s t e r 收购。 n a p s t e r 的命运跟p 2 p 技术的未来关系不大，它已经为p 2 p 技术充当了开路先 锋，而剩下的上作，还需要业界继续探索，不断前进。不论n a p s t e r 的命运最终如 何，都不能改变n a p s t e r 所使用的技术和思想给i n t e r n e t 带来的巨大影响。 n a p s t e r 的基本思想是相当简单的。在n a p s t e r 系统内，每一个用户称为p e e r ，在 各自的本地磁盘上存储m p 3 文件，而n a p s t e r 的中心服务器并不存储m p 3 文件， 只存储用户共享的m p 3 文件索引。为下载需要的音乐文件，用户向中心服务器发 出基于关键字的查询并获取拥有该文件的p e e r 的i p 地址，用户可以从获得的p e e r 中选择其中之一，直接下载该文件。 继n a p s t e r 之后，各种基于p 2 p 技术的应用风起云涌。文件交换方面比较有 代表性的有g n u t e l l a , f r e e n e t 等。在协同计算方面，加州大学伯克利分校的研究人 员开发了s e t i h o m e 项目，使用一个屏保程序占用大约1 0 0 万台c p u 的空阑时 间，分析寻求外太空生命过程中射电望远镜所产生的数据。i n t c l 公司开发了处理 器开发工具n e t b a t c h ，允许工程师们利用没有使用的1 0 0 0 0 台遍布全球的i n t e l 公 司工作站为芯片的设计执行计算机仿真，在1 0 年里己经为i n t e l 公司节约了5 亿 美元。即时消息方面的著名产品有a o li n s t a n tm e s s e n g e r , y a h o op a g e r 、微软的 m s nm e s s e n g e r 以及i c q 等。和以前在网络上被动接受网络资源相比，从技术角 度而言，p 2 p 提供了利用大量闲置资源的机会，能够有效的消除仅用单一资源造 1 2 山东大学硕十学位论文 成的瓶颈问题；p 2 p 还提供了方便的资源交换功能，能够利用p 2 p 的分散式计算 通过互联网进行合作创建媒体或软件、在线直接交谈、组建在线社区以及社区节 点合作进行病毒探测和报警等。 p 2 p 引导网络计算模式从集中式向分布式偏移，也就是说网络应用的核心从 中央服务器向网络边缘的终端设备扩散；服务器到服务器、服务器到p c 机、p c 机到p c 机，p c 机到w a p 手机所有网络节点上的设备都可以建立p 2 p 对话。 它使人们在i n t e r n e t 上的共享行为被提到了一个更高的层次，使人们以更主动深刻 的方式参与到网络中去。 2 2p 2 p 系统的定义 p 2 p 是一种新的分布式计算模式。在这种模式下，服务器与客户端的界限消 失了，网络上的所有节点都可以“平等”地共享其他节点的计算资源。我们可以定 义p 2 p 系统为： p 2 p 系