Link-disjoint QoS routing algorithm

Finding the link-disjoint path pair with respect to a number of additive constraints is a key issue of QoS routing. This paper presents and evaluates a new algorithm based on Lagrangian relaxation framework for this problem. Under the Lagrangian relaxation framework, the algorithm relaxes all the additive constraints and reduces the original problem to an unconstrained link-disjoint routing problem, which is a well-known tractable problem and can be solved efficiently. Furthermore, a series of heuristic steps have been incorporated into the traditional Lagrangian framework, which can achieve better performance of the solutions. Our simulations show that the proposed algorithm not only performs better than existing algorithms in terms of the rate of success in finding the feasible path pair, but also can achieve solutions which are close to the optimal solutions solved by commercial ILP solvers.