（通信与信息系统专业论文）随机网络编码在forces路由器中的应用研究.pdf

随机网络编码在f o r c e s 路由器中的应用研究摘要采用控制与转发分离( f o r c e s ) 技术，f o r c e s 路由器的功能模块能够灵活地进行重构而产生新的业务，使得新业务的添加就像简单的添加软硬件积木模块的过程。网络编码作为一种新颖的网络传输技术，其中间节点具有对信息进行编码、解码的能力。它的出现使最大化组播容量成为可能。在带宽受限的通信网络中，网络编码提供更高的传输速率和传输性能，具有较高的网络资源利用率。本文利用f o r c e s 路由器模块化特点，在其内部构造随机网络编码模块，使其能够在组播网络中，对满足编码条件的信息流进行编码。在此基础上，利用不相交路径，构造口层的二冗余组播编码图，对数据包采用分布式随机网络编码。实验表明，相比单纯的稀疏模式独立组播协议( p i m s m ) ，采用网络编码的f o r c e s 路由器能够得到更高的网络吞吐量，当信宿达到1 5 0 时，吞吐量增加一倍。关键词：f o r c e s ，网络编码，编码组播图，随机线性，路径a p p l i c a n o no fr a n d o mn e t w o r kc o d i n gd 寸f o r c e sa b s t r a c tf o r c e sr o u t e rw h i c ha d p o t sc o n t r o la n df o r w a r d i n gs e p a r a t i o n ( f o r c e s )t e c h n o l o g yh a so p e na r c h i t e c t u r e ，m o d u l a rd e s i g no ft h en e t w o r kc o m p o n e n t s i tc a ng e n e r a t ean e wr e c o n s t r u c t i o nb u s i n e s sf l e x i b l y , w h i c hm a k e sn e wb u s i n e s si m p l e m e n t a t i o ni st h es a m e 嬲a d d i n gt h es o f t w a r ea n dh a r d w a r em o d u l e sl i k eb u i l d i n gb l o c k s n e t w o r kc o d i n gi san o v e ln e t w o r k 缸3 a s i 嚣i s o i o l ：t e c h n o l o g y i tp r o p o s e san e wi d e ao ft h e o r yt h a ti n t e r m e d i a t en o d e sh a v et h ef u n c t i o no fe n c o d i n ga n dd e c o d i n g a san e wf i e l do fc o m m u n i c a t i o n ，i t sa p p e a r a n c em a k e sa c h i e v e m e n to fm u l t i c a s tc a p a c i t yi nt h el i m i t e db a n d w i d t hc o m m u n i c a t i o n sn e t w o r kp o s s i b l e ，p r o v i d i n gah i g h e rt r a n s m i s s i o nr a t ea n dt r a n s m i s s i o np e r f o r m a n c e 懿w e l la sh i g hu t i l i z a t i o no fn e t w o r kr e s o u r c e s i nt h i sd i s s e r t a t i o n ，f o r c e sr o u t e rm a k e su s eo fm o d u l a rc h a r a c t e r i s i c st oc o n s t r u c tr a n d o mn e t w o r kc o d i n gm o d u l a r a sar e s u l t ，i tc a ne n c o d ed a t as t r e a m st h a ts a t i f i e dt h er e q u i r e m e n ti nam u l t i c a s tn e t w o r k o nt h i sb a s i s ，am u l t i c a s tc o d i n gg r a p hw i t ht w or e d u n d a n ti pl a y e ri sc o n s t r u c t e du s i n gd i s j o i n tp a t h s w i t hs u c hg r a p h ，ad i s t r i b u t e dr a n d o mn e t w o r kc o d i n gi su s e di nf o r c e sr o u t e r e x p e r i m e n t ss h o wt h a tt h ep r o p o s e da l g o r i t h mc a ng e th i g h e rt h r o u g h p u t ，w h e nt h er e c e i v e rr e a c h e s15 0 ，t h et h r o u g h p u th a sd o u b l e dc o m p a r e dw i t hp i m s m k e y w o r d ：f o r c e s ；n e t w o r kc o d i n g ；r a n d o ml i n e a rn e t w o r kc o d i n g ；p a t h1 绪论1 1 研究背景及意义f o r c e s 4 能够灵活配置底层资源产生新的业务，该特性使网络编码在f o r c e s 路由器中的应用成为可能。网络编码1 2 8 1 作为一种新型的传输技术，能够提高有线网络的吞吐量和组播传输速率，使网络设备的性能得到进一步的提高。1 1 1 f o r c e s 技术路由器是互联网的关键设备，多功能的需求使得路由器的设计变得越来越复杂，关于路由器的体系架构和设计方法的创新逐渐引起关注。开放架构网络技术的研究成为目前国际上备受关注的新一代网络设备。i e t f 早在2 0 0 2 年专门成立，f o r c e s 工作组，开始有关f o r c e s 技术研究和相关协议标准的制定工作。f o r c e s 技术作为开放网络架构的一个重要组成部分，使一种资源开放的、可编程的、可方便重构设置的网络设备成为可能，该网络设备也是网络运营商所高度期望的新一代网络设备。1 1 2 网络编码技术早在1 9 5 6 年，香农在“a n o t eo r lt h em a x i m u mf l o wt h r o u g ha n e t w o r k ”一文中首次提出：“通信网络端对端的最大信息流，是由网络有向图的最小割决定的”。但是传统路由器只具有存储转发的功能，恰恰由于这个限制，组播难以达到香农提出的最大通信流量。也正是出于这一点，网络编码作为一种新颖的网络传输技术应运而生，它被看作是2 1 世纪后信息处理和信息传输研究领域上最重要的理论成果之一。网络编码的核心思想是在一个组播网络中，网络中的中间节点除了对数据进行存储转发外，还具有对接收到的信息进行线性或非线性的处理的能力。中间节点对数据包进行处理后，将其转发给其他节点。所有的数据包到达信宿节点后，信宿节点按照一定的处理方式，恢复原始信息。有别于传统的中间节点，具有网络编码能力的中间节点不仅具有存储、转发功能，还具有信息处理功能，扮演着编码器或信息处理器的角色。网络编码是对现有的网络体系结构的完全颠覆，在传统的路由器中实现网络编码是一件相当艰巨的任务；而f o r c e s 路由器具有资源开放的、可编程的、可方便重构的特点，为网络编码的实际应用提供了一种过渡方案。在不推翻原有网络体系架构的基础上，f o r c e s 路由器通过增加具有随机网络编码功能的软件模块，使网络编码在路由器上的应用成为了一种可能。具有随机网络编码能力的f o r c e s 路由器能够有效的提高网络吞吐量，它在f o r c e s 路由器中的应用研究是具有理论和现实意义的。1 1 3 研究意义目前，f o r c e s 已经成为国际上备受关注的开放架构网络设备的研究热点，它具有模块化、分布式、开放性、可编程的特点，通过灵活重构支撑新业务，使得业务功能的实现过程类似于简单的添加软硬件模块的过程。f o r c e s 技术代表了当前开放网络架构研究的前沿水平，为下一代网络设备的研究做出了重要贡献。网络编码颠覆了传统的网络设备复制和转发的基本思想。它提出网络的中间节点不仅要具有复制和转发功能，还具有数据处理功能，能够对信息进行压缩，处理，推翻了单个比特不能够被压缩的理论，大大提高的网络性能。网络编码的特点是复杂度低，应用性强。然而，如何将现有的网络编码的研究成果快速应用到真实的网络设备( 如路由器等) 中去，是摆在工程技术人员面前的一道难题。由于研究者找不到一个合适的平台进行实现测试和效果评估，之前大量有关网络编码的研究工作大都基于仿真完成，距离实际的应用部署依然遥远。通常新技术、新思想的实现需要一个良好的、开放性的实验平台，而f o r c e s 天然地具备这些特性，因此本论文研究性地探索两者结合的可行性，采用基于网络编码的f o r c e s 路由，以此来提高网络资源利用率，并进行了实现方面的尝试努力，具有一定原始创新性。1 2 f o r c e s 与网络编码的研究现状本论文对国内外有关f o r c e s 和网络编码已取得的研究成果和相关技术文献进行了了大量、详实的研究，具体内容综述如下。21 2 1 f o r c e s 的研究现状目前，i e t f 基本完成对f o r c e s 的相关标准的制定，国内外相关机构针对f o r c e s 网络设备的研发工作也已全面展开。系统实现方面，国内的浙江工商大学的网络与通信工程研究所基于i n t e li x p 2 4 0 0 2 8 5l 网络处理器【3 6 1 ，开发了f o r c e s 路由器的原型系统和f o r c e s 中间件，该中间件的出现，加快了将f o r c e s 技术应用到开放架构网络设备的速度。国防科技大学计算机学院研究小组深入研究了基于f o r c e s 的路由体系结构，特别是对基于f o 以e s 体系的i p v 6 路由器展开了研究，基于f o 心e s 思想开发新一代路由器，采用自主设计的接1 2 1 协议1 1 4 】，其控制件基于通用机，转发件基于网络处理器。北京交通大学的研究小组对路由器控制平面的实现展开研究，这个控制件是基于i x p 2 4 0 0 和通用c p u 的i p v 4 和i p v 6 t 2 1 ，并实现了原型系统。在国外，s u n 公司的n e o n 项目遵循控制和转发分离的基本思想及f o r c e s 协议接口，研究可编程网络组件的体系架构及其实现方法，并在f e 模型架构下使用规范来完成集成网络服务的处理工作。a t & t 网络研究部的路由器研究开发组提出从转发件分离出路由协议模块1 2 3 1 ，在f o r c e s 框架下实现分离路由控制平台r c p 。i b m 的f l e x i n e t项目在f o r c e s 结构的指导思想下设计分布式路由器【1 2 1 ，该路由器可以通过结点模块的动态删减、加载从而实现相应功能的动态删减、加载。瑞典皇家理工学院的m h i d e l l 等人自己定义了f o r z 协议【1 6 】【1 7 1 ，基于f o r c e s 结构实现了路由器，该路由器用n e t l i n k 实现转发件与控制件的内部通信，转发器采用l i n u x ，控制器基于u n i x 和z e b r a 的路由软件。在f o 疋e s 协议互操作方面，2 0 0 9 年7 月，在i e t ff o r c e s 工作组的指导下，由浙江工商大学、希腊p a t r a s 和日本n t t 三方机构一起进行了f o r c e s 协议实现的互操作测试【b 】，测试结果在第7 5 届i e t f 会议上进行报告。之后，浙江工商大学和j a m a lh a d is a l i m 又把各自独立开发的f o r c e s 协议解析模块嵌入到协议解释分析器t c p d u m p 和e t h e r e a l w i r e s h a r k 中，并在互操作测试中成功使用该解析模块中，：给第三方验证f o r c e s 协议带来了极大的方便性。1 2 2 网络编码研究现状网络编码概念的提出在学术界引起了极大的震动。世界各地的知名高校纷纷投入到网络编码的研究队伍中来，并取得了一些重要的研究成果，为网络编码的发展奠定了良好的基础，提供了宝贵的资源。2 0 0 0 年，a h l s w e d e 首次提出网络编码的概念【2 引，他从信息论角度出发对网络编码进行证明：当满足符号域接近无穷大的条件时，信源可以达到理想的组播容量，但他仅仅给出了最大网络信息流的存在性证明，并没有给出具体的模型和实现方式。在2 0 0 3 年，a h l s w e d e 再次发表论文【3 1 1 ，构造了网络编码的基本框架，给出了网络编码的实现方式。该文献的发表使网络编码从理论上升到了可以实现的技术高度，为后续的网络编码的应用和发展指明了方向，奠定了基础，意义重大。目前，关于网络编码的路由算法研究非常少，主要的有：k a p i lb h a t t a 0 8 l 提出了两个路由算法，分布式算法和有限路由算法。分布式算法使参与网络编码包的数目最小化，有限路由算法是基于网络编码的；d s l u n 提出在组播网络中建立最小代价多播连接【l o 】，得出的结论是在有线网络中，建立最小代价多播比s t e i n e r 弓i 用树可以少1 0 艄o 的计算量。在编码算法方面，最初的研究大多都是着重在提高编码所带来的传输速率。l i ，y e u n g 等) k i 3 1 】在2 0 0 3 证明使用线性网络编码能够达到组播容量最大化，他们认为节点的信息函数可以是简单的线性组合，例如f ( y l ，y 2 ，y 3 ) = yl y l + y2 y 2 + y3 y 3 。同理，信宿的解码同样可以使用线性计算。基于l i ，y e u n g 的研究结果，j a g g i ，s 觚d e r s 等人继续证明【2 5 】【2 9 】，在有向无环网络中，寻找编码和解码系数是一个多项式时间算法。在满足一个足够大的域的前提条件下，h o 等人【划【3 5 】提出随机网络线性编码，该方法是基于一种随机线性网络编码向量的策略，中间节点随机选取链路到链路映射的随机组合，这些映射的关系是相互独立的。这样做的好处是以较高的概率使转移矩阵满秩，保证信宿节点成功译码。j a g g i 等【l5 】指出l f i = 2 1 6 和i e i = 2 8 时解码成功率为0 9 9 6 ，c h o u 2 4 】等指出i f i = 2 8 就足够实际应用了。在实际应用方面，微软的p 2 p 文件共享系统a v a l a n a c h e l 6 1 就采用了随机网络线性编码这一编码策略。在编码安全方面，j o nf e l d m a n 等人在n c a i 提出的基于门限切割方案的安全模型【2 1 】1 2 2 1 基础上，提出了安全的网络编码构造等效于寻找某种普遍距离特性的线性码问题，通过编码域和容量两者间的折衷从而实现网络编码的安全性。4c h r i s t o sg k a n t s d i s 【8 j 等人提出文件分发问题的协作安全模型，该模型基于网络编码，不仅能够有效的检测熵的攻击和投放攻击，而且还能检测出恶意的中间节点。基于网络编码的网络连接研究。s r i i s 3 0 1 指出传统差错控制码的设计和差错控制的网络编码之间存在很强的联系，为基于差错控制的网络编码设计提供方向。k o e t t e r 和m e d a r d l 2 刀提出一种静态线性编码保障在链路中断可能的网络上进行可靠传输方式。综上，目前对于网络编码的研究现在还大多处于理论研究阶段，不过也有不少网络编码在实际应用研究中的成果出现。如微软公司开发了一款p 2 p 雪崩型( a v a l a n c h e ) 软件 6 】，该软件预计能够提高百分之二十至三十的网络信息传输率，不仅节约了下载时间，还能够增强p 2 p 系统的鲁棒性。p a c h o u 掣2 4 】研究了网络编码在实际应用中的相关问题和解决方案，并对其进行仿真和分析。网络编码在大数据分发中的应用问题也被研究7 】【8 1 9 1 1 2 6 。1 3 论文的主要工作和创新点1 3 1 主要工作论文在不推翻原有路由器等网络设备的体系架构的基础上，结合f o 疋e s 技术提出了一种随机网络编码在网络设备中应用的过渡方案。通过在f o r c e s 网络设备内部的数据处理路径上增加具有网络编码能力的逻辑功能模块( l f b ) ，使得网络编码在路由器上的应用成为可能。论文的主要工作如下：1 在充分分析随机网络编码算法原理的基础上，探索其与f o r c e s 技术的结合可行性。2 基于f o r c e s 路由器，设计了组播管理模块并构造了组播网络，进而为网络编码的应用奠定了基础。3 从f o r c e s 支持随机网络编码功能的角度出发，分析并设计了数据包的处理流程，基于该流程提炼出相关l f b 模型定义。4 以基于i p 层编码的f o r c e s 路由器为例，构建二冗余组播网络，分析并评估采用随机网络编码后，对网络整体性能的影响。1 3 2 创新点论文的创新点主要有两点：1 基于f o r c e s 结构，提出了一种随机网络编码在路由器中应用的过渡性的解决方案，该方案具有一定的原始创新性。2 针对f o r c e s 路由器中的随机网络编码功能，提出了一组相关l f b 的原创性的设计和定义，该工作是对f o r c e sl f b 库的扩展和补充。1 4 本文结构本文的正文部分一共为六章，其分布如下：第一章介绍了f o r c e s 技术和网络编码技术的研究背景、意义以及国内外研究现状，最后阐述本文的主要工作，创新点和论文组织结构。第二章介绍了f o r c e s 技术和网络编码技术，主要描述了f o r c e s 的网络件架构、转发件及逻辑功能模块，然后讲述了网络编码的理论基础，数学模型以及从理论高度上，对网络编码进行可用性分析。第三章介绍了f o r c e s 组播环境下的网络编码，重点描述了f o r c e s 体系架构的组播环境，为网络编码的应用奠定基础。第四章阐述了支持网络编码的f o r c e s 路由器的关键技术。在f o r c e s 路由器的框架下，进行组播网络的构建，然后根据网络编码和f o r c e s 路由器的实际情况，采用随机网络编码作为f o r c e s 路由器的码构造算法，添加相关网络编码模块，详细分析f o 疋e s 路由器对数据包的处理过程，最后对随机网络编码l f b进行设计。第五章阐述i p 层下的f o r c e s 路由器组播编码，f o r c e s 路由器构建一个二冗余组播图，在其内部维护一个随机网络编码的编码构造算法，根据数据包的输入情况，选择性地进行编码，并对其性能进行初步地仿真测试。第六章对全文进行总结，提出下一步的工作的想法和期望。62 f o r c e s 与网络编码网络编码的核心思想是编码构造算法，考虑到随机线性网络编码的特点以及优势，本文采用随机网络编码作为f o r c e s 路由器的编码算法。本章首先阐述f o r c e s 网络件架构，然后在网络编码的研究成果基础上，深入分析网络编码的传输机制以及随机网络编码构造算法，探索网络编码和f o r c e s 技术融合的可行性，为随机线性网络编码在f o r c e s 系统架构下的应用研究打下基础。2 1 f o r c e s 网络件架构i e t ff o r c e s ( f o r w a r d i n ga n dc o n t r o le l e m e n ts e p a r a t i o n ，转发件和控制件分离) 工作组专门研究开放可编程的i p 路由器的体系结构和协议标准，是目前开放可编程网络研究最受关注的研究组织之一。r f c 3 6 5 4 ( f o r c e s 需求分析1 和r f c 3 7 4 6 ( f o r c e s 框架) 对f o r c e s 规范的网络组件作了基本的定义。图2 1f o 疋e s 网络基本结构1 4 1图2 1 表示了f o r c e s 网络基本结构图【4 】，一个满足f o r c e s 标准的网络设备由至少一个( 或多个) 控制件( c o n t r o le l e m e n t ，c e ) 和多达上百个的转发件( f o r w a r d i n ge l e m e n t , f e ) ，其中多个转发件用来冗余备份。c e 与f e 之间通过“f o r c e s 协议”进行相互通信，这个连接点被称为f p 参考点( f o r c e s 控制接口) ，f p 参考点可以经由一跳( s i n g l eh o p ) 或多跳( m u l t i h o p ) 网络实现。控制件c e 主要处理f o r c e s消息，并且对f e 中的l f b 进行管理。f e 处理和转发数据包主要是线速的。f o r c e s协议规定f p 参考点上传递两种消息格式：控制消息和重定向消息。控制消息包含7c e 对f e 控制管理内容的消息，例如属性的配置和查询消息，能力和事件的上报消息。重定向消息是含c e 上所处理的重定向数据包的消息。重定向数据包是指从外部到达f e ，需要有f e “重新定向”到c e 进行处理的数据，或者是c e 产生的，需要f e “重新定向到”网络设备外部的数据包。f i f 是网络接口参考点，这个网络接口参考点是网络设备对外的接口，网络数据与网络设备的通信是通过这个接口参考点的，并由这个网络设备进行数据转发处理，而f i 是同一个设备内的各个f e 之间进行通信的接口协议，根据f e 之间的拓扑关系构成一个分布式的转发件网络，完成不同的转发功能。f r 是在同一个网络转发件中的各个c e 之间进行通信的连接协议。所有的c e 都是由c e 管理器( c em a n a g e r , c e m ) 进行管理，类似的情况，所有的f e由f e 管理器( f em a n a g e r , f e m ) 进行管理，而且c e m 和f e m 可以相互交换管理信息。特别需要注意的是，c e m 和f e m 仅仅对一些基本的设备进行管理，比如给每个c e 和f e 配置i d 号等等，对于f e 的管理则是有c e 通过f o r c e s协议来完成的，因此，c e m 和f e m 可以被看作是c e 和f e 用来管理人机接口的。虽然图中给出的c e m 和f e m 是在f o r c e s n e 内部，在c e 和f e 外部的，但是在物理上，c e m 和f e m 很有可能是被嵌入到c e 和f e 内部。2 1 1 转发件及逻辑功能模块转发件f e 内的体系架构主要是由f o r c e sn e 模型协议r f c5 8 1 2 定义的，f e内的基本结构图2 2 所示。不同的逻辑功能模块l f b ( l o g i c a lf u n c t i o n a lb l o c k ) 可以表示f e 内的资源，l f b 以及它的属性都是由c e 通过f o r c e s 协议定义的，各个l f b 之间连接关系也是由c e 经过f o r c e s 协议控制，从而形成不用的l f b 拓扑结构，实现资源的动态配置，为i p 数据包提供不同处理的数据通道。常见的l f b 有分类器( c l a s s i f i e r ) 、调度器( s c h e d u l e r ) 、最长前缀i p v 4 i p v 6 转发器等等。图2 2f o r c e s 转发件的基础结构f o r c e s 技术是一种开放性技术，它能够使网络设备具备强大的模块化积木式功能。软件c e 和硬件f e 可以在产品级进行分离，同一个网络设备的c e 和f e 可以由不同的厂家进行生产。进一步地说，在同一个f e 内，它的l f b 也可以由不同的厂家进行生产，在产品级实现分离。c e 通过f o r c e s 协议可以灵活配置l f b 的拓扑结构，从而实现不同的服务需求。例如，当网络设备要从i p v 4升级到i p v 6 时，f o r c e s 网络设各只需要加载i p v 6 的l f b 就可以完成升级这个目的。2 1 2 f o r c e s 控制接口考虑到c e f e 之间链路连接的复杂性、多样性，用于传送f o r c e s 协议消息的f o r c e s 控制接口被分成两层：协议层p l ( p r o t o c o ll a y e r ) 和传输映射层t m l( t r a n s p o r tm a p p i n gl a y e r ) ，具体结构如图2 - 3 所示。在f o r c e s 控制接口中，t m l底层媒介具有多样性，可以是基于s c t p 协议的，也可以基于t c p u d p ，或者是基于a t m 网络的传输层。在传输过程中，工作流程如下：发送端的p i e , 层将f o 以e s 协议消息传送给t m l ，t m l 将消息传送给接收端的t m l ，接收端的t m l 成功接收消息后，其t m l 将消息传给对应的p l 。t m l 主要负责传输中的组播、可靠性、拥塞控制等问题。9。ce的pl层c e 的t m l 层jl经过t m l 层封装的p j层f o r c e s 控制消息1rf e 的t 地层靶的p l 层，一i。一?一? 一? 张图2 3p l - t m l 层分离结构通过p l 层，c e 发送各种控制命令到f e ，实现对各l f b 的控制管理，具体包括对l f b 的属性进行配置、查询、订阅l f b 的事件等。f e 通过p l 和t m l上报被订阅事件和请求响应到c e ，这些响应主要是c e 的各种配置和查询请求的确认。t m l 存在的必要性在于使得f o r c e s 协议软件独立于运输层协议和传输媒介( 如t c p i p ，a t m 等) ，因而运输层协议和传输媒介的改变不会引起t m l 的显著变化，结构上保证了p l 与实现数据交互的运输层协议和传输媒介之间的低耦合。综上所述，对于c e 件和f e 的p l 通信而言，t m l 是处于一个相当重要、不可或缺的地位。2 2 基于网络编码的传输机制2 2 1 网络编码的理论基础什么是网络编码? 回答这个问题，不妨以通信网络中的一台路由器为例。传统路由器具有路由和转发功能，每个输出链路的信息都是输入链路信息的拷贝。而在允许编码的网络环境中，如图2 4 所示【2 们，具有网络编码能力的路由器还具备操作数据的能力，输出链路的信息可以是各输入链路信息的组合。1 0以jy。”y 一j r e ( y y e ，y e 、)_ _ _ - _ _ _ - _ r -图2 - 4 网络编码：网络节点对输入数据流进行操作图2 5 所示的是一个经典的蝴蝶网络，它有效地表示了网络编码。它是一个组播图，图中的s 表示信源节点，m l ，m 2 ，m 3 ，m 4 表示中间节点，t l ，t 2 表示信宿节点。假设图中的每条链路都是单位容量，如果是传统的组播，如图2 - 5 ( a ) 所示，m 3只能发送一个比特信息给下游链路。当s 发送两个比特信息数据包( 6 j ，6 2 ) 给节点t l和t 2 时，节点m 3 会成为一个瓶颈，m 3 丢弃( 6 ，6 2 ) 之中的其中一个比特，网络的组播容量无法实现。如果采用网络编码，如图2 4 ( b ) 所示，节点m 3 具有编码能力，对数据包( b l , b 2 ) 进行异或操作。m 3 不再是瓶颈节点，不会有比特的丢弃。中间节点一个简单的异或操作就能够实现网络的组播容量。s 弋im 1( a ) 普通网络数据传输( b ) 应用网络编码的网络数据传输图2 5 蝴蝶网络一网络编码举例 3 l j2 2 2 网络编码的数学模型1 、线性组播的两个重要定义设一个有向无环网络图g = 习，v 是网络中的节点集合，e 是网络中的链路集合，节点的数量n - - i r l ，链路p = ，1 ，) ，甜v ，1 ，v 。对于任意的节点，v ，全m 渺卜、m，：|，e 一( v ) 表示链路的输入，矿( v ) 表示链路的输出。对于任意的边e 鄂，其中v - ( e )表示链路e 的尾部，矿0 ) 表示链路p 的头部。若存在一个节点v ，使得e e - ( v ) ，e 矿) ，那么( 巳p - ) 为邻接节点。链路中传输的符号来自有限域f ，称为基础域。为了简单起见，假设整个网络无时延，源节点用j 表示，且其以单位时间的速率产生信息。节点s 为信源节点s e v , 节点t 为信宿节点，丁是信宿节点i - 岛的集合，d = t l ，h 为最小割，也是组播的最大传输速率。定义l ：在一个无环网络中，f 为伽罗华域 7 1 ，为证整数，( ) 维线性网络编码由两部分组成：每个邻接节点对( p ，e 9 的标量乞j 和每条链路的维列向量。= ，e e 。，) 屯o e + ( v ) )( 2 1 )向量& 表示链路e 的全局编码核，构成向量空间f 。的自然域，提供边界条件，也表示u 虚通道e e e ( s ) 。k ，局部编码核用i f ( y ) i i f ( 1 ，) ；矩阵表示：k 屯：。 一n 饨e + 【，( 2 - 2 )全局编码核与局部编码核的关系：假设信源节点发送维列向量信息x ，节点，接收到的符号为x g ( e ) ，e e + ( v ) ，链路e e 一( ，) 为节点1 ，的上游链路，x g ( e ) 表示如下：z g 。= z 乞。= 乞。( z )( 2 3 )# e e v )t e e ( v )在无环网络中，每个节点都有局部编码核，全局编码可以利用在上下游流之间递归调用2 。k e 弋，屯，( eee + ( v ) ) 方程式进行计算。关于线性组播，其定义如下：定义2 ：单信源有线无向网络中，使用u 维线性网络编码( 。维线性编码表示信源传输包含甜数据单元的信息) 。k = s p a n g , e - ( v ) )( 2 - 4 )只要满足以下约束条件，该网络就具有线性网络编码资格，约束条件描述如下：1 ) 对任意非源节点r ，网络最大流m a x f l o w ( d 甜，都有d i m ( t ) = 甜。2 ) 对任意一个非源节点正d i m ( t ) - - r a i n 1 ) ，其9 1 k k ，可由以下两个公式推得：兀i4i = 嘞i e 巧乃= l 七k ：( 甜( 七) ，( 七) ) = ( f ，埘( 2 1 0 )( 2 - 1 1 )3 ) 如果“( 七) = s ，那么五：t ata r ；否则五：兀4 一4 ，可由以下两个公k e q t式推出：q = l ，【2 砌】)q = 1 k k ：v ( 七) = 甜( 七) ( 2 - 1 2 )( 2 - 1 3 )4 ) 岛为信息操作全过程，岛：兀一q ，l ，三，原始信息工= 蟊( x ) 可由以k c w t下公式推得：弼= l s 七k ：p ( 惫) = f ，)( 2 1 4 )g ，：兀专q ，l z l( 2 1 5 )k e w lq 编码处理流程步骤如下：第一步：在编码会话建立之前，对于s 来说x 具有可用性。第二步：在编码会话期间，按时间顺序对x 的值进行k 次数据处理过程，每个数据处理过程是指节点把信息发送给另一个节点的过程。第三步：在第k 次数据处理中，节点甜内根据五进行编码，从以中发一个索引给v 0 0 ，五是指节点“例收到接收到的信息。“内有两种情况，表示如下：1 ) 如果“内鄙，那么五来自于q 。2 ) 如果“内知，那么q k 就涵盖了信息被发送到节点“例之前的所有信息处理过程，压表示如- l q以= n 。珏以( 2 - 1 6 )第四步：乃包含了节点i 到节点，所有的信息处理，因此j 7 表示从节点f到节点，的所有可能索引的数量。第五步：w i 涵盖了信息发送到f ，的所有处理过程，毋是节点t t 的译码函数。令r = 【r ，( ，_ ，) e 】，其中存在s 0 ，刀足够大，那么一个三元组o r , 允g )1 4允许口编码，对于所有的以夕e e , 口编码( 刀，( ，) e ，h 一占) 满足以下不等式：r t l 0 9 2 嘞吗4 8( 2 1 7 )2 3 随机网络编码2 3 1 随机网络编码简介基于组播的随机网络编码是一种分布式随机线性网络编码。网络中的编码节点随机的在伽罗华域中选择输入链路到输出链路的映射，不同的编码节点选取的映射关系是相互独立的。当伽罗华域足够大的时候，随机线性网络编码能够以接近1 0 0 的概率使转移矩阵达到满秩，使得组播网络达到组播容量上限。使用随机线性网络编码方法，信宿只需要知道信源随机过程全部的线性组合关系。对于信源随机过程来说，数据块或包的信息是以带系数的向量形式在网络中传输。数据包每经过任意一个编码节点，该编码节点就会随机的从伽罗华域中选取编码系数，使输入链路的信息向量线性映射到输出链路的信息向量，信息向量在编码节点处得到更新。当网络保持不变时，传输系数的开销会随着数据块长度的增加而减少。但是随机网络编码也存在缺陷，i p 数据包需要存储编码系数，这样会增加额外的控制开销。x 1 ，x 2磊x l图2 - 6 随机线性网络【川图2 - 6 是分布式随机线性网络网络的一个简单例子。在一个组播通信网络中，信源节点s r c 通过不同的传输路径将两个信息x 1 ，x 2 分别组播给两个信宿节点r e v l和r e v 2 。每条链路传送的信息向量都是信源信息x l ，x 2 随机线性组合而成的多项式，多项式的系数是随机选择的，而且保持相互独立。当信宿节点收到组播信息后，根据收到的信息组合，通过高斯消元法进行信息解码。如果线性多项式满秩，则可以成功编码。否则，编码失败。在一个任意的信源独立或线性相关组播网络中，编码需要的编码系数都是从伽罗华域日向 矽中选取，有一些编码系数可以固定。如果固定的编码系数对于网络的连接存在解决方案，那么随机编码网络可行的概率至少是( 1 一d q ) 。，q是符号边界，d 是接收节点的个数，a 是编码链路的个数。而在一个非循环组播网络g ，信源是相互独立或线性相关的，其熵率为y ，链路失败的概率为p 。在满足伽罗华域目前提条件下，假设y 为最小冗余，三为信源到信宿的最长路径，随机线性网络有效的概率至少为：辩y 卜一半) 厶( 1 - ( 1 一半) 厂p 哟h o 和k o e t t e r l 3 4 1 等提出一种矩形网络模型，该网络模型说明采用随机网络编码( 1 ) ，其信宿节点接收并正确解码信源信息的概率比采用随机洪泛( r f ) 的高。假设在一个无时延矩形网格网络中，信源节点发送两个随机过程，采用分布式传输机制，各节点之间没有协作关系或路由状态，这样做的目的是为了使任意节点接收到这两个随机过程的概率最大化。方法一、随机洪泛( 1 强) ：1 源节点s r c 分别沿着横轴的两个输出链路发送一个随机过程蜀，沿着纵轴的两个输出链路发送一个随机过程局。2 当某个节点从一条输入链路收到一个信息后，该节点就把这个信息转发给除这个输入链路的其他三个输出链路。3 当某个节点分别从两个输入链路接收到两个信息，该节点就以相同的概率把一个信息发送到一条输出链路，把另一个信息发送到剩余的另外一条输出链路该方法表明在采用l 强机制的矩形网格网络中，若一个接收节点的坐标为化1 6力，则该接收节点接收到信源信息的最大概率为：( 2 - 1 9 )方法二、随机编码( 1 讯)1 源节点s r c 在沿着横轴的两个输出链路发送一个随机过程，沿着纵轴两个输出链路发送一个随机过程局。2 当某个节点从一条输入链路收到一个信息后，该节点就把这个信息转发给除这个输入链路的其他三个输出链路。3 当某个节点分别从两条输入路径接收到两个信息后，该节点就从伽罗华域中随机的选取两个编码系数，把这两个信息进行随机线性组合得到一个新的信息，然后把这个新的信息发往其他两个输出链路。该方法表明在采用r c 机制的矩形网格网络中，若一个接收节点的坐标为阮，则该接收节点接收到信源信息并正确解码的概率至少为：p r ( 1 一l q ) 2 。 ”2 ( 2 - 2 0 )相关数据显示，对于不同的坐标x 和弘当x 和y 越小，接收节点成功接收信源信息的概率越大，采用随机编码策略的成功接收信源信息的概率大于采用洪泛策略。除此之外，码字表越大，随机编码成功接收信源信息的概率也越大。2 3 2 随机网络编码的性能分析及评价网络中所有的编码系数从伽罗华域f 中随机的、独立的、均匀的选取。只要这个伽罗华域f 足够大，那么转移矩阵就能以高概率满秩，即成功译码【3 5 】。随机网络编码的优势如下：1 提高带宽利用率如图2 7 所示，网络链路总共传送9 比特的信息。如果网络不允许编码，信源s 至少还要发送l 比特信息，信宿t l ，佗，t 3 才能成功接收b ，b 2 ，。如果使用网络编码，如图2 8 ，信源s 就不需要再发送额外的比特信息。综上所述，使用网络编码传输技术，网络带宽利用率提高了1 0 。图2 - 7 不采用网络编码的一个网络拓扑图2 提高吞吐量我们利用数学推论来说明网络编码在提高网络吞吐量方面的优势。假设b = b ，b 2 ，6m ) ，b 为信源发送的比特，设i b i l = 2 ，i = l ，2 ，3 ，当编码不被允许时，b = b i ub j ，l i 输出到通用组播转发l f b 的m e t a d a t a这与文献【1 l q b m e t a d a t a 是相同的，当编码分类l f b 认为该数据包是其它包以后，输出m e t a d a t a 就跟组播数据包经p i m s m 组播路由表查找正确时，其输出组播数据的同时输出的m e t a d a t a 信息一样。m t i d ( m u l t i c a s t t r e ei d ) ：组播树标示符，即为组播包输出端口列表索引号，该m e t a d a t a 信息为p i m s m 产生的主要结果信息，交由通用组播转发l f b ，以进一步查找对应的所有输出接口及决定数据包拷贝的份数。 输出到编码缓存l f b 的m e t a d a t a该m e m d a t a 信息为编码分类l f b 的组要结果信息，交给编码缓存l f b ，以进一步查找对应的输出接口和数据包拷贝的份数。4 、编码分类器l f b 类对编码分类l f b 类的完整定义包括一下几个方面 数据包的输入、输出数据包输入：从p i m s ml f b 输入的数据包，均为i p v 4 组播数据包。数据包输出：输出为i p v 4 组播数据包，输出通道有三种：输出到编码缓存通道，输出到通用组播转发通道和异常输出通道。其中异常输出通道输出到c e 。 操作属性编码分类l f b 操作主要属性为l f b s t a t e ：编码分类l f b 的当前状态，状态为可读写，开启或关闭。 事件无。4 2 3 编码缓存l f b根据f o r c e s 模型及协议，对编码缓存l f b 做如下定义。如图4 6 所示，该l f b 有多个输入，这个输入是从编码分类l f b 从数据通道转发过来的，该l f b 维护一个定时器，在该定时器的时间内，把从编码分类l f b转发过来的数据包缓存，当定时器到时间或缓存区满员时，将数据包从多个输出到随机编码l f b 。i n p u t0 u t p u tlo u t p u t ni n p u t mm e t a d a t at or a n d o mc o d e rl f b图4 - 6 编码缓存l f b 框图l 、通用数据类型只定义一个数据类型：l f b s t a m s v a l u e s与编码分类l f b 的状态定义相同2 、输入输出帧格式与编码分类l f b 的状态定义相同3 、m e t a d a t a该l f b 将输出到随机编码l f b ，m e t a d a t a 信息为o u t p u t p o r t i d ：描述需要被编码的组播包输出到随机编码l f b 的对应的端口号。4 、编码缓存l f b 类 数据包的输入、输出数据包输入：从编码分类l f b 转发过来的i p v 4 组播数据包。数据包输出：编码缓存l f b 输出的数据包为i p v 4 组播数据包。 能力信息s o p p o r t e d p o r t s n u m ：能, 够支持的最多输入和输出端口个数，最多可以支持1 6个输入、输出端口。， 事件无。4 2 4 随机编码l f b根据f o r c e s 模型和协议定义，对随机编码l f b 作以下定义。如图4 7 所示，随机编码l f b 有多个输入，有两个输出：一个是编码后的新的数据包输出，输出到编码包再生l f b ，一个是m e t a d a t a 信息。m e t a d a t a 信息包含对应的输出接口列表，可以计算出拷贝的数据包份数，输出到通用组播转发l f b ，最后输出到s c h e d u l e q ml f b i n p u o i l t p u ti n p u t mm e t a d a t ap