（计算机软件与理论专业论文）基于网络编码的p2p文件分发的研究.pdf

摘要 摘要 文件分发是一类将文件发送到大量的终端用户的应用的总称，包括了文件共 享、流媒体在线观看等一系列最为常见用的互联网应用。随着网络的发展，用户 的规模越来越大，对文件发布的性能要求也越来越高。p 2 p 技术利用了普通用户 的计算资源和上传带宽资源，可以提高文件分发的性能。网络编码烈e 咐o r k c o d i n g ) 是近几年通信科学一个新兴的研究领域。使用网络编码后，通信的中间 节点不再是直接转发数据包，而是将收到的一些包编码成一个新的包后进行转 发，目的节点进行解码得到原始数据。网络编码和p 2 p 技术结合，可以显著提 高文件分发的分发速度、鲁棒性、可扩展性等多方面的性能。 本文的主要研究内容和贡献有： 1 ) 本文提出了稀疏线性编码算法，并由c o o p e r 的关于稀疏矩阵的研究成果 推导出关于稀疏线性编码的编码成功率的定理。使用稀疏线性编码，可以降低网 络编码的编码复杂度，与原有的完全编码相比较，编码复杂度由o ( 以) 下降到了 o q o g ，1 ) ，其中n 是原始数据信息的数量。在对较大的文件进行分发时，稀疏编 码可以在保持高编码成功率的情况下，达到比完全编码算法高得多的编码速度。 实验中，以主流配置( i n t e lp e n t i u md 3 2 g h z ，1 g br a m ) 的个人计算机对1 2 8 m b 文件进行编码，在分块大小为2 5 6 k b 时，平均编码速度达到了7 m b s ，可以不 拖累网络传输。 2 ) 网络编码可以通过优化数据块调度的方式提高p 2 p 文件系统的性能。我 们将稀疏线性编码引入了p 2 p 文件分发系统，实现了一个使用稀疏线性编码的 系统( s n c ) 。基于相同框架，同时也实现了一个不使用编码的p 2 p 文件分发系统 ( l r f ) ，其中使用了局部稀缺优先算法进行数据块调度。我们在局域网平台上进 行了文件分发的对比实验。实验结果表明，在平均下载时间，总发布时间，整体 吞吐量几个方面，s n c 比l r f 性能更好。平均来说，使用稀疏编码减少了约 1 0 1 5 的下载时间。 3 ) 我们提出了预先检测机制，以避免无效( 线性相关) 的数据块被发送。基于 同样框架，我们实现了一个使用预先检测机制和稀疏线性编码的p 2 p 文件分发 系统( s m a r t c o d e ) ，以及用于对照的无编码系统( l r f ) 和未使用预先检测的编码系 统( e c o d e ) 。s m a r t c o d e 是第一个使用稀疏编码的广域网文件分发系统。在 p l a n e t l a b 上，我们进行了三种系统的广域网实验。实验结果表明，在平均下载 时间和鲁棒性方面，s m a r t c o d e 的表现优于其余两个系统。相比于e c o d e 系统和 摘要 l r f 系统，s m a r t c o d e 分别减少了平均7 和l l 的下载时间。在鲁棒性方面， s m a r t c o d e 的优势更大。在一些极端的情况下，l r f 没有节点能够完成下载，e c o d e 只有几个节点可以完成，而s m a r t c o d e 超过7 5 的节点都能完成下载。 关键词：网络编码p 2 p 文件发布稀疏线性编码预先检测 a b st r a c t f i l ed i s t r i b u t i o ni st od i s t r i b u t es o u r c ef i l e st oa l o to fe n du s e r s i ti si n v o l v e di n at y p eo fa p p l i c a t i o n s ，s u c ha s f i l e s h a r i n g ，l i v i n gs t r e a m i n g ，a n de t c a st h e d e v e l o p m e n to fi n t e m e ta n dt h eg r o w t ho ft h ea m o u n to fn e t w o r ku s e r s ，t h eq u a l i t y r e q u i r e m e n to ff i l ed i s t r i b u t i o nf r o mu s e r sa l s oi n c r e a s e s p 2 pm a k e su s eo f c o m p u t i n ga n du p l o a d i n gr e s o u r c e so fe n du s e r s ，a n di m p r o v e st h ep e r f o r m a n c eo f f i l ed i s t r i b u t i o n n e t w o r kc o d i n gi san e wr e s e a r c ha r e ai ni n f o r m a t i o nt h e o r y w i t h n e t w o r kc o d i n g ，i n t e r m e d i a t en o d e sb e t w e e ns o u r c ea n dd e s t i n a t i o n ( s ) e n c o d et h e i n c o m i n gp a c k e t si n t os o m en e wo n e st ot h eo u t g o i n gl i n k sw h i l et r a n s m i t t i n g ，a n d t h eo r i g i n a lc o n t e n ti sd e c o d e da tt h ed e s t i n a t i o n ( s ) w i t hp 2 pa n dn e t w o r kc o d i n g ， t h ep e r f o r m a n c eo ff i l ed i s t r i b u t i o ns y s t e m sc a nb ei m p r o v e d t h em a i nc o n t r i b u t i o n so f t h i st h e s i sa r e ： 1 ) w ep r o p o s eas p a r s el i n e a rc o d i n ga l g o r i t h m ，a n da n a l y z et h er a t eo fi t s s u c c e s s f u ld e c o d i n gb a s e do nc o o p e r sr e s u l t so ns p a r s em a t r i x e s w i t h s p a r s e c o d i n g ，t h ec o m p l e x i t yo fn e t w o r kc o d i n gc a nb eg r e a t l yr e d u c e df r o mo ( n ) t o o ( 1 0 9 力，w h e r eni st h eb l o c kn u m b e ro ft h ef i l et ob ee n c o d e d i ne x p e r i m e n t s t h e e n c o d i n gs p e e do fs p a r s ec o d i n gr e a c h e s7 m b s ，w h i c hi s h i g he n o u g ht oc a t c h u p l o a d i n gs p e e d ，a n dk e e p sah i g hr a t eo fs u c c e s s f u ld e c o d i n g 2 ) w ei m p l e m e n tap 2 pf i l ed i s t r i b u t i o ns y s t e mw i t hs p a r s el i n e a rc o d i n g ( s n c ) ， a n dw i t ht h es a m ea r c h i t e c t u r e ，w ea l s oi m p l e m e n ta s y s t e mw i t h o u tn e t w o r kc o d i n g 犯心，w h i c hu s e sl o c a l r a r e s t f i r s ts c h e m et os c h e d u l eb l o c k s e x p e f i m e n t a lr e s u l t s o nal a nt e s t b e ds h o wt h a ts n c i sb e r e rt h a nl r fi nt e r m so fa v e r a g ed o w n l o a d i n g t i m e ，t o t a ld i s t r i b u t i o nt i m ea n dt h ew h o l et h r o u g h p u t a v e r a g e l y , s p a r s ec o d i n g r e d u c e sa b o u t1 0 1 5 d o w n l o a d i n gt i m e 3 ) w ei n t r o d u c eap r e - c h e c k i n gm e c h a n i s mi no r d e rt oa v o i dl i n e a r l yd e p e n d e n t b l o c k sb e i n gt r a n s m i t t e d w i t ht h es a m ea r c h i t e c t u r e ，w e i m p l e m e n tap 2 pf i l e d i s t r i b u t i o ns y s t e mw i t hs p a r s ec o d i n ga n dp r e c h e c k i n g ( s m a r t c o d e ) ，as y s t e mw i t h s p a r s ec o d i n gb u tw i t h o u tp r e c h e c k i n g ( e c o a e a n das y s t e mw i t h o u tn e t w o r kc o d i n g ( l m 5 3 w ec a r r yo u tw i d e a r e an e t w o r ke x p e r i m e n t so np l a n e t l a b t h ee x p e r i m e n t a l r e s u l t ss h o wt h a ts m a r t c o d e p e r f o r m sb e t t e rt h a ne c o d ea n dl r fb o t hi nt h ea v e r a g e d o w n l o a d i n gt i m ea n dr o b u s t n e s s a v e r a g e l y , s m a r t c o d er e d u c e s7 d o w n l o a d i n g t l l t i m ec o m p a r e dw i t he c o d ea n di1 d o w n l o a d i n gt i m ec o m p a r e dw i t h 三尼fi ns o m e e x p e r i m e n t sa b o u tr o b u s t n e s su n d e rt h ea s s u m p t i o nt h a tt h ep e e r sc a nl e a v et h e s y s t e m ，n op e e rc o m p l e t e st h ed o w n l o a d i n gw i t hl r f , a n daf e wp e e r sc o m p l e t et h e d o w n l o a d i n gw i t he c o d e ，b u to v e r7 5 p e e r sc o m p l e t et h ed o w n l o a d i n gw i t h s m a r t c o d e k e y w o r d s ：n e t w o r kc o d i n g ，p 2 pf i l ed i s t r i b u t i o n ，s p a r s el i n e a rc o d i n g ，p r e c h e c k i n g i v 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均己在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：墨垄丝缢 犹年s 其1 日 该1 认肋 杪砷易 第l 章绪论 第1 章绪论 本章摘要： 随着网络规模的逐渐扩大，网络资源的日益丰富，使得网 络用户之间的资源共享和信息交流越来越普遍，网络文件分发 成为网络资源方便共享的重要途径。而随着计算机网络的发展 和用户数量的增长，传统的用户服务器( c li e n t s e r v e r ，简 写为c s ) 模式的文件下载和发布模式已经不足以满足用户在 文件下载和发布方面的需求。而对等网络( p e e r - t o - p e e r ，简 写为p 2 p ) 技术可以大幅度提高文件分发的速度和可扩展性。 网络编码( n e t w o r kc o d i n g ) 是近几年通信科学一个新兴 的研究领域。使用网络编码后，通信的中间节点不再是直接转 发数据包，而是将收到的一些包编码成一个新的包后进行转 发，目的节点进行解码得到原始数据，通过这样的方式，可以 增加网络传输的信息量，提高网络的吞吐率。最近的科研成果 表明网络编码可以显著提高p 2 p 文件发布系统的性能。 本章先分别介绍p 2 p 技术和网络编码的基本概念，然后简 要介绍了本文的研究内容和成果，最后介绍本文后续部分的组 织结构。 第1 章绪论 1 1 文件分发和p 2 p 技术简介 本节将简单介绍文件分发以及p 2 p 技术的概念和研究意义。 1 1 1 文件分发简介 文件分发( f i l ed i s t r i b u t i o n ) 指的是一类用网络将文件由一个( 或多个) 源发送 到多个终端用户的网络应用。现在互联网上的许多应用，如：病毒数据库升级服 务、文件共享、流媒体在线观看等等都可以看成是文件分发中的一种。本文的研 究主要集中在文件共享这一应用。 早期的网络中，由于个人计算机的存储和计算等能力与服务器之间的巨大差 距，c s 模式占据了互联网服务的主流位置。较早的文件分发应用多采用c s 模 式，由服务器向客户端提供数据，客户端并不提供服务。 伴随着网络规模的逐渐扩大，互联网用户越来越多，对文件分发的性能提出 了越来越高的要求，研究者们陆续提出来许多技术来提高文件分发服务的性能， 内容分发网络( c o n t e n td i s t r i b u t i o nn e t w o r k ，简称c d n ) 5 3 技术就是其中一类很 常见的技术。c d n 技术，用增加服务器数量、设置更多缓存等方法提高服务质 量。但是c d n 提供的服务仍然属于c s 模式，为更多的用户提供高质量服务的 代价高昂。而p 2 p 技术是一种廉价的可以提高文件分发性能的技术。 1 1 2 p 2 p 技术简介 p 2 p 是对等网络( p e e r t op e e r ) 的简称，通常可以定义 5 4 】为：网络的参与者共 享他们所拥有的一部分硬件资源( 处理能力、存储能力、网络连接能力、打印机 等) ，这些共享资源通过网络提供服务和内容，能被其它对等节点( p e e r ) 直接访问 而无需经过中间实体。在此网络中的参与者既是资源( 服务和内容) 提供者 ( s e r v e r ) ，又是资源获取者( c l i e n t ) 。p 2 p 文件分发，顾名思义就是使用p 2 p 技术 的文件分发应用。 随着个人计算机和网络的性能提高，p 2 p 逐渐发展起来。在p 2 p 文件分发中， 不存在传统的服务器和客户端的概念，每一个节点都是一个对等节点，每个节点 既从别的节点处获得数据，也向其他节点提供上传。在p 2 p 模式下，由于利用 了一般用户的上传带宽和计算资源，从而提高了网络的效率，可以为更多用户提 供服务。如图1 1 中的示例，图中每条边代表一条上传速率为1 的连接。在1 个 提供数据的节点，4 个节点需要数据的情况下，p 2 p 模式下的文件分发可以达到 第1 章绪论 l o 的总上传带宽，而c s 模式下，最多可达到4 的上传带宽。 o 可以达到的带宽 1 04 图1 1p 2 p 模式与c s 模式 相较于c s 模式，p 2 p 模式下的网络有分散化、可扩展性强、鲁棒性强、隐 私性强、性能优越、负载均衡等特点。由于上述特点，p 2 p 技术自诞生以来，就 在文件分发、流媒体服务、即时通信、分布式计算等领域被大量应用。 p 2 p 技术应用于文件分发系统，可以大幅度提高系统的分发速度和可扩展 性。最早的p 2 p 系统是n a p s t e r 3 7 】，一个用于共享m p 3 文件的系统。在n a p s t e r 之 后，很多p 2 p 文件分发系统和协议被开发出来，如：b i t t o r r e n t 4 0 】、e m u l e 4 1 】等 等。它们的共同特点是不存在服务器或者服务器只是提供索引功能，文件的上传 和下载主要在普通节点之间进行。b i t t o r r e n t 可以说是目前最为热门的p 2 p 文件分 发系统，在全世界有大量的用户使用。因为使用者甚多，现在对p 2 p 文件分发系 统的研究是网络研究的热点之一。 1 2 网络编码简介 本节将简单介绍网络编码的概念和研究意义。 2 0 0 0 年，香港中文大学r a l s h w e d e 等在i e e e 信息论会刊上发表的一篇论 文【1 】，首次提出了网络编码( n e t w o r kc o d i n g ) 的概念并从理论上证明：如果允许 网络节点对传输的信息按照合适的方式进行编码处理( 如异或、有限域上的运算 等) ，而非限于存储和转发，则基于该方式的网络多播能够实现理论上的，由最 大流最小截定理确定的最大传输容量。网络节点对传输信息进行操作和处理的过 程，就称为网络编码。 网络编码彻底改变了通信网络中信息处理和传输的方式，是信息理论研究领 域的重大突破，对网络吞吐率、鲁棒性、负载均衡、优化调度、安全等方面都有 第1 章绪论 提高的作用。网络编码一经提出，就吸引了众多学者的注意。有关于网络编码的 研究层出不求。 2 0 0 5 年，微软在【2 0 】一文中，首次提出了将网络编码引入p 2 p 文件分发系统 能够提高分发效率的观点，他们设计了一个使用随机线性编码 6 】的系统 a v a l a n c h e ，并在文章中通过模拟实验的结果，声称相较于一个类b i t t o r r e n t 的无 编码系统，a v a l a n c h e 提高了2 3 倍的下载速度。但是一些文章 2 2 指出网络编码 的计算开销等不利因素可能抵消它给p 2 p 文件分发带来的好处，甚至会导致使 用网络编码的系统性能不如无编码的系统。 1 3 本文的主要工作 为了降低网络编码的复杂度，我们提出了一种新的编码算法一稀疏线性编 码。在保证编码成功率的前提下，稀疏线性编码大幅度降低了网络编码的复杂度。 此后我们实现了一个使用稀疏线性编码的p 2 p 文件分发系统，并进行了与无编 码系统的对比实验，验证了稀疏线性编码可以提高p 2 p 文件分发系统的性能。 为了进一步提高使用稀疏线性编码的p 2 p 文件分发系统的性能，我们提出了预 先检测机制，并将其引入使用稀疏线性编码的p 2 p 文件分发系统，通过实验验 证了该算法可以提高系统性能。 本文的后续部分的组织如下，第2 章概要介绍p 2 p 技术和网络编码的相关 研究和应用，第3 章将提出稀疏线性编码算法，并分析它的复杂度。第4 章提出 一个基于稀疏线性编码算法的p 2 p 文件分发系统( s n c ) ，并与对照系统进行局域 网中的实验对比，分析它们在分发效率上的差异。第5 章在s n c 系统基础上引 入预先检澳g ( p r e c h e c k i n g ) 机制，得到一个改进系统( s m a r t c o d e ) ，在p l a n e t l a b 上 进行了广域网上的实验，与无编码系统和不使用预先检测的编码系统进行对比， 分析了系统在分发效率和鲁棒性上的性能优势。第6 章为全文的总结，并提出了 一些未来的研究方向。 4 第2 章背景知识 第2 章背景知识 本章摘要： 本章第一节将概要介绍p 2 p 技术的特点和研究现状，指出 p 2 p 目前的研究热点和面临的问题。同时也会对目前流行的 p 2 p 应用，如：p 2 p 文件共享、p 2 p 流媒体发布等进行简单介 绍。 在本章第二节中，我们将对网络编码的研究和应用现状做 出概述。在这一节中，我们首先介绍网络编码的背景知识和基 本原理，然后分析网络编码给网络带来的各种影响，对包括使 用网络编码的p 2 p 文件分发系统在内的各种网络编码的应用 进行概述。最后对现有的具体的网络编码算法进行简要介绍和 分析。 第2 章背景知识 2 1p 2 p 技术研究现状 本小节我们先介绍p 2 p 技术的特点，然后介绍一些p 2 p 技术的研究成果，最 后对p 2 p 技术的应用做概要介绍。 2 1 1 p 2 p 技术的特点 相较于c s 模式，p 2 p 模式下的网络有分散化、可扩展性强、鲁棒性强、隐 私性强、性能优越、负载均衡等特点。 1 ) 分散化：在p 2 p 网络中，网络交互需要的主要资源和信息分散储存于普 通用户节点中，不需要通过中心服务器或者只需要很少的中心服务，无 需中间环节，避免服务器的性能或带宽成为网络中瓶颈。分散化是p 2 p 的基本特点，给p 2 p 网络中带来可扩展性、鲁棒性等方面的优势。 2 ) 可扩展性：在传统c s 模式下，要为更多的用户提供服务，必须增加服务 器资源，在服务器端使用大量高性能计算机，铺设大带宽的网络，这些 产生了大量的开销，限制了系统规模的扩展。而在p 2 p 模式下，随着用 户的加入，系统整体的资源和服务能力也随着服务的需求同步增加和扩 充，能较容易地满足用户的需要。如果忽略管理开销，理论上p 2 p 网络 的扩展性接近无限，用户越多，系统的鲁棒性和服务质量就越好。 3 ) 鲁棒性：网络中可能发生很多种意外，例如：服务器当机，路由器损坏 等等。传统的c s 模式下，在某些意外造成服务器无法正常工作或用户无 法正常连接到服务器的情况下，无法提供服务。但是在p 2 p 模式下，服 务大部分是在各普通节点间进行，少数几个节点的失效并不会导致服务 失效。一些p 2 p 系统还能够根据带宽、节点数、负载等参数做出自适应 式调整，保证正常服务的进行。 4 ) 隐私性：当前的互联网通用协议不支持隐蔽通讯端地址的功能，用户的 信息对服务器端几乎完全透明，攻击者可以通过在服务器上放置木马等 方式获得用户信息甚至可以直接盗取用户计算机的控制权。在p 2 p 网络 中，由于消息传递的分散，用户的隐私信息更加难以被泄露。然而，p 2 p 网络也带来了管理困难、安全威胁等不利因素。 5 ) 性能：个人计算机的计算和存储能力已经得到了很大提高，互联网中存 在大量的个人计算机终端用户。这些计算机只作为用户存在的话，很多 存储、计算、上传带宽等资源都处于闲置状态。p 2 p 模式下，这些闲置 第2 章背景知识 资源可以得到更加充分的利用，可以用较低的成本提高整体服务的性能， 得到高性能计算和海量存储的效果。 6 ) 负载均衡：p 2 p 模式下各个节点从别的节点获得服务的同时也向其它节 点提供服务，由于节点数量很多，很难出现少数节点负载很大而多数节 点负载很小的情况。负载的分散使得p 2 p 模式和c s 模式相比，各节点的 负载更加均衡，可以避免出现服务器负载过高形成瓶颈的情况。 由于以上特点，p 2 p 在最近几年得到广泛的关注和研究。虽然也面临版权纠 纷，占用骨干网带宽过多，应用层交互过多增加了路由器压力等问题，大量的 p 2 p 软件和协议仍然是层出不穷。在以后的一段时间里，可以预见，p 2 p 还将是 网络研究和应用开发的热点。 目前和p 2 p 文件分发相关的研究热点主要集中于p 2 p 路由算法、p 2 p 信任和 安全问题、p 2 p 实际系统的实现和分析等几个方面。 2 1 2 p 2 p 路由的相关研究 p 2 p 路由不同于网络层的路由，主要是应用层的研究课题，包含p 2 p 中的节 点发现、拓扑结构的构建与维护、信息查找等方面的问题。按照信息索引方式的 不同，p 2 p 路由一般可以分成集中索引方式、洪泛广播方式、动态哈希表索引方 式几种模式： 1 ) 集中索引方式：集中索引方式即每一个节点将自己能够提供的资源信息 交付给一个或者多个中心服务器，由服务器提供索引功能。节点查找资 源时，先向中心服务器提出查询请求，由服务器找到拥有所需要的资源 的节点，然后节点之间进行交互。这种方式实现简单，查找快速，花费 的代价也较小。但是依赖中心服务器提供服务，系统的鲁棒性较差，早 期的p 2 p 系统如n a p s t e r 3 7 就是采用这种模式建立拓扑。 2 ) 洪泛广播方式：洪泛广播方式没有中心服务器，每一个节点查找资源时 向所有邻居节点发送查询请求，接到查询请求的节点向各自的邻居转发 查询请求，直至找到需要的资源或者查找失败为止。早期的g n u t e l l a 3 8 协议系统就是基于纯粹的洪泛广播方式。洪泛广播方式是完全的分布式 方式，不需要中心服务器，但是消耗的网络带宽等资源很多，搜索速度 和可靠性也不是很理想。 3 ) 动态哈希表索引方式：动态哈希表( d i s t r i b u t e dh a s ht a b l e ，简写d h t ) ， 第2 章背景知识 也叫做分散式杂凑表方式。d h t 是利用哈希表的方式将要搜寻的资料信 息( 一般是文件名) 映射到对应某个( 或某几个) 节点的d 上，由该节点储 存信息，查找资料时直接找到对应的节点即可。基于d h t 的p 2 p 网络 的关键问题在于如何进行映射，如何进行查找，以及如何处理节点的加 入和离开等等。例如：c a n e 3 9 、c h o r d 2 6 等都是基于d h t 的p 2 p 路 由协议。 使用d h t 方式进行路由和拓扑的p 2 p 网络相较于使用中心索引和洪泛广播 两种方式的p 2 p 网络来说，呈现出更多“结构化 的特点，在对p 2 p 进行分类 时也经常把这种结构归为分布式结构化p 2 p 类型。现在已经有了多种基于d h t 的p 2 p 路由协议，也有不少p 2 p 系统使用了这些路由协议进行拓扑控制和资源 搜索。 2 1 3p 2 p 中的信任和安全问题 本章对p 2 p 网络中面临的信任和安全问题做简单介绍，然后介绍一些在p 2 p 中应用的安全策略。 2 1 3 1p 2 p 中的信任和安全问题简介 随着互联网上的p 2 p 应用越来越多，针对p 2 p 的攻击行为也越来越频繁。由 于p 2 p 节点兼有服务器的功能，普通用户的个人计算机将会有更多的机会暴露于 互联网上，这样也就带来了更多的风险。p 2 p 网络所具有的特性可能会带来下列 安全隐患： 1 ) 拒绝服务( d o s ) 攻击：d o s 攻击即让目标机器停止提供服务或资源访问， 导致合法用户不能够访问正常网络服务的攻击行为。d o s 攻击是一种历 史悠久，但是简单有效的攻击方式，例如：发送大量的无用数据包来使 服务器瘫痪等等。在p 2 p 网络中，由于服务分散于大量的节点之中，d o s 攻击对于整体网络的影响并不是很大，但是对单个节点来说d o s 攻击仍 然可以造成节点瘫痪。恶意节点可以通过大量无效的数据请求消耗节点 的网络带宽，占用系统资源，使得系统性能降低甚至完全瘫痪。处理这 种攻击的难点在于如何将恶意节点和真正负载过重的节点区分开。合理 选择网络底层的拓扑结构，均衡系统中的负载和资源，加入流量控制策 第2 章背景知识 略等措施综合使用可使恶意节点无法占用过多的资源，降低其对系统的 影响。 2 ) 分布式拒绝服务( d d o s ) 攻击：d d o s 攻击也可以看作是一种d o s 攻击，通 过很多“僵尸主机”( 被攻击者入侵过或可间接利用的主机) 向受害主机 发送大量看似合法的网络包，从而造成网络阻塞或服务器资源耗尽而导 致拒绝服务。相对而言d d o s 攻击更加隐蔽，规模和破坏力更强，也更加 难以防范。针对p 2 p 服务的d d o s 攻击往往不是针对某一个p 2 p 应用，通 过伪装成正常的p 2 p 应用，消耗大量的网络资源，可能造成大规模的网 络性能下降甚至瘫痪。 3 ) 恶意软件分发：由于p 2 p 没有中央服务器控制，缺乏对分发文件的检测， 而且有的p 2 p 系统允许匿名分发。如果破坏者通过p 2 p 系统散发恶意软 件，会给大量用户带来安全隐患。信誉评估系统、完整性检测等手段可 以一定程度上遏制利用p 2 p 进行恶意软件分发的行为。 4 ) 信息泄露和篡改：使用p 2 p 的计算机必然要共享一部分资源，有的p 2 p 系统还要求用户保存一些网络地址和其他信息，恶意节点有可能利用这 些特点进行窥探和篡改。这方面主要靠p 2 p 协议设计时尽可能减少安全 漏洞来进行预防。 2 1 3 2p 2 p 中的安全策略 在一些工作 1 1 1 2 中提出可以通过结合以下三个标准要素来建立p 2 p 网 络的信任和安全体系： 1 ) 认证：确定某些实体实际上是否就是它们自称的人或东西的过程，网络 中的认证通常使用数字签名技术。在p 2 p 中，认证有两种形式。第一种 形式是网络中，一个节点向其它对等节点认证它自己。第二种形式是一 个p 2 p 应用的用户向该应用认证它自己。在一些p 2 p 应用中，两者实际 上是同一个过程。 2 ) 授权：授予一个认证过的节点实施某些行为或访问某些资源的许可过程。 在一个p 2 p 应用中，可能只将部分权限授权给一个节点，只有指定的资 源才允许访问。 第2 章背景知识 3 ) 加密：把易理解的信息( 明文) 转化为一种对未授权的个人和系统来说难 理解的形式( 密文) 的过程。解密则是将密文转化为明文的过程。在p 2 p 应用中，加密的一个明显的用途就是保护在一个可能不安全( 通信可能被 窃听或篡改) 的网络中，节点问流动的信息。与每个对等节点的安全认证 结合在一起，可以确保交换数据不会在通信中被窃听。如果同时进行了 数字签名或在信息中加入了消息认证码( m a c ) ，通信双方还可以确定该信 息是否被人篡改过。 2 1 4p 2 p 实际系统和应用 从1 9 9 9 年，第一个大型的p 2 p 系统n a p s t e r 3 7 投入使用起，有很多的p 2 p 应用 协议和实际系统被开发出来。在文件共享、流媒体服务、即时通信、分布式计算 等领域，p 2 p 技术被频繁应用，大幅度提高了网络的服务质量。本节主要对p 2 p 文件共享做一些简介。 2 1 4 1p 2 p 文件共享 文件共享是互联网中的重要应用，p 2 p 技术开始被人们熟知就是用于文件共 享。以下是对一些被广泛应用或曾经被广泛应用的p 2 p 文件共享协议和系统的简 单介绍： 1 ) n a p s t e r ：最早利用p 2 p 技术进行文件分发的大型系统是n a p s t e r 3 7 ，一个 主要用于m p 3 共享的p 2 p 网络系统。n a p s t e r 本身并不提供m p 3 文件的下 载，它使用一个中央服务器用于存储m p 3 文件的连接位置并提供检索， 而m p 3 文件则存放在用户自己的计算机上。n a p s t e r 具有强大的搜索功能， 可以将在线用户的m p 3 音乐信息进行自动搜寻并分类整理，以备其他用 户查询，用户搜索到的文件通过p 2 p 方式直接在节点间传播和共享。因 为版权方面的诉讼，n a p s t e r - - t 2 0 0 2 年6 月被迫关闭。 2 ) g n u t e l l a 3 8 】：g n u t e l l a 吸取t n a p s t e r 的教训，使用了完全分布的洪泛广 播方式进行索引。在g n u t e l l a 系统中没有中心服务器，所有的数据都存放 在普通节点中。用户只要安装支持g n u t e l l a 协议的终端软件，计算机就会 自动搜寻其他g n u t e l l a 节点，并加入g n u t e l l a 网络中。早期g n u t e l l a 纯粹地 使用洪泛方式进行资源查找和定位，造成g n u t e l l a 网络搜索的代价高昂， 而节点的频繁加入离开又造成搜索结果的不可靠。在较新的协议版本中， l o 第2 章背景知识 g n u t e l l a 将节点分成“超节点( u l t r an o d e s 或u l t r ap e e r s ) ”和“叶节点( 1 e a f n o d e s 或l e a f p e e r s ) ”两类，让超节点分担较多的搜索任务，一定程度上 提高了搜索性能。此外，g n u t e l l a 的一个拓展协议g n u t e l l a 2 ，提供了一个 扩展的数据包格式、基于u d p 的搜索算法和许多其它扩展比如数据包压 缩等等。 3 ) b i t t o r r e n t 4 0 ：b i t t o r r e n t 协议是架构于t c p i p 协议之上的一个p 2 p 文件传 输协议，处于t c p i p 结构的应用层，同时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 p 地址等) ，较新版本的 b i t t o r r e n t 同时也支持d h t 方式进行节点发现。b i t t o r r e n t 协议支持以文件 的数据块为单位进行传输，而b i t t o r r e n t 软件使用了局部稀缺优先( l o c a l r a r e s tf i r s t ) 算法进行文件块之间的传输调度，有很多研究指出该策略提高 了文件分发的效率。b i t t o r r e n t 协议相当流行，支持b i t t o r r e n t 协议的客户 端软件还有b i t c o m m e n t ，b i t s p r i t 等等，b i t t o r r e n t 协议非常适合于进行热 门文件的文件分发。 4 ) e m u l e 4 1 】：又称电驴，是一个开源的p 2 p 文件共享软件，基于e d o n k e y 的网络协议( e d 2 k 4 6 】) 。e m u l e 是现在使用最广泛的基于e d o n k e y 的网络 协议的p 2 p 软件。客户端使用多个途径搜索下载的资料源，e d 2 k 、来源交 换、k a d 8 共同组成一个可靠的网络结构。e m u l e 的排队机制和上传积分 系统有助于激励人们共享并上传给他人资源，以使自己更容易、更快速 地下载自己想要的资源。虽然节点的发现不依赖中心服务，但是e m u l e 的资源索引还是使用中心服务器，导致如果主要服务器被封锁，整个e d 2 k 网络都会遭到惨重打击，可能使得大量用户流失。 5 ) 迅雷 4 2 ：英文名t h u n d e r 。迅雷是由迅雷网络技术公司开发的一款的下 载工具软件，并不是一款纯粹的p 2 p 软件。迅雷采用p 2 s p ( p e e rt os e r v e r & p e e r ) 的方式来结合和取代传统的下载方式。例如：用户a 使用迅雷从某 个服务器下载文件时，它的信息会被共享。当用户b 使用迅雷下载同一 个文件时，如果用户a 的迅雷服务仍然开启，会通过后台向用户b 上传用 迅雷软件下载的文件，使得传统h t t p f t p 等协议下的资料以p 2 p 模式传 输，能够获得较高的下载速度。有说法称迅雷客户端一经执行，便会检 索客户端电脑全部资源( 无论用户设定与否) ，并将该台电脑所拥有的档 案资源泄漏于服务器，但是这种说法并没得到证实。 第2 章背景知识 除了上述几种p 2 p 协议和软件以外，m a z e 5 3 、k a z a a 5 4 等也有比较多的用 户，因为p 2 p 文件共享协议和软件很多，这里不再一一介绍。 2 1 4 2p 2 p 技术的其它应用 p 2 p 技术除了文件共享之外，在流媒体服务、即时通信、分布式计算等领域 被大量应用。 1 ) 流媒体服务：相对于p 2 p 文件共享来说，p 2 p 流媒体服务中用户对服务的 实时性要求更高，对参与节点的带宽要求也更高。p 2 p 流媒体软件一般 采用以服务器为根节点建立多播树，将用户节点作为多播树的一个节点 加入网络的方式提供服务。早期的p 2 p 流媒体软件大多只支持直播服务， 随着技术的进步，很多p 2 p 流媒体软件也可以支持点播( v o d ) 服务。 c o o l s t r e a m 2 5 ，p p l i v e 4 3 】等是比较著名的p 2 p 流媒体软件。 2 ) 即时通信：q q 4 7 】、m s n 4 8 】等即时通信软件，一般采用登录中心服 务器的方式验证用户身份，而用户间使用p 2 p 方式进行通信。这些软件 也支持p 2 p 的语音和文件传输功能。有些即时通信软件为了对文字中的 一些关键词进行过滤，文字信息的传递采用了中心服务器转发的方式， 也有的软件将过滤的关键词列表直接嵌入客户端，在服务器不参与文字 信息传递的方式下实现关键词过滤。 3 ) 分布式计算：分布式计算也叫网格计算。现代个人计算机的计算能力越 来越高，但是一般的用户大部分时间用不了那么多的计算资源，可以将 一些本身非常复杂，但是却很适合于划分的计算，划分成大量的更小的 计算片断，并通过互联网分配给大量的个人计算机，利用其闲置的计算 资源进行并行处理，最后将这些计算结果综合起来得到最终的结果。 s e t i h o m e 4 4 ，a v a k i 4 5 等系统就是利用互联网上大量个人计算机的 闲置资源进行大规模计算，其中普通的个人计算机间用p 2 p 方式进行通 信和合作。 除了上述应用以外，p 2 p 技术还被广泛应用于分布式存储、协作网络安全保 障、无线网络建立和维护等领域。 第2 章背景知识 2 2网络编码研究现状 传统的网络多播传输中，中间节点仅仅完成数据包的存储一转发，而不对数 据包做任何处理，有时候这种方式无法使多播传输达到“最大流最小割”( m a x f l o wm i n - c u t ) 定理 9 确定的最大理论传输容量。网络编码( n e t w o r kc o d i n g ) 1 】 是一种新的网络技术，在一定条件下可以提高网络的传输效率，达到理论上的最 大传输容量。本节将简要介绍网络编码的概念和特点。 2 2 1 背景知识：网络流和最大流 我们可以用有向图来对实际的通信网络进行抽象描述和研究。例如：图2 1 中的有向图g = ，e ) ，v 表示节点的集合，e 表示有向边的集合。边用( a ，b ) 或 者磙示，这里a ，6 为图中的两个节点。 s 图2 1 一个网络流图 对图中的任一顶点v 定义边集： 厂。( 力= ( w ，v ) l ( w ，de e 厂+ ( v ) = ( 1 ，w ) l ( v ，川a e ) 分别表示流进和流出节点v 的边的集合，其大小称作节点的入度和出度。一 个节点被称作源( 或者信源) ，用婊示，另外一个或一些节点称作汇( 或者信宿) ， 用壕示。用h e a d ( e ) 和e n d ( e ) 表示一条边的起点和终点。每一条边有非负权值w ( a ， b ) ，称为边的容量。这样的有向加权图也可以被称为网络图( 或者网络流图) 。 这里图中的节点表示网络中的主机，图中的边表示实际中的一条端到端的通 信链路，边的容量w ( a ，b ) 代表n 向6 发送数据的带宽。 对于网络流图g ，每一条边( i ，力都给定一个非负数f ( i ，力，如这组数满足 下列两个条件时称其为该网络的可行流( f l o w ) ，可以用卢 f ( i ，力f ( f ，力e ) 来 表示： 第2 章背景知识 1 ) 对每一条边( f ，力