解决聚合组播的自适应拉格朗日松弛算法

组播在数据转发上有明显的优势,但是当网络中的组播组很多时,转发状态大大增加,管理组播组需要消耗大量的资源和控制开销。聚合组播是一种新颖的减少组播状态的方法,它使网络中能够复合的组播组共用同一棵分布树,从而减少了组播树上核心路由器的开销。聚合组播问题实质上是最小集合覆盖问题,可以用自适应拉格朗日松弛算法来解决。与传统的贪婪算法相比,这个算法能得到全局

维普资讯 http://doc.guandang.net

第2 7卷第 4期20 0 7年 4月文章编号：0 1 0 1 20 ) 4—0 1 0 10—9 8 ( 0 7 0 8 1— 3

计算机应用Co mpue p i ains t rAp lc to

Vo. 7 N . 12 o 4Apr 0 .2 07

解决聚合组播的自适应拉格朗日松弛算法葛祖全，王华，马军 (东大学计算机科学与技术学院，山山东济南 20 6 ) 50 1( eu un 13 cm) gz q a@ 6 . o

摘要：组播在数据转发上有明显的优势，但是当网络中的组播组很多时，转发状态大大增加， 管理组播组需要消耗大量的资源和控制开销。聚合组播是一种新颖的减少组播状态的方法，它使网 络中能够复合的组播组共用同一棵分布树，而减少了组播树上核心路由器的开销。聚合组播问题从实质上是最小集合覆盖问题，可以用自适应拉格朗日松弛算法来解决。与传统的贪婪算法相比，这个算法能得到全局最优解的可能性更大，并且更加有效地提高了聚合度，少了组播转发状态。减 关键词：合组播；小集合覆盖；聚最拉格朗日松弛；格朗日乘子拉中图分类号： P 9 . 1 T 3 3 0文献标识码： AS l- da tv gr ng ea a i n ag rt o g r g t d m ulia t efa p ie La a e r lx to l o ihm f r a g e a e tc sG u q a, ANG Hu, u E Z—un W a MA J n

( colfC m ue c ne n eh o g,Sa d n n e i,Jn nS ad n 50 1 C i Sho o p t Si c dTcnl y h nog U i r t i hn og2 0 6, hn o r e a o v sy a a)Ab t a t sr c:Mu t a t a r a d a t g si a afr r i g u e n mb ro r ad n t ts b c me u e i o tr l i s sg e t v n a e d t owad n .B t h u e f o r ig sae e o sh g r u e s c h a n t fw n w e h r r a g u e fmu t a tgo p h ew r,wh c y c u e e p o i n f tt n omain a d c nr l h n te e a

e a lr e n mb ro l i s r u si te n t o k c n i h ma a s x l so so ae i fr t n o to s o

if r t n n o ma i .Ag rg t d mut a t sa n w a p o c o r d c h u e fmu t a ts t. I e a l s mu t a tg o p o o g e a e l is e p ra h t e u e t e n mb ro l i s t e t n b e l i s r u s t c i c a c

saeas￣ ir ui e ot th e nae e t vreda cr u r cnb eue .A g gt lt at a h r i eds b t nt es h e r ma gm n eha t oer t s a r cd gr a dMu i n n t o r a t te i o oe e d e e c c sa t a y b t b td t nma e o e rb e cu l at u e o mii ls tc v rp o l m, w d h i - o lt r b e l e i r b c sa NP c mp ee p l m. A efa a t e L g a g l x t n n o s l d p i a rn e Rea a o - v i

Agrh a cnahee￣ b p m lsltnw sdt slei i lt nrs t so a t sa o tm i bt r lo tm t t a c v oa o t a ou o a ue o o .S ai eu s hw t th grh se t i h i l i i s v t mu o l h i l i et a h o v n in e d g r h n ta ti mv sa ge ai n d ge n d c smut a tsae n mb r h n tec n e t a g e ya o t ol r l i m i h ti mp e r g t e ea d r u e l is t t u e . g o r e c Ke r s g r g td mu t a t y wo d:a g e ae l i s;mii l e o e;L g a g ea ai n a r g lt le c n ma s t v r a rn e r l t;L g a e mui i r c x o n p

0引言 自I P组播模型…建立以来，P组播技术一直是人们研 I究的热点。组播是一种有效的支持多点通信的机制，它采用树转发结构，

其数据分组在树的分支节点处被复制，在每条链

虽然不需要路由器维护组播转发状态，但是转移组播状态本

身就需要路由器来处理，了额外的开销。第三类方案是增加聚合组播技术”, J与前两类方法不同的是，方法使能够复该合的组播组共享一棵组播分发树 (聚合组播树 )使得网络中，组播树的数目大大减少，心路由器只需要维护每棵聚合树核而不是每个组播组的状态，因此转发状态大大减少。在选择

路上仅转发一次。这种方式使得 I播可以高效地将数据 P组同时传送到各个组成员，并有效地支持大量组播组。一棵组播树需要每一个路由器来维护组的转发状态。转发状态条目

聚合组播树时，u— o gC i用了贪婪算法。由于贪婪算 JnH n u采法每一次都选择当前情况下的最优解，容易陷入局部最优很解，到全局最优解的可能性小，以有一定的局限性。本文得所

的数量随着组数量的增加而线性增长，而这些不断增长的转发条目也使得路由器的内存需求增大，同时由于每个分组的转发需要地址查找，所以转发过程会变得很慢。因此当网络中的

提出了一种新的算法来解决聚合组播问题。

组播会话数很大时，会消耗大量的资源 (如保存组状态信息的内存 )和控制开销 (如建立和维护组播树 )来管理组播组。

1聚合组播背景介绍 11聚合组播的概念 .

针对这一问题，的一些研究者提出了许多种方案来国外解决此问题：第一类方案为状态聚合技术，如文献[]出了 2提 个算法来聚合转发状态并分析研究了内存和带宽的折中问题，文献[]用输输出过滤模型来分析转发状态的聚合 3使一一

图1描述了一个分层的域间网络对等结构。假定域 A是

个 IP骨干网， B、 D、、是域 A的用户网络。网络 S域 C、 E F都中有三个组播组 G ( 1B、 1、 1 F、 1 C ) G ( 1B ) D、 1C )G ( 1B、 1、 2 D、 1,

它们在域 A内的子树分别为 1 ( lA,b,2,3,1 A, 1 A, a A A A ) T ( 1 DA,b,2 A ) ( 1A, b A )由于三个组在域 A中有 aA A,3, A, aA,2。

等。这些状态聚集技术尝试在分布树构造好之后进行路由状态的聚集，而对于很多的服务提供商来说，然通常这是不能被

相同或相重

合的内部域子树，以可以使用同一个组播组地所址，建立一棵覆盖 A, 2和 A 1A 3节点的预定树 T A, a A, ( 1 A,b A,3, 2 A )这棵树称为聚合树，可以由多个组播组共享。

接受的。第二类方案为状态转移技术，如文献[]出将目 4提标地址编码到一个组播报文中，而路由器不需要维护组的从

转发状态信息，文献[ 6提出了在路由器上完全消除组播 5,]状态，将复杂性移到端节点上的方法等。这些状态转移技术收稿日期：0 6—1 20 0一I: 1修订日期：06—1 20 2—1 3

使用聚合树时，骨干网的边界路由器把特定组的数据在进入的边界路由器上封装，然后在聚合树中分发，并在离开的

基金项目：中国下一代互联网示范工程资助项目( N .—32 ) C GI 4 1 -T 0

作者简介：全( 9 2,,葛祖 18一)男山东蓬莱人，硕士研究生，主要研究方向：网络路由、聚合组播；王华 ( 9 2一)男， 16,山东淄博人，副教授， 博士，主要研究方向：网络优化算法、网络路由、组播；马军(9 6一),, 15男山东济南人，教授，博士生导师，主要研究方向：网络计算.