多约束QoS多播路由的模型和算法研究  

Research on Multiple Constraints-based QoS Multicast Routing Model and Algo rithms

作　　者：孙宝林[1,2] 李腊元1 

机构地区：[1]武汉理工大学计算机学院 [2]武汉科技学院数理系,武汉430073

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

基　　金：国家自然科学基金资助项目(编号:60172035);湖北省自然科学基金项目(编号:2000J154);湖北省教育厅重点科研项目(编号:2003A002);武汉科技学院基金资助项目(编号:20032418)

摘　　要：随着高性能网络、移动网络及Internet的不断发展,具有QoS约束的多播路由技术已成为网络及分布式系统领域的一个重要研究课题。基于约束多播路由的目的在于鉴别一条路径满足QoS约束,然而,多加、乘约束的路由是一个NP-完全性问题。因此,快速的和精确的约束路由算法是少有的,甚至不存在。如此基于路由算法的需求导致众多的启发算法和一些少有的QoS算法的出现。文章描述了一种适用于研究QoS多播路由的网络模型,给出一个完全,简洁和公平地评价7个典型的基于多约束QoS多播路由算法,并且提供多约束路径算法的最坏情况下复杂性的比较。Constraint-Based Multicast Routing aims at identifying a path that satisfies a set of quality of service(QoS)constraints.Unfortunately,routing with multiple additive constraints is known to be a NP -complete problem.Hence,accurate constraints -based routing algorithms with a fast running time are scarce,perhaps even non -existent.The expected impact of such a constrained-based routing algorithm has resulted in the proposal of numerous heuristics and a few exact QoS algorithms.This paper describes a network model for researching the QoS multicast routing problem.It presents a thorough,concise and fair evaluation of the seven important multiple constraint-based QoS Multicast routing algorithms known today,and it provides a worst -case complexity comparative overview of multi -constrained routing algorithms.

关 键 词：多播路由算法 多QOS约束 QOS路由 网络模型 NP-复杂性 

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