Research On QoS-guaranteed Multicast Source Routing Algorithms

Multicasting is widely used in various applications. To the muliticast application with strict realtime required, multicast routing must guarantee the quality of service. Accordingly, in this thesis, we do research on the problem of multicast routing with QoS quaranteed.As to multicast routing, the matter is to find a tree from the network covering the multicast source node and all destination nodes. In order to guarantee the quality of service, the tree must satisfy the QoS requirements. The problem to construct minimum cost multicast tree is NP-complete, but, many feasible heuristics have been invented to produce solutions for multicast tree construction. In these heuristic algorithms, some have a good performence in the cost of multicast tree, but their computational complexities are very high; On the contrary, some have acceptable complexities, but the performence is bad in constructing low-cost multicast tree. Based on these existing algorithms, this thesis presents several new multicast source routing algorithms, and tries to balance between the complexity and the performance of the algorithm.Firstly, we analyze the limitation of KPP multicast routing algorithm, and make some improvement upon KPP algorithm, then present a new multicast routing algorithm to minimize the cost of multicast tree. It is proven that this new algorithm can find a satisfactory routing tree as long as it exists. Experiment results show that comparing to KPP, the cost of multicast trees generated by the new algorithm is less than the cost of multicast trees generated by KPP,and the decreased cost is from 9% to 10%.Secondly, we introduce a new concept of link shareability as heuristic information, and present a multicast routing algorithm SBMR to minimize costs with delay constraint. Experiment results show that comparing to KPP, multicast trees generated by SBMR are 72% better than that generated by KPP with 13% decrease of cost, and 9% less links invoked. On the other hand, SBMR generates multicast trees also better than DCSP with the probability 82%, 15% decreased costs of the network, and 11% less links to be shared on an average. However, the CPU time increases 28% as a penalty in this case.