（计算机应用技术专业论文）大规模对等资源共享关键技术研究.pdf

摘要 摘要 对等( p 2 p ) 计算模型是一种相对于客户机服务器( c s ) 模型的新兴分布式 计算模型，能够有效利用网络边界资源，具有自组织、大规模、可扩展、高效和 低成本等技术优势。基于对等架构，可以构建健壮的、大规模的互联网应用，其 中最重要的是大规模对等资源共享，其所产生的流量是互联网流量的主要成分， 因此，研究大规模对等资源共享具有重要的理论意义和实用价值。 大规模对等资源共享的关键技术包括资源的搜索和内容的分发。由于p 2 p 模 式中资源分布在不同的结点，且无全局的状态信息和集中的中央控制结点，这些 特点给大规模资源共享带来了挑战。虽然现有的研究成果已经解决了其中部分问 题，但是随着实际系统的运行，新的难题不断出现，高效的稀有数据项查询和高 效的内容分发就是亟待解决的难题。 针对上述问题，本文从资源搜索和内容分发两个方面展开研究，提出新型的 复制策略来提高稀有数据项的搜索性能；通过数学建模、体系结构和流量优化等 方面来解决对等内容分发中的问题。主要贡献包括： 1 提出一种新的数据项复制与搜索策略d r s 。首先，根据无结构对等网络 中结点度的幂律分布特征，通过数学分析表明幂律随机图中的带偏随机游走能够 快速命中网络中的高度结点，并采用模拟的方式验证了这种特征；然后，基于上 述特征设计了基于带偏随机游走的复制与搜索策略d r s ，将数据项定向复制到网 络中小部分高度结点，资源搜索采用相同的方式进行。分析和模拟结果表明，所 提出的资源搜索算法能够以低消息开销和低延迟获得高的搜索成功率。d r s 特别 适用于对稀有数据项的管理与搜索，能够提高对等资源共享系统的性能。 2 提出一种基于随机微分方程的通用p 2 p 文件分发模型。根据实际系统分 类结点，分别对各类结点进行量化分析，基于随机微分方程建立系统的动态模型。 所建模型抽象邻居选择策略和结点到达率，能够支持各种邻居选择算法和不同的 结点到达率，并基于该模型分析了现有的邻居选择策略和结点到达率。通过与实 际系统的跟踪数据进行对比，所提出的模型能够准确描述现有的p 2 p 协作式文件 共享系统，是一种通用、实用的模型，有助于评估现有的方案，设计优化的系统。 3 提出了基于g n u t d l a 网络的无t r a c k e r 对等协作式文件共享系统 摘要 g n u t e l l a b t 。p 2 p 文件共享是重要的互联网应用之一，其中b i t t o r r e n t 是最有效的 p 2 p 协作式文件分发协议，同时也是此类系统事实上的标准。然而，现有的 b i t t o r r e n t 协议采用网页的形式发布t o r r e n t 文件，且需要专用的t r a c k e r 结点提供 邻居分配服务，这种架构存在多种不足，阻碍了b i t t o r r e n t 协议的应用。c m u t e l l a b t 利用g n u t e l l a 网络的搜索功能实现t o r r e n t 文件的查询，使得p 2 p 文件共享系统可 以脱离w w w 而运行；通过在特定t o r r e n t 网络上的随机游走来实现邻居分配功 能。设计了一种两层架构来实现上述功能，通过模拟实验表明，g n u t e l l a b t 能够 在脱离w w w 和t r a c k e r 结点的条件下有效运行。 4 提出了互联网服务提供商( i s p ) 感知的b i t t o r r e n t 流量优化方案s t r a c k e r 。 s t r a c k e r 由不同i s p 中的t r a c k e r 代理构成，这些t r a c k e r 代理之间以p 2 p 方式连 接，完成结点维护和i s p 感知的邻居分配。分析和模拟结果表明，s t r a c k e r 能够 在不增加内容下载时间的条件下，大量降低跨i s p 流量。s t r a c k e r 能够有效降低 i s p 的运营成本，提高互联网的效率。s t r a c k e r 的提出能够有效解决b i t t o r r e n t 协 议中存在的不足。 本文的研究成果解决了大规模对等资源共享中资源搜索和内容分发的关键问 题，能够有效提高资源搜索的性能，优化对等内容分发的流量，提高互联网的效 率。 关键词：对等计算，资源搜索，内容分发，流量优化 a b s t r a c t c o m p a r e d 、) l ，i mc l i e n t s e r v e r ( c s ) m o d e l ，p e e r - t o p e e r ( p 2 p ) i sa l le m e r g i n g c o m p u t i n gm o d e l ，w h i c hc a ne x p l o i tr e s o n r c eo nt h ee d g eo fn e t w o r ke f f i c i e n t y p 2 pi s c h a r a c t e r i z e db ys e l f - o r g a n i z a t i o n ，l a r g es c a l e ，s c a l a b l e ，e f f i c i e n t ，a n dl o wc o s t m a n y r o b u s ta n dl a r g es c a l ei n t e r n e ta p p l i c a t i o n sc a l lb ec o n s t r u c t e dw i t hp 2 pa r c h i t e c t u r e a m o n gt h e m ，t h em o s ti m p o r t a n to n ei sl a r g es c a l ep 2 pr e s o l l c es h a r i n gw h i c h a c c o u n t sf o r t h em a j o r i t yo ft o d a y si n t e r a c tt r a f f i c t h e r e f o r e ，r e s e a r c ho nl a r g es c a l e p 2 pr e s o u r c es h a r i n gt e c h n i q u e sh a ss i g n i f i c i e n tt h e o r e t i ca n d p r a c t i c a lv a l u e s t h ek e yp o i n t so fl a r g es c a l ep 2 pr e s o u r c es h a r i n ga r er e s o u r c es e a r c ha n de o n e n t d i s t r i b u t i o n p 2 pi saf u l l yd i s t r u b t e ds y s t e m r e s o u r c e sa r ed i s t r i b u t e dt h r o u g h o u tt h e n e t w o r k t h e r ea r en og | o b a ls t a t ea n dac e n t r a lc o n t r o ln o d e t h e s ea t t r i b u t e s c h a l l e n g et h el a r g es c a l ep 2 pr e s o u r c es h a r i n g a l t h o u g hm a n yp r o b l e m sh a v eb e e n s o l v e d ，n e wp r o b l e m sa r ce m e r g i n gw i mt h eo p e r a t i o n so fr e a ls y s t e m s ，w h i c hi n c l u d e e f f i c i e n ts e a r c ha l g o r i t h m sf o rr a t ei t e m sa n de f f i c i e n tc o n t e n td i s t r i b u t i o np a r a d i g m s t oa d d r e s sa b o v ep r o b l e m s ，t h i sw o r kf o c u s e so nr e s o u r c es e a r c ha n dc o n t e n t d i s t r i b u t i o n f i r s t l y , n e wr e p l i c a t i o ns t r a t e g i e sa r ee m p l o y e dt oi m p r o v et h es e a r c h p e r f o r m a n c eo fr a r ei t e m si nu n s t r u c t u r e dp 2 p s t h e n ，t h i sw o r ka t t a c k sp r o b l e m si n p 2 pc o n t e n td i s t r i b u t i o ni nt e r m so fm a t h e m a t i c a lm o d e l ，a r c h i t e c t u r e , a n dt r a f f i c o p t i m i z a t i o n t h em a i nc o n t r i b u t i o n so f t h i sw o r ka r ea sf o l l o w s ： 1 an o v e li t e mr e p l i c a t i o na n ds e a r c hs t r a t e g yi s p r o p o s e d ，w h i c hi sd r s u n s t r u c t u r e dp 2 pn e t w o r k sa r ec h a r a c t e r i z e d b yp o w e r - l a wd i s t r i b u t i o no fn o d e d e g r e e s f i r s t l y , b i a s e d r a n d o mw a l kc a nc o v e rh i 曲d e g r e en o d e sr a p i d l yi np o w e r - l a w r a n d o mg r a p h s ，w h i c ha r ev a l i d a t e db yb o t hm a t h e m a t i c a la n a l y s i sa n ds i m u l a t i o n s t h e n ，r e p l i c a t i o na n ds e a r c hs t r a t e g yb a s e do nb i a s e dr a n d o mw a l ki sd e s i g n e d b y d i r e c t i o n a lr e p l i c a t i o ni t e mt oh i g hd e g r e en o d e s ，i ti sv e r ye a s yt os e a r c ht h e s ei t e m s a n a l y s i sa n ds i m u l a t i o n ss h o wt h a tt h ep r o p o s e ds e a r c ha l g o r i t h mc a na c h i e v eh i 曲 s e a r c hs u c c e s sr a t ew i t hl o w m e s s a g eo v e r h e a da n dl o wd e l a y d s ri sv e r ys u i t a b l ef o r s e a r c h i n gr a r ei t e m s ，f o re x a m p l es y s t e ms t a t ei n f o r m a t i o n ，i nu n s t r u c t u r e dp 2 p i i i a b s l r a c i s y s t e m sa n di m p r o v e st h ep e r f o r m a n c eo fp 2 pr e s o u r c es h a r i n g 2 ag e n e r a ls t o c h a s t i c e q u a t i o n - b a s e dm o d e lf o rp 2 pf i l ed i s t r i b u f i o ni s p r e s e n t e d n o d e s a r ed i v i d e di n t o c a t e g o r i e sa c c o r d i n gr e a ls y s t e m sa n dt h e c o r r e s p o n d i n gq u a l i t ym o d e l sf o rn o d e sa r ea l s oc o n s t r u c t e d c o m b i n i n gw i t ht h e d y n a m i c so fn o d e s ，as t o c h a s t i ce q u a t i o n - b a s e dm o d e li sp u tf o r t h n e wm o d e la b s t r a c t n e i g h b o rs e l e c t i o ns t r a t e g i e sa n dn o d ea r r i v a lr a t e t h e r e f o r e ，i tc a ns u p p o r td i f f e r e n t n e i g h b o rs e l e c t i o na l g o r i t h m sa n dn o d ea r r i v a lr a t e b a s e do nt h ep r o p o s e dm o d e l ， d i f f e r e n tp a r a m e t e rs e t t i n g sa r ea n a l y z e d f u r t h e r m o r e ，ar e a ls y s t e mt r a c ed a t a s e ti s e m p l o y e dt oe v a l u a t et h ep r o p o s e dm o d e l t h er e s u l t ss h o wt h a tt h ep r o p o s e dm o d e l c a r ld e s c r i b et h ed y n a m i c so fp 2 pf i l ed i s t r i b u t i o ns y s t e m sa c c u r a t e l y t h ep r o p o s e d m o d e li sag e n e r a la n dp r a c t i c a lm o d e lw h i c hc a nb eu s e dt oe v a l u a t e e x i s t i n g p a r a d i g m sa n dd e s i g nn e wo n e s 3 g n u t e l l a b ti sp r o p o s e dt oa d d r e s st h ea r c h i t e c t u r ep r o b l e mo fb i t t o r r e n t p 2 pf i l es h a r i n gi so n eo ft h em o s ti m p o r t a n ti n t e r a c ta p p l i c a t i o n s a m o n gt h e m ， b i t t o r r e n ti st h em o s te f f i c i e n tp 2 pc o l l a b o r a t i v ep r o t o c o lf o rf i l ed i s t r i b u t i o na n dt h e d ef a c t os t a n d a r do ft h i sk i n do fs y s t e m s h o w e v e r , t h ea r c h i t e c t u r eo fc u r r e n t b i t t o r r e n th a ss o m es h o r t c o m i n g sw h i c hd e c r e a s ei t sr e l i a b i l i t y i tr e q u i r e sw w w t 0 p u b l i s ht o r r e n tf i l e sa n dad e d i c a t e dt r a c k e rn o d ef o rn e i g h b o ra l l o c a t i o n g n u t e l l a b t m e r g sg n u t e l l aa n db i t t o r r e n tt or e m o v ea b o v es h o r t c o m i n g s b ye x p l o i t i n gt h e s e a r c hf u n c t i o n a l i t yo fag n u t e l l an e t w o r k , t o r r e n tf i l e sc a l lb el o c a t e de f f i c i e n t l y w i t h o u t r v 州：t oa l l o c a t i o nn e i g h b o r sr a n d o m l y , g n u t e l l a b te m p l o y sr a n d o mw a l k o nas p e c i f i ct o r r e n tn e t w o r k t w o - t i e ra r c h i t e c t u r ei sd e s i g n e dt oi m p l e m e n ta b o v e f u n c t i o n s s i m u l a t i o n ss h o wt h a tg n u t e l l a b tc a nw o r ka sw e l la so r i g i n a lb i t t o r r e n t w i t h o u t 冈订 厂a n dt r a c k e rn o d e s 4 a ni s p 。a w a r eb i t t o r r e n tt r a f f i co p t i m i z a t i o ns c h e m ei sp r o p o s e d ，w h i c hi s c a l i e ds t r a c k e r t h es t r a c k e ri sc o m p o s e do ft r a c k e rp r o x i e si nd i f f e r e n ti s p s w h i c h a r ec o n n e c t e dw i t hp 2 pa r c h i t e c t u r e 。乃a c k e rp r o x i e sa r ee o l l a b o r a t i v et op e r f o r mn o d e i n f o r m a t i o nm a n a g e m e n ta n di s p a w a r en e i g h b o ra l l o c a t i o n t h en o d em a n a g e m e n t a n dn e i g h b o ra l l o c a t i o na l g o r i t h m sa r ea l s od e s i g n e da n di m p l e m e n t e d a n a l y s i sa n d s i m u l a t i o n ss h o wt h a ts t r a c k e rr e d u c e st h ec r o s s i s pt r a f f i cm a s s i v e l yw i t h o u t i n c r e a s i n gt h ed o w n l o a dt i m e s t r a c k e rc a ne f f i c i e n t l yi m p r o v et h ee f f i c i e n c yo f i n t e r a c ta n dd e c r e a s et h eo p e r a t i o nc o s to fi s p s i v a b s t r a c t t h er e s u l t so ft h i sw o r ks o l v e dt h ek e yi s s u e si nl a r g es c a l ep 2 p r e s o u r c 宅s h a r i n g d s rc a ne f f i c i e n t l yi m p r o v et h es e a r c hp e r f o r m a n c ef o rr a r ei t e m si nu n s t r u c t u r e dp 2 p n e t w o r k s n eg e 】a c r a lm o d e lf o rp 2 pc o n t c nd i s t r i b u t i o ni sae 1 0 r cr e a s o n a b l e a p p r o a c hf o ra l g o r i t h md e s i g na n de v a l u a t i o n g n u t e l l a b tc a ni m p r o v et h er e l i a b i l i t y o fp 2 pc o n t e n td i s t r i b u t i o ns y s t e m s 。s 砌c k c rc a nm a s s i v e l yr e d u c e 曲ec r o s s i s p t r a f f i ca n di m p r o v et h ee f f i c i e n c eo fi n t c r n e t k e y w o r d s ：p e e r - t o p e e rc o m p u t i n g , r e s o u r c es e a r c h ，c o n t e n td i s t r i b u t i o n ，t r a f f i c o p t i m i z a t i o n v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示谢意。 签名：_ 立卜啸w 夕年堋t 日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 虢毕 导师签名 醐：跏夕铂堋f 日 第一章绪论 第一章绪论 p 2 p 应用对整个互联网产生了重要影响，成为当前的研究热点之一，本文集 中于研究大规模对等资源共享中的关键问题。本章主要说明选题依据和意义、本 文的主要研究内容和研究工作的主要的创新点及取得成果，最后对本文的后续章 节安排进行说明。 1 1选题的依据及意义 本节从技术发展趋势、p 2 p 的技术优势和大规模对等资源共享所面临的挑战 来说明选题的依据及意义。 1 1 1 技术发展趋势 计算模式的发展经历了集中式、分布式、对等计算等，而且还在继续发展。 集中式计算模式下，一台大型机连接多个终端，用户通过终端分时共享主机提供 的计算服务。相对于独占资源而言，分时共享能够提高资源的利用率，增加系统 的吞吐率。随着网络技术的出现与应用，计算机之间能够实现通信，功能强大的 计算结点可以为功能较弱的结点提供计算服务，因此出现了客户机朋艮务器( c s ) 计算模式。c s 模式中计算任务主要由服务器完成，客户机只完成少量的工作， 这种模式适用于服务器功能强大而客户机功能较弱的条件。信息技术行业的摩尔 定律说明了信息技术的飞速发展，无论是主干网还接入网络，其带宽都是几年前 不能想像的，个人电脑功能的提高，存储设备成本的降低，上述发展导致了网络 边界的大量空闲资源。另一方面，用户对文件的共享需求迅速增加，特别是视频 文件、音频文件，这些是f t p 服务器内容的主要成分，而f t p 服务器无法有效满 足用户的需求。如何有效利用网络的空闲资源和如何有效共享内容成为两个表面 不太相关且迫切需要解决的问题。 19 9 9 年，s h a w nf a n n i n g 发布了世界上第一个p 2 p 网络软件n a p s t e r ，其注册 用户迅速到达5 0 0 0 0 万，而高峰时期的用户数达到2 6 4 0 万。n a p s t e r 的轰动效应 启发了学术界和产业界对对等计算模式的关注，导致了今天对对等计算的研究热 电子科技大学博士学位论文 潮。对等计算中，所有结点具有等价的地位，结点既是服务的请求者是提供者， 结点自主的加入和退出系统。对等计算利用空闲的网络资源为用户提供可扩展的 资源共享服务，既解决了空闲资源的利用问题又解决了高效资源共享问题。当前， 对等计算主要用于以下领域： ( 1 ) 对等搜索，如：c m u t e l l a 、c h o r d 等 ( 2 ) 内容分发，如：b i t t o r r c n t 等 ( 3 ) 网络电话，如：s k y p c 等 ( 4 ) 流媒体，如：p p l i v c ，c o o l s t r c a m i n g f l 】等 对等计算技术在上述领域的成功应用表明了该技术的有效性，能够有效解决 用户的需求。另一方面，实际系统的运行也揭示了大规模对等内容分发系统存在 的不足及迫切需要解决的问题。本文围绕大规模对等内容分发展开研究，解决其 中存在的关键问题。 1 1 2 对等计算的技术优势 信息基础设施的发展催生了p 2 p 技术的蓬勃发展，个人计算机性能的提高， 终端用户接入带宽的增加，导致大量的空闲资源，p 2 p 的本质就在于有效利用参 与结点的资源，使得结点既是服务的请求者也是提供者。与传统的c s 模式相比 较，对等计算具有不可比拟的优势，如可扩展、低成本、自组织、健壮性等技术 优势【2 一钉，这些特点的具体说明如下。 ( 1 ) 可扩展 可扩展性是指系统能否很好地适应规模的增长。通常，随着系统规模的增加， 如果系统的性能基本不受影响或者发生线性变换，则认为系统具有很好的可扩展 性。传统的c s 模式，服务器的能力是固定的，限制了其能并发服务的结点数量， 当并发服务请求增加时，服务器成为整个系统的瓶颈，其服务性能显著下降，c s 模式的可扩展性较差。对等网络中，结点既是客户机又是服务器，结点在使用服 务的同时又提供服务，新结点加入系统可能需要服务，同时带来了额外的服务能 力，使整个系统的服务能力随着系统规模的增加而增长。对等网络的工作模式决 定了其内在的可扩展性，实际系统的运行也说明对等系统具有很好的可扩展性， 如g n u t c l l a 网络的活跃结点数量通常超过1 百万【5 】。 ( 2 ) 低成本 2 第一章绪论 互联网应用的成本主要来自于两方面t 第一为基础设施的固定投资；第二为 运营成本。基于c s 模式的互联网应用，如w e b 服务，其服务器设施需要大笔 资金投入，同时需要向互联网服务提供商( i s p ) 提供接入费用。当负载增长时， 需要更多的网络资源，即需要向i s p 付更多的费用。对等计算能够有效利用网络 边界资源，如网络带宽、c p u 处理能力等，这些资源无需额外付费，因此能有效 降低运营成本。对等计算具有很好的可扩展性，即使负载发生变化的条件下，也 无需增加投入，就成本而言，对等计算模式是构建大规模互联网应用的更优模式。 ( 3 ) 自组织 对等网络是动态系统，结点任意加入或退出系统，无需专用的中央结点维护 系统的完整性。系统中的结点只具有局部的网络状态信息，即邻居结点信息，依 赖这些信息，所有结点相互连接，构成一个复杂的网络系统。结点之间相互协作， 共同实现系统的功能，当系统发生动态变化时，相关结点更新其状态信息，保持 系统的正常运行。自组织特性将系统维护开销分摊到所有结点，能够很好的适应 系统的动态性。 ( 4 ) 鲁棒性 大规模网络系统中，网络故障、结点故障的发生是不可避免的，这些故障对 系统的稳定性和服务质量造成影响。在c s 模式下，服务器成为整个系统的关键 结点，一旦服务器发生故障，导致整个系统的崩溃。在对等模式下，系统的服务 能力是结点服务能力的聚集，系统的服务能力是分散在不同的结点，而且结点提 供的服务具有冗余性。因此，部分结点和网络发生故障时，对整个系统的影响不 会太大，保证了系统的稳定性和服务的可用性。对等网络还是一个动态的自组织 系统，结点和网络故障触发网络的重新布局，形成新的稳定系统。因此，对等模 式具有很高的鲁棒性。 ( 5 ) 隐私保护 对等网络中，结点只维护局部的状态信息，无法直接获得其它结点的信息， 这种结构为隐私保护提供了基础。当结点接收到一条消息时，如果在该消息里没 有标明相关信息，该结点无法确定这条消息的来源，甚至无法知道其目的结点。 结合密码学手段，对等网络能够很容易地实现匿名功能【6 锕，包括发送者匿名、接 收者匿名和发送者接收者互匿，从而达到保护用户隐私的目的。相对而言，c s 3 电子科技大学博士学位论文 模式中，服务器掌控系统的全局信息，能够获得结点的所有访问信息，因此很难 实现隐私保护功能。 当前，互联网应用的显著特点是大规模、动态性、隐私保护需求等，而对等 计算能够很好的满足上述需求。因此，对等计算成为构建大规模互联网应用的首 选架构之一，特别是资源共享，如：文件共享、v o i p 、流媒体等等。 1 1 3 大规模对等资源共享面临的挑战 对等计算能够有效聚集网络边界资源，特别是大规模对等资源共享，具有c s 模式不可比拟的优势。当前，对等资源共享主要包括对等搜索和对等内容分发两 个关键技术，以对等搜索作为基础，解决定位资源的问题；以对等内容分发，解 决高效资源下载的问题。 经过多年的研究，对等搜索取得了显著的成果，分别提出了无结构对等搜索 网络、结构化对等搜索网络和混合搜索架构。结构化对等搜索网络对数据项的流 行度不敏感，能够以高概率达到1 0 0 的查全率。然而，结构化对等网络无法有 效支持复杂查询，并且受结点的动态性影响严重，因此不能够完全适用于解决大 规模对等共享问题。混合搜索架构结合了无结构搜网络和结构化搜索网络的优点， 但是也继承了其不足，同样不能有效支持复杂查询匹配操作。无结构对等搜索网 络，如g n u t e l l a 及其变体，能够有效适应结点的动态性，并支持复杂的查询匹配， 如多关键词匹配、模糊匹配等，无结构对等网络能够有效解决流行数据项的搜索 问题，但无法有效解决稀有数据项的搜索问题。对等资源共享中，稀有数据项和 流行数据项均具有重要的地位，稀有数据项的共享同样影响用户的体验。因此， 支持复杂查询的稀有数据项搜索算法是大规模对等共享系统中需要解决却未能很 好解决的一个难题。 在内容分发方面，用户需要更快的下载速度，以降低下载时间，分块并行下 载成为对等内容分发的首选策略。由于b i t t o r r e n t 具有比其它同类下载软件更好 的下载性能，已成为最流行的大文件共享工具，也是大文件共享事实上的标准。 b i t t o r r e n t 在成功的同时也存在不足，实际系统的运行表明，依赖于w e b 获取 t o r r e n t 文件降低了系统的可用性，t o r r e n t 文件的过时导致结点无法找到t r a c k e r 结点，从而无法加入t o r r e n t 网络；另外，对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 4 第一章绪论 系统的动态行为，但对于b i t t o r r c n t 的变体却无法有效描述。相对于初始的 b i t t o r r c n t 协议，当前的研究己产生了更多的改动，特别是邻居结点分配算法，因 此迫切需要一种通用的协作式对等内容分发模型。b i t t o r r c n t 的随机邻居分配算法 导致了大量的跨i s p 连接，从而导致了大量的跨i s p 流量，既提高了i s p 的运营 成本又降低了网络的效率。由于b i t t o r r c n t 是应用层协议，无下层网络的连接结 构知识，因此优化b i t t o r r c n t 流量成为一个难题。 1 2主要研究内容 对等网络的最重要应用之一为资源共享，其中的关键技术为资源搜索和内容 分发，而资源搜索是资源共享的基础。本研究工作围绕基于对等网络的大规模资 源共享展开，研究了稀有数据项的对等搜索的问题和对等内容分发中的关键问题， 所研究内容的关系如图1 1 所示。 图1 - 1 论文工作的研究内容 主要研究内容包括如下： ( 1 ) 高效的稀有数据项搜索算法 大规模对等资源共享建立在有效的资源搜索算法之上，获得资源的来源之后， 才能够进行有效的内容分发。无结构对等网络能够支持复杂的查询操作，使之成 为构建大规模资源共享的有效基础。现有的搜索算法能够有效定位系统中的流行 5 电子科技大学博士学位论文 数据项，而对稀有数据项的搜索性能较低。本文研究无结构对等网络的拓扑结构， 根据其特点研究定向复制策略，提高无结构对等网络对稀有资源的搜索性能。 ( 2 ) 对等内容发的数学建模 有效的模型有助于设计优化的算法和分析系统的性能，基于流模型的 b i t t o r r e n t 协议模型是一个比较完备的数学模型，但是该模型过于复杂。最近提出 的基于随机微分方程的b i t t o r r c n t 协议建模将非种子结点划分为两类，提高了模 型的复杂性，与实际系统不一致；在其分析中，认为结点到达率为常量，不符合 实际的系统行为；并且其评估方法是与模拟结果对比，不能验证模型的准确性。 已有的模型基本是针对当前的b i t t o r r e n t 协议，不能够适应协议的变化，不具有 通用性。p 2 p 协作式文件分发协议不断发展，协议的各部分会不断优化，特别是 邻居选择算法的不断改进，表明建立一个通用的、实用的数学模型是十分必要的。 因此，本文研究协作式对等内容分发的通用数学模型，提供简洁、准确的数学分 析途径。 ( 3 ) 对等内容分发的体系结构 b i t t o r r e n t 协议虽然简单、高效，但是其架构存在内在的不足。首先，b i t t o r r c n t 运行中需要采用w e b 方式发布t o r r e n t 文件，导致t o r r e n t 文件的有效性问题。 其次，b i t t o r r e ：n t 需要一个专用的t r a c k e r 分配邻居，t r a c k e r 结点需要成本投入且 是整个系统的薄弱环节。因此，需要研究对等内容分发的体系结构，解决现有系 统存在的不足，提出有效发现t o r r e n t 文件和可扩展的邻居分配策略。 ( 4 ) 对等内容分发中的流量优化问题 b i t t o r r e n t 是大规模内容分发事实上的标准，然而b i t t o r r e n t 协议不考虑下层 网络的连接结构，而且传输的内容来自于动态的用户结点，因此给互联网流量工 程带来严重的挑战。b i t t o r r e n t 是一个应用层协议，采用随机分配的方式从t r a c k e r 获取邻居结点，结点之间建立直接的逻辑连接，而不考虑下层对应的物理连接是 否跨越了多个i s p 。b i t t o r r e n t 的这种联网方式带来大量的冗余跨i s p 流量，这些 流量既降低了网络的性能，同时增加了i s p 的运营成本。i s p 通常采用流量控制 设备来应对这个问题，对p 2 p 流量进行限流、封堵等，这些措施无法从根本上解 决上述流量问题。本文研究对等内容分发中的流量优化问题，在不增加资源下载 时间的条件下，降低跨i s p 流量。 6 第一章绪论 1 3主要创新点及取得成果 本文围绕大规模对等资源共享展开研究，集中研究了其中的关键问题，即： 高效的资源搜索和高效的内容分发问题。首先研究了资源共享的基础资源搜 索问题，然后对对等内容分发中的数学模型、体系结构和流量优化等分别展开研 究。主要的创新性理论和方法如下： ( 1 ) 提出一种新的数据项复制与搜索策略d r s 根据无结构对等网络中结点度的幂律分布特征，首先通过数学分析证明幂律 随机图中的带偏随机游走能够快速命中网络中的高度结点，并采用模拟的方式验 证了这种特征；然后，基于上述特征设计了基于带偏随机游走的复制与搜索策略 d r s ，将数据项定向复制到网络中小部分高度结点，资源搜索采用相同的方式进 行。分析和模拟结果表明，所提出的资源搜索算法能够以低消息开销和低延迟获 得高的搜索成功率。d r s 特别适用于对稀有数据项的搜索，能够提高对等资源共 享系统的性能。 ( 2 ) 提出一种基于随机微分方程的通用p 2 p 文件分发模型 根据实际系统分类结点，分别对各类结点进行量化分析，建立基于随机微分 方程的系统动态模型。所建模型抽象邻居选择策略和结点到达率，能够支持各种 邻居选择算法和不同的结点到达率，基于所建模型分析了现有的邻居选择策略和 结点到达率。通过与实际系统的跟踪数据进行对比，所提出的模型能够准确描述 现有的p 2 p 协作式文件共享系统，是一种通用、实用的模型。该模型有助于评估 现有的方案，设计优化的系统。 ( 3 ) 提出了基于g n u t e l l a 网络的无t r a c k e r 对等协作式文件共享系统 p 2 p 文件共享是重要的互联网应用之一，其中b i t t o r r e n t 是最有效的p 2 p 协 作式文件分发协议，同时也是此类系统事实上的标准。然而，现有的b i t t o r r e n t 协议采用网页的形式发布t o r r e n t 文件，且需要专用的t r a c k e r 结点提供邻居分配 服务，这种架构存在多种不足，阻碍了b i t t o r r e n t 协议的应用。g n u t e l l a b t 利用 g n u t e l l a 网络的搜索功能实现t o r r e n t 文件的查询，使得p 2 p 文件共享系统可以脱 离w w w 而运行；通过在特定t o r r e n t 网络上的随机游走来实现邻居分配功能。 7 电子科技大学博士学位论文 设计了一种两层架构来实现上述功能，通过模拟实验表明，g n u t e l l a b t 能够在脱 离w w w 和t r a c k e r 结点的条件下有效运行。 ( 4 ) 提出了i s p 感知的b i t t o r r e n t 流量优化方案s t r a c k e r 对等内容分发系统，特别是b i t t o r r e n t ，造成了大量的跨i s p 流量，既增加了 i s p 的运营成本又降低了网络的效率。为了优化b i t t o r r e n t 的流量，本文提出 s t r a c k e r 方案。s t r a c k e r 由不同i s p 中的t r a c k e r 代理构成，这些t r a c k e r 代理之 间以p 2 p 方式连接，完成结点维护和i s p 感知的邻居分配。设计了相应的结点维 护算法和邻居分配算法。分析和模拟结果表明，s t r a c k e r 能够在不增加内容下载 时间的条件下，大量降低跨i s p 流量。s t r a c k e r 能够有效降低i s p 的运营成本， 提高互联网的效率。s t r a c k e r 的提出能够有效解决i s p 所面临的流量问题。 论文研究工作由国家自然科学基金( n o 6 0 4 7 3 0 9 0 和n o 6 0 8 7 3 0 7 5 ) 资助， 上述研究成果均已应用到项目中且获得好的效果。 1 4后续章节安排 论文后续部分的安排如下： 第二章综述大规模对等资源共享研究中与本文研