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

Self-adaptive Lagrange relaxation algorithm for aggregated multicast

作　　者：葛祖全[1] 王华[1] 马军[1] 

机构地区：[1]山东大学计算机科学与技术学院,山东济南250061

出　　处：《计算机应用》2007年第4期811-813,817,共4页journal of Computer Applications

基　　金：中国下一代互联网示范工程资助项目(CNGI-04-13-2T)

摘　　要：组播在数据转发上有明显的优势,但是当网络中的组播组很多时,转发状态大大增加,管理组播组需要消耗大量的资源和控制开销。聚合组播是一种新颖的减少组播状态的方法,它使网络中能够复合的组播组共用同一棵分布树,从而减少了组播树上核心路由器的开销。聚合组播问题实质上是最小集合覆盖问题,可以用自适应拉格朗日松弛算法来解决。与传统的贪婪算法相比,这个算法能得到全局最优解的可能性更大,并且更加有效地提高了聚合度,减少了组播转发状态。Multicast has great advantages in data forwarding. But the number of forwarding states becomes huge in routers when there are a large number of multicast groups in the network, which may Cause explosions of state information and control information. Aggregated multicast is a new approach to reduce the number of multicast state. It enables multicast groups to share a single distribution tree so that the tree management overhead at core routers can be reduced. Aggregated Multicast can actually be attributed to minimal set cover problem, which is an NP-eomplete problem. A self-adaptive Lagrange Relaxation Algorithm that can achieve global optimal solution was used to solve it. Simulation results show that this algorithm is better than the conventional greedy algorithm in that it improves aggregation degree and reduces multicast state number.

关 键 词：聚合组播 最小集合覆盖 拉格朗日松弛 拉格朗日乘子 

分 类 号：TP393.01[自动化与计算机技术—计算机应用技术]