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

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