基于最小生成树的时延约束多播路由算法

A Multicast Routing Algorithm Based on Minimum Cost Span Tree

多播路由已有广泛的应用,但满足时延约束而代价最小的多播路由算法复杂性很高.提出一种快速有效的基于最小生成树满足端到端时延限制的多播路由算法STBMR.STBMR试图建立原图的满足时延约束的最小生成树,如果这样的最小生成树不存在,则用已找到的树与时延最小路径一起组成满足时延约束的多播树.此算法简单易实现,时间复杂度为O(n2),与KPP[6]算法的时间复杂度O(Δn3)相比,具有更大的应用价值.当然,这是以多播树的费用增大为代价的.实验模拟表明STBMR算法构造的多播树费用比KPP算法构造的约大4%,但STBMR算法执行所耗CPU时间比KPP算法约少54%.

Multicasting is widely used in various applications. But the computational complexity of multicast routing algorithms is very high.This paper presents a new algorithm STBMR for multicast routing with delay constraint. This new algorithm,with a O(n2) complexity, can be implemented easily. It is proven that this new algorithm can find a satisfactory routing tree as long as it exists. Experiment results show that comparing to KPP[6], the cost of multicast trees generated by the new algorithm is a little higher than the cost of multicast trees generated by KPP, and the increased cost is about 4%.But,at the price of cost increasing,the CPU time used by STBMR is much less than that used by KPP, the decreased CPU time is about 54%.