Research On Delay-constrained Multicast Routing Algorithms

With the development of computer network technology, a variety of multimedia applications, such as audio / video conferencing, interactive simulation, online games, online stock trading, come into existence and become more and more popular in the network. Multicast technology, which transmits the same data from a source to a large number of destination nodes simultaneously, in order to save a great deal of bandwidth and reduce data redundancy in the network, can resolve the problem of bandwidth bottlenecks of the multimedia communications in a certain extent, and will become an important technology in the future.The core issue of multicast communications is multicast routing problem, i.e. how to construct a least cost tree from source to all the destination nodes. As most multimedia applications require real-time transmission, this thesis studied the delay-constrained multicast routing problem, classified existing delay-constrained multicast routing algorithms according to the ideas and the ways to realize, analyzed the typical algorithms of each category , compared the complexity, and pointed out the advantages and disadvantages of them.On this basis, the paper presented a fast low-cost delay-constrained multicast routing heuristic, called FLCH-S, which added end-to-end delay constraints to a non delay-constrained multicast routing algorithm FLSPT and was only suited to the static multicast group. Simulation results show that the multicast tree constructed by FLCH-S is capable to satisfy real-time requirements of multimedia multicast applications, the algorithm has good cost performance, low computational complexity, and is more suitable for the dense mode, that is, multicast destination nodes are densely distributed in the area.It's usually to encounter dynamic group membership in practical multicast applications. Adopting the idea of Greedy algorithm, the presented Dijkstra's Shortest Path based delay-constrained dynamic multicast routing algorithm, DSPH-D, finds a path, which is not only delay-constrained but also adds minimal cost to the original tree, for the joining node. The simulation results show that the algorithm has good cost performance, appropriate computational complexity, and is able to maintain stability in a long time.Finally, the random network generation algorithm was improved, and the...