| With fast development of network technologies, increase of network bandwidth and processing power makes the network provide more multimedia applications, and also makes the multicast communication that supports "one-to-many" or "many-to-many" become a necessary mode of multimedia services. A fundamental issue in multicast communication is how to determine an efficient multicast routing, and finding simple, effective and robust multicast routing algorithms is unsolved problem in network fields. In addition, many distributed multimedia applications have various demands on delay, delay variation, bandwidth and packet loss, which requires current network to transmit real-time multimedia information with these quality-of-service (QoS) constraints. So, as an indispensable component in a QoS-centric network architecture, research on multicast routing algorithms based on QoS constraint becomes an important part and hotspot issue of network research fields.This dissertation concentrates on researching multicast routing algorithms with QoS constraints, proposes several simple, effective and practical QoS multicast routing heuristic algorithms to solve some classical multicast routing problems with NP difficulty. Generally, the main achievements in this paper are as follows:(1) Develop a versatile, simple, and open QoS routing simulator (QRSIM), which provides a real and exact simulator platform for evaluating performance of proposed QoS routing algorithms. Also, as long as user presents new QoS routing algorithms programming according to standard interfaces, QRSIM can dynamically load these routing algorithms to simulate.(2) Propose four delay-constrained multicast source routing algorithms to solve delay-constrained least-cost multicast routing problem. LRDLMA makes use of the characteristic of Lagrange relaxation method, and finds multicast tree satisfying constraint by constructing closure graph and using Prim algorithm to make relaxation to this graph. A large number of simulations demonstrate that cost performance of the algorithm is close to BSMA algorithm whose performance is best, and it has characteristics of stable delay and quickness. TSESMA and TSPSMA algorithm are two routing algorithms based on Tabu search, and they take different approach to construct neighbors. TSESMA isbased on "edges-switching", and TSPSMA uses "paths-switching" strategy. Simulations show that two algorithms performs stable performance, high reliability, rapid convergence and reduce computing time. TSPSMA performs excellent performance of cost, and its cost is lower than BSMA algorithm's, which can improve network efficiency and optimize network resource. LODMA algorithm begins from a least-delay tree, then gets final multicast tree satisfying delay constraint by using "link optimizing" strategy. This algorithm has faster execution time and lower delay than other heuristics, and it is fit for those real-time multimedia applications with higher delay demands.(3) Apply the simulated annealing to multicast routing, and propose a multicast routing algorithm (SABDMA) based on simulated annealing to solve delay and delay variation constrained least-cost multicast routing problem. To avoid enlargement of search area and increase of computing time, SABDMA uses "paths-switching" strategy, which constructs neighbor set in the range of feasible solutions according to the relationship between delay and delay variation. Simulations demonstrates that the algorithm has characteristics of feasibility, stability and rapid convergence, and it can effectively construct multicast tree with lower cost according to QoS request, and has better real-time property.(4) Study many-to-many multicast routing problem and propose two heuristic algorithms to solve delay-constrained multiple-shared multicast tree problem: SCA algorithm and distributed heuristic algorithm DISA. The simulations show SCA algorithm consumed smaller run-time than others, without increasing number of centers. DISA algorithm has the best performance o...
|
PDF Full Text Request