一个时延约束的动态组播路由算法

分析了时延约束的动态最小代价组播路由问题，然后基于贪婪思想设计了一个动态组播树生成算法DCDG（Delay—Constrained Dynamic Greedy Algorithm），用于在动态环境下构造时延约束的低代价组播树。该算法通过节点动态贪婪地选择满足时延约束的最短路径加入组播树来降低代价；若时延不满足要求，则通过合并DDSP（Destination-Driven Shortest Path Algorithm）最小时延路径来产生一个满足时延约束的低代价组播树。仿真实验表明：DCDG算法动态生成的组播树代价较低、性能稳定，而计算复杂度仅为O（n）；在严格的时延约束下会话成功率高。

A Delay-Constrained Dynamic Algorithm for Multicast Routing

The issue of the delay-constrained multicast routing under dynamic environment was addressed firstly, and then a delay-constrained dynamic greedy algorithm (DCDG) was proposed to construct a serial of dynamic multicast trees based on the greedy strategy. By DCDG, a computing destination node can join the multicast tree by selecting the path which meets the delay requirement and has the least cost value to the existing multicast tree; if the path delay destroys the delay upper bound, the path based on the destination-driven shortest path algorithm (DDSP) will be merged into the existing tree to construct a multicast tree. The simulation results show that DCDG has a high performance in constructing low-cost dynamic multicast routing trees with a very low computing complexity of O(n). And more, it can achieve a high success ratio under strict delay constrain.