Lagrange Relaxation-Based Method For Constrained Least-Cost Multicast Routing

At present, the best-effort service is the one only transmitting model which is applied in the Internet, but this can not meet quick developing of multimedia and different requirements of the network's transmitting quality. As a result, QoS(Quality of Service) manipulative technology which is used to improve the utilizable rate of network resource and quality of service for users was born, and QoS based multicast routing technology is one of the most important key technologies for multimedia information's transmitting on network.Multicast is a network communication technology with sending single data copy from source node to many nodes which belong to a given group. Constructing a multicast tree for network helps to realize multicast communication, and the QoS based multicast routing algorithm is a useful way to construct a multicast tree which meet requirements of QoS. So this dissertation will focus on QoS based multicast routing algorithm.The principle of multicast technology and multicast routing is analyzed in this dissertation, and the basic principle of Lagrange Relaxation algorithm is also presented. Analyzing several typical QoS constrained multicast routing algorithms, those algorithms' shortages are pointed out and an algorithm named Lagrange Relaxation Based Method for Delay-constrained Least-cost Multicast Routing (LR-DLMR) is presented. This new algorithm has following characteristics:(1) It does not construct a complete closure graph for original graph, so it avoid the problem that is caused by the complete closure graph and it uses information of the nodes on link effectively.(2) It has good expansibility. In order to compare with other algorithms, it is only delay-constrained, and adds the delay-constrained qualification to the linear function to do Lagrange Relaxation. Similarly, it can add bandwidth-constrained, packet-losing rate-constrained and other qualifications to the linear function.(3) Its efficiency lies on the least-cost multicast routing algorithm that is used, which means that it has a long vitality. If a new more excellent least-cost multicast routing algorithm is invented, the new algorithm can be used in it.(4) It is adjustable. User can set a specific iterative number to request the algorithm to return a multicast tree in the time. And user can also set a parameter ε which is positive real number to request the algorithm to return a multicast tree when the cost margin between two trees is less than the parameter ε.By academic analyzing and proving, the worst time complexity of this algorithm is only O(p(m+3/2)n~2 -pm~2n), n is network's size, m is destination group's size, and p is iterative time. By simulated experiment and the result, it demonstrates that LR-DLMR is better than KPP and close to the cost-best algorithm BSMA on cost performance; and LR-DLMR is better than BSMA and similar to KPP on time performance, so the presented algorithm is very practical.