关键词: 组播路由, Steiner树, MPH算法, 时延约束, NPcomplete

Abstract: Multicast routing algorithm has received considerable attention from researchers in computer communication. In most conditions, it is NPcomplete and defined as a Steiner tree problem. In order to optimize cost and decrease time complexity with a delay upper bound, the delayconstrained Steiner tree problem is addressed. Time complexity of minimum path heuristic (MPH) algorithm is analyzed firstly, and then a delayconstrained leastcost (DCLC) multicast routing algorithm called DCMPH is presented to construct DCLC multicast tree. With DCMPH a computing member node can join the multicast tree by selecting the path whose cost is the least to the existing multicast tree; if the path’s delay destroys the delay upper bound, the leastdelay path computed by shortest path tree (SPT) algorithm is used to take the place of the leastcost path to join the current multicast tree. By this way, a lowcost multicast routing tree can be constructed and the delay upper bound isn’t destroyed. The correctness of DCMPH is proved by mathematical induction and the time complexity is analyzed in theory. Simulation results show that DCMPH is highperformance in constructing DCLC multicast routing tree and has a lower time complexity than many other DCLC multicast routing algorithms.

Key words: multicast routing, Steiner tree, minimum path heuristic, delayconstrained, NPcomplete