可分离QoS路由的拉格朗日松驰算法

为了满足网络新应用提出的服务质量保证和业务不受故障影响的新要求,分析了可分离的QoS路由算法.针对寻找优化某个QoS参数且另一个QoS参数满足约束条件的可分离路由问题,建立了问题的数学模型,利用拉格朗日松驰算子将问题分解为两个受限最短路问题,给出了求解的拉格朗日松驰算法,并从迭代方向和迭代步长两方面对算法中的次梯度技术进行了改进.算例表明,改进后的算法具有较快的收敛性能.

Lagrangean relaxation algorithm for disjoint QoS routing

In o rder to sati sfy the needs of Qo S( quali ty o f service) and surv iv abi li ty o f the netw o rk, a n algorithm fo r di sjoint Qo S routing w as studied. It is a N P problem to find tw o disjoint pa ths tha t sati sfy oneQo S meter and optimi ze a no ther Qo S meter. The mathematics model o f the problem w as establi shed whichcould be div ided into tw o rest ricted shor test paths by Lagrangean multipliers. The Lag rang ea n relax ationalg orithm w as presented to solv e the mathematics model. A modi fied itera tion di rectio n and step leng thw ere proposed to improv e the computational ef ficiency of subg radient techno logy in the algo ri thm. Finallythe examples demo nst ra ted the va lidi ty o f the alg orithm