SUCCESSIVELY IMPROVING BOUNDS ON PERFORMANCE MEASURES FOR PRODUCT FORM QUEUEING NETWORKS M. M. SRINIVASAN Department of Industrial & Operations Engineering The University of Michigan Ann Arbor, Michigan 48109-2117 JANUARY 1985 REVISED 7/86 Technical Report 85-2 (To appear in IEEE Transactions on Computers)

ABSTRACT The use of queueing network models to analyze the performance of computer systems is widespread. Typically the analysis requires certain assumptions to be made. Even under such assumptions, the exact analysis of these models for the performance measures could be quite time consuming, especially when various alternate configurations of the system are to be evaluated. In some situations, bounds on the performance may often be adequate. This issue of obtaining reasonable bounds has hence been the subject of some discussion and a number of bounding techniques have been proposed over the past few years. In this paper we present a bounding technique for networks with a single class of customers that appears to be more effective than techniques previously reported.

1. Introduction: A computer system is evaluated by estimating its performance under various patterns of demand on the system. Queueing network models are typically used here with a view to obtaining equilibrium analytic solutions for predicting the performance under various configurations. Each node in the network represents a service facility where customers queue up for, and receive, service. The exact solution of these queueing networks is, however, infeasible unless certain assumptions are made. These assumptions give rise to a certain class of networks known as Product Form (PF) networks, or separable networks. For these PF networks, it is possible to obtain equilibrium performance measures with relatively less effort. Quite often, situations arise where exact solutions of these queueing networks may not be required. This is especially the case when many alternate configurations are to be evaluated. Similarly, if the workload parameters are not known with reasonable accuracy, as is often the case in the design phase of a system, obtaining exact solutions may be unnecessary. In such cases, one would like to obtain approximate solutions fairly quickly. Needless to say, the errors incurred as a result of an approximate solution technique should be bounded, if possible. 1.1 Previous work: Recent years have witnessed a substantial amount of work on developing techniques for bounding the performance measures of queueing networks for PF networks with a single class of customers [3,4,7,11,13,14,15]. These bounding techniques are applicable when each node in the network is either single server fixed-rate type or is a delay (infinite server) type. The bounds obtained are for the cycle time (the mean system residence time) of a job, and the throughput of the system (number of job completions by the system in unit time). The input 1

parameters required for the calculation of these bounds are the loads at the various nodes. The load at a node is defined as the mean service time demand from the node by a job. Some results have recently been obtained for networks with multiple customer classes [5,6,7]. Results have also been obtained for networks with load dependent nodes and with a single class of customers [10,12]. The latter results depend, however, on bounds obtained for networks consisiting only of fixed rate and delay nodes, and whose behaviour closely approximates the behaviour of the network with the load dependent nodes. In this paper, we restrict attention to PF networks with fixed rate and delay nodes, and a single class of customers. A bounding technique which applies to a larger class of networks than those considered here is the Asymptotic Bound Analysis (ABA) [2]. The bounds obtained by this analysis are very loose. The Balanced Job (BJ) bounds analysis [15] obtains tighter bounds than those obtained by-the ABA. However, these bounds are also often quite loose. The ABA and BJB techniques do not provide a trade-off between computational effort and accuracy for the bounds. Further, bounds obtained here for networks with delay nodes are poor. The Performance Bound Hierarchies (PBH) [4] and the Generalized Quick Bounds (GQB) [14] are both based on the Mean Value Analysis (MVA) algorithm [9]. Both these techniques obtain a sequence of improving bounds (referred to as bounds of increasingly higher'levels') on cycle time and throughput. The GQB technique, however, cannot handle delay nodes, and does not appear to perform significantly better than the BJB technique. A technique based on the MVA algorithm and utilizing some properties of the relation between the throughput and the degree of multiprogramming is presented in [3]. The convolution algorithm of Buzen [1] is used to develop the Convolutional Bound Hierarchies [13]. This bounding technique seems appropriate only for networks with a small number of customers and a relatively large number of nodes. All these techniques 2

are basically recursive in nature. A technique which presents some closed form expressions for the bounds is given by Kriz [7]. This technique is based on the MVA algorithm. A number of computational formulae are presented by this author. However, these formulae generally perform well only as the network population becomes large (at which stage the network begins to behave like an open network). Although the PBH technique gives a better set of bounds than these above mentioned schemes, it requires considerable computational effort to produce increasingly tighter bounds. Exact analysis for the type of networks we consider here takes O(MN) computations, where M is the number of nodes and N the number of customers. The bounds we obtain take O(M) time to compute and use the MVA algorithm to develop a sequence of improving upper and lower bounds with only a marginal increase in computational effort for each set of bounds in the sequence. These bounds are shown to be tighter than the BJ bounds and compare quite favorably with the PBH technique for networks with a single class of customers. In the case of networks consisting of only fixed rate nodes, the first few bounds obtained are shown to be tighter than corresponding PBH bounds. Moreover, in general these successively improving bounds (SIB) can usually be obtained with considerably less computational effort than the PBH bounds. 2. Preliminaries We first consider networks where all nodes are fixed-rate nodes. The analysis extends directly to include delay nodes, and this is shown in section 3. In the following discussion, unless specified otherwise, the index for any summation is over the range 1 through M. Implicit in the discussion is the understanding that we are considering populations of N > 2. From the MVA algorithm, the mean residence time, wm(N), at a fixed rate 3

node m, with N customers in the system, is obtained as Wm(N) = Lm(1 + Qm(N-1)), (2.1) where Lm is the load at node m and Q,(K) represents the mean queue length that would form at node m with K customers in the system. The cycle time W(N) for a given request is the sum of the mean residence times at all nodes and is given by W(N) = Lm(1 + Qm(N-1)) = L(1 + I (Lm/L)Qm(N-1)) m m = L(1 + <(N-1)), (2.2) where L = Lm m 4(N-1) = I pmQm(N-1) (2.3) m with P = Lm/L. (2.4) The term pm is defined as the relative utilization at node m. A straightforward application of Little's rule [8] yields an expression for the mean queue length for any single server fixed-rate center m as (also refer [4] for a similar expression): Lm(1 + Qm(N-1)) Q(N) = N ---- ----—. (2.5) L (1 + O(N-1)) Setting, for notational convenience, DK = 1 + ~(K), (2.6) we can rewrite equation (2.5) as Qm(N-1) - O(N-1) Qm(N) = NPm + Npm( ) —-------— ). (2.7) DN-1 From equations (2.7) and (2.3), p(N-1) = (N-l) E Pm + ((N-1)/DN2)-Y' (N-2), (2.8) m 4

where Y'(N2) p (Qm(N-2) = I pnQn(N2)). (2.9) m n As a first step, we obtain a simple set of upper and lower bounds on ((N-1) (and hence, on the cycle time) which we show are better than the BJB bounds. We term these bounds as level 1 bounds. These bounds are obtained by noting that the term Y'(K) is non-negative for any K 2 O. To see this, we make use of a property which we call the'partial correspondence' property: Definition 2.1: Given a sequence X = {xm}, m=1,...,M, such that XM > XM-1 >... > xl > O, then a sequence Y = {ym}, m=1,...,M, is said to have a Partial Correspondence with X, denoted as Y(PC)X, if for some k, 1 < k < M, M.". > Yk 0 O; Ykl,-...,1 0. Lemma 2.1: Given two sequences X={xi}, and Y={Yi}, i = 1,...,m, such that xm Xm_-1 >... > x2 > xi > O, Y(PC)X E Xi < 1 i and Xi Yi ~ 0, i then, E xi yi > (I xiyi)(I Xj)2 i i j Proof: An alternate statement of the required inequality is to show that: 5

Yi x( —-- - 1) O (A1) i a where a = ) xiYi. Since C xi 5 1, it must be true that i i E xiyi' (Y xiyi)(X xj), i i j So, Yi xi( 1 ).> o. i ao yi Hence, Xkxi( -- - 1 ) > 0 for all xk. (A2) i a In view of (A2) and the fact that a > 0 and xi > O, there exists some m S n such that a yi for all i ~ m. We therefore have to consider two cases: (i) where all terms in the sum in Equation (A2) are non-negative, that is, a < y1, and (ii) not all terms are non-negative, that is y1 < a 6 Yn' Case (i) is trivial: all the terms in the summation in Equation (Al) are non-negative. We consider Case (ii). Here we choose k in Equation (A2) such that Yk < a <S Yk+l Then, from (A2), k n 0 < ) XkXi( yi/a - 1 ) =. XkXi( yi/a -1 ) + I xkxi( yi/a -1 ) i i=1 i=k+1 k n < xixi( Yi/a -1 ) + i XkXi( Yi/ -1 ) i=1 i=k+1 k n < xixi( Yi/a -1 ) + I xixi( yi/ -1 ) i=1 i=k+1 where the first (respectively second) inequality follows from the fact that (yi/a - 1); 0 (respectively > 0) for all i I k (respectively i > k). This final inequality is the same as (A1), so we are done. From the lemma, we have the following corollary which shows that the term 6

YI(K) > 0, for K > 0. Corollary 2.1: I Pm Qm(K) a (I Pm Qm(K))( pi); K > 0 (2.10) m m i Proof: The mean queue length at node i with K customers in the system can be expressed as [2]: K Qi(K) = PI P G(K-n)/G(K); K > 0, (2.11) n=1 where G( ) is a normalizing constant. In Lemma 2.1, let xi=pi, and yi=Qi(K), i=1,2,...,M. The nodes can be ordered so that 0 < p < p2 <... < PM' and from equation (2.11), we then get Q1(K)... < QM(K), in which case, (2.10) follows from Lemma 2.1. Let 3Si = I p (2.12) m and define N = N/DN-1 (213) Here, AN can be thought of as the throughput of a system with total load L = 1, and with population N. Note that XA = 1, and XN > 1; N > 1. Theorem 2.1 Let u = node with maximum load. Then, the term $(N-1) is bounded by: (N-1)S2 < 4(N-1) < = (T1 + T2)-0.5 (2.14a) where T1 = ((N-) Pu - 1), with Pu = Lu/L, (2.14b) and T2 = SQRT(T12 + 4(N-1)S2) (2.14c) Proof: From equations (2.8), (2.12) and (2.13), 7

((N-1) = (N-1)S2 + XN-1 Y'(N-2). (2.15) Clearly, XAN1 a O. From Corollary 2.1, Y'(N-2) is non-negative. Hence the term (N-1)S2 is a lower bound on ((N-1). For the upper bound, note that Y (N-2) = I (Qm(N-2) - PnQn(N-2)) m n (Pu - S2) <(N-2). (2.16) It is clear that pu 2 S2. Noting that DN 2 = 1 + 4(N-2), is seen that It2 s cla + 2th Pu i the term ((N-2)/DN_2 < 1(N-1)/DN_1. Hence we can write q(N-1) < (N-1)S2 + (N-1)(((N-1)/DN1) * (PU-S2). (2.17) The above equation is a quadratic in j(N-1), whose solution gives the desired bound. It can be seen from equations (2.14a,b,c) that the solution of this quadratic requires about 11 operations, given that S2 and Pu have already been computed. It is easy to show that the bounds developed above are tighter than the BJ bounds. This is expressed as: Corollary 2.2: The level one SI bounds on cycle time and throughput are tighter than the corresponding BJ bounds. Proof: We only need to show that the level 1 bounds on cycle time obtained by the SIB technique are tighter than the BJ bounds. A simple application of Little's rule will then show that the level 1 bounds on the throughput obtained by the SIB technique are tighter than the BJ bounds. The bounds on cycle time obtained by the BJB analysis are: L + (N-1).*La W(N) ~ L + (N-1).Lu, (2.19) 8

where Lu is the load at the node with the highest loading, and La is the average load among all the nodes, i.e., La = Lm/M. m In view of equations (2.17) and (2.19), we need to show that (i) LS > (N-1)La, and (ii) Lo< (N-1)Lu. A Lemma proved in [10] gives the following inequality with two increasing sequences {xi}, {Yi } i=l,..,n: I xiYi x Eyi where x = (1/n) Jxi i i i Now, to show (i), let xi- yi = Pi' Then I Pi? Pa Pi Pa i i where Pa = (1/M) I Pm. Hence L = L L-(N-1 ) (N1) = (N-1)-La. m m (ii) From Equation (2.14) we have, 2; ((N-1)pu -1) + SQRT[((N-l)pU -1)2 + 4E] Since, P u a p2. hence we have (N-1)pu 2. So we can write m 2_ < ((N-l)pu -1) + SQRT[((N-1)pU -1)2 + 4(N-l)pu] = ((N-l)p -1) + SQRT[((N-1)pU +1)2] = 2(N-1)pU. Hence, LA < (N-1)Lpu = (N-1)Lu. In concluding this section, it is remarked that the paper by Kriz has used the idea of obtaining'square root' bounds on throughputs for networks with delay nodes. When delay nodes are absent, however, these square root bounds reduce to the BJ bounds. 9

3. Successively Improving Bounds: In the above analysis, the level one bounds required the computation of the terms S2 and L, and these computations needed about 3M operations. We now express the term Y'(N-2) as the sum of a set of non-negative terms. This will enable a sequence of improving bounds to be obtained with some additional computational effort. These improving bounds are termed bounds of increasing levels. Each higher level requires an additional Si term to be computed. Thus, the level 2 SI bounds require the terms S2 and S3, the level 3 bounds require the terms Si, i=2,..,4, and so on. Each of these terms takes about 2M operations to compute. Given that the terms Sj, j=2,..,i, have been computed for some i, our objective here is to compute as tight a bound as possible with these terms. Equation (2.5) is first rewritten, using (2.13) as Qm(N) = PmAN + PmXN Qm(N1) (31) Define, for N > 0, fm(N) = Qm(N), (3.2a) and m(N) = p(fi(N) - nf1(N)); i > 0. (3.2b) n To obtain the expansion of the term Yi(N-2), we use Lemmas 3.1 and 3.2. Lemma 3.1: Consider the function fm(K) as defined by equations (3.2a and 3.2b). Let fi(K) = t(K) } and p = {pm, m = 1,...,M. Then, for i, K > 0, (a) fi(K) (PC) p, (3.3a) (b) Yi(K) = Pm fm(K) a (3.3b) m A proof of Lemma 3.1 is given in Appendix A. The terms Yi(K) are functions of the mean queue lengths at population K. Note that Yi () = 0. Lemma 3.2 now expresses Y (K) as comprising of (i) a term involving only the relative utilizations pm' m=1,...,M, and (ii) a term 10

involving the mean queue lengths at population K-l, and the throughput at population K. A proof of Lemma 3.2 is given in Appendix B. Lemma 3.2: The term fm(K) can be recursively defined, for i a 0, K a 1, as fi(K) = K fl(1) + AK (K-1) and hence, Yi(K) = I Pmfm(K) = K ai + AK Yl(K-l), K > 1;(3.4) m where ai = Yi(1) a 0. (3.5) From Lemma 3.1 and equation (3.2), noting that Qm(1) = pm' we can derive an expression for ai as follows: ao Pmf~(1) = S2 m'a, Pn,^(DP= Pm (fm1) -S S3 2 a, m m m and in general, i-1 ai Si+2 - Si+-jaj, i 1. (3.6) j=0 Now, define i AKi = n XK-n' K a i a O. (3.7a) n=0 = 1, i < 0. (3.7b) Theorem 3.1 obtains an expression for DK in terms of the ai's and the A's. Theorem 3.1: The term DK can be written, for K > i > 0, as i DK = 1 + KS2 + I (K-j) aj AKj_1 + Yi+l(K-i-1) AK,i. (3.8) j-=1 which can also be written, using equation (3.7b), as DK = 1 + I (K-j) caj AKj_. + Yi+l(K-i-1) AKi. (3.8a) j =-O 11

Proof: From equations (2.6) and (2.15), we have DK = 1 + KS2 + XK Y'(K-1). (3.9) The proof now follows by a repeated application of equation (3.4) in equation (3.9). 0 Theorem 3.2: p(K)/K > ((K-1)/(K-1). (3.10) Proof: From equation (3.8), noting that AK,j-l > AK-l.,j-l for K > j a 0, K-1 K-2 ~(K) = KS2 + I (K-j) aj AK,j_.1 KS2 + I (K-j) aj AKlj_-. s=1 j=1 Hence, ((K) K-2 K-j.. — > S2 + I ( —-) as AK_,j(311) zK j=1~ K 1J AK.l 9j (3.11) K j=l K-j > K-j-1 Now, it is clear that for K > j > 0, we must have - --- -. Hence the inequality in equation (3.11) gives ~(K) K-2 K-j-(K-1) -- S2 + K- 1- j AK-_1j-1 KK j=1 K-1 where the last equality follows from equation (3.8), with K-1 in place of K, and with i taken as K-2. 0 A lower bound on the term Yi+l(K-i-1) in equation (3.8) is given by Theorem 3.3. Theorem 3.3: The term Yj+1(K) a YJ(K) aj+1/aj; j, KaO. (3.12) A proof of Theorem 3.3 is given in Appendix C. From this theorem, we have the following: 12

Corollary 3.1: aj+l/aj > ai+l/ai, j > i > 0. (3.13) Proof: From Theorem 3.3 for K = 2, and using equation (3.14), we get 0 < yj+l(2) aj - YJ(2) aj+l 2 2 (2aj+1 +- yj2(1)) aj - (2 aj + -- yj+I(1)) cj+1 Di i D, - (2/D1) (aj+2 mj - OLj+1 aj+l)Since D, > O, this implies j+2/aj +1 > aj+ 1/aj (3.14) A repeated application of the above inequality gives the desired result. Theorem 3.4: For K > i > 0, i K-i-1 DK a 1 + KS2 + 2 (K-j)aj AK,j_ + (K-i1 ) Ai_ ( -- ) —. (3.15) j=1 J J1+(K-i-1)ao i-1 Proof: From equations (3.8) and (3.12), we get for K > i > 0, i c"i+1 DK a 1 + KS2 + I (K-j)aj AK, j1 + AK,i Y~(K-i-1) - j=1 "o Noting that (a) Y~(K) = 4(K) = DK - 1, and (b) AK,i = AKi-1 XK-i' we can rewrite the above equation, for K > i, as i 1 ci+l DK j 1 + KS2 + (K-j) AK,j1 + AK,i-1 XKiDK-i-l(1 - --- ) -- j=1 DK-i-l ao Now, using a level one lower SI bound on DKi_1 in the denominator of the last term, and noting that XK_iDK_i_1 = K-i, i K-i-1 DK > 1 + KS, + I (K-j)cj AKj-_ + (K-i) AKi_1 ( -----— )a; iO. j-=1 1 +(K-i-1 )ceo 13

From equation (3.14), for i > 0, ai+l a i-l. Using this in the inequality obtained above gives the desired result. o 3.1 The sequence of improving upper and lower bounds: In general, let n(N-1) (respectively, ~n(N-1)) denote the level n upper SI bound (respectively the level n lower SI bound) on ((N-1). We first obtain the sequence of upper SI bounds. 3.1.1 The upper bounds: We first develop a tighter level one upper bound on ((N-1) than was obtained in Section 2. This is obtained as follows: From equations (2.6), (2.8), (2.16) and (3.10), np(N-1) (N-1) (N-(N1)S2 + (N-1) * (Pu-S2) * --- --, (3.16) 1 + n4(N-1) where n =(N-2)/(N-1). (3.17) Equation (3.16) is a quadratic in j(N-1). Its solution is given by &j(N-1), where 0.5 ^1(N-1) = (T1 + T2) --, (3.18) n where T1 = (N-2) Pu - 1, (3.18a) and T2 = SQRT (T12 + 4(N-2)S2), (3.1 8b) with n as defined by (3.17). It is clear that since n < 1, n T(N-1) 4(N-1)....... < -..-... (3.19) 1 + (N1 + n (N-1) + (NHence use of equation (3.16) gives a tighter bound on <(N-1) than the bound obtained using equation (2.17). Corollary 3.2 shows that this bound is tighter than the level 2 PBH bound. (Note that both bounds need to compute the term S2). 14

Corollary 3.2: The level 1 upper SI bound given by equation (3.16) is tighter than the level 2 PBH upper bound for networks without delay nodes. Proof: The level one upper SI bound, u(N-1), is obtained using equation (3.16). This equation can be rewritten after some elementary algebra as S2 + (N-2)pu 1U(N-1)/(N-1) u(N-1) = (N-1) ( —----- I ) —--. (3.20) 1 + (N-2) 4U(N-1)/(N-1) Let OU(N-1) denote the level two PBH bound on 4(N-1). When delay nodes are absent, this is obtained as (equation (18) in [4]) S2 + (N-2)p2 0 ) (N-1) = (N-1) ( —----------- ). (3.21) 1 + (N-2)pu Comparing equations (3.20) and (3.21), it is easily seen that OU(N-1) < 3U(N-1) if 1(N-1) < (N-1)Pu. Noting that (N-l)pU is the BJ bound on O(N-1), this is obvious from Corollary (2.2). o The sequence of upper SI bounds on O(N-1), is given by Theorem 3.5. Theorem 3.5: The level n upper bound on O(N-1) is given, for N-1 > n, by 0.5 n(N-1) = --- (T1 + T2(n)), (3.22) n where T1 = (N-2)pu - 1, (3.22a) T2(n) = SQRT (T12 + 4(N-2)(S2 - o(N-1,n-1))), (3.22b) and i j-1 N-2-m a(N-1,i) = (PuSj+1-Sj+2) n ----—. (3.22c) j=1 m=0 -3 with DN_3 being a level one upper bound on DN_3. A proof of Theorem 3.5 is given in Appendix D. 15

For example, a level three upper bound is given using a(N-1,2) in equation (3.22b) where N-3 N-2 a(N-1,2) ( (PuS-S,) + (PUS3-S,) — ) -- DN-3 DN-3 3.1.2 The lower bounds: Theorem 3.4 is now used to develop a sequence of lower bounds on 4(N-1). Theorem 3.6 develops the bounds. A proof of Theorem 3.6 is given in Appendix E. Theorem 3.6: The level n lower bound on %(N-1) is given, for N-1 > n > 1, by %n(N-1) = (T1 + T2(n))/2n, (3.23) where T1 = ((N-2)S2 - 1), (3.23a) T2(n) = SQRT[T12 + 4(N-2)(S2 + (N-2)B(N-1,n-1))], (3.23b) and -(N-li) = O; i=O, i-1 j N-1-m i N-1-m ia (N-i-2) 8(N-l,i) = a I ---- + a ( II - ) (1 + -- - ----— ); i>, (3.23c) j=1 m=2 DN-m m=2 DN__m ai_1 1+(N-i-2)ao with DN-_1m = 1+%(N-l-m) where %(N-1-m) is an upper bound on %(N-1-m). Empty products are assumed here to have a value of unity in equation (3.23c). The level two lower SI bound obtained by setting i=1 in equation (3.23c) is tighter than the level three PBH bound as Corollary 3.3 shows (note that both bounds require the terms S2 and S3): Corollary 3.3: For networks without delay nodes, the level two lower SI bound on DN_1 is tighter than the level three PBH bound on DN_1, for N > 3. A proof of Corollary 3.3 is given in Appendix F. 16

For example, a level three lower bound is given by using B(N-1,2) in equation (3.23b). Here, 8(N-1,2) is given from equation (3.23c) as (N-4) )2 B(N-1,2) = a1 + a2((N-3)/DN_3)(1 + --------- - ) 1 + (N-4)S2 al with DN_3 being given by a suitable upper bound on DN_3. Operationally, we can first calculate the upper bound on <(N-1) using equation (3.22); call it p(N-1). Now, to calculate the lower bound on O(N-1) using equation (3.23), we need the terms ((N-1-m). These are easily calculated using Theorem 3.2 which gives p(N-1-m) 6 0(N-1)*(N-1-m)/(N-1). The performance of the SIB technique is now illustrated with an example, comparing the level three SI bounds with the level four PBH bounds. In addition, a comparison is made with the bounds developed by Kriz: the formulae used here are those recommended by Kriz, and use equation 26(a) in [7] for the upper bound on cycle time (this is the BJ bound since there are no delay servers), and the tighter of the bounds computed using equations 26(b) and 27 in [7], for the lower bound on cycle time. Table 3.1 tabulates the results. It is seen here that the SIB technique compares favorably with the other techniques. Example 3-1: This is the example presented in [4] to illustrate the PBH technique. There are 50 nodes with loadings as follows: 1 node at 20/417, 2 at 19/417, 5 at 18/417, 5 at 15/417, 5 at 10/417, 8 at 7/417, 8 at 5/417, 8 at 4/417, and 8 at 2/417. All nodes are single server fixed rate nodes. Table 3.1 presents the upper and lower bounds obtained using the SIB technique (SI up, SI dn), the PBH technique (PB up, PB dn), and the bounds obtained by Kriz (Kr up, Kr dn), at various population levels. 17

N SI up PB up KR up Exact KR dn PB dn SI dn 10 1.279 1.280 1.432 1.278 1.180 1.278 1.278 20 1.632 1.639 1.911 1.619 1.380 1.615 1.616 40 2.4543 2.467 2.871 2.376 1.931 2.337 2.346 60 3.349 3.364 3.830 3.197 2.882 3.090 3.106 80 4.274 4.288 4.789 4.057 3.839 3.859 3.878 Table 3-1 Bounds on cycle time for example 3.1 The bounds were computed for population values from 1 to a 100. The total time taken by the SIB and PBH techniques, (including computation of S2, S3 and S4) for obtaining these bounds at these populations, were measured. The calculations were made using an AMDAHL 5860 system running MTS. The SIB technique took a total of 6 milliseconds to obtain the bounds. The PBH technique took 15 milliseconds. In order to avoid unnecessary computation and any overheads in operation, the SIB formulae, as also the PBH formulae given by (3.27) were implemented without the use of recursion. These times appear to conform with the analysis of operation counts which is made in section 4. 3.2 Terminal Driven Systems: When interactive systems are modeled by queueing networks, typically a delay node is used to represent the time spent by users thinking between interactions with the system. The average think time is represented here as Lo, the load at the delay node. The BJB formulae here are not as simple as for the case with no delay nodes, and require an additional 0(N) computation. The PBH technique develops a hierarchy of bounds for terminal driven systems. Bounds are also developed by Kriz for terminal driven systems. SIB has a direct extension for terminal driven systems: consider the equation for mean queue lengths at the nodes. When a delay center is present, this can be written as 18

1 + Qm(N-1) -(N) ~ NL- ------------ -- ------ Qm(N) NLm Lo + (Ln + LnQ(N-1)) n 1 + Qm(N-1) NPm ( —- -----— ), (3.24) 1 + lPnQn(N-1) M where Pm = Lm/(Lo + L), and L = I Lm m=1 Comparing equations (3.24) and (2.5), it is seen that all the bounds we had derived earlier would apply here too, if we replace every occurrence of pm by pm, for m = 1,...,M, and replace the Si terms by Si = I pmi No additional operations are needed here. Example 3.2 compares the performance of the level 3 SIB technique with the level 4 PBH technique and the Kriz bounds. Example 3.2: This is the same example as given in [4] to demonstrate PBH for networks with delay nodes. The network is basically the same as example 3.1 with an additional delay node with a load of 4000/417. Table 3.2 shows upper and lower cycle time bounds at various population levels. The exact cycle times are also given. N SIB PBH Kriz Exact Kriz PBH SIB3B up up up Down Down Down 20 10.648 10.648 10.686 10.648 10.611 10.648 10. 648 40 10.716 10.720 10.802 10.715 10.652 10.715 10.715 80 10.885 10.959 11.110 10.883 10.744 10.880 10.882 120 11.132 11.418 11.566 11.118 10.851 10.096 11.104 160 11.525 12.156 12.244 11.466 10.976 11.376 11.396 200 12.196 13.162 13.202 12.004 11.123 11.731 11.764 Table 3.2: Bounds on cycle times for example 3.2 19

The bounds were computed for a range of population values from 1 to 200, and the total time taken by the SIB and PBH techniques when run on the AMDAHL 5860 machine, were compared. The SIB technique took 14 milliseconds to obtain the bounds, while the PBH technique took 37 milliseconds to obtain the bounds. It can be observed that the level 3 upper bound of the SIB technique gives noticeably better results than the other two techniques in this case. 4. Computational Effort: The bounding technique outlined above produces a sequence of increasingly tighter bounds. The computational effort required to produce these bounds is, further, usually less than that required of the PBH bounds. To illustrate this point, we analyze the number of operations required by both techniques. Suppose we compare the level three SI bounds with the level four PBH bounds. Both techniques, here, require computation of the terms upto S4 as an initial step. Given that these terms have been computed, for each population level, N, the number of arithmetic operations for the two techniques are as follows: (a) The SIB technique requires about 14 operations to compute a level one upper bound on DN_3 (refer equation 3.18), which is used for both the upper and the lower bounds on DN_1. Assuming that (i) the square root operation counts as one operation, and (ii) given N, evaluating N-i for any i > 0 counts as one operation, the upper bound on 4(N-1) then requires about 27 additional operations, (refer equation 3.22) and the lower bound about 22 additional operations (refer equation 3.23) for a total of about 63 operations. (b) The PBH technique proceeds as follows: the level i PBH upper or lower bound on the cycle time is given by f(i,1,N), where f(j-1, p+1, N-1) f(j,p,N) = Sp + (N-l) -—.. —-----, (4.1) Lo + f(j-1, 1, N-1) 20

with some boundary conditions when j=O in both cases. (It may be noted that computing a level i PBH bound on cycle time at population N requries computation of a level i-1 PBH bound at N-2, and so on upto a level 1 PBH bound at population N-i+1). A level i PBH bound requires (i+1) (i+2)/2 function evaluations of the form given by (4.1) for each of the upper and lower bounds at each population value. Of these, i+1 evaluations are at the boundary condition which requires only about 3 arithmetic operations. All other function evaluations require about 4 arithmetic operations at least when delay nodes are present, as can be seen from equation (4.1). This does not however, include the operations necessary to index into the array f, in order to evaluate f(j,p,n). For example, to compute f(j,p,n), it is required to set the indices j-1, p+1, and N-1 to determine the location of the desired functions f(j-1, p+1, N-1) and f(j-1, 1, N-). Hence, the calculation of the level four bounds requires about 10x4 + 5x3 = 55 operations for each upper and lower bound, for a total of about 110 operations per population value without considering these indexing operations. Thus, the PBH level four bounds require about twice as many arithmetic operations as the SI level three bounds do, even if the indexing operations, as described above, are disregarded in calculating the bounds. (If the setting of the indices are considered, each function evaluation other than those at the boundary condition, requires about 3 additional operations). Further, the PBH bounds require computation which increase as the square of the level. The SI bounds at higher levels require, on the other hand, about 10 additional operations in total for each additional level (plus some one time operations to calculate the required a terms). It is noted, though, that while the SI bounds are thus more efficient to compute than the PBH bounds, the sequence of PBH bounds ultimately converge to the exact solution while the SI bounds, as described above, do not. 21

5. An alternate set of lower bounds: In this section, an alternate means of obtaining a sequence of lower bounds is presented. These bounds require additional computational effort compared to those presented in section 3. The effectiveness of these bounds are demonstrated with a few examples. From equations (3.8) and (3.12), and using equation (3.7) to set AK,i = XK AK-1,i-1 ~i+1 i a-i+1 D 1 + KS2 + E (K-j)aj AK 1 + --- Y A j=1 at = 1 + KS2 + I (K-j)aj AK j- + - AK Y i K-i- 1 AKi (5.1) j=1 CLi From equation (3.8a), with K-1 in place of K, and i-1 in place of i, we get for K > i > 1, i-1 ^K-1,i-1 Y(K-i-1) = DK1 - 1 - - (K-j-1)aj AK-_1j-1 (5.2) j=0 So, from (5.1) and (5.2), for K > i > O, i a^i+1 i-1 DK a 1 + KS2 + I (K-j)ai AK,j-1 + --- XK [DK-1 1 I (K-j-1)aj AK..lj. (5.3) j=1 CLt j=0 In the right hand side of (5.3), since the term in the square bracket is nonnegative for all values of i, it can contribute to a tighter lower bound on DK. Since XK DK-1 = K, we can rewrite (5.3) after some elementary algebra as i. i i-1 i-1 Ci+l DK > 1 + K(ao + 1 j+) - (K-j-) - -; i > 0. (5.4) aLi j=0 ai ai Noting, from Corollary 3.1, that the term (ai+l/ai)aj > aj+l for j < i, the bounds are obtained now by suitably bounding the terms AK and AK,j. To illustrate, the level 3 bound is obtained as follows: Equation (5.4) with i=1 gives 22

a2 a2a 0a2 DK a 1 + K(ao + -— ) - (K-1) ( —- - A )K A --.K. (5.5) a11 0a1 a1 Thus, setting XN-1 = (N-1)/DN-2, a level 3 lower bound on DN_1 (and hence W(N)) is given by a2 (N-1) a2 a a2 DN.1 1 + (N-1)(ao + — ) - ---- [(N-2)( —-- - a) + -].(5.6) a1 DN-2 a1 a1 Equation (5.6) can use a level 3 SI bound or a level 4 PBH lower bound on DN2. We now present a few examples which compare the lower bound obtained using equations (5.4) with the PBH lower bound and the bound obtained using the formulae given by Kriz[7]. The bound obtained by the Asymptotic Bound Analysis (ABA) is also presented for comparison. In the following examples, the bound obtained using (5.4) is termed SIB-nA, where n is the level. This equation is used in conjunction with the PBH technique to illustrate the effect of a hybrid of the two techniques as follows: As we remarked earlier, computing a level n PBH bound at population K in turn computes a level n-1 PBH bound at population K-1, a level n-2 PBH bound at population K-2, and so on till a level 1 PBH bound at population K-n+1. Now, suppose we wish to compute the SIB-nA lower bound on DK. For this we would compute the Sj terms for j=2,..,n+1. With these Sj terms, we can compute a level n+1 PBH upper bound on AK, and this in turn would directly obtain PBH upper bounds on the terms XK1i,., AK_.n Some of these bounds may now be used in equation (5.4) to obtain the SIB-nA lower bound. (The use of equation (5.4) in this manner could also be interpreted as a possible extension of the PBH technique.) Example 5.1: Example 3.1 is now reworked to illustrate SIB-3A. Table 5.1 shows the comparisons at various population levels. 23

N Exact SIB-3A PBH Level 4 Kriz ABA 10 1.278 1.278 1.278 1.180 1.000 20 1.619 1.617 1.615 1.380 1.000 40 2.376 2.354 2.337 1.931 1.91 8 60 3.197 3.130 3.090 2.882 2.878 80 4.057 3.920 3.859 3.839 3.836 90 4. 497 4.324 4.246 4.315 4.31 4 Table 5.1 Lower Bounds on DN-1 for example 5.1. Example 5.2 There are 25 nodes in this example with loads as follows: 1 at 40/575, 2 at 35/575, 3 at 30/575, 5 at 25/575, 5 at 20/575, 5 at 18/575, and 4 at 15/575. The level 5 SI bound based on equation (5.6) (termed SIB-5A) and the level 6 PBH bound is used here. The comparisons are made in Table 5.2. N Exact SIB-5A PBH Level 6 Kriz ABA 10 1.404 1.404 1.404 1.360 1.000 20 1.886 1.885 1.883 1.760 1.391 30 2.408 2.396 3.389 2.089 2.087 40 2.974 2.930 2.913 2.783 2.783 50 3.581 3.479 3. 450 3.478 3.478 Table 5.2: Lower Bounds on DN-. for example 5.2 Example 5.3: There are 15 nodes in this example with loads as follows: 1 node at 20/1 92, 2 at 18/1 92, 2 at 17/1 92, 2 at 15/1 92, 2 at 14/1 92, 2 at 10/1 92, 2 at 7/192, and 2 at 5/192. Table 5.3 tabulates the results. The level 3 SI bound based on equation 5.6, and the level 4 PBH bound is used here. 24

N Exact SIB-3A PBH Level 4 Kriz ABA 10 1.716 1.715 1.714 1.60 1.042 20 2.568 2.556 2.546 2.267 2.083 30 3.463 3.416 3.393 3.1 34 3.125 40 4.392 4.286 4.247 4.170 4.167 50 5.351 5.208 5.208 5.209 5.208 Table 3.3: Lower Bounds on DN_1 for Example 3.3 It may be noted from these examples that the Kriz bounds obtained are usually just a little better than the ABA bounds. 6. Conclusion: A new means of obtaining bounds for closed single chain, separable networks has been developed. These are successively improving bounds in the sense that increasingly tighter bounds can be obtained, although at the expense of increased computation. These bounds are termed as bounds of increasing levels. The bounds obtained are computationally efficient. The SI bounds were compared with those obtained by other techniques through a number of examples to illustrate the effectiveness of the SIB technique. It was shown that for networks without delay nodes, the bounds at lower levels produced by the SIB technique are tighter than those obtained by the PBH technique with about the same degree of computational effort. At higher levels, the SIB technique requires much less computational effort than the PBH technique to obtain bounds. (although it may not produce comparable bounds at higher levels as it does not approach the exact solution.) Finally, in section 5, it was indicated how the SIB and the PBH technique could be used in conjunction to obtain lower bounds on the cycle times. These cycle time bounds appear to be better than the bounds obtained by either of the techniques in isolation. 25

Appendix A Proof of Lemma 3.1: Lemma 3.1: Consider the function fl(K) as defined by equation 3.2. Let fi(K)={f1(K)}, and p=pm}, m = 1,...,M. Then, for i, K > O, (a) fi(K) (PC) p, (Al) (b) Yi(K) = Pm fm(K) 0 (A2) m Proof: Proof by induction on i. For clarity we drop the subscript K since this will not affect the proof. For i=O, the proof is obvious since fm = Qm. Assume that for some i > 1, fJ(PC)p, j = 1,...,i, and Yi = I Pmf m In other words, > f... f f1 S 0, for some 1 < k < M. Hence there M- k k' 11k-1 1 exists a number kl > k such that; f... fk > m l > * f > 0; fI l (A3) Mki = m m < k O k-l. 0 Lemma 2.1 shows that Pfm > Pm p P mfi m m n Hence, yi+1 1 = pm2 (f -i Pnf) > 0. m m n Also, from (A3), it is clear that PM(fM - yi) >... > Pkl(fkl) > 0, i.e., fi+l >... > fk~+l O; and hence fi+1(PC) p. o 26

Appendix B Proof of Lemma 3.2: Lemma 3.2: The term fm(K) can be recursively defined, for i > 0, k a 1, as i+1 fm(K) = K fm(1) + AK m (K-1), (B1) and hence Y(K) I pmfm(K) = K ai + AK yi+l (K-1), K 1, (B2) m where ai = Yi(1) > O. Proof: Proof by induction on i. For i = 0, the proof is obvious from equations (2.7) and (3.1) (note that Y~(K) = 4(K)). Assume that the result holds for some i > 1. We need to show the result holds for i + 1. From equation 3.2, m+l (K) pm ( f(K) pnf(K))'m - m - Pnfn n Using (B1) to substitute for fi(K) and fi(K) yields to substitute for I n mnn fil(K) pm[f~1 - A K nf1( K)K f n ( (1) + (K f k n = Kpm(fmi(1) - i + X ( (K-l) i+l(-1 + K Pm (fm (K - nf (K-1)), n and hence, from equation (3.2), fm+ (K) = K f'+1(1) + Ak f(K-l). (B3) Further, from (B3), yi+l (K) i ) pmfmi+1(K) = K yi() + AK yi+2 (K-1). o m 27

Appendix C Proof of Theorem 3.3 Theorem 3.3 yj+l(k)aj 2 YJ(k) aj+1; j,k>O Proof: Proof by induction on k: For k = 1, the result is obvious, since Y(1) = aj Assume the result holds for same k-1. Pmfmj1+(k-1)aj - Pmfmj(k-1)aj+l O. m Hence, from equation (3.3), Yj+l (k)aO - Yj (k)aj+ 1 +lPmfm (k)aOj - Pmfm (k)aj+1 m m'+1~pl 2'+1 yj+l mn Dk1 m k - kpmfmj(1)a j+l ---- aj (pm2fm(k -1) - (k-1) ) m D0k-1 m =- - --- ['Pm 1 i(k-1) - Y3(k-1 )j )...... [)IPm2(fmjO'( - fmiJk+1l)aj+ -S2 Pm(fm (+l(kk-)j 1 fm(k J k-l) j+ )] m k.-.. [pm(g(k- l) - Pnn(k-l1 ))] Dk1 m n where gim(k-1) fmjl(k-l)aj - fmi(k-1)aj+ (C). If we can show gi(k)(PC)p for all k, where gj = {g J, m=1,...,M, we are done. 28

Note that from equations (3.2b) and (C1), g(k-1) = pm(fm(k-) - Y(k-1))aj f(k-1)aj,+ (j +1 = ajPm[f(k-1)(1 - ) - Y(k-1) ). Pmj Also, since pngnJ(k-1) a 0 by inductive assumption, at least one of the gm s a 0. n It is known that fJ(PC)p. Here, if for any two nodes m, n, we have both fi f 0, O then pm 2 pn implies fmi3 fn. This in turn implies that mj fn1j fmJ(k-1) (1..J. ) fnJ (k-1) (1 -.J. ). Pmaj Pnaj Hence if there are nodes m1, n1, such that g1(k-1) a 0, and gJl(k-1) a O, then pm Pnl implies gm1(k-1) > g91(k-1). Thus, gJ(k) (PC) p, and we are done. 29

Appendix D Proof of Theorem 3.5: Theorem 3.5: The level n upper bound on 4(N-l) is given, for N-1 > n, by 0.5 4U(N-1) = --- (T1 + T2(n)), (D1) n where T1 = (N-2)pu -, (Dla) T2 = SQRT (T12 + 4(N-2)(S2 - a(N-1,n-1))), (D1b) i j-1 N-2-m o(N-l,i) = I (PuSj+i-Sj+2) n ------ (Dic) j=1 m=-O DN3 with DN_3 being a level one upper bound on DN_3. Proof: We can express the term m pmQm(N-2) from equation (2.9) as ) Pm Qm(N-2) = pu(N-2) - (pp Pm p)Qm(K), m m and using equation (3.1) repeatedly, this gives I p2 Q (N-2) = pu (N-2) - (PS2-S3) (- p-2 PPm PmQm(N 3) m m - pu(N-2) - XAN2(PuS2-S3) - XN_2AN_3(PuS3-S) - AN-2N-3 (PuPm-P) PmQm(N-4), m and so on to get i Pm Qm(N-2) a pu(N-2) - (PuSj+lSj+2) AN2,1 i N-2. (D2) m j=1 Hence, from equations (2.8) (2.9) and (3.7), noting that for k > O, Xk = k/Dk-1' (N-1) i j-1 N-2-m )(N-1) 5 (N-1)S2 + ---— ( (pu-S2) ((N-2) - I (PuSj+lSj+2) ---- ). DN-2 j=1 m-O DN-m-3 Since ((N-2)/DN_2. nfl(N-1)/(l+nT((N-1)), (n is given by equation (3.17)), 30

n 4(N-1) 4(N-1) I (N-1)S2 + (N-l)(pU-S2) --------- 1 +nT(N-1) N-1 i j-1 N-2-m - (PuSj+1-Sj+2) n --—. DN-2 j=1 m=O DN-m-3 Since DN_2 = 1 + O(N-2) 5 1 + nT(N-1), and DNm_3 N DN_3 for m>O, we can write n ((N-1) N-1 4(N-1) < (N-1)S2 + (N-1)(PU-S2) -------- - -------- o(N-1,i), (D3) l+n((N-1) l+n((N-1) where i j-1 N-2-m o(N-l,i) = I (PuSj+l-Sj+2) H ------ (D) j=1 m=O DN_3 Equation (D3) is a quadratic in 4(N-1) if we replace DN_3 in (D4) by its level one upper bound. 0 Since the terms (DuSi+l-Si+2), i 2 0, are all non-negative, o(N-1,i) is an increasing function of i and hence bounds of higher levels areincreasingly tighter. 31

Appendix E Proof of Theorem 3.6: Theorem 3.6: The level n lower bound on p(K) is given, for K > n, by ln(K) - (T1 + T2(n))/2n, (El) where T1 = ((K-1)S2 - 1), (Ela) T2(n) = SQRT(T12 + 4(K-1)(S2 + (K-1)B(K,n-1), (Elb) and a(K,i) - 0; i=0, i-1 j K-m i K-m Oi (K-i-1) B(K,i) - I aj n ---- + a ( _ —-) (1 + ---- -------— ); i>o, (Elc) j=1 m=2 DKm m=2 DKm ai_1 l+(K-i-1)ao and DKm is a suitably chosen upper bound on DK_mProof: A bound on the term DK as given by (3.15) is 1i K-i-l a2 DK a 1 + KS2 + I (K-j)aij AK,j-1 + (K-i) AK,i-l ( —--------- -. (E2) J~1 -'J tl' 1+(K-i-1)ao.i_1 The term (K-j)AK _1 in the above equation is rewritten as follows: j-1 j-1 (K-j)AKj-1 = (K-j) I XK-n = (K-j) I ( K-n)/DKn n=0 n-O j-1 j = K In (K-n-1)/DKn_1 = K II (K-m)/DKm. n=0 m=l K(K-1) j K-m DK_1 m=2 DK-m Hence, from equation (E2) and (3.10), K(K-1) i j K-m rn (K-i-l) i K-m 4(K) > KS2 + ----— ( j 11 -- + ---- ------- - 11 ) DK-l j1 m=2 DK-m ai-l 1 +(K-i-1)ao m-2 DKm 32

K(K-1) a KS2 + ----- (K,i), (E3) 1 +((K-1)/K)+(K) where i-1 j K-m i K-m t (K-i-1) e(K,i) = I a n1 --- + a ( ) (1 -- ------- -). (E4) j=1 rm=2 DKm m=2 DKrm Oci-1 1+(K-i-1)ao and DK_m is a suitably chosen upper bound on DK_m. Equation (E3) is a quadratic in ~(K) whose solution gives the desired result. 33

Appendix F Proof of Corollary 3.3: Corollary 3.3: For networks without delay nodes, the level two lower SI bound on DN_1 is tighter than the level three PBH bound on DN_1 for N>3. Proof: Let 1l(N-1) denote the level two lower SI bound on <(N-1) and el(-1) denote the corresponding level three lower PBH bound. From equation (3.15) with i=1, setting K=N-1, we get (N-2)(N-3)a2/ao 4(N-1) > (N-1)S2 + XN1(N-2)a1 + XN-1...., 1+(N-3)S2 and using Theorem 3.2 this gives, with n=(N-2)/(N-1), (N-1)(N-2)aI (N-3)a,/S2 p(N-1) a (N-1)S2 + --------- ( 1 + -----—.- ). (F1) 1n +Tj(N-1) 1+(N-3)S2 The solution to this quadratic in O(N-1) gives the bound l(N-1). For notational ease, we omit the argument (N-1) on 42 and 91 to get (N-1)(N-2)c1 (N-3)a1/S2 2 = (N-1)S - + ----—. — ) (F2) 1+n s3 1+(N-3)S2 The PBH bound is given from section (3.2) of [4] as S2 + (N-2)S3 e = (N-1) ( -------- ) (F3) 1+(N-2)S2 We now prove that 4l > 41 by contradiction. Suppose that l < O1. Then from (F2), this implies that (N-1)(N-2) a1 (N-3) a1/S2 e4 > 41 > (N-1)S2 + -- - (1 + ---- ), (F4) 1 + n1f 1 + (N-3)S2 Equation (F3) can be rewritten after some elementary algebra, as 34

(N-1)(N-2)a1 81 = (N-1)S2 + ---------- (F5) 1+(N-2)S2 From equations (F4) and (F5), we get (N-1)(N-2)a1 (N-1)(N-2)aa1 (N-3) a/S2 (N-1)S2 + --------- - (N-) S1 + ----- + ) 1+(N-2)S2 1 + n 01 1+(N-3)S2 and cancelling out common items, we get 1 1 (N-3)a1/S2 __._ >I ------ ( 1 + ----—.. ) (F6) 1+(N-2)S2 1+nol 1+(N-3)S2 Expressing e1 in equation (F6) using equation (F5), and after some straight forward manipulation, this gives the inequality (N-3) (N-2)2 > ---- + 2(N-3)(N-2). (F7) S2 This last inequality is clearly a contradiction for N > 4, and hence the result follows. 03 35

REFERENCES 1. BUZEN, J.P., "Computational algorithms for closed queueing networks with exponential servers", Communications of the ACM, V. 16, No. 9, pp. 527-531. 2. DENNING, P.J., and BUZEN, J.P., "The operational analysis of queueing network models", Computing Surveys, v 10, 3, September, 1978, pp. 225-262. 3. DOWDY, L.W., PEREZ-DAVILA, A., and STEPHENS, L.E., "Performance bounds based upon throughput curve properties", Performance 1983, North Holland Publishing Company, pp. 285-294. 4. EAGER, D.L., and SEVCIK, K.L., "Performance bound hierarchies for queueing networks", ACM TOCS, vol. 1, No. 2, May 1983, pp. 99-115. 5. EAGER, D.L., and SEVCIK, K.C., "Bound hierarchies for multiple class queueing networks", J. ACM, v 33, no 1, pp. 179-206. 6. KEROLA, T., "The composite bound method for computing throughput bounds in multiple class environments", Technical Report CSD-TR4 75, Department of Computer Sciences, Purdue University, W. Lafayette, 1985. 7. KRIZ, J., "throughput bounds for closed queueing networks", Performance evaluation, v. 4, 1984, pp. 1-10. 8. LITTLE, J.D.C., "A proof of the queueing formula L = KW". Operations Research, 9, 1961, pp. 383-387. 9. REISER, M., and LAVENBERG, S.S., "Mean value analysis of closed multichain queueing networks", J. ACM, 27, 2, April 1980, pp. 313-322. 10. SHANTHIKUMAR, J.G., and YAO, D.D., "Throughput bounds for closed queueing networks with queue-dependent service rates", July 1985. 11. SRINIVASAN, M.M., "Approximate measures of performance for queueing network models and their application to the file assignment problem", Ph.D. thesis, Northwestern University, 1985. 12. SRINIVASAN, M.M., "On extending the scope of a bounding technique for closed queueing networks", Technical report 85-25, Industrial and Operations Engineering Department, The University of Michigan, Ann Arbor, 1985. 13. STEPHENS, L.E., and DOWDY, L.W., "Convolutional bound hierarchies", Performance Evaluation Review, Proceedings of the 1984 Sigmetrics Conference on Measurement and Modelling of Computer Systems, pp. 120-133. 14. SURI, R., "Generalized quick bounds for performance of queueing networks", Computer Performance, vol. 5 No. 2, June 1984, pp. 116-120. 15. ZAHORJAN, J. SEVCIK, K.C., EAGER, D.L., and GALLER, B., "Balanced job bound analysis of queueing networks", C. ACM, 25, 2, February 1982, pp. 134-141. 36