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

摘要

随着高性能网络、移动网络及Internet的不断发展,具有QoS约束的多播路由技术已成为网络及分布式系统领域的一个重要研究课题.基于约束多播路由的目的在于鉴别一条路径满足QoS约束,然而,多加、乘约束的路由是一个NP-完全性问题.因此,快速的和精确的约束路由算法是少有的,甚至不存在.如此基于路由算法的需求导致众多的启发算法和一些少有的QoS算法的出现.文章描述了一种适用于研究QoS多播路由的网络模型,给出一个完全,简洁和公平地评价7个典型的基于多约束QoS多播路由算法,并且提供多约束路径算法的最坏情况下复杂性的比较.