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

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