（计算机科学与技术专业论文）常量度p2p系统中复杂搜索技术研究.pdf

国防科学技术大学研究生院博士学位论文 摘要 近年来，基于对等结构( p e e r - t o p e e r ，p 2 p ) 的分布式系统在互联网上广泛的 流行起来，成为了当前占据i n t e m e t 主要流量的应用之一。基于分布哈希表 ( d i s t r i b u t eh a s h l a b l e ，d h t ) 的结构化系统是p 2 p 系统的重要组成部分，系统中 的各个节点通过某种规则相互链接，形成具有一定拓扑结构的网络，具有较高的 查询效率。常量度p 2 p 系统作为一种新型的结构化系统，具有邻居节点个数为常 数而查询效率为o ( l o 掣n ) 的特性。常量度p 2 p 系统能有效地减小系统维护开销， 简化系统结构，但同时也面临着容错、数据负载平衡、路由负载平衡等方面的问 题。如何解决常量度系统所面临的这些问题，是一个值得深入研究的课题。 此外，由于p 2 p 系统中往往具有着巨大的节点规模和节点在地理上广泛分布 的特点，因此在大规模p 2 p 环境下的资源搜索面临着两个重要的性能指标：搜索 效率和网络负载。高效的搜索有利于减小搜索的延时，提高用户的满意度；而较 低的网络负载有利于减轻网络流量，减小营运商的成本。特别是在p 2 p 环境下进 行复杂搜索时，面临着搜索效率和消息开销的性能折衷问题：优化其中一个往往 使得另一个表现出较差的性能。进行复杂搜索时，如何在保持搜索效率的同时减 小网络的消息开销将对网格系统、服务组合等应用具有现实的推动作用。 针对上述问题，本文首先拓展了c c c h 网络结构，为每个节点增加3 个邻居 节点，从而形成新的常量度p 2 p 重叠网络，它在负载平衡、路由效率等方面表现 出新的特性。在该系统的基础上，本文围绕复杂搜索中的区间搜索和t o p k 搜索 两个问题展开研究，提出了针对这两个问题的搜索算法，对算法进行的理论分析 和实验模拟表明这两种算法具有较高搜索效率和较低的网络负载。论文的主要贡 献主要包括： ( 1 ) 本文在c c c ( c u b e c o l m e c t e d - c y c l e ) 网络结构的基础上，提出了一种 新的常量度p 2 p 网络c a e t u s 。该系统中每个节点的邻居节点数为6 ，而在节点规 模不超过d x 2 4 的情况下，查询效率为o ( d ) ，其中d 是c c c 网络的维度。本文阐 述了c a c t u s 的拓扑构造、路由算法以及容错机制，并对相关实验及其结果进行了 分析。实验表明c a c t u s 在查询效率、负载平衡、容错性等方面均不逊于现有的常 量度数的p 2 p 系统。特别是与已有的容错算法相比，在节点非正常离开系统的情 况下，c a c t u s 采用了“反馈式”容错算法，使节点恢复邻居关系的消息个数从l o g z n 减小到3 1 0 9 n ，时问开销从l o g n 减小到2 步，从而使得系统具有较强的容错能力。 ( 2 ) 本文在c a c t u s 常量度系统基础上，设计了一种s m a r t - b r o a d c a s t 算法。 该算法根据被搜索区问的范围，动态建立一棵虚拟搜索树。该搜索树的结构与 第i 页 国防科学技术大学研究生院博士学位论文 c a c t u s 系统的底层拓扑结构相匹配，并使得被搜索的节点都聚集在根节点附近， 从而使得单值区间搜索的消息开销为o ( d ) ，而平均路由开销不超过0 ( d ) + ( 1 + 3 d ) m ，其中m 是被搜索区间内所有映射到的节点。本文描述了s m a r t b r o a d c a s t 算法，并在该算法的基础上设计了多属性区间搜索算法。对算法进行理论分析和 模拟实验证实s m a r t - b r o a d c a s t 算法在大规模节点的情况下，具有较小的消息开销 和路由开销。 ( 3 ) 本文在c a c t u s 系统和区间搜索算法的基础上，提出了一种t o p k 搜索算 法一i e s ( i t e r a t i v ee s t i m a t er a n g e s i z e ) 。算法根据资源属性，将资源看作是m 维 空间中的点，而t o p - k 搜索就转换为在m 维空间中搜索距离查询点最近的k 个点。 该算法根据a g r a w a l 发现的资源密集现象，在m 维空间中确定搜索区间大小，并 利用c a c t u s 的多区间搜索算法，迭代地在多个区间中搜索资源，使得算法同时保 持了高效和低负载的特点。本文证明了算法的正确性并分析了它的性能。分析和 实验表明，该算法在高属性维度、低查询维度的情况下，具有较好的查询效率和 较低的网络负载。 主题词：对等计算、d h t 系统、常量度系统、区间搜索、t o p k 搜索 第i i 页 国防科学技术大学研究生院博士学位论文 a b s t p a c t i nr e c e n ty e a r s ，m a n yp e e r - t o p e e r ( p 2 p ) s y s t e m sh a v eb e e np r o p o s e da n d b e c o m et h ea p p l i c a t i o n sw h i c hd o m i n a t et h et r a f f i cb a n d w i d t ho fi n t e r n e t d h t - b a s e d s t r u c t u r e ds y s t e mi sa l li m p o r t a n tc a t e g o r yo fp 2 ps y s t e m e a c hp e e ri nd h ts y s t e m c o n n e c t st oo t h e rp e e r sa c c o r d i n gt os o m ep r o t o c o la n da l lp e e r sf o r ma no v e r l a yw i t h s p e c i f i cn e t w o r kt o p o l o g y , w h i c hr e s u l t si nt h eh i g hl o o k u pe f f i c i e n f yo fd h ts y s t e m a m o n gl o t so fd h t b a s e ds t r u c t u r e dp 2 ps y s t e m s ，t h ec o n s t a n t d e g r e es y s t e mh a st w o n o v e lc h a r a c t e r i s t i c s ：t h en e i 曲b o rd e g r e eo fe a c hp e e ri sc o n s t a n ta n dt h el o o k u p e f f i c i e n c yi so ( 1 0 9 n ) t h ec o n s t a n t - d e g r e es y s t e mc a nr e d u c et h en u m b e ro fm e s s a g e s b e t w e e np e e r sa n ds i m p l i f yt h es y s t e ms t r u c t u r e h o w e v e r , i ta l s of a c e ss o m ed i f f i c u l t p r o b l e m ss u c ha sf a u l tt o l e r a n c e ，1 0 a db a l a n c eo fd a t aa n dr o u t i n gm e s s a g e i ti sag r e a t c h a l l e n g et os o l v et h e s ep r o b l e m si nc o n s t a n t - d e g r e ed h t - b a s e d s t r u c t u r e sp 2 ps y s t e m s i n c et h en u m b e ro f p e e r si su s u a l l yl a r g ea n dp e e r sa r ed i s t r i b u t e dg e o g r a p h i c a l l y a b r o a d l y , t h el o o k u pe f f i c i e n c ya n dn u m b e ro fm e s s a g ea r et w oi m p o r t a n tp e r f o r m a n c e m e t r i c so fr e s o u r c es e a r c ha l g o r i t h m si nl a r g es c a l ep 2 ps y s t e m e f f i c i e n tl o o k u pi s h e l p f u lt or e d u c et h es e a r c hl a t e n c ya n di m p r o v et h ed e g r e eo fu s e r s s a t i s f a c t i o n a n d l o w e rn e t w o r kt r a f f i cl o a di sh e l p f u lt or e d u c et h ed e m a n do nn e t w o r kb a n d w i d t ha n d d e c r e a s et h eo p e r a t i o nc o s t c o m p l e xs e a r c hi np 2 ps y s t e ma l s of a c e sat r a d e - o f f b e t w e e nt h el o o k u pe f f i c i e n c ya n dt h em e s s a g eo v e r h e a d i nt h i st h e s i s ，w es t u d ya b o v ep r o b l e m sd e e p l y f i r s t l y , w ee x t e n dt h ee x i s t i n gc c c t o p o l o g ya n dc o n s t r u c tan e wc o n s t a n t - d e g r e ep 2 po v e r l a yb ya d d i n gt h r e em o r e n e i g h b o r st oe a c hp e e r t h en e wc o n s t a n t d e g r e ep 2 po v e r l a y , c a l l e dc a c t u s i sn o t w o r s et h a no t h e rc o n s t a n t - d e g r e es y s t e mi nt h ea r e ao ff a u l t - t o l e r a t e ，l o a db a l a n c ea n d l o o k u pe f f i c i e n c y s e c o n d l y ，o nt h eb a s eo fc a c t u ss y s t e m ，w es t u d yt h ep r o b l e m so f r a n g eq u e r ya n dt o p kq u e r yi nc o m p l e xs e a r c h f o rt h e s et w op r o b l e m s ，w ep r o p o s e s m a r t - b r o a d c a s ta l g o r i t h ma n di e sa l g o r i t h ms e p a r a t e l y t h e o r e t i c a la n a l y s i sa n d s i m u l a t i o nr e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h m sa r es u p e r i o rt ot h ee x i s t i n g a l g o r i t h m si nl o o k u pe f f i c i e n c ya n dn e t w o r kt r a f f i cl o a d t h em a i nc o n t f i b u t i o i l so f t h i sd i s s e r t a t i o na r e - ( 1 ) ac o n s t a n t - d e g r e es y s t e mc a l l e dc a c t u sh a sb e e np r o p o s e db a s e do nc c c h y p e r e u b e i nc a c t u ss y s t e m , t h en e i g h b o rn u m b e ro fe a c hp e e ri s6a n dt h et i m e c o m p l e x i t yo fk e yl o o k u pi s0 ( d ) w h e nn o d en u m b e ri sn o tm o r et h a nd * 2 0 ，w h e r ed i s t h ed e g r e eo fc c c e x t e n s i v ee x p e r i m e n t a lr e s u l t ss h o wt h a tc a c t u ss y s t e mi sn o t w o r s et h a no t h e re x i s t i n gc o n s t a n t d e g r e es y s t e m si nt h ea r e ao ff a u l t t o l e r a t e 1 0 a d b a l a n c ea n dl o o k u pe f f i c i e n c y i nc a s eo fa b n o r m a ll e a v eo fn o d e s ，c a c t u sa d a p t st h e f e e d b a c kf a u l t - t o l e r a n ta l g o r i t h mt or e s t o r en e i g h b o rr e l a t i o n s h i p c o m p a r e dt oo t h e r 第i j i 页 国防科学技术大学研究生院博士学位论文 c o n s t a n t d e g r e es y s t e m s ，c a c t u sc a l lr e d u c et h en u m b e ro fm e s s a g ef r o ml 0 9 2 nt o 3 1 0 9 na n dr e d u c et h en u m b e ro f h o p sf r o ml o g nt o2 ( 2 ) ar a n g eq u e r ya l g o r i t h mc a l l e ds m a r t b r o a d c a s th a sb e e np r o p o s e do nt h eb a s e o ft h ec a c t u ss y s t e m a c c e d i n gt ot h es e a c h er a n g e ，t h es m a r t b r o a d c a s ta l g o r i t h m d y n a m i c a l l yc o n s t r u c t sa v i r t u a ls e a r c ht r e ew h o s es t r u c t u r ei sc l o s et ot h et o p o l o g yo f c a c t u s q u e r yo fn o d ei nr a n g ec a l lb ed o n ei no ( 1 0 9 n 3h o p sa n dt h ea v e r a g er o u t i n g o v e r h e a di sn o tm o r et h a no ( d ) “l + 3 d ) m ，w h e r emi st h en u m b e ro fp e e r si nt h e q u e r yr a n g e t h el o o k u pe f f i c i e n c ya n dm e s s a g el o a do fs m a r t - b r o a d c a s ta l g o r i t h ma r e v e r yc l o s et ot h ea s y m p t o t i cl o w e rb o u n d so fl a t e n c ya n dm e s s a g ec o s to fr a n g eq u e r i e s i n c o n s t a n t d e g r e ed h ti n f r a s t r u c t u r e s s i m u l a t i o nr e s u l t ss h o wt h a tt h ep r o p o s e d s m a r t - b r o a d c a s ta l g o r i t h mh a sh i g h e rq u e r ye f f i c i e n c ya n dl o w e rm e s s a g el o a dt h a n o t h e ra l g o r i t h m s ( 3 ) ab o t t o m - u pa l g o r i t h mc a l l e di e sh a sb e e np r o p o s e df o rt h ekb e s tm a t c h i n g r e s o u r c ei np 2 pe n v i r o n m e n t e a c hr e s o u r c ei st a k e na sap o i n ti nm d i m e n s i o ns p a c e a n dt h et o p kq u e r yp r o b l e mi st r a n s f e r r e dt os e a r c h i n gt h ekc l o s e s tp o i n t st ot h e e x p e c t e dq u e r yp o i n t b a s e do na g r a w 诅l sd i s c o v e r y , t os e a r c hr e s o u r c e s ，t h ei e s a l g o r i t l u nf i r s t l yd e t e r m i n e st h es i z eo ft h es e a c hr a n g ea n dt h e ns e a c h e sr e s o u r c e si n t h e s er a n g e si t e r a t i v e l yu s i n gt h em u l t i r a n g eq u e r ya l g o r i t h mp r o v i d e db yc a c t u ss y t e m w eh a v ep r o v e dt h ec o r r e c m e s so ft h ei e sa l g o r i t h ma n da n a l y z e di t sp e r f o r m a n c e a n a l ) r s i sa n ds i m u l a t i o ns h o wt h a tt h ei e sa l g o r i t h mh a sl l i g hl o o k u pe f f i c i e n c ya n d l o wn e t w o r kt r a m c1 0 a di nt h ec i r c u m s t a n c et 1 1 a tt h en u m b e ro fr e s o u r c ea t t r i b u t e si s m u c hl a r g e rt h a nt h en u m b e ro f a t t r i b u t e su s e db yc o r l s u m o l - k e y w o r d ：p e e r - t o - p e e r , d h ts y s t e m ，c o n s t a n t - d e g r e es y s t e m ，r a n g eq u e r y , t o p kq u e r y 第i v 页 国防科学技术大学研究生院博士学位论文 表目录 表1各种常量度系统的比较2 5 表2 各种单属性区问搜索技术2 9 表3 节点a ( 0 , 0 1 1 0 ) 的邻居节点表3 7 表4 超立方体优先算法( h y p e r c u b ef i r s ts e a r c h ，h f s ) 3 8 表5s m a r tb r o a d c a s t 算法5 6 表6 请求者建立搜索初始条件5 7 表7 多属性区间搜索算法5 9 表8 图2 9 中二维坐标系统的坐标。7 2 表9 基于区间查询的i e s 搜索算法7 3 表1 0c a c t u s 中确定初始半径r 0 的算法。7 4 表1lc a c t u s 中请求者的i e s 搜索算法。7 5 表1 2c a c t u s 中当前节点的t o p - k 搜索算法7 6 第1 v 页 国防科学技术大学研究生院博士学位论文 图目录 图lg n u t e l l a 系统中各个节点的连接能力分布图5 图2e m u l e 所反映的节点连接的频繁变化。6 图3 一致性哈希算法1 7 图4c h o r d 系统中节点负责的标识空间1 8 图5 路由效率折衷渐进线2 2 图6c y c l o i d 的邻居节点关系2 4 图7 属性区问【o ，1 】的k a u t z 树t ( 2 ，4 ) 2 8 图8c c c 网络拓扑结构图3 4 图9c a c t u s 构造的虚拟二叉树3 6 图l o 四维c a c t u s 系统简图3 6 图1 l 叶节点抢占算法。4 4 图1 2 不同系统的平均路由长度4 5 图1 3 稀疏节点的平均数据负载4 6 图1 4 稠密节点的平均数据负载。4 7 图1 5c a c t u s 与树结构的系统的路由负载比较。4 8 图1 6c a c t u s 与c y c l o i d 每层节点的路由负载比较4 8 图1 7 不同节点失效概率下的平均查询长度。4 9 图1 8 不同规模的节点离开的容错性能5 0 图1 9 单属性区间映射。5 3 图2 0 以1 0 1 0 为根的搜索树5 4 图2 14 维c a c t u s 中第二维上的区间搜索树。5 9 图2 2 不同策略的路由效率比较6 4 图2 3 不同策略的路由效率和消息开销的比较。6 5 图2 4 路由开销与节点规模的关系。6 5 图2 5 路由开销与搜索区间大小的关系6 6 图2 6 消息开销与被搜索区间大小的关系6 7 图2 7 实验消息开销与理论上下界的差距。6 7 图2 8 聚类在不同维度上的投影。7 1 图2 9 二维坐标系统。7 2 图3 0 在搜索树上获得搜索区间大小7 6 图3 1t o p 1 0 查询的平均访问节点数量8 0 第v 页 国防科学技术大学研究生院博士学位论文 图3 2 不同属性个数下t o p k 一1 0 查询的嗍络开销8 1 图3 3 在不同节点规模下t o p - k 1 0 查询的网络开销8 1 图3 4 不同属性利用率下的查询效率。8 2 图3 5 不同节点规模的查询效率8 2 第v i 页 国防科学技术大学研究生院博士学位论文 【1 】p 2 p 【2 c c c 【3 i e s 【4 】d h t 【5 】c s 【6 】b s 【7 】r i a a 【8 】h t l 【9 】b f s 1 0 】m i t 1 1 1 】s h a 【1 2 】m d 5 【1 3 】m s d b 【1 4 】s f c 【1 5 】d c f 【1 6 】t a 【1 7 】r r l 【1 8 h f s 【1 9 t f s 【2 0 】r c 【2 1 】m c 2 2 】n p c 2 3 】s a t 缩略语表 p e e r t op e e r c u b e c o n n e c t e d - c y c l e i t e r a t i v ee s t i m a t er a n g e s i z e d i s t r i b u t eh a s h 皿出l e c l i e n t s e r v e r b r o w e r s e r v e r r e c o r d i n gi n d u s t r ya s s o c i a t i o no f a m e r i c a h o p s t ol i v e b r e a t hf i r s ts e a r c h m a s s a c h u s e t t si n s t i t u t eo f t e c h n o l o g y s e c u r eh a s ha l g o r i t h m m e s s a g ed i g e s ta l g o r i t h m5 m o s ts i g n i f i c a n td i f f e r e n tb i t s p a c ef i l l i n gc u r v e d i r e c t e dc o n t r o l l e df l o o d i n g t h r e s h o l da l o r g i t h m t i m e t o l i v e h y p e r c u b ef i r s ts e a r c h t r e ef i r s ts e a r c h r e q u e s t e rc o o r d i n a t i o n m i d - p o i mc o o r d i n a t i o n n e a r e s t - p o i n tc o o r d i n a t i o n s i m p l ea l g o r i t hf o rt o p k 第1 0 1 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意 学位论文题目：鲎量廛里2 里丞缝生塞盘握塞挂盔班窒 学位论文作者签名：盘壑 日期：枷“年? 月工7 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复稍手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目t堂量廑至2 里丞红生复壅撞室挂丕班塞 学位论文作者签名 作者指导教师签名 日期：伽“年7 月a 7 日 日期：多卯乡年夕月2 7 日 国防科学技术大学研究生院博士学位论文 第一章绪论 自1 9 9 9 年以来，由于i n t e m e t 的广泛普及、网络带宽的大幅增加以及基于 i n t e m e t 的端系统计算能力的迅速增强，p e e r - t o p e e r 重叠网络( p 2 po v e r l a y ) 【2 】模 式逐渐成为研究和应用的热点。以往的分布式计算模型( 如c s 、b s 等) 往往考 虑如何充分利用和发挥服务器能力，而忽略了客户端的能力。然而随着个人计算 机的日益强大，c s 模型导致客户端资源的巨大浪费。为此，p 2 p 网络作为一种能 充分利用网络上所有资源，在多个节点之间直接交换数据的新型模型，受到了用 户的欢迎，也引起了学术界的广泛关注，具有广阏的应用前景。 1 1p 2 p 计算概述 在分布式计算中的c l i e n t s e r v e r 模型中，客户端只从s e r v e r 端获取数据，而 不( 或极少) 向s e r v e r 提供数据。如果普通用户拥有的节点只是以客户机的方式 连接到网络中，仅仅作为信息和服务的消费者，游离于互联网的边缘，那么对于 这些边际节点的能力来说，存在极大的浪费。p 2 p 系统与之相比，显著的区别就是 p 2 p 系统中的所有节点既从系统其他节点处消费服务，也向其他节点提供服务，使 得每个节点理论上在系统中具有相等的权利和义务，同时具备s e r v e r 和c l i e m 的 双重身份。当前不同的个人和组织对着这种计算模型都有不同的定义，其中具有 代表性的是o a ys h i r k e y 的模型定义u j ： “p 2 p 是一种利用位于i n t e m e t 边缘的各种可用资源( 如存储空间、计算能力、 媒体内容) 的应用。由于网络上大量的节点工作在d n s 系统之外，这些分散的资 源具有不稳定的连通性和未知的i p 地址。访问这些分散的资源，就意味着要在连 接不稳定和i p 地址不可预见的环境里工作。因此，p 2 p 节点必须能够独立于d n s 系统且高度自治”。 p 2 p 系统试图在i n t e m e t 的基础架构之上建立一个新的自治的覆盖网络，通过 整合多个节点服务的方式，利用一切可以利用的资源为节点提供高质量的服务。 但是该系统也面临着节点自治、扩展性、系统容错、节点广泛分布等方面的特点 和难点，从而引发了人们对p 2 p 系统研究的兴趣和热情。 1 1 1p 2 p 系统的发展历史 从最初的i n t e m e t 的基础架构a r p a n e t 和t c p i p 协议来看，i n t e m e t 中的节 点也是平等的两端，并没有能力的强弱之分。但由于当时的个人计算机处理能力 有限且分配给个人用户的带宽有限，使得具有强大的计算能力和高带宽的大型站 第l 页 国防科学技术大学研究生院博士学位论文 点成为了网络的中心。这些站点往往具备有丰富内容，能同时为多个客户端提供 服务且对客户端的资源要求少，从而形成了c l i e n t s e r v e r 模型。 随着个人计算机的处理能力e 益强大，当前的个人计算机甚至超越了2 0 世纪 9 0 年代一些服务器的能力；与此同时，随着i n t e m e t 基础设施的建设，分配给个人 的带宽从几k 增长到上百k 甚至上兆的规模。这些硬件和基础设施的发展为p 2 p 技术的出现提供了强大的支持。此外，虽然每个计算机可以共享的数据不多，但 是由于接入i n t e m e t 的计算机达到上亿的规模，使得分散在各个计算机上的资源能 通过互联网聚合在一起，共同为一个或多个节点服务，从而为p 2 p 技术的出现提 供了内容和性能支持。 1 9 9 9 年，文件共享系统n a p s t e r 【4 】作为一种新型的网络应用出现在互联网上， 为i n t e r n e t 上的用户提供m p 3 音乐文件共享和交换服务。他帮助用户快速的搜索 自己喜欢的音乐，并引导用户之间相互提供文件下载，使得用户搜索的准确性和 下载的速度得到较大的提高。n a p s t e r 采用中心索引服务器来维持系统中所有对等 节点所共享的音乐文件信息。当节点使用n a p s t e r 客户端软件第一次登录到中心索 引服务器时，向服务器注册登记其共享的音乐文件列表。当节点需要查找某个音 乐文件时，向中心索引服务器提供搜索查询请求；服务器在收到该请求后根据查 询关键字为请求节点返回节点列表：节点一旦收到查询反馈，则从节点列表中选 择一合适的节点，并直接与该节点进行连接以下载目标音乐文件。这些特性使得 n a p s t e r 迅速取得了巨大的成功，是成长最快的i n t e r n e t 应用之一，创立一年半后 ( 2 0 0 1 年1 月) 用户就达到了5 千万。虽然在1 9 9 9 年1 2 月r i a a ( r e c o r d i n gi n d u s t r y a s s o c i a t i o no fa m e f i c a ) 起诉n a p s t e r 的音乐文件交换服务侵犯了音乐版权后， n a p s t e r 被法院判决停止进行有版权的音乐文件交换，但是p 2 p 作为一种新的信息 交换模式已经不可避免的流行开来。 n a p s t e r 采用的集中式服务器方式带来了性能瓶颈、单点失效等方面的问题， 特别是版权问题使得他被迫停止运行。根据这些问题，新一代完全分布式网络被 建立起来：如g n u t e l l a 【5 】、f r e e n e t t 6 1 等。在这些网络中没有集中服务器，各个节点 的权利和义务完全是相同的。节点根据某个算法存贮数据或数据的索引，同时他 也根据某个算法请求数据或转发搜索请求，从而避免了集中数据库带来的一些问 题。但是这样的系统同时也产生了容错、系统维护等问题，成为了p 2 p 系统研究 的重点。 n a p s t e r 的另外一个问题是：在文件下载时，用户采用的依然是类似传统的c s 模式。这种方式对应大小不超过1 0 m 的m p 3 来说是足够了。但是，由于个人的带 宽依然是非常有限的，因此对于大容量的电影、资料等来说，下载的速度相对较 小。针对这种情况，b i t t o r r e n t 7 1 为下载大容量资源提供了新的途径。b i t t o r r e n t 采 第2 页 国防科学技术大学研究生院博士学位论文 用了w e b 发布，服务器引导下载的模式。用户将共享文件的元信息( 文件名、文 件大小、分块大小等) 发布到w e b 上和服务器上；其他用户得到该元信息后，登 录到t r a c k e r 服务器，该服务器从当前正在下载该文件的所有用户中按照随机邻居 选择算法，将最近的一组节点信息交给该用户。然后该用户与这些节点建立邻居 关系，从而能从该组所有用户中并发下载该文件；与此同时，该用户也必须将自 己已经下载的数据内容共享给其他用户。b i t t o r r e n t 的下载模式体现了一种“人人 为我，我为人人”的共享精神，成为当前大容量数据下载的主要模式。他使得信 息的传递拓扑从原来星型为主的结构，变成了从稀疏到紧密的网状结构；一个节 点可以同时连接多个节点，从而充分利用网络带宽，提高了下载的速度。b i t t o r r e n t 的出现为大容量数据的共享提供了新的途径，从而吸引了大量的研究，包括测量 研究限9 】、大容量数据下载模型研究1 0 1 、下载改进算法研究1 1 l - 1 3 1 等。 b i t t o r r e n t 将下载的节点分为两类：一类是拥有完整内容的节点，称为种子节 点；一类是拥有部分内容的节点，称为普通节点。由于b i t t o r r e n t 采用了w e b 发 布的形式。使得下载具有一定的时效性：如果网络中不存在种子节点，则用户不 能下载到完整的内容。其中，b i t t o r r e n t 不提供搜索机制，使得节点不能搜索网络， 以获得需要的内容。e m u l e 根据这种情况，将分布式搜索服务器与多节点共同下 载模式结合起来，为用户提供搜索、下载、共享等多种服务。e m u l e 将多个服务 器连接成一个超级节点网络，而用户只要登录其中一台服务器就可以进入这个超 级网络。同时用户共享的数据被分割为大小相同的数据块，每个数据块都形成m d 4 摘要，这些摘要被放置在服务器上供其他用户搜索。e m u l e 的用户只要搜索自己 需要的内容，e m u l e 就在所有的服务器上搜索该内容涉及到的所有数据块的摘要， 然后将拥有这些数据块的节点信息返回给请求者。请求者这时采用与b i t t o r r e n t 相 同的方式从多个节点处下载数据，并向其他节点上载自己拥有的数据。e m u l e 使 得只要网络中存在该数据块就一定可以被用户下载，以保证即使无种子节点，用 户也可以下载到完整内容；其次，e m u l e 采用了一定的激励机制，使得用户愿意 共享自己的数据，以保证网络拥有丰富的数据源；再次，e m u l e 同时采用了e d o n k e y 服务器和k a d e m l i a t l 4 1 网络，提高了网络的容错性和搜索的有效性。这样，如何在 网络中搜索有效的数据、如何激励用户、如何提供稳定的网络拓扑成为了研究的 重点。 现在，p 2 p 系统已经深入到文件共享、数据存储、网格计算、流多媒体等多个 应用领域。据统计，耳前i n t e m e t 上各类p 2 p 应用的流量己占骨干网流量的6 0 以 上【1 5 j 。这些p 2 p 应用系统的流行使得p 2 p 计算技术得到了整个社会的广泛关注， 获得了工业界的广泛支持。如i n t e l 公司联合h p 、s o n y 等公司成立了p 2 p 工作组 ( p 2 pw o r k i n gg r o u p ) ；m i c r o s o f t 在其n e t 框架下提出了支持p 2 p 的n e tm y 第3 页 国防科学技术大学研究生院博士学位论文 s e r v i c e ；s u n 公司则推出了j x t a 项目等。与此同时，学术界也对p 2 p 模型进行广 泛研究。自2 0 0 0 年起，在e o s d i 、s o s p 、s i g c o m m 、u s e n i x 、h o t o s 等系 统结构方向的项级会议上不断出现关于p 2 p 系统的重要研究成果。国际上也召开 了专门针对p 2 p 计算的国际会议，如i n t e m a t i o n a lw o r k s h o po np 2 pc o m p u t i n g 、 g l o b a la n dp 2 pc o m p u t i n go i ll a r g es c a l ed i s t r i b u t e ds y s t e m s 、i n t e r n a t i o n a l c o n f e r e n c eo np 2 pc o m p u t i n g 、o r e i l l yp 2 pa n dw e bs e r v i c e 等，特别是i e e e 的 i p t p s 会议上，发表了大量关于p 2 p 的优秀论文，是p 2 p 研究的风向标。从2 0 0 2 年开始，b e r k e l e y 、s t a n f o r d 等著名大学相继开设了p 2 p 相关的研究生课程，进一 步推广了p 2 p 这一新兴