Concepts of exact QoS routing algorithms

The underlying concepts of an exact QoS routing algorithm are explained. We show that these four concepts, namely 1) nonlinear definition of the path length; 2) a k-shortest path approach; 3) nondominance; and 4) look-ahead, are fundamental building blocks of a multiconstrained routing algorithm. The main reasons to consider exact multiconstrained routing algorithms are as follows. First, the NP-complete behavior seems only to occur in specially constructed graphs, which are unlikely to occur in realistic communication networks. Second, there exist exact algorithms that are equally complex as heuristics in algorithmic structure and in running time on topologies that do not induce NP-complete behavior. Third, by simply restricting the number k of paths explored during the path computation, the computational complexity can be decreased at the expense of possibly loosing exactness. The presented four concepts are incorporated in SAMCRA, a self-adaptive multiple constraints routing algorithm.