新的群播路由算法

考虑了费用非对称通信网络上的群播路由问题。首先提出了一种满足带宽约束接近最小成本的启发式算法NEW1-GM算法。该算法以FMPH算法(FastMinimumPathCostHeuristicAlgorithm)为基础,可以有效地降低成本。数值实验表明,这种算法是有效的,且所获得解的总费用几乎总是小于或等于由GTM算法所获得的解的总费用。然后,提出了一种满足延迟约束的DFMPH算法(Delay-ConstrainedFastMinimumPathCostHeuristicAlgorithm)。最后,在NEW1-GM算法和DFMPH算法的基础上提出了一种不仅满足延迟和带宽要求且接近最小成本的启发式算法DGM1算法。NEW1-GM算法和DGM1算法的时间复杂度均与GTM算法相同,为O(p3n2)。

Algorithm for Group Multicast Satisfying QoS

In this paper,we consider the Group Multicast Routing Problem(GMRP) in cost-asymmetric communication networks.Firstly,a heuristic algorithm based on the Fast Minimum Path Cost Heuristic Algorithm(FMPH),namely NEW1-GM,is presented.It can reduce cost effectively.The simulation results show that the algorithm is effective.Then,a delay-constrained multicast algorithm,the Delay-Constrained Fast Minimum Path Cost Heuristic Algorithm(DFMPH),is presented.At last,another heuristic algorithm(DGM1) based on NEW1-GM and DFMPH is presented,which can find a set of sub-optimal cost multicast trees satisfying delay and bandwidth constraints.NEW1-GM and DGM1 have the same time complexity O(p(?)n(?)) as GTM.