硕士论文-P2P环境内容分布服务算法研究.pdf

Y 9 8 8 9 6 3 P 2 P 境自窖 布 啦 算 究 分类号 U D C 密级 硕士学位论文 P 2 P 环境内容分布服务算法研究 论文答辩日期 吴限 指导教师菱堡宜教握 答辩委员会主席 论文评阅人一 学位授予日期 P 2 P 环境内容分布服务算法研究 P 2 P 环境内容分布服务算法研究 摘要 内容分布服务就是将相同的文件数据分发到网络中的多个节点 它 一直以来都是互联网研究的一个重要课题 其最关心的问题在于如何提高 网络带宽资源的利用率 随着互联网的迅猛发展 迅速增长的用户群使得 传统C S 结构不堪重负 同时传统的I P 多播未能大规模的普及应用导致人 们寻找在应用层的P 2 P 模式下实现内容分布服务的方法 本文主要做了以下方面的工作 一 将P 2 P 环境分为非合作式与合作式两类 并且对P 2 P 环境下的 内容分布服务算法的研究近况进行了综述 然后将这些算法分为结构化以 及非结构化算法 编码以及非编码算法四大类并分别加以讨论 二 针对非合作P 2 P 环境传统结构化算法中单棵树结构不能利用叶 子节点上传带宽的问题 提出了一种渐增式构建多树结构的算法一u 树组 产生算法 以求在多项式时间复杂度内对带宽资源的利用进行优化 最后 我们对该算法进行模拟实验 观察算法在I N E T 产生的I n t e m e t 拓扑下的表 现 并且将其与传统的树结构化算法进行吞吐量的对比 三 针对合作P 2 P 环境非结构化编码算法A v a l a n c h e 存在的解码计算 量大的问题 提出了一种粒度化的网络编码算法一G N C 算法 以求在尽量 不影响原A v a l a n c h e 网络编码算法的传输效率的情况下 减少编 解码的计 算规模 使得解码时间能够更平衡的分配 同时算法还带来安全性以及传 I I I P 2 P 环境内名1 分布月 务算法研究 输灵活性的提高 最后 我们利用P e e r s i m 的P 2 P 模拟环境对G N C 算法的 性能进行了实验 并且将其与原A v a l a n c h e 的网络编码算法进行了对比 最 后给出了实验结果的评价以及讨论 关键词 内容分布P e e r t o P e e r 网络编码A v a l a n c h e 广西大掌司仕掌位论文 P 2 P 环境内容分布月t 舟算法研究 o NA L G O R I T H M SO FC o N T E N TD I S T R I B U T I o NS E R V I C E I NP 2 PE N V I R o M E N T A B S T R A C T C o n t e n td i s t r i b u t i o ns e r v i c e Sg o a li st od i s t r i b u t et h es a m ef i l et o m u l t i p l eu s e r si nt h en e t w o r k w h i c hh a sa l w a y sb e e nt h ek e ys u b j e c to f I n t e r n e ts t u d y a n dt h em a i np r o b l e mo fi ti sh o wt oa c h i e v et h em a x i m u m u s a g eo fn e t w o r kb a n d w i d t h A st h eI n t e r n e ti sd e v e l o p i n gr a p i d l y t h e g r o w i n gn u m b e ro fu s e r so v e r w h e l m e dt h et r a d i t i o n a lC Sa r c h i t e c t u r e w h i l et h eI PM u l t i c a s tc o u l dn o tb er e a d i l yi m p l e m e n t e di nt h ew i d ea r e a n e t w o r k w h i c hf o r c e dp e o p l e t os e a r c hb e t t e rs o l u t i o n s o fc o n t e n t d i s t r i b u t i o ni nt h eP 2 Pe n v i r o n m e n to f a p p l i c a t i o nl a y e r T h i st h e s i sh a st h ef o l l o w i n gc o n t r i b u t i o n s 1 W ec l a s s i f i e dt h eP 2 Pe n v i r o n m e n ti n t ot w os c e n a r i o s w h i c ha r e c o o p e r a t i v ea n di n c o o p e r a t i v e s u m m a r i z e dt h er e c e n tr e l a t e dw o r k si nt h e f i e l do fc o n t e n td i s t r i b u t i o ni nt h eP 2 Pe n v i r o n m e n ta n dd i v i d e dt h e i r a l g o r i t h m si n t os t r u c t u r e do ru n s t r u c t u r e da n de n c o d e do rn o n e n c o d e d f o u rg r o u p s F i n a l l yw ed i s c u s sa l lk i n d so ft y p i c a la l g o r i t h m si nd e t a i l 2 f o r s i n g l e m u l t i c a s tt r e ec o n s t r u c t i o no ft h e t y p i c a l s t r u c t u r e d a l g o r i t h mc a n tf u l l yu t i l i z e t h e u p l o a d b a n d w i d t ho fl e a f n o d e s w e p r o p o s e dag r a d u a lw a yo fc o n s t r u c tm u i t i c a s tt r e e s Ut r e ep a c k i n g a l g o r i t h m O u ro b j e c ti s t oo p t i m i z et h eb a n d w i d t hu s a g ei np o l y n o m i a l t i m e F i n a l l y w em a d es o m es i m u l a t i o ne x p e r i m e n t t oo b s e r v et h e p e r f o r m a n c eu n d e r t h eI n t e r n e tt o p o l o g yg e n e r a t e db yI N E Ta n dc o m p a r e d t h et h r o u g h p u to fUt r e ep a c k i n gw i t ht h et r a d i t i o n a lt r e e b u i l ts t r u c t u r e d a l g o r i t h m s V 广西大掌硕士掌位论文 P 2 P 环境内容分布服务算法研究 3 A sf o rt h er e c e n t l y p r o p o s e du n s t r u c t u r e d e n c o d e dc o n t e n t d i s t r i b u t i o na l g o r i t h m A v a l a n c h ei sw e l la d a p t e dt ot h ec o o p e r a t i v eP 2 P e n v i r o n m e n t t h ed e c o d i n gp r o c e s si ss t i l l v e r yc o s t l y T h e r e f o r e w e p r o p o s e d a g r a n u l a rn e t w o r kc o d i n ga l g o r i t h m G N C w h i c ha i ma t r e d u c i n gt h ed i m e n s i o no fe n c o d i n ga n dd e c o d i n gw i t h o u tt r a d i n go f ft o o m u c he f f i c i e n c yo fd a t at r a n s f e ri nA v a l a n c h e W h a t Sm o r e G N C b r i n g s b a l a n c e dd e c o d i n gt i m ea n dm a k et r a n s f e rs a f e r m o r e f l e x i b l e F i n a l l y w es i m u l a t e dG N Ca l g o r i t h mi nP e e r s i ma n dm a d es o m ec o m p a r i s o n sw i t h A v a l a n e h e K E YW O R D S C o n t e n tD i s t r i b u t i o n P e e r t o P e e r N e t w o r kC o d i n g A v a l a n c h e f 西大掌司E 士掌位论文 P 2 P 环境内容分布服务算法研究 I I 课题的研究背景 第一章绪论 2 0 0 2 年底 全球有大约5 亿I n t e m e t 用户 而2 0 0 5 年底 这个数字将超过7 6 5 亿 I n t e m e t 用户以每6 个月翻一番的速度前进 它的发展早已打破了I T 行业著名的以1 8 个月为周期的 摩尔定律 1 1J 与此同时 在这个庞大的网络之中任何一个用户所拥有 的C P U 计算能力都比上个世纪九十年代早期的超级计算机要强1 0 0 倍 2 1 以至于根掘 G a r t n e rG r o u p 的研究报告 超过9 5 的今天的P C 计算能力被浪费了 这一点可以从 S L m h o m d 习项目得到验证 这个项目利用分布在I n t e m e t 的空闲计算资源来寻找外星 人 已经使用了超过百万年的C P U 时间 另一个例子是B T B i t T o r r e n t 的成功 它成 功的完成了1 7 7 G BL i n u xR e d h a t9 的发布工作 甚至软件巨头微软的X PS P 2 都采用B T 进行分发 因为微软自己的下载能力也只能支持到一天两百五十万份的下载量 正因为以上的大背景 才使得今天的P 2 P 能够大行其道 因为它能够利用上述网络 中的闲散资源 随着文件交换共享服务以及流媒体服务应用的兴起 对内容分布C o n t e n t D i s t r i b u t i o n 即数据分发D a t a D i s s e m i n a t i o n 的服务的需求越来越高 与此同时 面对 数百万之众的用户 传统的C S 架构已经不堪重负 人们越来越倾向于把这些服务转向 P 2 P 模式 当前I n t o r n e t 网络中的相当大部分流量正是由这些P 2 P 文件分发服务带来的 然而 面对这些大规模的P 2 P 数据分发应用 其中许多问题的研究尚不成熟 我们依然 有许多的问题需要解决 一 1 2 内容分布问题简介 简单来说 内容分靠 C o n t e n tD i s t r i b u t i o n 问题就是将一组相同的数据分发到网络 的多个客户机 C l i e n t 或者R e c e i v e r 如何更快的将数据分发到目标主机是一个主要的 问题 所以内容分布的服务质量通常存在如下主要目标 1 网络带宽资源利用效率 2 延时 3 可扩展性以及鲁棒性 4 可靠性以及安全性 其中提高带宽资源利用是一个 首要的目标 提高网络资源的利用率就能够提高整个网络的吞吐量 从而减少网络中用 户完成下载的时间 也就是说 相对流媒体等视频广播服务而言 以文件数据分发为代 表的内容分布算法对延时并不敏感 更需要高效的利用网络带宽 所以内容分布服务 在某些情况下 为了提高网络的端到端吞吐量 E n dt oE n dT h r o u g h p u t 可以牺牲一些 延时 典型的内容分布模式是多播 同时将同样的数据分发给多个节点 适用于那些在 时间上具有集中性 而在空间上只有分和性的应用 它最早的应用丌始于I P 多播 网 络最初主要是单点对单点的通信 随着应用的扩展 将同样的敛掘分发给多个网络节点 的需求开始出现 然而显然的是 采用多个单播 一对一 来实现内容分布不是高效的 方法 它造成了不必要的流量而且不具有可扩展性 基于对信息流的认识发现信息不但 可以像物品流一样转发而且可以在需要的时候复制多份拷贝 这样导致了多播 4 的 一 对多 出现 工作在网络层 基于I n t e m e t 体系结构的口多播 又称为组播 曾经是研 究方向1 5 6 它通过中间节点即路由器的对信息的复制可以使全网范围的分组复制数量 达到最少 从而使得带宽占用降低 是实现多播转发的最有效的方式 然而 口多播 气t 嚯 广西大掌硕士掌位 蹬文 P 2 P 环境内容分布服务算法研究 存在以下问题1 7 1 1 路由器必须为每个多播组保存状态 扩展性差 2 要求所有路 t h 器都支持 不利于推广使用 3 用统一的模型来适应所有应用 算法设计困难 4 多播组加入 退出和管理等开销大 5 多播地址空间太小 针对I P v 4 6 打破了 传统的根掘进入流量计费的机制 7 I P 多播在安全 拥塞控制等方面也存在问题 所以妒多播技术并没有得到广泛的应用 由于上述的诸多难以克服的困难 人们便试图在应用层实现多播 9 1 0 1 1 1 功能 也 就是在I n t e m e t 的端节点 T e r m i n a l 或者N o d e 中实现 而不是在路由器中实现 关于 这方面的研究有一个专有的名称 叫做 应用层多播 A L M A p p l i e a t i o nL a y e r M u l t i c a s t 应用层多播的思想是分组在端节点处进行复制 这样端节点在逻辑上构成覆 盖网络O v e r l a yN e t w o r k 由于在网络层仍然是使用单播 应用层组播的效率要低于P 组播 而且延时较大 但是易于实现 自此 内容分布的研究开始转到应用层 通过在 应用层中用算法构筑某种多播结构 组成自己的内容分布系统 与此同时 用户数量的迅猛增长以及分发内容的增加也使得传统的客户机朋殴务器 C l i e n t S e w e r 模式显得力不从心 因为这种模式不具备良好的可扩展性 所以跟不 上用户群的增长 这样的结果导致服务提供者在服务器端不断的投资 使C S 结构不断 扩展 如内容分发网络C D N C o n t e n tD e l i v e r yN e t 的A k a m a i l l 2 l 在全球拥有数万个服 务器以支持它的全球内容分布服务 然而多数服务提供者没有这种能力 所以得想其他 的办法 而P 2 P 模式正好可以解决这个问题 不断增长的I n t e m e t 用户以及端系统 T e r m i n a l 的处理能力使得P 2 P 模式开始流行 因为P 2 P 的合作性 自组织性以及自 治性使得它自身具有高度可扩展性 从O n e F o r A n 到A l l F o r A l l 的转变使得当新的用户 加入时 P 2 P 网络的带宽能力将会随之增加 因为新的节点也可以为其他的节点服务 整个系统的服务能力随着系统的需求不断增加 体现出高度的可扩展性 所以人们开始 探索在P 2 P 环境下实现内容分布服务 然而 合作环境 C o o p e r a t i v eE n v i r o n m e n t 下的P 2 P 模式具有原来P 多播网络不 具有的特性 带来了前所未有的挑战 如构建于I n t e m e t 之上的应用层使得应用程序无 法确知底层网络U n d e r l y i n g N e t w o r k 的具体结构 节点数目巨大无法获知网络全局信息 各个节点自治相互独立造成需要提供相应的动机因素以提高节点间的合作度 同样由于 自治问题导致节点动态的频繁的加入或者退出 由于文件或者数据长度较大分块 B l o c k 并行传输后需要解决数据块在节点间传输的时序 S c h e d u l i n g 问题 即什么 时候 向那个节点 传输哪一块数据 等等 综上所述 P 2 P 环境以及覆盖网络O v e r l a yN e t w o r k 技术 因为内容分发服务位于 应用层 是目前网络内容分布研究的两大特点 巨大的应用需求 导致了人们不断投入 了大量的资源对内容分布问题进行研究 不论在网络信息流的理论基础研究方面 还是 在实际的应用可行性方面 所以 本文对网络内容分布的研究具有重大的现实意义 1 3 相关的研究进展 在内容分布的效率方面 为了提高带宽资源的利用效率 将需要传输的数据分块并 行传输被证明是有益的 l 然而这就使得如何确定数据块传输的时序 S c h e d u l i n g 以 及路由 R o u t i n g 变成一个主要面对的问题 任何一个O v e r l a y 内容分布系统都需要解 决这个问题 本文的研究目标就是尝试通过对该问题已有的解决办法的改进 达到提高 内容分布系统带宽利用效率的目的 下面对当前相关的研究进展进行总结 正如文章 lo 所强调的 应用层多播的优势都来自于两个基本的属性 2 广西大掌硕士掌位论文 P 2 P 环境内容分布服务算法研究 1 O v e r l a y 网络的拓扑结构可以随着需要变化 因为其底层是h l t e m e I 一 个连 接稠密的口网络层 在上层看来就是一个全连接图 2 O v e r l a y 网络中的节点不同于底层网络节点 它们是终端系统且有远远超出网络 交换设备的能力 而路由器 交换机等网络交换设备只能对数据进行存储转发 所以按照第一个属性 即是否维持并使用某种特定的拓扑结构进行传输的作为标准 可以将现有的内容分都算 去分为结构化与非结构化两类 根据第二个属性 即是否利用 网络 包括在源端或者所有节点编码 对传输的数据进行编码又可以将算法分为编码与 非编码两类 这两类算法是相容的 可以交叉使用 1 结构化算法 将O v e r l a y 网络构建成单棵多播树S i n g l eM u l t i c a s tT r e e 简称树 多棵多播树M u l t i p l eM u l t i c a s tT r e e 简称多树 或者是网 M e s h 等结构进行 传输的算法 a 1 树结构 最初 应用层中典型内容分布算法是以覆盖网络上的端系统 E n d S y s t e m 为节点构建的多播树算法1 1 4J I J 先将文件数掘分成若干小块 然 后利用一棵全局多播树进行分发 比如O v e r c a s t t 4 8 以及N a r a d a l 4 9 1 b 多树或者网结构 虽然单棵多播树的维护比较简单 但是这种构建方法不 能较好的利用网络带宽 所以人们开始考虑使用多棵多播树或者网M e s h 的架构 比如S p l i tS t r e a m E 4 B u l l e t I J C o o p N e t t 等 基于树 T r e e 的传输架构能够创建非常适合流式内容数据的分布系统 因 为这一类系统的实时性较强 而最短路径树 S h o r t e s t P a t h T r e e 可以提供延时 的优化性能 但是在文件传输为代表的内容分布情况下 对带宽利用的优化要 比对延时的优化更为重要 而树的结构造成节点带宽限制于从根到该节点路径 的瓶颈带宽 叶子节点无法贡献上传的带宽资源等等问题 对带宽的利用率不 是最高的 所以基于树的架构未必总是最好的方法 5 2 l 相比而言 网M e s h 的 结构就比较好发掘平行节点直接连接的带宽资源 此外 对全局结构的维护必 然会削弱系统的可扩展性 不利于大规模数据分发应用 2 非结构化算法 这种算法并不特地维持某种结构 很多采用随机连接的方法进 行传输 这种算法以B i t T o r r e n t t 等文件共享的P 2 P 应用为代表 在目前互联 网的内容分布应用上非常流行 他们能够使用额外的连接较好的利用节点带宽 同时从多个节点进行数据传输 它的缺点也显而易见 由于没有固定的传输结 构 所以不能事先确定内容分发的路径 相反在节点面前有许多路径可以选择 然而如果它们根据局部信息进行传输则可能导致相同数据块在多个相互竞争的 路径上同时传输 但是如果使用全局信息必然失去可扩展性 所以这之中需要 考虑某种特殊方法来进行平衡 3 编码算法 编码算法就是在数据分发的过程中将数据块进行编码 解码操作以 提高数掘分发网络的性能 根据进行编码的操作的节点位置可以分为服务器端 编码以及网络编码两种9 a 1 服务器端编码 S o u r c eC o d i n g 又称为擦除码E r a s u r eC o d e 或者前向纠错 码F E C F o r w a r dE r r o rC o r r e c u o n 一般只在服务器端编码 最仞的F E C 前向纠错码如R e c d S o l o m o n 等 必须要提供删除几率 E r a s u r eP r o b a b i l i t y 所以后来发展出无几率删除码 R a t e l e s sE r a s u r eC o d e 如L T t 1 R a p t o r t 5 7 J 等 其目的本是使用冗余的码字来提供无须回传信道的纠错能力 提高传 输速率以及可靠性 但是由于节点仍然可能收到重叠的编码后的数据块 算法必须在节点间加入某种机制使得传输的更加有效 后来B y e r s 等人 Z Z l 提出一种编码调和技术减少节点间数据的冗余度 便在节点之间随机传输 3 广西大掌硕士掌位论文 P 2 P 环境内容分布服务算法研究 数据块而提高吞吐量的方法 服务器编码典型的应用如D i g i t a lF o u n t a i n 5 3 1 b 网络编码 N e t w o r kC o d i n g 网络编码理论 2 0 3 4 是这些年提出的一种编码 的新方法 它的提出本是为了提高网络的理论吞吐量 然而对它的研究尚 不透彻 发现在实际应用中提高吞吐量的效果并不明显 1 8 3 2 然而 后来 的研究发现网络编码可以使得内容分布算法的数据转发时序确定变得容 易 而且带来了系统健壮性的提高i 5 在这方面目曲大多是对其理论研究 的文章 只有少数的应用 I o 5 2 垆 典型的算法如结构化的N e t w o r kC o d i n g 树 1 0 1 非结构化的A v a l a n c h e J 4 非编码算法 这是传统的做法 它对数据块不作任何修改 直接在网络中传输 原始数据块 优点是算法简单 缺点是没有差错控制 需要靠良好的结构或者 转发时序来进行有效的利用带宽 B i f r o r r e m 就是非编码的算法 相对面言 数 据编码对非结构化的算法来说显得更为重要 因为结构化的算法可以通过已有 的结构进行传输 而无须路由 非结构化的算法就可以通过编码减少节点l 日J 数 据的冗余 提高带宽利用 正如本节开头提出的如何确定数据块传输的时序 S c h e d u l i n g 以及路由 R o u t i n g 的问题是内容分布需要解决的基本问题 所以人们提出以上不同的架构以及算法来解 决 由于网络应用的多样性 没有任何一种内容分布算法或者架构能够适应所有的应用 需求 使用不同机制来支持不同应用 的思想是互联网下一步的发展方向 所以不同 的架构以及在其上的算法还将继续并存 1 4 本文的主要工作 综上所述 面对各种算法的优点以及不足 本文将进行以下工作 1 首先 我们对前人的工作进行了总结 对现存的内容分布算法进行综述 2 对于结构化的算法 我们发现树T r e e 结构在带宽利用方面固有的不足 所以我 们在构建多棵多播树的基础上 开发出一种渐增式的流分配算法 首先 其底 层构建如N a r a d a 类似 构建为一个网M e s h 的形式 然后在其上执行U 树组产 生算法来最大化利用带宽资源 最后对其进行分析以及实验来证明其结果的有 效性 3 对于非结构化的算法 我们在A v a l a n c h e 的基础上 将网络编码N e t w o r kC o d i n g 的使用方法进行改进 以其使用流合并达到直接提高吞吐量的目的 值得注意的是 网络最大吞吐量 O p t i m a lT h r o u g h p u t 理论的研究成果 也能为我 们的工作提供指导性的建议 如可以考虑将S t e i n e rT r e eP a c k i n g 算法作为我们的算法 一种评价方式 将N e t w o r kC o d i n g 利用到算法中来探索流合并对吞吐量提高的可行性等 等 使得理论研究与应用研究能够相互促进 1 5 论文的组织 下面对我们本文的其余部分的内容进行介绍 第二章 P 2 P 环境下的内容分布服务综述 首先对支持目前网络内容分布服务的两 个重要的支持技术 P 2 P O v e r l a yN e t w o r k 进行介绍并且讨论它们之间的联系 然后 将内容分布主要的算法的理论基础如S t e i n e r T r e e N e t w o r k C o d i n g 进行简单介绍以及对 比 对典型的内容分布算法进行分类总结 最后探讨一下网络内容分布算法的评价方法 4 广西大掌硕士掌位论文 P 2 P 环境内容分布服务算法研究 以及今后的发展方向 第三章 P 2 P 环境下的一种非结构化算法一u 树组产生算法 我们在集中式P 2 P 环 境下 提出一种对P 2 P 进行渐增式流分配路由的结构化算法 即U 树组 U n i t T r e e P a c k i n g 的生成算法 同时对算法进行试验分析 对结果进行评估 算法都在多项式时 间内完成 精确度以及计算量可以根据实际情况进行调整 第四章 合作式P 2 P 环境下的非结构化算珐 对于大规模的内容分却算法一般使用 非结构化的算法 因为非结构化的算法可以具有最好的可扩展性 比如大名鼎鼎的 B i t T o r r e n t 最近对网络编码N e t w o r kC o d i n g 的研究成果使得非结构化的算法设计更加 高效 将传统的非结构化算法与N e t w o r kc o d i n 窖理论进行结合的一个应用的例子是微软 研究室的A v a l a n c h e 它能够几乎无冲突的在节点间交换数据 但是同时它带来了相当 的计算量以及安全婀题 我们对A v a l a n c h e 进行改进 并提出一种将传统的N C 进行粒 度化的传输编码算法 G N C G r a n u l a rN e t w o r kC o d i n g 编码传输方法 这同样是完全 的分布式算法 在原来的传输效率基本不受影响的情况下 使其能够在计算量以及安全 性上有所提高 我们在P e e r s i m l 0 1 环境下对G N C 进行测试 实验结果达到预期的效 果 第五章 对本文的总结以及对未来研究的一些展望 广西大掌硕士掌位论文 P 2 P 环境内萼L 分布服务算法研究 第二章P 2 P 环境下的内容分布服务综述 2 1 内容分布服务的两个关键支持技术 当f i 的内容分布算法有两个基奉的特点 一个是合作性 一个是位于应用层 这两 个特点都有相应的背景技术支持 一个是P 2 P 网络技术 另 个是O v e r l a y 技术 其中 P 2 P 网络有不同的架构 而不同的架构有不同的自治性以及合作性 这样在不同的架构 条件下就需要有不同的内容分布算法 所以我们需要对P 2 P 的结构有所了解 而O v e r l a y 技术支持算法工作在应用层 它有自己的一些特点以及评价方法 下面对这两种技术做 简单的介绍 2 1 1P 2 P P e e rt oP e e r 网络技术简介 P 2 P 定义尚未完全统一 本文使用如下定义 P 2 P P e e r t oP e e r 是一类应用程序 它们共享分布在因特网边缘节点上的资源 比如存储空间 C P U 时钟 内容信息等等 4 I 简单的说 P 2 P 就是 个位于应用层的特殊的异步并行分布式存储系统 系统之中任一 对节点可以通过P 2 P 路由协议进行通信 2 1 1 1P 2 P 网络结构分类 蚰1 1 1 纯P 2 P 结构 一个纯粹的P 2 P 应用程序没有任何形式的中心服务器 如图2 一l 它动态发现其它的P e e r 然后与他们交换内容 这种模型的好处是它不依靠服 务器来发现其他P e e r 但是同时它的D i s c o v e r 能力是有限的 所以限制了应用 程序的能力 这种场合下 P e e r 之间通过局部路由协议 路由表 或者通过广 播或多播来发现对方 使用这种模型的P 2 P 实例有G n u t e l l a 图2 1 纯P 2 P 结构示例 删 F i g u r e2 1P u r eP 2 PE x a m p l e i l 混合P 2 P 结构 这种结构需要部分的依赖于服务器的功能 根据对服务器功能 依赖的不同可以进一步分为以下三类 a 简单P e e r 目录服务器的P 2 P 模型 如图2 2 架构 它与纯P 2 P 架构的区别 在于它有一个中心服务器用来保存在线的p e e r 目录列表 在这个模型中 6 广西大掌硕士掌位论文 P 2 P 环境内容分布服务算法研究 P e e r 在启动时需要通知中心服务器 然后下载目前在线的P e e r 列表 通过 其中的地址P e e r 可以直接与它们联系 在很多场合下 这种模型的可扩展 性比纯P 2 P 方式要好 它只需较小的代价 一台中心服务器 不大的带宽 开销 就可以实现P e e r 之间的联络 但同时中心服务器如果失效 P e e r 之 间将无法发现对方 目前的e D o n k e y e M u l e 都是利用了这种模型 图2 2 混合P 2 P 结构 目录或者内容查找服务器 5 0 l F i g u r e2 2P 2 Pw i t haS i m p l eD i s c o v e r yS e r v e 删l b 1P e e r 目录与内容查找服务器P 2 P 结构 与上一种结构类似 服务器扩展了 共享资源内容查找的服务 在这种情况下 P e e r 不但在S e r v e r 上注册自己 而且还周期性上传自己所拥有的资源的信息 当某个P e e r 要查找某个特定 的资源 它可以向服务器发请求 而不是向所有的其它P e e r 发请求 这个 模型在某些场合更加高效 因为它减少了网络中Q u e r y 的数量 然而它也 增加了S e r v e r 的开销 目前流行的B i t T o r r e n t 利用了这种模型 c 1P e e r 目录 内容查找与存储服务器P 2 P 结构 这种结构在前一种结构的基 础上又更进了一步 服务器可以接受P e e r 的上传的内容 如图2 3 这样 的话 模型实际上就是经典的C S 模型 因为P e e r 不再与其它P e e r 交换信 息了 这样 S e r v e r 很快就成为了系统的瓶颈 广西大掌硕士掌位论文 P 2 P 环境内容分布服务算法研究 图2 3 混合P 2 P 结构 目录 内容查找以及 存储服务器 删 F i g u r e2 3P 2 Pw i t haD i s c o v e r y L o o k u p a n dC o n t e n ts e n 怕F 删 2 1 1 2 合作环境与非合作环境的P 2 P 网络 今天大多数的P 2 P 网络都是建立在这样的假设之上 所有参与的节点都是乐意且能 够协作的 一般P 2 P 的节点属于不同的自治系统 如果这些节点都对它们提供资源所付 出的代价不太关心或者不了解 那么协作的确是可行的 不过这样也限制了它的应用场 合 而在同一个自治系统的场合下 比如公司内部专用网或者移动通信网 是不一定需 要P 2 P 架构的 这里把P 2 P 环境下节点提供服务的动机模型分为两组m l 一种是弱动机模型 即在 网络中没有获取实际利益的动机表现 另一种是强动机模型 即节点某些服务的提供是 强制性的 其中 弱模型可分为三种 1 依靠用户自身 这是曾经应用最多的经典的模 型 如w w w 信息服务 搜索服务等 用户可以不需要提供服务而获得服务 2 纯慈 善 用户仅仅提供服务而并不享用服务 也并不获益 比如S E T I h o m e 3 共同利益 表现上与2 差不多 只是共享服务的结果会对参与者有直接的利益 强模型也可分为三 种 1 微货币 在各个节点之间建立了一种虚拟的货币机制 提供或消费服务都会用这 种货币进行交易 这种情况可能 斋要一个货币中心束管理 而实际上可行的话还要提出 一个经济模型 2 夕p 部结账 与其它动机模型不同 这种模型需要在外部结账 在当今 的网格之中非常流行 3 强制共享 用户如果要下载其它用户的文件就必须提供文件共 享 比如e D o n k e y 2 0 0 0 B i t T o r r e n t 上传与下载速率之比被限制 但并非线性关系 当 上传超过一定速率后 下载将不再受限 根据P 2 P 节点提供服务的动机强弱 l 我们将P 2 P 网络分为两类 合作与非合作 环境 非合作环境中的节点一般处于同一个自治系统之中 或者它们向用户提供付费服 8 r 西大掌硕士掌位论文 P 2 P 环境内容分布服务算法研究 务 如G r i d 或者移动通讯专用网 这种环境具有最强的动机 提供的服务质量也较高 合作环境中的节点往往处于不同的自治系统 为了使用网络中的服务 必须向其他节点 提供服务 现在多数P 2 P 应用属于这种情况 如B T e M u l e Q Q L i v e 等等 这种环境 的动机稍弱且受该P 2 P 网络既有服务的质量的影响 不同的环境中P 2 P 节点的参与和共享程度不同 关系到节点提供服务的质量 稳定 程度 是舀随时退出等等细节凼素 所以不同的P 2 P 吞吐量算法对环境有不同的要求 比如集中式算法比较适合在非合作环境中运行 分白式算法在两者中均可运行 但是更 加适合在合作环境下运行 2 1 2 覆盏网络 O v e r l a yN e t w o r k 技术 覆盖网络 O v e r l a yN e t w o r k 定义 2 5 为 覆盏网络是构建在一个或者多个已经存在 的网络之上的网络 它附加了 一个间接的虚拟的层次以改变下层网络一个或者多个属 性 从而实现原有网络无法提供的功能或者服务 比如现有的I n t e r n e t 就是一个覆盖网 络 它构建于众多局域网 N 电话网 P S T N 之上 目的就是通过统一的口协 议实现异构的局域网之间的相互通信 此外我们研究的P 2 P 也属于覆盖网络 它构建于 I n t e r n e t 之上 覆盖网络的实现方便 不需要对原有的设备或者协议做改变 下层网络节嘉可以随 时选择是否需要加入覆盖网络以使用其功能 当然 覆盖网络的实现也是有成笨的 如 增加网络协议栈的层数 信息冗余 增加复杂性等等 覆盖网络的评价标准 1 1 覆盖网络图的属性 如相邻节点的数量 路径长度 2 1 将覆盖网络映射到第3 层网络 即网络层 评价参数如伸展度S t r e t c h 覆盖 网络中两个节点延时与网络层中对应节点问最短路径延时的比值 重压度 S t r e s s 在同一条物理连接上传输相同数据的次数 如下图所示 有两处重压 度为2 从A 到B 的伸展度为1 5 6 4 图2 4 覆盖网络伸展度S t r e t c h 与重压度S t r e s s 示例闭 F i g u r e2 4E x a m p l eo fS t r e t c ha n dS t r e s so fO v e d a yN e 溆o r k 嘲 3 构建并且维持覆盖网络拓扑结构的协议的属性 9 e 西大掌硕士掌位论文 P 2 P 环境内客分布服务算法研究 2 2 内容分布算法的信息理论基础 以文件分发为代表的内容分布算法以提高带宽利用率为主要目标 所以寻找达到网 络最佳端到端吞吐量 O p t i m a lE n dt oE n dT h r o u g h p u t 的方法一直是人们在信息理论方 面追求的目标 信息网络是由一系列网络终端节点通过网络交换设备连接组成 它定义了各种寻 址 路由和服务模型 最一般的情形 节点与节点之间的通讯线路是双向双工 可同时 发送以及接收 的 物理线路的传输负载有相应的上限 并且两个方向的传输负载的上 限可以不对称 如现在广泛使用的A D S L 对某个节点 终端节点和网络交换设备节点 而言 也有数据处理能力的上限 鲡数据产生的能力以及数据接收的能力 终端节点相 应的是上传以及 卜载数掘速率的上限 不过就目前一般的情况而言 这个上限要高于传 输线路负载的上限 即高于网络的数据处理能力 网络交换设备节点相应的是数据吞吐 量的上限 同样取决于该设备的数据处理能力 因为网络自身的复杂性 理论研究一般将其经过简化后利用图论的知识来进行建 模 比如对以上的信息网络的定义进行建模 就可以得到一个无向图 图的吞吐量的限 制条件来自点 边的容量以及图的拓扑结构 由于目前终端节点的信息处理能力远大于 网络的信息传输能力 所以该图一般为边权网络而非点权网络 根据应用程序的不同 一个网络会话可以分为单播 u n i e a s t 多播 m u l t i c a s t 广播 b r o a d c a s t 以及组间通讯 G r o u pC o m m u n i c a t i o n 分别对应于一对一 一对多 一对全部以及多对多的数据传输 在一个或者多个这样的网络会话中如何计算并且达到 最大的端到端吞吐量 e n d t o e n dt h r o u g h p u t 是一个基本的问题 然而在信息网络中计算最佳吞吐量 O p t i m a l T h r o u g h p u t 并不容易 我们可以拿典 型应用一多播来举例 这个问题等价于S t e i n e rT r e eP a c k i n g 问题 l 它既是N P 完全问 题 又是A P X 难问题 不存在多项式时间的近似算法的问题 除非P N P 由此可见 最佳吞吐量问题的难度 更不用说其他更加复杂的会话情形 2 2 1 信息流理论研究简介 一直以来 人们都热衷于研究如何提高网络资源的利用率 达到网络最大的流量或 者吞吐量 比如图论中基本的可增流 最大流算法以及最大流最小割定理等 都是为了 研究现实中的一些典型的应用 如运输问题 调度问题等等 不过这些都是研究物品流 在物理网络中的行为表现 这些定理对于单播网络流也适用 因为单播中的中间节点只 是负责转发 这与物品流的性质类似 随着网络的进一步发展 对各种应用的要求提高 多播逐渐成为研究的热点 注意 到信息流可以在适当时候被复制这个特点 基于I n t e m e t 体系结构的I P 组播 多播 曾 经是研究方向 5 它通过中1 日J 节点即路由器的对信息的复制可以使全网范围的分组复 制数量达到最少 从而使得带宽占用降低 是实现组播分组转发的最有效的方式 然而 由于口组播存在种种限制 如很难实现可靠性组播和拥塞控制等 口组播技术并没育 得到广泛的应用 一 由于上述的诸多难以克服的困难 人们便试图在应用层实现组播 s g l O o I D q 功能 也 就是在I n t e r n e t 的端系统中实现 而不是在路由器中实现 应用层组播的思想是分组在 端系统处进行复制 这样端系统在逻辑上构成覆盖网络 在网络层仍然是使用单播 应 用层组播的效率要低于口组播 而且延时较大 但是易于实现 1 0 广西大掌司E 士掌位论文 P 2 P 环境内容分布服务算法研究 其后出现了大量的关于在应用层多播提高吞吐量算法的研究文彰2 1 2 2 2 3 3 5 1 但是 如何达到端到端理论最佳吞吐量的高效算法却较少被深入研究 虽然相似的问题却被广 泛研究讨论过 比如服务质量Q o S Q u a l i t yo fS e r v i c e 路由f 2 7 问题 O o s 的目标是寻 找到能够满足带宽或者延时等要求的端到端路径或者多播树 从而提供所需的Q o S 保 证 然而可以肯定的是 寻找达到理论最佳吞吐量的途径的难度明显高于找到一种满足 带宽要求的拓扑结构 2 8 1 一直以来 关于多播的理论最佳吞吐量问题都是基于图论的S t e i n e rT r e eP a c k i n g 问 题 1 计算也十分困难 直到2 0 0 0 年 网络编码的提出才使得我们向理论上限靠近了 一步 网络编码 2 0 1 1 3 0 1 基于这样一个事实 信息在信息网络中不但可以被复制而且还可以 被编码 且长度不变 以下将S t e i n e r T r e e P a c k i n g 司题以及N e t w o r k C o d i n g 问题的研究做简单介绍 2 2 2S t e i n e rT r e eP a c k i n g 问题 S t e i n e r T r e e P a