当前位置:首页 >> >>

Optimal partition of QoS requirements for many-to-many connections


Optimal Partition of QoS Requirements for Many-to-Many Connections
Dean H. Lorenz?
Distributed Computer Systems IBM Haifa Research Labs Haifa, Israel Email: dean@il.ibm.com

Ariel Orda
Department of Electrical Engineering Technion – Israel Institute of Technology Haifa, Israel Email: ariel@ee.technion.ac.il

Danny Raz
Department of Computer Science Technion – Israel Institute of Technology Haifa, Israel Email: danny@cs.technion.ac.il

Abstract— We study problems related to supporting multicast connections with Quality of Service (QoS) requirements. We investigate the problem of optimal resource allocation in the context of performance dependent costs. In this context each network element can offer several QoS guarantees, each associated with a different cost. This is a natural extension to the commonly used bi-criteria model, where each link is associated with a single delay and a single cost. This framework is simple yet strong enough to model many practical interesting networking problems. The fundamental multicast resource allocation problem under this framework is how to optimally allocate QoS requirements on the links of the multicast tree. One needs to partition the end-toend QoS requirement along the various paths in a tree. The goal is to satisfy the end-to-end QoS requirement with minimum cost. Previous studies under this framework considered single-source multicast connections, where the End-to-end QoS requirement is speci?ed from the source to all other multicast group members. In this paper we extend these results to the more general, and considerably harder case of multicast sessions, where the end-toend requirement hold for every path between any two multicast group members. Our aim is to provide rigorous solutions, with proven performance guaranties, by way of algorithmic analysis. The problem under investigation is NP hard for general cost functions, thus we ?rst present a pseudo-polynomial exact solution. From this solution we derive two ef?cient -approximate solutions. One achieves optimal cost, but may violate the endto-end delay requirement by a factor of (1 + ), and the other strictly obeys the bounds and achieves a cost within a factor of (1+ ) of the optimum. Furthermore, we present improved results for discrete cost functions, and give a simple linear-time exact polynomial solution for a speci?c, and practically interesting, family of convex cost functions.

I. I NTRODUCTION Consider a conference call that uses IP telephony. Such an application requires a delay bound of say 120msec in order to be at an acceptable quality level. Assume further that the participants in the meeting are located at different locations and the links among them can travel through different administrative domains. One could construct different trees connecting the participants in the conference call, each resulting in different QoS (delay) guaranteed by the different providers according to the different SLAs we have with each one of them. Even if the tree is ?xed (i.e., we cannot create the multicast tree), we could still decide to partition the
? Part of this work done while Dean Lorenz was with the Department of Electrical Engineering, Technion – Israel Institute of Technology, Haifa, Israel.

delay “budget” in various ways among the different providers. Among all such partitions that guarantee the required QoS, we would seek to use the one that is most cost-effective. This problem is precisely the many-to-many QoS partition problem on trees, which is the subject of this study. In this problem, we are given a set of end-points connected through a ?xed given tree. Each link in this tree is associated with a cost-delay function that indicates the cost per delay guarantee on the link. We are also given a global bound on the delay between any two participants. The objective is to ?nd the least expensive partition of the delay along the different links in the tree in a way that the delay between any two end-points (along the unique path in the tree) will be bounded by the global bound. The tele-conferencing example described above is an instance of this partition problem, where each link corresponds to a provider’s network. Each link is associated with several working points each representing a possible guaranteed delay and its cost. Fig. 1 shows how this problem can be modeled for a very simple example. In this example each network element offers three levels of service: Gold, which costs $3 and guarantees a delay of 20msec; Silver, which costs $2 and guarantees 40msec; and Bronze which costs only $1, but guarantees 50msec. There are different possibilities for ensuring a many-to-many bound of no more than 120msec and the problem is to ?nd the least costly choice. One can consider different examples in which each link is associated with a general resource-cost function. The cost may represent the consumption of local resources (such as buffer or bandwidth reservations) that must be reserved on every link of the route to support the QoS guarantee. The cost may also represent the decrease in overall network performance resulting from establishing the selected connection. For instance, there may be loss of revenue due to blocked future calls or there may be management costs. If we assume some of the suggested pricing schemes for QoS provision, the cost may represent a real price that the user has to pay in order to use the link. All these examples indicate that the performance-dependent model is of practical importance, and any ef?cient solutions established within its framework may become essential for future network planning and control. This is particularly true as applications like

0-7803-7753-2/03/$17.00 (C) 2003 IEEE

IEEE INFOCOM 2003

Level Cost Gold $3 Silver $2 Bronze $1 E2E demand:

Delay 20msec 40msec 50msec 120msec

? ?? ?
D E {Gold, Silver, Bronze}

? ?? ?
D {Bronze} E {Silver}

? ?? ?
D {Silver} E {Silver}

? ?? ? ??  ?c2 (d) ? ? ?  B C ?? ??
c3 (d) D c4 (d) E

{Gold, Silver, Bronze}

?? Silver, {Gold, Bronze}  ? ? ? ?  B C ?? ?? ? ??
A {Gold, Silver, Bronze}

??  ?{Bronze} ? ? ?  B C ?? ?? ? ??
A {Gold}

??  ?{Silver} ? ? ?  B C ?? ?? ? ??
A {Silver}

? ??
A

c1 (d)

(a)

(b)

(c)

(d)

Fig. 1.

Example: The many-to-many partition problem

The multicast tree (a) offers three levels of service on each link: {Gold, Silver, Bronze} associated with delays {20msec, 40msec, 50msec} and costs {$3, $2, $1}. The desired end-to-end delay bound is 120msec. The allocations (b), (c) demonstrate that, even in this simple case of identical links, there are several possible ways to split the delay between the links. The end-to-end delay between any two nodes in the tree must satisfy the connection requirements of 120msec. Option (b), which induces an overall cost of $7 is better than option (c), which costs $8. In the general case (d), there is an arbitrary cost function on each link, which maps delay guarantees to cost.

video conferencing and video streaming over wireless are expected to become popular, and as different providers are deploying various pricing schemes in order to create revenue from the new services offered. Accordingly, this study investigates the problem of many-to-many multicast sessions within the performance-dependent model, and employs algorithmic analysis in order to provide rigorous solutions, with proven performance guaranties. Similar problems, generally referred to as QoS routing and partitioning, were considered recently, both for unicast and for multicast [1]–[3]. However, in the context of multicast they all dealt with the restricted case of one-to-many connections, where the QoS requirement is just between the common root to the other members. Since we deal with many-tomany connections, the bound on the delay should be valid for any pair of end users and not only from the root to the end users. This requirement makes the problem different, and inherently more dif?cult. Since the tree no longer has a clear root, building a dynamic solution based on the tree structure becomes more complex. In general, the partition problem is intractable. The special case where the link cost functions (i.e., the functions that describe the cost of allocating a QoS parameter on a link) are continuous and convex was addressed recently by several works. Multicast trees for the strongly convex case were dealt in [4]. In [5], polynomial algorithms both for trees and paths for weakly convex cost functions were presented, and the QoS routing problem was also addressed. The discrete cost function case was addressed in [6], and approximation algorithms were considered in [1], [2], [7]. The speci?c aspect of resource allocation in this context has also been extensively studied; in particular, a similar framework was studied by [3]–[5], [8], [9]. The reader is also referred to [10] for a survey on QoS multicast routing algorithms, though from a slightly different perspective. In this paper we provide exact and approximated solutions for various cases. We ?rst present a pseudo polynomial solu-

tion that uses dynamic programming to ?nd the best partition of the tree. We then describe a set of steps that allow us to use this algorithm in order to derive a polynomial approximation algorithm for the problem. We note that, while the techniques used for these results are similar to the one used in [2], [5], the problem in our case is signi?cantly more complex and thus the actual algorithms (and their proofs) are much more complex. We then deal with speci?c cost-delay function which are of practical importance. These include discrete cost functions (which re?ect the current DiffServe architecture [11]), and a speci?c case of a convex cost function that is often used in this context. For the latter, we present a remarkably ef?cient linear algorithm that ?nds the best partition of the delay along a given tree. The rest of the paper is organized as follows. In the next section we give the basic notions and preliminary observations. Then, in Section III, we present the basic pseudo polynomial algorithm. In section IV we describe the approximation algorithms, and in Section V we present particularly ef?cient algorithms for some cost-delay functions of special interest. We conclude with a brief discussion. II. P RELIMINARIES A. Terminology The network is represented as an undirected graph G(V, E). We are given a multicast group M ? V and a multicast tree T ? E, such that for all u, v ∈ M , there exists a unique path, pu?v from u to v, on links that belong to T . We use T to denote both the links and the nodes of a tree, and denote by n = |T | its size (number of links). N (u) denotes all the outgoing links from u, namely N (u) ≡ {(u, v) ∈ T }. If the degree of node u is one, i.e., N (u) consists of a single link (u, v), then we use the term leaf for both u and (u, v). We assume that T is a binary tree, namely |N (u)| ≤ 3 for all u ∈ T . This assumption greatly simpli?es the presentation

0-7803-7753-2/03/$17.00 (C) 2003 IEEE

IEEE INFOCOM 2003

without loss of generality.1 We denote by T uv the sub-tree rooted at u, for which (u, v) is the ?rst (root) link. For example, for any node u ∈ T we have T = ∪v∈N (u) T uv . Although links are undirected, note that T uv = T vu , since these denote different sub-trees on the two sides of the link. Also, note that T uv ∪ T vu = T , and T uv ∩ T vu = {(u, v)}. We use Luv , Ruv respectively to denote the “left” and “right” child of node v on T uv , and the corresponding sub-trees are denoted by T Luv and T Ruv . We call the union of both sub-trees the branches of T uv and use T Buv ≡ T Luv ∪ T Ruv ≡ T uv \ {(u, v)}. Each link l ∈ E offers different delays with different costs. The cost associated with a link is a function cl (dl ) of the delay allocated to it. Each link cost function cl (dl ) is nonincreasing with the delay and both the delays and associated costs are assumed to be integers.2 A delay partition on a tree T speci?es the delay allocated on each link, i.e., is a set of link delays d ≡ {dl }l∈T . The cost of a partition d on a tree T is de?ned as the sum of all link costs, namely cost(T , d) ≡ l∈T cl (dl ). A given partition determines the end-to-end delay of any path p ? T . Since delay QoS requirements are additive, the end-to-end delay of a path is the sum of the delays allocated on its links, i.e., delay(p, d) ≡ l∈p dl . We de?ne two end-to-end delay metrics for the whole tree which we term depth and width. The depth of a tree is the maximal end-to-end delay of any path from its root, and the width of a tree is the maximum delay between any two of its nodes. More formally, the depth and width of a tree T uv are de?ned as depth(T uv , d) ≡ maxw∈T uv delay(pu?w , d), and width(T uv , d) ≡ maxx,y∈T uv delay px?y , d . We say that a partition d is D-deep on T uv if depth(T uv , d) ≤ D, namely delay(pu?w , d) ≤ D for all w ∈ T uv . Similarly, we say that a partition d is D-wide on T if width(T , d) ≤ D, namely delay px?y , d ≤ D for all x, y ∈ T uv . We use the shorthand Duv (d) ≡ depth(T uv , d) and may omit the argument d when it is clear from context. B. Problems De?nition We can now de?ne the problems of interest, namely Problem WPQ and Problem DPQ for multicast trees. Problem DPQ (Depth optimal Partition of QoS): Given a multicast tree T uv and an end-to-end delay requirement D from u to all other m ∈ M , ?nd a D-deep partition d? , such that cost(d? ) ≤ cost(d), for every (other) D-deep partition d on T uv . Problem WPQ (Width optimal Partition of QoS): Given a multicast tree T and an end-to-end delay requirement D between any two members in M , ?nd a D-wide partition d? , such that cost(d? ) ≤ cost(d), for every (other) D-wide partition d on T .
1 If the degree at any node is greater than 3 we can add “dummy” links to split the node. Overall, at worst, this doubles the number of links. 2 This is true for any real-life network since neither link reservations nor payments can be made with arbitrary precision.

Note Both problems are NP-hard. In [12] it is shown that Problem DPQ is NP-hard even for a simple path topology. Since for a path both problems are equivalent, Problem WPQ is also intractable. III. S OLUTION TO P ROBLEM WPQ A. Foundations In this section we show that any optimal partition on a tree is made of optimal partitions on sub-trees. This tree decomposition allows for the dynamic programming solution, which we present in the next section. The observation made in the following lemmas are quite intuitive, however their proofs require careful formulation. It is possible to skip directly to Section III-B, which is self-contained. We start with Lemma 1, which states that all sub-trees of a D-wide tree are also D-wide. Lemma 1: Let d be a D-wide partition on T and let T be any sub-tree of T . Then, d is a D-wide partition on T . Proof: Since d is D-wide, delay px?y ≤ D for all x, y ∈ T implying delay px?y ≤ D for all x, y ∈ T ? T . Hence, d is D-wide partition on T . Note that, although all sub-tree have width not greater than D, Lemma 1 does not imply that it is exactly D. In fact, their actual width may be much smaller than D. Also, note that a partition is D-wide iff it is D-deep on every T uv ? T . Lemma 2: Let d be a D-wide partition on T , let T uv be any sub-tree of T , and let w ∈ T \ T uv be a node outside the sub-tree. Then, Duv + delay(pu?w ) ≤ D. Proof: Let y be a Duv -deep node in T uv , namely delay py?u = Duv (such a node must exist in T uv by the de?nition of the sub-tree depth, Duv ). Since w is outside T uv , py?w = py?u + pu?w .3 Combining with the fact that this is a D-wide partition, we get Duv + delay(pu?w ) = delay py?u + delay(pu?w ) = delay py?w ≤ D, as claimed. Lemma 3 provides the relation between the depths of adjacent sub-trees. Lemma 3: Let d be a D-wide partition on T uv . Then DLuv + DRuv ≤ D. Proof: By Lemma 1, d is a D-wide partition on T Buv . We can apply Lemma 2 on T Luv as a sub-tree of T Buv , therefore DLuv +delay(pv?w ) ≤ D for all w ∈ T Ruv . Hence, DLuv + max delay(pv?w ) = DLuv + DRuv ≤ D.
w∈T Ruv

We will use Lemma 3 as a feasibility test when searching for an optimal partition. Also, note that the lemma can be applied in any “direction” and by symmetry we have DLuv +Dvu ≤ D and DRuv + Dvu ≤ D.
3 Here

’+’ is a path concatenation operator.

0-7803-7753-2/03/$17.00 (C) 2003 IEEE

IEEE INFOCOM 2003

We proceed to show that an optimal partition is also optimal on sub-trees. But ?rst, we need Lemma 4 that allows us to build a new partition by replacing part of an old one. Lemma 4: Let d1 be a D-wide partition on T , let T uv be 1 any sub-tree of T and let d2 be both a D-wide and Duv -deep uv partition on T . Then, the partition dl = d2 l d1 l l ∈ T uv l ∈ T Bvu

can replace it with an optimal one. The resulting overall Dwide partition would be cheaper than d? on T contradicting the optimality of d? on T . The same claims hold for any sub-branches as follows: Corollary 1: Let d? be an optimal D-wide partition on uv ? T . Then, d? is an optimal D-wide and DBuv -deep partition
? on T Buv , where DBuv ≡ depth T Buv . Proof: The proofs of Lemma 4 and Lemma 5 apply (with slight modi?cations) to this case too.

is a D-wide partition on T . Proof: T uv ∪ T B(v,u) = T and T uv ∩ T B(v,u) = ?, thus for any x, y ∈ T we have three cases: (1) x, y ∈ T uv : In this case, px?y ? T uv so delay px?y , d = delay px?y , d2 . Since d2 is a D-wide partition on T uv , we get delay px?y , d = delay px?y , d2 ≤ D. (2) x, y ∈ T uv : Here x, y ∈ T B(v,u) , so delay px?y , d = delay px?y , d1 . Similarly to the previous case, we have delay px?y , d = delay px?y , d1 ≤ D. (3) x ∈ T uv , y ∈ T uv : 1 Here px?u ? T uv and d2 is Duv -deep on T uv , 2 1 hence delay px?u , d ≤ Duv . Also, d1 is a D-wide partition on T , so by Lemma 2,
1 Duv + delay pu?y , d1 ≤ D

B. The algorithm The previous lemmas provide us with the building blocks of our algorithm. We solve Problem WPQ using dynamic programming, computing optimal partitions on sub-trees and combining them to an optimal partition on the whole tree. Algorithm WPQ (Fig. 2) ?nds the best D-wide partition for every possible depth. The work is done by Procedure F IND C OST-TAB which recursively computes the tables T , L, R, B corresponding to T uv , T Luv , T Ruv and T Buv , respectively. The tables are all of size D which hold an entry for every every depth 0 ≤ d ≤ D. The entry for d is the best cost achieved for a D-wide and d-deep allocation on the tree. Procedure F IND -C OST-TAB recursively merges tables of subtrees until it reaches the root of the tree.
1 T ←F IND -C OST-TAB(T uv , {cl (d)}l∈T uv , D) 2 if T (D) = ∞ return FAIL 3 (else) return T (D) and the corresponding partition. Procedure F IND -C OST-TAB (T uv , {cl (d)}l∈T uv , D): 1 L ←F IND -C OST-TAB(T Luv , {cl (d)}l∈T L , D) 2 R ←F IND -C OST-TAB(T Ruv , {cl (d)}l∈T R , D) 3 for d = 0 . . . D/2 4 B(d) ← L(d) + R(d) 5 for d = D/2 . . . D 6 B(d) ← min{(L(d) + R(D ? d)), (L(D ? d) + R(d))} 7 for d = 0 . . . D 8 T (d) ← min cuv (x) + B(d ? x) 9 return T
0≤x≤d

WPQ (T uv , {cl (d)}l∈T uv , D):

and therefore delay px?u , d2 + delay pu?y , d1 ≤ D. Since in this case px?y = px?u + pu?y we can write delay px?y , d = delay(px?u , d) + delay pu?y , d = delay px?u , d2 + delay pu?y , d1 .

Fig. 2.

Algorithm WPQ

Combining all, we get delay px?y , d ≤ D. In all three cases delay px?y , d ≤ D, thus d is a D-wide partition on T . We have shown that any D-wide partition is made of Dwide sub-partitions. This observation also applies to optimal partitions, as stated in Lemma 5. Lemma 5: Let d? be an optimal D-wide partition on T and let T uv be any sub-tree. Then d? is an optimal D-wide and ? Duv -deep partition on T uv . ? Proof: By de?nition, d? is a Duv -deep partition on T uv and by Lemma 1, it is D-wide. By Lemma 4, if we replace the ? sub-partition on T uv with any D-wide and Duv -deep partition on T uv then we would still get a D-wide partition on T . If d? ? is not an optimal D-wide and Duv partition on T uv then we

The computation of the table for T Buv (B) is based on Corollary 1 and Lemma 3. By Corollary 1, the optimal allocation on T Buv is made of optimal allocations on T Luv and T Ruv . By Lemma 3, the depth of those allocations must satisfy DLuv + DRuv ≤ D. The computation is divided into two separate regions. For all depths 0 ≤ d ≤ D/2 , the requirement DBuv = max{DLuv + DRuv } ≤ d is satis?ed, since DLuv + DRuv ≤ 2 D/2 ≤ D. Therefore, the cost of the optimal D-wide and d-deep partition on T Buv is found by simply summing the cost of d-deep partitions on T Luv and T Ruv . This is done at Line 4 of Procedure F IND -C OST-TAB by summing the corresponding entries from L and R. On the other hand, for all depths D/2 ≤ d ≤ D, if we allocate d on one sub-tree then we must allocate D ? d on the other in

0-7803-7753-2/03/$17.00 (C) 2003 IEEE

IEEE INFOCOM 2003

order to satisfy DLuv +DRuv ≤ D. Line 6 of Procedure F IND C OST-TAB chooses the least costly among these two options. The computation of the table for T uv (T ) is based on Corollary 1 and the fact that Duv = duv + DBuv . By Corollary 1, the optimal allocation on T uv is made of an optimal allocations on T Buv . In order to ?nd the best partition we must check all possible depth allocations between (u, v) and T Buv . This is done at Line 8 of Procedure F IND -C OSTTAB. Observe that, so long as Duv ≤ D, the resulting partition is D-wide. To see this, we ?rst note that the delay for all paths from u to any other node in T uv is less than Duv ≤ D. Second, any path between other nodes of T uv is entirely inside T Buv , therefore its delay is less than D because the partition on T Buv is D-wide. When the recursive call returns, all entries of T correspond to valid D-wide partitions. We must check the entry for a depth of D, which is the least restrictive, hence should have minimal cost. If any link requires a minimal delay allocation on it then we might have in?nite cost on it. If no partition satis?es the minimal delay requirement of all links then we would have overall in?nite cost and the algorithm returns FAIL. With each cost entry update of T at Line 8 of Procedure F IND -C OSTTAB, we can also record the allocation to (u, v) that achieved the minimum. Thus, if the algorithm is successful it can return both the optimal partition and its cost. Complexity Each iteration of Procedure F IND -C OST-TAB requires O(D2 ) operations. Each link is processed once, so the overall time complexity is O(nD2 ). Parallel implementation The algorithm can be implemented in a parallel fashion, computing L and R at the same time. Such an implementation would require O(hmax D2 ) time, where hmax is the depth of the recursion. Observe, that hmax is bounded by the maximal number of hops in any path, i.e., the width of the tree in terms of hops. For balanced trees, hmax is of order O(log n). Distributed implementation The algorithm can also be easily modi?ed to operate in a distributed fashion. Each subtree can compute is optimal partition and forward the result. Such a solution is obviously parallel and also has the advantage that the link cost functions do not have to be advertised. Note We must call Algorithm WPQ with T uv = T , however we can select any leaf (u, v) of the tree. IV. A PPROXIMATE S OLUTION Algorithm WPQ is a pseudo polynomial solution, which depends on the value of D. The latter could be arbitrarily large, depending on the precision in which delays are speci?ed. Hence, in this section we improve the complexity at the expense of ?nding an approximate solution. The techniques we use are similar to the ones used in [2] for the approximate solution to Problem DPQ. We therefore give only a brief description and omit the proofs. We consider two types of approximations: delay-approximation and cost-approximation. An -delay optimal solution is a partition which is (1 + )D-wide with cost no greater than

the cost of the optimal D-wide partition. An -cost optimal solution is a D-wide partition with cost no greater than a factor of (1 + ) from the cost of the optimal D-wide partition. A. Delay Approximation Delay approximation is useful when the application can tolerate a delay that slightly higher than the required end-toend delay. In general, as shown in [7], delay approximation is considerably simpler than cost approximation. The approximation is based on scaling and rounding. Rather than ?nding the optimal cost for every possible depth 0 ≤ d ≤ D, we consider only delays that correspond to integer factors of some scaling factor S. Algorithm D-WPQ (Fig. 3) is a Fully Polynomial Approximation Scheme (FPAS) which ?nds an -delay optimal solution to Problem WPQ using scaling. It is polynomial in n and 1/ . D-WPQ (T uv , {cl (d)}l∈T uv , D, ):
1 2 3 4 5 hmax ← width of T uv in hops S ← hD max for each l ∈ T de?ne cl (d) ≡ cl ( d ? S ) ? ? D ← hmax

? 6 return WPQ T uv , {?l (d)}l∈T uv , D c Fig. 3. Algorithm D-WPQ

A careful choice of S is required to ensure that the resulting solution is indeed -delay approximate and the complexity is low enough. It can be shown that the overall error due to this type of scaling is hmax S,4 since the delay error of any path is summed over all its links. Thus, S = hD ensures an -delay max optimal solution. Each D factor in the complexity expression for Algorithm WPQ is reduced to D/S = hmax / . This result is summarized by Theorem 1. Theorem 1: Algorithm D-WPQ ?nds an -delay optimal solution to Problem WPQ in O n( hmax )2

time. Note A distributed/parallel implementation requires O h3 / max time. B. Cost Approximation Often, the end-to-end requirement is strict and delay approximation cannot be used. One might be tempted to slightly strengthen the original delay requirement and then use delay approximation. However, while this indeed leads to a feasible solution,5 its cost might be arbitrarily higher than that of the optimal solution. In order to facilitate cost approximation, we must ?rst reverse the roles of cost and delay in Algorithm WPQ. Instead
4 Recall 5 So

2

that hmax denotes the width of the tree. long as there exist a solution which satis?es the stricter requirement.

0-7803-7753-2/03/$17.00 (C) 2003 IEEE

IEEE INFOCOM 2003

of storing tables that hold the best cost achieved for every delay, we will store tables that hold the best delay achieved for every cost. Then, the same scaling techniques that were use for delay-approximation can be applied. 1) Cost-based dynamic programming: Algorithm C-WPQ (Fig. 4) is a cost-based version of Algorithm WPQ. Each table holds, for every cost c, the minimal depth achievable with overall cost no greater than c and width no greater that D. The size of each table is U , which is an upper bound on the cost. We shall assume for now that U is known and differ ?nding U to Section IV-B.3. The algorithm returns FAIL(Line 1) if no feasible solution can be found with cost not greater than U . Otherwise, it searches the table T for the min-cost entry that achieves a feasible solution (Line 3). C-WPQ (T uv , {cl (d)}l∈T uv , D, U ):

link “delay”-function duv (c), which is the equivalent of cuv (d) used in Algorithm WPQ. We use the Z table to store duv (c) for all 0 ≤ c ≤ U (Line 9). Each entry represents the minimal delay that induces a cost no greater than c. Note that the cost cuv (d) is a monotonic non-increasing function of the delay, hence a binary search can be used to ?nd the minimum. Once duv (c) is computed, we proceed to ?ll T . The computation at Line 12 is similar to the one done for B, but here we are guaranteed a width no greater than D so long as the depth is no greater than D (see the discussion of Algorithm WPQ). Complexity If we employ a binary search at Line 9 of Procedure F IND -D EPTH -TAB then each entry can be computed in O(log D) steps and O(U log D) for the whole table. All other computations require O(U 2 ). Thus, O(U (log D + U )) time is required for each link and the overall time complexity is O (nU (log D + U )) . Note A distributed, parallel implementation would require O hp U (log D + U ) time. 2) Cost scaling: We can now apply the same scaling methods as for the delay-approximation in order to achieve an -cost approximation. Algorithm C-WPQ ?nds an -cost optimal solution, given a lower bound L and an upper bound U on the optimal cost. C-WPQ (T uv , {cl (d)}l∈T uv , D, L, U, ):
1 S← L n 2 for each l ∈ T 3 de?ne cl (d) ≡ cl (d)/S ? ? 4 U ← U/S ? ? 5 return C-WPQ T uv , {?l (d)}l∈T uv , D, U c Fig. 5. Algorithm C-WPQ

1 T ←F IND -D EPTH -TAB(T uv , {cl (d)}l∈T uv , D, U ) 2 if T (U ) > D return FAIL 3 (else) return min{c|T (c) ≤ D} and the corresponding partition. Procedure F IND -D EPTH -TAB (T uv , {cl (d)}l∈T uv , D, U ): 1 L ←F IND -D EPTH -TAB(T Luv , {cl (d)}l∈T L , D, U ) 2 R ←F IND -D EPTH -TAB(T Ruv , {cl (d)}l∈T R , D, U ) 3 for c = 0 . . . U 4 for x = 0 . . . c 5 Z(x) ← max{L(x), R(c ? x)} 6 if L(x) + R(c ? x) > D then 7 Z(x) ← ∞ 8 B(c) ← min Z(x) 9 for c = 0 . . . U 10 Z(x) ← min{d|cuv (d) ≤ c} 11 for c = 0 . . . U 12 T (c) ← min Z(x) + B(c ? x) 13 return T
0≤x≤c 0≤x≤c

Fig. 4.

Algorithm C-WPQ

Procedure F IND -D EPTH -TAB is similar to Procedure F IND C OST-TAB of Algorithm WPQ and recursively calls itself for each sub-tree. However, it computes “depth”-tables instead of “cost”-tables. Unlike delay, the cost can be arbitrarily divided between the sub-trees, therefore we must check all possible cost allocations. In order to compute a single entry B(c), we must check all possible cost divisions between T Luv and T Ruv , i.e., all pairs L(x), R(c ? x). This is done at Line 1 of Procedure C-WPQ and stored in a temporary table entry Z(x). Each entry in Z corresponds to the overall depth of the pair and is simply the maximal depth of the two. The overall depth of an allocation is the sum of the depths. If it is greater than D then the cost allocations is unfeasible, hence its entry is removed (at Line 3) by assigning an in?nite delay. After Z(x) is computed for all 0 ≤ x ≤ c, the minimal entry in Z is the best depth that can be achieved with cost c. The computation and the update to B(c) are done at Line 8. Procedure F IND -D EPTH -TAB computes all the entries of B and continues to ?nd the optimal partition between (u, v) and T Buv . As before, we need to check all possible divisions of cost between (u, v) and it branches. However, we need the

Theorem 2 is the equivalent of Theorem 1 for the -cost approximation. Again, a careful choice of S is required to ensure that the resulting solution is indeed an -cost approximate and the complexity is low enough. In this case, the overall error due to scaling is nS, since the cost error is summed over all links of the tree. Thus, S = L ensures an -delay optimal n solution. Here, each U factor in the complexity expression for Algorithm C-WPQ is reduced to U/S = O(nU/( L)). Theorem 2: Algorithm C-WPQ ?nds an -cost optimal solution to Problem WPQ in O n2 U L log D + nU L

time. 3) Finding good bounds: Algorithm C-WPQ and its complexity depend on good bounds on the optimal cost c? . If we chose U < c? then we might not be able to ?nd a feasible partition (in which case the algorithm would FAIL). If we choose U c? then U/L would be large and the complexity

0-7803-7753-2/03/$17.00 (C) 2003 IEEE

IEEE INFOCOM 2003

would be too high. The same applies for the choice of L: if L > c? then the scaling error might be too large, i.e., we cannot ensure an -cost optimal solution; if L c? then U/L (and the complexity) may grow up to the order of c? . The problem of ?nding tight bounds L, U that satisfy L ≤ c? ≤ U and U/L = O(1) was addressed in relation to the restricted shortest path problem [13], [14] and to Problem DPQ [2]. The details of these techniques are out of the scope of this work, however, for completeness, we present an outline of the solution. The general idea is to perform a binary search for a tight upper bound. At each iteration, a possible bound is tested by some test procedure that indicates whether it is too small or too large. An accurate test procedure might require a large number of operations for each run. Two key methods allow a very ef?cient search. First, approximate tests are used. These tests have a “gray-zone” around the tested value, for which they do not provide any information, however they still enable narrowing in on the bound. The idea is to initially use a simple and coarse test to ?nd valid bounds that satisfy U/L < n, and then use more accurate (and costly) tests to re?ne these bounds. The second key is the application of geometric (rather than arithmetic) mean while performing the binary search. Lemma 6 and 7 summarize these techniques. Lemma 6: Valid bounds, L ≤ c? ≤ U , that satisfy U/L ≤ n, can be found in O(n log D log(Dn)) time.6 Lemma 7: Valid bounds that satisfy U/L ≤ n, can be re?ned to tight bounds that satisfy U/L = O(1), in O n2 log log n(log D + n) time. The test procedure that enables the result of Lemma 6 searches for the minimum cost required on the most costly link. Given a possible bound β, it checks in O(n log D) whether any feasible D-wide partition exist if we assume that the cost of any single link is no more than β. Selection in matrices with sorted columns [15] is used to search for such a feasible bound among theO(Dn) possible values. The test procedure that enables the result of Lemma 7 is Algorithm CWPQ with = 1. Using geometric mean in the binary search enable ?nding the tight bounds in O(log log n) tests. Combining Algorithm C-WPQ with the ef?cient bound search techniques establishes Theorem 3. Theorem 3: An -cost optimal solution to Problem WPQ can be found in n O n ( )2 + log2 D time.7 V. S PECIAL C LASSES OF C OST F UNCTIONS So far, the only assumption on the link cost functions was that they are monotonic non-increasing with the delay. In practice, link cost functions are more restrictive. For instance, a link may not offer the full range of delays, but rather provide
such bounds can be found in O(n log D log log β0 ), where β0 is the ratio of some coarse (possibly trivial) initial bounds. 7 Assuming 1/ > log log n.
6 Alternatively,

only a few SLAs. The cost functions in such a case would be discrete functions,8 i.e., de?ned only for speci?c delays. In this section we show that, by focusing on more speci?c classes of cost functions, more ef?cient solutions can be established. We discuss two cases of practical interest. A. Discrete Cost Functions Discrete cost functions are de?ned only for a (relatively) small set Q = {q1 , q2 , q3 , . . .} of link QoS requirements. Alternatively, we can view each cost function as a step function with steps at each value in Q. Even if we de?ne the cost (as a step function) over the whole range of delays, any optimal allocation would use only values from Q. Indeed, there is no gain from allocating a delay qi < d < qi+1 on any link, because the cost of qi is the same with better performance. Let q be the maximal number of values on any link, then the binary search at Line 9 of Algorithm C-WPQ can be performed in O(log q). If we use Algorithm C-WPQ with the ef?cient bound search then the overall complexity is O n ( n )2 + log2 q = O n( n )2 , assuming q < n/ . This is an improvement over the general case whenever log D > n/ . B. An Example of “Homogeneous” Functions Here we demonstrate that a more signi?cant improvement can be achieved when all link cost functions are of the same form. Speci?cally, we investigate cost functions of the form cl (d) = Al /dθ + C l , where Al , θ, C l are given constants. This function has many desirable practical characteristics. It decreases with the delay, as required; it is convex; it assigns in?nitely high cost when the required delay guarantee approaches zero, and it assigns a ?xed minimal link usage cost C l , even if no guarantee is required. The constant θ determines how fast the cost grows for low delays and the constant Al is used as a scaling constant. In the following we establish a linear-time algorithm. We l begin by observing that the ?xed cost C = l∈T C is charged for any partition, so we can just assume add it later and assume C l = 0 for all l ∈ T . We will also assume, for now, that θ = 1 and shall relax this assumption later. We ?rst establish some properties of the optimal tree cost. We can view each table T computed by Algorithm WPQ as the cost function of the sub-tree T uv . It provides the cost of the optimal partition as a function of the depth of the subtree, under the assumption that it is D-wide. We call this the uv tree cost function and denote it by cT (d) or cT . Similarly, we de?ne cL , cR , and cB as the cost functions for the subtrees T Luv , T Ruv , and T Buv . We want to be able to compute uv cT (d) analytically, without having to compute it for every d, as is done by Algorithm WPQ. Lemma 8 provides us with a method to do so. Lemma 8: If each link cost functions is of the form Al /d then for any sub-tree, cT
8 We
uv

(d) = AT

uv

/d

?d ≤ D/2,

follow here the terminology of [6].

0-7803-7753-2/03/$17.00 (C) 2003 IEEE

IEEE INFOCOM 2003

where AT is a scaling constant for the sub-tree. Furthermore, there exist similar scaling constants AL , AR , AB for T Luv , T Ruv , and T Buv . Proof: The proof is by induction. Obviously, the claim holds if T uv is a single link. We ?rst show that if the claim holds for T Luv and T Ruv then it is also true for T Buv . By the results of Section III, we have for d ≤ D/2 cB (d) = cL (d) + cR (d). By the assumption cL (d) = AL /d and cR (d) = AR /d, hence cB (d) = AL /d + AR /d = (AL + AR )/d, namely cB (d) = AB /d, for AB = AL + AR . Next we show that if the claim holds for T Buv then it is also true for T uv . Again, from Section III, cT (d) = min cB (x) + cuv (d ? x).
0≤x≤d

uv

C OMPUTE -A (T , {cl (d)}l∈T ): 1 Select any root link (u, v) ∈ T uv 2 AT ←B UILD -A(T uv ) 3 Starting from v, visit all nodes w ∈ T uv in pre-order order 4 x ← parent(w) wx 5 AT ←B UILD -A(T wx )
Procedure B UILD -A (T uv , {cl (d)}l∈T uv ): 1 if T uv is a link then uv 2 AT ← Auv 3 return uv 4 (else) if AT is already known then 5 return 6 (else) call B UILD -A(T Luv , {cl (d)}l∈T Luv ) 7 call B UILD -A(T Ruv , {cl (d)}l∈T Ruv ) 8 A B ← AL √ A R √ + uv 9 AT ← ( AB + Auv )2 10 return Fig. 6. Algorithm C OMPUTE -A

Applying the assumption, we have cT (d) = min AB /x + Auv /(d ? x).
0≤x≤d

It is easy √ verify that the minimization yields a cost of to √ cT (d) = ( AB + Auv )2 /d at √ AB d. (1) x= √ √ AB + Auv That is, cT (d) = AT /d, where √ √ √ AT = AB + Auv . We can build cT (d) = AT /d recursively, starting from the leafs. We have shown that the assumption is preserved throughout this build procedure. Thus, we have established the claim with √ √ √ AB = AL + AR and AT = AB + Auv . Lemma 8 states that this type of cost function is closed under the tree building computations, for all depth no greater uv than D/2. Using this result, Procedure B UILD -A builds AT recursively in linear (O(n)) time. uv Algorithm C OMPUTE -A computes AT for all sub-trees uv vu uv T ∈ T . Note that, AT = AT , therefore it is not enough to run Procedure B UILD -A for a single root link. However, uv after a single call to Procedure B UILD -A we have AT in one direction for all links of T . The other direction is computed by starting from the root link and visiting all nodes in pre-order. The traversal maintains the property that after a node w is viswx is known for every link (w, x) ∈ N (w). This ited then AT vu property trivially holds for v, since only AT is not computed vu by the initial call to Procedure B UILD -A and AT = Avu . wx only for Throughout the traversal, we need to compute AT the parent x = parent(w) of w, since all other values are

already known after the initial call to Procedure C OMPUTE -A. Furthermore, the call to Procedure C OMPUTE -A requires O(1) operations, since a recursive call to B UILD -A(T wx ) terminates immediately. This is because x was already visited, hence xy AT is already known for all (x, y) ∈ N (x). Thus, overall only O(n) additional operations are performed after the initial call to Procedure C OMPUTE -A. Theorem 4 summarizes these results. uv Theorem 4: Algorithm C OMPUTE -A computes AT for uv all sub-tress T ∈ T in O(n) time. uv We have established cT (d) for all sub-trees and for all d ≤ D/2. Next we show how we can avoid having to compute uv cT (d) for larger values of d. We need to ?nd a location in the tree that is no further than D/2 from any node. We call this the center of the optimal partition and de?ne it formally as follows. For a given partition, we call u a center-node if Duv ≤ D/2 for all (u, v) ∈ N (u); we call a link (u, v) a center-link if Duw ≤ D/2 for all (u, w) ∈ N (u) and Dvw < D/2 for all (v, w) ∈ N (v). The center of a partition is either a center-node or a center-link. Next, we establish some properties of the center. Lemma 9: If u is a center-node of an optimal D-wide partition and all costs are strictly monotonic then Duv = D/2 for all (u, v) ∈ N (u). Proof: Let (u, v) be a link for which Duv < D/2. Since u is a center node, both DLvu and DRvu are less than D/2, hence so is DBvu . This implies that the delay allocation on T uv can be increased to D/2 without violating the width constraint. Since all costs are strictly monotonic, an increase in the delay allocation must reduce the cost, contradicting the optimality of the partition. Each cost functions Al /d is strictly monotonic so Lemma 9 can be applied.9 Lemma 9 implies that we can have either a center-link or a center-node, but not both. The strict monotony
9 Even if the cost functions are not strictly monotonic, the proof of Lemma 9 implies that there exists an optimal partition for which u is the center node and the equality holds.

0-7803-7753-2/03/$17.00 (C) 2003 IEEE

IEEE INFOCOM 2003

implies that the minimal allocation on any link must be greater than zero, and there exists at least one path through every link for which delay(p) = D. Otherwise, the allocation to the link can be increased, reducing the cost without violating the width assumption. It also implies that Duv > DBuv . (2)

Lemma 10: In any optimal D-wide partition there exists a unique center. Proof: Lemma 9, together with Equation 2, implies that we cannot have more than one center-node. Equation 2 also implies that we can not have more than one center-link. Thus if either a center-node or a center-link exists then it is unique. We prove their existence by showing how a center can be found. First, we replace each link (u, v) with two directed links (u, v), (v, u). Then, we color each link green if Duv > D/2 and red otherwise. If all outgoing links from a node u are red then u is a center-node. If both (u, v) and (v, u) are green then (u, v) is a center-link. We start from any leaf and traverse over green links only. For any leaf node u the directed link (u, v) must be colored green, since at least one path through (u, v) must have a delay of D. By Lemma 3, there is at most one green outgoing link from any node so the traversal is well de?ned. If we cannot continue the traversal then all outgoing links are red and we have reached a center-node. Otherwise, we must eventually enter a simple cycle. Since we started from a tree, the directed cycle must correspond to a single bi-direction link, which is a center-link. Lemma 11: Let (u, v) be a center-link √ an optimal Dof √ √ wide partition. Then, ABvu < ABuv + Auv . Proof: Since (v, u) is a center-link DBvu < D/2. Consider the allocation we get by moving δ ≤ D?DBvu delay from the allocation of (u, v) to increase the depth of T Bvu . It is easy to verify that the allocation we get still satis?es the widths constraint. Optimality implies that there is no gain from such a move. Since this is true for any δ and both cBvu and cvu are differentiable, we must have |cBvu (DBvu )| ≤ |cuv (duv )|. Hence, ABvu Auv ≤ , 2 (DBvu ) (duv )2 implying √ duv Auv ≤√ . DBvu ABvu √ DBuv ABuv ≤√ . DBvu ABvu √ √ Auv + ABuv √ . ABvu

Lemma 12: Let u be a center-link of an optimal D-wide uv partition. Then, for any (u, v) ∈ N (u), AT ≤ ABuv . Proof: In this case Duv = DBuv + duv = D/2, hence DBuv < D/2, and duv < D/2. Following the proof of Lemma 11, it is feasible to move δ from T Bvu to either (u, v) or T Buv . Since there must be no gain from such a move, this implies |cBvu (DBvu )| ≥ |cuv (duv )| or √ duv Auv ≥√ . DBvu ABvu We also have √ DBuv ABuv ≥√ . DBvu ABvu Summing, as before, we get Duv duv + DBuv 1= = ≥ DBvu DBvu
T uv

√ √ uv √ Auv + ABuv AT √ = √ , Bvu A ABvu

hence, A Bvu ≤ 1, and the lemma follows. A After we run Algorithm C OMPUTE -A, Lemma 11 allows us to test whether a link (u, v) can be a center link by comparing √ √ √ √ √ Bvu Buv + Auv . Note that, ABuv + Auv = √A uv to A uv AT , therefore we can simply compare ABvu and AT . uv If ABvu ≥ AT then (u, v) is not a center-link. Lemma 12 uv provides a similar test for a center-node. If AT > ABvu then u is not a center-node. Since ABvu = ALvu + ARvu , from symmetry, there is at uv most one link (u, v) ∈ N (u) for which AT > ABvu . Note that, this test cannot fail for any leaf u ∈ T . In order to ?nd the center we repeat the method in the proof of Lemma 10. We replace each link (u, v) with two directed links (u, v) uv and (v, u). Then, we color each link green if AT > ABvu and red otherwise. If all outgoing links from a node u are red then u is a feasible center-node. If both (u, v) and (v, u) are green then (u, v) is a feasible center-link. All conditions of that proof apply, therefore a feasible center can be found. The time complexity is O(n) since at most n links can be traversed before a cycle is entered. The actual partition on each sub-tree can be computed using Equation 1. All the above results, with slight modi?cations apply even if θ = 1. The modi?cations are straightforward and therefore omitted. We summarize our results in Theorem 5. Theorem 5: Given link cost functions of the form cl (d) = Al /dθ +C l for all l ∈ T , an optimal solution to Problem WPQ can be found in O(n). VI. D ISCUSSION We have dealt with the many-to-many QoS partition problem on trees in context of performance-dependent costs [1], [2], [6], [12]. The relation between performance and cost is an important aspect of QoS provisioning in a commercial environment. Providing QoS guarantees requires resource allocations on each network element and thus is associated with direct and indirect costs. Finding the least cost allocation which satis?es the connection’s QoS requirements is a fundamental network

For similar reasons,

Summing both we get Duv duv + DBuv = ≤ DBvu DBvu

The lemma follows from Duv > D/2 > DBvu , which implies that 1 < Duv /DBvu .

0-7803-7753-2/03/$17.00 (C) 2003 IEEE

IEEE INFOCOM 2003

optimization problem. The performance-dependent cost framework considered in this paper is a simple yet powerful model that incorporates the Cost-QoS tradeoffs. It is an extension of the well known bi-criteria model in which each link is associated with a single QoS guarantee and a single cost. Instead of a single level of service, each link may offer multiple levels of service or, generally, a complete Cost-QoS function. This framework is more descriptive of the practical tradeoffs between the strictness of the QoS requirement and the cost of their guarantee. We have continued the work presented in [2], which dealt with one-to-one and one-to-many connections. The present study has established the ?rst solution to the many-to-many case, which arises in the context of QoS-supported group communication sessions, such as tele-conferencing and virtual classes. In such applications, there is an end-to-end QoS requirement between any two members of the session. It turns out that the many-to-many problem, with additive (delay) QoS bounds, is inherently much more complex than the one-tomany multicast tree case. Thus, a considerable amount of work was needed in order to develop ef?cient algorithms for this case. We established the structure of optimal solutions to this problem and presented an optimal pseudo-polynomial solution. From this exact solution, we derived two types of ef?cient (fully polynomial) approximations: delay-approximation and cost-approximation. The approximations are within (1 + ) of the optimal solution (in either delay or cost). We showed improved results for the practical case of discrete cost functions. We further studied a special case of convex cost functions which are of practical interest. For this case, we developed a remarkably ef?cient algorithm that achieves an exact solution to the many-to-many problem in linear time. In this study, we have assumed the existence of a single multicast tree for a session. While some proposed multicast protocols construct more complex topologies, such as mesh and reduced-mesh, most of the basic multicast protocols, such as CBT or PIM, typically maintain a single tree for each session. Extending the results of this study in order to make them apply to more complex or failure-resilient topologies would require a considerable amount of work, since the theoretical properties of the problems change signi?cantly. Nonetheless, we believe that the results presented here, regarding trees, provide signi?cant insight and some of the required basics for such extensions.

An important ?nding of this study is that some generic functions allow for more ef?cient solutions than even the discrete model, which is the current basis for QoS provisioning (e.g., [11]). Our results show that a more expressive multivalued cost function framework is not only feasible, but practical. We believe that ef?cient linear solutions can be established for other cases of special practical interest, beyond those investigated in this paper. These ?ndings should be taken into consideration when de?ning future QoS pricing schemes. R EFERENCES
[1] F. Erg¨ n, R. Sinha, and L. Zhang, “QoS routing with performanceu dependent costs,” in Proceedings of the IEEE INFOCOM’2000, TelAviv, Israel, Mar. 2000. [2] D. H. Lorenz, A. Orda, D. Raz, and Y. Shavitt, “Ef?cient QoS partition and routing of unicast and multicast,” in In Proceeding of The 8th International Workshop on Quality of Service (IWQoS 2000), Pittsburgh, PA, June 2000, pp. 75–83. [3] V. Firoiu and D. Towsley, “Call admission and resource reservation for multicast sessions,” in Proceedings of the IEEE INFOCOM’96, San Francisco, CA, Apr. 1996, pp. 776–785. [4] M. Kodialam and S. H. Low, “Resource allocation in a multicast tree,” in Proceedings of the IEEE INFOCOM’99, New York, NY, Mar. 1999, pp. 262–266. [5] D. H. Lorenz and A. Orda, “Optimal partition of QoS requirements on unicast paths and multicast trees,” IEEE/ACM Transactions on Networking, pp. 102–114, Feb. 2002. [6] D. Raz and Y. Shavitt, “Optimal partition of QoS requirements with discrete cost functions,” IEEE Journal on Selected Areas in Communications, vol. 18, no. 12, pp. 2593–2602, Dec. 2000. [7] A. Goel, K. Ramakrishnan, D. Kataria, and D. Logothetis, “Ef?cient computation of delay-sensitive routes from one source to all destinations,” in Proceedings of the IEEE INFOCOM’01, Anchorage, Alaska, Apr. 2001. [8] R. Nagarajan, J. Kurose, and D. Towsley, “Allocation of local quality of service constraints to meet end-to-end requirements,” in IFIP Workshop on the Performance Analysis of ATM Systems, Martinique, Jan. 1993. [9] A. Orda and A. Sprintson, “A scalable approach to the partition of QoS requirements in unicast and multicast,” in Proceedings of the IEEE INFOCOM’02, New York, NY, June 2002, pp. 685–694. [10] S. Chen and K. Nahrstedt, “An overview of quality-of-service routing for the next generation high-speed networks: Problems and solutions,” IEEE Network Magazine, vol. 12, no. 6, Nov./Dec. 1998. [11] S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, and W. Weiss, “An architecture for differentiated services,” Internet RFC 2475, Nov. 1998. [12] D. H. Lorenz and A. Orda, “QoS routing in networks with uncertain parameters,” IEEE/ACM Transactions on Networking, vol. 6, no. 6, pp. 768–778, Dec. 1998. [13] R. Hassin, “Approximation schemes for the restricted shortest path problem,” Mathematics of Operations Research, vol. 17, no. 1, pp. 36– 42, Feb. 1992. [14] D. H. Lorenz and D. Raz, “A simple ef?cient approximation scheme for the restricted shortest path problem,” Operations Research Letters, vol. 28, no. 5, pp. 213–219, June 2001. [15] G. N. Frederickson and D. B. Johnson, “The complexity of selection and ranking in X + Y and matrices with sorted columns,” Journal of Computer and System Sciences, vol. 24, no. 2, 1982.

0-7803-7753-2/03/$17.00 (C) 2003 IEEE

IEEE INFOCOM 2003


赞助商链接
相关文章:
更多相关标签: