Research On Degree-constrained QoS Multicast Routing Algorithm

As the rapid development of the Internet, there are more and more new applications of multimedia real-time business such as video conference, remote education etc. But the Quality of Service of traditional media streaming service system which is made of Client/Service model is constrained by the performance and bandwidth of service. For solving this problem, P2P emerges as the times require. P2P can well solves the existing problems such as lack of the server's processing ability, overweight of network bandwidth in media streaming transport, and so on. The QoS multicast routing in P2P network becomes much more important research topic.This paper finds the importance of degree constraint in multicast routing by studing multicast routing technology and algorithm. On this basis, it proposes the mathematic model of degree-constrained multicast routing problem by analyzing satisfactory optimization theory and some dependent key problems. The model considers constraints of bandwidth, delay, delay jitter and packet loss rate. Its optimal goal is satisfaction evaluation function of the performance and to seek a multicast tree which meets the degree-constraint. In the light of the disadvantage of heuristic search algorithm, and the complexity of QoS multicast routing problem with degree-constraint, the paper introduces Genetic Algorithm, which is good for solving this kind of complex class distinction NP-Complete problem. On this basis, the paper proposes a Genetic Algotirhm which issues the 2-dimensional coding method. So the chromosome containing the connection information can display the node's degree information directly, which is useful to judge whether the router can satisfy the constraint of transmitting ability. The Genetic Algorithm uses the strategy of holding the same link of parent chromosome to avoid the production of illegal individual, and the 2-dimensional coding method is easy to search the same path. In addition, because there is high requirement of real-time in QoS multicast routing algorithm, the algorithm's termination condition is that there is a multicast tree in the population according with QoS constraint condition. In the end, the comparison of the multicast tree between the model with degree-constraint and the model without degree-constraint proves the importance of considering the degree-constraint.In the simulation experiment, it can be seen that the algorithm can not only get the solution which satisfies the constraints, but also the solution is good performance with fast convergence speed. The algorithm possesses smaller time complexity, and is suitable for development environment of large scale P2P network. The algorithm stresses on the problem of multicast routing, so it can be used in the routing which is degree-constrained and with high requirement of real-time.