An efficient algorithm for finding a path subject to two additive constraints.
One of the key issues in providing end-to-end quality-of-service guarantees in packet networks is how to determine a feasible route that satisfies a set of constraints while simultaneously maintaining high utilization of network resources. In general, finding a path subject to multiple additive constraints (e.g., delay, delay-jitter) is an NP-complete problem that cannot be exactly solved in polynomial time. Accordingly, heuristics and approximation algorithms are often used to address to this problem. Previously proposed algorithms suffer from either excessive computational cost or low performance. In this paper, we provide an efficient approximation algorithm for finding a path subject to two additive constraints. The worst-case computational complexity of this algorithm is within a logarithmic number of calls to Dijkstra's shortest path algorithm. Its average complexity is much lower than that, as demonstrated by simulation results. The performance of the proposed algorithm is justified via theoretical performance bounds. To achieve further performance improvement, several extensions to the basic algorithm are also provided at low extra computational cost. Extensive simulations are used to demonstrate the high performance of the proposed algorithm and to contrast it with other path selection algorithms.
Introduction
Integrated network services (e.g., ATM, Intserv, Diffserv) are being designed to provide quality-
of-service (QoS) guarantees for various applications such as audio, video, and data. Many of these
applications have multiple QoS requirements in terms of bandwidth, delay, delay-jitter, loss, etc. One
of the important problems in QoS-based service offerings is how to determine a route that satisfies
multiple constraints (or QoS requirements) while simultaneously achieving high utilization of network
resources. This problem is known as QoS (or constraint-based) routing, and is being extensively
* This work was supported by the National Science Foundation under Grant ANI 9733143 and Grant CCR 9815229.
investigated in the research community [4, 8, 13, 23, 25, 26, 28, 34]. The need for QoS routing
can be justified for both reservation-based services (e.g., Intserv, ATM) as well as reservationless
services (e.g., Diffserv). For example, in the ATM PNNI protocol [16], constraint-based routing
is performed by source nodes to determine suitable paths for connection requests. In the case of
Diffserv, the constraint-based routes can be requested, for example, by network administrators for
traffic engineering purposes. Provisioning of such routes can also be used to guarantee a certain
service level agreement (SLA) for aggregated flows [38].
In general, routing consists of two basic tasks: distributing the state information of the network
and searching this information for a feasible path with respect to (w.r.t.) given constraints. In this
paper, we focus on the second task, and assume that the true state of the network is available to
every node (e.g., via link-state routing) and that nodes use this state information to determine an
end-to-end feasible path (see [18] for QoS routing under inaccurate information). Each link in the
network is associated with multiple QoS parameters. These parameters can be roughly classified into
additive and non-additive [2, 35]. For additive parameters (e.g., delay), the cost of an end-to-end
path is given, exactly or approximately, by the sum of the individual link parameters (or weights)
along that path. In contrast, the cost of a path w.r.t. a non-additive parameter (such as bandwidth)
is determined by the value of that parameter at the bottleneck link. Non-additive parameters can
be easily dealt with as a preprocessing step by pruning all links that do not satisfy the requested
QoS values [36]. Hence, in this paper we will mainly focus on additive parameters. The underlying
problem of path selection subject to two constraints can be stated as follows.
Constrained Path Selection (MCP): Consider a network that is represented
by a directed graph is the set of nodes and E is the set of links. Each link
associated with two nonnegative additive QoS values: w 1 (u; v) and w 2 (u; v). Given two
constraints c 1 and c 2 , the problem is to find a path p from a source node s to a destination node t
such that w 1 (p) - c 1 and w 2 (p) - c 2 , where w
The MCP decision problem is known to be NP-complete [17, 24]. In other words, there is no efficient
(polynomial-time) algorithm that can surely find a feasible path w.r.t. both constraints unless
NP=P. A related yet slightly different problem is known as the restricted shortest path (RSP) prob-
lem, in which the returned path is required to satisfy one constraint while being optimal w.r.t. another
parameter. Any solution to the RSP problem can be also applied to the MCP problem. However,
the RSP problem is also known to be NP-complete [1, 17]. Both the MCP and RSP problems can
be solved via pseudo-polynomial-time algorithms in which the complexity depends on the actual
values of the link weights (e.g., maximum link weight) in addition to the size of the network [24, 21].
However, these algorithms are computationally expensive if the values of the link weights and the
size of network are large. To cope with the NP-completeness of these problems, researchers have
resorted to several heuristics and approximation algorithms.
One common approach to the RSP problem is to find the k-shortest paths w.r.t. a cost function
defined based on the link weights and the given constraint, hoping that one of these paths is feasible
and near-optimal [20, 32, 15, 19]. The value of k determines the performance and overhead of this
is large, the algorithm has good performance but its computational cost is prohibitive.
A similar approach to the k-shortest paths is to implicitly enumerate all feasible paths [3], but this
approach is also computationally expensive. In [37] the author proposed the Constrained Bellman-Ford
(CBF) algorithm, which performs a breadth-first-search by discovering paths of monotonically
increasing delay while maintaining lowest-cost paths to each visited node. Although this algorithm
exactly solves the RSP problem, its worst-case running time grows exponentially with the network
size. The authors in [31] proposed a distributed heuristic solution for the RSP problem with message
complexity of O(n 3 ), where n is the number of nodes. This complexity was improved in [39, 22].
In [21] the author presented two ffl-optimal approximation algorithms for RSP with complexities of
O(log log B(m(n=ffl)+log log B)) and O(m(n 2 =ffl) log(n=ffl)), where B is an upper bound on the solution
(e.g., the longest path), m is the number of links, and ffl is a quantity that reflects how far the solution
is from the optimal one. Although the complexities of these algorithms are polynomial, they are still
computationally expensive in large networks [29]. Accordingly, the author in [29] investigated the
hierarchical structure of such networks and provided a new approximation algorithm with better
scalability.
Although both the RSP and MCP problems are NP-complete, the latter problem seems to be
easier than the former in the context of devising approximate solutions. Accordingly, in [24] Jaffe
considered the MCP problem and proposed an intuitive approximation algorithm to it based on
minimizing a linear combination of the link weights. More specifically, this algorithm returns the
best path w.r.t. l(e) def
using Dijkstra's shortest path algorithm, where ff; fi
The key issue here is to determine the appropriate ff and fi such that an optimal path w.r.t. l(e) is
likely to satisfy the individual constraints. In [24] Jaffe determined two sets of values for ff and fi
based on minimizing an objective function of the form g. For
the RSP problem, the authors in [6] proposed a similar approximation algorithm to Jaffe's, which
dynamically adjusts the values of ff and fi. However, the computational complexity of this algorithm
grows exponentially with the size of the network. Chen and Nahrstedt proposed another heuristic
algorithm that modifies the problem by scaling down the values of one link weights to bounded
integers [7]. They showed that the modified problem can be solved by using Dijkstra's (or Bellman-
Ford) shortest path algorithm and that the solution to the modified problem is also a solution to the
original one. When Dijkstra's algorithm is used, the computational complexity of their algorithm is
Bellman-Ford algorithm is used, the complexity is O(xnm), where x is an adjustable
positive integer whose value determines the performance and overhead of the algorithm. To achieve
a high probability of finding a feasible path, x needs to be as large as 10n, resulting in computational
complexity of O(n 4 ). In [14] Neve and Mieghem used the k-shortest paths algorithm in [9] with a
nonlinear cost function to solve the MCP problem. The resulting algorithm, called TAMCRA, has a
complexity of O(kn log(kn) is the number of constraints. As mentioned above,
the performance and overhead of this algorithm depend on k. If it is large, the algorithm gives good
performance at the expense of excessive computational cost.
Other works in the literature were aimed at addressing special yet important cases of the QoS
routing problem. For example, some researchers focused on an important subset of QoS requirements
(e.g., bandwidth and delay). Showing that the feasibility problem under this combination is not NP-
complete, the authors in [36] presented a bandwidth-delay based routing algorithm that simply prunes
all links that do not satisfy the bandwidth requirement and then finds the shortest path w.r.t. delay in
the reduced graph. Several path selection algorithms based on different combinations of bandwidth,
delay, and hop-count were discussed in [28, 27, 5] (e.g., widest-shortest path, shortest-widest path).
In addition, new algorithms were proposed to find more than one feasible path w.r.t. bandwidth and
delay (e.g., Maximally Disjoint Shortest and Widest Paths (MADSWIP)) [33]. Another approach to
QoS routing is to exploit the dependencies between the QoS parameters and solve the path selection
problem assuming specific scheduling schemes at network routers [27, 30]. Specifically, if Weighted
Fair Queueing (WFQ) scheduling is being used and the constraints are bandwidth, queueing delay,
jitter, and loss, then the problem can be reduced to standard shortest path problem by representing
all the constraints in terms of bandwidth. Although queueing delay can be formulated as a function
of bandwidth, this is not the case for the propagation delay, which is the dominant delay component
in high-speed networks [10].
Contributions and Organization of the Paper
Previously proposed algorithms for the MCP problem suffer from either excessive computational
complexities or low performance in finding feasible paths. In this paper, we provide in Section 3 an
efficient approximation algorithm (the basic algorithm) for the MCP problem under two additive con-
straints. Our algorithm is based on the minimization of the same linear cost function ffw 1 (p)+fiw 2 (p)
used in [24], where in our case we systematically search for the appropriate ff and fi. This formulation
is similar to that used in the Lagrange relaxation technique. However, the Lagrange technique
serves only as a platform, rather than a solution, by formulating constrained optimization problems
as a linear composition of constraints. The solution to the Lagrange problem requires searching for
the appropriate linear composition (Lagrange multipliers); the appropriate values of ff and fi in our
case. Any combinatorial algorithm (heuristic) that has been or will be proposed for linear optimization
problems is a careful refinement of the search for the appropriate multipliers in the Lagrangian
problem. When formulated as a Lagrangian multipliers problem, the search would typically be based
on computationally expensive methods, such as enumeration, linear programming, and subgradient
optimization [1]. Instead, we provide a binary search strategy for finding the appropriate value of k
in the composite function w (p) that is guaranteed to terminate within
a logarithmic number of calls to Dijkstra's algorithm. This fast search is one of the main contributions
in the paper. The algorithm always returns a path p. If p is not feasible, then it has the
following properties: (a) w j (p) - c j , and (b) w i (p) is within a given factor from a feasible path f
for which w i (f) is minimum, where (i; are either (1; 2) or (2; 1). Our basic algorithm performs a
binary search in the range [1; B] by calling a hierarchical version of Dijkstra's algorithm, which is
described in Section 2. Using an efficient implementation of Dijkstra's algorithm with complexity of
log n) [1], the worst-case complexity of our basic algorithm is O(log B(m Its
average complexity is observed to be much less than that. The space complexity is O(n). By proper
interpretation of the bounds in (a) and (b), we also present two extensions to our basic algorithm
in Section 4, which allow us to achieve further improvement in the routing performance at small
extra computational cost. Simulation results, which are provided in Section 5, demonstrate the high
performance of our algorithm and contrast it with other path selection algorithms. Conclusions and
future work are presented in Section 6.
Hierarchical Shortest Path Algorithm
In this section, we describe a hierarchical version of Dijkstra's shortest path algorithm that is used
iteratively in our algorithm with a composite link weight l(e) def
In addition to
finding one of the shortest paths w.r.t. l(e), this hierarchical version determines the minimum w 1 ()
and w 2 () among all shortest paths. To carry out these tasks, some modifications are needed in
the relaxation process of the standard Dijkstra's algorithm (lines 4-14 in Figure 1). The standard
8 else if
9 if min w
14 end if

Figure

1: New relaxation procedure for the hierarchical version of Dijkstra's algorithm.
Dijkstra's algorithm maintains two labels for each node [12]: d[u] to represent the estimated total
cost of the shortest path from the source node s to node u w.r.t. the composed weight l(e), and -[u]
to represent the predecessor of node u along the shortest path. The hierarchical version of Dijkstra's
algorithm maintains additional labels: w 1 [u] and w 2 [u] to represent the cost of the shortest path
w.r.t. the individual weights, and min w 1 [u] and min w 2 [u] to represent the minimum w 1 and w 2
weights among all shortest paths. 1 The standard relaxation process (lines 1-3 in Figure 1) tests
whether the shortest path found so far from s to v can be improved by passing through node u. If so,
d[v] and -[v] are updated [12]. Under this condition, we add the update of w 1 [v], w 2 [v], min w 1 [v],
and min w 2 [v]. In addition, if the cost of the shortest path found so far from node s to node v is the
same as that of the path passing through node u, then min w 1 [v] and min w 2 [v] are also updated if
passing through node u would improve their values.
3 Basic Approximation Algorithm For MCP
Our algorithm, shown in Figure 2, first executes the hierarchical version of Dijkstra's algorithm with
link weights 1. If p is feasible, then the algorithm
BasicApproximation(G(V; E); s; t; c
/* Find a path p from s to t in the network E) */
/* such that w 1
Execute hierarchical Dijkstra's algorithm with link weights
4 return SUCCESS
7 return FAILURE
return FAILURE /* one can use the extensions in Section 4 */
Execute Binary
14 else if min w 1 [t] - c 1 then
Execute Binary
BasicApproximation

Figure

2: Approximation algorithm for finding a feasible path subject to two additive constraints.
1 Notice that w i [:] is a node label, whereas w i (:) indicates the weight of a link or the cost of a path.
terminates. Otherwise, p is not feasible, and several other cases need to be considered. If both
then it is guaranteed that there is no feasible path in the network,
so the algorithm terminates. If both min w 1 [t] - c 1 and min w 2 [t] - c 2 , then there are at least
two paths, say p 1 and p 2 , that have the same cost w.r.t. l() but that violate either c 1 or c 2 (if
vice versa). In this case, changing the value of ff or fi
does not help since the algorithm will always return an infeasible path. To improve performance
in such a case, one can use the extensions presented in Section 4. On the other hand, if either
but not both, then there might be a feasible path that can be
found using different values of ff and fi. The challenge is to determine the appropriate values for ff
and fi as fast as possible such that a feasible path can be identified. Finding the appropriate values
for ff and fi can also be formulated as a Lagrangian multipliers problem. But in this case, finding
the Lagrange multipliers would typically be done using computationally expensive methods (e.g.,
enumeration, linear programming, subgradient optimization technique) [1]. Instead, we carefully
refine the search required by the Lagrangian problem and provide a binary search strategy for ff and
fi that is guaranteed to terminate within a logarithmic number of calls to Dijkstra's algorithm.
If either min w 1 [t] - c 1 or min w 2 [t] - c 2 , then the algorithm executes the binary search presented
in Figure 3 with either 1). These two cases are called Phase 1 and
Binary
l p
6 Execute hierarchical Dijkstra's algorithm with link weights
8 return SUCCESS
9 end if
as a result, k will be increased */
else
as a result, k will be decreased */
14 end if
Binary Search

Figure

3: Binary search for our approximation algorithm.
Phase 2. In Phase 1, the algorithm executes the binary search using link weight
In Phase 2, the algorithm executes the binary search using link weight
k. If the returned shortest path w.r.t. l(e) is not feasible,
the algorithm repeats the hierarchical Dijkstra's algorithm up to a logarithmic number of different
values of k in the range [1; B], where is an upper bound on the cost of the
longest path w.r.t. w j (). Lemma 1 in Section 3.2 shows that a binary search argument in the above
range can be used to determine an appropriate value for k. Furthermore, we show (in Lemma 2) that
if the binary search fails to return a feasible path, then it returns a path p such that w j (p) - c j and
feasible path and (i; j) is either (1; 2) or (2; 1).
This is a reasonble scenario for searching fast for a feasible path that satisfies one of the constraints
and that tries to get closer to satisfying the other constraint. According to this bound, k needs to
be maximized; the above binary search tries to achieve this goal. In addition to maximizing k, the
algorithm may attempt to minimize the difference (w to make the approximation bound
tighter. This is an extension to the basic algorithm that is presented in Section 4.
In the rest of this section, we first illustrate how our algorithm works and contrast it with the
one in [24]. Second, we present the binary search argument with the related lemma and its proof.
Finally, we prove the performance bound associated with our basic approximation algorithm.
3.1 How the Algorithm Works

Figure

4 describes how an approximation algorithm minimizes w 1 (p) +kw 2 (p) by scanning the path-
cost space searching for a feasible path at a given value of k. The shaded area indicates the feasibility

Figure

4: How the approximation algorithm searches the feasible region using different values for k.
region. Black dots represent the costs of different paths from source node s to destination node t.
Each line in the figure shows the equivalence class of equal-cost paths w.r.t. the composed weight.
The approximation algorithm determines a line for the given value of k, and then moves this line
outward from the origin in the direction of the arrow. Whenever this line hits a path (i.e., black dot
in the figure), the algorithm returns this path which is the shortest w.r.t. the composed weight at
the given k. The approximation algorithm in [24] makes a good guess for k (e.g., returns
a path based on this k. However, if this path is infeasible the algorithm in [24] cannot proceed. As
shown in Figure 4, the likelihood of finding a feasible path is much higher if one tries different values
of k (e.g., example results in a feasible path). The advantage of our algorithm over the
one in [24] is that ours searches systematically for a good value for k instead of fixing it in advance.
If the returned path p is not feasible, then the algorithm decides to increase or decrease the value of
k based on whether min w 2 (p) - c 2 or not.
The systematic adjustment of k is illustrated in the examples in Figures 5 and 6 for two different
phases. Figure 5 illustrates Phase 1 where the returned path with . The
(a)
(b)

Figure

5: Searching for a feasible path in Phase 1.
algorithm executes the binary search with returns a feasible path when
as shown in Figure 5(b). Figure 6 illustrates Phase 2 where the returned path with
but not c 2 . In this case, the algorithm executes the binary search with finally
(a)
(b)

Figure

Searching for a feasible path in Phase 2.
returns a feasible path when 4. If the binary search fails, then the basic algorithm stops even
though there might be a feasible path in the network. In Section 4, we illustrate such a case and
provide possible remedies to it based on a scaling extension.
3.2 Binary Search
Lemma 1 Suppose that each link e 2 E is assigned a weight is an
integer, and the pair (i; j) is either (1; 2) or (2; 1), depending on the phase. During the execution of
the binary search, if the algorithm cannot find a path p for which l(p) is minimum and w j (p) - c j ,
then such a path p cannot be found with larger values of k.
Lemma 1 implies that using a binary search, the algorithm can determine an appropriate value for
k. Although in the worst-case this search requires log(n executions of hierarchical
Dijkstra's algorithm, we observed that its average complexity is significantly lower than that.
Proof of Lemma 1: The binary search is applied to finding the largest k such that there exists
a shortest path p w.r.t. . Assume that
integer r. Let P be the set of all paths from s to t w.r.t. l(e) and let p be a path that the algorithm
selects during the binary search. When since every edge e is assigned the weight
f
In order to prove the lemma, it suffices to show that if
then the algorithm should never search for a path p 0 that satisfies the constraint c j by assigning
weights
By explicitly checking min w j [t] in line 10 of Figure 3, the algorithm guarantees that
c j for all shortest paths q 2 P , where it suffices to show that if the algorithm
assigns weights and fails to find a feasible path w.r.t. constraint c j , then no
path p 0 for which X
will satisfy both
and
when the value of k is increased to r + fl. In other words, it is useless to weight with the rule
in order to search for a path p 0 whose
minimum but satisfies the c j constraint.
Since path p violates the c j constraint, in order for path p 0 to satisfy this constraint, we must
Observe that (1) can be rewritten as
From (3) and (2), we have X
Based on (2) and (4), we know that the right-hand side and the left-hand side of (3) are positive.
Thus, it can be implied that
from which we conclude that
This, in turn, implies that p 0 will not be selected by the algorithm.
3.3 Performance Bounds
Lemma 2 If the binary search fails to return a feasible path w.r.t. both constraints, then it returns
a path p that satisfies the constraint c j and whose w i () cost is upper bounded as follows:
where f is a feasible path, k is the maximum value that the binary search determines at termination,
and the pair (i; j) is either (1; 2) or (2; 1), depending on the phase.
Note that the worst-case value for the bound in Lemma 2 is obtained when
which case
For the worst-case scenario (w i place, the feasible path f must lie on the upper
right corner of the feasibility region, with all other paths having w
is a rare scenario; most often, feasible paths are scattered throughout the feasibility region, allowing
the algorithm to terminate with k ? 1, which in turn results in a tighter bound than c
thermore, w j (p) is often greater than zero, further tightening the bound on the cost of the returned
path.
Proof of Lemma 2: Let f be any feasible path. Assume that the returned path p is infeasi-
ble. Since it is the shortest path, we have
In addition, w j (p) - c j . From (7), we can write a bound on w i (p) as follows:
These approximation bounds provide some justification to the appropriateness of the basic algorithm.
They can also be used to obtain heuristic solutions for the MCP problem, as described next.
4 Extensions of the Basic Algorithm
4.1 Finding a Path with the Closest Cost to a Constraint
From Lemma 2, it is clear that one way to improve the performance of the basic algorithm is to
minimize the difference w by obtaining a path p for which w j (p) is as close as possible
to c j . This can be done via the following modification to the basic algorithm of Section 3. Without
loss generality, we assume that 2. Note that this extension is to be used when the
returned path from the basic algorithm is infeasible but min w
For the given k, a DAG (directed acyclic graph) that contains all possible shortest paths w.r.t l(e)
is constructed. In fact, this can be done during the execution of the hierarchical Dijkstra's algorithm
at no extra cost. A path p from this DAG is selected in such a way that w 2 (p) is maximized but
is still less than or equal to c 2 . Although a path p with the maximum or minimum w 2 () cost can
be found in the DAG, it is not easy to find a path p for which w 2 (p) is as close as possible to c 2 in
polynomial-time. However, very efficient heuristics can be developed based on the fact that we can
compute the maximum and the minimum w 2 () from the source to every node and from every node
to the destination. Let the following labels be maintained for each node u: M [u], m[u], f
M [u], and
e
m[u]. Labels M [u] and m[u] indicate, respectively, the maximum and minimum w 2 () from the source
node s to every node u. Labels f
M [u] and e
m[u] indicate, respectively, the maximum and minimum
from every node u to the destination. Labels M [u], m[u], f
M [u], and e
m[u] are determined by
using a simple forward and backward topological traversal algorithm [1]. Considering the pairwise
sum of these labels as follows, we can assign the following non-additive weight oe(u; v) to every link
(u; v) in the DAG, which indicates how close w 2 () of the paths passing through link (u; v):
negative
where min non negative is the minimum nonnegative value. Then, the closest path to c 2 can be found
via a simple graph traversal algorithm as follows. Starting from the source node s, the algorithm
selects the link (s; u) with the minimum oe. It then goes to node u and again selects the link (u; v)
with the minimum oe. The algorithm keeps selecting links with minimum oe until it hits t. Although
this extension does not guarantee finding a feasible path, the following lemma shows that it always
returns a path, i.e., s and t are not disconnected by assigning 1 to some links.
Lemma 3 When the above extension is used, it always returns a path, i.e., s and t are not disconnected
by assigning 1 to some links.
First, note that the basic algorithm always returns a path. If this path is not feasible but
both min w 1 [t] - c 1 and min w 2 [t] - c 2 , then the above extension can be used. Since min w 2 [t] - c 2 ,
there is at least one path, p, with w 2 (p) - c 2 . Assume that p consists of l nodes (v
t. Note that the extension first computes the labels M [u], m[u], f
M [u], and
e
m[u] for each node u. Since w 2 (p) - c 2 , we have
From which we conclude that
Also, 1. Thus, we have oe(v every link (v along the path p. This
ensures that there is at least one path from s to t, i.e., s and t are not disconnected. Of course, if
no feasible path is found under the extension, the algorithm can trivially return the path p itself,
ensuring the connectedness of s and t.

Figure

7 depicts an example of how a DAG of shortest paths is constructed. The original network
is shown in Figure 7(a). Suppose a path p is to be found from s to t such that w 1 (p) - c
Consider the case when There
are three shortest paths from s to t: p 1 =! s;
with 9. For each
of these paths, min w than the respective constraints, so we can apply this
extension. The corresponding DAG that contains all shortest paths w.r.t. is shown in
4,2
5,6(a)
s t2
4,5
(b)

Figure

7: An example of a network and the DAG containing the three shortest paths from s to t.

Figure

7(b). By traversing forward and backward on this DAG, we compute the labels M [u], m[u],
M=6
s t2
(a)
s t2
(b)

Figure

8: Finding the closest path to c 2 .
f
M [u], and e
m[u] (see

Figure

8(a)). After calculating oe for each link as shown in Figure 8(b), the
algorithm first selects link (s; 1), followed by link (1; 2), and finally link (2; t). Thus, the closest path
3 is found. Since this heuristic step tends to minimize the additive difference in the approximation
bound presented in Lemmas 2, the returned path p is more likely to satisfy both c 1 and c 2 .
4.2 Scaling
In some pathological cases, no linear combination of weights can result in returning a feasible path,
despite the existence of such a path. An example of such a case is shown in Figure 9(a). Suppose
that a path p is to be found from s to t such that w 1 (p) - c As shown
in

Figure

9(b), there are three paths from s to t: p 1 =! s;
2. Only p 2 is feasible. The approximation algorithm, say in Phase 1, returns a path based
on the minimization of the composed weight To return the feasible path p 2 ,
the algorithm needs to find an appropriate value for k such that l(p 2 ) is less than both
Hence, the value of k needs to be greater than 7=6 to satisfy (l(p 2
w2(p)2 9
p3

Figure

9: A scenario in which the basic algorithm fails to find a feasible path from s to t.
also less than 8=7 to satisfy (l(p 2 2k). But this is impossible. In other
words, the approximation algorithm cannot find the feasible path p 2 , irrespective of the value of k.
This situation is illustrated in part (b) of the figure.
To circumvent such pathological cases, we provide an extension to our basic algorithm based on
the scaling in [7]. A new weight w 0
2 (e) is assigned to every link in the original graph as follows:
where x is an adjustable positive integer in the range [1; c 2 ]. The problem reduces to finding a path
in the scaled graph such that w 1 (p) - c 1 and w 0
x. It has been shown that a solution in
the scaled graph is also a solution in the original one [7]. If we scale the network in Figure 9(a)
by the scaled graph is shown in Figure 10(a). If the approximation algorithm uses the cost
(b)
p3

Figure

10: Scaling the network in Figure 9 by allows the algorithm to find a feasible path.
function l 2
2 (p) in the scaled graph with return the feasible path p 2
(see

Figure

10(b)), since l(p 2
Using the above scaling function, one may increase the number of shortest paths in the scaled
graph. If we apply our basic approximation algorithm to the scaled graph, the algorithm will consider
more shortest paths (in the scaled graph) in each iteration of the binary search. It is intuitively true
that the algorithm will terminate with a better (i.e., larger) value of k.
It is important to note that in contrast to the algorithm in [7], the value of x does not affect
the complexity of our algorithm. Choosing x as small as possible may increase the number of
shortest paths as desired. However, this also decreases the number of paths for which w 0
i.e., the algorithm may not return a feasible path. The tradeoff between the value of x and the
associated performance improvement after scaling by x is shown in Figure 11. Here, we measure the
performance of the path selection algorithm by the success ratio (SR), which shows how often the
algorithm returns a feasible path [7]:
number of routed connection requests
otal number of connection requests
where a routed connection request is one for which the algorithm returns a feasible path.
Sucsess
ratio
x
Sucsess
ratio
x
Our algorithm with scaling by x
Optimal algorithm
Our algorithm with scaling by x
Optimal algorithm

Figure

11: Performance of the path selection algorithm for different values of the scaling factor x.
When the basic algorithm fails to return a feasible path, we scale the graph using different values of
x and run the algorithm again. The following lemma shows that a binary search argument can be used
to determine an appropriate x in the range [1; c 2 ]. Since the basic algorithm is executed for each value
of x, the overall computational complexity of the scaling extension is O(log c 2 log B(n log n
Note, however, that this extension is used only after the basic step with no scaling fails.
Lemma 4 If the algorithm cannot find a path p for which w 0
in the scaled graph by x, then
such a path cannot be found in a graph that is scaled by x
Proof of Lemma 4: Let the graph G be scaled by x = 2r for some integer r, and let P be
the set of all possible paths in the scaled graph. If the algorithm fails to return a path p for which
l w 2 (e)\Delta2r
In order to prove the lemma, it suffices to show that if (9) is true, then the algorithm should never
search for a path p 0 for which w 0
l w 2 (e)\Deltar
r when the links of the graph are scaled
down by
we can rewrite
from which we conclude X
This, in turn, implies that no path will be selected by the algorithm, and the claim is true.
5 Simulation Results and Discussion
In this section, we contrast the performance of our basic algorithm with Jaffe's second approximation
algorithm [24], Chen's heuristic algorithm in [7], and the first ffl-optimal algorithm in [21]. In [24] Jaffe
presents two approximation algorithms for the MCP problem based on the minimization of w
in the first algorithm and
in the second. Of the two approximations,
the latter one provides better performance, and hence it will be used in our comparisons. As a point
of reference, we also report the results of the exact (exponential-time) algorithm, which considers all
possible paths in the graph to determine whether there is a feasible path or not. The performance
has been measured for various network topologies. For brevity, we report the results for one of these
topologies under both homogeneous and heterogeneous links.
5.1 Simulation Model and Performance Measures
In our simulation model, a network is given as a directed graph. Link weights, the source and
destination of a connection request, and the constraints c 1 and c 2 are all randomly generated. We
use the success ratio (SR) to contrast the performance of various path selection algorithms. Another
important performance aspect is the computational complexity. In here, we measure the complexity
of path selection algorithms by the number of performed Dijkstra's iterations. While the algorithm
in [24] requires only one iteration, the algorithm in [7] always requires x 2 iterations, where x is
an adjustable positive integer. The number of iterations in our basic algorithm varies in the range
log B], where B is the upper bound on the longest path according to one of the link weights. For our
algorithm, the average number of Dijkstra's iterations (ANDI) per connection request is measured
and compared with the deterministic number of Dijkstra's iterations in the other algorithms. It
should be noted that our algorithm runs at its worst-case complexity only if it is deemed to fail, i.e.,
if the algorithm succeeds in finding a path, it will do so with much fewer Dijkstra's iterations than
log B. This is confirmed in the simulation results.
5.2 Results Under Homogeneous Link Weights
We consider the network topology in Figure 12, which has been modified from ANSNET [11] by
inserting additional links. Link weights are randomly selected with w 1 (u; v) - uniform[0; 50] and
200]. The same network topology, link weights, and constraints were used
in [7]. For different ranges of c 1 and c 2 , Table 1 shows the SR of various algorithms based on twenty0101010101010101001101010101010101010101010101001111010101010101 010101000000000000000000000000000000000011111111111111111111111111111111110000000000000000000000000011111111111110000000001111111110000001111000000000000111111111000000000000000000111111111111111111000000001111110000000011111111000000000000000111111111111111
28 29272221

Figure

12: An irregular network topology.
runs; each run is based on 2000 randomly generated connection requests. For our algorithm, the
Range of c 1 and c 2 Exact Our Alg. Jaffe's Chen's ffl-optimal

Table

1: SR performance of several path selection algorithms (homogeneous case).
ANDI for each range in Table 1 is given by 2.49, 2.63, 2.23, 1.61, and 1.21, respectively. The number of
feasible paths, and thus the SR, increases as the constraints gets looser in the table. As this happens,
the ANDI in our algorithm decreases. The overall average complexity per connection request is about
two iterations of Dijkstra's algorithm. In terms of SR, our algorithm performs almost as good as
the exact one. The results show that our algorithm provides significantly superior performance to
Jaffe's approximation algorithm. To compare our algorithm with Chen's heuristic algorithm [7] and
the ffl-optimal algorithm [21], we need to properly set the values of x and ffl. In theory, as x goes
to infinity and as ffl goes to 0, the performances of the corresponding algorithms approach that of
the exact one. However, since the complexities of these algorithms depend on x and ffl, large values
for x and small values for ffl clearly make the corresponding algorithms impractical. To get as close
as possible to achieving about the same average computational complexity of our algorithm, we set
the performance of Chen's algorithm lags significantly behind
ours. Even if we increase x to ten, making the computational requirement of Chen's algorithm many
times that of our algorithm, its performance still lags behind ours. When the ffl-optimal
algorithm has roughly the same average complexity as ours; but with ours having a 50% higher
SR. The ffl-optimal algorithm uses a dynamic-programming approach that maintains a scaled cost
array with size of (n=ffl) at each node and it can determine paths whose scaled cost is less than
(n=ffl). When the values of constraints are increased, more longer paths becomes feasible, but the
ffl-optimal algorithm cannot determine them unless ffl gets very small. For example, the performance
of the ffl-optimal algorithm becomes close to that of ours if ffl is set to 1. But in this case, the
complexity of the ffl-optimal algorithm is about ten times that of ours. (The complexity of the ffl-
optimal algorithm is O(log log B(mn log log B)), compared to an average of about two iterations
of Dijkstra's algorithm for our algorithm. The complexity of Dijkstra's algorithm is O(n log n +m).
in the underlying
network, we have 2(n log n m) - 10% of log log B(mn log log B).)
In the above simulations, the two constraints are almost equally tight (i.e., E[w 1
have comparable values). We now examine the case when one constraint is much
tighter than the other. We use the same network and parameter ranges as before, except for c 1 whose
upper and lower limits are now set to 1=5 of their original values. The SRs of various algorithms
are shown in Table 2. Since the first constraint is now tighter than before, the SR values for all
algorithms, including the exact one, are smaller. Nonetheless, the same previously observed relative
performance trends among different algorithms in Table 1 are also observed here. Note that by
making one constraint much tighter than the other, the problem almost reduces to that of finding
the shortest path w.r.t. the tighter constraint. By dynamically changing the value of k, our algorithm
can adapt to the tightness of this constraint by giving it more weight (through k).
The above discussion simply says that relative to the exact algorithm, the performance of our
approximation algorithm does not change significantly by making one constraint tighter than the
other provided that the links are homogeneous. However, this is not the case when the links are
heterogeneous, as demonstrated in the next section.
Range of c 1 and c 2 Exact Our Alg Jaffe's Chen's ffl-optimal

Table

2: SR performance of several path selection algorithms when the first constraint is much tighter
than the second (homogeneous case).
5.3 Performance Under Heterogeneous Links
The heterogeneity of links in a network may severely impact the performance of a path selection
algorithm. Hence, before drawing any general conclusions on the merits of our algorithm, we need
to examine its performance in a network with heterogeneous links. For this purpose, we start with
the same network topology in Figure 12. We then divide the network into three parts, as shown in

Figure

13. The link weights w 1 and w 2 are determined as follows: if u is a node that belongs to0101010101010101001101010101010101010101010101001111010101010101 010101000000000000000000000000000000001111111111111111111111111111111100000000000000000000000011111111111111111111111100000000011111111100000011111100000000000011111111100000000000000000011111111111111111100000000111111110000000011111111000000000000000111111111111111
28 29272221

Figure

13: Network topology with heterogeneous link weights.
the upper part of the network, then w 1 (u; v) - uniform[70; 85] and w 2 (u; v) - uniform[1; 5]; if it
belongs to the middle part, then w 1 (u; v) - uniform[45; 55] and w 2 (u; v) - uniform[45; 55]; and
if it belongs to the lower part, then w 1 (u; v) - uniform[1; 5] and w 2 (u; v) - uniform[70; 85]. The
source node is randomly chosen from nodes 1 to 5. The destination node is randomly chosen from
nodes 22 to 30.
For different ranges of c 1 and c 2 , Table 3 shows the SR of various algorithms based on twenty runs;
each run is based on 2000 randomly generated connection requests. For our algorithm, the ANDI
Range of c 1 and c 2 Exact Ours Jaffe's Chen's

Table

3: SR performance of several path selection algorithms (heterogeneous case).
for the five ranges of c 1 and c 2 in Table 3 are given by 4.03, 4.59, 4.55, 4.52, and 2.75, respectively.
It can be observed that in this case, as the constraints become looser, the difference between the
SR of any of the tested algorithms and the SR of the exact algorithm increases significantly (see
the fifth row in the table). One can attribute this performance degradation to the linearity of the
cost functions used in these algorithms, which favors links with homogeneous characteristics. Our
algorithm still provides better performance than Jaffe's approximation algorithm. To achieve about
the same average computational complexity of our algorithm, we set x = 3 in Chen's algorithm and
in the ffl-optimal algorithm. With these values, the SRs of these algorithms lag behind is
observed to lag behind ours.
6 Conclusions and Future Work
QoS-based routing subject to multiple additive constraints is an NP-complete problem that cannot be
exactly solved in polynomial time. To address this problem, we presented an efficient approximation
algorithm using a binary search strategy. Our algorithm is supported by performance bounds that
reflect the effectiveness of the algorithm in finding a feasible path. We studied the performance of
the algorithm via simulations under both homogeneous and heterogeneous link weights. Our results
show that at the same level of computational complexity, the proposed algorithm outperforms existing
ones in its performance. We also presented two extensions to our basic algorithm that can be used
to further improve its performance at little extra computational cost. The first extension, which
is motivated by the presented theoretical bounds, attempts to find the closest feasible path to a
constraint. The other extension (i.e., scaling) improves the likelihood of finding a feasible path by
perturbing the linearity of the search process (or equivalently, changing the relative locations of the
paths in the parameter space). Our basic approximation algorithm runs a hierarchical version of
Dijkstra's algorithm up to log B times, where B is an upper bound on the longest path w.r.t. one
of link weights. Specifically,
Phase 2. When scaling is used, the algorithm runs Dijkstra's algorithm up to log c 2 log B times.
These worst-case complexities are rarely used in practice. In fact, simulation results indicate much
lower average complexities. The space complexity of our algorithm is O(n).
The path selection problem has been investigated in this paper assuming a flat network topology
and complete knowledge of the network state. In practice, the true state of the network is not
available to every source node at all times due to network dynamics, aggregation of state information
(in hierarchical networks), and latencies in the dissemination of state information. Our future work
will focus on investigating the MCP problem in the presence of inaccurate state information and
evaluating the tradeoffs among accurate path selection, topology aggregation (for spatial scalability),
and the frequency of advertisements (for temporal scalability). Another aspect that we plan to
investigate is that of renegotiation. When our algorithm fails to return a feasible path, it always
returns a path which is close to satisfying the given constraints. Hence, we plan to investigate how
such a path can be advantageously used in the renegotiation process to achieve further performance
improvements.



--R

Network Flows: Theory
ATM internetworking.
Shortest chain subject to side constraints.
QoS routing mechanisms and OSPF extensions.
Quality of service based routing: A performance perspective.
An approximation algorithm for combinatorial optimization problems with two parameters.
On finding multi-constrained paths
An overview of quality-of-service routing for the next generation high-speed networks: Problems and solutions

Strategic directions in networks and telecommunications.
Internetworking with TCP/IP
Introduction to Algorithms.
A framework for QoS-based routing in the Internet
A multiple quality of service routing algorithm for PNNI.
Finding the k shortest paths.
the ATM Forum.
Computers and Intractability

Search space reduction in QoS routing.
A dual algorithm for the constrained shortest path problem.
Approximation schemes for the restricted shortest path problem.
A delay-constrained least-cost path routing protocol and the synthesis method
ATM routing algorithms with multiple QOS requirements for multimedia inter- networking
Algorithms for finding paths with multiple constraints.
QoS based routing for integrated multimedia services.
Routing subject to quality of service constraints in integrated communication networks.
On path selection for traffic with bandwidth guarantees.
Routing traffic with quality-of-service guarantees in integrated services networks
Routing with end-to-end QoS guarantees in broadband networks
QoS based routing algorithm in integrated services packet networks.
A distributed algorithm for delay-constrained unicast routing
Solving k-shortest and constrained shortest path problems efficiently


On the complexity of quality of service routing.

the design and evaluation of routing algorithms for real-time channels
Internet QoS: a big picture.
A new distributed routing algorithm for supporting delay-sensitive applications
--TR
Solving <italic>k</>-shortest and constrained shortest path problems efficiently
Introduction to algorithms
Internetworking with TCP/IP (2nd ed.), vol. I
Network flows
Approximation schemes for the restricted shortest path problem
Strategic directions in networks and telecommunications
Quality of service based routing
On the complexity of quality of service routing
QoS routing in networks with inaccurate information
Routing with end-to-end QoS guarantees in broadband networks
Computers and Intractability
A Delay-Constrained Least-Cost Path Routing Protocol and the Synthesis Method
A Distributed Algorithm for Delay-Constrained Unicast Routing
QoS based routing algorithm in integrated services packet networks
On path selection for traffic with bandwidth guarantees
An Approximation Algorithm for Combinatorial Optimization Problems with Two Parameters
Search Space Reduction in QoS Routing

--CTR
Anthony Stentz, CD*: a real-time resolution optimal re-planner for globally constrained problems, Eighteenth national conference on Artificial intelligence, p.605-611, July 28-August 01, 2002, Edmonton, Alberta, Canada
Gang Cheng , Nirwan Ansari, Rate-distortion based link state update, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.17, p.3300-3314, 5 December 2006
Xin Yuan, Heuristic algorithms for multiconstrained quality-of-service routing, IEEE/ACM Transactions on Networking (TON), v.10 n.2, April 2002
Zhenjiang Li , J. J. Garcia-Luna-Aceves, A distributed approach for multi-constrained path selection and routing optimization, Proceedings of the 3rd international conference on Quality of service in heterogeneous wired/wireless networks, August 07-09, 2006, Waterloo, Ontario, Canada
Zhenjiang Li , J. J. Garcia-Luna-Aceves, Finding multi-constrained feasible paths by using depth-first search, Wireless Networks, v.13 n.3, p.323-334, June 2007
Gargi Banerjee , Deepinder Sidhu, Comparative analysis of path computation techniques for MPLS traffic engineering, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.40 n.1, p.149-165, September 2002
Andrea Fumagalli , Marco Tacca, Differentiated reliability (DiR) in wavelength division multiplexing rings, IEEE/ACM Transactions on Networking (TON), v.14 n.1, p.159-168, February 2006
Wei Liu , Wenjing Lou , Yuguang Fang, An efficient quality of service routing algorithm for delay-sensitive applications, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.47 n.1, p.87-104, 14 January 2005
Zhenjiang Li , J. J. Garcia-Luna-Aceves, Loop-free constrained path computation for hop-by-hop QoS routing, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.51 n.11, p.3278-3293, August, 2007
Turgay Korkmaz , Marwan Krunz, Bandwidth-delay constrained path selection under inaccurate state information, IEEE/ACM Transactions on Networking (TON), v.11 n.3, p.384-398, June
scalable routing;multiple constrained path selection;QoS routing