一种基于拉格朗日松弛法的QoS路由算法

本文提出了一个新的QoS路由算法,可以有效地求解延时约束条件下的最小代价问题。算法以拉格朗日松弛法为基础,将链路代价参数吸收到延时参数中,同时在迭代过程中结合延时约束条件,可以在多项式时间内找到一个较优解,并对该算法进行了分析和仿真,结果表明该算法比其它一些同类算法在性能上有较大的改善。

A QoS Routing Algorithm Based on Lagrange Relaxation Method

A new QoS routing algorithm is proposed. It provides a solution to the delay constraint least cost routing problem efficaciously. The algorithm is based on Lagrange Relaxation Method. By absorbing the cost of link into the delay measure and taking the delay constraint into account on each iteration process, a path can be found in polynomial time and the cost metric of the path is close to the optimal solution. Some related theorem has been given and proved in the paper. The result of simulation shows that t...