Search space reduction in QoS routing
Liang Guo, Ibrahim Matta · 2003
To provide real time service, integrated networks require the underlying routing algorithm to be able to find low cost paths that satisfy given Quality of Service (QoS) constraints. The problem of constrained shortest (least cost) path routing is known to be NP hard, and some heuristics have been proposed to find a near optimal solution. However, these heuristics either impose relationships among the link metrics to reduce the complexity of the problem which may limit the general applicability of the heuristic, or are too costly in terms of execution time to be applicable to large networks. We focus on solving the delay constrained minimum cost path problem, and present a fast algorithm to find a near optimal solution. This algorithm, called DCCR (Delay-Cost-Constrained Routing), is a variant of the k-shortest path algorithm. DCCR uses a new adaptive path weight function, together with an additional constraint imposed on the path cost, to restrict the search space. Thus, DCCR can return a near optimal solution in a very short time. Furthermore, we use the method proposed by D. Blokh and G. Gutin (1995) to further reduce the search space by using a tighter bound on path cost. This makes our algorithm more accurate and even faster. We call this improved algorithm SSR+DCCR (Search Space Reduction+DCCR). Through extensive simulations, we confirm that SSR+DCCR performs very well compared to the optimal but very expensive solution.