组播路由综合优化及其算法  

Integrated Optimization of Multicast Routing and Its Algorithm

作　　者：董庆阳[1] 李毓麟[1] 

机构地区：[1]上海交通大学区域光纤通信网与新型光通信系统国家重点实验室,上海200030

出　　处：《计算机学报》2001年第4期395-399,共5页Chinese Journal of Computers

摘　　要：路由优化是组播通信的一个关键问题 ,它的目标是降低路由费用 .论文中首次提出了组播路由费用综合优化的思想 ,即组播路由的网络费用和目的地费用同时得到优化 :优化网络费用以降低路由消耗的网络资源 ;优化目的地费用以减少源到目的地的平均时延 .并提出了一种组播路由费用综合优化算法 ,该算法的时间复杂性低 ,实现简单 ,还可以分布式实现 .The recent emergence of multimedia communication and collaborative work in distributed environments provides an incentive to system designers to include communication support for these applications. A prevalent pattern in such environments is multicast (one-to-many or many-to-many) communication. Routing is one of the key problems to multicast communication. The objective of multicast routing optimization is to minimize the network cost or destination cost. Finding a multicast routing tree with minimized network cost is known to be an NP-Complete problem in the most general case. The existing heuristics have high time complexity. The heuristics with simple, easy and distributed implementations are under research. Up to now, there is no balanced method between optimization of network cost and optimization of destination cost yet. In this paper, a concept of integrate optimization of multicast routing is put forward, in which both network cost and destination cost are optimized in a certain degree. Optimization of the network cost can reduce network resources consumed by communication, while optimization of the destination cost can reduce average delay from source to receivers. An algorithm is also put forward, which can accomplish integrated optimization of multicast routing. An attenuation method is applied to this algorithm. An attenuation parameter is set in the algorithm, which can adjust optimization level between optimization of network cost and optimization of destination cost. The algorithm is simulated in many random network models, and is proved that it has better performance than existing heuristics. This algorithm has low time complexity, and can also be implemented easily and in distributed fashion.

关 键 词：组播路由 目的地费用衰减算法 优化 多媒体通信 路由树 

分 类 号：TN919.8[电子电信—通信与信息系统]