多QoS约束的层次多播路由算法框架  

The Hierarchical Multicast Routing with Multiple QoS Constraints

作　　者：颜昕[1] 李腊元[1] 

机构地区：[1]武汉理工大学计算机科学系,武汉430063

出　　处：《计算机科学》2007年第2期27-34,110,共9页Computer Science

基　　金：国家自然科学基金(No.60172035;90304018)资助

摘　　要：为了解决网络路由的扩展性问题,大型网络通常被划分成若干个不同的域。拓扑聚集是对这些域的拓扑状态信息进行汇总的过程。在拓扑聚集的基础上,QoS层次多播路由算法用来构造满足QoS要求的域间多播树。现有的QoS层次多播路由算法在其拓扑聚集和路径计算的过程中都只考虑了存在两个QoS特征值的情况。本文提出了一种具有多QoS约束的层次多播路由算法框架HMRMQ(Hierarchical Multicast Routing with Multiple QoS con-straints),此算法框架不仅为基于多QoS特征值的拓扑状态聚集和状态信息表示提供了新的方法,而且提出了一种适应于多QoS约束的层次多播路由新算法。我们提出的状态信息表示法和拓扑聚集算法都具有很好的扩展性,分布式的路由算法也便于某些安全性策略的实施。理论分析和实验结果不仅证明了HMRMQ的正确性和有效性,同时也表明了HMRMQ在网络路由的扩展性、路由成功率、网络代价以及报文负载等方面都具有良好的性能。In order to deal with the scalability problem of network routing, large networks are often structured hierarchically by grouping nodes into different domains. Topology aggregation is the process of summarizing the topological state information of the domains. Based on topology aggregation, QoS-aware hierarchical multicast routing algorithms are used to construct a multicast tree satisfying QoS requirements among network domains. The existing QoS-aware hierarchical multicast routing algorithms don＇t take into account more than two QoS metrics during their topology aggregations and route computations. In this paper, we propose an algorithm framework of hierarchical multicast routing with multiple QoS constraints, called HMRMQ, which provides both new schemes for topological state aggregation and state information representation based on multiple QoS metrics and a novel hierarchical multieast routing algorithm with multiple QoS constraints. The schemes of representing and aggregating multiple QoS metrics are very scalable, and the distributed routing algorithm is facile to implement certain security policies. Our theoretical analysis and simulation results not only prove the correctness and availability of HMRMQ, but also show that HMRMQ achieves the routing scalability and the improved routing performance in terms of routing success ratio, average network cost and average message overhead.

关 键 词：拓扑聚集 层次路由 多QOS约束 QOS多播路由 

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