（计算机软件与理论专业论文）组播中的核管理机制研究.pdf

盟型型型堕燮 塑茎 摘要 随着多媒体业务的发展，网络带宽的需求原来越大。组播作为一种数据传送 技术，可以极大的节省带宽，提高数据的传送效率。其中，有核组播因其良好的 可扩放性而受到广泛关注。有核组播在网络中选取一个核节点，并以它作为根来 建立一棵连接组播组中所有成员节点的单一共享树，而不是为每个源节点建立 棵树。由于不同位置的核节点将生成不同的组播树，核节点实际上决定着有核组 播的性能。因此，核节点管理机制是有核组播中的重要问题。本文就核管理机制 中的核选择和核迁移两个方面展开了研究，主要工作和贡献为： 1 针对多到多的组播模型，提出了一种新的核节点评价机制。该机制能够 较好的反映多到多组播的总代价。 2 给出了一个以优化总代价为目标的核选择完全算法，该算法的良好设计 使得其算法复杂度较低。 3 设计了两种核选择近似算法，并分析了它们的近似比。理论分析和实验 分析都说明了算法的有效性。 4 对已有的核迁移算法进行了综述，并进行了分析比较。在此基础上，提 出了一种可扩放的核迁移算法。该算法中的树代价估算机制为核节点的 迁移时机提供了一个可信的评价标准。 本文主要研究内容是网络中的组播问题，但组播中的很多优化问题是与图论 相关的，因此本文在组播树性质、最短路性质等方面的研究既对组播有实际意义， 又有一定的理论意义。 关键词：有核组播，核节点选择，核节点迁移，s t e i n e r 树，最短路径 中国科学技术大学硕士学位论文 a b s t r a c t a l o n gw i t ht h ed e v e l o p m e n to fm u l t i m e d i as e r v i c e ，t h ed e m a n df o rn e t w o r k b a n d w i d t hb e c o m e sm o r ea n dm o r e g r e a t a sad a t at r a n s m i s s i o n t e c h n o l o g y , m u h i c a s tc a ns a v eb a n d w i d t h e n o r m o u s l ya n de n h a n c et h e d a t at r a n s m i s s i o n e f f i c i e n c y c o r e b a s e dm u l t i c a s tr e c e i v e sw i d e ra t t e n t i o nb e c a u s eo fi t s g o o d s c a l a b i l i t y c o r eb a s e dm u l t i c a s ts e l e c t sac o r en o d ei nt h en e t w o r k ，a n dt h e nu s e si tt o e s t a b l i s has i n g l es h a r i n gt r e e c o v e r i n ga l lm u l t i c a s tg r o u pm e m b e r s ，o t h e rt h a n b u i l d i n gt r e e sf o re a c hs o u r c en o d e c o r en o d e si nd i f f e r e n tp o s i t i o n sw i l lg e n e r a t e d i f f e r e n tm u l t i c a s tt r e e s ，s ot h ec o r en o d ea c t u a l l yd e t e r m i n e st h ep e r f o r m a n c eo fc o r e b a s e dm u l t i c a s tt h e r e f o r e ，c o r em a n a g e m e n ti sa ni m p o r t a n ti s s u ei nc o r eb a s e d m u l t i c a s tt h i st h e s i ss t u d i e sc o r es e l e c t i o na n dc o r em i g r a t i o n ，t h em a i nw o r ka n d c o n t r i b u t i o ni n c l u d e ： 1 p r o p o s i n gan e wc o r e n o d ea p p r a i s a lm e c h a n i s mi na l l u s i o nt om a n y t o m a n y m u l t i c a s tm o d e lt h i sm e c h a n i s mc a nr e p r e s e n tt h et o t a lc o s tv e r yw e l l 2 g i v i n gac o m p l e t e c o r es e l e c t i o na l g o r i t h mw h i c ht a r g e t sa tt o t a lc o s t o p t i m i z a t i o n t h eg o o dd e s i g nr e s u l t si nl o wc o m p l e x i t y 3 d e s i g n i n gt w oa p p r o x i m a t ea l g o r i t h m sf o rc o r es e l e c t i o na n dg i v i n gt h e a n a l y s i so fa p p r o x i m a t i o nr a t i o b o t ht h et h e o r e t i c a la n a l y s i sa n dt h ee x p e r i m e n t a l a n a l y s i sd e m o n s t r a t et h ee f f e c t i v e n e s s 4 p r e s e n t i n gas u r v e yo fc o r em i g r a t i o na l g o r i t h m sa n dg i v i n ga n a l y s i sa n d c o m p a r i s o n ，a n dt h e ng i v i n gas c a l a b l e c o r em i g r a t i o na l g o r i t h m t h et r e ec o s t e s t i m a t i o nm e c h a n i s mp r o v i d e sac r e d i b l ec r i t e r i o nf o rt h em i g r a t i o nt i m e t h em a i nr e s e a r c h s u b j e c t o ft h i st h e s i si sm u l t i c a s ti n n e t w o r k m a n y o p t i m i z a t i o np r o b l e m s i nm u l t i c a s ta r er e l e v a n tt o g r a p ht h e o r yt h e r e f o r e ，t h e r e s e a r c hi nt h i st h e s i so nm u l t i c a s tt r e ep r o p e r t i e sa n ds h o r t e s tp a t hp r o p e r t i e sh a s t h e o r e t i c a ls i g n i f i c a n c ef o rg r a p ht h e o r ya sw e l la sp r a c t i c a ls i g n i f i c a n c ef o rm u l t i c a s t k e y w o r d s ：c o r eb a s e dm u l t i c a s t ，c o r es e l e c t i o n ，c o r em i g r a t i o n ，s t e i n e rt r e e ， s h o r t e s tp a t h i i 中国科学技术大学颂士学位论文 图表索日 图1 1 单播，广播与组播 图1 2 有源树与有核树 图1 - 3 有核组播生命周期 一 图2 - 1 核迁移 幽2 2 绸捅葬法分类 图2 - 3 有核树的优势 图3 - 1s t e i n e r 树 图3 2 单播代价的对比 图3 - 3 完全算法性能分析 幽3 - 4 核选择近似算法1 性能分析 图3 5 核选择近似算法2 性能分析 图4 - 1 定时核切换步骤1 图4 - 2 定时核切换步骤2 图4 - 3 定时核切换步骤3 幽4 - 4 逐步核切换步骤l 剀4 - 5 逐步核切换步骤2 图4 - 6 逐步核切换步骤3 幽4 7 逐步核切换步骤4 表2 1 核选择算法对比 表2 - 2 核选择算法的复杂度 图表索引 v 2 1 2 2 一 m 捞 如 ” 拈 曲 如 如 蚰 ” 犯 舛 中国科学技术大学硕士学位论文 第一章绪论 1 1 引言 第一章绪论 近年来，随着互联网的迅速普及和爆炸性发展，在网络上产生了很多新的应 用，比如分布式数据库开发、视频会议等，它们对传统的路由选择机制提出了新 挑战。 在这些应用中，交换信息的方式有其重要的特点。当规模比较小时，交换信 息只需要单播即可；如果规模较大，采用单播则对网络、对信息发送者而言都是 一种负担，要付出昂贵的代价，另外还可能引起网络拥塞。拥塞的发生会使网络 资源处于饱和状态，从而导致信息传输延时变长，包丢失率上升，系统吞吐量急 剧下降，严重时会使得网络崩溃。当然也可以采用广播方式进行处理，但如果在 一个上百万节点的网络上向数以干计的节点进行广播，这是极其低效甚至是不可 能的。因为绝大多数的节点并不需要此信息，这将造成信息垃圾，增加非接收者 的开销。另外，如果采用广播方式，源节点和目的节点必须在同一子网中，不能 跨越子网传送，这就大大限制了广播方式的应用。因此，需要一种方法让规模较 大而相对互联网又较小的节点组能够方便快捷的传递信息，并尽可能节约网络资 源。 因此，引入了组播的概念。 1 2 组播工作原理 数据在网络中的传输一般有3 种方式：单播( u n i c a s t ) 、广播( b r o a d c a s t ) 和组播 m u l t i c a s t ) 。 单播在源节点和每个目的节点之间建立单独的数据信道。如果源节点同时给 很少量的接收者传输数据，一般没有什么问题。但如果有大量节点希望获得数据 包的同一拷贝时则很难实现。因为这将导致发送者负担沉重、网络延迟变长、网 络拥塞等问题。为保证定的服务质量，就需要大量增加硬件和带宽。在单播中， 接收节点和源节点可以不在同一个子网里。 中国科学技术大学硕士学位论文 第一章绪论 广播是多点传递的一种形式，它向每个目的节点传送数据的一个拷贝，其主 要缺点是：对信息不感兴趣的节点也会收到该信息。广播传输会增加非接收者的 开销，相反，有可能由于网络拥塞，想得到的却得不到。广播会耗费大量的主机 资源和网络资源，而且不能穿透子网，因为路由器会封锁广播通信。 组播界于二者之间。组播是一种由源节点同时发送单一的数据包到多个目的 节点的优化使用带宽的网络技术，它有助于减少主机的处理量及控制网络的流 量。组播源把数据发送到特定的组播组中，只有属于该组播组的成员才能接收到 数据包。组播可以大大的节省网络带宽，既提高数据的传送效率，又减少主干网 络出现拥塞的可能性。组播以最佳的方式将数据传输给所有的组播成员。组播成 员可以是动态的，即成员可以在任何时间加入一个组或者离开一个组。组播组的 大小和位置也没有限制，一个主机可以是多个组的成员。 图1 1 显示了单播、广播，组播三者间的区别。 v i d e o s e r v e r 中国科学技术大学硕士学位论文 第一章绪论 图1 1 单播，广播与组播 1 3 组播网络模型和算法 在研究计算机网络中的组播问题时，网络可以表示为无向加权图g = ( 日。 v 表示图g 中的通信节点集合，表示边集合，即任意两相邻节点间的通信链路 的集合。i 表示网络节点数，旧表示网络中的链路数。 一般规定，任意两个节点间最多有一条链路，链路上的参数表示其当前的状 态。例如延时函数d e l a y ( e ) ：e f ，表示在传输链路e 上的延时( 包括排队延时， 传输时间等) 。同样的，也可以将链路的可用带宽作为链路的参数。另外还可以 把网络节点的参数作为该节点当前的状态，例如：当前可用的缓冲区空间，包丢 失率等。把局部的节点链路信息收集起来就可以得到整个网络的状态信息。 在组播中，用s 表示源节点，丁表示目的节点集，v t 称作组播组成员。组 播树是g 的一个子图，并且包含s 和丁中的所有节点，有可能还包括图中其它 的一些节点作为转发节点。根据源节点和目的节点的组合，组播通信可以分为一 对一，一对多，多对多的方式。 要保证组播通信的有效进行，确定组播路由是关键。在路由算法中，通常给 定组播组、目标优化函数以及约束条件集合，约束条件集合可以包括端到端延时、 延时抖动、包丢失率、跳数、带宽中的一个或多个。组播路由算法就是要根据网 络拓扑结构，在链路状态满足约束条件的前提下建立种结构来实现目标函数的 优化。 解决组播路由问题的有效方法就是建立组播树结构。之所以采用树结构，因 中国科学技术大学硕士学位论文 第一章绪论 为：第一，信息可以沿着树的分支并行的传到各目的节点，实现组播的功能；第 二，信息只在树的分支处进行复制，从而使得复制的份数尽可能的少，从而有效 的利用了网络资源。 组播算法与组播协议有所不同。组播算法决定组播树的建立过程，指明经过 什么样的操作步骤使组播路由器建立起组播转发表；协议则是为实现算法而规定 的控制报文结构以及交换这些报文的规程。不同的协议通常会使用不同的算法， 例如d v m r p ( v 3 ) 协议使用了基于“广播并剪枝”的r p m 2 1 算法而m o s p f 3 协议则使用了最短路径算法。但是，不同的协议也可以使用相同或相似的算法， 例如p i m d m f 4 0 ( 协议无关组播密集模式) 就使用了与d v m r p 相同的r p m 算法。 两者的差别在于，p i m d m 不包括传播常规单播路由信息的工具，而是假定路由 器已经使用了一个单播路由协议来计算到每个目的节点的最短路径。 从上述分析可以看出，算法是协议的核心，算法决定协议的基本特征；协议 是围绕算法而发展的一整套规约，协议把算法有机地包含在内，但协议的内容更 宽泛。协议更多地关心路由信息收集和维护问题、组关系管理问题等。本文主要 关注组播算法。 以下根据不同角度对组播算法进行分类。 1 3 1 集中式算法与分布式算法 集中路由算法( c e n t r a l i z e dr o u t i n ga l g o r i t h m ) 其特点是：每个节点计算出从源 节点到目标节点集的整棵组播树。为此，网络中的每个路由器都必须维护一个全 局状态( g l o b a ls t a t e ) 信息库并且周期性地对其进行更新。最具代表性的采用集中 路由的组播算法是m o s p f 。当一个路由器第一次接收到一个组播数据包时它就 使用d i j k s t r a 算法计算出以该数据包源节点为根的最短路径树( s h o r t e s tp a t h t r e e l 。由于所有路由器都拥有相同的网络拓扑信息，因此每个路由器将计算出相 同的组播树。集中式路由算法的问题是，路由器为存储全局状态而付出的开销较 大，同时它也是计算密集型的。但集中式算法可以有效地避免环( l o o p ) 的出现。 分布式算法( d i s t r i b u t e dm u l t i c a s ta l g o r i t h m ) 的特点在于组播树的计算是由位 于网络中的多个路由器协作完成的。例如p i m s m ( 5 1 ( 协议无关组播一稀疏模式) 的算法是分布式的。分布式算法的存在的问题是，虽然计算负担被分散了，但容 中国科学拉术大学硕二匕学位论文 第一章绪论 易导致环的出现。 分布式算法还可细分为需要全局状态的和不需要全局状态的。例如p i m s m 需要常规单播路由信息来适应网络结构的变化，因此它是需要全局状态的。一些 纯粹以泛洪技术( f l o o d i n g ) y 4 基础的算法可归于不需要全局状态信息的分布式算 法，因为其使用的泛洪技术完全是依靠所有路由器的简单协作来建立传播路径 的。例如在s p a n n i n g - j o i n t l 6 j 组播路由算法中，路由器接收到组播数据包时在除了 数据包到达的端口外的其余端口上转发数据包，这个过程不需要全局状态信息。 这两种分布式算法中，前者跟集中式路由一样面临存储开销太大的问题，而后者 又会引起较高的传输开销。 1 3 2 完全算法、近似算法与启发式算法 所谓完全算法( c o m p l e t ea l g o r i t h m ) 是指在一定条件下以确定的计算步骤求 解问题最优解的算法。完全算法的优点是算法思想比较简洁直接，但往往具有较 高的时间复杂度。m o s p f 所使用的d i j k s t r a 算法属于完全算法，算法根据路由 器所存储的全局状态拓扑信息，计算出从源节点到目的节点的最短路径树。 近似算法( a p p r o x i m a t ea l g o r i t h m ) 是指以多项式时间解决优化问题并保证能 够得到近似解的算法。例如，k m b l 7 j 算法是一个被评述较多的s t e i n e rt r e e 近似 算法。但k m b 算法需要网络全局拓扑信息，因此不太适合大规模网络，同时 k m b 还假定组播组是静态的。 启发式算法( h e u r i s t i ca l g o r i t h m ) 采用某个启发式函数或启发式规则对计算步 骤进行限制，它不保证一定能够找到可用解，但是一个设计较好的启发式算法， 往往能够得到接近最优的解( n e a ro p t i m a ls o l u t i o n ) ，同时具有相对低的时间复杂 度。很多组播路由问题都是n p 难解的，例如延时受限的组播问题、带宽受限的 组播问题等等，这类问题一般采用启发式算法。 1 3 3 数据驱动算法与需求驱动算法 数据驱动算法( d a t a d r i v e n ) 也称为源发起算法( s o u r c e i n i t i a l i z e d ) ，其特点是 在网络中将数据发送到所有节点，直到接收了确切的抑制消息后一些节点才停止 转发。基于泛洪技术的反向路径转发( r p f ) 、截尾反向路径转发( t r p f ) ；g l 反向路 中国科学技术大学硕：e 学位论文 第一章绪论 径组播t p , jm ) 算法均属数据驱动的。数据驱动算法不需要传播组成员信息，但会 在一些没有接收节点的分枝上产生额外的传输开销，同时这种方法不支持基于接 收者的q o s 请求来进行选路。 与数据驱动算法不同，需求驱动( o n d e m a n d ) 算法是由需要加入组播组的接 收者发起的( r e c e i v e r i n i t l a l l z e d ) ，只有当源节点或树上节点( o n t r e e n o d e ) 接收到 加入请求后才开始转发组播数据。m o s p f 、c bt ”、p i m s m 等协议采用了需求 驱动算法。需求驱动算法克服了数据驱动算法会在一些没有接收者节点的分枝上 产生额外传输开销的弊端，但是，类似m o s p f 这样的协议需要传播组成员关系 信息，其可扩放性( s c a l a b m t y ) 不好，因为它的路由决策依赖于特定组的链路状态 信息的全网广播。 1 3 4 单路径算法与多路径算法 单路径路由算 法( s m g l ep a t hr o u t i n g ，s e a ) 提供一条单一的路径将新成员连接 到组播树上，而多路径路由算法( m u l t ip a t hr o u t i n 岛m p r ) 提供多条路径供新成员 选择，新成员选取其中最能满足其要求的一条连接到组播树上。m o s p f 、c b t 和p i m s m 等协议都采用了单路径路由算法，s p a n n i n g - - j o i n 协议所用算法是m p r 的典型代表。多路径路由算法较单路径路由算法在支持q o s 、提高连接成功率、 缩短加入时间等方面有较大优势，但它的控制报文开销较大。如果能够找到有效 办法降低这种开销，多路径路由是更有前途的算法。一些学者基于理论和实验分 析，也倾向于发展多路径路由算法一j 。 1 3 5 有源算法与有核算法 有源树( s 0 u r c eb a s e dt r e e ) 采取为每一个源节点建立一棵组播树的策略。这种 算法能够为每个源节点提供延迟优g t ? q _ h n n ，同时有利于网络负载的平衡。但 是，为每个源节点分别建立组播树会使组播路由表的大小正比于网络中的源节点 数与组播组数目的乘积，所以这类算法的可扩放性不好。有源树比较适合一点到 多点的组播通信，d v m r p 、p 1 m - d m 、m o s p f 等即属于有源算法。 中国科学技术大学 o i - i - ：学位论文 第一章绪论 绑描成员 组播成员2 组播成越3 图1 2 有源树与有核树 有核树( c o r eb a s e dt r e e ) 其基本思想是尽可能地让组播组的所有源节点共享 同一个转发树。有核树算法建立一棵植根于被称为核节点( c o r en o d e ) 的路由器 的组播树。这种策略的优点是每个路由器无需存储( 源，组) 对的组播路由表项， 而是存储形如f + ，组) 的表项，“号表示任意源，因此存储丌销只正比于组 播组的数目，而与源节点的数目无关，因此有较好的可扩放性。有核算法的问题 在于，通信量在核节点的集中会导致瓶颈效应，同时有核树往往难以做到为所有 源节点提供最优路由。c b t 和简单组播( s m ) 1 0 1 等属于有核树类型的算法。 p i m s m 严格讲属于混合型算法，因为它的主体是有核算法，但是它也支持有核 树向最短路径树切换。 图1 2 给出了有源树和有核树的例子。另外，组播算法之问还有其它种类的 中国科学披术大学硕二l 学位论文第一章绪论 区分，例如动态算法与静态算法，支持q o s 和不支持q o s 的组播算法等等。 1 4 有核组播及其生命周期 在组播通信中，每一个参与组播会话的节点均可以作为源节点发送数据，因 此，如果采用面向源节点的组播路由策略，为每一对( 源节点，组播组) 均建立一 棵独立的组播树来传输数据的话，势必会造成系统路由开销的增加以及网络资源 的巨大浪费，同时在某些情况下，由于一些链路被多棵组播树所共享，这些链路 将会成为会话中的瓶颈链路，一旦这些链路发生拥塞，势必会阻断相应的组播会 话，最终造成整个会话过程的失败，进而给组播通信造成巨大的破坏。所咀，在 当前的组播群组通信中。往往不采取面向源节点的路由策略，而是通过建立一棵 为所有源节点所共享的组播树来解决以上这种单一组播组下多会话的组播路由 问题，这一方法被称为有核组播路由策略。 1 4 1 有核组播的优点 有核组播路由策略最早是由w a l l 在文献 1 1 中提出的，其思想是，在网络中选 取一个核节点，并以其作为根节点建立一棵连接组播组中所有成员节点的共享 树。当需要发送数据时，组播会话的源节点首先通过运行相应的单播最短路径算 法将数据发送到核节点，然后再由核节点通过共享树向所有其他的成员节点进行 转发。在共享树中，源节点与目标节点之间不是通过最短路径来传输数据的，因 此，数据的传输并不是时延最小的，但是对于整个组播组来说，采用共享树的方 式可以极大的节省网络资源。 与有源组播路由算法不同的是，由于在组播群组通信中必须满足多对多的数 据传输模式，有核组播路由策略实际上是面向目标节点的。在这一策略中，由于 不必像前者那样为每一对( 源节点，组播组) 都建立一棵组播树，对于给定组播组 上的多个组播会话它仅仅需要建立一棵共享树，所以大大降低了路由算法的系统 开销。此外，由于共享树中的链路资源可以被组播组中的所有节点所共享，不同 的组播会话分时占用共享树中的路径进行数据的传送，所以在提高网络资源利用 率的同时，有核组播路由策略也大大降低了瓶颈链路由于过度拥塞而造成组播会 话失败的可能性。 中国科学技术大学硕士学位论文 第一章绪论 具体来讲，采用有核组播路由策略具有以下几个优点： 1 与有源组播路由算法不同，有核组播路由算法将缩放比例因子( s c a l i n g f a c t o r ) ns n 减小到n ，其中s 为源节点的个数，而n 为组播组中节点的个数。 这是因为，在基于核节点的组播路由算法中，共享树建立是以组播组的个数为单 位，而不是以组播会话的个数为单位。一个组播组只需建立一棵共享树，对于组 播组中不同的( 源节点，组播组) 来说，没有各自独立的组播树；特定组播组上的 所有组播会话均共享此组播树上的路径。因此，即便网络中存在多个组播组，每 一个路由器也只需以组播组的个数为单位保存相应链路的状态。而不必以不同的 组播会话为单位，为每个( 源节点，组播组) 保存相应的链路状态。这样不仅大大 减少了路由器所需保存的信息，降低了路由算法的系统开销。同时还使得网络资 源得以最大的利用，减小了多个纽播树之间由于资源竞争而产生耦合的概率，最 终实现了减小缩放因子的目的。 2 在有核组播路由策略中，共享树的建立是面向目标节点的 ( r e c e i v e r b a s e d ) ，不是面向源节点的。因此，一个处于共享树与源节点之间的最 短路径上的路由器来可以不必花费相应的组播树建立丌销。 3 共享树的建立与报文的传送虽然利用了下层的单播路由策略，但事实上却 是与之相分离的，这就是说下层的单播路由策略相对于上层的组播会话来说是透 明的，上层基于核节点的组播路由策略“封装”了下层的单播路由算法，组播数 据的发送并不需要了解下层单播路由策略如何实现，后者的实际选取并不影响上 层组播会话的进行。因此，在组播路由算法的选取与设计上具有很大的灵活性。 4 在有核组播路由策略中，共享树的所有信息均不必经过附加的操作就可以 通过相应路由器中的单播路由表获得。这就使得上层的组播路由策略具有与下层 的单播路由策略相同的鲁棒性，而后者常常将算法的鲁棒性作为一个重点因素予 以考虑，因此从客观上保证了组播路由算法的鲁棒性。 1 4 2 有核组播的生命周期模型 生命周期模型描述了一个有核组播会话中的各种问题。在一个有核组播会话 的生命周期中，有三个问题可能出现：组变动，网络变动以及流量变动。前面两 个要考虑的问题是：当出现组播成员加入退出组播组的时候，或者当网络拓扑 中国科学技术大学硕士学位论文 第章绪论 中的链路节点发生失效新增的情况时，如何使得组播树保持最优：第三个问题 与流量控制、拥塞管理以及错误控制有关。组播组的特性直接影响着生命周期的 形态，根据这些特性可将组播组分类为： 1 稠密组稀疏组：稠密组中，组播成员非常集中，而稀疏组的组成员呈现分 散分布。 2 开放组封闭组：开放组允许组播组之外的节点成为源节点( 发送节点) ， 而封闭组则要求源节点属于组播组。 3 永久组瞬时组：永久组的存在延续时间要比瞬时组长的多。 4 静态组动态组：动态组允许成员的加入离开，而静态组不允许。 一个网络体系结构如果要提供完整的组播通信，则必须要以对用户透明的方 式管理组播会话的整个过程。实现透明的组播服务则对网络的具体实现有一些特 殊的要求，从而可以在各个阶段处理各种事件。图1 3 给出了在一个典型组播会 话中会出现的各个阶段及事件：组播组的生成、组播树的建立、数据传输、组播 会话撤销旧。 图1 3 有核组播生命周期 1 组播组生成：组播会话初始化的第一步是给组播组分配一个唯一的组播地 址，从而避免组播组之间的数据传输冲突。组播地址分为静态的和动态的，静态 的地址始终被分配给唯一的一个组播组，而动态地址在不同时间可能被分给不同 中国科学拽术大学硕士学位论文第一章绪论 的组播组。组播组和组播地址之间最合适的匹配就是把静态地址分给永久组，把 动态地址分给瞬时组。 2 组播树的建立：一旦生成组播组，下一个阶段就是建立一棵覆盖源节点及 所有组播组成员的组播分发树。组播路由之所以被设计成树形结构，有以下三个 原因： 在树结构上，源节点只需要发送一个组播数据包； 在树结构上，数据可以并行的向组播组成员扩散； 在树结构上，数据复制被最小化，因为数据只需要在分支节点进行复制： 在构建分发树之前的一个重要步骤就是选择树根，在基于有源树的组播中， 发送信息的源节点就作为树根。在基于核的组播中，就需要以一定的评价标准选 出一个节点来作为树根，这也就需要运行核选择算法。如果核选择算法是低效的， 则组播路由算法的性能和效率就必然要受到极大影响。 3 数据传输：以上两个阶段完成后，组播数据就开始传输了。在数据传输过 程中，有四种情况可能发生： 组成员动态性：组播组成员是动态变化的，因此网络在组播会话期间应该跟 踪组播组的现状。跟踪到变化之后，网络开始向新的组成员转发数据或者停止向 离开的组成员转发数据，即图中的受限在线组播( c 0 l m ) 所示。对组成员动态 性进行跟踪的方法有洪泛式，集中式或者分布式 1 3 。 网络动态性：在组播会话生存期中，如果支持这个会话的某个节点或者链路 失效，则组播服务就会中断。因此需要一种机制来检测失效，从而能够对组播树 进行重新配置，即图中的f a i l u r eh a n d l i n g 。如果组播协议是独立于而不是依靠单 播路由协议，它就必须自己处理失效事件。 传输问题：类似于单播中的流量控制，即图中的t r a f f i cc o n t r o l 。 源节点之间的竞争：在有核组播中，多个源数据发送者共享同一个组播树， 这些组播会话之间就存在着资源竞争。由此引发的缓冲区溢出将导致数据丢失， 从而产生传输问题。因此需要会话控制机制来对多个发送者进行仲裁和协调，即 图中的s e s s i o nc o n t r o l 。 4 组播树变动： 在动态组播会话中，有两个指标非常重要：组成员的加入离开不会中断正 中国科学技术大学顺士学位论文 帮一章绪论 在进行的组播会话；组成员, d l l y i 离开之后组播树依然保持最优或者近似最优。 当有组成员d i l l 离开的时候，可以重新建立一棵组播树来满足要求，但这样需 要把已有的组播成员从旧树迁移到新树上，从而引起大规模服务中断，这通常是 不被允许的。另一种方法采用嫁枝剪枝机制对组播树进行增量的变动，但增量 的方法无法保证组播树的最优性。因此，一个组播路由算法必须考虑两个重要却 互相矛盾的目标：组播树代价最优和服务中断时间最小。为了取得这两个目标之 间的平衡，就需要有一种机制来监测组播树的质量，当质量低于一个阂值的时候， 就会引发组播树的重整。即图中的t r e er e a r r a n g e m e n t 。 5 核节点迁移： 在有核组播中，核节点的选择至关重要，它影响着组播树的代价和延迟。随 着组播成员的加入离开，组播树的质量恶化，为了保持组播树的最优，就需要 重新选择核节点，基于新核节点重新建立组播树，然后将组播成员从旧树迁移到 新树上。 核迁移还可以作为核节点恢复机制的一部分来解决核节点失效的问题。核迁 移机制中包含着一些折衷。一个是核迁移的引发时机：保持高质量的组播树要求 经常性的核迁移，但这会导致服务中断和额外开销。因此核迁移算法的引发时机 非常重要；另一个是组播树代价：在核迁移过程中，如果不惜分配大量的资源， 则可以使得服务中断时间最少，因此资源消耗和服务质量之间也存在着折衷。 6 组撤销：当组播会话结束时，源节点发起撤销过程。这个过程包括释放组 播树所有链路上的资源，清空与这个会话相关的组播路由条目。最后组播地址被 释放，完成组播组的撤销。 1 5 本文的研究内容及主要成果 由上节可知，有核组播中的两个非常重要的问题是核节点选择以及核节点迁 移。本文的主要研究内容就是核选择算法和核迁移算法。 已有的核选择算法在进行核节点的选择时，只考虑到一到多的组播情况，对 多到多组播场景下的组播树优化未作考虑，但有核组播的提出本身就是为了实现 多个源节点场景下的网络优化。本文针对多到多组播的场景，设计了核选择的完 全算法和近似算法。 中国科学技术大学硕士学位论文 第一章绪论 在组播生命周期中，组播成员和网络拓扑都可能发生频繁的变化，因此会使 当前的组播树的性能下降，此时就需要进行核节点的迁移，调整组播树的形态， 以使得网络资源得到优化使用。本文对现有核迁移算法进行了广泛调研，在吸收 己有成果的基础上，展开了深入研究，提出了一个可扩放的核迁移方案。 本文剩下内容组织如下： 第二章介绍了有核组播中需要研究的问题，重点综述了有核组播中的核管理 机制，包括核选择以及核迁移。 第三章针对多到多组播提出了一种代价最小的核选择算法，分别给出了完全 算法和近似算法。对近似算法的近似比进行了推导，并在模拟实验中予以验证。 第四章在充分调研已有核迁移方法的基础上，提出了一种可扩放的核迁移算 法。该算法利用最短路径信息估算最优组播树代价以及评价当前组播树代价，算 法复杂度较低，且可根据网络状态进行调整。 第五章给出了总结，并对进一步研究进行了展望。 中国科学技术大学硕士学位论文 第二章有接组播及其棱管理机制 2 1 引言 第二章有核组播及其核管理机制 有核组播的思想是在网络中选取一个核节点，并以其作为根来建立一棵连接 组播组中所有成员节点的共享树。当需要发送数据时，组播会话的源节点首先通 过运行相应的单播最短路径算法将数据发送到核节点，然后再由核节点通过共享 树向所有的组播组成员节点进行转发。在共享树中，源节点与目标节点之间不是 通过最短路径来传输数据的，所以数据的传输并不是时延最小的，但是对于整个 组播组来说，采用共享树的方式可以极大的节省网络资源。 2 2 有核组播中需要研究的问题 2 2 1 核节点的选择 有核组播路由算法中的一个重要问题就是核节点的选择问题 1 4 。顾名思义， 这一问题的研究重点就是选择网络中的哪一个节点作为有核树的根节点。由于不 同位置的核节点将生成不同的有核树，而不同的有核树必定具有不同的性能指 标，因此核选择问题实际上是决定组播会话性能指标的问题。同时，考虑到有核 组播路由策略是基于共享树的整体资源优化，可能无法为所有的组播会话提供最 优路径，特别是当一个相对集中的组播组具有一个外部核节点时，其性能将大打 折扣，因此研究核节点的选择与有核树性能之问的关系就变得愈发重要。 2 2 2 核节点的动态迁移 核节点的动态迁移问题就是在组播群组会话的过程中，如何动态地选择新的 核节点，并以其替代当前核节点的问题”】。动态迁移的目的就是在当前核节点 的性能指标不能满足条件的情况下，重新优化网络资源的配置，确保组播通信的 正常进行。在基于核节点的组播路由问题中，由于所有组播会话必须通过核节点 进行传送，所以核节点是整个问题的瓶颈，一旦核节点失效或发生拥塞，将会使 中国科学技术大学硕士学位论文 第二章有核组播及其檀管璀机制 得整个有核树解体，从而导致所有组播会话的中断，在这种情况下只有选择新的 核节点重建有核树，才能继续完成组播群组会话的功能。 其次，在组播群组会话中，当网络节点动态地加入或退出组播会话，可能会 导致核节点严重偏离组播组的“中心”，从而造成原有组播树资源的严重失配。 这时，也要求网络及时地将原有组播树的核节点调整至一个新的位置，以便在保 证服务质量请求的情况下降低路由算法的系统开销并降低有核树占有的系统资 源，例如在图2 1 中，黑色节点表示组播组成员，灰色节点表示核节点，核节点 由位置1 迁移到了位置2 。在核节点的动态迁移问题中要注意有核树的环路形成 情坍。 图2 1 核迂移 2 2 3 核节点的失效检测问题 基于核节点的组播路由策略中，核节点是整个结构的瓶颈节点，一旦失效必 将导致整个有核树的失效，进而给组播组通信造成极大的破坏。因此有必要研究 核节点的失效预防与检测以及相应的失效恢复机制。 目前针对以上问题，共有两种解决方案 8 ：单一核节点的有核树的备份方案 以及针对多核节点的有核树方案。这两种方案的本质都是通过维护多个核节点来 实现核节点的失效预防、检测与恢复。但是两者不同的是，在具有单一核节点的 有核树中，核节点的失效将意味着整个有核树的解体，所有基于此有核树的组播 会话都将被阻断。因此在相应方案中，系统通过维护多个备用的核节点来降低发 中国科学技术大学硕士学位论文 第二章有核组播及其核管理机制 生这种情况的可能性。当某一核节点的性能大大降低时，网络中的路由器可以通 过附加核节点继续进行组播会话。而在第二种情况下，任意核节点均具有相同的 重要性，任意节点的失效均不会影响有核树的整体效果，系统通过维护多个核节 点来保证整个网络的可靠性，同时，由于这一方案主要适用于网络节点广泛分布 的情况，因此，核节点往往定位于成员节点相对集中的区域，以便优化这些节点 之| b j 的路径。但是第二种方案的缺点在于，系统维护的工作量增大，并且同步所 有核节点比较困难。 2 2 4 环路问题 所谓环路问题是指在组播路由的过程中，某个组播树上节点既是数据分组的 发送方，同时又是相同分组的接收方，也就是说在组播树中包含有环形路径。环 路在路由算法中是应该被尽量避免的，这是因为一旦环形路径产生，任何进入环 路的分组都将沿着此环路无限循环，直到超时后被丢弃为止；同时，在环路上的 每一个脱离环路的分支节点处，分组都将被复制，并被发送至相应的下游节点， 从而造成网络中大量的重复数据；如果进入环路的分组较多，那么网络中必将产 生大量重复数据，最终将产生网络拥塞，甚至使网络饱和，导致网络通信的崩溃。 有核组播路由策略是面向目标节点的路由方式，因此，在建立有核树的过程 中与其它目标节点驱动的路由方式类似也将不可避免地面临着环路问题m 】。尤 其是在核节点动态迁移的过程中，旧核节点与共享路径的删除，以及新核节点与 共享路径的选择与创建将会使得发生这一情况的概率进一步加大。环路的产生将 会对数据传输造成极大的损害，是造成网络拥塞的个最重要的原因。在环路问 题中，有效的检测及恢复机制是解决这一问题的关键，因此在相应的路由算法中， 需要包含这一机制，或者从理论上能够保证环路不会发生。 2 2 5 网络负载平衡问题 组播通信的网络负载平衡问题在文献1 7 1 中又被称为组播打 n 。( m u l t i c a s t p a c k i n g ) i n l 题。这一问题主要研究的是当网络中存在多个组播组时，如何均衡或 优化系统资源占用，即如何解决多个组播通信的资源共享问题。 当网络中存在多个组播组，而每一个组播组又涉及到多个组播会话时，网络 中国科学技术大学硕士学位论文第二章有核组播及其核管理机制 为所有组播组建立的共享树之间有可能相互覆盖，即在各个有核树之间存在共享 链路。由于在这些共享链路上可能同时传输多个组播会话，所以将会造成瓶颈效 应。一旦这些链路发生拥塞或者失效，将会对整个网络的数据传输造成灾难性的 影响。因此，在这种情况下，必须考虑共享链路的负载均衡问题，将所有共享链 路上的负载降低到最低限度，一般可以通过找出网络中的最坏共享链路并降低其 流量负载来实现。 2 3 核管理机制及其研究现状 上节讨论了有核组播中的一些主要课题。本论文的研究重点是其中的核节点 选择以及核节点迁移，并称为核管理机制。 核管理机制可以在主机层面或者网络层面完成。在主机层面的机制中，主机 或者用户选出核节点，当它们向边缘路由器提出加入组播组的请求时，它们需要 同时提供核节点的位置。但是，主机对于网络的拓扑特性以及流量分布不甚了解， 因而缺乏必要的信息来选出“最好”的核节点。本文中，我们只考虑网络层面的 核管理机制，即由网络中的路由器而不是主机来承担选择核节点。 在核管理机制中，核节点和组播组之间的对应关系可以选择保存或者不保存 在网络中。在隐式核管理机制中，核节点的身份可以从组播组的i d 直接推导出 来，因此不需要额外的存储。例如，可以利用哈希函数对组播组i d 和核节点进 行映射匹配。这种方法节省路由器的空间，但是核选择过程受到了限制。p 1 m s m 中的核管理机制就属于这一类。在显式核管理机制中，所有活动组播组的核节点 都显式的存放在网络中的某个位置，例如一个预先设置好的核管理服务器。这种 方法可以配合使用各种核选择方法，但是也引起了额外的管理以及存储开销。文 献 【1 8 中给出了这样的一种方法。 当前，针对核选择及核迁移问题，己经进行了大量的研究工作。文献 1 4 提 出了任意核节点( a r b i t r a r yc o r ec h o i c e ) 、随机选择( r a n d o mc o r ec h o i c e ) 、基于网 络拓扑结构( t 0 p 0 1 0 9 y b a s e dc o r ec h o i c e ) 以及基于组播组结构( g r o u p - b a s e dc o r e c h o i c em e t h o d s ) 四种解决方案，然后分别针对组播通信中的三种场景