Title: Search Space Reduction in QoS Routing
Authors: Liang Guo and Ibrahim Matta
Date: October 8, 1999
Abstract:
To provide real-time service or engineer constrained-based paths,
networks require the underlying routing algorithm to be able to find
low-cost paths that satisfy given Quality-of-Service (QoS)
constraints. However, 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. In this paper, 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 (for 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 Blokh and Gutin 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
(for Search Space Reduction+DCCR). Through extensive simulations, we
confirm that SSR+DCCR performs very well compared to the optimal but
very expensive solution.
* This technical report revises TR NU-CCS-98-09.