Computer Networks 37 (2001) 407^23

www.elsevier.com/locate/comnet
Hop-by-hop quality of service routing
Piet Van Mieghem a'*, Hans De Neve b, Fernando Kuipers a
L Delft University of Technology, Information Technology and Systems, P.O. Box 5031, 2600 GA Delft, Netherlands b Alcatel Corporate Research, Francis Wellesplein 1, B-2018 Antwerp, Belgium
Received 5 May 2000; received in revised form 22 September 2000; accepted 20 April 2001 Responsible Editor: R. Guerin
Abstract
Based on the self-adaptive multiple constraints routing algorithm (SAMCRA), an improved and exact version of our QoS routing algorithm, the tunable accuracy multiple constraints routing algorithm (TAMCRA) we have investigated QoS routing in a hop-by-hop manner because it forms the basis of IP networking as e.g. in OSPF. In particular, we studied 'hop-by-hop destination based only' (HbHDBO) QoS routing that ignores the source and previous path history (as in current IP routing). We demonstrate that an exact QoS algorithm assures the avoidance of routing loops in this HbHDBO setting. However, despite the use of an exact QoS routing algorithm as SAMCRA, the exact solution cannot be guaranteed with HbHDBO routing. Fortunately, large simulation results on various sizes of random graphs show that the overall quality of the HbHDBO QoS routing is remarkably good. Finally, we show that, by using active networking as opposed to current IP routing, exact QoS routing in a hop-by-hop way can be guaranteed. © 2001 Elsevier Science B.V. All rights reserved.
Keywords: Routing; Quality of service; NP-completeness; (T)SAMCRA
1. Introduction: HbHDBO routing
The main motivation of this article is the question whether current OSPF can be extended to multiple constraints QoS routing. Our study may be seen as a complement to that of Apostolopou-los et al. in Ref. [1]. We assume the existence of a QoS supporting routing protocol of the link state family that is capable of offering each node in the network a consistent view of the topology. Obtaining a 'consistent' view of the topology is a
Corresponding author. Tel.: +31-15-278-2397; fax: +31-15278-1774.
E-mail address: p.vanmieghem@its.tudelft.nl (P. Van Mieg-hem).
complex problem that has currently attracted a lot of interest (see also PNNI). The difficulty of obtaining complete topology information has lead to researches on QoS routing in networks with inaccurate information [12]. Apostolopoulos et al. [2] broadly discuss dynamic QoS routing aspects, while Chen and Nahrstedt [5] focus on dynamic QoS routing in wireless media (also called ad hoc networks). The dynamic updating of the topology link metrics due to coupling with the resource consumption in the nodes of the network is regarded here as beyond the scope and is treated elsewhere [22]. Presuming the full knowledge ofthe network topology at a certain time interval during which we regard the topology metrics as frozen, we focus here on algorithmic aspects of (static) QoS

Fig. 1. Comparison of exact end-to-end QoS routing (via source routing) and HbHDBO QoS routing.
routing using the tunable accuracy multiple constraints routing algorithm (TAMCRA) [8,9] or its exact modification, the self-adaptive multiple constraints routing algorithm (SAMCRA). T(S)AMCRA will be briefly reviewed in Section 2.
A network topology supporting QoS consists of link metrics vectors with non-negative QoS measures as components. The QoS measure of a path can either be additive in which case it is the sum of the QoS measures along the path (such as delay, jitter, the logarithm of packet/cell loss, cost of a link, etc.) or it can be the minimum(maxi-mum) of the QoS measures along the path (typically, available bandwidth and policy flags). Min(max) QoS measures are treated by omitting all links (and possibly disconnected nodes) which do not satisfy the requested min(max) QoS measure. We call this topology filtering. Additive QoS measures are expected to cause more difficulties: the multiple constraints problem (MCP), defined as finding a path subject to more than one additive constraint, is known to be NP-complete [10,25] and hence, considered as intractable for large networks.
Section 3 deals with the feasibility of 'hop-by-hop destination based only' (HbHDBO) QoS routing. Although QoS routing naturally asks for on-demand, end-to-end and explicit routing [20], we focus on the MCP for routing in a connectionless environment as shown in Fig. 1. The study is motivated by the fact that, first of all, 'diffserv' routing is a missing and desirable network architectural building block and further, that, apart from policy (or inter-domain) routing, all routing protocols in the Internet operate in a hop-by-hop mode. Thus, it directly impacts the question whether OSPF is extendable to provide QoS with a suicient level of 'guarantee hardness'.
In that Section 3, we show that (a) HbHDBO QoS routing with an exact QoS algorithm such as SAMCRA assures loop-freeness, that (b) even with an exact algorithm and as opposed to single parameter routing (as Dijkstra), no end-to-end constraints can be guaranteed. Immediately, the question about the quality of HbHDBO QoS routing arises. Section 4 presents simulations 1 of the performance of HbHDBO QoS routing in random graphs with uniformly distributed link weights. For that class of networks, we find that the differences with respect to the exact result are remarkably small. Finally, Section 5 demonstrates that, by using active networking as opposed to current IP routing, exact QoS routing in a hop-by-hop way can be guaranteed.
2. QoS routing: T(S)AMCRA
Here we briely review our QoS routing algorithm, TAMCRA, analyzed earlier in Ref. [9]. TAMCRA returns the path between a given source and destination subject to the (end-to-end) constraints Lj on each QoS measure (1 < j < m).
Additional results are presented in Ref. [18].
TAMCRA is based on three fundamental concepts: a non-linear measure for the path length, the k-shortest path approach and the principle of non-dominated paths.
All m additive QoS measures are considered as equally important. Each link is specified by a m-dimensional weight vector (w1; w2,wm). The path vector w,(P ) = {w>1(P), W2(P),..., Wm(P)} is the vector sum of the link weights along this path, thus, Wj(P)= 2,i-l€Pwj(i — l) for each j. The path
rl cti
length is a vector norm and given by
i(P) = max (wj(p)/lj)
1 ^ j ^ m
(1)
This definition (1) obeys the criteria for 'length' or 'distance' in vector algebra (see Appendix A) and is motivated by the geometry of the constraints surface in m-dimensional space. In the next subsection, other deinitions than Eq. (1) are considered. An important corollary (see Appendix A) of a non-linear length function such as Eq. (1) is that the subsections of shortest paths in multiple dimensions are not necessarily shortest paths. This corollary suggests to consider in the computation more paths than only the shortest one, leading us naturally to the k-shortest path [6] approach (i.e. we consider the shortest path, the 2nd shortest, etc. up to the kth shortest path). Finally, the multidimensional character of QoS routing invites the use of state space reduction, which has been implemented via the concept of non-dominated paths 2 [15]. TAMCRA possesses tunable accuracy (coupled to the running time) via one integer parameter k, which reflects the maximum number of shortest paths stored in each nodal queue. There always exists a inite value of k, which is upper bounded by
(
kmax = min
riLi
max(Lj)
, \e(N - 2)!J
(2)
and for which TAMCRA returns the exact path. The irst argument of the min-operator in Eq. (2) refers to the number of relevant path vectors
2 A path Q is dominated by a path P if, for all vector components j holds that wj(P) ^ wj(Q).
within the constraints surface. The second argument, where [xJ denotes the largest integer equal to or smaller than x and e = 2.718is an attainable upper bound for the number of paths between two nodes in any graph with N nodes [23].
SAMCRA, is an exact modiication and improvement of TAMCRA that avoids the explicit determination of the parameter k. Instead of requiring in each node of the graph G a queue size &max, the queue size can be adapted independently per node during the course of the routing algorithm. In this mode, TAMCRA self-adaptively inds the exact solution avoiding the need to determine an overall queue size of length k < kmax for each node. In the Appendix A, we proof that SAMCRA is exact. Besides the concept of dominated paths, an additional increase in the computational efficiency can be gained. Better than checking the path length in an intermediate node with the constraints, each new entry in the queue is now irst compared against the minimum entry in the destination-queue. Indeed, if we already have a path P1 with length l(P1), we can discard all the other (sub)-paths P2 with length l(P2) > l(P0, because their length can never be smaller than l(P1) as the link-vectors consist of non-negative additive metrics.
2.1. SAMCRA implemented with other definitions of length than Eq. (1)
Depending on the specifics of a constrained optimization problem, SAMCRA can be used with different length functions, provided they obey the criteria for length. This subsection exempliies the use of a diferent deinition of length to solve the delay-constrained least-cost (DCLC) path problem and the hop-constrained maximum bandwidth (HCMB) problem.
2.1.1. Delay-constrained least-cost path
Given a graph G(N, E) where each link is characterized by a delay and (monetary) cost. Given a delay constraint D, the problem is to ind a path P from a source and a destination node within the delay constraint for which the cost is minimum.
m
A suitable length function for this problem is:
c(P)
l(P)=
C '
oo,
if d(P) < D, else
(3)
where C = 7Vmax1 ^i^£(c(ei)) is a cost-constraint that each cycle-free path can obey, c(P) is the cost of P and d(P) is the delay of P. The length function (3) only optimizes for one metric, the cost or price, which is often considered the most important metric to minimize. Although it is tempting to call this length function linear since it only optimizes a single metric, the constraint(s) make (3) non-linear (the function is linear only within the constraints surface). Therefore, again, the subsections of shortest paths are not necessarily shortest paths. Guo and Matta [13] have successfully used this approach to solve the DCLC problem. Korkmaz and Krunz [17] have adopted a similar approach and evaluated the performance of TAMCRA, the predecessor of SAMCRA, and an altered TAMCRA algorithm against Jaffe's algorithms [16] and one of the approximation schemes proposed by Hassin [14]. In their simulations, the performance of the TAMCRA(-like) algorithms signiicantly outperformed the other algorithms.
2.1.2. Hop-constrained maximum-bandwidth problem
Given a graph G(N, E), where each link has a speciied capacity (bandwidth), ind a path P from a source to a destination with no more than H hops that has maximum capacity.
A suitable length function for this problem is:
1
l(P)=
BW (P)
o,
if h(P) < H, else
(4)
where BW(P) is thecapacityofPinminimumunits (e.g. Mb/s) and h(P) is the number of hops taken by P. The length function (4) is similar to Eq. (3) and illustrates that min/max parameters can also be incorporated. Besides a diferent length function, this problem requires a small but simple change to SAMCRA's code, because BW(P) is not the sum of the capacities of the links on P, but the minimum link capacity on P. A discussion of the HCMB problem can be found in Apostolopoulos et al. [1].
We have shown that, provided a suitable definition of length is chosen, SAMCRA applies to numerous constraint/optimization problems.
2.2. The meta-code for SAMCRA
SAMCRA(G, s, d, L)
G: graph, s: source node, d: destination node, L: constraints
1 counter = 0 for all nodes
2 endvalue = 1.0
3 path(s[1]) = NULL and length(s[1]) = 0
4 put s[1] in queue
5 while(queue = empty)
6 EXTRACTJMIN(queue) — u[i] 7u[i] = marked grey 8if(u = d)
9 STOP
10 else
11 for each v € adjacency.list(u)
12 if(v=previous node of u[i])
13 PATH = path(u[i]) + (u, v)
14 LENGTH = length(PATH)
1 n nn -"hi n nlr n j
15
16
17
18 19 20 21 22 23 24
25 26
check all non-black paths at v and PATH for dominancy, endvalue    mark obsolete
and
paths black if (LENGTH < endvalue non-dominated) if(paths are not black) counter v     counter v
r(v) = counter(v) + 1 j = counter(v) path(v[j]) = PATH length(v[j]) = LENGTH put v[j] in queue else
replace a black path with PATH
d and LENGTH < endvalue)
endvalue   LENGTH
if(v
end
Line 1 to line 4 are initializations, line 1 initializes the counter for each node to zero. This counter keeps track of the number of entries in the queue. To start the algorithm with the source node, this node is inserted into the queue (line 4). The EXTRACT_MIN function (see Ref. [7]) in line 6 selects the minimum path length in the queue and returns the associated node u with entry number i. This is the ith path stored in the queue at node u. The extracted node is marked gray in line 7. If the extracted node u equals the destination, the shortest path satisfying the constraints is returned else the scanning procedure is invoked (lines 11 and 12). Line 13 describes how the path up to node u is extended towards the neighboring node v. Line 15 checks for path dominance as explained in Ref. [9]. If an old unmarked path is dominated by the new entry PATH, it is marked black. A node marked black has become obsolete and may be replaced by a new path. The efficiency gain via endvalue in line 16 keeps track of the smallest path length in the destination queue so far. Lines 17 to 24 describe how path(length)s for a node can be added. The endvalue is updated in line
26.
2.3. Worst case complexity of SAMCRA
If N and E are the number of nodes and of links respectively in the graph G = (N, E), the queue in SAMCRA can never contain more than kN path lengths. When using a Fibonacci heap to structure the queues, selecting the minimum path length among kN different path lengths takes at most a calculation time of the order of log (AN) [7]. As each node can at most be selected k times from the queue, the EXTRACT_MIN function in line 6 of SAMCRA's meta-code takes 0(kN log (AN)) at most. The for-loop starting on line 11 is invoked at most k times from each side of each link in the graph. Calculating the length takes O(m) when there are m metrics in the graph while verifying path dominance takes O(km) at most. Adding or replacing a path length in the queue takes O(1). The total complexity of the for-loop now becomes 2kE(O(m) + O(km) + O(1)) = O(kEkm). Adding the contributions yields a worst-case complexity with k = kmax of
O(kN log(kN) + k2 mE). (5)
Clearly, for a single constraint (m = 1andk = 1), the complexity (5) reduces to that of the Dijkstra algorithm. When the constraints/metrics Li are real numbers, the granularity is infinitely small implying that the first argument in Eq. (2) is infinite and, hence, kmax = O(N !)= O(exp(N ln N)). In this case, the QoS routing problem is NP-complete. If Li for i = 1,..., m can be upper bounded by a constant or polynomial in log(Li), Eq. (5) is polynomial as proved by Chen and Nahrstedt [4].
2.4. An example of the operation of SAMCRA
Consider the topology drawn in Fig. 2. We are asked to ind a path from the source node A to the destination node B subject to the constraints vector L = (10,10).
SAMCRA returns the shortest path satisfying the L vector in eight steps. Whenever a node is extracted from the queue (line 6 of the meta-code), the corresponding box is colored in gray. The arrows refer to line 11, while line 12 has already been taken into account (i.e. no arrow to an adjacent, previous hop of the path). The algorithm stops when the irst entry of the destination node B is extracted from the queue.
In step 4 of Fig. 3, the end-to-end length of 1.1 fails the constraint test in line 16 and is not maintained in the SAMCRA queue of node B. Moreover, at step 4, the queue in node E contains two path entries and the new entry: AFE with path vector (3,7) and length 0.7, ACE with path vector (5,6) and length 0.6 and ACDE with path vector (5,5) and length 0.5. Since the vector components of the path ACE are all larger than or equal to those of the path ACDE, the path ACE is dominated by path ACDE and removed from the queue. (The path is not actually removed, but marked to be replaced by the new entry.)

Fig. 2. Example topology.

Fig. 3. Example of the operation of SAMCRA (step 1 to 4).
Step 5 deserves attention because, since only the previous hop is maintained (line 12), SAMCRA stores 3 new subpaths (Fig. 4). But, the path AC-DEC with length 0.8 obviously contains a loop. In the dominance check (line 15), this path is again removed since it is clearly dominated by AC. An alternative approach could be to check the entire path so far and only visit neighbors that do not already belong to the subpath. In that case, step 5 would immediately exclude the subpath ACDEC. However, regarding computational complexity, the current approach is more economical if m < N, which is normally the case. In step 7, we note that the path AFED with length 0.8 is dominated by

Fig. 4. Example of the operation of SAMCRA (step 5 to 8).
the path ACD with length 0.4 and thus not stored in the queue of node D. The only remaining queue entry is at the destination node B and SAMCRA stops in step 8 (line 9). The resulting path satisfying all constraints is AFEB with path vector (9,8) and length 0.9.
Since the granularity is 1 (the vector components are all integers), we observe that, although with Eq. (2) kmax = 10, kmin = 2 suffices for the exact solution because two queue entries are needed at node E, while all the other nodes store equal or less entries. This example also shows that the end-to-end shortest path (AFEB) with length 0.9 is merely the third shortest path from A to the intermediate node E with length 0.7. In addition, this shortest path AFEB is the only path that meets all constraints. If TAMCRA were used with k = 1, no path satisfying the constraints would have been found. SAMCRA always guarantees that, if there is a compliant path, this path is certainly found. Finally, the eiciency gain (line 25, 26) only occurs in the inal step 8 when we irst ind a path satisfying all constraints. Removing (marking black) all queue entries larger than 0.9, unfortunately, does not result in a speed-up in this example.
3. Hop-by-hop QoS routing
Since QoS routing assumes multiple end-to-end constraints, a pre-computed routing table should contain in every node at least one path (e.g. the 'shortest' depending on some 'length' criterion) for each source-destination pair and each class of service. This means that every node should store the next hop towards the destination. The next hop is obtained in every intermediate node along the path via a route computation from the original source (not the intermediate node itself) to the destination. The number of table entries grows like O(N2) as opposed to O(N) for ordinary BE where only the destination matters. Zhang et al. [26] have briefly mentioned two arguments for source-destination routing in unicast Q-OSPF: (a) resource reservations are generally based on a source-destination pair and (b) lows with same destination but diferent sources can follow diferent paths. Based on our experience with T(S)AMCRA, there is a more fundamental reason to support source-destination routing embodied by the above mentioned corollary: when using a non-linear definition of the path length, the subsections of shortest paths in multiple dimensions are not necessarily shortest paths. Indeed, suppose we construct the end-to-end path in the 'traditional' (as e.g. in OSPF) hop-by-hop way ignoring the source address. This corollary demonstrates that, even with exact multiple parameter routing algorithms (such as SAMCRA), a hop-by-hop route computation does not necessarily result in the shortest path, as exemplified below in Section 3.2. Immediately, the question arises whether a non-linear vector length introduces the possibility of creating loops in the path when computed in a hop-by-hop fashion.
3.1. On routing loops
Let Pk denote the shortest path from an intermediate hop k towards the destination computed
by SAMCRA.
Lemma 1. If Pk+1 is a subsection (or subpath) of Pk there holds that l(Pk) ^ l(Pk+1), otherwise l(Pk) > l(Pt+1).
Proof. If Pk+1 is a subsection (or subpath) of Pk,we have that Pk = q + Pk+1 where q is a single link vector (the irst link vector on the shortest path from hop k to the destination). The first condition then is immediate from Eq. (A.2) in the Appendix
A.
The second condition follows from the corollary that subsections of shortest paths are not necessarily shortest paths. Hence, we may have that, referring to Fig. 5, the path Pk = q + Q is the shortest path from k to the destination while Pk+1 = P is the shortest path from hop k+l to that same destination. Thus, l(P + q) > l(Q + q) and l(Q) > l(P). Using Eq. (A.2) gives l(Q + q) ^ l(Q). Combining all inequalities leads to l(P + q) >
l(Q+q) > l(Q) > l(P) or l(Pk) > l(Pk+1). □
Since SAMCRA is exact, the corollary is not just an artefact of SAMCRA, but a property of multiple constraints routing in general.

Fig. 5. Construction of hop-by-hop paths via SAMCRA.
Lemma 1 implies that the sequence of the lengths of the shortest paths from the different intermediate hops to the (same) destination is non-increasing:
/(Pi) > 1{P2) > ... > l(Pk) > l{Pk+{) > ••• > 0.
The end-to-end path from source node S to destination node D computed by hop-by-hop SAMCRA consists of the node list {S, n2,..., nj,..., D} where nj is the second node in the node list of path
Pj-i-
Property 1. The end-to-end path computed by hop-by-hop SAMCRA is guaranteed to be loop free.
Proof. Property 1 is a consequence of Lemma 1. Indeed, a loop means that at some hop k, the path has returned to a node n previously visited at hop j with j < k. Further, the presence of a loop implies that not all Pk are subsections of P1 and that, in the sequence of lengths of shortest paths between hop j and hop k, there must be at least one strict inequality sign (Lemma 1) yielding l(Pj) > l(Pk) with j < k. Let P denote the shortest path from node n to the destination. At hop j, we first arrive at node n and we have Pj = P. Since the loop returns during hop k at node n again, we obtain Pk = P implying that Pj = Pk and thus l(Pj) = l(Pk) for j < k. This condition contradicts the previous one based on Lemma 1.    □
Corollary. Removing dominated paths Q for which holds that Wj(P) ^ Wj(Q) and thus l(P) ^ l(Q) also eliminates loops.
In conclusion, we have demonstrated that 'hop-by-hop destination based only' multiple constraint routing with SAMCRA is loop-free. In case of an approximate QoS routing algorithm that cannot guarantee to ind always the shortest path towards the destination in every hop, the arguments used in the proof of Property 1 and Lemma 1 do not exclude the occurrence of loops. Hence, so far, we have shown that exactness is a sufficient condition. It remains to show that exactness is also necessary. Therefore, it suices to illustrate with an example that loops can indeed occur if the xth shortest path is chosen with x > 1.
Consider the simple graph of Fig. 6 where a path is to be found from source A to destination B subject to a constraints vector L =(13,13). If the source node A uses an exact computation for the QoS path towards B, it finds two paths: ADB with length max(4/13,12/13) = 12/13 and ACDB with length max(9/13,11/13) = 11/13 which is clearly the shortest path from A to B. Hence, source node A forwards the packet for B to C. Suppose now that node C uses an approximate algorithm, such as TAMCRA with k = 1. Node C receives the packets without remembering where they came from (i.e. 'hop-by-hop destination based only') and it computes the path towards B as follows (very similar to Dijkstra's greedy algorithm). First the adjacent nodes D and A are investigated with length 6/13 and 1/13 respectively. Second, the computation proceeds with A (the smaller of the two length so far) and we ind that the path CAD has length 5/13. Now, since C computes paths with an approximate QoS algorithm where k = 1, it only stores the shortest path to node D, which is CAD. Hence, C computes the path CADB with length 1. However, although the path CADB just satisfies the constraints, it clearly creates a loop because the packet is sent back to the source node A.
This example shows that approximate algorithms can produce loops by excluding intermedi

Fig. 6. Example demonstrating the existence of a loop with approximate QoS routing.
ate paths. In fact, C has stored the second shortest path to B instead of the shortest. If C had used TAMCRA with k = 2, the correct path (without loops) would have been found. Indeed, both paths CD and CAD would have been checked, which would have resulted in CDB with length 10/13 instead of CADB with length 1. In that case, C would have forwarded the packet for B to D, without any bouncing (or loops).
3.2. HbHDBO QoS routing cannot guarantee to find the exact result
We now investigate the quality of QoS routing relying on a hop-by-hop approach only based on the destination. In particular, only the shortest path (according to SAMCRA's non-linear length definition) is computed in each hop towards the destination (ignoring the previous history where it came from). The resulting end-to-end path computed in HbHDBO mode via SAMCRA is compared, as shown in Fig. 1, with the shortest end-to-end path satisfying all QoS constraints.
The following example topology (Fig. 7) demonstrates that (exact) SAMCRA operating in a distributed HbHDBO mode cannot guarantee to ind the exact result.
Each link is characterized by three additive QoS metrics (or vector components). Suppose that node i wants to send packets to node a according to a certain CoS. The CoS is characterized by a constraint for each of the graph metrics. In this example, the constraints are chosen to be 14, 11 and 22 respectively. Using SAMCRA, node i cal

Fig. 7. Example topology.
culates the shortest path to node a as shown in Fig. 8.
The shortest path from node i to node a runs over nodes/, e and c and has a path length of 0.95. Thus, all constraints are satisfied. Node i will store in its routing table that the next hop for destination a and the class of service speciied by constraints (14, 11, 22) is node /. Node /will construct its routing table in a similar manner: it uses SAMCRA to calculate the shortest path to destination a subject to the constraint vector (14, 11, 22). So far, no deiciencies have occurred for the packets originated at node i because the shortest path from node i to node a coincides with the shortest path from node / to node a.
However, this is no longer the case for node e! The shortest path from node e to node a for the class of service characterized by the constraint vector (14, 11, 22) is shown in Fig. 9. The shortest path from node e to node a runs over node b and not over node c. The path over node c is shown with dashed lines and has a path length of 0.77 which exceeds the path length of the path e-b-a which is only 0.73. Thus node e will store in its routing table that all packets for destination a and the above speciied CoS need to be forwarded to node b. Packets from node i will thus no longer follow the shortest path between node i and node a.
Fig. 10 shows both the end-to-end hop-by-hop path and the shortest path from node i to node a for the CoS speciied by the constraint vector (14, 11, 22). The shortest path satisfies all constraints but the hop-by-hop path has an unacceptable path length of 1.09 > 1. In particular, the box in Fig. 10 indicates that the hop-by-hop path satisies the constraints for the irst and the third metric but violates the constraints for the second metric. Thus, although there is a path from node i to node a satisfying all constraints, in a distributed hop-by-hop mode, this example illustrates that the packets will follow a path that violates one of these constraints.
In this example, it can be veriied that the hop-by-hop path turns out to be the third shortest path from node i to node a for the CoS speciied by constraints (14, 11, 22). The second shortest path is P(i, f, d, b, a). The path length of the second shortest path satisfying all constraints is exactly

Fig. 10. Comparison between the shortest path (in bold) and the hop-by-hop path (arrows).
1.00, which means that at least one of the con-       N nodes and independently chosen links with
straints is precisely met. probability p. Each link is further specified by a
vector with m components, which are all uniformly distributed random variables on [0,1]. We further
4. Performance analysis in simple random graphs denote the class GP(N) with uniformly distributed
link weights by RGU. In each graph of RGU, the The simulations were performed on (simple)       shortest path between source (node 1) and desti-
random graphs of the class GP (N) [3] consisting of       nation (node N) subject to a constraints vector
with components Lj = N (for all 1 < j < m) has been computed with SAMCRA in the two modes as shown in Fig. 1.
The value Lj = N for each constraint j implies that all paths from source to destination lie within the constraints. Via the exact source-routing mode, a list of all possible shortest paths was computed as reference to compare the HbHDBO path. For each quantity of interest such as the xth shortest path, difference in the length etc., one million RGU graphs were simulated, a number satisfactorily large to obtain accurate probability density functions up to roughly 10—4 for that quantity. Similar to one-dimensional shortest path problems (see Ref. [24]), the dependence of the shortest path properties to the link density p (above the disconnectivity threshold) in higher dimensions also was found negligibly small. This presumably general law for the class of RGU allows us to eliminate the extensive simulations as function of p. Besides the ease in computing a graph of the RGU class, its use was mainly motivated by an analogy to linear system theory. By applying an impulse to a linear system, all internal modes are excited. Similarly, by simulating a large number of diferent graphs in RGU, the underlying randomness was expected to trigger the different 'modes' of the hop-by-hop QoS routing problem. We emphasize, however, that all simulation results only apply to the class RGU.

x-shortest path [x]
Fig. 11. The pdf of the ranking in shortestness of the hop-by-hop (hp) shortest path for m = 2.
4.2. The difference in end-to-end path length
Fig. 12 shows that, although the exact path (x = 1) may not be found, the relative difference in length between the HbHDBO and shortest path in the class RGU is surprisingly small (for x > 0be-low a probability of 0.01) and that it decreases faster than an exponential. In any topology, Property 2 upper bounds the relative error in case one wrong decision is made.
4.1. The xth shortest path found with HbHDBO QoS routing
For various number of nodes N and link density
p, Fig. 11 plots the probability that the HbHDBO
path is the xth shortest path. The exact solution (x = 1) is found in 89.4% of the cases in RGU with N = 100. When the network size N increases, the probability that the exact solution is found decreases as expected because the number of paths between source and destination increases with N and, hence, also the average hop count and the average number of decisions which enhances the chance on wrong decisions. When constraints (L,- < N — 1) are imposed, the number of paths between source and destination will increase, of course, less rapidly.

Fig. 12. The probability that the length of the HbHDBO path is x% longer than the shortest path for m = 2.
Property 2. If the HbHDBO path only makes one wrong decision (compared to the true shortest path), the resulting length never exceeds 100% of the length of the (exact) shortest path. Moreover, this bound is sharp.
Proof. Consider the graph in Fig. 5. Assume that the shortest path from source k to destination d consists of the paths q and P with length l(q + P) while the shortest path from k + 1to d is Q. Thus, l{Q) < l(P). Ignoring the past history, the hop-by-hop path makes a wrong decision at node k + 1 where it follows path Q resulting in a final path with length l(q + Q) > l(q + P).
Using the properties of the length of a vector (see Appendix A), we can arrange the lengths in increasing order as follows:
l(Q) < l(P) < l(q + P) < l(q + Q) < l(q) + l(Q)
< l(q) + l(P) < l(q) + l(q + P).
The relative diference in length therefore has an upper bound:
l(q + Q) — l(q + P)     l(q) + l(q + P) —l(q + P) l(q + P) < l(q + P)
=     l(q)     < 1 l(q + Pp   "
Fig. 13 demonstrates that this bound is sharp.   □
The proof shows that a wrong hop decision at the end of the path (near the destination) can have more severe consequences than a wrong decision near the source (the first hop is always correct!), because l(q) tends to l(q + P) when we hop to

Fig. 13. The shortest path is drawn in bold, whereas the HbHDBO path is in dotted line. The constraint vector is (1000, 1000, 1000). Referring to the notation of previous figure, we have that l(Q) = 0.499, l(P) = 0.5, l(q + P) = 0.510 and l(q + Q) = 0.999 resulting in a relative difference of 96%.
wards the destination. An extension of Property 2 to multiple wrong decisions is straightforward resulting in an overall upper bound equal to the sum of the independent, single, wrong hop upper bounds.
4.3. Simulated complexity of SAMCRA in the class RGU
Fig. 14 plots the minimum queue size needed to find the exact path. This minimum queue size kmin is, in fact, the maximum queue size that appears in a node during the evaluation of SAMCRA. If a lower queue size k < kmin were used, the exact shortest path would not be found. The constraints in the simulation-program were denoted as doubles (real numbers), which makes the upper bound on the queue-size knax (2) extremely large. With an expected £[kmin]?s 1, these simulations suggest that the average complexity for the class of RGU is O(N log N + m£).
4.4. The influence of the number of constraints m
Figs. 15 and 16 show the influence of the dimension m on the quality of the HbHDBO path. As well known (see also Corollary 1 in the Appendix A) for a single metric or m = 1, the HbHDBO path is also the exact shortest path. In higher dimensions (m > 1) and in the class RGU,

Fig. 14. The probability density function of kmin. Note that -E[k^n]~ 1 for N up to 1600 and that max(kmin) does not exceed 10.

x-shortest path [x]
Fig. 15. Probability that the hop-by-hop path equals the x-shortest path in various dimensions m for N = 20 and p = 0.2.

Fig. 16. The probability that the relative length difference is x% for N = 20 and p = 0.2.
we observe that the case with m = 2 is worst and that there is a noticeable decrease towards the exact solution as m increases.
Property 3. If the m components of the link weight vector are independent random variables and the constraints Lj are such that 0 ^ Wj/Lj ^ 1, any path with K hops has precisely a length (as defined in Eq. (1)) equal to K in the limit m — oo.
Proof. Consider a path P from source to destination with K hops. The vector sum of the weights along this path equals wj(P) = 2i—/ePwj(i — I) and 0<wj(, — l)/Lj<1. Then Prhv,(P)/Lj>K]=0. Moreover, with definition (1), Pr[l(P)>k]=0.
Since we assume that the link weights are independent, we have Pr[l(P) < K — s]=n1<j<m Pr[wj(P)/Lj < K — s]. But, for any real s > 0 and each j,Pr[wj(P)/ Lj<K — s]< 1, Pr[l(P)<K — s]=0
e, in that limit
for m — oo. Hence, in that limit, each path with K hops has length precisely equal to K.   □
For m —o , the m-dimensional problem reduces to a single metric problem where the path that minimizes the hopcount is also the shortest path. As the latter problem is exactly solvable (via Dijkstra), this explains the observed decrease towards the exact solution as m increases. Notice that the limit law in Property 3 is quite general: It only assumes independent link weight components Wj and constraints Lj such that 0 < Wj /Lj < 1 and it holds for any graph.
5. Active networking
The model assumption of pre-computed routing tables as in current Internet, is actually limiting the lexibility and quality of hop-by-hop QoS routing. Active networking, a new dynamic concept in networking, can provide the necessary lexibility to guarantee QoS in hop-by-hop routing. In active networks, the active nodes can perform computations on the data part of the datagram and the users, on the other hand, can ''program'' the network by supplying the active node with their instruction code [21]. Two 'active' scenarios for hop-by-hop QoS routing with SAMCRA are discussed:
1. The first scenario will be referred to as ''active constraints''. Similar as in Q-OSPF (RFC2676), the routing table at a node contains the next hop (computed with SAMCRA) for each class of service (CoS) specified by a constraint vector LCoS for that node. Each packet contains the 'active' constraints vector L which is decreased at each node by the link weight vector of the previous hop. The packet is classiied (and accordingly forwarded) in that CoS for which Lj > LCoSjj for 1 < j < m and for which the next upper CoS, say CoS', has at least one   component   j   violating   the   condition
Lj > LCoS'j. This type of active routing excludes forwarding over paths that violate the constraints, without adding much complexity: O(Nm) per packet, because there are not more than N — 1 hops and at each node there are m subtractions.
2. In the second scenario (called ''active SAM-CRA'') the packet has an extra ield containing the link weight vector of the intermediate path traversed so far and the original (ixed, not decreased) constraint vector L. At each hop, the link weight vector and the path towards the destination is computed. Active SAMCRA is exact as can be veriied from SAMCRA's meta-code at the price of a higher complexity: O(kN log(kN)+ k2m£ + m) per packet per node.
Both scenarios guarantee that a path within the constraints is returned ifsuch a path exists. The diference between ''active constraints'' and ''active SAMCRA'' is that the irst might return non-shortest (feasible) paths, whereas the second always returns the shortest path. Since our goal is to ind a path within the QoS constraints, the irst approach prevails over the second, due to its smaller complexity. However, if we consider a rapidly changing topology (due to coupling of the link weights with the traffic in that link for instance), active SAMCRA is to be preferred because computing one path costs less than computing a whole routing table at each frequently occurring topology update.
6. Summary
We have investigated the problem of connectionless QoS routing. To limit the number of routing entries, we have investigated the possibility of forwarding packets based on the destination only. We have irst demonstrated that an exact algorithm as SAMCRA is loop free when used in hop-by-hop mode. Moreover, with a non-linear path length deinition, an exact algorithm is not only suicient but also necessary to avoid loops. We have further shown that ''hop-by-hop destination based only'' QoS routing, even with an exact routing algorithm (and contrary to 'single metric routing' as in OSPF), does not guarantee that the exact end-to-end solution is found. Extensive simulations in the class of RGU have shown that deviations from the exact results are small and occur infrequently. Moreover, the maximum relative diference in length can be bounded.
The intractability of exact QoS routing with multiple additive link measure (due to NP-com-pleteness) is only one of the complicating factors in the QoS routing problem. Indeed, topologically SAMCRA does not scale much worse than Dijk-stra. Moreover, simulations in RGU (up to N = 1600 nodes) indicate that the minimum queue size needed to retrieve the exact result is much smaller than the worst case prediction since kmin C kmax. In spite random graphs do not resemble actual communication networks, we believe that future topologies due to the increased importance of wireless and ad hoc (or imbedded) networks, may possess a larger degree of randomness both in topological structure as in the link weights. However, mainly the granularity of the constraints as exhibited by expression (2) for kmax determines the complexity. Hence, a careful design of QoS routing (thus both algorithm and protocol) may beneit from a coarse granularity in the constraints (i.e. decreasing kmax). Also the dynamic behavior of QoS routing (not considered here, but see Ref. [22]) simpliies as the number of topology updates triggered by signiicant changes in the link metrics diminishes accordingly. Thus, we believe that SAMCRA together with a minimum acceptable kmax, is a promising strategy to provide a notion (hard guarantees are shown to be impossible) of QoS in the hop-by-hop Internet of today.
Finally, if the current Internet mode of HbHDBO routing (ignoring the past path history) is relaxed, at the expense of more computations, hop-by-hop routing with active packets can be exact provided the length vector of the path traversed so far and the constraint vector is stored in each packet. This observation is directly veriied from the meta-code of SAMCRA.
Appendix A
The definition of the length of a vector p, such as Eq. (1), satisies the criteria [11,19]:
1. l(p) > 0 for all non-zero vectors and l(p) = 0 only if p = 0,
2. for all vectors p and u holds the triangle inequality
l(p + u) < l(p) + l(u). (A.1)
If p and u are non-negative vectors (i.e. all vector components are non-negative), we have
l(p + u) ^ l(p)(A.2)
because the length of a non-negative vector cannot decrease if a non-negative vector is added.
For example, if p =[1,3, 5,1,9], u =[4, 5,2, 1,0] and L =[10,1,10,10,1], then, using (1), p + u =[5, 8, 7,2, 9], l(p)=9 and relation (A.2) gives l(p + u) = l(p) = 9.
Corollary 1. Subpaths of shortest paths in multiple dimensions (m > 1) are not necessarily shortest paths.
This is an important corollary that follows from non-linear path length definitions as Eq. (1) or
l(p)= (£ wn (a.3)
The proof relies on the inequality (A.1). Consider two paths P1 and P2 for which l(P1) < l(P2) and assume that, by adding a same link a to both paths, the paths P3 and P4 can be constructed.
1. Let us first focus on the case where the equality sign in Eq. (A.1) holds, typically if q = 1 in Eq. (A.3). By construction, we have l(Pj) = l(P + a) and by Eq. (A.1) with the equality sign, l(P1 + a) = l(P1) + l(a) and analogously,    l(Pt ) = l(P2 + a) = l(P2) + l(a).    Since
l(P1) < l(P2), there holds that l(P3) < l(P4) or, the
subpaths of shortest path with linear deinition of path length are again shortest paths, leading to the well-known and intuitive result.
2. When the inequality sign holds in Eq. (A.1), typically if q > 1 as readily verified from Eq. (A.3), we arrive in a similar fashion to the set of inequalities l(P4) = l(P2 + a) < l(P2) + l(a); l(P3) = l(P + a) < l(P1) + l(a) and l(P) < /(P.). However, from this set, it cannot be concluded whether l(Pj) < l(P4) or l(P,) > l(Pt). It suffices to show that the latter situation may exist in order to prove the corollary. This can be illustrated on the example graph of Fig. 7. For the constraints (14, 11, 22), the shortest path from node a to node i runs over node c, e and fas shown in Fig. 8. According to the definition (1), the path length of P(i, f, e, c, a) equals 0.95 which means it satisies all constraints. However, as illustrated in Fig. 9, the shortest path from node a to node e does not traverse node c but node b.   □
Theorem. SAMCRA is exact
Proof. SAMCRA is essentially a brute-force algorithm that eiciently reduces its search-space. SAMCRA uses a k-shortest path approach. As shown by Chong et al. [6], this k-shortest path approach will return all (loop-free) paths between source and destination, provided k is chosen large enough. It can be veriied from SAMCRAs meta-code that in the absence of the search-space reduction, SAMCRA evaluates every possible path from source to destination, and therefore is exact by definition. 4 To prove that SAMCRA in its search-space reduction is exact, we need to prove that the reductions do not exclude the shortest path.
1. Lines 8 and 9 in SAMCRA's meta-code cause the algorithm to stop when the extracted path belongs to the destination node. Since line 6 only extracts the path with the shortest length, all other path lengths left in the queue are equal or longer than the length of the extracted path and hence will never become the shortest path. The shortest path from source to destination has been attained and it is therefore useless to proceed with the algorithm. We have therefore justified lines 8 and 9.
2. SAMCRA discards all paths that exceed the constraints (line 16: if (LENGTH < 1.0)). Since these paths cannot accommodate the requested QoS, there is no need to examine them.
3. SAMCRA has two ways to remove loop-containing paths from the search-space: (a) Line 12 ensures that the path does not return to the
The proof that SAMCRA without search-space reduction returns all paths is given in Ref. [20].
node it just came from. This way of preventing loops only eliminates loops between two adjacent nodes. (b) Loops containing more nodes are targeted by only allowing non-dominated paths (lines 15 and 16) as follows from the corollary in Section
4.1.
4. Finally, each new entry is compared to the minimum entry in the destination-queue. If we already have a path Pa with length l(Pa),wecan discard all other (sub)-paths P6 with length l(Pa) ^ l(P&), because their length will never become smaller than l(Pa).    □
References
[1] G. Apostolopoulos, D. Williams, S. Kamat, R. Guerin, A.
Orda, T. Przygienda, QoS Routing Mechanisms and OSPF
extensions, RFC 2676, August 1999. [2] G. Apostolopoulos, R. Guerin, S. Kamat, S.K. Tripathi,
Improving QoS routing performance under inaccurate link
state information, ITC16, 1999, pp. 1351-1362. [3] B. Bollobas, Random Graphs, Academic Press, London,
1985.
[4] S. Chen, K. Nahrstedt, On finding multi-constrained paths,
Proc. ICC'98, Atlanta, Georgia, 1998. [5] S. Chen, K. Nahrstedt, Distributed quality-of-service
routing in ad hoc networks, IEEE J. Sel. Areas Commun.
17 (8) (1999) 1488-1505. [6] E.I. Chong, S. Maddila, S. Morley, On finding single-source single-destination k shortest paths, J. Comput. Inf.,
special issue ICCI'95, 1995, pp. 40-47. [7] T.H. Cormen, C.E. Leiserson, R.L. Rivest, Algorithms,
MIT Press, Boston, 1991. [8] H. De Neve, P. Van Mieghem, A multiple quality of service
routing algorithm for PNNI, IEEE ATM Workshop,
Fairfax, May 26-29, 1998, pp. 324-328. [9] H. De Neve, P. Van Mieghem, TAMCRA: a tunable
accuracy multiple constraints routing algorithm, Comput.
Commun. 23 (2000) 667-679. [10] M.R. Garey, D.S. Johnson, Computers and Intractability,
A Guide to the Theory ofNP-Completeness, Freeman, San
Francisco, 1979. [11] G.H. Golub, C.F. Van Loan, Matrix Computations, first
ed., North Oxford Academic, Oxford, 1983. [12] R.A. Guerin, A. Orda, QoS routing in networks with
inaccurate information: theory and algorithms, IEEE/
ACM Trans. Network 7 (3) (1999) 350-364. [13] L. Guo, I. Matta, Search space reduction in QoS routing,
Proceedings of the 19th International Conference on
Distributed Computing Systems, Austin, Texas, June 1999.
[14] R. Hassin, Approximation schemes for the restricted shortest path problem, Math. Oper. Res. 17 (1) (1992) 36-42.
[15] M.I. Henig, The shortest path problem with two objective functions, Eur. J. Oper. Res. 25 (1985) 281-291.
[16] J.M. Jaffe, Algorithms for finding paths with multiple constraints, Networks 14 (1984) 95-116.
[17] T. Korkmaz, M. Krunz, Multi-constrained optimal path selection, INFOCOM 2001.
[18] F.A. Kuipers, Hop-by-hop routing with QoS constraints, Master Thesis in Electrical Engineering at Delft University of Technology, 2000.
[19] H.L. Royden, Real Analysis, third ed., Macmillan Publishing Company, New York, 1988.
[20] B. Sales, P. Van Mieghem, Dual-mode routing: a general framework for IP over ATM integrated routing, Proceedings of the Third IEEE Symposium on Computers and Communications (ISCC'98), June 30-July 2, Athens (Greece), 1998, pp. 326-330.
[21] D.L. Tennenhouse, S.J. Garland, L. Shrira, M.F. Kaa-shoek, From Internet to ActiveNet, RFC, January, http:// www.tns.lcs.mit.edu/publications/rfc96/, 1996.
[22] P. Van Mieghem, H. De Neve, Aspects of quality of service routing, SPIE'98, Boston, November 1-5, [3529A-05], 1998.
[23] P. Van Mieghem, A lower bound for the end-to-end delay in networks: Application to voice over IP, IEEE Globe-com'98, November 8-12, Sydney (Australia), 1998, pp. 2508-2513.
[24] P. Van Mieghem, G. Hooghiemstra, R. van der Hofstad, A scaling law for the hopcount in Internet, Delft University of Technology, report 2000125, 2000, http://wwwtvs.et. tudelft.nl/people/piet/telconference.html.
[25] Z. Wang, J. Crowcroft, QoS routing for supporting multimedia applications, IEEE J. Sel. Areas Commun. 14 (7) (1996) 1188-1234.
[26] Z. Zhang, C. Sanchez, B. Salkewicsz, E. Crawley, Quality of service extensions to OSPF or quality of service path first routing (QOSPF), draft-zhang-qos-ospf-01, 1997.
Piet Van Mieghem has obtained the Master and Ph.D. in Electrical Engineering from the K.U. Leuven (Belgium) in 1987 and 1991, respectively. He has joined the Interuniversity Micro Electronic Center (IMEC) from 1987-1991. He was a visiting scientist at MIT, department of electrical engineering from 1992 to 1993. From 1993 to 1998, he was working in Alcatel Corporate Research Center in Antwerp where he has gained experience in performance analysis of ATM systems and network architectural concepts of both ATM networks (PNNI) and the Internet. Currently, he is full professor at Delft University ofTechnology with a chair in telecommunication networks. The main theme of the research is evolution of the Internet architecture towards a broadband and QoS-aware network.

Hans De Neve received a Master in Electrical Engineering from the University of Ghent in 1991, a Master in Physics of Microelectronics and Materials Science from the University of Leuven in 1992 and a Ph.D. in Electrical Engineering from the University of Ghent in 1997. From 1997, he has been working for the Alcatel Corporate Research Center in Antwerp, building expertise with routing protocols and routing algorithms. Currently he is part of the Network Strategy Group of Alcatel covering the domains of IP Virtual Private Networks and IP Quality of Service.

Fernando A. Kuipers received the M.Sc. degree in electrical engineering at Delft University of Technology in 2000. Currently he is working towards his Ph.D. degree at the same faculty. He is also a member of the DIOC (interdisciplinary research center) on the Design and Management of Infrastructures, where he is taking part in the Telecommunications project. His current research interests include QoS-based routing, multi-constrained path selection, routing with inaccurate/ incomplete information and evaluating the applicability of certain telecommunication-solutions to road-traffic problems.