Highly responsive and efficient QoS routing using pre- and on-demand computations along with a new normal measure

Multi-constrained path (MCP) selection is one of the great challenges that QoS routing (QoSR) faces. To address it in an efficient and highly responsive manner, we propose a new QoSR algorithm, namely NM_MCP (normal measure-based multiple constrained path). Using the Dijkstra’s algorithm with respect to each link metric, NM_MCP pre-computes k primary paths in advance, where k is the number of link weights. When a routing request arrives, NM_MCP executes a modified version of the Dijkstra’s algorithm using a newly proposed, normal-measure-based nonlinear cost function. Extensive simulations show that NM_MCP achieves higher success rate in finding feasible paths with less computational cost than existing algorithms. To further improve the performance, we incorporate Pareto and nonlinear look-ahead mechanisms into the algorithm.