多播路由KPP算法的改进  

Some Improvement on the Multicast Routing Algorithm of KPP

作　　者：曾锋[1] 姚兰[1] 王东[1] 

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

出　　处：《计算机工程与应用》2005年第29期137-140,共4页Computer Engineering and Applications

摘　　要：论文提出一种满足端到端时延限制的多播路由算法。该算法参考KPP[7]算法,在构造多播路由树的过程中动态调整路径的选取,使尽可能地共享网络中的链路,并对所构造的多播树进行进一步的调整优化,最后得到一棵低代价的满足端到端时延限制的多播路由树。论文通过对KPP算法进行分析发现KPP算法思想忽略了对转发节点的处理,而且在两节点间路径的选取过程中仅仅选取最佳路径,这就导致了对边稠密的图,KPP算法存在缺陷。算法基于上述缺陷完善了KPP算法,在复杂的网络图中应用该算法比KPP算法更加有效,实验模拟表明该算法构造的多播树与KPP算法构造的多播树相比能优化9%到10%。This paper analyzes the limitation of KPP（71 multicast routing algorithm,and makes some improvement upon KPP algorithm,then presents a new multicast routing algorithm to minimize costs with delay constraint.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,the cost of muhieast trees generated by the new algorithm is less than the cost of muhieast trees generated by KPP,and the decreased cost is from 9% to 10%.

关 键 词：多播路由算法 时延限制 STEINER树 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] TP301[自动化与计算机技术—计算机科学与技术]