A fast approximation scheme for the multiple constraints routing problem

Finding a path between a source-destination node pair that satisfies two or more end-to-end constraints is a fundamental problem in Quality-of-Service (QoS) routing. To the best of our knowledge, it is NPhard and has no solution in polynomial time. Different from existing algorithms, a fast approximation scheme (FAS) was proposed in this paper, at finding such a path for multiple constrained optimal paths (MCOP) problem. By analyzing the proposed algorithm theoretically, the presented FAS can find an approximation path with the ratio of (1+Ε) and the time complexity O (mQK-1) (where m is the number of edges, Q is the positive real number and K is the number of constraints) in the network, which outperforms the previous best-known algorithm for MCOP. Copyright © 2015 Binary Information Press.