Informatica 36 (2012)201-212 201 Optimal Allocation of Rates in Guaranteed Service Networks Aniruddha Diwan Motorola India Electronics Ltd Bagmane Techpark, C. V. Raman Nagar, Bangalore 560093, India E-mail: aniruddha@motorola.com Joy Kuri Department of Electronic Systems Engineering, Indian Institute of Science, Bangalore 560012, India E-mail: kuri@cedt.iisc.ernet.in, http://www.cedt.iisc.ernet.in/people/kuri/ Sugata Sanyal School of Technology & Computer Science Tata Institute of Fundamental Research, Homi Bhabha Road, Mumbai 400005, India E-mail: sanyals@gmail.com, http://www.tifr.res.in/~sanyal Keywords: guaranteed service networks, IntServ, optimal rate allocation, rate reservation Received: October 6, 2011 We examine the problem of rate allocation in Guaranteed Services networks by assigning a cost corresponding to a rate, and examining least cost allocations. We show that the common algorithm of allocating the samerate to a connection on alllinks alongitspath (called the Identical Rates algorithmhence-forth) is, indeed, a least cost allocation in many situations of interest This finding provides theoretical justification for a commonly adopted strategy, and is a contribution of this paper. However, it may happen that the single rate required is not available on some links of the route. The second contribution of this paper is an explicit expression for the optimal rate vector for the case where Identical Rates is in-feasible. This leads to an algorithm called General Rates that can admit a connection by allocating possibly different rates on the links along a route. Finally, we simulate the General Rates algorithm in a dynamic scenario, and observe that it can provide, at best, marginally improved blocking probabilities. Our conclusion is that the performance benefits provided by General Rates are not compelling enough, and the simpler Identical Rates suffices in practice. Povzetek: V članku je analiziran način alociranja v servisnih omrežjih. 1 Introduction In this paper we consider the problem of rate allocation in the context of the Guaranteed (G) Service framework [1]. The G Service framework enables the receiver of an individual data flow to compute the rate (say R) that it needs to reserve, so that its QoS requirements are satisfied. Thus, a rate vector (R,R,...,R) is reserved, with the vector having as many elements as there are links on the path between the source and the destination. R is a function of the traffic parameters and QoS requirements of the flow, as well as network characteristics such as the number of hops on the path, the scheduling policy employed at each hop and the propagation delay along each hop. Now suppose that the rate R is not available on some links of the route. When this happens, the Connection Admission Control (CAC) module is usually programmed to block the incoming flow. But, in fact, sufficient bandwidth may not be available only on a few links. There might exist other rate vectors that satisfy the delay constraint and the available link bandwidth constraints. Hence, the CAC module may end up blocking a connection request unnecessarily. This scenario provides the starting point for the work described in this paper. We are motivated to examine the rate allocation problem in the hope that we may avoid unnecessary connection blocking and thereby achieve a bigger admission region than possible when a single rate (viz., R) is reserved on all nodes along the path. To this end, we assign a cost to bandwidth allocation at each hop and look for minimum cost allocations. Rate allocation in Guaranteed Services networks has a long and rich history [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]. However, a common theme that runs through the vast literature is that of identical rate assignment at each node. Our approach to this problem is novel because we do not start by making this tacit assumption. We pose and answer the questions: (a) Are there circumstances in which allocating unequal 202 Informática 36 (2012) 201-212 A. Diwan et al. rates is beneficial? (b) What criteria can one use to compare alternate rate allocations? What is the best rate allocation that can be done according to a chosen criterion? To the best of our knowledge, the existing literature does not raise these questions. We begin by listing in Section 3 a few important results in the areas of arrival and service curves, as well as end-to-end delays in Guaranteed Services. These results are used subsequently in our analysis. in this paper is different from the one in our work, because we do not have traffic shapers before each node. To summarize, we find two threads in the literature. One group of papers assumes that the same rate is allocated at each hop on the path. The second group allows different rates to be allocated at each hop, but the focus is on finding formulae for end-to-end delay; the issue of assessing and comparing different possible rate vector allocations has received hardly any attention. In this paper, our concern is with precisely this question. 2 Related Work As we have mentioned above, the question that we address does not seem to have received attention in the literature. In this section, we discuss some papers that analyze questions that are related to, but distinct from, the object of study in our paper. [4] surveys basic mechanisms to support QoS guarantees. Scheduling and buffer management are the basic techniques to achieve QoS. The authors discuss RSVP, the end-to-end resource reservation protocol that was suggested to ensure delay guarantees in the Internet. It is stated explicitly that resource reservation proceeds on the basis of a single reservation rate allocated at each node. The general class of schedulers called Latency Rate (LR) servers is discussed in [6]. Latency and allocated rate are the two parameters that influence the delay experienced by a packet served by an LR server. To analyze the delay experienced by a connection passing through a network of servers, the authors assume that the same rate is allocated to a connection at every node on its path. [10] studies a general network with multiple multihop connections sharing the nodes in the network, and focuses on obtaining end-to-end delay bounds, as well as understanding issues related to stability. Each session is associated with a minimum backlog clearing rate. With this rate given, the authors obtain formulae yielding end-to-end delay bounds. However, the issue of how to allocate the service rate at each node was not addressed; it was assumed that the rates are given. In this paper, we are concerned precisely with the question of how to allocate rates so that some pre-defined objective is met. Thus, our work addresses a novel aspect of the problem. In the same way, [7] allows different allocated rates at different nodes, but the interest is in obtaining end-to-end delay bounds for a given vector of rates. On the other hand, our concern is with how to allocate the vector of rates, so that target delay guarantees can be provided while keeping aggregate resource consumption (i.e., bandwidth consumption) low. Thus, the problem considered in our work is orthogonal to that considered in this paper. Yet another paper considering related problems is [11]. Each node on the path of a connection uses a "rate-controlled service discipline," but traffic shapers are employed at each hop. Thus, the network model considered 3 IntServ and Guaranteed Services To ensure that the QoS requirements are guaranteed, the G Service requires each node on the route of the connection to dedicate an appropriate rate R and a buffer space B to the flow during its holding time. Also, a data flow is required to declare its flow characteristics at the time of connection setup and each node is required to declare its network characteristics. If the flow is admitted, only those packets of the flow that conform to the characteristics are guaranteed the QoS requirements. The rate R and the buffer space B required to guarantee the QoS requirements are a function of the flow characteristics and the network characteristics. In this paper, we consider only R as the resource requirement. The flow characteristics are specified in terms of the token bucket parameters which are a triplet (b, p, p), where b is the token bucket size, p is the token accumulation rate, and p is the peak rate of the flow. Node i specifies its network characteristics in terms of the parameters Ci and Di; typically, Ci and Di approximate the departure of the service provided by node i from the "fluid" model of service, in which the flow effectively sees a dedicated channel of bandwidth R between source and receiver. The arrrival process has an envelope Am(r) that is given by A[n(r) = min{L + pr,b + pr},t > 0 (1) where L represents the packet size. When an identical rate R is reserved at each, the service curve for a tandem of nodes 1,2, • • • ,N is given by [16], Sn (t ) N \ i=i J N R -J2 Ci i=1 (2) Ci represents the Maximum Transmission Unit (MTU) on the link leaving the ith node on the path, and Di is the maximum non-preemption delay at the ith node. The end-to-end delay bound is the maximum horizontal distance between the arrival curve Am(r) and the service curve SN(t). With this, the following delay bound can be eas- + t — OPTIMAL ALLOCATION OF RATES IN. Informatica 36 (2012) 201-212 203 ily obtained1. D bound (b - Lmax)(p - R) L R(p - p) N r + + E =i — + D, R + ' Ln R + N E ,=i — + D, R + ' R P > R, P < R. (3) where Lmax denotes the maximum packet size on this connection. If Dreqd is the worst-case end-to-end delay that is acceptable for the packets of a flow, Dbound < Dreqd gives the minimum rate R that has to be allocated at each node on the route of the flow. We denote this minimum rate by Requal. Now we describe the delay bound when different rates are allowed at the nodes. Let the rate allocated at node i be R». The arrival process envelope is Am(r) as before. Let Rmin = min» Ri and Rmin > p. It was shown in [12, 6] that the service curve for a tandem of nodes 1, 2, ■ ■ ■ , N is given by (example 3.5 of [12]) sn (t ) = N N —, -E D--E £) R (4) D bound Rmin (P - P) — + D, Ri N E ,=i N T max L - + E R — + D, Ri Rm P > Rmin, P < Rm 3. R» < j», 1 < i < N; j» is the available link bandwidth on link i (which may be less than the capacity of the link). This constraint simply says that the allocated rate should not exceed the available link bandwidth. There may be many rate vector assignments that satisfy the above constraints. We associate a cost with allocating a rate on a link. The cost function fi(Ri) for link i is assumed to be strictly convex and increasing in the allocated rate R». This implies that low-cost rate allocations will tend to avoid assigning large rates. It is further assumed that the cost function is the same for each link and is denoted by f (). For a rate vector R = {Ri, ■ ■ ■ , RN}, the total cost is defined as t(R) = J2j=i f (R»). We would like to allocate that rate vector which minimizes the total cost and hence our optimization criterion is minimization of the total cost for the flow. Without loss of generality, we order the N links in the tandem such that the link with the least available capacity is numbered 1 and so on, i.e., ji < < ■ ■ ■ < . The total cost minimization problem, denoted by MinimumCost, is as follows: (MinimumCost) min^N=i f (R») As before, the end-to-end delay bound is the maximum horizontal distance between the arrival process envelope Am(r) and the service curve SN(t). Then the following delay bound can be easily obtained. (b - Lmax)(p - Rmin) + + subject to: (b - Lmax)(p - Rmin) Lmax N Rmin (P - P) ' R min < Dreqd Ri < Yi, 1 < i < N Rmin > P i=i —+D p + Di Ri (6) (7) (8) (5) It can be seen that when the rate allocated at all the nodes is identical and R, we recover the delay bound of Eqn. (3). 4 Minimum Cost Rate Allocation Suppose that a rate R»is allocated to the flow on link i, 1 < i < N, in such a way that the QoS requirements of the flow are met. We call R = {Ri; ■ ■ ■ ,RN} the "rate vector" assigned to the flow. Then the flow can be admitted if there exists a rate vector assignment R that satisfies the following constraints: 1. Rmin = min» R» > p, i.e., the minimum allocated rate along the route is greater than the average arrival rate of the flow. 2. Dbound < Dveqd, i.e., the end-to-end delay seen by packets of the flow is less than the end-to-end delay requirement specified by the flow. We note that if R\ = R2 = ■ ■ ■ = RN = p is a feasible solution to the MinimumCost problem, it is also the optimal solution. That is, the end-to-end delay requirement is met by simply allocating the average rate of arrivals at each link on the path. To avoid this trivial case, we consider only those connections for which allocating the average rate at each link violates the end-to-end delay requirement. Such connections are called "delay-constrained." In other words, we assume that (p,p, ■ ■ ■ ,p) is not a feasible solution to the MinimumCost problem. Substituting a = (bp - pLmax)/(p — p), we can rewrite the constraint in Eqn. (6) as follows. Rm N — N (b T max) + E R < D"qd - E Di (9) 1 We assume R > p because when R < p, the delay is unbounded. We denote the R.H.S. of Eqn. (9) by D and note that D is a positive quantity. Let x» = 1/R», 1 < i < N, 6» = 1/j1 < i < N and 6 = 1/p. Let xmax = max» x». Let x = (xi; ■ ■ ■ ,xN). Let h(xi) = f (1/xi). The two results that follow are stated without proof. Lemma 1. If f (x) is a convex non-decreasing (concave non-increasing) function over x > 0, then h(x) = f (1/x) is a convex non-increasing (concave non-decreasing) function over x 0. max + a 204 Informatica 36 (2012) 201-212 A. Diwan et al. We now recast the MinimumCost problem in terms of h(), xi, 0i and 5. (MinimumCost) min £ N= 1 h(xi) subject to: + £f=1 Cjxj < D xi > ei, 1 < i < n xi < 5, 1 < i < N (10) (11) (12) Let H ( x) — i=i h(xi) where x — (x\, ■ ■ ■ , xn). The following can be easily proved. Lemma 2. H (x) is a convex function in x. It can be seen that the MinimumCost problem has a convex cost function with linear constraints. For such problems, there exist simple necessary and sufficient conditions (in terms of Lagrange multipliers) for a feasible solution to be optimal [17]. 5 The Unbounded Link Capacities Case First, we investigate the special case of the problem where we can allocate any amount of bandwidth on the links, i.e., Yi — and 0i — 0,1 < i < N. We note that the constraint Eqn. (10) is actually equivalent to N constraints: N axi + Cjxj < D, 1 < i < N j=i (13) We denote by UnbddRates this special case, i.e., the Min-imumCost problem without the available link bandwidth constraints, viz., (UnbddRates) min£ i=1 h(xi) subject to: + £ = Cjxj < D, 1 < i < N xi > 0, 1 < i < N x* < 5, 1 < i < N (14) (15) (16) Now suppose that we decide to allocate an identical rate to the flow on each link along its route. It is easy to compute the minimum identical rate Requai from the delay bound constraint of Eqn. (14); we have xequal — and Requai — - ^i 1 Ci a + £ i= Ci D Thus _ i xequal — (xequai, ■■■ , xequai) is a feasible solution to the UnbddRates problem and among all identical rate vectors, Requai — (Requai, ■ ■ ■ , Requai) has the least total cost. This follows because reducing xequal further will only push up the cost J2i=1 h(xi), as h(xi) is a non-increasing function. The approach of allocating of Requai is widely used to provide end-to-end delay guarantees under the Guaranteed Services framework. We refer to this policy as the Identical Rates policy. Our next theorem states that xequai need not always be the optimal solution to the UnbddRates problem and gives an explicit condition for xequal to be the optimal solution. Theorem 1. xequal is the optimal solution to the UnbddRates problem iff a + Cj > NCU 1 < i < N. Proof: We apply Proposition 3.4.2 of [17]. The constraints of the UnbddRates problem are ordered as follows. - axi + N=1 Cj xj < D is the ith constraint, (1 < i < N ). - xi > 0 is the (N + i)th constraint, (1 < i < N). - xi < 5 is the (2N + i)th constraint, (1 < i < N). As seen before, xequal is a feasible solution to the UnbddRates problem. Let n* denote the multiplier for the ith constraint. - If xequal is also the optimal solution, we need to show the existence of appropriate scalars n*, 1 < i < 3N that satisfy the conditions of Proposition 3.4.2 of [17]. - If xequal is not the optimal solution, we need to show that there exist no scalars n*, 1 < i < 3N that satisfy the conditions of Proposition 3.4.2 of [17]. Let J and A() be as defined in Proposition 3.4.2 of [17]. Therefore, let J = {1, • • • , 3N} and at xequal, A(xequal) = {1, • • • , N} as these are the only active constraints at xequal. If xequal is the optimal solution to the UnbddRates problem, then ¡j,* =0, (N +1) < i < 3N and we need to show that there exist unique nonnegative ¡1, • • • *n , not all zero, such that (using the notation of Proposition 3.4.2 of [17]), g(x) = f (x) + J2jeJ Jj(ajx -bj ) is minimized at xequal. In our case, N g(x) = h(xi)+-----+h(xn)+y^j j=1 N axj + Cixi — D i=1 _ _ _ (17) Note that g(x) is a convex function in x. If g(x) is minimized at xequai, the partial derivatives of g(x) should vanish at xequai. If we take partial derivatives w.r.t. xi, 1 < i < N and set each partial derivative equal to 0 at xequai, we get N linear equations for ¡j,*, 1 < j < N as follows, N -J* + Jj — -hh (xequai), 1 < i < N (18) j = 1 where h'(xequai) is the derivative of h(x ) at xequai . Solving these N equations for jj gives Ji = h'(c ) a + £f=1 Cj — NCi , equal £f=1 Cj i = 1, • • ,N (19) max a OPTIMAL ALLOCATION OF RATES IN. Informatica 36 (2012) 201-212 205 Note that h'(xequai) is a negative quantity. This implies that if a + £ jj=1 Cj > NCi Vi, then xequal is the optimal solution. Otherwise, there do not exist non-negative H* Vi e {1, • • • , N} and hence xequal is not the optimal solution. ■ There are two points to note here. Firstly, Theorem 1 is true for any convex non-decreasing cost function f (). Secondly, it can be seen from Theorem 1 that the identical rate vector xequal need not always be optimal. We give a numerical example to show that a better rate vector indeed exists if a + £ j=1 Cj > NCi is not satisfied for every i. Let us consider the simple cost function f (R) = R which means h(xi) = 1/xi. Thus our optimization criterion is the minimization of the total allocated bandwidth. Consider the following choice of parameters. - N = 3 and a = 30, C1 = 25, C2 = 5, C3 = 5, p = 1,D = 6.5. Then it can be seen that a + £3=1 Ci > 3C2 and a + £?= i Ci > 3C3, but a + £?=i Ci < 3Ci. - The identical rate vector is xequal = (0.1,0.1,0.1) for which the total cost is H(xequal) = 30. - Consider x' = (x1,x2,x'3) where x'-y = 0.095, x'2 = 0.103 + 0005,x3 = 0.103. It can be easily verified _ 35 3 _ that x' is a feasible solution and H(x') = 29.93 < H(xequal ). This shows that xequal is not the optimal solution as x' is a better rate vector. Corollary 1. For the case C1 = C2 = • • • = CN and unbounded rates, Requal is the optimal rate allocation vector. Ci corresponds to the MTU at the interface i. When the same link technology is employed in a network backbone (a situation that may occur quite often in practice), we have the special case of equal MTU:C1 = C2 = • • • = CN (= Cequai). In the rest of the paper we work with this assumption. 6 The Bounded Link Capacities Case Now suppose that the optimal rate Requal is not available on some links of the route. When this happens, the Connection Admission Control (CAC) module is usually programmed to block the incoming flow. But, in fact, sufficient bandwidth might not be available only on a few links. There might exist another rate vector which satisfies the delay constraint and the available link bandwidth constraints. We note that if such a rate vector exists, the total cost of this rate vector is greater than H(xequal). Thus, this is the price to be paid for admitting the flow: the cost is higher. When xequal is infeasible, there is at least one link which the available bandwidth is less than Requal. By our numbering convention, link 1 has insufficient bandwidth; i.e., Y1 < Rqual. Let x* = (x1,x*, • • • , xjj) be the optimal solution when xequal is infeasible. Lemma 3. When xequal is infeasible, the optimal vector x* is characterized by x* = 01 and x* < 01,2 < i < N. The result above says that when xequal is infeasible, it is optimal to allocate the entire available bandwidth on link 1 (reciprocal of 01) to the incoming connection. Proof: The proof relies on establishing the three claims that follow. Claim 1: There exists i e {2, • • • , N} such that x* < 91. Proof: We have N axequal + X Cequal xequal = D i=1 Let xmax = maxi x*. As x* is the optimal solution, N axmax + Cequal xi < D i=1 But x1 > 61 > xequal. This implies N {a + (N 1)Cequal}xequal > axmax + Cequal ^ ^ x* But x*max > x*i ^ xmax > Xequal. This implies N + 1)Cequal}xequal > ®xequal + Cequal ^ ^ which gives i=2 1 N (N - 1) ^ ^ xi < xequal Hence there exists an i G {2, • • • , N} such that x* < xequal < Denote it by x*k. Claim 2: x\ = 01. Proof: We prove this by contradiction. Assume that xi > 01. Recalling that x*k < Q1, consider a new rate vector x' such that, xi — xi - e > #1, x'k — x*k + e < d1 and xi — x*,i — {1,fc}. Let x'max — maxj xi. We choose an e that preserves the structure of x*, i.e., if x'ax — x*, then x'ax — xj. It is easy to see that such an e exists. Note that x' satisfies the delay constraint. Also note that h(x\ ) + h(x*k ) > h(x'1 ) + h(x'k as h() is a convex function. This implies x' is the optimal rate vector and not x*. This is a contradiction. Thus x** — #1. Claim 3: x* < #1, 1 < i < N. Proof: We know that x* — #1 and x*k < #1. We need to prove the claim for the rest. We do this by contradiction. Let there exist a j (among the rest) such that x* > #1. Consider x1 — x1 + e and xj — x* - e. With arguments similar to those of claim 2, we get a better cost at x' which contradicts the assumption that x* was the optimum. Thus x* < #1, as required. ■ x ) 206 Informática 36 (2012) 201-212 A. Diwan et al. 6.1 The OneLink Problem Now we consider the case when yi < Requal, but there are no restrictions on the available link capacities on other links. We refer to this as the OneLink problem and want to obtain the corresponding optimal rate vector. Let x* = {x\, • • • ,x*N} denote the optimal rate vector. >From Lemma 3, we know that x* < 0\,i = {2, • • • , N} and x\ = Then the OneLink problem is as follows: (OneLink) minj^N=2 h(xi) subject to: Cequal^2j=2 Xj < D - (a + Cequal)®1 (20) Therefore, j=2^ 3 aXi + Cequ&lY. j=2 Xj < D - Cequal® 1, 2 < i < N xi > 0, 2 < i < N xi < 5, 2 < i< N (21) (22) (23) Lemma 4. For the OneLink problem, the optimal rate vector is such that x\ = • • • = x*N. Proof: By contradiction. Assume there exist x* = x*k. Without loss of generality x* < x*k. Let x' Then by convexity of h(), x* + xk\ 1 x*+xk 2 ■ hj^^J < 2 {h(x*) + h(xk)} — xj — (N - l)Cequal 1 — D - (a + Cequal ® , r1 — 1 L . xequal — (n _ 1)C Requal — x1 ■ Let (N l)Cequal xequal xOneLink — (®1,xlqual' ,xlqual) and ROneLink — Proof: From Lemma 3, x\ = ®\ and x* < ®\. Claim 1: There exists i G {3, • • • , N} such that x* < ®2. Proof: We have N a®1 + Cequal® 1 + ^ ] Cequalxlqual — D i=2 Let x*max — maxi x*, then x*max — ®1 .As x * is the optimal solution, N axmax + Cequal^~"l xi < D i=1 N a®1 + Cequal® 1 + Cequal ^^ x* < D But x2 > ®2 > xlqual. This implies that N (N - 2)Cequalxlqual > Cequal ^ x* i=3 which gives 1 (N - 2) N E x * < x, equal which gives h(x') + h(x') < h(x*) + h(x*k) contradicting the assumption that x* is the optimal rate vector. ■ It is easy to see that the delay constraint inequality is tight at the optimal rate vector. This gives D — (a + Cequal)® 1 Hence there exists a i G {3, • • • , N} such that x* < Xequal < ®i. Denote it by x*k. Claim 2: x* = ®2. Proof: Similar to that of Claim 2 of Lemma 3. Claim 3: x* < ®2,3 < i < N. Proof: Similar to that of Claim 3 of Lemma 3. ■ Next, we consider the problem where yi < Requal and Yi < Rlqual, but there are no restrictions on the available link capacities on other links. This is the TwoLinks problem. Let x* = {x^ • • • , x*N} denote the optimal rate vector for this problem. >From Lemma 5, we know that x* = ®\ and x* = ®2. Then the problem is: (TwoLinks) minj^N=3 h(xi) subject to: (Y1, Rlqual, ••• , Xlqual). S^arizmg, we have tte M- Cequa^j=3 xj < D - (a + Cequal)®1 - Cequal ®2 lowing: Cequal^2j=3 xj < D - Cequal®1 - (a + Cequal)®2, Theorem 2. xoneLink is the optimal solution to the OneLink problem and therefore ROneLink the optimal axi + rate allocation vector for the OneLink problem. 6.2 The TwoLinks Problem It is possible that xequal and xoneLink are both not feasible. Lemma 6. Ce equal j=3 xj j < D - Cequal (®1 + ®2 ) 3 < i < N xi > 0, 3 < i < N xi 5, 3 i N Then we know that ®i > xequal and ®2 > x1qual. Let x* = {x\, • • • ,x*N} be the optimal solution for this case. Lemma 5. When xequal and xOneunk are both infeasi-ble, the optimal rate vector x* is characterized by x* = ®ux* = ®2 and x* < ®2,3 < i < N. j Proof: Same as that of Lemma 4. ■ It is easy to see that the delay constraint inequality is tight at the optimal rate vector. This gives x** = • • • = * _ D — (a + Cequal )®1 — Cequal®2 j (N - 2)Cequal 1 OPTIMAL ALLOCATION OF RATES IN. Informatica 36 (2012) 201-212 207 Let x1qual R2 equal D — (a + Cequal )O1 — CequalO2 (N — 2)Cequal and 1 equal Let xTwoLinks = (O1j O2j x1qual j RTwoLinks = (Y1 J Y2 , Rlqual J have: Iqual ) and ). Then we R2 J Requal Theorem 3. xTwoLinks is the optimal solution to the TwoLinks problem and therefore RTwoLinks is the optimal rate allocation vector for the TwoLinks problem. 6.3 The K-Links Problem It is clear that in a similar way, one can have problems where 3,4,5, • • • links have limited capacities. The pattern of the optimal solution for the K-Links, problem, K > 3, is already clear from the optimal solutions for the OneLink and the TwoLinks problems. Let Ri _ (N — I '^Cequal equal D - & + Cequal Ce 1 and ri equal Let RfLinks = Xf Links = (Ol = 1/Rf = (Yi Yi equal 72 C equal , Of, xf , Yf j RequalJ equal Yi > Requal ) and equal equal )jI > 1. The K-Links problem is as follows. - The available link capacity on link 1,1 < I < K, is yi , where yi < Requll and unlimited capacity is available on links (K + 1), • • • ,N. What is the optimal rate allocation vector that minimizes the total cost and obeys the delay constraint and the available link capacity constraints? As the technique of obtaining the optimal solution is essentially the same as that in the TwoLinks case, we state the results directly, without proof. Let x* = [x\, • • • , x*N} be the optimal solution to the K-Links problem. Lemma 7. x* i< N. Oi, 1 < i < K and x* < Ok, (K +1) < Lemma 8. x} = ■ ■ ■ = x N- x(K+1) Theorem 4. xKLinks is the optimal solution to the K-Links problem and therefore RKLinks is the optimal rate allocation vector for the K-Links problem. In practice, the available capacities of the links are always bounded. The previous results lead directly to a General Rates allocation algorithm that can be used to decide whether a flow can be admitted and, if so, the optimal rate allocation vector. 7 Simulation Results General Rates allows an incoming connection to be possibly accepted even when Identical Rates blocks it. But, as we have remarked earlier, the total bandwidth required to be allocated is more for General Rates. This means that less bandwidth may be available for calls in the future. So even though General Rates looks appealing in the short term, the long-term consequences of following it need to be examined. In this section, we simulate the General Rates algorithm to study this aspect. We provide some details of our simulation scenario. At each link, the packets are scheduled according to the Weighted Fair Queueing (WFQ) policy [18, 9, 10]. WFQ falls under the Guaranteed Services framework with the following parameters: For a flow j at link i, Ci = L™ax and Di Lm Yi + dprop, where Lmax is the maximum I > packet size of flow j, Lmax is the maximum size of the packets at link i, Yi is the capacity of link i and ddprop is the propagation delay of link i. We assume that all the connections to be routed are full-duplex, that all links are bidirectional and the two halves of a full-duplex connection are to be routed on the same path. Connection requests are assumed to arrive according to a Poisson process and last for a duration that is exponentially distributed. We further assume that the traffic specifications and delay requirements of the connection requests are as specified in Table 1. Our performance criterion is the blocking probability of connections. Class b(kB) p(Mbps) p(Mbps) Dreqd (ms) Lmax(kB) Voice 0.1 0.064 0.064 50 0.1 Vid conf 10 0.5 10 75 1.5 Stored vid 100 3 10 100 1.5 Table 1: Traffic Parameters Figure 1: The homogeneous ring topology, with 155 Mbps links and propagation delay of 4 ms on each link. To study the impact of the General Rates policy, we consider source-destination (SD) pairs with at least 2 hops on the path. We consider the homogeneous ring topology of Fig 1 and the NSFNET topology of Fig. 2. Both 2 hops and 3 hops away SD pairs are considered. To study the effect of non-identical link characteristics, we also consider the ring and NSFNET topologies with link 2 0 5 208 Informática 36 (2012) 201-212 A. Diwan et al. 12 Figure 2: The NSFNET topology, with 155 Mbps links and propagation delay of 4 ms on each link. e 'J2 0.12 0.1 0.08 0.06 0.04 0.02 0 250 1 i i , - / - - Identical -e— / - General -h— - 300 350 400 Offered traffic 450 link rate (Mbps) delay (ms) 0 1 155 4 09 310 4 1 2 155 4 23 310 4 34 155 4 45 310 4 56 155 4 67 310 4 78 155 4 89 310 4 Figure 3: Blocking probabilities for the ring topology of Fig. 1; uniform load, 2 hops away SD pairs. Table 2: Link parameters for the nonhomogeneous ring topology. e 3 0.14 0.12 0.08 0.06 - 0.04 0.02 400 450 500 550 600 650 Offered traffic 700 750 link rate (Mbps) delay (ms) 0 1 155 4 02 310 4 07 620 4 1 2 155 4 1 3 310 4 25 620 4 34 155 4 3 10 310 4 45 620 4 46 310 4 59 620 4 5 13 155 4 67 310 4 78 620 4 89 155 4 8 11 310 4 8 12 620 4 10 11 155 4 10 12 310 4 11 13 620 4 12 13 155 4 Table 3: Link parameters for the nonhomogeneous NSFNET topology. Figure 4: Blocking probabilities for the NSFNET topology of Fig. 2; uniform traffic distribution, 2 hops away SD pairs. bandwidths taking values 155 and 310 Mbps, and 155, 310 and 620 Mbps, respectively, as shown in Tables 2 and 3. 7.1 Uniform Load First, we consider the situation when traffic load is uniform across all SD pairs. In the next subsection, we present results when traffic load is distributed among SD pairs in an uneven manner. In Figs 3 to 6, we consider topologies that are "homogeneous" in the sense that link capacities are equal. In Figs 7 to 9, link capacities are unequal. Each of the figures shows a plot of connection blocking probability as traffic load increases. Fig 3 shows that for the homogeneous ring topology and 2-hop away SD pairs, the General Rates policy achieves slightly better (lower) connection blocking probability than the Identical Rates policy. The same is true for the homogeneous NSFNET topology (Fig 4). However, when we consider 3-hop away SD pairs, the General Rate policy is unable to show any appreciable improvement (Figs 5 and 6). OPTIMAL ALLOCATION OF RATES IN. Informatica 36 (2012) 201-212 209 0.16 0.14 0.12 1 0.1 •a o & 0.08 M e 13 0.06 o m 0.04 0.02 0 150 200 250 300 Offered traffic 350 e 'J2 0.08 0.06 0.04 - 0.02 - 0 600 650 700 750 800 Offered traffic 850 900 Figure 7: Blocking probabilities for the ring topology of Fig. 1 with link parameters of Table 2; uniform load, 2 hops away SD pairs. Figure 5: Blocking probabilities for the NSFNET topology of Fig. 2; uniform traffic distribution, 3 hops away SD pairs. 0.12 0.1 1 0.08 o & M 0.06 e 13 o 0.04 m 0.02 0 400 450 500 550 600 650 700 750 Offered traffic & M e 3 200 250 300 350 Offered traffic 400 450 Figure 6: Blocking probabilities for the NSFNET topology of Fig. 2; uniform traffic distribution, 2 & 3 hops away SD pairs. Figure 8: Blocking probabilities for the NSFNET topology of Fig. 2 with non-identical link parameters of Table 3; uniform traffic distribution, 2 hops away SD pairs. Next, we consider nonhomogeneous topologies. Figs 7, 8 and 9 show that once again, the General Rates and Identical Rates policies perform similarly as far as connection blocking probability is concerned. 7.2 Nonuniform Load With nonuniform loads, the general trends are similar. Figs 10 and 11 show that for the homogeneous case (link capacities equal), as long as the SD pairs are 2 hops away, the General Rates policy shows a slight improvement in connection blocking. However, as we include SD pairs that are 3 hops away, the advantage disappears (Fig 12 and Fig 13). Similarly, for nonhomogeneous topologies, there is little to distinguish between the performances of the General Rates and the Identical Rates policies. We show the 2-hop away SD pair case for the Ring topology in Fig 14, the 2-hop away SD pair case for the NSFNET topology in Fig 15. The case with a mixture of 2-hop away and 3-hop away SD pairs is shown in Fig 16. 210 Informática 36 (2012) 201-212 A. Diwan et al. Offered traffic Figure 9: Blocking probabilities for the NSFNET topology of Fig. 2 with non-identical link parameters Table 3; uniform traffic distribution, 2 & 3 hops away SD pairs. Offered traffic Figure 10: Blocking probabilities for the ring topology of Fig. 1; nonuniform load, 2 hops away SD pairs. Figure 11: Blocking probabilities for the NSFNET topology of Fig. 2; nonuniform load, 2 hops away SD pairs. Offered traffic Figure 12: Blocking probabilities for the NSFNET topology of Fig. 2; nonuniform load, 3 hops away SD pairs. Offered traffic Figure 13: Blocking probabilities for the NSFNET topology of Fig. 2; nonuniform load, 2 & 3 hops away SD pairs. 600 650 700 750 800 850 900 Offered traffic Figure 14: Blocking probabilities for the ring topology of Fig. 1 with link parameters of Table 2; nonuniform load, 2 hops away SD pairs. OPTIMAL ALLOCATION OF RATES IN. Informatica 36 (2012) 201-212 211 0 300 350 400 450 500 Offered traffic 550 600 Figure 15: Blocking probabilities for the NSFNET topology of Fig. 2 with link parameters of Table 3; nonuniform load, 2 hops away SD pairs. is •a o s^ & M e ¿2 250 300 350 400 Offered traffic 450 Figure 16: Blocking probabilities for the NSFNET topology of Fig. 2 with link parameters of Table 3; nonuniform load, 2 & 3 hops away SD pairs. 7.3 Summary The series of plots indicates that the blocking performances achieved by the Identical and General policies remain close, with slight improvement in one or the other in some cases. The results indicate that there is not much to choose between the two policies as far as blocking performance is concerned. 8 Connection Blocking We saw in the previous section that accepting a connection whenever possible (what the General Rates policy does) may lead to significant blocking of future connections. In this section, we attempt to obtain some insight into this aspect by using very simple arguments. Suppose that we have a very simple "network" with two links in tandem. Let the capacities of the links be 2.5 and 10 units respectively. Type A connections traverse both the links while type B connections pass over the second link only. The average rate of traffic from a connection of either type is 0.45. The delay requirement of a type A connection can be met by allocating 2 units of bandwidth on the two links. Similarly, the delay requirement of the Type B connection can be met by allocating 2 units on the second link. For the network and traffic types above, the Identical Rates policy would admit only one Type A connection. Now let us consider the General Rates policy. Let us assume that it is possible to accommodate a second Type A connection by allocating 0.5 and 6 units on the first and second links, respectively. Let us now suppose that the network is empty to begin with, and two Type A connections arrive in quick succession. Also, we assume that these connections have infinite lifetimes. The Identical Rates policy will admit the first Type A connection and block the second, as well as all future Type A connections. The fraction of Type B connections that will be blocked can now be obtained using the Erlang-B formula. The bandwidth available on the second link is 8 units and, therefore, 4 Type B connections can be accommodated; the M/M/4 model applies. The General Rates policy will admit both the Type A connections. As a result, the bandwidth available on the second link is only 2 units. For this case, the M/M/1 model applies. Clearly, the overall blocking probability in this case will be much higher: the fraction of Type A connections blocked is the same as for Identical Rates, while the fraction of Type B connections blocked is much more. Admittedly, our example network and traffic scenario are very simple and contrived. Nevertheless, they do highlight the problem that can result when the General Rates policy is followed. We are currently working on a complete analysis of this problem to extend the intuitive understanding that can be obtained from this simple model. 212 Informática 36 (2012) 201-212 A. Diwan et al. 9 Conclusions In this work, we study the problem of rate allocation from the perspective of total cost minimization. It is shown that the Identical Rates policy need not always minimize the total cost, and a specific condition is derived which, if satisfied, makes the Identical Rates policy optimal. However, if the computed identical rate is not available on every link along the path of a connection, Identical Rates blocks a request without searching for other rate allocations. To admit a connection whenever it is possible at all, a General Rates algorithm is developed; it computes an optimal rate vector with possibly different rates allocated on different links. However, Genenral Rates is forced to allocate more bandwidth on the end-to-end path, and this leaves less resources for future connections. Simulations show that the increased bandwidth consumption of General Rates can become significant in the long run, as a result of which the alo-gorithm is unable to show appreciably improved blocking probability. Hence, the simpler Identical Rates algorithm is sufficient for all practical purposes. References [1] S. Shenker, C. Partridge, and R. Gu6rin. Specification of guaranteed quality of service. RFC 2212, September 1997. [2] 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, January 1993. [3] D. Raz and Y. Shavitt. Optimal partition of QoS requirements with discrete cost functions. In IEEE IN-FOCOM, 2000. [4] R. Gu6rin and V. Peris. Quality-of-Service in packet networks: basic mechanisms and directions. Computer Networks, 31(3):169-179, February 1999. [5] P. White. RSVP and integrated services in the Internet. IEEE Communications Magazine, May 1997. [6] D. Stiliadis and A. Varma. Latency-rate servers: a general model for analysis of traffic scheduling algorithms. IEEE/ACM Transactions on Networking, 6(5):611-624, October 1998. [7] P. Goyal and H. Vin. Generalized guaranteed rate scheduling algorithms: a framework. IEEE/ACM Transactions on Networking, 5(4):561-571, August 1997. [8] H. Zhang. Service disciplines for guaranteed performance service in packet-switching networks. Proceedings of the IEEE, pages 1374-1396, October 1995. [9] A. Parekh and R. Gallagher. A generalized processor sharing approach to flow control in integrated services networks: the single node case. IEEE/ACM Transactions on Networking, 1(3):137-150, 1993. [10] A. Parekh and R. Gallagher. A generalized processor sharing approach to flow control in integrated services networks: the multiple node case. IEEE/ACM Transactions on Networking, 2(2):347-357, 1993. [11] V. Peris L. Georgiadis, R. Guérin and K. Sivara-jan. Efficient network QoS provisioning based on per node traffic shaping. IEEE/ACM Transactions on Networking, 4(4):482-501, August 1996. [12] R. Agrawal and R. Rajan. Performance bound for guaranteed and adaptive services. Technical Report RC20649, IBM Research Report, December 1996. [13] L. Georgiadis, R. Guérin, and A. Parekh. Optimal multiplexing on a single link: delay and buffer requirements. In IEEE INFOCOM, 1994. [14] S. Shenker and L. Breslau. Two issues in reservation establishment. In SIGCOMM Symposium on Communications Architectures and Protocols, Cambridge, Massachusetts, September 1995. [15] H. Ahmadi, J. Chen, and R. Guérin. Dynamic routing and call control in high-speed integrated networks. In 13t^ International Teletraffic Congress, pages 19-26, Copenhagen, Denmark, 1991. [16] L. Georgiadis, R. Guérin, V. Peris, and R. Rajan. Efficient support of delay and rate guarantees in an Internet. In ACM SIGCOMM, pages 106-116, August 1996. [17] D. Bertsekas. Nonlinear Programming. Athena Sci-etific, Belmound, Massachusetts, 1995. [18] A. Demers, S. Keshav, and S. Shenker. Analysis and simulation of a fair queueing algorithm. In ACM SIGCOMM, pages 3-12, 1989.