基于链路可共享性的多播路由算法

A Multicast Routing Algorithm Based on Shareability Analysis

基于链路可共享性,提出一个快速有效的时延约束多播路由算法SBMR.该算法首先计算各链路的可共享性,然后根据链路的可共享性,由大到小依次选择链路参与多播路由,最后由所选链路组成一棵低代价的多播树.实验结果表明,与多播路由KPP算法相比,本算法构建的多播树有72%比KPP算法构建的多播树更优,代价降低13%,启用的链路数减少9%,而且CPU时间减少15%.与多播路由DCSP算法相比,本算法以增加28%的CPU时间为代价,构建的82%的多播树比DCSP更优,代价降低15%,而且启用的链路数减少11%,达到了更好的链路共享.

This paper introduced a new concept of link shareability as heuristic information, and presented a multicast routing algorithm SBMR to minimize costs with delay constraint. It was proved that SBMR could find a satisfactory routing tree as long as it existed, and the complexity was O（K2n2）, or O（ n I EI ）. Experiment results showed that, compared with KPP, multicast trees generated by SBMR were 72 96 better than that generated by KPP with 13% decrease of cost, and 9% less links invoked. On the other hand, SBMR also generated multicast trees better than DCSP with a probability of 82%, 15% decrease of costs of the network, and 11% less links to be shared on the average. However, the CPU time increased by 28% as a penalty in this case.