Chinese Journal of Computers   Full Text
Title	Dynamic Hierarchical Multicast Routing with Delay-Bandwidth Constraints
Authors	HU Hong-Yu LU Hui-Mei CAO Yuan-Da RAO Si-Min
Address	(Beijing Laboratory of Intelligent Information Technology, School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081)
Year	2009
Issue	No.3(564—575)
Abstract &   Background	Abstract In order to solve the scalability problem of QoS routing in large networks, large networks are structured hierarchically by grouping router nodes into different domains. Routing algorithms based on hierarchical networks are investigated and become one of the most effective solutions for the scalability problem. The authors conduct a comprehensive study on dynamic hierarchical multicast routing with delay-bandwidth constraints based on PNNI hierarchical network model in this paper. A novel topology aggregation method, Stair method, has been proposed in the authors’ previous work, which is the first step for hierarchical routing and in which two QoS parameters (delay and bandwidth) are considered. On this basis, the authors further study the Multicast Tree State Information (MTSI) that tree nodes need to maintain for multicast routing and the aggregation problem of internal MTSI of a domain. Pseudo Tree Border Node (PTBN) mode for MTSI aggregation is then proposed in this paper. Finally Delay-Bandwidth constrained Hierarchical Multicast Routing (DBHMR) algorithm using aggregated topology information and multicast tree state information is designed, which supports group members to join and leave multicast group dynamically. Simulation results show that the whole routing system achieves large compression of topology information and multicast tree state information not only stored in but also exchanged by nodes and at the same time gains the similar route efficiency compared with the flat network. Scalable multicast routing in large networks is realized eventually in this paper. Keywords delay; bandwidth; multicast tree state information; multicast routing; hierarchical routing Background With the fast development of hardware technologies, as well as with the increasing demands for quality of services (QoS) fueled by continuously emerging multimedia applications, offering guaranteed and better services than best effort services becomes an important and challenging issue for the next generation networks, among which QoS-based unicast/multicast routing is the core and indispensable technology. Although many QoS-based multicast routing schemes have been proposed, most of them are not practical in the Internet environment because many issues are involved in them, such as, excessive computation overhead, large amount of the knowledge of the global network state, only one QoS parameter considered, no support to the dynamic group membership and the heterogeneous QoS requirements imposed by group members. This paper conducted a comprehensive study of all of these problems, which get support by the National Natural Science Foundation of China (Nos.60503050, 60773045), Basic Research Foundation of Beijing Institute of Technology (No.200511F4212) and Key Discipline Construction Project of Beijing. The authors have proposed several QoS multicast routing algorithms to solve the scalability problem: QHMR［1］ and HBHMR［2］. QHMR focus on the hierarchical multicast routing problem with only one QoS parameter constraint (bandwidth) based on HMR hierarchical network model. HBHMR resolved the dynamic hierarchical multicast routing problem with the heterogeneous bandwidth requirements imposed by different group members which is as same as based on HMR model. Further more, the authors deeply discussed the aggregation problem of the topology information of a domain and Stair method was proposed in 2007. With the basis of their previous work［1-3］, this paper conducted a detailed study on the aggregation problem of the multicast tree state information of a domain with more QoS parameter constraints (delay and bandwidth) and the dynamic multicast routing using the aggregated topology information and multicast tree state information based on PNNI model which is a more popular hierarchical network model.