Research On Delay-constrained Multicast Routing Algorithm

With the development in Internet technology, a lot of multimedia applications suchas video on request, teleconference, online education, netgame have been used more andmore widely, and the requirements of quality of services(QoS) is also higher. In order tomeet the real-time multimedia service demands, multicast technology is put forward.Multicast technology is a kind of communication mechanism that can transfer the samedata from one node to a large of nodes simultaneously. It could solve the problem ofquality of services bottlenecks of the multimedia communication which includes delay,bandwidth, and cost in a certain extent.The core issue of multicast routing problem is the constraint multicast routingproblem, and the core issue of the constraint multicast routing problem isdelay-constrained multicast routing problem which is to find a low-cost multicast treeon the premise of the delay-constrained. The issue of the delay-constrained multicastrouting is a NP completed problem which can not be solved in polynomial time. Inorder to reduce the time of solving NP completed problems, heuristic algorithm hasbeen used to solve the NP completed problem instead of accurate algorithm. Specific tothe delay-constrained multicast routing problem with one source node, this paperpresents a dynamic algorithm of the delay-constrained multicast routing. This algorithmis divided in two parts，one is static part and the other is dynamic part. By consideringthe connection between construction of initial multicast tree and update the tree whenmulticast nodes move, the algorithm can reduce the total time. This algorithm is notonly suitable for the problem of static delay-constrained multicast routing, but alsoappropriate for the problem of dynamic delay-constrained multicast routing.The main content of this paper has been summarized as follows:①Introduces the background of multicast technology, research status, workingprinciple, implementation model, relevant protocols and classification of algorithms.②Analyzes the multicast routing problem with no constrained(aim at steiner treeproblem) and compares some classical heuristic algorithms.③Illustrates the mathematic model of the problem of Steiner tree, some commondefinitions and explains the connection between the static delay-constrained multicastrouting algorithm and the dynamic delay-constrained multicast routing algorithm.④On the basis of the connection between the static delay-constrained multicast routing algorithm and the dynamic delay-constrained multicast routing algorithm,presents a new dynamic delay-constrained multicast routing algorithm,. The newalgorithm is divided in two parts, static part and dynamic part. The static part whichactually is a static delay-constrained multicast routing algorithm is to construct an initialmulticast tree. This part not only improves the existing path selection function, but alsoput in frequency of key node. On the basis of static part, the dynamic part is to updatethe ordinary multicast tree when multicast nodes join or leave. The dynamic partimproves the handling method of forwarding node leaving and reduces the time ofconstructing a multicast tree by sharing the frequency of key node. The simulationresults show that on the premise of not increasing the cost of the multicast tree, the newalgorithm takes less time and it is suitable for larger network.