Optimal partition of QoS requirements on unicast paths and multicast trees.
We investigate the problem of optimal resource allocation for end-to-end QoS requirements on unicast paths and multicast trees. Specifically, we consider a framework in which resource allocation is based on local QoS requirements at each network link, and associated with each link is a cost function that increases with the severity of the QoS requirement. Accordingly, the problem that we address is how to partition an end-to-end QoS requirement into local requirements, such that the overall cost is minimized. We establish efficient (polynomial) solutions for both unicast and multicast connections. These results provide the required foundations for the corresponding QoS routing schemes, which identify either paths or trees that lead to minimal overall cost. In addition, we show that our framework provides better tools for coping with other fundamental multicast problems, such as dynamic tree maintenance.
INTRODUCTION
Broadband integrated services networks are expected to support
multiple and diverse applications, with various quality of
service (QoS) requirements. Accordingly, a key issue in the design
of broadband architectures is how to provide the resources
in order to meet the requirements of each connection.
Supporting QoS connections requires the existence of several
network mechanisms. One is a QoS routing mechanism, which
sets the connection's topology, i.e., a unicast path or multicast
tree. A second mechanism is one that provides QoS guarantees
given the connection requirements and its topology. Providing
these guarantees involves allocating resources, e.g., bandwidth
and buffers, on the various network elements. Such a consumption
of resources has an obvious cost in terms of network per-
formance. The cost at each network element inherently depends
on the local availability of resources. For instance, consuming
all the available bandwidth of a link, considerably increases the
blocking probability of future connections. Clearly, the cost
of establishing a connection (and allocating the necessary re-
sources) should be a major consideration of the connection (call)
admission process. Hence, an important network optimization
problem is how to establish QoS connections in a way that minimizes
their implied costs. Addressing this problem impacts both
the routing process and the allocation of resources on the selected
topology. The latter translates into an end-to-end QoS
requirement partition problem, namely local allocation of QoS
requirements along the topology.
The support of QoS connections has been the subject of extensive
research in the past few years. Several studies and proposals
considered the issue of QoS routing, e.g., [2], [8], [9], [21], [24]
and references therein. Mechanisms for providing various QoS
guarantees have been also widely investigated, e.g. [7], [22].
email:fdeanh@tx,ariel@eeg.technion.ac.il
Although there are proposals for resource reservation, most notably
RSVP [3], they address only the signaling mechanisms and
do not provide the allocation policy. Indeed, the issue of optimal
resource allocation, from a network perspective, has been
scarcely addressed. Some studies, e.g. [13], consider the spe-
cific, simple, case of constant link costs, which are independent
of the QoS (delay) supported by the link. Pricing, as a network
optimization mechanism, has been the subject of recent studies,
however they either considered a basic best effort service envi-
ronment, e.g. [14], [18], or simple, single link [17] and parallel
link [20] topologies.
In this paper, we investigate the problem of optimal resource
allocation for end-to-end QoS requirements on given unicast
paths and multicast trees. Specifically, we consider a frame-work
in which resource allocation is based on the partition of
the end-to-end QoS requirement into local QoS requirements
at each network element (link). We associate with each link a
cost function that increases with the severity of the local QoS
requirement. As will be demonstrated in the next section, this
framework is consistent with the proposals for QoS support on
broadband networks. Accordingly, the problem that we address
is how to partition an end-to-end QoS requirement into local
requirements, such that the overall cost is minimized. This is
shown to be intractable even in the (simpler) case of unicast
connections. Yet, we are able to establish efficient (polynomial)
solutions for both unicast and multicast connections, by imposing
some (weak) assumptions on the costs. These results provide
the required foundations for the corresponding QoS routing
schemes, which identify either paths or trees that lead to minimal
overall cost. Moreover, we indicate how the above frame-work
provides better tools for coping with fundamental multi-cast
problems, such as the dynamic maintenance of multicast
trees.
A similar framework was investigated in [4], [19]. There too,
it was proposed that end-to-end QoS requirements should be
partitioned into local (link) requirements and the motivation for
this approach was extensively discussed. [19] discussed unicast
connections and focused on loss rate guarantees. It considered
a utility function, which is equivalent to (the minus of) our cost
function. However, rather than maximizing the overall utility,
[19] focused on the optimization of the bottleneck utility over
the connection's path. That is, their goal was to partition the
end-to-end loss rate requirement into link requirements over a
given path, so as to maximize the minimal utility value over the
path links. Specifically, [19] investigated the performance of a
heuristic that equally partitioned the loss rate requirements over
the links. By way of simulations, it was indicated that the performance
of that heuristic was reasonable for paths with few (up
to five) links and tight loss rate requirements; this finding was
further supported by analysis. However, it was indicated that
performance deteriorated when either the number of links became
larger or when the connection was more tolerant to packet
loss. It was concluded that for such cases, as well as for alternate
QoS requirements (such as delay), the development of optimal
QoS partition schemes is of interest. [4] considered multicast
trees and a cost function that is a special case of ours. Each
tree link was assigned an upper bound on the cost, and the goal
was to partition the end-to-end QoS into local requirements, so
that no link cost exceeds its bound. Specifically, [4] considered
two heuristics, namely equal and proportional partitions,
and investigated their performance by way of simulations. It
was demonstrated that proportional partition offers better performance
than equal partition, however it is not optimal. [4]
too concluded that more complex (optimal) partition schemes
should be investigated. These two studies provide interesting
insights into our framework, and strongly motivate the optimization
problems that we investigate.
Another sequence of studied that is related to the present one
is [9], [16]. These studies investigated QoS partitioning and
routing for unicast connections, in networks with uncertain pa-
rameters. Their goal was to select a path, and partition the QoS
requirements along it, so as to maximize the probability of meeting
the QoS requirements. As shall be shown, the link probability
distribution functions considered in [9], [16] correspond to a
special case of the cost functions considered in the present pa-
per. The algorithms presented in [16] solve both the routing and
the QoS partition problem for unicast connections, under certain
assumptions. The present study offers an improved, less restric-
tive, solution for unicast, and, more importantly, a generalized
solution for multicast.
The general resource allocation problem is a constraint optimization
problem. Due to its simple structure, this problem
is encountered in a variety of applications and has been studied
extensively [12]. Optimal Partition of end-to-end QoS requirements
over unicast paths is a special case of that problem,
however the multicast version is not. Our main contribution
is in solving the problem for multicast connections. We also
present several algorithms for the unicast problem, emphasizing
network related aspect, such as distributed implementation.
The rest of this paper is structured as follows. Section II formulates
the model and problems, and relates our framework to
QoS network architectures. The optimal QoS partition problem
for unicast connections is investigated in Section III. The optimal
partition problem for multicast connections is discussed in
Section IV. This problem is solved using a similar approach to
that used for unicast, nonetheless the analysis and solution structure
turn out to be much more complex. Section V applies these
findings to unicast and multicast QoS routing. Finally, concluding
remarks are presented in Section VI. Due to space limits,
many technical details and proofs are omitted from this version
and can be found in [15].
II. MODEL AND PROBLEMS
In this section we present our framework and introduce the
QoS partition problem. We assume that the connection topology
is given, i.e., a path p for unicast, or a tree T for multicast.
The problem of finding such topologies, namely QoS routing,
is briefly discussed in Section V. For clarity, we detail here
only the framework for unicast connections. The definitions and
terminology for multicast trees are similar and are presented,
together with the corresponding solution, in Section IV.
A. QoS Requirements
A QoS partition of an end-to-end QoS requirement Q, on a
path p, is a vector l2p of local QoS requirements,
which satisfies the end-to-end QoS requirement, Q.
There are two fundamental classes of QoS parameters: bottleneck
parameters, such as bandwidth, and additive parame-
ters, such as delay and jitter. Each class induces a different
form of our problem, and the complexities of the solutions are
vastly different. For bottleneck parameters, we necessarily have
determined by the bottle-neck
link, i.e., allocating more than Q
induces a higher cost, yet does not improve the overall QoS, the
optimal partition is x
. For additive QoS require-
ments, a feasible partition, xp , must satisfy
In
this case, the optimal QoS partition problem is intractable [16],
however we will show that, by restricting ourselves to convex
cost functions, we can achieve an efficient (tractable) solution.
Some QoS parameters, such as loss rate, are multiplicative, i.e.,
l2p (x l ). For instance, for a loss rate QoS requirement
L, we have case too can be expressed as an
additive requirement, by solving for (\Gamma log Q); indeed, the end-
to-end requirement becomes (\Gamma log
an additive requirement.
There are QoS provision mechanisms, in which the (additive)
delay bounds are determined by a (bottleneck) "rate". A notable
example is the Guaranteed Service architecture for IP [23],
which is based on rate-based schedulers [7], [22], [25], [26].
In some cases, such mechanisms may allow to translate a delay
requirement on a given path into a bottleneck (rate) require-
ment, hence the partitioning is straightforward. However, such
a translation cannot be applied in general, e.g. due to complications
created by topology aggregation and hierarchical routing. 2
Hence, our study focuses on the general partition problem of
additive QoS requirements.
B. Cost Functions
As mentioned, we associate with each local QoS requirement
value x l , a cost c l (x l ), and make the natural assumption
that c l (x l ) is higher as x l is tighter. For instance, when x l
stands for delay, c l (x l ) is a non-increasing function, whereas
when x l stands for bandwidth, c l (x l ) is non-decreasing. The
overall cost of a partition is the sum of the local costs, i.e.,
The cost may reflect the resources, such as bandwidth, needed
to guarantee the QoS requirement. Alternatively, the cost may
be the price that the user is required to pay to guarantee a specific
QoS. The cost may be associated with either the set-up or
the run-time phase of a connection. Also, it may be used for
1 This is also true for a multicast tree T.
2 Indeed, the ATM hierarchical QoS routing protocol [21], requires local (per
cluster) QoS guarantees.
network management to discourage the use of congested links,
by assigning higher costs to those links.
A particular form of cost evolves in models that consider
uncertainty in the available parameters at the connection setup
phase [9], [16], which we now briefly overview. In such mod-
els, associated with each link is a probability of failure f l (x l ),
when trying to set up a local QoS requirement of x l . The optimal
QoS partition problem is then to find a QoS partition-
that minimizes the probability of failure; that is, it minimizes
the product
we have log
l2p log f l (x l ), we can restate this problem back as a summa-
tion, namely we define a cost function for each link, c l
log f l (x), and solve for these costs.
C. Problem Formulation
The optimal QoS partition problem is then defined as follows.
Problem OPQ (Optimal Partition of QoS): Given a path p
and an end-to-end QoS requirement Q, find a QoS partition
x
l g l2p
, such that c
x
for any (other) QoS
partition x 0
.
This study focuses on the solution of Problem OPQ for additive
QoS parameters, which, as mentioned, is considerably more
complex than its bottleneck version. In Section III we solve the
problem for unicast paths, and in Section IV we generalize the
solution to multicast trees. For clarity, and without loss of gen-
erality, we concretize the presentation on end-to-end delay requirements

III. SOLUTION TO PROBLEM OPQ
In this section we investigate the properties of optimal solutions
to Problem OPQ for additive QoS parameters and present
efficient algorithms. These results will be used in the next section
to solve Problem MOPQ, i.e., the generalization of Problem
OPQ to multicast trees. As mentioned, Problem OPQ is
a specific case of the resource allocation problem. The fastest
solution to this problem, [5], requires O(jpj log D=jpj). 3 In
Section III-B we present a greedy pseudo-polynomial solution.
This solution provides appealing advantages for distributed and
dynamic implementations, as discussed in Section III-C. In
Section III-D we present a polynomial solution that, albeit of
slightly higher complexity than that of [5], provides the foundations
of our solution to Problem MOPQ. Finally, in Section III-E
we discuss special cases with lower complexity.
As mentioned, we assume that the QoS parameter is end-to-
delay. We further assume that all parameters are integers,
and that the link cost functions are non-increasing with the delay
and (weakly) convex.
A. Notations
xp (D) is a feasible partition of an end-to-end delay requirement
D on the path p if it satisfies
l2p x l - D. We omit
the subscript p and/or the argument D when there is no ambigu-
ity. x
(D) denotes the optimal partition, namely the solution of
Problem OPQ for an end-to-end delay requirement D and a path
3 jpj log(D=jpj) is also a lower bound for solving Problem OPQ [11], that is
no fully polynomial algorithms exist.
p. We denote by jx p j the norm
l2p jx l j, hence x is feasible if
The average ffi-increment gain for a link l is denoted by
The average ffi-move gain
is denoted by \Delta e!l (x;
B. Pseudo-polynomial Solution
Problem OPQ is a special case of the general resource allocation
problem which has been extensively investigated [11], [12].
With the (weak) convexity assumption on the cost functions, it
is a convex optimization problem with a simple constraint. It
can be proved [12] that a greedy approach is applicable for such
problems, namely it is possible to find an optimal solution by
performing locally optimal decisions.
GREEDY-ADD (D; ffi; c(\Delta); p):
do
5 return x
Fig. 1. Algorithm GREEDY-ADD
Algorithm GREEDY-ADD (Figure 1) employs such a greedy
approach. It starts from the zero allocation and adds the delay
bit-by-bit, each time augmenting the link where the (negative)
ffi-increment gain is minimal, namely where it most affects the
cost. Using an efficient data structure (e.g. a heap), each iteration
requires O(log jpj), which leads to an overall complexity of
O( D
log jpj). In [11] it is shown that the solution is ffi-optimal
in the following sense: if x ffi is the output of the algorithm and
x   is the optimal solution, then jx
Algorithm GREEDY-MOVE (Figure 2) is a modification of Algorithm
GREEDY-ADD that, as shall be explained in Section III-
C, has important practical advantages. The algorithm starts from
any feasible allocation and modifies it until it reaches an optimal
partition. Each iteration performs a greedy move, namely the
move with minimal (negative) ffi-move gain.
Fig. 2. Algorithm GREEDY-MOVE
Let '(x) be the distance of a given partition from the optimal
one, namely '(x) j jx \Gamma x   j, where x   is the optimal
partition that is nearest to x. The next lemma implies that Algorithm
GREEDY-MOVE indeed reaches a ffi-optimal solution.
Lemma 1: Each iteration of Algorithm GREEDY-MOVE decreases
'(x) by at least ffi, unless x is a ffi-optimal partition.
Lemma 1 implies that Line 3 can be used as a (ffi-)optimality
check. It also implies that the algorithm terminates with a ffi-
optimal solution and that the number of iterations is proportional
to '(x). Theorem 1 summarizes this discussion.
4 This also established the error due to our assumption of integer parameters.
Theorem 1: Algorithm GREEDY-MOVE solves Problem OPQ
in O( '(x)
log jpj).
Proof: By Lemma 1, there are at most '(x)=ffi iterations
and a ffi-optimal solution is achieved. Each iteration can be implemented
in O(log jpj) and the result follows.
C. Distributed and Dynamic Implementation
Algorithm GREEDY-MOVE can be employed in a distributed
fashion. Each iteration can be implemented by a control message
that traverses back and forth between the source and des-
tination. At each traversal e; l of Line 2 are identified and the
allocation change of the previous iteration is performed. This
requires O(jpj'=ffi) end-to-end messages. Such a distributed
implementation also exempts us from having to advertise the
updated link cost functions.
Algorithm GREEDY-MOVE can be used as a dynamic scheme
that reacts to changes in the cost functions after an optimal partition
has been established. Note that the complexity is proportional
to the allocation modification implied by the cost changes,
meaning that small allocation changes incur a small number of
computations.
D. Polynomial Solution
In this section we present an improved algorithm of polynomial
complexity in the input size (i.e., jpj and log D). In Section
IV, we derive a solution to Problem MOPQ using a similar
technique.
Algorithm BINARY-OPQ (Figure finds optimal solutions
for different values of ffi. The algorithm consecutively considers
smaller values of ffi, until the minimal possible value is reached,
at which point a (global) optimum is identified.
2 start from the partition
3 repeat
Fig. 3. Algorithm BINARY-OPQ
Obviously, the algorithm finds an optimal solution, since its
last call to GREEDY-MOVE is with 1. The number of iterations
is clearly of order O (log(D=jpj)). We need to bound
the number of steps required to find the ffi-optimal partition at
Line 4. Each iteration (except the first, for which
starts from a 2ffi-optimal partition and employs greedy moves
until it reaches a ffi-optimal partition. This bound is the same
for all iterations, since it is a bound on the distance between a
2ffi-optimal partition and a ffi-optimal partition.
Lemma 2: Let x GREEDY-MOVE(x; 2; c(\Delta); p). Then
This lemma, proven in [15], resembles the proximity theorem
presented in [11].
Theorem 2: Algorithm BINARY-OPQ solves Problem OPQ
in O (jpj log jpj log(D=jpj)).
Proof: By Lemma 2 and Theorem 1, each call
to GREEDY-MOVE requires O(jpj log jpj). Since there are
O(D=jpj) such calls, the result follows.
E. Faster Solutions
The following lemma, which is a different form of the optimality
test in Algorithm GREEDY-MOVE, provides a useful
threshold property of optimal partitions.
Lemma 3: Let \Delta   j min l2p \Delta l
For all l 2 p, \Delta l (d; \Gamma1) is a non-increasing function (c l is
convex) and (by definition) \Delta l (d
the threshold \Delta   relates to the optimal allocation as follows:
l - d , \Delta l (d;
This implies that an optimal solution to Problem OPQ can
be found by selecting the D largest elements from the set
For certain cost functions, this can be done analytically. For
instance, in [16] we provide an O(jpj) solution for cost functions
that correspond to delay uncertainty with uniform probability
distributions.
More generally, if the cost functions are strictly convex, then,
given \Delta   , one can use (1) to find an optimal solution in O(jpj).
In [16], a binary search is employed for finding \Delta   . Ac-
cordingly, the resulting overall solution is of O(jpj log \Delta
where pg. Note
that log \Delta max is bounded by the complexity of representing a
cost value.
IV. SOLUTION TO MULTICAST OPQ (MOPQ)
In this section we solve Problem OPQ for multicast trees.
Specifically, given a multicast tree, we need to allocate the delay
on each link, such that the end-to-end bound is satisfied on every
path from the source to any member of the multicast group, and
the cost associated with the whole multicast tree is minimized.
We denote the source (root) of the multicast by s and the set
of destinations, i.e., the multicast group, by M . A multicast tree
is a set of edges T ' E such that for all there exists a
path, p T (s; v), from s to v on links that belong to the tree T.
We assume there is only one outgoing link from the source s, 5
and denote this link by r.
all the outgoing links from v, i.e., all
of l's neighbors; when N(l) is an empty set then we call l a leaf.
T l is the whole sub-tree originating from l (including l itself).
The branches of T are denoted by -
frg. Observe that
A feasible delay partition for a multicast tree T, is
a set of link-requirements xT l2T such that
We can now define Problem OPQ for multicast trees.
Problem MOPQ (Multicast OPQ): Given a multicast tree T
and an end-to-end delay requirement D, find a feasible partition
x
(D) , such that c (x
(D)), for every (other)
feasible partition xT (D).
Remark 1: If there is more than one outgoing link from the
source, then we can simply solve Problem MOPQ indepen-
dently, for each tree T r i
corresponding to an outgoing link r i
5 See Remark 1.
6 Again, when no ambiguity exists, we omit the sub-script T and/or the argument
D.
from s. Thus, our assumption, that there is only one outgoing
link from r, does not limit the solution.
We denote by MOPQ(T; d) the set of optimal partitions on
a tree T with delay D. c T (d) denotes the tree cost function,
i.e., the cost of (optimally) allocating a delay d on the tree T. In
other words, c T
A. Greedy Properties
The general resource allocation problem can be stated with
tree-structured constraints and solved in a greedy fashion [12].
An efficient O(jTj log jTj log D) algorithm is given in [11].
However, that "tree version" of the resource allocation problem
has a different structure than Problem MOPQ. Indeed, the
simple greedy approach, namely repeated augmentation of the
link that most improves the overall cost, fails in our framework.
However, as we show below, some greedy structure is main-
tained, as follows: if at each iteration we augment the sub-tree
that most improves the overall cost, then an optimal solution is
achieved.
The main difference of our framework is that the constraints
are not on sub-trees, but rather on paths. The greedy approach
fails because of the dependencies among paths. On the other
hand, we note that the tree version of the resource allocation
problem may be applicable to other multicast resource allocation
problems, in which the constraints are also on sub-trees.
For example, suppose a feasible allocation must recursively sat-
isfy, for any sub-tree T e ,
some arbitrary (sub-tree) constraint.
We proceed to establish the greedy structure of Problem
MOPQ. First, we show that if all link cost functions are
convex, then so is the tree cost function.
Lemma 4: If fc l g l2T
are convex then so is c T (d).
By Lemma 4, we can replace T by an equivalent convex link.
Any sub-tree T l , can also be replaced with an equivalent convex
link, hence so can -
T. However, these results apply only if
the allocation on every sub-tree is optimal for the sub-tree. This
property is sometimes referred to as the "optimal sub-structure"
property [1], and is the hallmark of the applicability of both
dynamic-programming and greedy methods.
Lemma 5: Let x
let the sub-partition x e
(D e
l g l2Te
, where D
r . Then x e
Lemma 5 implies that, for any optimally partitioned trees, we
can apply the greedy properties of Section III. That is, the partition
on r and -
T is a solution to Problem OPQ on the 2-link path
T). This suggests that employing greedy moves between r
and -
T will solve Problem MOPQ, and this method can be applied
recursively for the sub-trees of T. Indeed, this scheme is
used by the algorithms presented in the next sections.
B. Pseudo-polynomial Solution
We employ greedy moves between r and -
T. The major
difficulty of this method is the fact that c -
T (d) is unavailable.
Computing c - T (d) for a specific d requires some x
MOPQ(T; d). Fortunately, we can easily compute c - T (d
given x
(d). Since the greedy approach is applicable, we may
simply perform a greedy augmentation and recompute the cost.
Note that adding ffi to -
adding ffi to all fT l g l2N(r)
. In
the worst case, this must be done recursively for all the sub-trees
and O(jTj) links are augmented.
Procedure TREE-ADD (Figure performs a ffi-augmentation
on a tree T. We assume that for each sub-tree T l the value of
(D T l ; ffi) for the current allocation is stored in the variable
(ffi). At Line 1 it is decided if r or -
T would be augmented.
(D T l ) or \Delta r
can be made by a simple comparison. If -
T should be augmented
then Procedure TREE-ADD is called recursively on its compo-
nents. Finally, \Delta T (\Sigmaffi) is updated at Lines 6-7.
3 else
4 for each l 2 N(r) do
(ffi)g a
a If r is a leaf we define the sum to be 1.
Fig. 4. Procedure TREE-ADD
Algorithm BALANCE (Figure 5) is a dynamic algorithm that
solves Problem MOPQ. It starts from any feasible tree partition
and performs greedy moves between r and -
T. The while loop
at Line 7 computes \Delta r! -
T (x; ffi). If it is negative then moving
from r to -
T reduces the overall cost. The augmentation of -
is done by calling TREE-ADD on each of its components. The
while loop at at Line 11 performs moves from -
T to r in a similar
way.
To be able to check the while condition and for calling TREE-
ADD, we must have
(\Sigmaffi) for all l 2 T. This requires
an optimal partition on each sub-tree. Algorithm BALANCE
makes sure that this is indeed the case by recursively calling
itself (Line 5 ) on the components of -
T. Since any allocation to
a leaf is an optimal partition on it, the recursion is stopped once
we reach a leaf. After the tree is balanced the algorithm updates
which is used by the calling iteration.
if T is a leaf then
4 return
5 (else) for each l 2 N(r) do
7 while
9 for each l 2 N(r) do
13 for each l 2 N(r) do
Fig. 5. Algorithm BALANCE
We proceed to analyze the complexity of BALANCE. We first
define a distance 'T (x) which is the tree version of the path
distance defined in Section III-B. Let ' r (xT
where x
is the optimal partition nearest to T. Let x l
x l
e
e2T l
. We define '(xT
Theorem 3: Algorithm BALANCE finds a ffi-optimal solution
to Problem MOPQ in O(jTj('(x)=ffi)
Proof: '(x)=ffi bounds the number of calls to Procedure
TREE-ADD. At the worst case, TREE-ADD requires
O(jTj) for each call. The recursive calls to BALANCE also require
O(jTj).
Remark 2: We can apply Algorithm BALANCE on the feasible
partition rg. Clearly,
'(x) - D in this case. Thus, Problem MOPQ can be solved in
O(jTjD=ffi).
C. Distributed and Dynamic Implementation
Algorithm BALANCE can be readily applied in a distributed
fashion. Each augmentation in Procedure TREE-ADD is propagated
from the root to the leafs. A straightforward implementation
requires O(t) time, 7 where t is the depth of the tree.
At most O(t) recursive calls to BALANCE are performed se-
quentially. Finally, the number of calls to TREE-ADD after
the sub-trees are balanced, is bounded by ' max
r (x)=ffi, where
). The overall complexity is, there-
fore, O
r (x)=ffi
. Note that for balanced trees
O(log jTj).
Algorithm BALANCE (as is the case for Algorithm GREEDY-
MOVE) can be used as a dynamic scheme that reacts to changes
in the cost functions after an optimal partition is established.
The complexity of Algorithm BALANCE is proportional to the
distance from the new optimal allocation. Again, small changes
(i.e., small '(x)) incur a small number of computations.
D. Polynomial Solution
We can now present a polynomial solution. Algorithm
BINARY-MOPQ uses an approach that is identical to the
one used for the solution of Problem OPQ. The algorithm consecutively
calls BALANCE for smaller values of ffi, until the minimal
possible value is reached, at which point an optimal partition
is identified.
4 repeat
Fig. 6. Algorithm BINARY-MOPQ
We will show that, at each iteration of the algorithm, ' max
r (x)
is bounded by tffi. Therefore, '(x)=ffi - tjTj and the over-all
complexity of this algorithm is O(jTj 2 t log(D=jTj)). The
Lemma 6 is the equivalent of Lemma 2 for multicast.
Lemma t.
7 assuming that traveling a link requires one time unit.
denote the value of \Delta T (ffi) at the termination of
T). Note that \Delta T (d; ffi) assumes a ffi-optimal
partition on the tree, hence it is different from (c T (d
which assumes the optimal partition.
Theorem 4 states the complexity of Algorithm BINARY-
MOPQ.
Theorem 4: Algorithm BINARY-MOPQ finds a solution to
Problem MOPQ in O(jTj 2 t log(D=jTj)).
Comparing this result to the O(jTjD=ffi) complexity of
Algorithm BALANCE (see Remark 2), indicates that Algorithm
BALANCE is preferable when D=ffi ! jTjt log(D=jTj).
Again, note that, for balanced trees
we can implement Algorithm BINARY-MOPQ in a distributed
fashion (as in Section IV-C), with an overall complexity of
O(t 3 log(D=jTj).
Remark 3: Algorithm BINARY-MOPQ starts from a coarse
partition and improves the result by refining the partition at each
iteration; this means that one may halt the computation once the
result is good enough, albeit not optimal.
Remark 4: It is possible to modify the algorithm to cope
with heterogeneity in the QoS requirements of the multicast
group members. In the worst case, the complexity of the solution
grows by a factor of O (jM j), while the complexity of the
pseudo-polynomial solution remains unchanged. The details of
this extension are omitted here.
V. ROUTING ISSUES
In the previous sections, we addressed and solved optimal
QoS partition problems for given topologies. These solutions
have an obvious impact on the route selection process, as the
quality of a route is determined by the cost of the eventual (opti-
mal) QoS partition over it. Hence, the unicast partition problem
OPQ induces a unicast routing problem, OPQ-R, which seeks a
path on which the cost of the solution to Problem OPQ is min-
imal. Similarly, Problem MOPQ induces a multicast routing
problem MOPQ-R. In this section we briefly discuss some current
and future work in the context of these routing problems.
A. OPQ-R
As was the case with Problem OPQ, with OPQ-R too there
is a significant difference between bottleneck QoS requirements
and additive ones. As explained in Section II, for a bottleneck
QoS requirement, the end-to-end requirement determines Q
Q for all links in the path (or tree), and a corresponding link
cost, c l (Q). Therefore, the routing problem OPQ-R boils down
to a "standard" shortest-path problem with link length c l (Q).
As noted, in the context of Problem OPQ, providing delay requirements
through rate-based schedulers [7], [22], [25], [26],
translates the additive requirement into a (simpler) bottleneck
requirement. However, in the context of Problem OPQ-R, such
a translation is not possible anymore, since paths differ also in
terms of constant (rate-independent) link delay components. Efficient
solutions for Problem OPQ-R, under delay requirements
and rate-based schedulers, have been presented in [9].
The general OPQ-R problem, under additive QoS require-
ments, is much more complex, and has been found to be intractable
[16]. Note that, even in a simpler, constant-cost frame-
work, where each link is characterized by a delay-cost pair
(rather than a complete delay-cost function), routing is an intractable
problem [6]. In the latter case, optimal routing can be
achieved through a pseudo-polynomial dynamic-programming
scheme, while ffl-optimal solutions can be achieved in polynomial
time [10].
The general OPQ-R problem, under the framework of the
present study, was solved in [16]. The solution is based on
dynamic-programming and assumes that the link cost functions
are convex. An exact pseudo-polynomial solution, as well as an
ffl-optimal polynomial solution, have been presented. We note
that a single execution of those algorithms finds a unicast route
from the source to every destination and for every end-to-end
delay requirement.
B. MOPQ-R
As could be expected, finding optimal multicast trees under
our framework is much more difficult than finding unicast paths.
Even with bottleneck QoS requirements, MOPQ-R boils down
to finding a Steiner tree, which is known to be an intractable
problem [6].
We are currently working on solving MOPQ-R for additive
QoS requirements. We established an efficient scheme for the
fundamental problem of adding a new member to an existing
multicast tree. This provides a useful building block for constructing
multicast trees. Another important building block is
the optimal sub-structure property (established in Section IV),
which is an essential requirement for the application of greedy
and dynamic programming solution approaches.
Interestingly, the above problem, of adding members to multicast
trees, may serve to illustrate the power of our framework
over the simpler, constant-cost framework. In the latter, there
is a single delay-cost pair for each link (rather than a complete
delay-cost function), and the goal is to find a minimal cost tree
that satisfies an end-to-end delay constraint. 8 Under that frame-
work, it is often impossible to connect a new member to the
"tree top", i.e., the leaves and their neighborhood. This is a consequence
of cost minimization considerations, which usually result
with the consumption of all (or most of) the available delay
at the leaves. For example, consider the network of Figure 7.
The source is S and the multicast group is fA; Bg; the end-to-
end delay bound is 10 and the link delay-cost pairs are specified.
Suppose we start with a tree for node A, i.e., the link (S; A).
Since A exhausts all the available end-to-end delay, we cannot
add B to the tree by extending A's branch with the (cheap) link
rather, we have to use the (expensive) link (S; B). Note
that we would get the same result even if there were an additional
link from S to A with shorter delay, say 9, and slightly
higher cost, say 11.
Our framework allows a better solution, as it lets the link
several delays and costs. For instance, it could
advertise a delay of 10 with a cost of 10 and a delay of 9 with a
cost of 11. When adding B to the tree, we can change the delay
allocation on (S; to 9 (thus paying 11 instead of 10),
which allows us to use the link (A; B) for adding B. The cost
of the resulting tree is 12, as opposed to 20 in the previous solution
(i.e., using link (S; B)). Note that, when adding B, one can
8 That framework was the subject of numerous studies on constrained multi-cast
trees.
'j 'i `j 'i
'j 'i
Fig. 7. Example: extending a multicast tree
consider the "residual" cost for each link, i.e., the cost of tightening
the delay bound on existing allocations. In our example,
the residual cost function of link (S; A) is 0 for a delay of 10
(i.e., the current allocation) and 1 for a delay of 9 (i.e., the added
cost for tightening the requirement). The last observation implies
that adding a new member to an existing tree boils down to
finding an optimal unicast path, with respect to the residual cost
functions, from the new member to the source; i.e., an instance
of Problem OPQ-R, for which efficient solutions have been established
in [16].
VI. CONCLUSIONS
We investigated a framework for allocating QoS resources on
unicast paths and multicast trees, which is based on partitioning
QoS requirements among the network components. The quality
of a partition is quantified by link cost functions, which increase
with the severity of the QoS requirement. We indicated that this
framework is consistent with the major proposals for provisioning
QoS on networks. Indeed, the problem of how to efficiently
partition QoS requirements among path or tree links has been
considered in previous studies, however till now only heuristic
approaches have been addressed. The present study is the first
to provide a general optimal solution, both for unicast paths and
multicast trees.
We demonstrated how the various classes of QoS requirements
can be accommodated in within our framework. We
showed that the partitioning problems are simple when dealing
with bottleneck requirements, such as bandwidth, however they
become intractable for additive (or multiplicative) requirements,
such as delay, jitter and loss rate. Yet we established that, by
introducing a mild assumption of weak convexity on the cost
efficient solutions can be derived.
We note that weak convexity essentially means that, as the
QoS requirement weakens, the rate of decrease of the cost function
diminishes. This is a reasonable property, as cost functions
are lower-bounded, e.g. by zero. Moreover, it indeed makes
sense for a cost function to strongly discourage severe QoS
requirements, yet gradually become indifferent to weak (and,
eventually, practically null) requirements. Hence, the scope of
our solutions is broad and general.
Specifically, we presented several greedy algorithms for
the unicast problem (OPQ). Algorithm GREEDY-MOVE, is
a pseudo-polynomial solution, which can be implemented in
a distributed fashion. The complexity of this solution is
O('(x) log jpj), where '(x) - D is the distance between the
initial allocation, x, and the optimal one. It can also be applied
as a dynamic scheme to modify an existing allocation.
This is useful in dynamic environments where the cost of resources
changes from time to time. Note that the complexity is
proportional to '(x), meaning that small cost changes require
a small number of computations to regain optimality. Algorithm
BINARY-OPQ is a polynomial solution from which we
later build our solution to the multicast problem (MOPQ). The
complexity of this solution is O (jpj log jpj log(D=jpj)).
Next, we addressed the multicast problem MOPQ. We began
by showing that the fundamental properties of convexity
and optimal sub-structure generalize to multicast trees. Then,
we established that Problem MOPQ also bears a greedy struc-
ture, although much more complex than its OPQ counterpart.
Again, the greedy structure, together with the other established
properties, provided the foundations for an efficient solu-
tions. Algorithm BALANCE is a pseudo-polynomial algorithm
which can be applied as a dynamic scheme. Its complexity
again, the distance between
the initial allocation and the optimal one. A distributed
implementation requires O(t 2 ' max
r (x)), where t is the depth
of the tree and ' max
r (x) is the maximal distance of any link's
allocation from it optimal one. Note that for balanced trees
Algorithm BINARY-MOPQ is a polynomial solution
with a complexity of O(jTj 2 t log(D=jTj)). A distributed
implementation of this algorithm requires O(t 3 log(D=jTj). We
note that our solutions are applicable to heterogeneous multicast
members, each with a different delay requirement.
Lastly, we discussed the related routing problems, OPQ-R
and MOPQ-R. Here, the goal is to select either a unicast path
or multicast tree, so that, after the QoS requirements are optimally
partitioned over it, the resulting cost would be minimized.
Again, unicast proves to be much easier than multicast. In par-
ticular, for bottleneck QoS requirements, OPQ-R boils down to a
simple shortest-path problem. For additive requirements, OPQ-
R is intractable, yet an efficient, ffl-optimal solution has been
established in [16]. For multicast, all the various versions of
MOPQ-R are intractable. We are currently investigating Problem
MOPQ-R under additive requirements, and have obtained
an efficient scheme for adding new members to a multicast tree.
Several important issues are left for future work. One is
multicast routing, i.e., Problem MOPQ-R, for which just initial
(yet encouraging) results have been obtained thus far. Another
important aspect is the actual implementation of our solutions
in within practical network architectures. In this respect, it
is important to note that a compromise with optimality might
be called for. Indeed, while our solutions are of reasonable
complexity, a sub-optimal solution that runs substantially faster
might be preferable in practice. Relatedly, one should consider
the impact of the chosen solution for QoS partitioning on the
routing process. The latter has to consider the quality of a selection
(i.e., path or tree) in terms of the eventual QoS parti-
tion. This means that simpler partitions should result in simpler
routing decisions, which provides further motivation for compromising
optimality for the sake of simplicity. The optimal
solutions established in this study provide the required starting
point in the search of such compromises.
Lastly, we believe that the framework investigated in this
study, where QoS provisioning at network elements is characterized
through cost functions, provides a powerful paradigm for
dealing with QoS networking. We illustrated the potential benefits
through an example of dynamic tree maintenance. Further
study should consider the implications and potential advantages
of our framework, when applied to the various problems and
facets of QoS networking.



--R

Introduction to Algo- rithms
A framework for QoS-based routing in the internet - RFC no

Call admission and resource reservation for multicast sessions.
The complexity of selection and ranking in X
Computers and Intractability.
Efficient network QoS provisioning based on per node traffic shaping.
QoS routing mechanisms and OSPF extensions.

Approximation schemes for the restricted shortest path prob- lem
Lower and upper bounds for the alloction problem and other nonlinear optimization problems.
Resource Allocation Problems.
Multicast routing for multimedia communication.

Optimal partition of QoS requirements on unicast paths and multicast trees.
QoS routing in networks with uncertain pa- rameters
A new approach to service provisioning in ATM networks.
Pricing Congestable Network Re- sources
Allocation of local quality of service constraints to meet end-to-end requirements
Incentive pricing in multi-class communication networks
Private network-network interface specification v1
A generalized processor sharing approach to flow control in integrated services networks: the multiple node case.
Specification of guaranteed quality of service - RFC no

Service disciplines for guaranteed performance service in packet-switching networks

--TR
Introduction to algorithms
Approximation schemes for the restricted shortest path problem
Multicast routing for multimedia communication
A new approach to service provisioning in ATM networks
Lower and upper bounds for the allocation problem and other nonlinear optimization problems
A generalized processor sharing approach to flow control in integrated services networks
Efficient network QoS provisioning based on per node traffic shaping
QoS routing in networks with uncertain parameters
QoS routing in networks with inaccurate information

--CTR
Ariel Orda , Alexander Sprintson, A scalable approach to the partition of QoS requirements in unicast and multicast, IEEE/ACM Transactions on Networking (TON), v.13 n.5, p.1146-1159, October 2005
Wen-Lin Yang, Optimal and heuristic algorithms for quality-of-service routing with multiple constraints, Performance Evaluation, v.57 n.3, p.261-278, July 2004
Wen-Lin Yang, A comparison of two optimal approaches for the MCOP problem, Journal of Network and Computer Applications, v.27 n.3, p.151-162, August 2004
Sun-Jin Kim , Mun-Kee Choi, Evolutionary algorithms for route selection and rate allocation in multirate multicast networks, Applied Intelligence, v.26 n.3, p.197-215, June      2007
Ariel Orda , Alexander Sprintson, Precomputation schemes for QoS routing, IEEE/ACM Transactions on Networking (TON), v.11 n.4, p.578-591, August
Bin Xiao , Jiannong Cao , Zili Shao , Qingfeng Zhuge , Edwin H. -M. Sha, Analysis and algorithms design for the partition of large-scale adaptive mobile wireless networks, Computer Communications, v.30 n.8, p.1899-1912, June, 2007
routing;broadband networks;convex costs;QoS partitioning;QoS-dependent costs;multicast;unicast