Qos Constrained Multicast Routing Algorithms

Recently, many of the multi-media applications require networks to provide multicast. These applications, for instance, can be audio,video conference,distributed simulation,network game,distributed database and so on. Multicast technology, which transmits the same data from a source to a large number of destination nodes simultaneously, in order to save a great deal of bandwidth and reduce data redundancy in the network, can resolve the problem of bandwidth bottlenecks of the multimedia communications in a certain extent, and will become an important technology in the future.The main purpose of multicast routing algorithms is to construct a tree rooted at the source and spanning all destinations, while the quality of service (QoS) will be satisfied. Delay and delay variation are two QoS metrics that directly related to real-time interactive applications. In this thesis we further study the problem of delay and delay variation bounded multicast routing.The first part considers the delay constraint multicast routing problem. This problem refers to constructing minimum-cost spanning trees constrained by delay, which is known to be NP-Complete problem. On the basis of some related work in this area, we present two new heuristic algorithms. One of the algorithms considers the influence that the links to the cost of the tree and the delay of the links, we present the concept of key nodes, the algorithm can find the low-cost multicast tree under the delay constraint. In the other algorithm we introduce node priority function and link choice function, and use the politics of unicast routing algorithm for generating low-cost tree while satisfying the delay constraint. The conclusion is that these two algorithms are of low time complexity and low-cost under delay constraint. In the second part, we discuss the significant of delay variation in some multicast applications. We also present a heuristic algorithm for multicast routing problem with delay and delay variation constraints. Based on the function we give a delay and delay variation bounded heuristic Steiner tree constructing algorithm. It's shown that, in terms of delay variation, the heuristic algorithm demonstrates good average case behavior through simulations.