An approximation for mean waiting times in cyclic server systems with non-exhaustive service M. M. Srinivasan Department of Industrial and Operations Engineering The University of Michigan, Ann Arbor 48109-2117 Technical Report 86-36 September 1986 Revised May 1987 This research was supported in part by a fellowship from the Rackham Graduate School, The University of Michigan, Ann Arbor.

An approximation for mean waiting times in cyclic server systems with non-exhaustive service Abstract The cyclic server system has been the subject of considerable research over the last few years. Interest in analyzing such systems has gained momentum due to their application in the performance analysis of token ring networks. In this paper, we consider cyclic server systems with the non-exhaustive service discipline. The performance measures of interest here are the mean waiting times at the nodes in the system. Exact analysis of such systems for these performance measures is very difficult in general, and a number of approximation schemes have been proposed in the past to evaluate these quantities. This paper presents a new approximation technique that gives accurate estimates of these mean waiting times, based on extensive validation with simulations.

1. Introduction: A cyclic server system is a system in which a single server attends, in a cyclic manner, to a number of centers (nodes) at which requests arrive, and queue up for service. The number of requests serviced at a node, during a visit there by the server, depends on the service discipline that the server adopts. The service disciplines that are typically modeled are the exhaustive, the gated, and the non-exhaustive service disciplines (Watson 1984). When the server departs from a node, he can take a finite amount of time to switch to the next node, and this is termed the switchover time. Interest in the analysis of such systems for their performance has gained considerable momentum recently, especially owing to their direct application in the modeling and analysis of token ring networks. In modeling such ring networks, the token is modeled as the single server, and the packets that are generated by the nodes, for transmission to other nodes, are the requests for service from the system. When the bandwidth is constant, the size of the packet determines the service time required to transmit it. The overhead involved in buffering data and switching control from one node to the next, and the propagation delay, together constitute the switchover time between nodes. Some typical performance measures of interest here are the mean waiting time for a request, and the distribution of the cycle time (the time required to make one complete scan of the system). In this paper, we consider systems with the non-exhaustive service discipline where, at most one request is attended to by the server during a visit to a node. This discipline has been widely adopted in the implementation of token ring networks, due to its perceived fairness. Requests are assumed here to arrive at the nodes according to independent Poisson processes and it is assumed that there is unlimited waiting room at each node to hold these requests. It is also assumed that in each cycle the server visits each node exactly once. If the server finds no requests at a node when he visits it, it is assumed that he immediately begins to switch over to the next node. The analysis of such systems presents considerable difficulties; in general, the exact analysis for even the mean waiting times in systems with more than two nodes is unknown at present, and a number of approximate analytical schemes have been proposed in the past for obtaining these mean waiting times. In this paper, a new approximation technique, termed Myopic Analysis of Cyclic Non-Exhaustive Service 1

Systems (MACNESS) is presented. This approximation technique appears to be very effective in obtaining estimates of the mean waiting times, in comparison with techniques previously reported. 2. Previous work on cyclic server systems: The seminal work on the analysis of cyclic server systems is due to Cooper (1969, 1970), who considered systems with exhaustive and gated service disciplines, and without switchover times. Following the work of Cooper, a number of papers have presented both exact and approximate analyses for systems with the exhaustive and gated service disciplines. Bux (1981) reports exact results for the system in which all nodes have identical arrival patterns, service time distributions, and switchover times (the symmetric system). Ferguson and Aminetzah (1985) present exact results for non-symmetric cyclic server systems (namely, systems where the arrival rates and the service time distributions at each node as also the distributions of switchover times can all be different). Simple, approximate analytical models for non-symmetric systems have been proposed by Bux and Truong (1983) and Carsten et al. (1977) 2.1 Previous work on cyclic server systems with non-exhaustive service: The analysis of systems using the non-exhaustive service discipline, however, presents considerable difficulties. A complete analysis of the system with two nodes, without switchover times has been presented by Eisenberg (1979); and the system with two nodes with switchover times, but with identical characteristics, has been analyzed by Boxma (1984). These require a complex analysis of Riemann-Hilbert boundary value problems, and even for the mean waiting times, no simple expression results. For the symmetric case, a simple closed form expression for the mean waiting times has been obtained (Watson (1984), Takagi (1985), Fuhrmann (1985)). In addition, a conservation law exists for such systems (Watson 1984), which presents one equation for a weighted sum of the mean waiting times in terms of known data parameters. Since the exact analysis of such systems appears extremely difficult in general, a number of approximation techniques have been proposed in the past, for obtaining these mean waiting times. These approximations are usually validated through extensive simulations. 2

A notable contribution towards approximate analysis of cyclic server systems with non-exhaustive service is the work of Kuehn (1979) who considered systems with batch Poisson input. The analysis obtained the generating function of the stationary state probabilities, the Laplace-Stieltjes transforms of the delay distributions, and the mean waiting times at each node, i, in the system. To obtain these estimates, two conditional cycle times were considered: a cycle time which included a service at node i, and a cycle time which had no service at node i. The variance of each of these cycle times was then approximated assuming that in either of these cycles, the sojourn time at each node was independent of the sojourn times at the other nodes (the independence assumption). An imbedded Markov chain approach was then used to obtain the desired estimates. In addition, a stability criterion was derived for general GI/G/1 systems with cyclic priority service. Following the work of Kuehn, a number of papers have reported approximate analytical results for such networks (Berry and Chandy (1985), Boxma and Meister (1986), Rego (1986) and Kimura and Takahashi (1986)). The paper by Berry and Chandy (1985) requires identical distributions for the service times at all nodes. Arrivals at individual nodes are assumed to be Poisson. The switchover time is assumed to be a small constant, and is the same for each pair of nodes. With these assumptions, the approximation technique then views the entire system as a single M/G/1 queue with an arrival rate set equal to the sum of the arrival rates over all nodes. It calculates the overall mean queue length in this M/G/1 system, and then allocates this quantity among the nodes using an iterative heuristic that is developed in the paper. A simple application of Little's rule (Little (1961)), then provides the mean waiting times at these nodes. Kimura and Takahashi (1986) present a diffusion approximation to analyze systems in which each node can be subject to batch arrivals having arbitrary distributions. The analysis considers conditional cycle times, and uses the independence assumption on these conditional cycle times in a manner similar to Kuehn's analysis. For the special case where the arrivals are Poisson, the mean waiting times obtained by this analysis are very close to the values obtained by the method of Kuehn. 3

Boxma and Meister (1986) consider a non-symmetric system with Poisson arrivals at each node. The approximation makes use of the conservation law presented by Watson (1984), and obtains a closed form expression for the mean waiting times in systems with switchover times. This approximation appears to provide the most accurate estimates for the mean waiting times among the techniques reported in the past. A similar result for systems without switchover times is presented in Boxma and Meister (1987). 3. The analysis: vTdt A t hoAeo Let N denote the number of nodes in the cyclic server system. Requests for service at node n in this system, arrive according to an independent Poisson process with rate Xn. The service time demand of a request at node n is assumed to be an independent, identically distributed random variable with mean bn, and second moment bn(2). The switchover time between node n and node (n mod N) + 1 is an independent, identically distributed random variable with mean sn, and second moment sn(2). The utilization of the server at node n, pn, is defined as Pn = Xn bn. In the ensuing discussion, unless otherwise specified, the index for any summation is assumed to be over the range 1 through N. Let S = Sn, n and P = Pn n The expected cycle time, c, is obtained from (Kuehn 1979) C = Sn + Pn c, (3.1) n n from which, c = (3.2) It can be shown (Kuehn 1979) that the following conditions are necessary and sufficient for the stability of this system: 4

p < 1, (3.3a) and max Xn c < 1. (3.3b) n It is assumed that the system being analyzed satisfies the above stability conditions. To motivate the analysis consider, first, the cyclic server system with just one node. This corresponds to an M/G/1 vacation system wherein the server takes a vacation following each visit to the node. Assuming that the distribution of the vacation time is known, and is independent of the time spent at the node, a technique is presented which obtains the exact mean waiting time experienced by a request at this node. This technique is then extended in a direct manner to obtain mean waiting time estimates for the general system with N nodes: let wn denote the mean waiting time at node n. To obtain the wn's, each node in the system is considered in isolation as a single node, single server system with vacations. 3.1 The analysis for a system with one node: For this case, we drop the subscript on the parameters. Thus, we let s denote the mean vacation time, and s(2) denote the second moment of the vacation. Consider a tagged request (customer) that arrives to the system. Let p(i) denote the probability that the arriving customer sees i customer already in the system. Owing to the fact that Poisson arrivals see time averages (Wolff 1982), this tagged customer sees the equilibrium distribution of customers present at the node. Let f denote the fraction of time that the server is away from the node, on a vacation. Since the utilization of the server at the node is given by p, it can be seen that f = 1-p. In this system, the server immediately begins a new vacation if he finds no customer present at the node when he visits it. Hence, he is away on vacation at least p(O) of the time, on the average. Let x denote the fraction of the time that the server is away on vacation, given at least one customer is present at the node. Then it is clear that the fraction of time that the server is away from the node can also be written as 5

f = p(O) + (1- p(O)) x. Equating the two expressions for f, 1- - p(O) x = 1 - p(0) (3.4) Let t denote the mean system time (mean waiting time + mean service time) for this tagged customer and let t(i) represent the mean time in the system for this customer, conditioned on the fact that it@ sees i customers on arrival. Thus, w+b = t = p(i)t(i). (3.5) i Consider the case where the arriving customer found the system empty. In this case, the server has to be on vacation, and the customer interrupts a special vacation which has an expected residual life (Kleinrock (1975)) of s(2)/2s. In this case, the expected time in the system for the customer is given by s(2)/2s + b. Suppose, on the other hand, that the tagged customer found i > 0 customers already present in the system on arrival. In this case, we choose to identify the customer at the head of this queue as the Head-Of-Line (HOL) customer. The expected amount of time it spends in the systerh is then the sum of two quantities: (i) the expected time, r, until the HOL customer departs the system, and (ii) the expected time for the server to complete service on the i-1 remaining customers, followed by a service on the tagged customer, namely to complete i successive cycles, each of which includes a service at the node. To determine r, we consider two possible situations: (a) The customer found the server on vacation: the fraction of time this occurs is, on the average, x. In this case, the customer interrupts a special vacation which has an expected residual life of s(2)/2s. This implies that the expected time till the departure of the customer at the head of the line is s(2)/2s + b. (b) The arriving customer found the server servicing the HOL customer: the fraction of time this occurs is, on the average, (1-x). The expected time till the departure of the HOL customer here is just the expected residual life of this special service time which is equal to b(2)/2b. @ The neuter gender will be used to describe the customer, in order to distinguish it from the server. 6

Hence, t( s(2) b( W\ r = x 2s + b + (1-x) (-) (3.6) Thus, the values for t(i) are: s(2) t(i) = + b, i =0, (3.7a) t(i) = x — + b + (1-x) -b) + i(s+ b), i > 0. (3.7b) From equations 3.4, 3.5, and 3.7, w + b = 2s + b (p(O) + x(l-p(0)) + 2b (l-x)(l-p(O)) + (v+b)X i p(i). (3.8) Note that from Little's rule (Little (1961)) we can set I i p(i) = X (w + b). i Using this in equation 3.8, we obtain the following result which we state as Lemma 1: The mean waiting time, w, in a single node, single server, vacation system is given by the expression w (1 - (s+b)) = p 2 + (l-p) (2s) + s. (3.9) This expression for w is exact. The above approach is now extended to obtain the mean waiting times in a system with N > 1 nodes. 3.2 The analysis for general cyclic server systems: The approximate analysis for the general case, MACNESS, proceeds as follows: to estimate the mean waiting time at any node, the system is viewed, myopically, as a single node system with vacations. When the server departs from a 7

node, the vacation, from the point of view of this node, is now due to the time spent by the server at all the other nodes as well as the switchover times between the nodes. Consider the mean waiting time experienced by a tagged customer arriving to a node n, 1 < n < N. Following the approach of the previous sub-section, let pn(i) denote the probability that the tagged customer at node n finds i customers already present at this node. As before, two cases are considered: where i=0, and where i > 0. If the tagged customer finds i=0 customers at node n on arrival, then it always sees the server on vacation from that node and interrupts this vacation. Let vn denote the expected residual life of this interrupted vacation. Thus this arrival would spend, on the average, vn + bn units of time in the system, with probability p,(O). Suppose, on the other hand, that the tagged customer finds i > 0 customers at node n on arrival. The expected time in the system, for the tagged customer, is then the sum of two quantities: (i) the expected time, rn, from the time of its arrival fill the HOL customer departs the system, and (ii) the expected time for the server to complete i cycles of the system, starting with the instant of the departure of the HOL customer, and ending with the completion of service on the tagged customer. Similar to equation 3.4, let 1 - Pn - Pn(O) n 1 - Pn(O) (3.10) denote the fraction of time that the server is away from node n given that there is at least one customer present at the node. The term rn is then given, analogous to equation 3.6, as rn = n (n + bn) + (-Xn) 2bn J This expression assumes that if the server is on vacation at the time of arrival of the tagged customer, then the expected residual life of this vacation is the same, independent of the number of customers present at the node at that time. This is clearly an approximation since, in general, the length of a vacation is dependent on the number of customers present at the node. It still remains to determine the expected time for the tagged customer in the system from the moment that the HOL customer, till the time of service completion on the tagged customer. To this end, let 8

Vn denote the expected length of a vacation which begins after a normal service at node n (i.e. after a service of expected length bn), ending when the server returns to node n. Also, let Cn = n + bn, (3.11) denote the expected length of a cycle which begins with a normal service at node n, ending with the next arrival instant of the server at node n. This cycle includes possible services at the other nodes, plus the sum of all the switchover times. To determine Cn, let amn denote the probability that this cycle contains a service at another node m. Then, since at most one customer is served at node m, we can write (also refer Kuehn (1979) for a similar derivation): aXmn k Xm Cn, man. Note that it is possible that when the arrival rate some node, m, is high, then COmn may exceed 1, in which case, it can no longer be interpreted as a probability. In such cases, it will be necessary to restrict this quantity to be at most 1. Hence, the expected length of this cycle is given by Cn = s + bn + min(m Cn, l)bm. (3.12) mrn If Cmn < 1 for all m, then the above expression simplifies to s + bn Cn (3.12a) 1 - p + pn otherwise, computing the Cn values will involve some iteration. Each of these vacations following the departure of the HOL customer is preceded by a service at node n. We could now assume that the expected length of each of these vacations equals vn and proceed exactly as in the analysis of the single node system. However, this assumption would be incorrect in the case of the vacation immediately following the departure of the HOL customer. To illustrate, consider the situation where the tagged customer found the server at node n, attending to the HOL customer. The arrival then interrupts a special service which has expected duration bn(2)/bn. Adopting a similar reasoning as was used earlier to obtain Cn, the cycle which includes this special service has an expected length Cn(b), where 9

Cn(b) - s + bn + min(km Cn(b), 1)bn. (3.13) mxn As before, it may be necessary to restrict the term XmCn(b) to be at most 1 in some cases. If this term is less than 1 for all m, the above expression simplifies to s + bn(2/bn Cn(b) s + b(2)b (3.13a) 1 - p + pn otherwise obtaining Cn(b) will generally involve some iteration. Let vn(b) = Cn(b) - bn(2)/bn, (3.14) denote the special vacation following this interrupted service. Clearly this is not equal to vn. Similarly, if the tagged customer arrives at node n when the server is on vacation, then he interrupts a special vacation which, in turn, influences the vacation following the subsequent departure of the HOL customer at node n. Let the expected length of the vacation, following the departure of the HOL customer, be denoted by vn. Let tn(i) denote the expected time in the system for an arrival at node n, given i customers were observed at the node at the time of arrival. Similar to the analysis for the single node system, we can write tn(i) = vn + bn, i =0, (3.15a) b (2) A tn(i) = xn(vn + bn) + (1-xn) 2bn) + bn) + (i-1)(Vn + bn), i > 0. (3.15b) The expected system time, tn, is: tn = wn+ bn = pn(i)tn(i). (3.16) i From equations 3.15 and 3.16, bn(2) Wn(1 - Xn Vn - Pn) = Vn (1 - Pn) + Pn — + Pn (vVn- vn) (1 - pn(O)). (3.17) In the above expression, to determine wn, we still need to evaluate the terms Vn, vn and pn(O). The expressions for these terms are developed in sections 3.3 and 3.4. 10

3.3 Determining the probability, pn(0): For this system, determining pn(O) exactly can be very complex. Here, this term is estimated by considering this cyclic server system from a different viewpoint. Consider a single node, single server system with Poisson arrivals in which, for each customer, the server requires a setup time that is independent of the service time. Further, suppose that this setup time has a different distribution for the customer that arrives to an empty system, than for a customer that arrives to a non-empty system. Such a system was also studied by Welch (1964) who obtained the distribution of the number of customers present at the node, given the first two moments of the distributions for the two setup times and for the service time. We shall refer to this system, for convenience, as system W. The probability, no, of finding zero customers at a random point in time in this system is presented below as Lemma 2. A proof of the Lemma may be found in Welch. Here, we develop the expression for no using somewhat informal reasoning. This will assist in drawing an analogy with the cyclic server system, which is used to estimate pn(O). Suppose the arrival rate to system W is X. Let f3 denote the first moment of the distribution for the service time, and let WN (respectively, v ),denote the setup time required for arrivals to a non-empty system (respectively, arrivals to an empty system). The expression for no requires only these first moments, and is given by Lemma 2: 1 - X(W + P) =Proo 1 - R(~- V) Proof: In effect, the mean amount of service time expended by the server on a customer is increased (on the average) either by F, for an arrival to an empty system, or by yf, for an arrival to a non-empty system. In fact, with probability no, this mean (enhanced) service time is equal to j + P, and with probability 1 - 7o, the mean (enhanced) service time is equal to v + P. So, the mean (enhanced) service time, A overall, is given by, where 11

= o (i + 3) + (1-to) (V + P). ~~AA Now, the utilization of the server by this system, denoted as p, can be written as = 1 - o. Alternately, this utilization is also given as A A p = = (Co ( + p) + (l-7o) ( + )). n Equating the two expressions for p, and simplifying, the desired result is obtained. It can be observed that the behavior of the cyclic server system with nonexhaustive service, as we have modeled it, closely resembles system W. When an customer arrives to an empty system at node n it interrupts a special 'setup' time, which has a mean residual life equal to vn at the time of interruption, before the server can begin actual service on this customer. Assuming that the total setup' time in this case is twice this residual life (of course, this is a heroic assumption, but we shall maintain this), the setup time here is 2vn. On the other hand, if the customer arrives to a non-empty system, then the mean 'setup' time in progress, between services to customers at this node, is given by vn (with the exception, which we choose to ignore, of the service following the HOL customer, which involves a mean 'setup' time of vn as per our assumptions). Hence, the probability, pn(O), of finding zero customers in this system, is then equated to 0o, with appropriate substitution of parameters, to obtain the following: Proposition 1: 1 - kn(vn + bn) pn(O) (3.18) 1 - Xn(n - 2in ) 3.4 Evaluating the terms n andvn: The terms vn and vn are evaluated by conditioning on the position of the server, as observed by the tagged customer on arrival. Let Ym denote the event that the server 12

is at node m at the time of arrival of the tagged customer. Similarly, let am denote the event that the server is switching from node m to node (m mod N) + 1 at the time of arrival of the tagged customer. Let q(ym) and q(acm), respectively, denote the probabilities of these events. From equation 3.1, it can be seen that ~(sm/c) + SPm = 1. m m Thus the term pm can be interpreted as the probability that the server is present at node m at a random point in time, and similarly, the term sm/c can be interpreted as the probability that the server is switching between nodes m and (m mod N) + 1 at a random point in time. Noting the fact that a Poisson arrival takes a random look at the system, we must have q(ym) = Pm, and q(am) = Sm/c. We also need to define the expected length of two cycles, (i) A cycle which includes a special service at node n of expected length bn(2)/bn, denoted as Cn(b), and (ii) a cycle which includes a special switchover between nodes n and n+l of expected length Sn(2)/Sn, denoted as Cn(s). The expression for Cn(b) was given by equation 3.13. The expression for Cn(s) is obtained using a similar reasoning: s + Sn(2)/Sn - Sn Cn(s) = s + s - (3.19) 1 - p The expression for v'n is then presented below as Proposition 2. The derivation for this expression is given in the Appendix. Proposition 2: Vn = - ( q(ym)/(1-pn)) v(n lym) + Z ( q(m)/(1-pn)) v(nl( m), (3.20) m m men where bi(2) n n v(nlym) = 2,bm+ Sk + + mink Cm(b), 1) bk, (3.20a) k=m k=m+l and Sm(2) n n v(n I m) = -si + Ask + A min(k Cm(s), 1) bk, (3.20b) k=m+l k=m+l 13

In equations (3.20a) and (3.20b) it is assumed that 1 < m < n < N. This avoids the use of the mod function. Note that this does not lead to any loss of generality. A Proposition 3 now develops the expression for the term vn. The derivation of this expression is also presented in the Appendix. Proposition 3: Vn = (1 - Xn) vn(b) + xn Vn(), (3.21) where Vn(l) = (q(ym)/(1-pn)) Vn(l lym) + (q(m)/(l-pn)) Vn( I m), (3.22) m m m~n with vn(l lYm) = s + Z min(Xk max[Cm(b),Cn],l) bk, (3.22a) k ken and vn(l I m) = s + Xmin(Xk max[Cm(s),Cn],l) bk, (3.22b) k ken A In equation 3.17, substituting for Xn and vn, using 3.10 and 3.21, an alternate expression for Wn is obtained as: Wn(l - Xn Vn - Pn) = n(l - Pn) + Pn(vn(b) + 2bn( + (vn(l) - Vn) (1-pn-pn(O)). (3.23) It is easy to show that the expression for the mean waiting times, given by 3.17 (or 3.23), is exact for some limited cases. This is stated as Proposition 4. The proof of this proposition is straightforward, and is omitted. Proposition 4: The expression for the mean waiting times given by equation 3.17 is exact for the single node vacation system, and for the symmetric system having deterministic service times, and deterministic switchover times. * 14

4. The accuracy of the approximation: The mean waiting time estimates obtained by MACNESS was validated for its accuracy through extensive simulation on a substantial number of test cases. Under conditions of relatively low traffic (p < 0.5), the estimates obtained by MACNESS were very close to the simulation estimates. Under conditions of heavy traffic, when the system was quite asymmetric, some differences were observed between the two estimates. In this section, using the conservation law of Watson (1984), a means of improving the accuracy of the estimates obtained by MACNESS is presented. 4.1 The conservation law: The conservation law (Watson (1984)), which provides one equation for the mean waiting times in terms of known data parameters, is presented below: Pn(l - XnC) wn = 2(1-p) Xn bn(2 )-n + P,( - p+n(1 + Pn). (4.1) n n n n This law can indicate how effective the approximation is. Suppose we substitute the mean waiting times obtained from equation 3.17 in place of the wn values in equation 4.1 and evaluate the resulting expression on the left hand side. Let the factor 4 denote the ratio of the expression on the right hand side of this equation, to the quantity evaluated on the left hand side. Obviously, the closer this ratio is to 1, the more confidence one would have in the above approximation. A substantial number of experiments were conducted to determine the accuracy of the approximation. At low traffic intensities (p < 0.5), the factor, 4, was between 0.96 and 1.0 in all of these test cases. In addition, the estimates of wn were very close to the simulation estimates here. At heavy traffic intensities, this factor ranged, in general, between 0.90 to 1.10, with a few exceptions outside this range occuring as the system was nearing the limits of stability. This is to be expected since we have made several assumptions in arriving at the expression for the mean waiting times. It is conjectured that the approximation used to obtain the expression for vn is a major contributor in causing the factor to be different from 1 for the heavy traffic case. We now make use of the conservation law to obtain an improved estimate for v'n in the following section. 15

It is to be noted that Boxma and Meister (1986) use the conservation law directly, to obtain their estimates of mean waiting times. This technique, (henceforth referred to as the B&M technique) proceeds as follows. At the time of arrival of the tagged customer at node n, the server is at some place in the system. The arrival sees the equilibrium distribution of customers at the various nodes, and hence, on the average, sees qn = An wn customers waiting at node n. So the mean waiting time for this customer consists of two quantities: (i) the expected residual cycle time, rcn, for the server to reach node n, from the place he is currently at, and (ii) the time for the server to complete Xn Wn cycles, each of length Cn, to serve qn customers. The mean waiting time is then obtained as: rcn Wn = 1- XnCn The B&M technique now assumes that the residual cycle times are the same for each node. It then uses the conservation law to obtain a closed form expression for the wn's. It is remarked, though, that the resulting expression does not provide an intuitive understanding for the behavior of the system. 4.2 Improved estimates of n using the conservation law: Equation 3.17 is first rewritten as: Wn = Kn + n, (4.2) where bn(2) Kn = Vn (1 - Pn) + n + Pnvn, (4.2a) and A n = (vn - n) (1 - Pn(O)). (4.2b) In order to improve on the estimates of vn, it is assumed that the term Kn is the same for all nodes. Note the similarity between this assumption and the assumption made by the B&M technique. In fact, if we had not accounted for the 'special' vacation following the departure of the HOL customer, then this approximation would just reduce to the B&M technique and KCn would represent the 'residual cycle time' here. (We have, of course, presented an intuitive approach for obtaining this 'residual cycle time'). Applying the conservation law to the above expression for wn, and setting Cn = K, an expression for K can be obtained in a straightforward manner as 16

X- u)nOn n K: = ' (4.3) On n where X represents the expression on the right hand side of the conservation law given in equation 4.1, and pn (l - Xnc) 1 - Xnn -Pn Thus, a new estimate of v'n is obtained from equations 4.3 and 4.2a. This estimate is now used in equation 3.17 for obtaining the wn's. The use of the conservation law in this manner does imply that this is an iterative algorithm for obtaining these values. However, in practice these values converge within a few iterations, and in using this approach we choose not to iterate more than once. Finally, note that the use of equation 4.1 in this manner guarantees (although indirectly) that the resulting estimates of Wn do satisfy the conservation law. 4.3 The special case of systems with zero switchover times: Although the MACNESS approach was motivated by considering a single node vacation system, it has a direct extension for systems with zero switchover times. We merely set the mean switchover time at all nodes to be some arbitrarily small but finite value. Then all the expressions presented earlier hold. (An alternate view of this approach would be to consider that each of the q(on) terms are uniformly replaced by a factor equal to (l-p)/N.) The resulting mean waiting time estimates appear to be as accurate as in the case with non-zero switchover times. Boxma and Meister (1987) also present an approximation technique for such systems. This is also based on the conservation law and is very similar to their technique for systems with non-zero switchover times. 5. Experimental results: The estimates of the mean waiting times obtained by MACNESS for some test cases are presented in Tables 1 through 16. Of these, Tables 1 through 12 are taken from Boxma and Meister (1986, 1987), and these cover all the examples they present 17

therein. The simulation results presented in these tables are also taken from their papers. It must be noted that the simulation estimates could have some statistical error. However, the simulation results that are presented in these tables mostly satisfy the conservation law fairly closely. For comparison, the estimates obtained using the B&M technique are also presented in these tables. As mentioned earlier, the B&M technique gives the best results among all the techniques previously reported. For example, the methods of Kuehn, and Kimura and Takahashi, when applied to these test cases, often gave large errors, sometimes in excess of 50 %. The errors, indicated in parantheses in these tables are calculated relative to the values obtained by simulation. 5.1 Discussion of results: For ease of presentation, the results in these tables represent mean waiting times that are averaged over groups of queues which have identical characteristics, and for which the mean waiting times obtained were quite close. It is to be noted that the B&M technique obtains the same values for these groups of queues. In general, however, there will be some (possibly small) difference in mean waiting times between two adjacent nodes even though they may have the same characteristics with regard to their service time demands, arrival rates, and switchover times.The errors presented in these tables are based on comparison with simulation estimates. When the system is quite asymmetric, with one or more nodes approaching saturation (as indicated by equation 3.7), then the B&M technique stipulates a modification to their algorithm if switchover times are not insignificant. In this modified approach, the conservation law is used to obtain the mean waiting times at the nodes which are nearing saturation. Then, these nodes are removed, and their presence in the system is accounted for by inflating the means and second moments of some of the switchover times accordingly. The mean waiting times for the nodes in the resulting system (which now has less nodes than in the original system), is now evaluated using the conservation law once again (it is suggested that this procedure be repeated several times if necessary). While this appears to improve on the estimates, there are two potential problems with this approach. First, using this modified procedure clearly implies that the resulting mean waiting times need not 8 Note, however, that the analyses of Kuehn, and Kimura and Takahashi, obtain more than just the mean waiting times. 18

now satisfy the conservation law on which the technique is based. Secondly, it is hard to recognize exactly when, and to what extent, this method is to be applied, namely, whether this really does improve the estimates at all, and if so how many nodes are to be removed in this manner (Boxma and Meister do present some thumb rules for guiding this choice; however, see the remark regarding table 11 below). Among the test cases reported, this modified approach to the B&M technique is applied in tables 2, 8, and in tables 10 through 13 at p=0.8; and table 15 at p=0.75.The application of this modification does not appear to improve on the estimates in table 11, for example. However, it does significantly improve on the estimates obtained in the other cases. The errors reported in the tables are based on comparison with simulation estimates. In making any comparisons between the two techniques, however, it is to be noted that the simulation results could be subject to some statistical error of probably upto 10% in estimating the true mean, especially under very heavy traffic. In general, for comparing the accuracy of the two approximation techniques, we choose to ignore cases where the errors are of the order of about 5% or less. Comparing MACNESS with the B&M technique, it can be observed from the tables that both produce estimates that are very close to those obtained by simulation when the traffic is relatively low (p < 0.5). When the traffic is heavy, and the systems are quite asymmetric, MACNESS does appear to perform significantly better than the B&M technique. This appears to be especially true when the switchover times are zero, (as in tables 1, 3, 6, 10 and 14, for example) where the B&M technique gives estimates that are upto about 40% away from the simulation estimates. The relative accuracy in the MACNESS estimates is significant considering that it does not call for a modification in the algorithm under heavy traffic conditions, as required by the B&M technique (for the case of systems where switchover times are not negligible). In general, even under conditions of heavy traffic, for the cases presented here, the estimates obtained by MACNESS are usually within 10% of the simulation estimates, with a notable exception being table 11, where the errors are as high as about 18%. It is important to note that this is one case where the simulation results appear to be quite in error. This observation is based on the fact that the conservation law, when applied on the simulation estimates, is far from being satisfied. (It was not possible to get better estimates here as the system is close to saturation in this example). It is expected that when the systems are even more asymmetric and under even heavier traffic, the approximation would give larger errors. Some such cases 19

were tested; however, the simulation results were unreliable here, and these cases are not reported, as meaningful comparisons cannot be made. 6. Summary and Conclusion: The analysis of cyclic server systems with non-exhaustive service is complex. In general, even obtaining the exact mean waiting times for such systems presents considerable difficulties. Hence a number of approximate techniques have been presented in the past. A new technique, Myopic Analysis of Cyclic Non-Exhaustive Service Systems (MACNESS), has been proposed in this paper. This technique appears to perform much better than techniques previously reported, based on extensive validations through simulations. A notable feature of the technique is that it presents an intuitively appealing explanation for the average waiting time behavior of these complex systems. This expression produces estimates that are usually very close to the mean waiting times obtained by simulations, and appears to be fairly robust even at very high utilizations, particularly when the conservation law is used to recalculate the values of the residual vacation times. The approximation is based on a simple approach, developed in this paper, for obtaining the mean waiting time for a single node vacation system. This approach is then, heuristically, extended to the general system with N > 1 nodes. It can be easily verified that the resulting expression for the mean waiting times, given by equation 3.17, is exact for the completely symmetric case whenever the service times and switchover times are both deterministic. The approximation has a straightforward extension for analyzing systems with zero switchover times. It has been observed (Boxma and Meister (1987)), that the accuracy of approximate techniques usually degrades as switchover times tend to zero. In fact, the B&M technique does perform relatively quite poorly in some of the test cases when the switchover times are zero. However, no noticeable change in accuracy of estimates can be noticed in the MACNESS approach. Acknowledgement: The author benefited considerably from several stimulating discussions on this topic with S.M.Pollock. 20

REFERENCES Berry, R. and Chandy, K.M. (1983), "Performance models of token ring local area networks", Performance Evaluation Review, (special issue), pp. 266-274, August 1983. Boxma, O.J. (1986), "Two symmetric queues with alternating service and switching times", Proceedings. Performance '84, North Holland, Amsterdam, pp.475 -490. Boxma, O.J., and Meister, B. (1986), "Waiting-time approximations for cyclic-service systems with switch-over times", Performance '86 and ACM Sigmetrics 1986, Proceedings of the Joint Conference on Computer Performance Modeling, Measurement, and Evaluation, pp.254-262, Raleigh, N. Carolina, May 1986. Boxma, O.J., and Meister, B. (1987), "Waiting-time approximations in mulit-queue systems with cyclic service", Performance Evaluation, vol 7, 1987, pp.59-70. Bux, W. (1981), "Local area subnetworks: A performance comparison", IEEE Transactions on Communications, v COM-29, no 10, October 1981, pp. 1465 -1473. Bux, W., and Truong, H.L. (1983), "Mean-delay approximation for cyclic service queueing systems", Performance Evaluation, v 83, 1983, pp. 187-196. Carsten, R.T., Newhall, E.E., and Posner, M.J.M. (1977), "A simplified analysis of scan times in an asymmetric Newhall loop with exhaustive service", IEEE Transactions on Communications, v COM-25, no 9, September 1977, pp. 951 -957. Cooper, R.B., and Murray, G. (1969), "Queues served in cyclic order", Bell System Technical Journal, v 48, no 3, March 1969, pp. 675-689. Cooper, R.B. (1970), "Queues served in cyclic order: waiting times", Bell System Technical Journal, v 49, no 3, March 1970, pp. 399-413. Eisenberg, M. (1979), "Two queues with alternating service", SIAM Journal of Applied Mathematics, v 36, 1979, pp 287-303. Ferguson, M.J., and Aminetzah, Y.J. (1985), "Exact results for non-symmetric token ring systems", IEEE Transactions on Communications, v COM-33, no 3, pp. 223-231, March 1985. Fuhrmann, S.W., and Cooper, R.B. (1985), "Stochastic decompositions in the M/G/1 queue with generalized vacations", Operations Research, v 33, no 5, September-October 1985, pp. 1117-1129. 21

Kimura, and Takahashi (1986), "Diffusion approximation for a token ring system with nonexhaustive service", IEEE Journal on selected areas in communications, vol SAC-4, no 6, September 1986, pp. 794-801. Kleinrock, L. (1975), Queueing systems. Volume I: Theory, Wiley, New York, 1975. Kuehn, P.J. (1979), "Multiqueue systems with non-exhaustive cyclic service", Bell System Technical Journal, v 58, no 3, March 1979, pp. 671-698. Little, J.D.C. (1961), "A proof of the queueing formula L = kW", Operations Research, v 9,1961, pp. 383-387. Takagi, H. (1985), "Mean message waiting times in symmetric multi-queue systems with cyclic service", Performance Evaluation, vol 5, 1985, pp. 271-277. Watson, K.S. (1984), "Performance evaluation of cyclic service strategies - a survey", Performance '84, Elsevier Publishers, New York, 1984. Welch, P.D. (1964), "On a generalized M/G/1 queueing process in which the first customer in a busy period receives exceptional service", Operations Research, v 12,1964, pp. 736-752. Wolff, R.W. (1982), "Poisson arrivals see time averages", Operations Research, v 30, 1982, pp. 223-231. 22

APPENDIX Derivations of the expressions in Propositions 2 and 3 Proposition 2: Vn = (q(Ym)/(l-pn)) v(nlym) + X (q((m)/(l-pn)) i(nI (m) (Al) m m man where bm(2) n n n I 7m) = - + Sk + Z min(kk Cm(b), 1) bk, (A2) k=m k=m+l and Sm(2) n n I(n I am) = 2 + sk + min(Xk Cm(s), 1) bk, (A3) m k=m+l k=m+l Derivation of equation Al: In section 3.4 the fraction of time that the server is present at a node m was obtained as q(ym) = Pm, and the fraction of time that the server was switching between node m and node (m mod N) + 1 was obtained as q(am) = sm/c. Extending this line of reasoning a little further, given that the tagged customer sees the server on vacation at the time of its arrival, the fraction of time it sees the server at node m, m ~ n, (respectively, switching between nodes m and (m mod N) + 1), is just q(ym)/(l-pn), (respectively, q(am)/(l-pn)). Now, let v'(n lym), (respectively, v'(n lm)), denote the conditional residual vacation time, from the point of view of an arrival at node n, given that the server was found busy at node m, (respectively, switching between node m and node (m mod N) + 1), at the point of arrival of the tagged customer. Suppose that the arrival at node n found the server on vacation, and at some node m, man. (For ease of discussion, it is assumed that 1 < m < n < N). This arrival 23

then interrupts a special service which has an expected duration of bm(2)/bm. The expected residual life of this interrupted service is, of course, bm(2)/2bm. Following the completion of this service, the server then needs to complete the rest of this interrupted vacation. This service interruption has, however, induced a cycle of expected length Cm(b), as given by equation 3.13. Hence, considering a node k on the path from node m to node n, the expected number of customers served at this node would be Xk Cm(b). (Again, at high arrival rates, this quantity might exceed 1, and in this case the probability of a service at node k is assumed as equal to 1). Thus we have: bm(2) n n (n I ym) 2b — + Sk + min(k Cm(b), 1) bk. k=m k=m+l Similarly, consider the case where the tagged customer interrupts the server switching between nodes m and (m mod N) + 1. The expected length of this interrupted switchover is sm(2)/Sm, and this induces a cycle of length Cm(s), where Cm(s) S + Sm(2)/Sm Sm Cm(s) = 1 - p In this case, the conditional residual vacation time v'(n I am) is obtained as M(2) (n n v(n I om) += sk+ + min(k Cm(s), 1)bk. k=m+l k=m+l Finally, the residual vacation time vn is determined as Vn = ( q(Ym)/(1-pn)) V(nlym) + Z (q(cm)/(l-pn)) v(n lm). m m man Tn Tn~~~~~~~~ 24

Proposition 3: n = ( - xn) vn(b) + n vn(l). (A4) Derivation of equation A4: Implicit in the discussion here is the understanding that the tagged customer arrives to node n and finds one or more customers already present at the node. Consider the position of the server at the instant of arrival of the tagged customer. With probability 1 - xn, the arrival finds the server at node n. In this case, it interrupts a special service of expected duration bn(2)/bn. As discussed earlier (refer equation 3.13), this induces a special cycle of expected length Cn(b), with a corresponding vacation of expected length vn. This accounts for the first term on the right hand side. Suppose, on the other hand, that the tagged customer, on arrival at node n, finds the server away from the node. This happens with probability xn. In this case, the arrival interrupts a special vacation. Suppose that the server was performing a service at node m, men. The fraction of time this occurs is just q(ym)/(1-pn), and the expected length of the interrupted service is bm(2)/bm. This was the argument used to obtain the residual life of the interrupted vacation vrn, wherein it was proposed that the effect of this interruption induces a special cycle, Cm(b), which continues until the server reaches node n, where he now performs a 'normal' service (i.e. a service of mean duration bn). Here, this argument is extended a little further: it is proposed that the effect of this interrupted service at node m could continue even after the server completes the service at node n, i.e., during the vacation following this service. In effect, it is proposed that this vacation is governed by either the interrupted service at node m or the service at node n, whichever dominates. Thus, in this vacation, the probability of service at a node k, ken, is given by akm, where Akm = min(Xk. max[Cm(b),Cn],l). Hence, with probability q(ym)/(l-pn), the expected length of a vacation, vn(l I ym), which follows a service at node n on the customer at the head of the queue, is given by 25

Vn(1 I Ym) A S + Xakm. k ken Suppose, on the other hand, that the server was switching between node m and node (m mod N) + 1, at the time of arrival of the tagged customer. The fraction of time this occurs is q(om)/(l-pn). In this case, adopting an entirely similar argument, the expected length of this vacation following the service on the customer at the head of the queue at node n, Vn(l I am), is given by Vn(l I Cm) s + (akm, k ken where xakm = min(Xk. max[Cm(s),Cn],l). Hence, the expected length of a vacation following the service on the customer at the head of the line, denoted as Vn(l), is obtained by the weighted average of these conditional cycle times as: Vn(1) = E (q(Ym)/(l-pn)) Vm(ll Ym) + (q(Cm)/(l-pn)) Vm(l I am). m m mmn Given that the arriving customer saw the server away from the node on arrival, the special vacation following the departure of the customer at the head of the line is just Vn(l). Since this occurs with probability xn, the result follows. 26

Utilization (P) Node Method 0.3 0.5 0.8 Simulation* 0.135 0.553 4.144 1 MACNESS* 0.137 (1.5) 0.557 (0.7) 4.251 (2.6) Boxma & Meister 0.136 (0.7) 0.556 (0.5) 3.942 (-4.9) Simulation* 0.115 0.393 1.477 2 to 3 MACNESS* 0.116 (0.9) 0.414 (5.3) 1.623 (9.9) Boxma & Meister 0.118 (2.6) 0.417 (6.1) 2.087 (41.3) * The mean waiting times have been averaged over corresponding group of queues. Errors are indicated in parantheses. Table 1: Comparison of mean waiting times obtained by MACNESS with simulation, and with technique of Boxma and Meister. N=3, x1 = 0.6, X2 = X3 =0.2; All service time distributions exponential with bl=b2=b3. All switchover times equal to zero. Utilization (p) Node Method 0.3 0.5 0.8 Simulation* 0.333 0.976 9.090 1 MACNESS* 0.334 (0.3) 0.970 (-0.6) 9.162 (0.8) Boxma & Meister 0.334 (0.3) 0.959 (-1.7) 8.360 (-8.0) Simulation* 0.261 0.599 1.920 2 to 3 MACNESS* 0.261 (0.0) 0.614 (2.5) 2.083 (8.5) Boxma & Meister 0.262 (0.4) 0.628 (4.8) 1.480 (-22.9) * The mean waiting times have been averaged over corresponding group of queues. Errors are indicated in parantheses. Table 2: Comparison of mean waiting times obtained by MACNESS with simulation, and with technique of Boxma and Meister. N=3, X1=0.6; X2=X3=0.2; All service time distributions exponential with b2=b3=(1/3) bl. All switchover times exponential and equal to 0.05. 27

Utilization (P) Node Method 0.3 0.5 0.8 Simulation* 0.175 0.677 4.473 1 MACNESS* 0.182 (4.0) 0.731 (8.0) 4.905 (9.7) Boxma & Meister 0.180 (2.9) 0.733 (8.3) 5.203 (16.3) Simulation* 0.156 0.569 3.570 2 to 3 MACNESS* 0.151 (-3.2) 0.553 (-2.8) 3.203 (-10.3) Boxma & Meister 0.155 (-2.5) 0.550 (-4.8) 2.755 (-23.6) * The mean waiting times have been averaged over corresponding group of queues. Errors are indicated in parantheses. Table 3: Comparison of mean waiting times obtained by MACNESS with simulation, and with technique of Boxma and Meister. N=3,,1 = A2 = X3 =1/3; All service time distributions exponential with b2=b3=(1/3) bl. All switchover times equal to zero. Utilization (p) Node Method 0.3 0.5 0.8 Simulation* 0.570 1.384 11.260 1 MACNESS* 0.570 (0.0) 1.470 (6.2) 12.591 (11.8) Boxma & Meister 0.570 (0.0) 1.494 (7.2) 13.020 (15.6) Simulation* 0.502 1.196 8.600 2 to 3 MACNESS* 0.493 (-1.8) 1.157 (-3.3) 7.554 (-12.2) Boxma & Meister 0.493 (-1.8) 1.121 (6.3) 6.890 (-19.9) * The mean waiting times have been averaged over corresponding group of queues. Errors are indicated in parantheses. Table 4: Comparison of mean waiting times obtained by MACNESS with simulation, and with technique of Boxma and Meister. N=3, X1 = X2 = X3 =1/3; All service time distributions exponential with b2=b3=(1/3) bl. All switchover times exponential and equal to 0.10. 28

Utilization (P) Node Method 0.3 0.5 0.8 Simulation 0.175 0.679 4.490 1 MACNESS 0.176 (0.5) 0.711 (4.7) 4.718 (5.1) Boxma & Meister 0.170 (-2.9) 0.681 (0.3) 4.965 (10.6) Simulation* 0.163 0.602 3.891 2 to 6 MACNESS* 0.160 (-1.8) 0.610 (1.3) 3.832 (-1.5) Boxma & Meister 0.161 (0.0) 0.622 (3.3) 3.724 (-4.3) Simulation 0.175 0.675 4.468 7 MACNESS 0.176 (0.6) 0.710 (5.2) 4.708 (5.4) Boxma & Meister 0.170 (-2.9) 0.681 (0.9) 4.965 (11.1) Simulation* 0.161 0.620 3.869 8 to 16 MACNESS* 0.160 (-0.6) 0.610 (-1.6) 3.831 (-1.0) Boxma & Meister 0.163 (1.2) 0.622 (0.3) 3.724 (-3.7) * The mean waiting times have been averaged over corresponding group of queues. Errors are indicated in parantheses. Table 5: Comparison of mean waiting times obtained by MACNESS with simulation, and with technique of Boxma and Meister. N=16, X1 =.- = 16 = 1/16; All service time distributions exponential with bl=b7, b2=..=b6=b8=..=bl6=(1/3)bl. All switchover times equal to zero. Utilization (p) Node Method 0.3 0.5 0.8 Simulation 0.140 0.595 4.538 1 MACNESS 0.142 (1.4) 0.604 (1.5) 4.601 (1.4) Boxma & Meister 0.140 (0.0) 0.584 (-1.8) 4.383 (-3.4) Simulation* 0.110 0.355 1.149 2 to 16 MACNESS* 0.108 (-1.8) 0.345 (-2.8) 1.098 (-4.4) Boxma & Meister 0.113 (2.8) 0.375 (5.6) 1.427 (-24.2) * The mean waiting times have been averaged over corresponding group of queues. Errors are indicated in parantheses. Table 6: Comparison of mean waiting times obtained by MACNESS with simulation, and with technique of Boxma and Meister. N=16, 31=0.6; X2=..=X16=2/75; All service time distributions exponential with identical means. All switchover times equal to zero. 29

Utilization (P) Node Method 0.3 0.5 0.8 Simulation 0.823 1.697 8.780 1 MACNESS 0.835 (1.5) 1.752 (3.2) 9.349 (6.5) Boxma & Meister 0.831 (1.0) 1.742 (2.7) 10.060 (14.6) Simulation* 0.793 1.591 7.980 2 to 6 MACNESS* 0.796 (0.4) 1.586 (-0.3) 7.900 (-1.0) Boxma & Meister 0.797 (0.5) 1.590 (-0.1) 7.540 (-5.5) Simulation 0.833 1.720 8.900 7 MACNESS 0.835 (0.2) 1.752 (1.9) 9.340 (4.9) Boxma & Meister 0.831 (-0.2) 1.742 (1.3) 10.060 (11.8) Simulation* 0.793 1.591 7.910 8 to 16 MACNESS* 0.796 (0.3) 1.586 (-0.3) 7.850 (-0.8) Boxma & Meister 0.797 (0.5) 1.590 (-0.1) 7.540 (-4.6) * The mean waiting times have been averaged over corresponding group of queues. Errors are indicated in parantheses. Table 7: Comparison of mean waiting times obtained by MACNESS with simulation, and with technique of Boxma and Meister. N=16, k1 =.. = X16 = 1/16; All service time distributions exponential with bl=b7, b2=..=b6=b8=..=bl6=(1/3)bl. All switchover times equal to 0.05. Utilization (p) Node Method 0.3 0.5 0.8 Simulation 0.330 1.015 9.710 1 MACNESS 0.325 (-1.5) 1.026 (1.1) 10.284 (5.9) Boxma & Meister 0.321 (-2.7) 0.996 (-1.9) 9.790 (0.9) Simulation* 0.222 0.495 1.350 2 to 16 MACNESS* 0.219 (-1.4) 0.484 (-2.2) 1.303 (-3.5) Boxma & Meister 0.224 (0.9) 0.521 (5.3) 1.240 (-8.1) * The mean waiting times have been averaged over corresponding group of queues. Errors are indicated in parantheses. Table 8: Comparison of mean waiting times obtained by MACNESS with simulation, and with technique of Boxma and Meister. N=16, X1=0.6; X2=..=X16=2/75; All service time distributions exponential with identical means. All switchover times equal to 0.01. 30

Utilization (P) Node Method 0.3 0.5 0.8 Simulation 0.377 1.479 10.748 1 MACNESS 0.349 (-7.4) 1.403 (-5.1) 10.427 (-3.0) Boxma & Meister 0.375 (-0.5) 1.512 (2.2) 10.662 (-0.8) Simulation* 0.332 1.107 4.128 2 to 6 MACNESS* 0.300 (-9.6) 1.030 (-7.0) 4.605 (11.6) Boxma & Meister 0.328 (-1.2) 1.134 (2.4) 4.719 (14.3) Simulation 0.385 1.547 11.105 7 MACNESS 0.422 (9.6) 1.709 (10.5) 11.027 (-0.7) Boxma & Meister 0.375 (-2.6) 1.512 (-2.3) 10.662 (-4.0) Simulation* 0.307 1.015 3.888 8'to 16 MACNESS* 0.299 (2.7) 1.015(0.0) 4.523 (16.3) Boxma & Meister 0.328(6.8) 1.134(11.7) 4.719 (21.4) * The mean waiting times have been averaged over corresponding group of queues. Errors are indicated in parantheses. Table 9: Comparison of mean waiting times obtained by MACNESS with simulation, and with technique of Boxma and Meister. N=16, X1=X7=0.15; X2=..X6=X8=..X16=0.05; Service time distributions at nodes 2..6, and 8..16 exponential with identical means; service at node 1 Erlang-4 with bl=6b2; service at node 7 Hyperexponential with coefficient of variation=2, and b7=6b2. All switchover times equal to zero. Utilization (p) Node Method 0.3 0.5 0.8 Simulation* 0.131 0.532 3.905 1 to 4 MACNESS* 0.133 (1.5) 0.535 (0.6) 3.926 (0.5) Boxma & Meister 0.131 (0.0) 0.521 (-2.1) 3.612 (-7.5) Simulation* 0.123 0.439 1.896 2 to 16 MACNESS* 0.121 (-1.6) 0.437 (-0.5) 1.910 (0.7) Boxma & Meister 0.124(0.8) 0.463 (5.5) 2.467 (30.1) * The mean waiting times have been averaged over corresponding group of queues. Errors are indicated in parantheses. Table 10: Comparison of mean waiting times obtained by MACNESS with simulation, and with technique of Boxma and Meister. N=16, X1=..=X4=0.16;,5=..=X16=0.03; All service time distributions exponential with identical means. All switchover times equal to zero. 31

Utilization (P) Node Method 0.3 0.5 0.8 Simulation 1.198 3.253 41.260 1 MACNESS 1.200 (0.2) 3.189 (-2.0) 33.993 (-17.6) Boxma & Meister 1.224 (2.2) 3.271 (0.6) 33.840 (-18.0) Simulation* 0.946 2.011 6.270 2 to 6 MACNESS* 0.913 (-3.5) 1.933 (-3.9) 7.059 (12.6) Boxma & Meister 0.940 (-0.6) 2.027 (0.8) 4.900 (-21.9) Simulation 1.247 3.335 39.210 7 MACNESS 1.273 (2.1) 3.447 (3.3) 34.379 (-12.3) Boxma & Meister 1.224 (-1.8) 3.271 (-1.9) 33.840 (-13.7) Simulation* 0.922 1.902 6.170 8 to 16 MACNESS* 0.912 (-1.1) 1.923 (1.1) 7.027 (13.9) Boxma & Meister 0.940 (2.0) 2.027 (6.6) 4.900 (-20.6) * The mean waiting times have been averaged over corresponding group of queues. Errors are indicated in parantheses. Table 11: Comparison of mean waiting times obtained by MACNESS with simulation, and with technique of Boxma and Meister. N=16, Xl=X7=0.15; X2=..66=X8=..16=0.05; Service time distributions at nodes 2..6, and 8..16 exponential with identical means; service at node 1 Erlang-4 with bl=6b2; service at node 7 Hyperexponential with coefficient of variation=2, and b7=6b2. All switchover times equal to 0.05. Utilization (p) Node Method 0.3 0.5 0.8 Simulation* 0.898 1.929 17.660 1 to 4 MACNESS* 0.901 (0.3) 1.922 (-0.4) 17.901 (1.3) Boxma & Meister 0.897 (-0.1) 1.884 (-2.3) 16.870 (-4.2) Simulation* 0.717 1.267 3.570 2 to 16 MACNESS* 0.714 (-0.4) 1.255 (-1.0) 3.967 (11.1) Boxma & Meister 0.720 (0.4) 1.307 (3.2) 3.14 (-12.0) * The mean waiting times have been averaged over corresponding group of queues Errors are indicated in parantheses. Table 12: Comparison of mean waiting times obtained by MACNESS with simulation, and with technique of Boxma and Meister. N=16, X1=..=X4=0.16; X5=..=X16=0.03; All service time distributions exponential with identical means. All switchover times equal to 0.05. 32

Utilization (P) Node Method 0.3 0.5 0.8 Simulation* 0.505 1.188 9.250 1 to 3 MACNESS* 0.505 (0.0) 1.160 (-2.4) 10.160 (9.8) Boxma & Meister 0.504 (-0.2) 1.041 (3.8) 10.056 (8.7) Simulation* 0.379 0.685 1.597 4 to 8 MACNESS* 0.376 (-0.8) 0.681 (-0.6) 1.782 (11.6) Boxma & Meister 0.378 (-0.2) 0.701 (2.3) 1.451 (-9.1) * The mean waiting times have been averaged over corresponding group of queues. Errors are indicated in parantheses. Table 13: Comparison of mean waiting times obtained by MACNESS with simulation, and with technique of Boxma and Meister. N=8, X1 =.. = X3 =0.3, k4 =.* = X8 = 0.02; bl=.. = b8. Service at nodes 1 through 3 are Erlang-4. Service at nodes 4 through 8 are Hyperexponential with coefficient of variation = 2. All switchover times equal to 0.05. Utilization (p) Node Method 0.3 0.6 0.9 Simulation* 0.206 1.251 6.103 1 to 5 MACNESS* 0.204 (-1.0) 1.231 (-1.6) 5.682 (-6.9) Boxma & Meister 0.208 (1.0) 1.305 (4.3) 8.580 (28.9) Simulation 0.236 1.875 26.747 6 MACNESS 0.240 (1.7) 1.935 (3.2) 24.541 (-8.2) Boxma & Meister 0.235 (-0.4) 1.837 (-2.2) 20.727 (-22.51) * The mean waiting times have been averaged over corresponding group of queues. Errors are indicated in parantheses. Table 14: Comparison of mean waiting times obtained by MACNESS with simulation, and with technique of Boxma and Meister. N=6, kl = X = X5 = 0.0673, X6 = 0.2558; All service times have bimodal distribution with coefficient of variation 1.01, and identical means. All switchover times are equal to zero. 33

Utilization (P) Node Method 0.25 0.50 0.75 Simulation* 0.952 2.251 5.915 1,4 MACNESS* 0.931 (2.2) 2.251 (0.0) 6.590 (11.4) Boxma & Meister* 0.936 (-1.7) 2.331 (3.6) 5.383 (-11.0) Simulation* 0.995 2.675 8.999 2,5 MACNESS* 1.009 (1.4) 2.679 (-0.1) 9.951 (10.6) Boxma & Meister* 1.008 (1.3) 2.697 (0.8) 7.094 (-21.1) Simulation 1.145 3.748 28.870 3 MACNESS 1.180 (3.1) 3.730 (-0.5) 26.659 (-7.7) Boxma & Meister 1.176 (2.7) 3.639 (-2.9) 23.519 (-18.5) * The mean waiting times have been averaged over corresponding pairs of queues. Errors are indicated in parantheses. Table 15: Comparison of mean waiting times obtained by MACNESS with simulation, and with technique of Boxma and Meister. N=5, Xi = X4 = 0.05, X2 = X5 = 1/12, X3 = 0.15; Service time distributions exponential with identical means. All switchover times equal to 0.2. Utilization (P) Node Method 0.25 0.50 0.75 Simulation 1.146 3.858 21.405 1 MACNESS 1.184 (3.3) 3.564 (-7.6) 22.253 (4.0), Boxma & Meister 1.183 (3.2) 3.615 (-6.3) 23.214 (8.5) Simulation 1.077 3.064 15.320 2 MACNESS 1.079 (-0.2) 2.906 (-5.2) 15.540 (1.4) Boxma & Meister 1.082 (-0.5) 2.892 (-5.6) 14.857 (-3.0) Simulation 1.050 3.113 15.574 3 to 5 MACNESS 1.047 (-0.3) 2.726 (-12.4) 13.210 (-15.2) Boxma & Meister 1.048 (-0.2) 2.651 (-14.8) 12.070 (-22.5) * The mean waiting times have been averaged over corresponding groups of queues. Errors are indicated in parantheses. Table 16: Comparison of mean waiting times obtained by MACNESS with simulation, and with technique of Boxma and Meister. N=5, Xl = *- = X5 = 0.15; Service time distributions exponential with b3 = b4 = b5, bl = 5b3, b2 = 2b3. All switchover times equal to 0.2. 34