Studies On Multicast Routing Algorithms

With recent advances in high-speed communication network the demand for providing more multi-media applications is increasing. Many of these applications require networks to provide multicast. These applications,for instance,can be audio/video conference,distributed simulation,multi-user game,distributed database.Network resources and network nodes' processing ability will be wasted dramatically,thus it may result in network congestion if multicast is realized by sending packet copies to every destination individually. Hence,to realize multicast communication,the packets usually are transmitted along a multicast tree which is constructed by multicast routing algorithms. Therefore,it is very important to research efficient multicast routing algorithms. This dissertation concentrate on research multicast routing and relevant center selection problem after the background of multicast communication and on-researching problem are discussed.Firstly,the heuristic for calculate the Steiner tree is researched. After analysis of existing heuristic,four new heuristics for solve Steiner problem which are KBMPH(Key-Node Based Minimum cost Paths Heuristic) algorithm,KBMPH,algorithm,KDDMC(Key-Node and Destination Driven Multicast routing) algorithm and WDDMC (Weighted Destination Driven Multicast Routing)algorithm are presented. The main idea of KBMPH and KBMPH] is based on key nodes which more paths pass through. In KBMPH,key nodes is calculated according the paths between all nodes in a network while key nodes of KBMPH! is calculated according the paths between nodes only including source and destinations. By modifying the cost of paths which include at least one key node,these paths will be added to the tree with some priority,therefore this results in more link share during constructing multicast tree and finally the cost of whole multicast tree drops. Simulation results show that the cost of KBMPH and KBMPHi is lower than that of MPH(Minimum cost Paths Heuristic) algorithm. KDDMC is a key-node and destination driven multicast routing algorithm. Also multicast routing with low cost is achieved through using some paths including key nodes with priority to share some links. WDDMC combine DDMC algorithm,Dijkstra algorithm and Prim algorithm together by adjusting the coefficient. The cost of multicast tree can be decreased by choosing appropriate coefficient. Simulation results show KDDMC is the best and WDDMC is superior to DDMC on cost performance. The complexity of WDDMC is identical to DDMC. The time complexity of KDDMC andKBMPH is higher. The time complexity of KBMPH,is the same as MPH.Secondly,QoS constrained Steiner tree problem is studied. One of constrained problem is delay constrained Steiner tree problem. A heuristic DBMA(Delay-Bounded Multicast routing Algorithm) based on minimum delay path set and minimum cost path set is proposed. Simulation result demonstrate that it is a delay constrained algorithm with low time complexity and low cost. Another constrained problem is delay and delay variation constrained multicast routing problem. SP-DVMA(Shortest Path Delay Variation Multicast Algorithm) algorithm based on minimum delay path is presented. The time complexity is low because only shortest paths connected to relay nodes is compared. Simulation results show that fairly good cost performance is achieved. There is trade-off between complexity and performance. The delay and delay variation constrained minimum Steiner tree problem is also researched. LCDVMA(Low-Cost Delay Variation-constrained Multicast Algorithm) is proposed for this problem. Low time complexity,low cost and constrained delay and low delay variation are achieved by only comparing minimum delay paths and minimum cost paths. Simulation results also are given.Thirdly,we involved in research dynamic multicast algorithm. At first,various existing dynamic multicast routing algorithms with no constraint is compared. A dynamic multicast algorithm DPG (Dynamic Prim-Based Greedy multicast algorithm) which is based on minimum span tree is p...