（通信与信息系统专业论文）基于网络编码的最小代价组播路由研究.pdf

摘要 摘要 随着i n t e m e t 技术的迅猛发展和人们对新奇事务的不断追求，网络承载数据的 压力越来越来大。现有网络资源在面对诸如音视频直播、点播、大文件下载等带 宽消耗“大户 时显得日益紧迫。组播技术自从上世纪八十年代产生以来，一直 是网络研究的热点。经过二十多年的发展，组播技术得到不断完善。现今很多网 络设备都支持组播协议。然而另一方面，尽管音视频、大文件下载等网络服务符 合组播技术的支持范围，但是现今真正使用组播技术进行数据传输的网络服务寥 寥无几。形成这一局面的原因有很多，但作为组播基础的组播路由是主要原因之 一。很多学者和科研机构都致力于寻找简单、高效、健壮的组播路由求解方法， 但一直未能完全解决的。 2 0 0 0 年网络编码技术的提出给组播技术带来了新的希望。通过使网络拓扑中 的节点不仅拥有存储、转发、复制数据的能力而且还能对数据编解码，提高了组 播的带宽利用率。对于组播路由而言，网络编码技术使组播路由中原本在不同组 播树重合边上存在的链路带宽竞争不再存在，使组播能够以更小的代价完成数据 传输。本文主要研究网络编码在最小代价组播路由方面的作用，通过分析网络编 码技术针对最小代价组播路由的实质，提出了利用局部优化方法求解全局的最小 代价组播路由的方法。 本文首先对网络编码技术、最小代价组播以及现今基于网络编码技术求解最小 代价组播路由的研究状况作了简要介绍。然后分析了网络编码技术给包括最小代 价组播在内的组播网络优化带来的实质性变化。接着描述了网络编码环境下组播 网络优化的现有方案。针对两个代表性方案和已成功申请的专利进行详细阐述和 分析。指出现有方案存在的不足，并提出了改进思想。在本文的第四章，正式提 出了利用局部优化求解全局最小代价组播路由的方法。本文提出的方法不仅拥有 现有基于网络编码技术的方法在带宽利用率上的优势和可以分布、非同步地实现 以外，由于本文提出的方法是建立在局部优化的基础之上，因此比起现有利的全 局方法在对网络动态变化的健壮性、对节点加入的灵活性以及计算的复杂度等方 面都有较大优势。在第五章，针对论文提出的方法、传统组播和网络编码的全局 方法在v c + + 平台上作了仿真。通过仿真结果可以清楚地验证本方法相比传统组 摘要 播方法和网络编码全局方法的优势，但同时也发现本方法相对于网络编码全局方 法在解的精确性上仍然存在一点差别。 在论文的最后对全文进行了总结，归纳了论文的主要贡献和创新点，并提出了 进一步工作计划。并在附录里对第三章中描述的代表性方法用到的一些数学理论 基础和优化算法进行了概述，方便对已有方法的理解。 关键词：网络编码，最小代价组播，链路带宽竞争，局部优化 i l a bs t r a c t a sr a p i dd e v e l o p m e n to fi n t e m e ta n dp u r s u i n gn o v e l i t yb yp e o p l e ，t h e r ea r em o r e a n dm o r el o a do nn e t w o r k t h en e t w o r kr e s o u r c e sb e c o m e d e f i c i e n tw h e nf a c i n gs o u n d a n dv i d e os e r v i c e sa n dl a r g es c a l ef l e sd o w n l o a d ，w h i c hc o n s u m el a r g eb a n d w i d t h t h er e s e a r c ha b o u tm u l t i c a s t h a sb e e nk e e p i n gh o ts i n c eb r o u g h tf o r w a r d i nl a s t e ig h t i e s a f t e rd e v e l o p e df o rm o r et h a nt w e n t yy e a r s ，m u l t i c a s th a sb e e nc l o s et ob e g o o d n o w , m a n yn e t r w o r kf a c i l i t i e ss u p p o r tm u l t i c a s tp r o t o c 0 1 h o w e v e r , a l t h o u g h s o u n d v i d e oa n dl a r g ef i l ed o w n l o a da r ef i t t ou s em u l t i c a s t ，t h e r ea r ef e ww h i c h h a v i n gu s e dm u l t i c a s t t h e r ea r em a n yr e a s o n s m u l t i c a s tr o u t i n gi sa m o s ti m p o r t a n t o n e m a n y r e s e a r c h e r sa n di n s t i t u t e sh a v eb e e nd o i n gt h e i rb e s te f f o r tt of i n aaw a y t o g e tm u l t i c a s tr o u t i n ge a s i l y , e f f e c t i v e l ya n dr o b u s t l y b u tu n t i ln o w , r i og o o d r e s u l t n e t w o r kc o d i n gt e c h n o l o g y , w h i c hw a sb r o u g h tf o r w a r di n2 0 0 0 ，b r o u g h tn e w h o p et om u l t i c a s t b ym a k i n gn o d ei nn e t w o r kt o p o l o g yg e tt h e a b i l i t yo fc o d i n ga n d d e c o d i n gt od a t ai n c o m i n go ro u t g o i n gb e s i d e ss t o r a g e ，f o r w a r d i n ga n dr e p l i c a t i o n a b i l i t y , m u l t i c a s tc a nu s e b a n d w i d t hm o r ee f f e c t i v e l y a sf o rm u l t i c a s tr o u t i n g ，n e t w o r k c o d i n gm a k e sc o m p e t i t i o nd i s a p p e a r , w h i c he x i s t i n g i ns u p e r p o s i t i o nl i n ka m o n g d i 腩r e n ti 皿1 t i c a s ts t c i n e rt r e e si n t r a d i t i o n a ln e t w o r ke n v i r o n m e n t t h i sm a k e s m u l t i c a s tt r a n s p o r td a t ai nl o w e rb a n d w i d t hc o n s u m e d t h i st h e s i se m p h a s i z e so n n e t w o r kc o d i n g ，se f f e c t i o no nm i n i c o s tm u l t i c a s tr o u t i n g b ya n a l y z i n ge s s e n t i a l so f n e 咐o r kc o d i n go nf i l e do fm i n i c o s tm u l t i c a s tr o u t i n g ，ab r a n d n e wm e t h o d ，w h i c h u s i n gl o c a lo p t i m i z a t i o nw a y st og e to v e r - a l lo p t i m i z a t i o ns o l u t i o n ，i sb r o u g h tf o r w a r d i nt h e s i s a tt h eb e g i n n i n g ，t h e s i ss i m p l yi n t r o d u c e sn e t w o r kc o d i n gt e c h n o l o g y , m i n i c o s t m u l t i c a s ta i l dc u r r e n tm e t h o d so fm i n i c o s tm u l t i c a s tr o u t i n gb a s e d o nn e t w o r kc o d i n g t h e n t h e s i sa n a l i z e sw h a tr e a lc h a n g e st h e n e t w o r kc o d i n gb r i n g st om u l t i c a s t o p t i m i z a t i o ni n c l u d i n gm i n i c o s tm u l t i c a s tr o u t i n g a f t e rt h i s ，t h e s i st a l k sa b o u tc u r r e n t m e t h o d s m a i n l yf o c u s i n go nt w ow e l li n f l u e n c e dm e t h o d sa n da u s a sp a t e n t ，t h e s i s e x p a t i a t e so nc u r r e n tm e t h o d s i nt h ef o u r t hc h a p t e r , t h e s i sf o r m a l l yb r i n g sf o r w a r dt h e 1 1 1 l o c a l0 p t i m i z a t i o nm e t h o dw h i c ha i m i n ga t o v e r - a l lo p t i m i z a t i o ns o l u t i o n b e c a u s eo f i o c 赳叩e r a t e d ，t h em e t h o dh a s a d v a n t a g e si nr o b u s t n e s sf o r1 1 e t 、) l ，o r k ，s d 1 a d i c c h a n g e s ，c o n v e n l e l l t n e s sf o rs i n k sj o i n i n g , c o m p l e x i t yf o rm e t h o d c o m p u t a t i o na n d o 廿1 e ra s p e c t s ，c o m p a r e dw i t hc u r r e n tm e t h o d sb a s e do n n e t w o r kc o d i n g i nc h a p t e r5 ，a s 1 m u l a t j o n1 s 舀v 锄f o rv a l i d a t i n gt h e m e t h o d sp e r f o r m a n c e t h er e s u i t i s j u s t 嬲 e x p e c t e d1 n 向r i l l e rt h e o r ya n a l y s e , i n c l u d i n ga d v a n t a g e st 0 删i t i o n a l m u l t i c a s t 姐d c u 砌tm e t h o da sw e l la sa l i t t l ed e f f r e n c eo na c c u r a c yw i t hc u 哟! t m e 血o d a tl a s t , t h e s i s 罂v e so u ta s u m m e r y , w h i c hs u m m i n g u pt h em a i nc o n t r i b u t i o n sa 1 1 d 1 m l o a t l o n sa 1 1 dp l a n n i n gt h ef u r t h e rr e s e a r c h i n a p p e n d i x ，t h e s i sd e s c r i b e ss o m e m a t h 锄a t l c a 】t 1 1 e o t i e so no p t i m i z a t i o nw h i c ha r cu s e di n c u r r e n tm e t h o da 1 1 dv e r v i m p o r t a n tf o ru n d e r s t a n d i n gt h e s em e t h o d s k e y w o r d s ：n 咖。r kc o d i n g ，m i n i 哟s tm u l t i c a s tr o u t i n g , l i n kb a n d w i d t h c o m p e t i t i 。n ， l o c a lo p t i m i z a i t o n i v 关键术语解释 关键术语解释 1 网络编码：网络编码是指让网络中的节点不光拥有对数据进行存储转发的 能力，还可以对数据进行编码操作，从而达到提高网络在进行组播时的带宽利用 率及改善鲁棒性等网络性能的目的。 2 最小代价路由：最小代价路由是指在数据通过链路的代价随着数据流量的 增长而增长，且链路有最大流量限制的网络拓扑中，组播的最小代价路由。最小 代价路由往往还有一些其他限制条件，比如组播组播速率限制。本文研究的最小 代价组播就是需要保证组播速率的最小代价组播路由。 3 线性资源优化：在例如费用、无线发射能量等最小为目的的组播环境中， 各条链路的资源消耗和链路所承载的数据流量的比值为常数。即链路资源消耗为 链路数据流量的单调递增线性函数。这种情况下的路由优化称为线性资源优化。 4 非线性资源优化：在例如延时、拥塞等最小为目的组播环境中，各条链路 的资源消耗和链路所承载的数据流量成单调递增的凸函数关系。即链路的数据流 量越大，链路消耗资源的增加速度越快。这种情况下的路由优化称为非线性资源 优化。 5 全局优化：为得到最优的组播路由，需要计算各条链路消耗的代价。链路 消耗的代价和链路所承载的数据流量有关。在全局优化中，链路承载的数据流量 是以整个组播业务为考虑对象。即某一个组播业务在链路上需要多少数据流量。 从数学模型的角度，全局优化可以描述成所有宿消耗资源的和的最小化。 6 局部优化：计算链路代价的数据流量是以每个宿为考虑对象。局部优化一般 是从各个宿发起。每个宿只关心自己到源的路由代价最小化，并不考虑整个组播 路由的情况。从数学模型的角度，组播的局部优化可以描述成所有宿消耗资源最 小化的和。 7 目标方程和约束条件：在一个数学优化模型中，反应优化目的的方程称为目 标方程或目标函数，如下优化模型的( a ) 式；对目标方程中的自变量起约束作用的 等式或不等式成为约束条件，如下优化模型的( b ) 式和( c ) 式。是自变量。 v l l 关键术语解释 ( m i n i m i z e a ) 砖) 一j qu t e t ( i ，j e a ) s u b j e c t t o ： ( 6 ) ( c ) 8 优化解：优化解是目标函数值。网络优化的目的是求得最优解，但在本文中 定义的优化过程中凡是满足优化观点( 目标函数) 和优化条件( 约束条件) 的解 都是优化解。最优解是优化解中的最优值。 9 可行解：可行解是目标函数的自变量值。在数学优化模型中，满足约束条件 限制的自变量值称为可行解。通过可行解集合中的解可以在目标函数中计算出优 化解。约束条件往往只反映网络状况，如节点流量守恒、链路容量限制等。但不 反映优化类型，如局部优化、全局优化；或代价类型，如费用、延时；或资源类 型，如线性资源、非线性资源。这些信息由目标函数体现。 1 0 数学优化模型与图论求解算法。两者不是平等可代替的关系。数学优化模 型是用来描述一个优化问题。图论求解算法如d i j k s t r a 算法、单纯型法、 f o r d f u l k e r s o n 算法、s 松弛算法等是用来求解优化问题的。之所以要用到数学优 化模型，首先是将一个实际问题描述成抽象的数学问题。其次可以对抽象的数学 优化模型进行数学运算或变换，将一个数学优化模型转换成另一个优化模型。也 就是将一个优化问题转换成另一个优化问题。转换后的优化问题可能会比原问题 更容易求解。例如，主对偶方法，将一个优化问题转换成对偶问题；拉格朗日松 弛方法能将优化问题简化，文酬4 】利用拉格朗日松弛方法和次梯度方法将组播优 化问题转换成若干单播优化问题，然后再利用图论求解算法求解单播优化问题。 v i l i r 以 钉 v 辞 v船 i 一 ， 工0 j 忍 第一章绪论 第一章绪论 本章首先介绍本论文的两个基础技术网络编码技术和最小代价组播。然 后简述基于网络编码的最小代价组播路由的研究现状。接着给出本论文所做的工 作。最后是本论文的组织结构。 1 1 网络编码技术简介 当前通信网络带宽和处理能力的提高使网络能提供更多的多媒体业务，其中 许多业务都要求网络具有组播( m u l t i c a u s t ) 能力，例如音频视频点播直播会议、交 互式仿真、网络游戏、分布式数据库等。所谓组播，指的是一个源节点向多个目 的节点发送信息的通信方式，参与组播的多个目的端点组成了一个组播组，每个 端节点称为组播组成员。 2 0 0 0 年r a h l s w e d e 等人在文献【i 】【z 】中提出网络编码这一概念。所谓网络编 码，就是指让网络中的节点，不光拥有存储转发数据分组的能力，还能够对信息 进行编码操作，从而能够大幅度提高网络在执行组播应用时的吞吐率和带宽利用 率。这一点可以由图1 1 中的简单例子加以说明。 假设图中所有线路的传输速率均为l b i t 每单位时间，而节点s 要利用这个网 络同时向节点y 和节点z 组播信息。假设某一单位时间内，s 向t 和u 分别发出 比特b 1 和b 2 ，如果每个节点都只有存储转发功能，则节点w 只能从b l 和b 2 中 选择一个传给节点x ，显然节点y 和节点z 无法同时收全b 1 和b 2 ，网络提供给 节点s 到节点y 和z 的组播速率是小于2 b i t 单位时间的。而如果在这个网络的节 点中引入编码功能，即让节点w 把b 1 和b 2 做异或运算的结果传给节点x ，再由 x 将它分别传给y 和z ，则节点y 可以通过这个结果和自己从节点t 收到的比特 解出节点s 发送给u 的比特。而节点z 也可以通过类似的方式收到s 发给t 的 比特。从而使s 向y 和z 组播的速率达到了2 b i t 单位时间。 文献【l 】【2 】中证明了，任何网络中，假设在进行单播时源到各接收点 t 1 ，t 2 ，t n 的最大速率( 这个速率可以使用图论中的最大流最小割定理求得) 分别为( m f i ，m f 2 ，m f n ) ，则该源必定能够以m i n m f n ) 的速率同时对所 有接收节点进行组播。而从图1 1 中的例子可以看到，若节点不具备编码功能， 电子科技大学硕士学位论文 这个速率通常是无法达到的( 该例中m i n m f n 为2 b i t 单位时间) ，而只有引入了 网络编码，这个速率才可以达到。文献【1 】中还证明了，如果网络中的节点具有数 据编码的能力，则无论在何种拓扑的网络中进行组播，理论上的最大速率都是可 以达到的，而如果网络中的节点只具有存储转发能力，在多数情况下，这个理论 最高速率是无法达到的。 网络编码对提高组播吞吐率的特点已被广大学者接受。从相反的一个角度讲， 网络编码对组播的好处还体现在当组播吞吐率一定时，组播所消耗的网络资源( 如 网络带宽等) 将减少。后者正是本论文研究的出发点。 ( d ) 传统组播的数据分发路由，( e ) 网络编码下的组播路由，多 多播速率只有1 b “单位时闻 播速率达到2 h i t 单位时闻 图1 1显示网络编码对网络吞吐率改善的网络拓扑 2 第一章绪论 1 2 最小代价组播及其路由简介 1 2 1 组播技术的提出 传统的i p 通信有两种方式：第一种是在一台源i p 主机和一台目的i p 主机之间 进行，即单播( u n i c a s t ) ；第二种是在一台源i p 主机和网络中所有其他的i p 主机之 间进行，即广播( b r o a d c a s t ) 。如果要将信息发送给网络中的多个主机而非所有主机， 则要么采用广播方式，要么源主机分别向网络中的多台目标主机以单播方式发送 数据包。采用广播方式实现时，不仅会将信息发送给不需要的主机而浪费带宽， 也可能由于路由回环引起严重的广播风暴：采用单播方式实现时，由于数据包的重 复发送而白白浪费大量带宽，也增加了服务器的负载。所以，传统的单播和广播 通信方式不能有效的解决单点发送多点接收的问题。 组播是指在m 网络中将数据包以尽力传送e s t e f f o r t ) 的形式发送到网络中的 某个确定节点子集，这个子集称为组播组( m u l t i c a s tg r o u p ) 。组播的基本思想是， 源主机只发送一份数据，这份数据中的目的地址为组播组地址：组播组中的所有接 收者都可一接收到同样的数据拷贝，并且只有组播组内的主机可以接收该数据， 网络中的其他主机不能收到。 1 。2 2 组播技术的路由实现 考虑一个通信网络，它是由一些节点和边组成的集合，我们用有向图 g = ( y ，e ，c ) 来表示，矿和e 分别是节点和边的集合，非负数c ( e ) 用来表示边e 允 许传输信息的容量上限。在这个通信网络中，要实现由一点s 矿向多点tcv 组 播信息，传统的路由方式是通过在通信网络中建立一个或多个组播树 g k = ( 圪，b ，c k ) ，每个组播树都将信源和所有的信宿连接起来，所要传输的信息 就在这些事先选好的路径上传输。每个组播树可以实现的传输速率取决于组成这 个树的所有边中容量最小的边，也就是m i n 。吐q ( e ) 。为了可以获得更高的组播 速率，我们可以建立多个组播树g k ，k = 1 ，k ，并且在不同的组播树上传输不同 的信息，只要每条边上传输的信息量满足叉y c 。( e ) c ( e ) 即可。 1 2 。3 组播路由算法的分类 从不同的角度，组播路由算法可以有多种分类的方法。 集中式与分布式：集中式算法要求计算节点知道所有的网络状态信息，而分布 电子科技大学硕士学位论文 式算法则只要求计算节点知道部分信息，可以看出，在广域网上布署一个集中式 算法是有困难的，因此，寻求分布式的求解算法是非常重要的。 静态型与动态型：所谓的静态型是指在组播树生成以后就不再发生变化了，显 然这对于大部分应用来说是不适合的，而动态型则与此相反，在会话阶段，它允 许节点动态地加入或者离开，这符合实际的需求，但同时也给算法带来了新的问 题。 源基树与共享树型：解决组播路由问题的算法大致可分两类：一类算法称为源 基树算法，该算法为组中每一个发送者建立一棵以发送者所在子网为根的组播树， 源基树算法只适用于广播业务，另一类算法则为组内所有发送者与接收者建立一 棵共享树，这类算法适用于会议型业务( 如计算机会议) ，会议型业务具有以下特 征：( 1 ) 既有j t o 万型传输，也有m t o ，l 型传输；( 2 ) 对信息传送的时延有严格要求；( 3 ) 数据量大，且媒体多样要求不同的处理；( 4 ) 在改变发言者时要求进行快速的路由切 换。 理想的目标是设计出分布式的、动态的、共享型的时间复杂度低的、受时延约 束的、代价尽可能小的组播树，这当然具有相当大的难度，而且到目前为止也还 没有出现如此完善的算法。 1 2 4 最小代价组播 网络优化是数学优化的一个分支，主要解决两个问题：1 ，一定网络资源下， 源到宿的最大流；2 ，保证一定组播速率下，源到宿的最小代价( 资源消耗) 。“代 价根据目的不同有多种，如费用最少，延时、拥塞最小，天线发射功率最小等。 在组播网络中，前者被称为最大流组播问题，后者被称为最小代价组播问题。 自从网络中的节点除了拥有存储、转发能力还拥有复制能力后，基于树结构路由 的组播大大提高了组播的带宽利用率。原因是源到各个宿的共用链路上只需要传 递数据的一份拷贝。除此之外，由于服务器不用针对每个宿分别建立一个进程传 递数据，组播树使服务器可能只需要一个进程针对所有的宿传递一份数据。服务 器的负担大大减少了，相应地提高了其处理能力。 组播树对应于图论中的s t e i n e rt r e e 问题。s t e i n e rt r e e 是一颗除了源、宿节点外 还包含s t e i n e rn o d e 的树。s t e i n e rn o d e 是仅仅传递数据的节点。与源和宿节点不 同，流入s t e i n e rn o d e 的数据流量和流出的数据流量相等。当极限情况下，s t e i n e r t r e e 中所有节点除了源就是宿时，s t e i n e rt r e e 就是一颗s p a n n i n gt r e e ( 生成树) 。 4 第一章绪论 不幸的是，s t e i n e rt r e e 是一个公认的n p - c o m p l e t e 问题( s p a n n i n gt r e e 不是) ，也 就是不存在一个多项式时间算法可以求解s t e i n e rt r e e 问题，更进一步说求解s t e i n e r t r e e 问题将随着节点数的增加消耗无穷的时间。文献【3 】举例说u n i f o r mb i p a r t i t e 网 络结构c ( 5 ，3 ) ( 包含1 6 个节点，3 5 条连接) 中拥有近五千万个s t e i n e rt r e e 。工程上 解决此类问题有两种思路，一是采用s h o r t e s tp a t ht r e e ( 最短路径树) 代替m i n m u m s t e i n e rt r e e 。前者和后者的不同是，前者表示源到各组播宿都是以最短路径相连； 而后者表示源到个组播宿的路径之和最短。因此前者是局部最优( s e l f i s h o p t i m i z a t i o n ) ，后者是全局最优( o v e r a l lo p t i m a i t i o n ) 。如图1 2 所示。现今很多 组播协议如d v r m p 、m o s p f 、p i m d m s m 中都是采用最短路径算法计算组播 树。另一种思路主要是采用一些近似算法逼近m i n m u ms t e i n e r t r e e ，这主要应用 在网络优化中，如最小代价组播。但是近似算法是以网络资源消耗的增大换取计 算资源消耗的减少。 s t 1 图1 2 边上的数值表示长度。s p t 是由s t l 和s t 2 组成， m s t 是由s u t l 和s u t 2 组成 1 2 5 多重组播树 为了增大组播的吞吐率或将组播数据均匀分散到各条链路以防止链路拥塞，组 播路由需要采用多颗组播树多重组播树。对于网络优化的这两个问题，多重 组播树尤其重要。对于最大流组播问题，需要在一定的网络资源内寻找尽可能多 的组播树，这一问题对应到图论中被称为s t e i n e rt r e ep a c k i n gp r o b l e m 。同样，当 一颗组播树无法提供最小代价组播要求的组播速率时，需要根据代价从小到大地 寻找多颗组播树，这问题对应到图论中被称为m i n i m u ms t e i n e rt r e ep r o b l e m 。 5 电子科技大学硕士学位论文 同样这两个问题也都是n p c 问题。 1 3 研究现状 现阶段研究网络编码环境下的最小代价组播路由问题的方案并不是很多。其中 最有影响的是m i t 的l u ns l u n 。针对网络编码环境下的最小代价组播问题，l u n 发表了若干文献 4 棚。并于2 0 0 6 年7 月6 日成功申请了名为网络编码下的最小代 价路由的美国专利【9 1 。l u n 的方案针对线性资源和非线性资源分别建立数学模型 并指出了求解算法。除此之外，文献【1 0 】【1 1 】也针对非线性资源给出了自己的方案。 文献【1 0 】和文献【1 1 】建立的数学模型各不相同，但是得到的结论却非常相似。不过， 文献【】提出算法所依据的结论在证明过程中可能有些问题。而文献】依据的结论 似乎只是一个必要条件，因此依据此结论的算法可能并不会得到最优解。l u n 针 对线性资源提出的算法是分布式的而且是非同步的。针对非线性资源提出的算法 也是分布式的，但是由于非线性资源的复杂性，算法需要参与计算的节点相互同 步。 由于网络编码的引入，组播的数据流量可以增大，组播消耗的网络资源也可以 减少。但是一个尴尬的局面仍然摆在大家面前! 尽管现今很多d 网络支持组播， 尽管现今网络上形如组播的业务供求都很大，如视频直播、点播，大文件传输， 但是真正采用i p 组播的微乎其微! 实际中采用的都是单播或是应用层的多线程或 是p 2 p 技术。原因我们总结主要有两个：1 、单颗组播树路由下，组播的速率很 难达到一个较高的水平。而多重组播树的计算相对复杂。在需要速率保证的数据 业务中，路由计算更是麻烦。2 、现有组播对环境限制太多。 针对第一个问题文献3 】都从自己的方向，通过引入网络编码，使组播路由的 计算变得更分布、更有效率。但第二个问题，局限了组播的广泛应用。现有组播 路由算法需要各个节点和网络链路都要有很高的稳定性。对于追求整体性能的组 播优化而言，网络中的任何变化都可能导致组播路由的重新计算。在热点的视频 直播、点播或是大文件传输这样的业务中，节点增加、退出是很平常的事，随着 网络链路负担的日益加重，各个链路的情况发生较大变化也是有较大概论发生的。 因此组播可能会经常需要路由计算。对于终端用户而言，他们的感觉是经常陷入 因为路由计算而引起的业务等待。 6 第一章绪论 1 4 本文所做的工作 针对基于网络编码的最小代价组播路由计算，本文主要作了一下几个方面的工 作： 一、研究网络编码理论，明确网络编码的主要思想。针对组播路由，找出网络 编码带来的实质性变化。 二、研究现有组播协议中针对路由计算方法。对比一般非限制性组播和最小代 价组播在路由计算上的区别，寻找可以借鉴一般组播路由的若干方面。 三、研究现有的基于网络编码的组播路由计算方案。由于最小代价组播属于网 络优化的一部分，因此有很多数学规划理论需要学习。研究一些现有方案采用的 数学模型、全局优化算法、局部优化算法，如拉格朗日松弛思想，次梯度优化算 法，占松弛算法等。 四、采用局部优化方法求解全局优化的核心思想，设计基于网络编码的最小代 价组播路由计算方案。相比直接采用全局优化方法，使最小代价组播路由在计算 复杂度、计算收敛速度、灵活性、对网络动态变化的健壮性等方面取得进步。 五、设计节点对数据的传输方案，使不同的宿节点可以根据其带宽情况拥有不 同的组播速率。 六、针对提出的路由方案进行模拟仿真，并分析数据。 1 5 论文结构 第一章主要讲述论文将用到的一些技术概念和理论基础。包括网络编码技术介 绍，最小代价组播介绍以及现今基于网络编码的最小代价组播路由的研究状况。 除此之外，还阐述了论文的主要研究工作，以及论文的组织结构。 第二章主要讲述网络编码技术对包括最小代价组播在内的组播网络优化带来 了什么实质性的优势。首先对组播网络优化的概念和传统组播在网络优化方面的 困难进行描述，然后分析网络编码对于组播网络优化的实质，最后分析组播在灵 活性和对网络动态变化的健壮性上的先天不足，并给出解决问题的总体思想。 第三章描述网络编码环境下组播网络优化的现有方案。首先从整体上介绍现有 方案，包括研究团队、主要思想、现有成果等。其次针对两个代表性方案进行详 细阐述。接着对已成功申请的专利进行概要性描述( 专利的核心思想和其中一个 代表性方案相同) 。最后针对已有方案，分析存在的不足，并提出改进思想。 7 电子科技大学硕士学位论文 第四章正式提出本论文的创新方案利用局部优化求解最小代价组播的全 局优化。在首先介绍了核心思想之后，将整个方案分成针对线性资源的方案和针 对非线性资源的方案两个部分，并分别描述。然后给出实现同一组播组下不同组 播速率的实现办法。最后总结论文的方案。 第五章主要针对论文提出的方案建立仿真模型进行模拟，通过仿真结果分析方 案的优劣。 第六章对整篇文章进行了总结，归纳了论文的主要贡献和创新点，并提出了迸 一步工作计划。 最后在附录里对第三章中描述的代表性方案用到的一些数学理论基础和优化 算法进行概述，方便对方案的理解。 第二章网络编码技术给组播网络优化带米的革新 第二章网络编码技术给组播网络优化带来的革新 本章首先对组播网络优化的概念和传统组播在网络优化方面的困难进行描述， 然后分析网络编码对于组播网络优化的实质，最后分析组播在灵活性和对网络动 态变化的健壮性上的先天不足，并给出解决问题的总体思想。 2 1 组播网络优化简介 网络流问题是最优化问题中最重要也是最常遇到的一类问题。当分析和设计大 的系统，如通信网络、交通网络、生产系统时会很自然地产生这些问题。对一些 重要的组合问题，如带宽分配、最短路径、最大流路由、最小代价路由，这些理 论可以用来建模。 粗略地讲，网络流问题由源、宿以及将他们连接起来的路由组成。路由将源的 数据传送到宿。路由中可能还包括一些数据传送点。通常源、宿和传送点可以被 建模成图中的节点，路由可以被建模成途中的路径。甚至也有可能多个宿共享一 个路由的情况。除此之外，路由的某些特征可以被加入一些限制，比如传输带宽、 某些路由的代价等。这些情况通常都被建模成网络优化问题，简单地说这些问题 就要选择最小代价的路由将源的数据传送到宿。 网络优化包含的主要问题有：最短路径问题、最大流问题、最小代价流问题。 其中，通常最短路径问题是一个局部优化问题( s e l f i s ho p t i m i z a t i o n ) ，它解决的仅 仅是源到每一个宿的路径最短，而不考虑源到所有宿的路径之和最短。如组播协 议的最短路径树( s p t ) 、o s p f 路由器中路径树等。但是就数学问题本身来讲， 最短路径问题还是一个全局优化问题( o v e r a l lo p t i m i z a t i o n ) 。最大流问题主要解 决的是在一定网络资源下，最大化源到宿的网络流。最小代价流问题是在某些限 制下选择代价最小的网络流。其中的限制包括链路上带宽容量的限制和链路最低 流量的限制。除此之外，根据通信业务的不同还可能有不同的限制，比如源到宿 的网络流大小限制。通信目的不同还将导致代价的表示不同，如费用、延时、拥 塞、发射功率等。这些表示的不同将直接导致网络模型的不同。最小代价流问题 根据代价表示可以分为两大类。一类是线性资源问题，线性资源是随着链路流量 的增大，链路资源的花费成线性增长，如费用、发射功率等；而非线性资源问题 9 电子科技大学硕士学位论文 是随着链路流量的增大，链路资源成非线性增长，如延时、拥塞。 最短路径问题实际上是没有链路容量限制的最小代价流问题。最大流问题实际 可以转化成没有链路代价的最小代价流问题。三个网络优化问题都可以被建模成 与图相关的数学模型，如图2 1 所示。其中s 是源，f 是宿，a 是链路的集合，f ， 是图中的节点。厶是链路( f ，_ ，) 的长度。a u 是链路( f ，) 的代价函数，可能是链路流 量厶的线性函数也可能是非线性凸函数。，c 扩是链路( f ，j f ) 的链路流量限制。4 是节点i 内到宿节点t 的组播流量。当4 0 时，节点f 是源，当4 0 时，说明f 是宿，当4 = 0 时，f 是传送点。 m i n i m i z e 1 日 i , j e a ) s u b j e c t ： 乃一厶= 磊，v i en , t t j x i ，j ) e a抓，。j 冲 ( a ) 最短路径问题的数学模型 m a x i m i z ex s u b j e c t ： e 驴乃，v ( i ，j ) a 乃一厶= o o t h e r s x i ， i= s ， 朋k 一仆 d “ 【- 一z i = t ( b ) 最大流问题的数学模型 m i n i m i z e a 。( 乃) ( i j e a ) s u b j e c t ： ic u 兀6 f ，v ( i ，) 彳 1 乃一厶= 4 ，v i e n ，te t l 用j ，j ) e aj i i ( j d ) e a ( c ) 最小代价流问题的数学模型 图2 1 网络优化的数学模型 对于网络优化问题有很多算法求解。对于局部优化的最短路径问题有著名的 d i j k s t r a 算法，对于最小代价流问题有单纯型法、主一对偶算法、f o r d f u l k e r s o n 算法、s 松弛算法等。其中s 松弛算法可以分布式并非同步的实现。由于最大流 问题可以转化为最小代价问题，因此求解算法大同小异。组播的网络优化问题变 1 0 第二章网络编码技术给组播网络优化带来的革新 得复杂很多，由于宿不止一个节点，宿之间相互制约的因素很多，因此要找到一 个全局优化解很不容易。组播的网络优化问题对应到图论中的s t e i n e r t r e e 问题。 这是一个公认的n p c o m p l e t e 问题。 本论文主要研究带组播速率保证的最小代价流组播问题。由于最大流组播可以 转化为最小代价流组播，因此一些最大流组播问题也在研究范围之内。 2 2 传统组播网络优化的困难 在单播情况下，中间节点( 如路由器) 拥有存储、转发数据包的能力。当中间 节点拥有复制数据包的能力时，组播就产生了。从图论的角度，中间节点复制数 据包的能力表现为不同宿节点可以利用相同的一段链路从源得到相同的数据包。 更进一步讲，传统组播中，不同宿节点共享的链路必定是从源节点出发的，然后 这条共享链路在某个中间节点处分开为若干条通向不同宿节点的不同链路。共享 链路的这个特点是因为复制数据包的能力只能使不同宿节点通过共享链路获得相 同的数据包，而不同的数据包则不能通过共享链路获得。 共享链路的使用使组播的资源消耗可能减少。从图论的角度，共享链路使传统 组播的优化问题对应了s t e i n e rt r e ep r o b l e m 。最大流组播优化对应了s t e i n e rt r e e p a c k i n g 问题，即在一定的网络资源下，塞满最多的s t e i n e rt r e e ；当 c 。r ，v ( i ，) a ( 即组播速率小于等于任意一条链路容量) 时，线性最小代价 组播优化对应了m i n i m u ms t e i n e rt r e e 问题；c o - f , j ，v ( i ，j ) ea 2 一劈) - ，v i e n ，f r 抓j ) e 瓜) e 一 砌一心三p 图2 - 2 存储、转发下的组播最小代价优化模型 除此之外，即使在不考虑共享链路上厶= m a x 疋j d ) 的情况下约束( 2 “；7 c f ，厶= ，v ( i ，j ) a ，t t 限制了组播优化问题不能采用分布且非同步 ( i 。d 。e 。a ) 。 的算法进行求解。假设组播路由需要如图2 - 3 ( a ) ( 虚线，点线分别代表一颗组播 树，重合的链路用实线表示) 所示的两个组播树组成：s - u 1 u 3 u 4 t i t 2 和 s u 2 1 1 3 u 4 t 1 t 2 。两棵组播树在u 3 u 4 ，“t 1 ，u 4 t 2 重叠。以1 1 3 u 4 为例考虑链路带 宽约束问题，f ( t r e e l ) + f ( t r e e 2 ) q 3 。当采用分布式算法时，每个组播树的计 算实际上不是从源s 出发上考虑两颗组播树的，而是从t 1 ，t 2 的角度出发。例 如，计算t 1 到s 的两条最短路径，计算他到s 的两条最短路径。于是从t 1 考 虑，其到s 的路径为t l u 1 - s 和t 1 一u 4 - u 3 - u 2 s ；从1 r 2 考虑，其到s 的路径为 t 2 u 2 s 和t 2 u 4 u 3 u 1 s ，如图2 3 ( b ) ( 虚线代表t l 到s 的路径，点线代表t 2 到s 的路径，两者重合的地方用实线表示) 所示。那么链路u 3 u 4 的带宽约束问 第二章网络编码技术给组播网络优化带来的革新 题实际计算中是考虑：“+ 名。c 幽。这给计算带来了很大的