The revisit of QoS routing based on non‐linear Lagrange relaxation

The development of efficient quality of service (QoS) routing algorithms in a high‐speed networking or the next generation IP networking environment is a very important and at the same time very difficult task due to the need to provide divergent services with multiple QoS requirements. Recently, a heuristic algorithm H_MCOP, which is based on a non‐linear Lagrange relaxation (NLR) technique, has been proposed to resolve the contradiction between the time complexity and the quality of solution. Even though H_MCOP has demonstrated outstanding capability of finding feasible solutions to the multi‐path constrained (MCP) problem, it has not exploited the full capability that an NLR‐based technique could offer. In this paper, we propose a new NLR‐based heuristic called NLR_MCP, in which the search process is interpreted from a probability's perspective. Simulation results indicate that NLR_MCP can achieve a higher probability of finding feasible solutions than H_MCOP. We also verify that the performance improvement of a MCP heuristic has a tremendous impact on the performance of a higher level heuristic that uses a MCP heuristic as the basic step. Copyright © 2006 John Wiley & Sons, Ltd.