Exact Algorithms for Multi-Constrained QoS Routing

Free registration required

Executive Summary

The modern network service of finding a feasible or an optimal path subject to multiple constraints on performance metrics such as delay, jitter, loss probability, etc. gives rise to the Multi-Path Constrained (MCP) or Multi-Constrained Optimal-Path (MCOP) QoS routing problems, which are NP-complete. In this paper, these problems are solved through exact algorithms. Even though exact algorithms may not be used in practical applications, they are necessitous for evaluating the quality of other heuristics. The proposed exact algorithms are based the linear Lagrange relaxation technique, i.e., an aggregate weight is constructed first and then a loopless K-shortest-path algorithm is employed to find a feasible or an optimal solution.

  • Format: PDF
  • Size: 166.2 KB