（计算机应用技术专业论文）基于网络编码的应用层组播算法研究.pdf

摘要 2 0 0 0 年，a h l s w e d e 等人基于网络信息流的概念提出了网络编码的 思想。通过允许网络节点进行编码，可以获得网络组播速率的最大流 限，即网络资源利用的理论上限，而通过传统的路由和复制并不一定 能够获得该最大流限。此外通过网络编码可以取得节省网络带宽资 源，平衡链路负载，优化能量受限网络的能量消耗等好处。目前，有 关网络编码理论的研究已经引起了学术界的高度重视，网络编码已经 成为网络信息理论领域最受瞩目的研究热点之一。 论文在分析网络编码理论的基础上，深入研究了网络编码与应用 层组播的融合机制，着重研究了基于随机方式的网络编码的应用层组 播算法。 本文首先介绍网络编码的原理，分析网络编码获得最大吞吐量的 原因。研究网络编码与应用层组播的融合机制，在对各种机制性能进 行分析基础上，提出了一种基于随机方式的网络编码的应用层组播算 法；对于网络拓扑结构的建立，采用最小费用最大流算法来实现，为 了节约带宽，在最小费用最大流算法基础上提出减少组播会话冗余吞 吐量算法，目的就是使网络流量最大而费用最小；对随机方式的编码 策略进行分析研究，提出所解决的问题。最后，在所提出的算法的基 础上，对基于随机方式的网络编码的应用层组播进行性能评价，评价 标准包括报文开销( m e s s a g eo v e r h e a d ) 、编码的延迟率( c o d e d e l a y r a t i o ) 、吞吐量，对b r i t e 拓扑生成器作了详细介绍。从实验结果分 析得出，本文提出的算法所达到的吞吐量和理论上的最大吞吐量很相 近。 关键词应用层组播，网络编码，最大吞吐量，最小费用最大流 a b s t r a c t n e t w o r kc o d i n gi si n t r o d u e e db ya h l s w e d ei n2 0 0 0 w h i c hi sb a s e d o nt h ec o n c e p t i o no fn e t w o r ki n f o r m a t i o nf l o w i fc o d i n gi sp e r m i t t e db y t h en e t w o r kv e r t i c e s ，t h em a x f l o wb o u n do fn e t w o r km u l t i c a s tc a nb e a c h i e v e d ，i e t h et h e o r e t i c a lu p p e rb o u n do fn e t w o r kr e s o u r c eu t i l i z a t i o n ， w h i c hc a nn o ta l w a y sb ea c h i e v e db yt r a d i t i o n a lc o p y i n ga n dr o u t i n g f u r t h e r m o r e ，t h r o u g hn e t w o r kc o d i n g ，w ec a l lo b t a i nt h eb e n e f i t so f s a v i n gi nb a n d w i d t h , l o a db a l a n c i n g ，o p t i m i z i n gt h ee n e r g yu s a g eo f e n e r g y - l i m i t e dn e t w o r k sa n ds oo n n o w ，t h er e s e a r c ho fn e t w o r kc o d i n g h a sr e c e i v e dg r e a ti n t e r e s t sa n dh a sb e c o m eo n eo ft h em o s ta t t r a c t i v e f i e l d si nn e t w o r ki n f o r m a t i o nt h e o r y n i st h e s i si n v e s t i g a t e ss o m ea s p e c t so fn e t w o r kc o d i n gw i t l l e m p h a s i so nt h ea p p l i c a t i o no fn e t w o r kc o d i n g ，l u c u b r a t e st h ei n t e g r a t i o n m e c h a n i s mo fa p p l i c a t i o nl a y e rm u l t i c a s tw i t hn e t w o r kc o d i n g ，f o c u so n a l mm e c h a n i s mb a s e do nr a n d o mn e t w o r kc o d i n gm e c h a n i s m f i r s t ，t h ep r i n c i p l eo fn e t w o r kc o d i n gi si n t r o d u c e d ，a n a l y s i st h e r e a s o n sf o rt h en e t w o r kc o d i n gg e t sm a x i m u mt h r o u g h p u t i n t e g r a t i o n m e c h a n i s mf o ra l ma n dn e t w o r kc o d i n gi sr e s e a r c h e d ，o nt h eb a s i so f a n a l y s i s o ft h ep e r f o r m a n c eo fv a r i o u sm e c h a n i s m s ， c o m p a r e sa n d a n a l y s e sa l m b a s e d0 1 1n e t w o r kc o d i n gp e r f o r m a n c e ，p r o p o s e saa l m a l g o r i t h mb a s e do nr a n d o mn e t w o r kc o d i n g ：f o rt h ee s t a b l i s h m e n to ft h e n e t w o r kt o p o l o g y ，u s e sam i n i m u mc o s t - m a x i m u mf l o wa l g o r i t h mt o a c h i e v e ，t oc o n s e r v eb a n d w i d t h ，b a s e do i lm i n i m u mc o s t - m a x i m u mf l o w a l g o r i t h mp r o p o s e s am e t h o df o rr e d u c i n gt h r o u g h p u to fm u l t i c a s t s e s s i o n r e d u n d a n c y ，t h eo b j e c t i v e i st oe n s u r em i n i m u mc o s t sa n d m a x i m u mn e t w o r kf l o w ；a n a l y s i st h er a n d o mn e t w o r kc o d i n gs t r a t e g y ， a n dr a i s e st h ei s s u er e s o l v e d f i n a l l y , o nt h eb a s i so ft h em e c h a n i s m p r o p o s e d ，g i v e np e r f o r m a n c e e v a l u a t i o ns t a n d a r do ft h ew h o l e m e c h a n i s m ：m e s s a g eo v e r h e a d 、c o d e d e l a yr a t i o 、t h r o u g h p u t , t h e n i n t r o d u c e st h es i m u l a t i o n p l a t f o r m f r o m t h e e x p e r i m e n t a l r e s u l t s a n a l y s i s ，i nt h ec a s eo fc o d e d e l a yr a t i oi n c r e a s ei sn o tv e r ys i g n i f i c a n t ， t h ea l mm e c h a n i s mo fb a s e do nr a n d o mn e t w o r kc o d i n gt oa c h i e v e t h r o u g h p u ti sv e r yc l o s e t ot h et h e o r e t i c a l l ym o s t t h r o u g h p u t k e yw o r d s a p p l i c a t i o nl a y e rm u l t i c a s t ，n e t w o r kc o d i n g ，m a x i m u m t h r o u g h p u t ，m i n i m u mc o s ta n d m a x i m u mf l o w i i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：匹碰日期：塑互年半月塑日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文；学校可根据国家或湖南省有关部门规定送交学位论文。 作者躲趔年新签碰单吼粤年勘望日 硕e 学位论文 第一章绪论 1 1 课题研究背景 第一章绪论 随着网络技术的不断发展，特别是分布式多媒体应用技术的兴起，出现了诸 如视频会议、视频点播、网络电视、新闻发布等一对多或多对多的组播通信需求。 这种业务的特点是“在时间上具有一致性，空间上具有分布性”【l 】。比如，具有 多个分会场的视频会议系统是典型的多数据源多接收者的组播通信需求，而网 络电视是典型的单数据源多接收者的组播通信。 这种单点到多点，多点到多点的群组通信应用，需要有如下的保证： ( 1 ) 在目前网络的条件下，有效地将数据从数据源传送至所有的接收者。 ( 2 ) 不论接收者处于网络的任何位置，其都能接收到所感兴趣的数据而不受 网络条件的限制。 ( 3 ) 接收者可以自由地加入、退出通信组。 ( 4 ) 接收者数目很多时，系统照常能够工作。 ( 5 ) 不论接收者是何种设备，其都能有效的接收数据。 满足了以上保障的通信技术，就是有效的组播( m u l t i c a s t ) 通信。 i p 组播是指在i p 网络中将数据包以尽力传送( b e s t - e f f o r t ) 的形式发送到网络 中的某个确定节点子集，这个子集称为组播组( m u l t i c a s tg r o u p ) 。组播的基本思想 是，源主机只发送一份数据，这份数据中的目的地址为组播组地址；组播组中的 所有接收者都可接收到同样的数据拷贝，并且只有组播组内的主机可以接收该数 据，网络中的其他主机不能收到。 然而，十多年过去了，虽然对i p 组播的研究一直都在进行，但是由于m 组 播本身所固有的缺点，使得i p 组播至今并没有能够得到广泛的应用： ( 1 ) 路由器必须为每个组播组单独保存状态，这造成i p 组播的扩展性很差。 ( 2 ) 要求所有参加组播的端系统之间的路由器都必须支持组播功能，这给i p 组播的推广使用带来很大的困难。 ( 3 ) 试图用一种统一的组播模型来适应所有的应用，而现实中不同的应用对 组播的要求差别很大，这给组播算法的设计造成很大的困难。 ( 4 ) 组播组的管理方法存在缺陷，在组播组的加入、退出和管理等方面开销 大，组播组的加入和退出的延迟也很大。当存在大量规模很小的组播组， 或者组播成员在空间上的分布很稀疏时，组播组管理上的开销将超过组 播在带宽方面上的优势。 硕士学位论文第一章绪论 ( 5 ) i p 组播( 这里主要针对i p v 4 ) 的地址空间太小，在组播地址的分配上存 在困难。 ( 6 ) 在经济方面，组播打破了传统的根据通过进入流量计费的机制。除了以 上这些问题以外，i p 组播在安全、拥塞控制等方面也存在很多问题。 1 2 应用层组播技术 1 2 1 应用层组播模型 面对i p 组播业务在因特网中的困境，一些研究者开始反思i p 组播体系结构 本身的问题。针对冲组播存在的这些问题，提出将复杂的组播功能放在端系统 实现的新思想。于是出现了一种以底层网络为基础的基于叠加网的应用层组播协 议。覆盖网( o v e r l a yn e t w o r k s ) 是一个位于一个或多个己知网络拓扑上的独立的虚 拟网络。它的主要优点在于它的架构，它不需要改变底层网络的结构，可以快速 部署所需的网络功能。如果在叠加网的基础上实现组播，我们可以把组播实现提 高到应用层。端系统实现组播业务的思想是将组播作为一种叠加的业务，实现为 应用层的服务，因此，端系统组播又称为应用层组播( a p p l i c a t i o nl a y e r m u l t i c a s t ， a l m ) 。 有两种实现a l m 的基本模式，一种称为p 2 p 组播，其组播树建立在p 2 p 霹j ( p 2 p o v e r l a y ) 基础上，端系统( p e e r s ) 之问通过随机方式构成组播树，应用比较灵活，但 其传输延时因一些p e e r s 较慢以及较长的物理路径而较高，设计不好的组播算法 也容易导致网络拥塞和较低的网络资源利用率。另一种模式称为基于代理的组播 ( b a s e d - p r o x ym u l t i c a s t ) ，通过部署若干服务节点构成一个传输基础结构( o v e r l a y ) ， 其特点是稳定性高、节点与链路资源便于管理。 应用层组播的基本模型【2 l 如图1 。1 所示。图1 - 1 ( a ) 为i p 组播数据传输的方式， 数据在网络内部的路由器上进行复制；图1 - 1 ( b ) 为应用层组播的数据包在网络的 终端系统进行复制。 ( a ) i p 组播 图1 - 1 应用层组播模型 2 ( b ) 应用层组播 硕上学位论文第一章绪论 1 2 2 应用层组播研究现状 围绕应用层组播面临的问题，国内外学者开展了大量研究，提出了很多不同 的解决方案。基本上，可以将以往的研究划分为三个阶段： ( 1 ) 初步探索阶段。2 0 0 0 年，美国卡耐基梅隆大学的y a n g 等人提出了n a r a d a 3 1 应用层组播算法，这是在i p 组播面临一系列困难的情况下较早将研究兴趣转移 到应用层的尝试。n a r a d a 首先构造一个覆盖网，之后采取类似i p 组播d v m r p 协议的算法实施组播。n a r a d a 的贡献在于首次提出了一个相对完整的端系统组 播方案，强调了应用层组播面临的特殊问题。其他类似的研究还有t a g ( t o p o l o g y a w a r eg r o u p i n g ) 0 j , t s ( d i ，它与n a r a d a 很相像，不同点在于t a g 的组播成员通过 会话建立从树根到自己的路径。o m n i ( o v e r l a ym u l t i c a s tn e t w o r ki n f r a s t r u c t u r e ) 5 1 则是一个两层的覆盖网组播协议，底层由一组服务节点构成，提供数据分发服务； 而段用户则通过以o m n i 节点为根的有向生成树连接到o m n i 节点获得服务， 这是第二层，并独立于底层。o m n i 的特点在于分层机构，但是其组播算法本身 与上述方案并无实质性区别。 ( 2 ) 应用实验阶段。由于应用层组播便于实现和推广，因此稍后一些的研究 多半以某种比较成功的p 2 p 覆盖网为基础结构，通过特定组播算法实现具体应 用。例如，p a s t r y 6 1 采取节点自组织方法构造覆盖网，而s c r i b e t t | 则使用反向路径 转发技术实现组播。t a p e s t r y t 8 】也是一个有名的覆盖网结构，而b a y e u x t g l 以 t a p e s t r y 为基础，采用前向路径转发算法完成数据组播。此外，c a n 组播【l o 】也 是对p 2 p 结构c a n t “1 的一个扩展。 基于p 2 p 结构的组播放发的特点事成员关系管理机制建立在已有的p 2 p 结构 基础上，具有较好的规模伸缩性，适合于数据共享；但是，应用层组播面临的性 能问题，资源利用率问题等，仍悬而未决。 ( 3 ) 优化提高阶段。由于分布式多媒体应用始终把高性能放在首位，因此人 们不得不关注组播算法的性能问题。国内，中科院曹佳等研究了应用层组播的最 小延迟生成树算法【1 2 l ，通过分析影响延迟的主要因素，把应用层组播树的求解 抽象成“度约束最小延迟生成树”问题，并提出了两类启发式近似算法。该研究 强调了度约束对应用层组播优化的重要性。东南大学吴家皋【1 3 】等针对异构环 境，研究了覆盖网组播路由问题，对度约束模型进行扩展，描述了一种新的适应 异构环境的覆盖网组播模型，采用分层的带宽分配策略，提出了一种异构环境下 构造最小延迟半径组播树的启发式算法，有效降低了组播树的高度和网络资源使 用量。该研究还以此为基础，采用局部优化策略，在延时和带宽之间进行平衡， 从而向综合优化方向迈出了一步1 1 4 1 。 为了提高组播性能和网络资源利用率，研究人员也探索了所谓拓扑敏感的组 硕士学位论文第一章绪论 播，例如1 a g 通过时新加入的节点能够尽可能长地共用其父节点地网络路径， 以降低链路开销。 总的看来，上面提到的各种解决方案都不同程度地推动了应用层组播研究的 发展，但诚如文献【1 5 】所言，现有的每一种方案都强调某个特定目标的优化。 n a r a d a 和各种基于p 2 p 覆盖网结构的组播主要考虑组播算法的实现问题。t a g 考虑了网络信息的利用，提高了资源利用率，但仍然忽视了其他优化因素f 如度 约束和延时等1 。 在应用层组播算法的设计中，有以下一些假设： ( 1 ) 网络中的带宽和转发资源是相对丰富的，而服务器的能力是一个主要瓶 颈。使用应用层组播会比i p 组播消耗更多的带宽，但是和单播方案相比，它还 是可以有效的降低服务器的负载和减少带宽的使用。 ( 2 ) 大多数参与组播的端系统可以贡献出一部分资源用于组播的转发。这个 假设并不是针对所有的应用层组播算法，但是不少的应用层组播算法都有这个假 设。 ( 3 ) 上层应用对性能的要求并不很苛刻，可以容忍报文的丢失和较大的延迟。 i n t e m e t 的可靠性本来就无法完全保证，参与组播的主机性能也无法保证。所以， 应用层组播并不针对所有的应用，而主要针对那些对可靠性和性能要求较低的应 用。应用层组播的主要优势有两点。首先，应用层组播便于实现和推广。它只需 要改变端系统，而不需要对路由器进行任何修改。其次，应用层组播便于针对特 定应用进行优化，可以针对不同的应用使用不同的实现方案，而不必像l p 组播那 样必须统一到一个模型中。 我们对现有的应用层组播进行分类。如图1 2 所示，我们可以将应用层组播按 分发算法和集中算法分为两大类。其中属于集中算法的有a l m i ，h b m l l 6 1 ，它们 主要对成员进行集中的管理。而分发算法则按其拓扑的建立分为m e s h 网优先和 树优先。利用m e s h 网优先其组播鲁棒性好，但控制负荷较大。另外现有的应用 层组播依据其发送者的个数，我们可以将现有应用层组播分成单源和多源。 o v e r c a s t 1 7 嘱于单源，它们只有一个发送源，通常情况网络拓扑比较稳定，实现 起来也比较方便。n a r a d a 属于多源，它们可以有多个发送源，因此网络拓扑需要 动态的改变，实现也比较复杂。利用和结合i p 组播，有t a g ，h m t p 培1 。针对少 量的接收成员情况，有a l m i ，n a r a d a 。此外，现有的应用层组播将p 2 p 的思想应 用到组播路由的设计，可以实现大量接收者的组播，如c a n ，b a y e u x ，s c r i b e 。 还有应用数学上的方法进行网络拓扑的设计，构造出适于应用层组播的网络拓 扑，如d t 1 9 1 ，s e a t t e r c a s t l 2 0 主要是用于广域网的内容分发。y o i d t 2 1 1 提出一系列的 协议。适应普遍的内容分发网络。另外，还有针对延迟、带宽等方面的应用层组 4 硕士学位论文第一章绪论 播实现，也有针对实际应用的应用层组播。 h u 棚 ( a 】集中算法分类 t r a n g u i a t i o n ( b ) 分发算法分类 图1 2 应用层组播的分类 1 2 3 应用层组播亟待解决的问题 直观上，端系统实现组播功能可以避开网络层实现组播功能的许多难题： ( 1 ) 无i p 组播中复杂的地址结构、复杂的协议。 ( 2 ) 应用层组播的状态在主机系统中维护，不需要路由器保持组的状态，解 决了业务的扩展性问题，网络可以支持大量的组播组。灵活性地定制组播业务。 ( 3 ) 组播应用可以随时部署，无须购买昂贵的组播路由器、不需要网络设备 的升级和功能扩展。 ( 4 ) 可以简化组播的控制、可靠等功能的实现，建立在网络连接之上的应用 层组播可以使用t c p ，u d p 服务，如可以利用t c p 的可靠和拥塞控制简化组播 的可靠和拥塞控制。在网络层实施组播易产生拥塞的限制，因此应用层组播解决 i p 组播的不可靠性及拥塞问题。 但是，应用层组播尚存在许多亟待解决的问题： ( 1 ) 组播性能不高。由于应用层组播是通过端系统的单播实现组播的，应用 层对网络状态( 包括拓扑和q o s 状态信息) 不了解，应用系统通过自组织方法构造 出来的覆盖组播树往往出现多个覆盖路径穿过同一物理链路，使通信量在一些物 理链路上过于集中，导致所谓的链路紧张；同时因缺乏网络信息的支持，容易产 生折返连接，使端系统之间的传输延时较大，传输带宽需要提高。 ( 2 ) 动态适应性不强。应用层组播的动态性比网络组播更为强烈，因为不仅 端系统的加入和退出会改变组播结构，它所依赖的网络层也是一个动态变化的平 台，所以，组播算法应在两个方面都具有良好的动态适应性，当群组关系和网络 状态发生变化时，及时重构组播树，以保持良好的性能和资源利用率。 ( 3 ) 网络资源利用率低。与i p 组播相比，一般的应用层组播会使用更多的网 络资源。这里，组播算法不能做到网络敏感仍然是主要原因，例如大折返除了增 大传输延时外，还必然消耗更多的网络链路和带宽资源，因此降低了网络资源利 用率。另外，算法没有考虑端系统在能力上的变化和有限性也是原因之一，例如 硕上学位论文第一章绪论 一个性能欠佳的主机不太可能承担更多的存储与转发任务，而一个性能更好的主 机则应当发挥更大的作用，如果组播算法无视这一点，势必导致资源利用上的不 合理。 上述第三点己经提到，应用层组播虽然使用了更多网络资源，但是它的网络 资源利用率并不高，所以，如何提高应用层组播的网络资源利用率，实现最大的 传输容量是亟待研究的问题。 1 3 网络编码的提出和发展现状 正是针对现有应用层组播技术的上述问题，网络编码( n e t w o r kc o d i n g ，n c ) 应运而生，它可以用来实现由最小割最大流定理t 2 2 1 给定的一个通信网络的容量 上限。由最小割最大流定理，我们可以知道网络中两点之间的最大流量可以通过 最小割来衡量；同时，实现最大流的路径可以通过最大流算法瞄】找到。所以， 当要建立两点之间通信的时候，我们可以在两点之间，应用最大流算法，得到它 们之问的最大传输速率。但是，当我们考虑一点向多点的组播路由树的建立时， 问题就复杂起来。一般认为，组播树的建立是一个n p 问题【2 4 】。一般采用的方法 是先采用最大流算法找到信源与一个信宿之间的最大流及其实现的路径；然后再 依次寻找其他信宿与信源之间的路径。在寻找信源与第二个信宿之间的路径时， 往往就在原通信网络中去掉信源与第一个信宿之间已经用过的链路的容量。这样 处理是因为，传统路由认为网络中传输的信息是不能叠加的，只能进行存储转发。 我们可以看到，这样的组播树的建立方式会导致信源与第二个及其后面所有信宿 之间的路径都不是以它们之问的最大流进行传输的。这将最终使得组播可以实现 的传输容量远远小于最小割最大流确定的容量上限。 1 3 1 网络编码的提出 随着信息时代的不断发展，各种通信网络与人们工作生活的各个方面结合的 越来越紧密。与此同时，由于用户数量的激增，网络服务的多样化以及针对网络 传输质量要求的不断提高，如何提高现有网络资源的利用率，优化网络，己成为 当今网络通信研究的重要课题之一。传统的网络组播方式是在网络中寻找一棵有 效的组播树，这种方式下网络节点只对数据分组进行路由或复制。这样很难达到 网络组播的最大传播容量。从信息论的观点讲，我们没有必要对网络节点的功能 加以限制。 2 0 0 0 年，香港中文大学的a h l s w e d ee ta 1 等人【2 5 l 在i e e e 上发表了一篇题为 “网络信息流”的文章，这篇文章为我们提高网络的传输容量指明了一个新的发 展方向，他们从信息论的角度出发，严格证明了：网络编码可以帮助我们达到通 6 第一章绪论 f ? i 列络的最人容量，从而最大限度的利用网络的现有资源。网络编码的提出从本 质1 i j 般了通信网络中传统的信息处理方式，它现在已是通信网络研究领域中的 一个衙的研究热点。 像很多基本的概念一样，网络编码也是基于一个很简单的思想。网络编码是 指n 舅 播通信网络中，可以在网络的中间节点上对接收到的信息进行一定形式的 编鹳处理，然后再传输出去，而不是像传统通信网络中那样在中间节点上只是进 j 存储转发。然后再在信宿节点上，通过一定的处理方式，译出信源所发的信息。 一个通信网络可以用有向图来表示，根据图论中的最小割最大流定理可知， 一个m 络町以传输的最大流量等于其最小割。但传统的存储转发式路由方式，并 不能实现网络的最大流传输，所以它并不是最佳的；而如果使用网络编码的话， 即在删络的中间节点上，对其接收到的信息允许先进行编码后再传输出去；在接 收端，h 的节点再根据自己的要求译出所需的信息，则可以大大提高网络的传输 速率，充分利用网络中的链路资源，从而实现最小割最大流定理给定的可传输信 息的上限。严格的讲，其实传统的路由方式是网络编码的一种特殊形式。 图1 - 3 经典网络编码例子 f 面我们举一个例子【2 5 】来说明网络编码的基本处理思想及其带来的好处。在 这里，我们考虑的是一个无差错的传输系统。通信网络如图1 3 所示，这是一个 组播网络，不考虑时延和传输差错。其中s 是源节点，y 和z 是目的节点，每条 边的信息速率均为每单位时间l 比特。从图中我们可以看出，为了从信源节点s 同时传输两比特信息6 l ，b ，到目的节点，则在中间节点w 处，必须通过网络 编码，使输出边( w ，x ) 传输两个输入边上携带信息的线性组合b l + b e ，那么在目 的节点y 和z 处，才可分别由b l + 致和b l ，b l - i - b e 和b ，恢复出所有信息a l ，a 2 。 如果按传统路由方式，在一个单位时间内将无法完成以上传输。 7 硕= ：学位论文 第一章绪论 网络编码不但可以用在组播通信网络中而且还可以用在非组播网络中以提 高网络容量。另一方面，网络编码在提高网络的通信容量的同时，在负载均衡、 降低能量消耗等方面也有不容忽视的作用。 1 3 2 网络编码的发展和研究现状 自从2 0 0 0 年r a h l s w e d e 等人提出网络编码的基本概念之后，关于网络编码 的研究如雨后春笋般多起来。目前，有很多电信业巨头和著名的大学都在致力于 这方面的研究，比如说，有香港中文大学、微软、麻省理工学院、伊利诺伊大学、 加利福尼亚大学洛杉矶分校、以色列的t e l a v i v 大学等等。他们的研究方向也是 多种多样，下面简单介绍一下。 ( 1 ) 基于已知整个网络的拓扑信息。一类是由r k o e t t e r 和m m e d a r d 2 6 1 1 2 7 2 s 1 给出的网络编码的代数构造方式。这类构造方式是在知道整个网络的拓扑信息的 情况下，用一个系统转移矩阵来描述信源输入信息和信宿上接收到的信息之间的 关系，并通过构造符合要求的系统转移矩阵来实现网络编码。另一类是es a n d e r s 等人提出了一种实现网络编码的多项式时间算法 2 9 1 1 姗。这种方法将网络编码的 构造进一步简化，它也是在己知拓扑的情况下，首先通过最小割最大流算法找到 完成组播所需的路径的集合，在找出的这个子图上，再自上而下的确定各个节点 所需要进行的操作。这种方法不但把网络编码构造的复杂度从指数级降到了多项 式级，而且大大降低了网络编码中所采用的字母表的下限。 ( 2 ) 不需要网络拓扑信息的分布式网络编码和随机网络编码。分布式网络编 码p l 】的实现是在网络中传输的每个数据包上留出一些比特用来记载此数据包在 前面各个节点上所经历的各种操作，那么接收节点就可以从接收到的数据包中直 接译出信源所发送的信息。这种方法是可以在不知网络拓扑信息的情况下实现网 络编码，但是增加了网络负载，但是仿真表明，在整个信息的组播过程中，这种 处理方式所带来的负载代价是不大的。另外一种不需网络拓扑的方法是随机网络 编码1 3 2 1 1 3 3 1 ，即在网络的中间节点上对接收到的信息在一个有限域内随机选择一 个元素作为组合的系数。研究己经表明只要有限域取得足够大，这种方法的失败 率就可以很低。这种方法带来的缺点一个是以一定的概率实现正确无误的传输， 另一个是需增大通信网络中所需的字母表的大小。 ( 3 ) 文献【3 4 】讨论了所谓最小网络编码组播问题，提出了一种使网络编码数据 包数量最小的分布式算法，该文还研究了在某些节点路由受限的情况下如何进行 编码的问题。文献【3 5 】首次研究了无线网络环境下的实用网络编码技术，提出了 一个机会编码算法，一个节点通过学习其邻居节点信息以便检测编码机会；如果 节点a 获悉节点b 有足够的信息解码a 发过来的包，a 就将多个包的编码发给b 。 8 硕：i ：学位论文第一章绪论 文献【3 6 】研究了网络编码用于提高组播吞吐量问题，作者提出了一个具有网络编 码功能的覆盖网组播方案，通过构造k 冗余组播树形成所谓组播图( m u l t i c a s t g r a p h ) ，然后实施网络编码。其分布式算法分为三个步骤，首先建立一个由所有 群组成员构成的密集连通图，然后基于该图得到一个所谓次树，该树仅包含源s 和中间节点( 属于成员节点但不是接收者) ；最后运行一个选择算法将叶节点( 接收 者1 通过两条路经连到中间节点上去，构造出所谓k 冗余树( 该文仅讨论了k = 2 的情 况) 。该方案在编码上沿用了线性组合方法，没有具体考虑数据内容的特点；k - 冗余树构造算法要求叶节点不断查询中间节点，报文开销较大；该方案将成员节 点划分成中间节点和叶节点的做法不符合应用层组播的特点，即便在o v e r l a y 组 播中允许安置这种中间节点，也付出了较多额外代价：此外方案未考虑k - 冗余树 的维护与重构问题。 “) 这类建议在覆盖网高带宽数据传输中，构造多组播树或者是一个覆盖 m e s h 网，这些例予有s p l i t s t r e a m 3 7 1 ，b u l l e t 3 8 1 ，还有d i g i t a lf o u n t a i n 捌。在 s p l i t - s t r e a m 中，它对源数据进行分段并且通过不同的树发送，以提高传输带宽。 在d i g i t a lf o u n t a i n 和b u l l e t 中，接收端接收到一定数量的独立分组后就能将其还原 成原始数据，这种方案有效地推进了覆盖m e s h 网的发展。为达到最大的吞吐量， 这类建议方案都依靠它们很强的缓冲池能力来权衡端与端的延迟，所以这些建议 方案对于大宗数据下载和对延迟敏感的流媒体都是很有价值的。另一类建议是每 个覆盖节点建立k 条链路到其它的覆盖节点，随机建立的链路可能是最短的( 最小 的延迟) ，最宽的( 最高的带宽) 。但是先前的研究表明，若总是选择k 条最好的链 路可能会导致连接性能变差和覆盖m e s h 网的直径变大。解决这样的问题，可以 选择最好的链路和随机链路的混合 4 0 1 。y o u n ge ta 1 】提议一个分布式算法来计 算k 最小生成树( k m s t ) ，边的权对应着它的延迟或者损失率。 假定一个覆盖节点可以在g a l o i s 域使用线形编码来编码和解码数据，那么理 论上的网路编码可以就应用到实际中去【4 2 】。相对于一般性的编码，网络编码仅 在源和目的节点分别编码和解码，它允许每一个网络节点根据需要编码和解码数 据流。编码过程就是在g a l o i s 域使用线形编码，它包括两个基本的符号：+ 和运 算符，由于在o a l o i s 域中的元素有固定长度，所以数据流的字节长度在编码后并 不会增加。 近来，不少组播算法【4 3 m 4 5 闱已提出利用编码组播的基本网络流结构可有效 地实现高效率传输和低成本的传输。 总之，现在关于网络编码的研究是百家争鸣，各种方法和应用层出不穷，但 是没有一个统一的标准，而且多数是基于理论分析，试验仿真很少。到目前为止， 网络编码应用到实际网络中去还比较少，所以关于网络编码的研究还有很多东西 9 硕士学位论文第一章绪论 去做，这是一个相当诱人的新领域。 1 4 本文研究内容及结构 1 4 1 本文研究内容 网络编码理论的提出之后，它在提高网络资源利用率方面的非凡能力引起了 人们的极大兴趣。网络编码的核心思想在于：使网络节点不仅能够存储转发数 据流，而且能够对数据流进行编码和解码，业已证明，在这个前提下一个源端可 以将数据以网络的最大容量( 理论上的最高值) 传输到一组接收者。网络编码是一 个十分新颖的技术，但是现有的研究大部分集中在网络编码理论上，而如何将网 络编码与应用层组播算法相融合的研究则刚刚起步。 首先，网络编码并不是为应用层组播技术本身而提出来的，在很多领域，应 用层组播节点是端系统，本身可以承担编码、解码，但网络编码有很多冗余节点， 它和应用层组播并不是天然地融合在一起，所以本文研究内容之一就是要研究网 络编码是怎样与应用层组播技术相融合的。 其次，清楚了如何科学合理地把网络编码应用到应用层组播算法中的融合机 制以后，本文还将深入研究基于随机方式的网络编码的应用层组播算法研究，要 解决的问题就是在考虑链路的费用的情况下，网络能否达到最大的吞吐量。应用 层组播中的节点需要知道网络的拓扑结构，对于网络拓扑结构的构造，不仅要考 虑每条链路的最大流，还要考虑链路的费用，因此，本文还将拟研究如何构造一 个符合编码传输的这样一个传输拓扑网，来达到网络的最大吞吐量。 最后，如何对这种算法的性能进行评价也是本文研究的重点之一。本文用网 络拓扑生成器来生成网络拓扑，并从报文开销( m e s s a g eo v e r h e a d ) 、编码的延迟率 ( c o d e - d e l a yr a t i o ) 、吞吐量3 个评价指标来衡量提出算法的性能。 总之，本文拟深入研究如何利用网络编码技术提高应用层组播的传输吞吐 量，提高组播的有效性，从而一定程度地解决组播应用所面临的问题，以适应不 同的网络状况和应用目的。 1 4 2 本文结构 本文拟重点研究采用网络编码给应用层组播带来的好处，着重探讨提高组播 吞吐量的途径和方法，并通过模拟仿真实验，检验算法设计的正确性和有效性。 论文全文共分五章： 第一章绪论。详细地论述网络编码是如何产生的，重点介绍了当前网络编 码发展的趋势和未来的发展方向，并且阐述了作者即将进行的课题，最后对文章 1 0 硕l 学位论文第一章绪论 的研究内容和结构作简单介绍。 第二章网络编码与应用层组播的融合机制。阐述了网络编码组播的最大流 限的概念，给出了网络编码应用层组播的几种融合机制，在此基础上提出了一种 基于随机方式的网络编码与应用层组播融合机制， 第三章基于随机方式的网络编码应用层组播算法。首先提出了一种基于随 机方式的网络编码的应用层组播算法的基本思想，接着提出了一种在最小费用最 大流算法基础上构造网络拓扑结构，使用随机方式的网络编码思想在构造的网络 拓扑上传输信息。 第四章算法性能评价。本章中对提出的一种基于随机方式的网络编码的应 用层组播机制的性能进行了评价、模拟，最后总结和分析了实验结果。 第五章结论与展望。对所做的研究与设计工作进行了总结，并阐述了将来 进一步的工作计划。 硕士学位论文第一二章网络编码与应用层组播的融合机制 第二章网络编码与应用层组播的融合机制 本章首先介绍网络编码的概念，然后阐述网络编码组播的最大流限：在分析 网络编码与应用层组播算法融合机制的基础上，给出了一种新的基于随机方式的 网络编码与应用层组播的融合机制。 2 1 网络编码 对于一个实际的通信网络，我们可以采用一个有向图来加以描述和研究。有 向图中的节点表示一台主机，图中的一条边表示实际中的一条端到端的通信链 路。 2 1 1 网络流与信息流 对于一个有向图g = ( 矿，e ) ，这里v 表示节点的集合，e 表示边的集合。网 络中一条边用( 口，6 ) 表示，这里a ，b 为网络中的两个节点。对图中的任一顶点v 定义边集： r _ 1 ( v ) = 矿l ( 嵋v ) 毋( 2 1 ) r “( v ) = w i ( w , v ) 毋( 2 2 ) 表示流进和流出节点v 的边的集合，其大小称作节点的入度和出度。入度为 零的节点称作源( 或信源) ，出度为零的节点称作汇( 或信宿) 。用h e a d ( e ) 和c n d ( e ) 表示一条边的起点和终点。 若一个有向图g = ( y ，e ) 仅有一个源点和一个汇点，且有向图中的每一条边 ( f ，) 对应着一个非负数，我们将其称作该边的容量，则称该有向图为网络流 图【1 4 l 。图2 1 便是一个网络流图。 s 固2 - i 一个网络流图 硕士学位论文第一二章刚络编码与应用层组播的融合机制 对于网络流图g ，每一条边( f ，_ ，) 都给定一个非负数只，这一组数满足下列两 个条件时称为这网络的可行流，用f = e ：( j ，) e ) 表示它。 ( 1 ) 每一条边( f ，j ) ，有e r 。； ( 2 ) 除信源s 和信宿t 以外的所有的节点i ，恒有： 凡= 而 ( 2 - 3 ) t j 这表示中间节点流量守恒，输入的与输出的量相等。 ( 3 ) 对发点s 和收点t ，有 f s i = 矽= w ( 2 - 4 ) f ， w 称作该网络流的流量，而且从s 点流出的总量等于流入信宿t 的总量。当 局= 时便称边( f ，_ ，) 饱和，或f 饱和，表示流f 对该边己饱和。该网络流图的 最大流指从信源s 送往信宿t 的流量w 的最大值，用m a xf l o w ( s ，f ) 表示。 设u 为节点集合的一个子集，使得s u ，t 叠u ，我们把一个端点在u 而另 一个端点不在u 的边的集合毛= ( f ，) e ：i u ，_ ，萑u 称作节点s 和t 的一个 割。割的容量定义为集合e u 中包含的所有边的容量的和，用c ( s ，t ) 表示，即， 厨 ( 2 5 ) ( 1 。j ) e g v 图2 1 中虚线表示节点s 和t 的一个割，其中： u = i s ，b ，c ，j ， c ( s ，) = r 腑+ r 蛔+ r 肿+ r 前= 4 + 3 + 2 + 4 = 1 3 。( 2 - 6 ) 很显然，对于一对节点，其不同的割对应的容量可能不同。 定理2 - 1 ( 最小割最大流定律) m 1 ：厨于已知的网络芴盈吼以蔗派j 勇偌宿f 的谠堂 w 的最大值等于其最小觏的容量印 m a xj i o w ( s ，f ) = m i n c ( s ，f ) ( 2 7 ) 该定理的证明可以参考文献 2 2 1 。 对于一个有向网络，我们可以采用f o r d f u l k e r s o n 标号算法和d i n i c 算法 2 2 1 求解网络的最大流。 前面在对有向网络的流的介绍中指出，对于网络中的非源节点和非汇节点， 流进该节点的流量的总和等于流出该节点的流量的总和，即，流量是守恒的。但 是该特性只适用于实际的商品流。因为信息流不同于商品流，信息可以进行复制 和压缩。但是信息流也遵循一定的法则。 虽然物质商品和信息本质上是不一样的，但是它们都遵循一定的流的法则的 约束。