Research On Multi-Constrained Application Layer Multicast Algorism

The network layer multicast can implement one-to-many data delivery in a much more efficient way than unicast and significantly improved the using efficiency of network resource. However, the traditional network layer multicast technology has many problems such as the expansion of routing forward states and high deployment cost, which largely influenced the application of multicast. All kinds of solutions have been proposed, which have changed the situation in a better way, but never solved these problems ultimately. Under this situation, the application layer multicast is proposed. Application layer multicast implemented the multicast forward on application layer, ultimately solved the forward state problem of network layer multicast. In recent years, application layer multicast is widely deployed in applications such as video conference, network television, video communication, network flow media etc. However, along with the improvement of the user requirement, the application layer multicast technology has shown some weak points too, such as large end-to-end delay, node overload, the unstable forward network, which have become obstacles of the application layer multicast.This paper has concluded all kinds of performance measurements of application layer multicast and the influence they have to the multicast quality. What's more, we compared all kinds of application layer multicast algorism models and decided to use degree- and delay- constrained minimum spanning tree(DDCMST) as the algorism model of the application layer multicast. This model constrained two of the most important measurements: end-to-end delay and node degree. It can improve the quality of multicast forward; keeps the multicast delay in the acceptable range. The model regards the cost of the spanning tree as the optimizing target, can satisfy the requirement of the user and save network resource at the same time, which is very helpful to the deployment of application layer multicast.Based on the analysis of the DDCMST problem, we proved it is a NP-Complete problem, and proposed a new solution using particle swarm optimization (PSO) algorism. PSO is a new kind of swarm intelligence algorism. The basic idea of PSO is from the information sharing and influence between individuals during the food hunting activities of the bird flock. The iterative process of the algorism demonstrates the connection between optimization process of the team and the experience exchanging process.At the beginning, PSO algorism is mainly used in the solving of the non-linear functions. The PSO algorism cannot solve combinational optimization problems like DDCMST directly. Based on the basic idea of PSO algorism, we changed the standard PSO algorism, including the generation of the random solutions, the refresh of the speed vector, the transformation of the spanning tree and the circle truncation and so on, successfully solved DDCMST problem using PSO algorism and then concluded a novel application layer multicast routing algorism. This algorism inherited the advantages of PSO algorism which has good scalability and fast convergence. It is very good at solving large scale multicast routing problems.The PSO based algorism proposed in this paper is not only good at solving DDCMST problem. It can be used in solving all kinds of constrained spanning tree problems. The only change need to make is to change the fitness functions according to different constrains. Based on this idea, we proposed another two PSO based algorisms which respectively solve the degree-constrained minimum spanning tree problem and the leaf-constrained minimum spanning tree problem.In the experiment, we implemented the simulation program of the application layer multicast algorism proposed in this paper and two other strategies based on ant colony and generation algorism and compared them with our strategy. The experiment result has shown that, the algorism proposed in this paper has good advantages on end-to-end delay, spanning tree cost, node degree and convergence time. Especially on large scale topology, the advantage become larger, this has shown good stability and scalability.