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/spl I.bar/MCOP, which is based on a nonlinear Lagrange relaxation (NLR) technique, has been proposed to resolve the contradiction between the time complexity and the quality of solution. Even though H/spl I.bar/MCOP has demonstrated an outstanding capability of finding feasible solutions to the multipath constrained (MCP) problem, it has not exploited the full capability that an NLR-based technique could offer. We propose a new NLR-based heuristic, called NLR/spl I.bar/MCP, in which the search process is interpreted from a probability perspective. Simulation results indicate that NLR/spl I.bar/MCP can achieve a higher probability of finding feasible solutions than H/spl I.bar/MCOP. We also verify that the performance improvement of an MCP heuristic has a tremendous impact on the performance of a higher level heuristic that uses an MCP heuristic as the basic step.
['Gang Feng']
The revisit of nonlinear Lagrange relaxation based QoS routing