基于带宽和时延约束的服务质量任播路由算法

QoS Anycast Routing Algorithm Based on Bandwidth and Time Delay Constraints

为在满足带宽需求的前提下找到时延最短的任播路径集合,研究基于带宽和时延两个约束度量的服务质量任播路由算法。为解决带宽和时延约束问题,提出一个适用于该非确定性多项式问题的多项式时间近似优化算法。仿真结果表明,当网络规模增加或客户带宽需求较大时,该文算法时延增加相对较小,因此具有较好的可扩展性和健壮性。与包括最短路径优先任播路由算法和最大带宽优先任播路由算法的启发式算法相比,在带宽受限大型网络中该文算法具有更好的性能优势。

To find a set of anycast routing paths satisfying both the bandwidth requirement and the shortest time delay, a quality of service anycast routing algorithm with bandwidth and time delay constraints is researched. A polynomial time approximation scheme suitable for the nondeterministic polynomial problem is proposed to solve the problems of bandwidth and time delay constraints. Simulation results show that：while the network scale or bandwidth requirement grows, the increase of time delay of this algorithm is little so that it is sealable and robust. Compared with heuristic algorithms such as the shortest path first anycast routing algorithm and the maximum bandwidth path first anycast algorithm, this algorithm has better performance advantages in bandwidth-limited largesize networks.