Guarantee Quality Of Service Multicast Routing Algorithm

With the fast development of computer and network technology, network applications have changed from the simple exchange of information to the development of distance learning, video on demand, web conferencing, data distribution and network games. These applications not only require network support multicast services, but also have a higher demand for the quality of service (QoS). A key issue in multicast communication is the realization of the multicast routing algorithm, is just how to construct a tree, which covers multicast source and all destination nodes and meets the requirements of the application of quality of service.To support real-time multicast communications, computer networks have to guarantee an upper bound on the end-to-end delay in order to ensure information conveyed to each receiver in time. Meanwhile, to ensure that every user can receive information at the same time, end-to-end delay variation must be constraint. Therefore, study the delay and delay variation limited multicast routing algorithm, which can not only guarantee the quality of service, but also to promote the development of real-time multimedia applications is of great significance. Therefore, this paper raised two heuristics about delay and delay variation issues.First, about the delay bound multicast routing problem DCLC, proposed a delay constraint Steiner tree algorithm DBLC. The algorithm is based on the MPH algorithm, each destination node joins the multicast tree by smallest cost path; if the delay does not meet requirements, then use improved P(s,t,Δ) algorithm to join multicast tree, resulting in a minimum cost multicast tree which meets the delay constraints. Correctness and performance of the algorithm are analyzed in theory. At the same time, simulation experiments prove that: DBLC algorithm construct a multicast tree with better performance and lower cost complexity compared with the similar method without breaking the delay upper bound.Second, about delay and delay variation multicast routing problem DVBMT, proposed a delay and delay variation constraint Steiner tree algorithm DVMC. By example analysis can get that delay and delay variation in DVBMT model are contradicted, and find the relationship between the every path delay and the two constraints. DVMC algorithm derives from the k shortest path in DVMA algorithm, exploring of a similar greedy algorithm, using the maximum delay of each path as delay bound of the current constructed multicast tree, choosing path using a function based on the maximum delay of each path and cost of the links, therefore, generating a multicast tree with delay and delay variation meet constraints and minimum cost. Correctness and performance of the algorithm were analyzed in theory. Simulation experiments prove that: DVMC spanning tree algorithm has obvious advantages in the cost, success rate and complexity.