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

A Multicast Routing Algorithm Based on Shareability Analysis

作　　者：王东[1] 曾锋[1] 闵应骅[1] 

机构地区：[1]湖南大学计算机与通信学院,湖南长沙410082

出　　处：《湖南大学学报（自然科学版）》2006年第4期111-114,共4页Journal of Hunan University:Natural Sciences

基　　金：国家自然科学基金项目资助(60273070)

摘　　要：基于链路可共享性,提出一个快速有效的时延约束多播路由算法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.

关 键 词：多播 时延 链路共享 STEINER树 

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