基于网络编码的应用层组波路由优化方案研究

1、摘 要随着通信网络技术的发展和多媒体技术的广泛运用，网络资源紧张和分配不合理的问题越来越突出。在P组播无法被全网范围内部署利用的情况下，基于端系统的应用层组播应运而生。与传统路由节点只能对数据进行复制和转发不同，应用层组播中的端系统可以对接收到的数据进行运算操作(如线性运算)。利用网络编码，端系统对收到的数据进行组合编码，从而有效地利用网络带宽，增加网络容量。关键词：应用层组播、网络编码、分布式算法、最大效用、凸优化AbstractWith the development of communication network and multimedia technology,the requir

2、ement of supporting large scale data distribution such as video streaming has come into being and soon gathers a great research interestWhile currently the limitation of network resources as well as the inefficient network resource utilization renders a great challenge towards its further developmen

3、tWith the consideration of failing to implement IP multicast within a wide range of network,the end system based application layer multicast(ALM) has been proposedBesides equipped with a11 the function of traditional routing node such as data forwarding,data duplicating，the mighty end system in ALM

4、Can also carry out some operation(eg1inear combination)upon the traffic receivedSpecifically, we employ network coding，a brand new multicast technology in some end systems with the purpose of better utilizing bandwidth resources and improving network throughputKeywords：Application level Multicast，Ne

5、twork Coding,DistributedAlgorithms，Max utility,Convex optimize目 录第一章 绪论1第一节 课题来源1第二节 课题研究的目的和意义1第三节 论文的主要研究内容2第二章 网络编码3第一节 网络编码原理3第二节 网络编码的优点5第三节 络编码的应用7第三章 一种基于网络编码的应用层组播路由算法9第一节 应用层组播9第二节 基于网络编码的应用层组播路由算法11第三节 实验仿真和结果分析17第四章 应用层网络编码的网络传输最优化23第一节 最优化技术：凸优化方法23第二节 基于网络编码的应用层组播最优化24第三节 基于网络编码的应用层组播净效

6、用最优化24第四节 仿真结果与分析28结论33致 谢34参考文献35第一章 绪论第一节 课题来源本课题来源于国家高技术研究发展计划(863计划)(2006AA012322)：视频媒体基于信息可重用的分布式网络化编码及传输。第二节 课题研究的目的和意义随着宽带多媒体网络的不断发展，各种宽带网络应用层出不穷，例如：数字电视、视频会议、数据和资料分发、网络音频应用、网络视频应用、多媒体远程教育等。这些宽带多媒体应用都对现有宽带多媒体网络的承载能力提出了挑战。采用单播技术构建的传统网络已经无法满足新兴宽带网络应用在带宽和网络服务质量方面的要求，随之而来的是网络延时增加、数据丢失等等问题。于是，组播通信

7、方式被提出，旨在改善现有网络中存在的一些网络资源紧张问题，提高网络的服务质量QoS11。组播是现在网络研究中的一个重要课题。组播通信的基本出发点是：在同时存在多个接收者时，通过合并重复信息的传输来达到减少带宽浪费和降低服务器处理负担的目的。其发展之一的IP组播模型是对Internct基本的“单播、尽力发送模型的一个重要扩充，它把组播的主要功能都放在路由器上实现。而由于口组播在传输技术和管理上存在严重的问题，主要是口组播需要路由器维护组播通信的状态信息，增加了网络的复杂性并严重约束网络组播的扩展，其次网络的可靠性、拥塞控制、流量控制、安全性无法得到保障，另外由于P地址空间有限，无法满足众多应用的

8、需求，因此目前IP组播没有在Internet中得到普遍采用21。研究人员反思口层组播体系存在的问题后，在2000年提出了应用层组播。它的主要思想是：保持Intemet原有的模型，尽量不改变原来网络的体系结构，而主要通过增加端系统的功能来实现组播的功能。由于对网络本身的改变很少，应用层组播具有很好的灵活性。随着Peel'-mPeer Network和OverlayNetwork等技术的提出和发展对应用层组播的研究也有很大的促进作用。但是，上海大学硕士学位论文端系统的稳定性一般不如专用网络设备，并且应用层组播在带宽利用效率及网络延迟方面也无法和P组播相比。另外，应用层组播中的系统框架和很多

9、细节技术也还在研究当中。这些问题的存在为应用层组播的研究提供了广阔的空间。网络编码的思想在2000年由RAhlswede首次提出，我们发现网络编码可以大大提高网络的传输能力和传输可靠，其理论创新具有普遍意义，应用前景十分广阔。考虑到应用层组播是基于应用层端系统之上的，端系统比传统的IP路由器功能更为强大，可以在端系统上引入网络编码，将接受到的信息进行解码和编码可以提高网络传输的效率。第三节 论文的主要研究内容本论文是作者攻读硕士学位期间承担课题的工作总结。第一章中阐述了课题来源、研究目的和意义以及国内外本课题研究的现状。第二章阐述了课题研究的基本理论网络编码的概念和基本原理，包括如何进行编码和

10、解码，以及网络编码的优点和使用范围。第三章在对比其它传统组播路由算法的基础上，结合网络编码提出了新的基于网络编码的分布式应用层组播路由算法。第四章中，考虑到第三章中提出启发式算法本身作为NPcomplete问题不能得到网络最优解的局限性，从凸优化角度分布式考虑如何使得整个网络的效用最大及网络传输开销最小，利用拉格朗日对偶和次梯度算法来求解，使得网络源节点效用最大和链路中流量分配合理。最后第五章总结了全文以及硕士期间的研究工作，并以后工作提出了设想。35第二章 网络编码第一节 网络编码原理在现有的通信网络中，信息传输都是由源节点经过中间节点，以存储转发的方式传送到目的节点的。除了数据复制以外，一

11、般来说在网络的中间节点并不需要做任何数据处理。在许多实际应用中，人们为了信息分析、信息安全以及交换的目的，总是要在中间节点进行某种形式的数据处理。但是人们普遍认为，中间节点所进行的数据处理对数据传输过程本身并不会带来任何好处。2000年，RAhlswcde首次提出了对信息进行网络编码的思想。所谓网络编码，就是指节点对输入的多路信息流进行代数组合运算，生成一路或多路新的输出信息流。在传统的网络中，大量存在的中间节点只能对接收到的数据进行路由、复制和转发，这对于有限的网络资源是严重浪费。由于网络中被传递的信息本质上就是连续的比特流，是一系列抽象的代数符号，因此信息除了可以被转发和复制之外，应该还可

12、以进行代数运算，网络编码技术打破了中间节点不对数据处理的限制。它允许中间节点对接收到的信息进行编码，并将接收到的多个数据包按照某种特定算法重新组合再发送出去。网络编码是在有限域中进行的，主要分为线性和非线性两种方式。但相比非线性编码，线性网络编码的编码和解码都相对简单，这里以目前被普遍采用的随机线性网络编码为例，来说明网络编码的原理。假定流入节点的每个数据包的包长度均为比特(较短的数据包位数不够，在末尾添零补齐)，如果把这工比特中每连续的s比特映射为有限域聪中的一个元素，那么就可以把这个数据包看成一个包含个元素的向量。于是，从代数学的角度来看，数据包之间的编码运算就等同于一系列向量的线性组合，

13、而线性组合所用到的加法和乘法遵循有限域的运算法则。这里需要指出的是，选择有限域是缘于它的两条性质，其一是有限域中的元素个数是有限的，其二是有限域中的元素对于该有限域所定义的两种运算(an法和乘法)是封闭的。这不仅极大增强了线性组合的灵活性，同时保证了运算所得的结果不会占据额外的存储空间，即新组合的包的长度和原始数据包长度一致。一、编码过程假设一个或多个原始信源所发送的信息由疗个数据包M1，M组成，中间节点可以对流入其中的n个数据包进行网络编码，生成1个新的数据包x=：。g，M。其中毋就是有限域巧中的元素，它由节点随机产生。由于编码运算在有限域中进行，因而x所占据的存储空间大小与膨7所占大小完全

14、相同。组合运算的系数g=(gl，gn)称为编码向量，石称为信息向量。编码完成后，节点将编码向量和信息向量(g'x)同时转发出去，用于目的节点对信息向量进行解码，恢复原始信源。网络编码可以对编码的数据包重复进行编码，换言之，节点可以对收到的已编码的信息向量进行再次编码。假定节点收到了m个信息向量它对聊个信息向量再次编码，生成新的信息向量。这里代表与相对应的编码向量，二者满足 二、解码过程在线性编码下，运用乘法和加法运算，使得从节点发送出来的数据为一系列线性组合，便于解码。当一个节点收到ra个编码后的数据包后，为了恢复出万个原始数据包，只需求解以下方程组： 这是一个含有刀个未知数，m个方程

15、的线性方程组。我们知道，只有当线性方程组的方程个数大于或等于未知数个数(即mn)时线性方程组才有唯一解。当然m刀并不是充分条件，因为方程之间有可能出现线性相关的现象，即编码向量之间线性相关。虽然编码向量之间的线性相关程度取决于所选取的有限域的大小，但实验证明即使选择比较小的有限域，比如S=8的有限域，编码向量之间出现线性相关的概率也是非常小的。因此，节点的解码过程是非常简单的，节点不需要接收指定内容的数据包，只要接收到足够数量的线性无关的编码数据包，就可以成功恢复原始数据。第二节 网络编码的优点一、最大流最小割原理在分析网络编码技术及其应用之前，首先来介绍图论的相关背景知识。对于包含一个源节点

16、s和个汇节点，V代表顶点(Vcrticc)集合，E代表有向边(Edge)集合，用嘞表示边(f，j)E的容量, ，F表示流经边(的流量，显然对所有，。而且，对有向图G上任意节点即流入中间节点f的数据总量等于流出节点f的数据总量。根据最大流最小割定理：任何带发送节点和接收节点的网络中都存在最大流和最小割，并且最大流的流值等于最小割的容量。如果用max表示从源点s到汇点f，的最大流值。二、网络编码的优势在传统的组播通信中，网络中的节点只能存储转发所收的数据包，当信源s到不同信宿厶之间的最大流经过的路径可能在G的某些链路上形成交叉共享链路，进而影响共享链路之间节点的数据传输率，因此采用传统的存储转发模

17、式一般是不可能达到最大流最小割定理规定的组播信息容量上限的。2003年，RLi证明了在单个源节点向多个目的节点发送数据的情况下，应用线性网络编码理论，一定能够达到网络组播容量的上限。除了能使得网络传输达到组播容量的上限，网络编码的应用还可以为系统带来以下几方面的益处：1提高组播速率，实现组播最大容量。图21(a)给出了网络拓扑结构及不同链路的容量，其中S是信源，墨、恐和恐是三个不同的信宿。显然，从S到RO=l，2，3)的最大流均为4，所以将信息从S同时发送给羁、岛和马时的最大组播容量也是4。然而从图21(b)可以看出，存储转发模式下的单组播最大速率仅为2，图21(c)显示在部分节点上进行网络编

18、码能够提高组播速率至4，实现组播最大容量。（a）网络拓补和链接容量（b）传统传输方式（c）网络编码实现最大流（d）负载平衡图2.1存储转发方式与网络编码方式的比较三、节约系统带宽，并有利于负载平衡。采用图2 的存储转发方式，同时传输2bR信息占有的链路带宽总量为10；而采用图2 1(d)的网络编码方式，同时传输2bit信息所占有的链路带宽总量为9。相比之下，后者可以节约10的系统带宽。而且，前者集中使用了系统中的5条链路，闲置了另外4条链路，导致节点上的带宽资源占用情况非常不平衡；而后者均衡地利用了系统中的全部9条链路，很好地平衡了网络负载。四、提高系统的鲁棒性和白适应性。如图22所示，图中每

19、个节点都存储了一组固定长度的数据。图22(a)中的每个节点均以原始格式对数据进行存储，图22中的每个节点均以网络编码后的格式对数据进行存储，可以看出，图2.2(a)中只能容忍节点2或3中一个失效或离开，否则系统中的其它节点就不能剩余节点中完整地获取数据a、b、c、d；而圈22(b)中允许任一节点失效或离开，其它节点都能够自适应地做出调整，重新路由，从剩余的三个节点完整地获取数据a、b、“d。图2.2节点失效或离开的影响失效第三节 络编码的应用网络编码将原先分立于物理层和网络层的两个核心概念编码和路由有机的融为一体，彻底改变了路由器只能对信息进行存储转发的传统模式，建立起一种全新的网络体系结构及

20、信息编码和传输模式。网络编码代表了一种协同工作的理念，这使得它的应用不仅局限于改进组播增加网络容量，与其它技术相结合已经应用于分布式内容存储与分发应用层组播无线传感器网络数据采集网络管理信息安全等众多领域。1)分布式内容存储与分发。传统的分布式内容分发或P2P对等通信时，Peer之间传送的是未编码的原始数据块(block)，诸如Peer节点的搜索定位方法、资源分发与调度算法优化、网络负载平衡以及数据分发路由设计等问题都是目前P2P内容分发所面临的难题。而在Peer之间传输经过网络编码的数据块能够有效解决甚至避免这些问题。2)应用层组播。P2P技术与覆盖网络(overlay network)的发

21、展，将组播功能从P层扩展到了应用层，在P2P应用层组播系统中，Peer节点对流经的数据除了进行存储转发外，如果还可以进行额外的网络编码处理，将可以在很大程度上改善应用层组播性能，提高覆盖网络数据吞吐能力。3)无线传感器网络数据获取。在无线传感器网络中，传感器节点的数据存储能力十分有限，如何将这些节点采集的信息在最小代价、最小能耗、最大容量等约束下发送给存储节点是当前网络编码在无线通信领域的一个新课题。4)网络管理。对于链路被截断等物理故障，传统的解决办法是启用备份链路进行重新路由，而对于采用网络编码的节点，改变编码规则就可以改变其传递给其它节点的信息内容，这同样起到了重新路由的作用，而且这种网

22、络管理方式的开销非常小。5)信息安全。攻击者恶意篡改网络上传输的数据内容将直接影响接收端的信息接收，这是目前计算机通信网的一个潜在隐患。采用随机网络编码技术，攻击者对接收端收到的其它编码数据无法进行预知和控制，数据篡改的影响可以降至最低。第三章 一种基于网络编码的应用层组播路由算法第一节 应用层组播一、应用层组播的提出互联网上的大规模媒体存储与发布普遍是基于传统的客户机服务器(CS)系统架构，这种集中式的分发模型容易造成中央服务器的过量负载，直接导致网络吞吐量的下降，并且一旦中央服务器出现故障将直接导致整个传输体系瘫痪。随着视频点播、网络电视、远程教育等多媒体服务飞速发展，中央服务器的带宽瓶颈

23、问题日益凸显，以致集中式的分发模型逐步向基于P2P覆盖网络(overlay network)架构的分布式结构过渡。IP层组播是面向组通信应用的，被认为是大规模数据分发的最佳方法。然而口组播增加了网络层的复杂性，而且需要对现有网络的底层设备进行巨大改动，因此至今口层组播仍然无法广泛部署。叠加网(Overlay Networks)是一个位于一个或多个己知网络上的独立的虚拟网络。它的主要优点在于它的架构，它不需要改变底层网络的结构，可以快速部署所需的网络功能。如果在叠加网的基础上实现组播，可以把组播实现提高到应用层。端系统实现组播业务的思想是将组播作为一种叠加的业务，实现为应用层的服务，由此构成了应

24、用层组播(application layer multicast)应用层组播是在叠加在m层之上的用于实现组播业务逻辑的功能性网络，应用层组播网络中的节点是由组播中的成员主机构成的，并由它们完成数据路由、复制和转发功能。因为不再依靠网络层路由器来实现，所以不需要任何网络底层架构的改变，只需改变端系统，便于实现和推广。图31对m组播和应用层组播的数据传输方式进行了比较：图31 m组播和应用层组播的数据传输方式比较图31中假设A、B、C、D为四个端系统主机，R1，R2为路由器，箭头方向代表数据包的发送方向。图31(a)为IP组播，A为网络中的源节点，数据包从A发到R1，再由R1转发给B和R2，R2再

25、将收到的数据包转发给C和D。图31(b)为应用层组播，A发送两份相同的数据包分别给B和C，再由C复制一份给D。从图31(b)可以看到应用层组播有以下一些优点：1所有数据包都是通过单播传输的，无需路由器的支持，节点只需安装应用层软件即可，操作方便、易于广泛部署；2.底层物理网络无需保存状态信息，而节点仅需要保存该组少量其它邻近成员的信息，可扩展性好；3利用单播，可以有效地采取适合流媒体应用特点的错误恢复、流量控制、拥塞控制等策略，提供端到端的服务质量保证；4不但能跨越空间维，还能跨越时间维进行数据传输，可牺牲同步性能来获得更好的服务质量保证；5地址可采用层次结构，可有效地扩大地址空间。但从图31

26、中可以看出应用层组播存在的一些固有问题，如效率不高，多条覆盖网络上的逻辑链路可能经过物理网络的同一链路；延迟大，两个节点之间的通讯可能要通过其它节点：同步性能差，所有节点之间很难同步接收数据；可能跨越多个节点，丢包概率增大。应用层组播的效率比P组播的效率要低，因为不可避免的会有组播路径重复的经过同一条底层链路，也就必然带来冗余的流量，例如在图31(b)中(A，R1)和(R2，C)这两条链路上有两个相同的数据包重复经过同一条底层链路，而图31(a)的口组播则只有一次。另外，两个端系统之间的通信，可能要通过中间其他端系统的转发来实现，这也不可避免的造成两个通信节点之间延时的增加。二 应用层组播路由

27、协议应用层组播协议通常都按照两个拓扑结构组织组成员，一个是控制拓扑，一个是数据拓扑，控制拓扑的组成员周期性地交互刷新消息以相互标识身份并从节点失效中恢复。而数据拓扑通常是控制拓扑的子集，它用于标识组播转发时使用的数据路径。数据拓扑作为应用层组播协议的重要组成部分，即组播中文件数据的如何路由是本文讨论的重点。一般来说，组播组用于标识组播转发时用的数据路径通常是一棵组播树。其中在组播中最基本两种数据转发方式是：建立最短路径树和最小生成树，常见的路由算法为：BellmanFord最短路径树算法、Dijstra最短路径树算法和Prim最小生成树算法。最短路径树是从源节点到所有接收节点的每条路径上链路权

28、值之和最小的组播树。如果所有的链路的权值都表1，则为最小跳树。如果权值代表链路延时，则为最小时延树。最小生成树是指覆盖所有组成员且权值最小的组播树。此外，还有基于Steiner树的问题致力于使组播树的总代价最小，这已经证明了是图论中一个NPcomplete问题。如果组播树包含了树中所有节点，Stoner树问题转化为最小生成树问题。一般通过启发式算法求解，典型的启发式算法有：MST、RS、KMB31，321。Steiner树问题可以扩展到包括其它的链路约束。例如延时、延时抖动或者它们的组合。通常这些问题是NPComplete的，所以也需要采用启发式算法解决。第二节 基于网络编码的应用层组播路由算

29、法在日常生活中，我们经常要使用到比较大规模的通信网络，我们都希望通信网络能为我们提供更为安全、快速的网络服务。于是我们提出了实现在已有通信网络中达到最大数据流的目标。由前一章可知，网络编码可以实现网络的最大流传输。网络信息理论的研究指出：在组播通信中，每个接收节点可以以网络拓扑中信源发送点与信宿接收点之间的最大流容量进行信息传递。然而，从信源到不同信宿之间的最大流经过的传输路径可能在网络拓扑的链路上形成交叉共享链路，因此采用传统的存储转发模式即P组播的方式，无法达到最大流最小割的理论上限。网络编码，作为一种协同工作的理念，将原先分立于物理层和网络层的两个核心概念编码和路由有机地融为一体，通过在

30、中间节点中进行传递信息的编码组合运算，建立起一种异于传统存储转发的全新网络信息传输模式。应用层组播是以端系统为基础的逻辑覆盖网(overlay network)，不同与以往m层组播中的路由器节点，端系统可以提供更为强大的功能，如能够对数据进行编码组合运算，这为网络编码在覆盖网络上的应用提供了技术支撑。本节的主要内容就是建立一种基于网络编码的启发式应用层组播路由算法，目的在于利用网络编码技术在分布式网络中建立数据分发拓扑使得网络传输容量趋于组播容量上限。在分布式拓扑中运用随机线性网络编码技术，即中间节点对发往不同目的节点的组播数据进行编码组合后再转发，以避开数据流对链路的竞争冲突，提高组播通信的

31、吞吐量。一、冗余路径考虑到网络编码在提高网络的吞吐量方面的优点，为了进一步改善应用层组播的性能，从而我们引入了网络编码技术。但是网络编码不是万能的，不是所有的网络组播拓扑都能使用。应用层组播要结合网络编码技术，在路由选择方面必须满足两个条件：(1)网络中存在冗余的路径；(2)具有相同目的节点的路径之间不能存在共用的路径。图3.2 不相交的冗余路径(对于Tl而言，SU1T1和S-U2U3-U4-T1分别是ST1的两路不相交路径)图32我们可以看到对于网络中的目的节点T1存在两条不相交的路径通向源节点S，因此目的节点能同时收到多路独立数据流。所谓不相交路径是指对同目的节点而言的不同路径之间不存在共

32、用的链路。不相交性保证了对于发送至同一个目的节点的不同路径的数据之间不会存在时间上的竞争，它们之间是线性无关的。此时，对于不同目的节点的路径之间必然存在链路的公用问题而产生的瓶颈链路，网络编码的引入可以很好的解决瓶颈链路的问题。图32中，链路m3，U4)就是目的节点T1和T2之间的瓶颈链路，在节点U3进行网络编码就可以实现网络的最大流传输，达到网络的最大容量2。(假设定义网络中链路的带宽均为l，由最大流最小割定理可以算的图32所示网络结构的最大流为2)。这里，多条不相交的数据传输路径的存在使得以往组播进行数据通信的组播树演变成组播图，即由多棵组播树的叠加而成。二、一种基于网络编码的应用层组播路

33、由算法和分析为了使应用层多播的整体性能尽可能逼近口多播性能，在本节中，我们设计了一种基于网络编码的应用层组播路由算法，它是面向异构化接入不同类型客户机的应用层覆盖网络组播路由算法，并且充分考虑因网络编码的构造采用多路径方法。本节提出的算法作为启发式算法的一种，适合运用在P2P等分布式网络中，相对于传送未编码原始数据块的传统分布式内容分发及P2P对等通信，通过在由采集节点、存储节点、客户机所构造的覆盖网中Peer之间传输经过网络编码的数据分组，可以有效提高覆盖网络数据吞吐能力。这里建立组播拓扑图是以在源节点和目的节点之间建立两条传输路径为例展开说明，并且两条路径在建立过程中分别遵循最大接入带宽和

34、最小传输时延原则。两条传输路径的组播拓扑图是按以下步骤完成的：(图33为算法流程图)步骤1：目的节点申请加入组播组，首先从与其邻接的节点获取相应的链路状态信息；步骤2：根据链路的当前状态，在建立第一条数据分发路径时，选择能够提供最大接入带宽的邻接节点作为其父节点；步骤3：所选定的父节点如果是组播图中的源节点，则执行步骤4，否则继续执行步骤2，直至完整建立好一条通往源节点的传输路径；步骤4：目的节点和源节点之间的传输路径建立完成后，优化更新新加入组播图的所有路径的链路状态，包括衰减链路成本参数和链路延时参数，使得链路为更多的目的节点所共用：步骤5：根据链路的状态，为同一目的节点建立第二条数据分发

35、路径，选择链路不在第一条路径上，并且能够使传输时延达到最小的邻接节点作为其父节点；步骤6：所选定的父节点如果是组播图中的源节点，则执行步骤7，否则继续执行步骤5，直至完整建立好一条通往源节点的传输路径；步骤7：第二条传输路径建立完成后，优化更新新加入组播图的所有路径的链路状态，包括衰减链路成本参数和链路延时参数，使得链路为更多的目的节点所共用。图3.3（a）第一次寻路算法流程图图3.3（b）第二场寻路算法流程图我们以图34(a)所示拓扑为例来说明在具体网络拓扑给定下如何为每一个目的节点独立地建立两条与S通信的数据传输链路。图34(a)表示的是数据分组在源节点处被采集，初始化时，组播拓扑图中只有

36、源节点，其他目的节点并未加入组播组。当目的节点申请加入组播组，则按照图33流程的7个步骤为其建立两条互不相交的路径。如图34(b)所示的两条路径，其中UIO是申请加入的目的节点。目的节点除了作为数据接收者，同样可以作为中间节点完成对数据的存贮、处理和转发功能。因此，对于新申请加入的目的节点，它既可以通过共用组播图中的其它目的节点，也可以通过接入与其邻接的中间节点来加入组播拓扑图。图34(c)所示的就是目的节点Ull通过共用目的节点UIO的路径建立一条传输路径，通过接入中间节点U6建立另一条路径。图34(d)给出了目的节点U9和UIO的两条路径，两条细线表示的路径是到目的节点U9，两条粗线表示的

37、是到目的节点UIO。对于不同的目的节点，存在瓶颈链路(S，U1)、(u6，UIO)，只需在节点S和节点U6处进行网络编码即可解决数据碰撞的问题。图3.4 具体图例说明第三节 实验仿真和结果分析考虑到DDSP(目的驱动的最短路径树算法)361作为一种基本的目的驱动型组播路由树算法，这里选它是被用来做算法比较。我们先用图33的算法生成的基于网络编码的两条路径组播图和DDSP生成的最短路径树进行性能比较来考察这里提出的路由算法的对网络端到端吞吐量和网络延时影响。首先假设网络中节点数目发生变化，图35(a)和图35(b)给出了两者间网络带宽和平均延时方面的比较。从图中可以明显得到，加入了网络编码的具有

38、冗余度的组播图可以有效地提高网络的吞吐量，同时的网络延时增加量却不大。考虑到网络带宽的有效增加，新增加的延时可以忽略。图3.5（a）网络端到端吞吐量图3-5（b）网络端到端延时随网络中节点数目变化另一方面，假设在固定的网络规模中，目的节点的数目发生改变，两者间的网络吞吐量和平均延时的比较于图36(a)和图360)给出。加入了网络编码的具有冗余度的组播图同样也获得了较好的网络带宽，表现出了其优越性。图3.6网络平均带宽带随网络中目的节点数目变化图3-6（b）网络端到网络延时随目的节点数目变化我们提出的路由算法是希望建立多条传输路径来使得网络的传输流量逼近图论中的网络最大流。然而在建立多条传输路径

39、后，随之而来的网络延时问题将会被扩大，下面的仿真给出了目的节点在尽可能多建立到源节点的路径情况下形成的组播图与只建立两条路传输路径(即冗余度为2)的组播图以及单路径组播树之间的性能比较。考虑到每一个目的节点的实际接受数据的处理能力，我们设置网络中目的节点入度最大值为5。下面分别比较有单路径树，2冗余路径组播图和多路径图的性能，还主要是网络端到端吞吐量和网络延时：图3-7（a）网络平均宽带随网络中节点数目变化图3-7（b）网络端到端延时随网络中节点数目变化图37(a)和图37(b)主要是通过改变网络的规模来比较路径数量不同对网络性能的影响。假设网络的目的节点为10，在不同的网络规模中，源节点向各

40、个目的节点进行数据传输，通过图37(a)可以发现通过建立多条路径的方法，网络的端到端的流量大大提高，而网络的延时相比之下也有一定提高(图370)所示)。在传输大量数据的时候，每一个目的节点使用多路径算法找出能逼近最大流的多条路径同时进行传输，结合网络编码技术使得每一个目的节点可以独立享用整个网络资源，从而大大提高了网络的吞吐量。与此同时，对于每一个目的节点而言，其网络延时则是全部路经延时的最大值，而通过仿真可以看到，对于多条路径带来的延时增加相对与网络流量的成倍增加是较小的。图3-8（a）网络平均宽带随网络中目的节点数目变化图3-8(b)网络端到端延时随目的节点数目变化同样，考察在相同的网络拓

41、扑规模下，目的节点加入组播所占比例不一样对与网络性能的影响。假设在网络规模为100个节点的条件下，分区取10个，20个，70个目的节点比较三种方法的性能。从图38(a)和图38(b)，同样可以发现多路径的方式在增加少量延时的代价下，大大提高了整个网络的数据流量，从而提高了网络服务质量，增加了网络带宽。第四章 应用层网络编码的网络传输最优化第一节 最优化技术：凸优化方法一、凸优化问题首先给出凸优化问题的定义，考虑下面的最小化问题, 由于线性函数可以看做是特殊的凸函数，这样，优化问题(41)就是在凸集上求凸函数的最小点，这类问题被称为凸优化问题。另外，如果优化目标是求凹函数的最大值，并且同样满足约

42、束条件都是凸集，这样的问题同样也是凸优化问题。凸优化问题是非线性优化中非常重要的一种类型，它对于实际优化问题的求解有着非常重要的作用，受到了广泛关注。这是由于凸函数的极值点自身具有良好的性质，即凸函数在其定义域上的任一极点都是其在定义域上的全局最优点，且极值点的集合也是凸集。因此如果凸优化问题的目标函数是一个严格凸函数，且存在极小点，那么它的极小点就是最小点，并且这个点是唯一的。二 、格朗日对偶法拉格朗日对偶法是凸优化算法中一种被广泛采用的方法。首先考察一个一般优化问题(4-2)：我们将问题(42)称为原始问题，将满足所有约束条件的解石称为原始变量，并且假设p+是优化问题(42)的全局最小值。

43、于是，引入对偶变量允R”和yR7释放不等式约束和等式约束，可以得到下面的拉格朗日函数：拉格朗日乘子五和匕被称为对偶变量。这样，我们可以得到原始问题(42)的对偶函数(44)-假设P是优化Ih-J题(42)的最优值，对于任何名0和I，可以得到：对偶函数g(A，y)是一个凸函数，可以看作是关于变量名和y的极小值函数。可以通过求解对偶函数的方法来求解原始函数。第二节 基于网络编码的应用层组播最优化网络编码的采用可以使得网络以最大流方式进行数据传输，网络中的节点的功能也得到扩大。但是由于网络中节点之间存在的差异，以及分布式网络中多个数据源节点的存在使得网络链路速率的分配和网络传输成本之间的矛盾越来越明

44、显。第三章中讨论分析了一种启发式路由算法，通过建立多条数据传输通道，利用网络的冗余性结合网络编码技术来提高网络端到端的吞吐量，主要是解决数据路由拓扑的建立问题，而源节点是以固定单一速率不间断发送数据块。我们可以发现第三章并没有考虑到多个源节点同时存在，并且网络各个节点之间可能存在的差异性。假设网络中源节点在向多个接受能力不同的目的节点提供数据服务的时候，网络中的最大流根据网络流理论可知是网络中各目的节点最大流的最小值。当源节点以最小的最大流进行数据传输的话，势必很多目的节点的资源会被浪费。如何合理分配多个源节点发送速率以及每条链路上的具体流量是本节讨论的重点。第三节 基于网络编码的应用层组播净

45、效用最优化在提高网络端到端吞吐量时，为了克服应用层组播中的带宽瓶颈问题，我们将网络编码技术引入到组播通信组里，在瓶颈链路使用网络编码解决数据碰撞问题，从而提出了第三章的应用层组播路由算法。本节在此基础上考虑如何网络优化，即在网络容量的约束下确定各源节点的发送速率和每条链路上的流量大小，使得整个网络的源节点效用最大而流量代价达到最优。一、最优化问题阐述在进行信息流组播传输时，我们的目标是希望最大化每一个组播组源节点的效用，但同时要以合理的速率传输尽可能多的信息。所谓合理即是要考虑整个网络中所有目的节点的接收能力，并且整个网络的传输代价要尽可能的小。对于网络中的任一组播组m，这里用硝表示在组播组m

46、中，链路(f，j)上发送至目的节点t的信息流速率。于是，我们得到下面的最优化目标及其约束条件problem(4.9)为：我们的目标就是要最大化网络源节点的效用同时最小整个网络的传输代价。网络流平衡约束条件和链路带宽容量约束条件分别由式(492)和式(49-4)来表示。约束条件(493)表示，对于任一条链路O，力上流向任一目的节点的信息流应该小于该条链路实际流量，这是由于(f，jf)上可能被多个组播组和目的节点所共用。二、解决方案对上面提出来的优化目标，我们希望能寻找分布式的算法从而可以应用于大规模分布式网络中。考虑到这里假设的代价函数是凸的且连续递增的，对应的每一条链路单位流量通过产生的代价，

47、同时也为一个凹函数。对于一个凸的目标函数在一个线性约束集下，根据凸函数最大化问题我们可以知道该最优化问题存在唯一的最优解。为了寻找一个分布式的算法来求解，首先考虑上述问题的对偶，并释放流平衡约束和链路容量约束，于是上式的拉格朗日对偶函数可表示为：负数也是凹函数，它们的线性组合亦为凹函数)上式存在唯一的最优解，则对应于变量宝和声、以及拉格朗日乘子多和互应该满足条件：Problem(4-11)为Problem(4-9)在加入网络编码后的变形，Problem(4-11)1拘对偶问题Dual：利用分布式的次梯度算法来求解我们优化问题，可以知道，使用迭代算法求解非线性最优化问题的关键在于，如何构造每一次

48、的搜索方向和确定适当的步长。我们可以利用primaldual算法求解优化问题Problem(411). 我们假设在网络节点和链路上均设置相应的processor。对于node processor而言，在其中记录每次循环迭代值。图4-1算法流程图在分布式网络中，我们假设的节点和链路processor则是按照以下方式对于接收的数据进行处理和更新的：从上面的算法，我们可以看出利用次梯度迭代算法对我们的目标函数求解，是个分布式的，不需要全局信息，能很好的使用与大型网络，并且由于源节点可以提供可伸缩的数据流速率，可以应用于大规模异构网络中。如果在这里我们加入了网络编码，又可以在一定程度上提高网络的吞吐量。第四节 仿真结果与分析我们以图42所示的网络结构作为仿真模型，其中S1S3为网络中的三个源节点，T1T2为目的节点，N1-N4为中间节点。对于网络的任意两节点间的链路都有单位流量成本和链路容量两个网络参数(前面一个参数为单位代价，后面一个参数为为链路容量)。可以将图42所示的网络拓扑视为图43中的三个组播组，每一个组播中有一个源节点以及若干中间节点和目的节点