基于拉格朗日松驰的多约束QoS路由算法

提出了一个有效的求解多约束的QoS 路由算法, 该算法使用拉格朗日松弛求解满足两个以上约束条件下的最小代价QoS 路径。在求解拉格朗日松弛的过程中, 提出了一种适用于网络结构的迭代方法, 能够快速有效地搜索到可行路径。该算法是一个伪多项式时间的算法, 比较仿真实验结果, 发现算法的搜索成功率不仅与约束数目拓扑大小有关, 还与拓扑类型有关, 对于与现实情况接近的网络拓扑, 其搜索成功率比较高。

Method for Multi-constraint QoS Routing Problem Based on Lagrange Relaxation

With the multi-constraint QoS routing algorithm, least cost QoS routing path satisfying two or more constrained conditions can be found based on Lagrange Relaxation. During this procedure, a method of overlap fit for network structure is proposed, thus the feasible path can be searched rapidly. This algorithm is a pseudo polynomial time algorithm, and comparing with the simulated results, the success rate of searching is not only related with the constraint number but also with the type of topology, and the more closer the network topology is to the real network, the more successful rate of searching reaches.