Study Of Multicast Routing Algorithm Based On QoS

With the rapid development and widely using of the Internet, the multimedia data such as common data, audio, image and video, etc, are increasingly transferred through the Internet. All of these new multimedia applications ask Internet Service Provider (ISP) for much higher quality of service (QoS): such as network bandwidth, transmitting cost and delay, delay jitter and the loss rate are included. Although the model of "best effort" is the main transmission now, it cannot meet the different requirements for different multimedia applications. Some multimedia applications who send IP packets from single point to multiple receivers adapt multicast technique to save network resource and share network links. QoS of the multicast for network applications includes routing selection, traffic engineering, QoS negotiation mechanism, Constraint Based Routing etc, and the routing selection is the key one.The major achievement of this dissertation is outlined in the following:(1) In this dissertation, we apply the traffic engineering load balancing techniques to the summary, multifaceted analysis and evaluation of the taxonomy of the multicast routing algorithms at large.(2) A static routing model, called GMM-model, is detailedly analyzed for this model puts forward multitree-multicast load balancing with splitting in a multiobjective context for the first time, whose mathematical solution is a whole Pareto Optimal set.(3) A dynamic multiobjective optimization model, called D-GMM model, is proposed by using bidirectional search algorithm. The algorithm can develop a multicast transmission load balance by using multiple paths given by the D-GMM-model. We have employed a multi-objective algorithm to minimize 11 different functions and 7 constraints to get Pareto optimal solutions.(4) The analysis of the correlations between objective functions and comparative analyse of the D-GMM-BS, D-GMM-BFS and MOEA by experiment show that the minimum values for each function calculated by D-GMM-BS algorithm are equal or very close to that of GMM-MOEA. The time complexity of the BS algorithm is polynomial time,but the GMM-MOEA is nondeterministic polynomial algorithm A correlation analysis between each pair of objective functions was also performed to get an idea of the real necessity of using (or not) that large a number of objective functions.A very large correlation clearly means that if one objective function is optimized, another one with a high correlation is also indirectly optimized.(5) The D-GMM-BS algorithm can get more solutions than BFS. Furthermore, Time and space efficiency of the BS algorithm are better than those of BFS algorithm.