基于信源路由的时延受限点到点路由算法

Source-Based Delay-Constrained Unicast Routing Algorithms

本文研究了网络路由中的一个NPC问题 :时延受限最小代价路由问题 .文中提出了一个理论框架 ,并给出了多个简单有效的启发式算法 ,在满足给定时延约束条件可行路径存在时 ,算法总能找到满足约束条件的代价优化路径 .文中提出的启发式算法复杂性为O(|V|2 )且在线复杂性为O(|V|) .仿真显示算法取得了良好的平均代价性能 .

We study the NP-hard delay-constrained least-cost routing problem. We propose a new framework to solve the problem and provide simple and efficient source routing heuristics from the model, through which one can always find a delay-constrained path if such a path exists. Computation complexity of our heuristics is O(|V|2) and on-line complexity is O(|V|). Simulation results show that our heuristics achieve good cost performance. Finally, we extend the model to routing problem under multiple QoS constraints.