Non-Deterministic Polling Systems Mandyam M. Srinivasan Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117 Technical Report 88-18 December 1988 (Revised: November 1989)

Non-Deterministic Polling Systems Abstract A non-deterministic polling system is considered in which a single server serves a number of stations. The service discipline at each station is, consistently, either non-exhaustive, semi-exhaustive, gated, or exhaustive. If the server polls a station i which uses either the non-exhaustive or the semi-exhaustive service discipline, then the next station polled is station j with probability Pij if there was service at station i. The service time at station i is a random variable which may depend on the station polled next. If no service is performed at station i, then the next station polled is station j with probability eij. The time to switch between stations i and j is a random variable which may depend on whether service was performed at station i or not. If the server polls a station i that follows either the exhaustive service discipline or the gated service discipline, then the next station polled is station j with probability pij regardless of whether there was service at station i or not. Cycle times and stability conditions are derived for this system, and Conservation Laws are obtained which express a weighted sum of the mean waiting times in terms of known data parameters. For systems with a mix of exhaustive and gated service stations, we show how the individual mean waiting times can be obtained.

1. Introduction The single-server polling system is a queueing system in which a single server attends to M stations. Each station receives requests for service according to independent arrival processes, and the server polls these stations in some order, servicing the requests present there. The number of requests served at a station depends on the service discipline at that station. The service disciplines that are typically modeled and studied are: i) non-exhaustive service: wherein the server serves exactly one request if the station is non-empty at the polling instant; ii) exhaustive service: wherein the server continues to serve requests at the station until it is empty; iii) gated service: wherein the server serves exactly those requests present at the station at the polling instant, and iv) semiexhaustive service: wherein the server continues to serve requests until the number of requests waiting for service is one less than the number found by the server at the time the station was polled. Polling systems have been extensively studied for the case where the order in which the stations are visited is deterministically specified in advance. We refer to these systems as "deterministic polling systems." In this paper, we introduce the "non-deterministic polling system" where the order in which the stations are polled is not deterministically specified. We consider a system with a mix of nonexhaustive, semi-exhaustive, exhaustive, and gated service stations. The movement of the server between the stations in the system is specified as follows. Suppose that the server has just polled a station i which follows either the non-exhaustive or the semi-exhaustive service discipline. If one or more requests are present at the polling instant, then following the service at station i, the server next polls station j with probability pij after a random amount of time, Lij. The service time for a request at station i is a random variable, Bij, which may depend on the station j that is polled next. If there are no requests present at station i when it is polled, then the server next polls station j with probability eij after a random amount of time, Sij. If station i follows either the exhaustive service discipline or the gated service discipline, then the server next polls station j with probability Pij regardless of whether service was provided at station i or not. The service time for a request at station i a random variable Bij, if the station j is polled next. The switchover time from station i to station j is a random variable Sij. This work has been motivated by a specific application in material handling systems studied by Bozer and Srinivasan (1988). In this application, the material handling system is a unit-load Automated Guided Vehicle (AGV) system in which a single vehicle serves a manufacturing "cell" moving loads from one machining center in the cell to another. When the AGV delivers a load to a center, it inspects (polls) the output buffer of that center to determine if there are any loads waiting 1

to be transported. If at least one load is present in the output buffer, then the AGV takes a certain amount of time to pick up a load from this output buffer, and a certain amount of time to transport the load and deliver it at its destination. Following this, the AGV polls the output buffer of the center which receives the load. If there are no loads waiting at the center that is polled by the AGV, it immediately switches to poll another center with some predetermined probability. The time taken by the vehicle to travel loaded from i to j (Lij) could be quite different from the time it takes to travel empty from i to j (Sij). (For instance the empty vehicle may follow path different from the loaded vehicle.) Note that in this application, all the stations use the non-exhaustive service discipline. As another application for the non-deterministic polling system, consider a "messenger boy" who serves a number of centers, picking up messages from one center and delivering them to another. The messages that the messenger picks up from a center will dictate which center he next visits. Upon arrival at, say, center i, if the messenger finds no waiting messages, then one policy he may adopt could be to remain at this center periodically checking for messages to be delivered from center i, until one arrives (this is a case with eii = 1, Si > 0); an alternate policy he may adopt could be to immediately switch to poll another center j with some predetermined probability eij. An application in computer communication networks is presented in Kleinrock and Levy (1988), where a random polling system is used to predict the expected delay in a Slotted ALOHA system. In the random polling system proposed by Kleinrock and Levy, the server, after polling a station i, next polls station j with probability Pj, whether or not a service was performed at station i. In this paper, we obtain an expression for the cycle time which represents the expected time between two successive polls at a specified station, and present the stability conditions for the general system with an arbitrary number of stations. Following this we obtain a conservation law which relates a weighted sum of the mean waiting time at each station in terms of the data parameters for two special cases: i) the case where ij = eij for all i,j and ii) the system with two stations and arbitrary pij's and ej's at the non-exhaustive and semi-exhaustive service stations. Finally, for systems with a mix of exhaustive and gated service stations, we obtain the individual mean waiting times by solving O(M3) linear equations. 2. Previous Work There is considerable literature on deterministic polling models. An excellent survey of work on polling systems is presented by Takagi (1988). Some of the earliest work on polling systems with an arbitrary number of stations can be attributed to Cooper and Murray (1969), and Cooper (1970). Following this work, a number of papers have appeared on exact analysis of these systems with 2

non-zero switchover times for both the continuous-time and the discrete-time case (Eisenberg 1972, Ferguson and Aminetzah 1985, Konheim and Meister 1974, Swartz 1980). The analysis of the non-exhaustive and semi-exhaustive service systems presents considerable difficulties. Even obtaining the mean waiting times appears to be a challenging task in general. Although mean waiting times for symmetric non-exhaustive service systems can be obtained exactly (Fuhrmann 1985, Takagi 1985), such analysis for asymmetric systems is available only for the case of M=2 (Boxma and Groenendijk 1987b). Indeed, while mean waiting times for gated and exhaustive service systems can be computed with only the first two moments of service and switchover times, this does not appear to be the case for non-exhaustive service systems in general (Takagi 1988). The development of conservation laws (Watson 1984, Boxma and Groenendijk 1987a, Srinivasan and Lee 1987) for these systems has thus proved to be very useful in providing insight on their behavior. These laws express a weighted sum of the mean waiting times at the stations in terms of data parameters, and require only the first and second moments of the service and the switchover times. In particular, Boxma and Groenendijk present an elegant analysis based on a work decomposition approach, which also provides some intuition as to why these conservation laws hold. For symmetric systems, the conservation laws obtain an expression for the mean waiting times in a closed form. These laws also enable the development of approximate solutions for asymmetric systems (Boxma and Meister 1986, Srinivasan 1988, Fuhrmann and Wang 1988). Most of the work on deterministic polling systems is based on cyclic polling systems, although there is some work on analyzing systems with a more general order of service (Baker and Rubin 1987, Mapp and Manfield 1986, Boxma et al. 1988). All of the above work relates to deterministic polling systems in which the order of visits to the stations by the server is fixed deterministically. A system in which the server visits the stations in a probabilistic order (according to a "Bernoulli schedule") is considered by Keilson and Servi (1986) wherein the server, on completion of a service at station i, next switches to station i+l with probability pi or polls station i with probability 1-pi. The cases where pi = 1 and pi = 0 reduce to the deterministic non-exhaustive and the deterministic exhaustive service system respectively. Kleinrock and Levy (1988) analyze a discrete-time random polling system, where the server next polls station j with probability pj. They obtain the mean waiting times in exhaustive and gated service systems through the solution of O(M3) linear equations. For completely symmetric random polling systems (in which all the stations adopt exactly one of three service disciplines, namely, the exhaustive, gated, or the non-exhaustive discipline), they obtain the mean waiting times explicitly. 3

Boxma and Weststrate (1989) have, independent of this paper, considered a polling system with "Markovian server routing", and obtained the conservation law for a system with a mix of nonexhaustive, exhaustive, and gated service stations in an elegant manner using the work decomposition approach. Their analysis requires the identification of a time-reversed Markov chain in order to obtain the conservation law. The system analyzed by Boxma and Weststrate is the special case considered in our paper where pij = eij for all stations including the non-exhaustive service stations. It may be observed that many other well-known polling systems, including the random polling system presented by Kleinrock and Levy, are special cases of the non-deterministic polling system. 3. The Model A system with M stations is considered. Requests for service arrive at station i according to an independent Poisson process at rate Xi. It is assumed that there is an infinite capacity to hold these requests until they can be served. Denote by N, S, E, and G, the set of non-exhaustive, semiexhaustive, exhaustive, and gated service stations respectively. At a station i which uses either the non-exhaustive or the semi-exhaustive service discipline, the switchover time Lij (which arises when there is service at station i) has mean and second moment yij and 2), respectively, and the switchover time Sij (which arises when there is no service at station i) has mean and second moment aij and t(2), respectively. We assume that yij > aij for all i,j. At stations which adopt the exhaustive or the gated service disciplines the switchover time to station j is Sij (regardless of whether service is performed at station i or not), with mean and second moment cij and oa), respectively. For ease of exposition we assume that for i E [S, E, G}, the service time is Bi, independent of the station that is polled next. (The analysis extends directly to the case where the service time could depend on the station next visited.) The mean and second moment of Bi are denoted by Ti and T(2) respectively. For i E N, the service time Bij has mean and second moment Pij and p(2 respectively. To analyze the system, we consider the system state at each polling instant. Let (i; n1,..., nM) denote the state of the system at an arbitrary polling instant, where i denotes the station that is currently being polled by the server, and nm, m = 1,..., M, denotes the number of requests present at station m at this instant. In the following discussion, unless otherwise specified, the index for summation is implicitly assumed to range over 1,..., M. (It is also implicit that station M+1 is just station 1.) Since the arrivals at the stations follow independent Poisson processes, it is easily seen 4

that the state of the system at successive polling instants follows a Markov chain. We only consider systems in which for each station k, Xk > 0, and there exists at least one station i * k for which either pik > 0, or eik > 0. Then, if the system is stable, it can be seen that the set of all the possible states observed at polling instants is irreducible. Purely for ease of exposition, we first consider a system in which all the stations adopt the non-exhaustive service discipline, and obtain the generating function of the number of customers present at each station when the server polls station i. This will facilitate the subsequent derivation of the corresponding generating function for the system with a mix of non-exhaustive, semiexhaustive, exhaustive, and gated service stations. When all stations use the non-exhaustive service discipline, the transition probabilities for the Markov chain are obtained as follows. Let Qm(k;t) denote the probability of k arrivals at station m during an interval of length t, and for any random variable U, with distribution function Fu(.), we oo M denote by A {a,..., aM; U} I I [ H Qm(am; t)] dFu(t), the probability that there are ai arrivals at 0 m=l station i; i = 1,...,M, during a time U. Consider a transition from the state (k; x1,..., xM) to the state (i; n,,..., nM), with nm > xm, for m ~ k, and nk > Xk - 1. When xk > 0, the probability of this transition is Pki A{nl-x,...,nk-xk+l,..., nxM-; Bki + Lki), and when xk = 0, the transition probability is eki A {nl-x,..., nk,..., nm-XM; Ski }. Hence, if we let 7(i; nl, n2,..., nM) denote the equilibrium probability that the server polls station i and the state is (i; ni,..., nm) at the polling instant, then this probability is obtained as M 7i(i; n1,...,nM) = k [ 7c(k; Xl,...,xk,..., XM) PkiA{nl-xl,...,nk-Xk+l,...,n(-xM; Bki+ Lki} k=l X:xk>O + X 7(k; Xl,...,X,....,XM) ekiA{nl-xl,..., nk,..., nM-xM; Ski }], (3.1) X:xk=O where the above summations are taken over all feasible values of X=(x,..., XM). Let Pi(n1, n2,..., nM) denote the equilibrium probability that there are nm customers at station m, for m = 1,..., M, when (i.e., given that) station i is polled, and let xi denote the unconditional probability that station i is polled. Note that 7i(i; nl,..., nM) = Pi(n,..., nM) xi. (3.2) Let Z = (zi,...,ZM), and consider the generating function 5

00 00 Fi() i=... Pi(nl,..., nM) z"nl... ZMn. (3.3) nl=O nM=O Substituting in equation (3.1), the expression for 7c(i; n,..., nM) given by equation (3.2), and using equation (3.3), we obtain: 7i Fi(z) = [,tk ) pSki B(ki( (m- nm Zmn))Lki( (m - Am Zm)) k k m m + 7k Fk(O) eki Ski( (n - m Zm))], m where Fk(O) = Fk(zi,...,Zk-l,,Zk+1,...,ZM), and Bki(), Lki(-) and Ski() denote the Laplace Stieltjes transforms (LST) of the service / switchover times, Bki, Lki, and Ski, respectively. Note that Fk(O)l =i is the probability that station k is empty at the instant it is polled. Let qk = Fk(O)l -i, and k = 1 - qk. (3.4) For ease of expression, we denote the state (i; ni,...,nM) by (i; n). If the system is stable then, for at least one station, there will be a non-zero probability that the system is empty at the instant that the server polls this station. Without loss of generality, let station 1 be one such station. We now consider the regeneration epochs at which the server polls station 1 and finds the system empty. We shall refer to the time between two such epochs as a regeneration period and let C(1; 0) denote its expected value. Note that C(1; 0) < oo if the system is stable. Between two visits to state (1; 0), the expected number of visits to state (i; n) is i(i; in) / i(l; 0). Since ni = Y, i(i; n), (the summation is taken over all possible values of n) the expected number of visits to station i during a regeneration period is ni / iC(I; 0). The expected number of requests arriving at station i during a regeneration period is hi C(1; 0), and clearly all these requests are served during this same period of time. Since the server serves exactly one request per visit to station i if it is non-empty at the polling instant, the probability of a service per visit, qi, is thus hi C(l; O)7t(l; 0);i = ~ (3.5) 7li Now consider systems in which all four types of service stations can be present. Let Hk(-), for k E {S, E}, denote the LST of a busy period at station k, that is initiated by a single request. For notational ease, let 6

Bki Bki (B(Xm-mzm)) Lk4i L *i( (m-m Zm)), and Ski S*I (m Zm)) ki ki ( n- hn m m m Adopting the same approach as we used earlier for the system with only non-exhaustive service stations, we obtain the following equation for Pi Fi(z): i FiC() = E [ 7 Fk(Z)-Fk(O) k B L + k Fk(O) eki S] Z [ /I~k Zk P ki Bki L+k F k(0) e ki Ski] keN + [ Fk F(Zk( o)ki Hk( (m - Xm Zm)) Li + 7k Fk(O) eki Si] kE S mok + / 7k Pki Fk(Zi,...,Zk-i,Hk( k (m- X Zm)),Zk+l,..,ZM) Si ke En m + Ad 7k Pki Fk(Zi,...,Zk-i,B( (m-mZm))Zk+,...,ZM) Ski (3.6) keG m Setting z, =... = ZM = 1 in equation (3.6), we get xi = X A k (k Pki + qk eki) + 7 k Pki, (3.7) keN,S k E,G In the above equation, qk, for ke N, is defined by equation (3.5). For a station k which uses the semi-exhaustive service discipline, qk is obtained in an analogous manner as follows. Consider a standard M/G/1 queueing system in which the server is always available to serve customers, and with the same arrival rate and service time distribution as station k in the non-deterministic polling system. Then the busy period initiated by a single arrival in the M/G/1 system has a mean Tk/(l-Xktk). Now, in the non-deterministic polling system, suppose the server finds station k non-empty at the instant it is polled. Since this station adopts the semi-exhaustive service discipline, when the server subsequently leaves the station, the number of requests present there will be exactly one less than the number present at the polling instant. Hence it is easily seen that the expected number of requests served at station k is equal to 1 plus the expected number of requests served during a busy period in the corresponding standard M/G/1 queueing system, i.e., equal to 1 + hktk/(l-kkTk)- Since the expected number of visits to station k during a regeneration period is Ck / XC(1; 0), the expected number of requests served at station k during a regeneration period is qk ( — ) ~k. This is just equal to Xk C(1; 0), 1-ktk 71(1; 0) which is the expected number of arrivals at station k during the regeneration period. Hence we get 7

Xk C(1; 0) 7(1; 0) qk = - k(Xkk), k E S. (3.8) lk As in the non-exhaustive service case, qk = 1 - qk, for k E S. Let i = E PikPik, iEN, Pi = YS ikPik, ie N,S}, (3.9.a) k k and Oi = aikeik, (2) (2) eik; i= 1..,M. (3.9.b) k k Let Ti denote the expected time from the instant that the server polls station i until the instant when the next station is polled. For ieN, the server finds one or more requests waiting at station i with probability qi and in this case the expected time until the next polling instant is given by Ti+cpi. With probability qi, the server finds no requests waiting at station i at the polling instant, in which case the expected time until the next polling instant is given by 0i. Hence, Ti = qi Oi + qi (Ti + (pi); i N. (3.10.a) For ic S, the expected number of requests served per visit is 1/( l-iTi) if station i is non-empty at the polling instant. Hence the expected time until the next polling instant is Ti /(l-kiTi) + (pi with probability qi, and is otherwise 0i with probability qi. So, -i Ti = qiOi + qi [ +(pi]; ieS. (3.10.b) lr-iTi For i e (E, G), the expected number of requests arriving at station i during a regeneration period is Xi C(1; 0), and the expected number of visits to i during this period is Ri / i(l; 0). Hence it follows that the expected amount of time the server spends at i per visit is just Ti Xi C(1; 0) ic(l; 0) / ii. So, Ti = XT. (1i O (0) + Oi. i E {E, G}. (3.10.c) Iti Since the expected number of visits to any station i during a regeneration period is ni / 7c(1; 0), C(1;O) = ETi. (3.11) i c(1; O) 8

Substituting in equation (3.11) the expression for Ti given by equations (3.10.a) through (3.10.c), setting qi = 1 - qi and using equations (3.5) and (3.8) to express qi for i E (N, S}, C(1; ) = E [Xi i C(1; )+ + i C(1; 0) ((Pi -i)] ieN i(1; 0) + E [I Ti C(1; 0) + i 0i + Xi C(1; 0) (1-Xhii) ((Pi -0;)] ieS It(1; O) + [iTi C(1;O) + i i]. iE {E,G] t(1; 0) Collecting terms involving C(1; 0), and setting 5i = i Ti + xi ((i-i ), i e N, (3.12.a) Xi Ti + (1-XiTi) Xi ((pii ), i E S, (3.12.b) XiTi, i {E,G}, (3.12.c) and e =, 6i, (3.12.d) i we obtain sii t(1; O) C(1; O) = 1. (3.13) From equation (3.13) we observe that for C(1; 0) to be non-negative and bounded, we need * < 1. (In addition, we obviously require that 0 < qk < 1, k e {N, S}.) Let Ci = (l; O) C(1; O) / i, (3.14) and set vi = li / ti. (3.15) The term Ci denotes the expected time between two successive visits by the server to station i. We shall refer to C1 as the "cycle time", and the vi's will be referred to as the "visit ratios". Note that by definition, v, = 1. From equations (3.4), (3.5), (3.8), (3.14) and (3.15), we obtain alternate expressions for qk, ke {N, S}, stated as 9

Proposition 3.1: qk = 1 - k Ck = 1 - k C / k, k E N, (3.16.a) 1 - Xk Ck (1-XkTk) = 1 - k C1 (1-xkTk)/ Vk, k E S, (3.16.b) From equations (3.13) through (3.15), an expression for C, is obtained from Proposition 3.2: ~ viei Vi C1 = (3.17) 1-O The conditions for the stability of this system are obtained from the above development as: O < 1, (3.18.a) XkCk < 1, k N, (3.18.b) XkCk(l-Xktk) < 1, k S, (3.18.c) By suitably choosing the parameters pij and eij, we can consider several polling systems of interest. For notational convenience, in the following we set O = S0i. (3.19) i The deterministic service system The corresponding deterministic service system is obtained by setting pi+l = eii+l = 1 for all i. For this system the switchover time from station i (to station i+1) is the same regardless of whether the server performed a service at station i or not. In other words, for i E {N, S}, Ji,i+1 = Yi,i+1, and so Oi = (pi. From equations (3.7) and (3.15), we have vi = vi_1. Hence the visit ratio is the same for all stations and so from equation (3.17) the cycle time is the same for all stations. Since v, = 1 by definition, the resulting cycle time is the well known expression C =. (3.20) 1 - i XTi i The random polling system of Kleinrock and Levy Consider the dispatching rule pij = eij = p. This rule has been studied by Kleinrock and Levy (1988) and specifies that the station next polled by the server is station j with probability p 10

regardless of the station the server is currently at, and whether a service is performed there or not. For this system, equations (3.7) and (3.15) give A vi = vj Pi, j and so Vi /i = V1 / = j, for alli. j Hence, from equation (3.17), A Pi Pi Ci C1 = -A- (3.21) Pi (1 -l) The First-Encountered-First-Served Rule The First-Encountered-First-Served (FEFS) rule has been used by Stone and Fuller (1973) to model the retrieval of records from a rotating drum. This rule provides a natural application for the non-deterministic polling system: consider a system where all the stations use the non-exhaustive service discipline, and for all i, ei,^l = 1 and pii = 0, with the other pij's taking on arbitrary values. Such a policy specifies that the server serves exactly one request at a station if the station is nonempty at the polling instant; otherwise, the server polls the next station in some logical order. The FEFS policy has been used in this manner by Bozer and Srinivasan (1988) to model the unit-load AGV system as a polling system. For this policy we have, from equations (3.7) and (3.15), Vi = vj qj pji + vi_ qi_,, i=1,..,M. (3.22) j (Note that if we set piil = 1, then this is just the deterministic non-exhaustive service system.) Set Ai = E Xj Pji. Using Proposition 3.1, equation (3.22) is rewritten as j vi = Vi + (Aii-) C1. (3.23.a) Continuing to express vi in terms of vi_2,..., V, i vi = (Aj-X-_)C, + v1, i=2,...,M. (3.23.b) j=2 Hence, the cycle time C1 is obtained from Proposition 3.2 and equations (3.22) and (3.23.b) as e C1 = M i (3.24) 1 - - I, S (Aj-ij-=) O i=2 j=2 11

4. Conservation laws and mean waiting times: In this section, we obtain the conservation law for two special cases of the non-deterministic polling system: the case where pij = eij for all i E [N, S), and the case with M=2 but Pij ~ eij for i E {N, S}. Following this, we obtain the individual mean waiting times in a system with a mix of exhaustive and gated service stations, through the solution of O(M3) equations. To obtain the conservation laws, we need the first and second partial derivatives of Fi(z) with respect to j, j = 1,...,M, evaluated at z=l. Let fij aF( ) I=T, = a2) IZ=T, and gij - = F j. - Dzj = 4.1. The conservation law when pij = eij for all stations We first obtain the conservation law for the case where pij = eij for all i e N, S}. Purely for ease of exposition, for all i E {N, S}, we set Lij = Sij, and for i E N, we set Bij =Bi, and E[Bi] = Ti. (Note that with this we have XiTi = 1i for all i.) The extension to the case where Lij # Sij, and where Bij can depend on the next station visited, is straightforward. In order to obtain the first and second partial derivatives of Fk(i) for this system, we need the first and second partial derivatives of Fk(Hk) - Fk(Zi,...,Zk-,Hk( E ( n- m Zm)),Zk+,...,ZM); k E E, mAk and Fk(Bk) - Fk(B)FZl,...,Zk-1,Bk( (m- XZm)),Zk+i,...,ZM); k E G, m evaluated at z=. Let 8(mj) = 1, if m = j, and equal to 0 otherwise. Set 6(m,j) = 1 - 8(m,j). Then the first and second derivatives of Fk(H*) and Fk(B*), evaluated at z=T, are obtained as follows (also refer Takagi 1986). For k e E, Fk(Hk) I= = (fkj + fkj ) (k,j),;zj.1-.k a2Fk(H*) Tk2 a2ZZk) - = fh(2)kjm+ fi+ fX2) + tk2 azja lz=T [f(=^ + l nnh + f2w ^ j) —+ fkkk j km 2 ojmI1-1h (1-kk) Tk(2) + fkk --- k ] 5 (kj) 5(k,m), (1-*k )3 12

and for k e G, aFk(f ) iz=1 = fkj (kj) + fkk j Tk, az-j a2Fk(B) z = f(2)kjm 6(k,j) (kj) + f(2)kkm (k,m) + fkkj (kj))Tk + fkk j Xm k2 + fk Xj m k(2). Let T = {N, S, E, G} and define the indicator function A(j,T) = 1; jeT; = 0; jT. Differentiating equation (3.6) once with respect to j at z=T, we get (note that Fk(O) I -_. = qk) vifij = vk pki [fkj + qk Xj (tk + aki) + qk Xj oki] - vj j Pji A(j ) keN + Vk Pki [fkj + qk Xj ( + + q ki (1 + - ) Vj j Pji A,5) IkES 1-1-j ke5S'"^ l-v-t Tk fjj + Vk Pki [fkj + fkk Xj - + j (ki] -Vj Pji l A(j,E) k~E + Vk Pki [fkj + fkk j'k + j Oki] - vj Pji f A(j,G). (4.1) ke G The term fjj represents the expected number of requests present at station j when the server polls station j. This term is easily obtained for the exhaustive and gated service stations as (also refer Watson 1984 and Takagi 1986): fji Df- = Cj; j EE, (4.2.a) fjj = j Cj; j G. (4.2.b) From equations (3.16), (4.1) and (4.2), noting that A(jN) + A(j,S) + A(j,E) + A(j,G) = 1, we obtain the following expression for fij stated as Proposition 4.1 Vifij = Vkpkifkj + Xj ( (k C1 Tk + Vk Oki)Pki - C1 ji). (4.3) k k Observe that when pij = eij for i E {N, S}, then from equations (3.7) and (3.15), 13

Vi = Vkpki, k i= 1,...,M. (4.4) It may also be observed, from equations (4.3) and (4.4), that we can express fij in terms of f/j as: fij = ij + j Yij, (4.5) where the yij s are constants which need to be determined. From equations (4.3) through (4.5), Vifij = Vk (fjj + j Ykj) Pk + Xj ( (ok Ci + vk Oki) Pki - C Pji) k k = Vi fj + h ( Vk ykj Pki + X (ok Ci + vk Oki) Pki - C Pji)- (4.6) k k Hence, from equations (4.5) and (4.6), we get vi Yij = Vk Ykj Pki + (Ok Cl + Vk Gki) Pki - C1 Pji, i=l,..,M, (4.7.a) k k with vjYii = 0. (4.7.b) For each j, equations (4.7.a) and (4.7.b) form a system of M linear equations in the M unknowns yij, i = 1,...,M, which can be solved to obtain the yij's. The resulting solution can now be used in equation (4.6) to obtain the fij's in terms of fj. Note from equations (4.2.a) and (4.2.b) that for exhaustive and gated stations, the fji terms can be obtained explicitly in terms of the data parameters. This observation will be seen to be key in determining the individual mean waiting times for systems with a mix of exhaustive and gated service stations, in section 4.3. We now differentiate equation (3.6) twice with respect to j and m, and obtain an expression for f(2)ijm in terms of the unknowns f(2)kj; k,j,m = 1,...,M, and the unknowns fkj and gkj, k E {N, S} and j = 1,...,M. Following this, we eliminate all unknowns except for fij, for j e {N, S}, and f(2)ijj, for j E {E,G}, to get one equation in M unknowns. The resulting expression is stated as Proposition 4.2. A detailed derivation of Proposition 4.2 in presented in the Appendix. Proposition 4.2 v^jfjj'jj [L Vmm] v+ [*- VmOm] + (1 —) vjf ( J + (1 —) vjf(2)j 2 jeN j m J jeS (l-j) m v jeE 2j(l-j) jEg 2 - 1 Cl j X(2) + vj 0(2) -(1-,) ~ Oj 0j Ci + Oij ~ Vm Om Ymj 2 j 2 J j j j j m Xj (2) + ~ vjfTjjj + (l-O) ~ TjCl - (l-) t - )jC1. (4.8) j {E,G) m Vj je {NS jE S,E) 2(1-9j) 1 14

Denote, by Wj, the mean waiting time at station j. Lemma 4.3 expresses the unknowns fj: j E {N,S}, and f(2)j j e. E, G}, in terms of the mean waiting times at the stations. The proof of Lemma 4.3 is straightforward and is omitted. (Refer Watson (1984) and Takagi (1986) for analogous expressions in the case of deterministic polling systems.) Lemma 4.3 fj = (xj Wj + 1), j E N, (4.9.a) jlzz.(2) fi = (j j + - 2( )) j S, (4.9.b) 2(1-Qj) f(2)jj Xj2,(2) - = X Wj - 2( j E, (4.9.c) 2 ~ J 2(1-fj)2j f(2)jjj Xj Wj 2f1 - -(l+t) jE G. (4.9.d) 2fj (1 +Oj) Substituting the values given by Lemma 4.3 in equation (4.8), we obtain Lemma 4.4 The conservation law for the non-deterministic polling system with non-exhaustive, semiexhaustive, exhaustive, and gated service stations, where Pij = eij for all stations is: jwj - o J + Wj s -x (1- v-) + (-i) j Wj jefS m je m j m Nm J jS m J je IE,G) 2f'X.'(2' + Vj0(2) + IVj0j + Z IJ((Vm0 i - ~ 5j2E~o + ~ ~Vm + ~i ZJ Z +. (4.10) jLe {c buS,ootE, ex mean jwi 2S m j mmr Lemma 4.4 can be used to obtain, explicitly, the mean waiting times in symmetric systems. Implicitly, these are systems in which all the stations adopt only one of the four service disciplines considered in this paper. Note, however, that symmetry here does not imply that the probabilities Pij need to be the same for all ij, nor that ij be the same for all ij. The only requirement here is that all stations have identical characteristics with respect to each other. This is illustrated in example 4.1 below. 15

Example 4.1 Consider a non-deterministic polling system with 4 stations, with all stations adopting the non-exhaustive service discipline. The data parameters for this system are as follows: Pij = eij = 0.10 0.40 0.300.20 - 0.20 0.10 0.40 0.30 0.30 0.20 0.10 0.40' 0.40 0.30 0.20 0.10 J 0.10 0.30 0.20 - 0.15 0.15 0.10 0.30 0.20 0.20 0.15 0.10 0.30 0.30 0.20 0.15 0.10, All Bij's exponentially distributed, 0.10 0.15 0.20 0.30 - 0.30 0.10 0.15 0.20 Yij = 1ij = 0.20 0.30 0.10 0.15' 0.15 0.20 0.30 0.10 J Xi = [0.3125, 0.3125, 0.3125, 0.31: Lij and Sij i.i.d., exponentially distributed, The derived data parameters for this system are Ti = 0.45, and Oi = (pi = 0.26 for all i. The visit ratio obtained from equation (4.4) is 1.0 for each station, and the cycle time, obtained from equation (3.17) is 1.3639 for each station. The mean waiting time at a station, obtained from equation (4.10) is 2.21124. The random polling system We now consider, as a special case of the conservation law, the random polling system introduced by Kleinrock and Levy (1988). For this system, Pji = i for all j, and so the visit ratios are obtained from equation (4.4) as vi = E vj i. In other words, j vi / Pi Let Xvj = j vj/j, for all ij. (4.11) (4.12) Ki = (ok Cl + Vk ki) i -C Pi. k So, from equations (4.7.a) and (4.7.b), Yij = vkYkj Pi/Vi + Ki/vi k Pk Ykj + K /vi. k Since yjj = 0, we must have (4.13) 16

Pk Ykj = - Kj/Vj, k and so from equations (4.11) and (4.12), Yij = Ki/Vi - Kj /Vj = (i / vi ) Vk(Oki-kj). k Thus, it may be observed that the conservation law for the random polling system does not require the solution of M sets of M linear equations in order to determine the yij's. Remark: Kleinrock and Levy obtain the mean waiting times for the discrete-time, symmetric system with constant service times. Note that the conservation law gives an explicit expression for the mean waiting times for a symmetric random polling system in the continuous-time case, which is very similar to the expression for the mean waiting times obtained by Kleinrock and Levy. U 4.2. The Conservation Law when pij eij We present the conservation law for a system with two stations, for the case where Pij ~ eij. The derivation of the conservation law for the system with more than two stations is a topic for further research. We consider a system where both stations adopt the non-exhaustive service discipline, since this appears to be one of the more complicated systems to analyze when there are only two stations. The conservation law in this case is more difficult to obtain since the gij terms now constitute an additional M2 - M unknowns. (For the case Pij = eij these terms vanished simultaneously resulting in equation 4.1.) From equation (3.6) with M=2, we have 2 viFi(z,,Z2) = [ Vk,Z2Fk(O) B Lk + VkFk(O) eki S ] i=1,2. zk k=l Let Vki = Bk Lk. In the above equations, setting zl=z, and z2=l, we have two equations in the three unknowns Fl(z,l), F2(z,1), and F2(z,O) (note that Fl(0,1) = q1). We can now eliminate F2(z,O) from these two equations, and express F2(z,1) in terms of Fl(z,l) as follows: v2F2(z,1) = VlFl(z,1) a(z) - v q c(z) (4.14) where a(z~ * * * * * - p12V * * * * a(z) = z (p22V2*2 2222 ) + p12V12 p21V - PSVlll p22V22 - p 2 e21S + pl b(z) = z (p21V21 - e21S21 + P22V22 e21S2 - P21V21 e22), c(z) = a(z) + z(p221V*2 elSll - P21V2 e12 S12 + el2S12 e21S21 - e1S1 e22S2 - P22V22 + e22S22 ) 17

An expression for vl Fj(l,z) in terms of v2 F2(1,z) can be obtained in a similar manner. Differentiating equation (4.14) with respect to z, and evaluating it at z=1 gives an expression for f2l in terms of f 1 and the data parameters. (This involves two applications of L'Hospital's rule.) In a similar manner, we can express fl2 in terms of f22 and the data parameters. We now substitute these expressions for f2l and f12 in equation (4.13) and then express fii in terms of Wi, i=1,2, using Proposition 4.3. The resulting expression, obtained after considerable algebraic manipulation, is stated as Lemma 4.5 The conservation law for the non-detenministic polling system with two non-exhaustive service stations and arbitrary Pij and eij values is 2 2 2 2 i Wi vi qi i = ( k E (viqi( + viqi(2)) + i=1 k=l i=1 2 2 kkOj [ (viqipijij + viqieijij)], j = k mod 2 + 1. (4.15) k=l i=l In equation (4.15), we have set (2) = [(2+) + + 2 ij yij] Pij, J = e21 01 + e12 2, T11 = e12 (XT + (1) - P12 01, and 12 = e21 (T2 + P92) - P21 02. Since there are only two stations, it is possible to express the cycle time C1 given by equation (3.17) explicitly in terms of the data parameters as Z C1 = %. (4.16) e21- Xi[(t1-0,)e21+(e1-p 1)02] - T 12 The terms vi qi = vi-.C1, i=1,2, are easily obtained using equations (3.7), (3.15) and (4.16). Although equation (4.15) is valid for only two stations, it is the most general form of the nondeterministic polling systems, and it may be verified that the conservation laws for the deterministic and random polling systems with non-exhaustive service can be obtained as special cases of equation (4.15), by a suitable choice of the data parameters. It is interesting to note that the 18

conservation law for the deterministic and random polling systems with exhaustive service can also be obtained from equation (4.15). The conservation law for the deterministic exhaustive service system is obtained by setting Pii = ei,i+ = 1, Pii = Ti, yii = 0, j = i, (2) = T(2) y(2) = 0, and (2) = (2) to get, after some elementary algebra, the well known expression: 2 0 2 0 2 _ 2 iWi = i t(2) + var(0i) + ( i- i2). (4.17) ~i=1 2(1-0i) i=l1 20 i=i 2(1-) i= The conservation law for the random polling system with exhaustive service can be obtained from equation (4.15) in a similar manner by setting pii = 1, eij = A, ii = Ti, yii = 0, 7ij = i p=(2) -( 2) 2)=0, and <(2) (2). 4.3. Mean Waiting Times: systems with Exhaustive and Gated Service Stations In this section we indicate how the individual mean waiting times may be obtained for nondeterministic polling systems consisting only of Exhaustive and Gated service stations. Differentiating equation (3.6) twice with respect to j and m, setting z=T, and using equations (4.2) and (4.5), we get if(2)ijm = Vk Pki {f(2)kjm + (f(2)kkj ) + f(2)kkm j) - + f(2)kkk j Tm kEE 1-Ok (1- )2 + Vk Pki {f(2)kjm + (f(2)kkj )m + f(2)dkm Xj) Tk+ f(2)kkk Xj Xm Tk2} keG - Vj PAi o) ( ( () f f -2. ) - Vpm Pmi A(mE) g(o0m)( + f(2)mmm l-*j (1-Oj)2 1-m (1-Vm)2 - vj Pji A(j,G) (f(2)jm + f(2)1jjj kTj) - vm Pmi A(m,G) ((jsm)f(2)mj + f(2)mmm j Tm) + Dijm (4.18) where (2)ki Vk (Ykj + Ykm) Dijm X= x m C {, Pki [k ) + + (2i + 0k ki + (v + j) ki + Ck k v + P.Pki[k+)2Lk _ VkJki (+ )] - jiPji - mi Pmi k~E (1-lk)2 - Ji m T(2) C(2) - Pji A(iE) Xj (1- 2 pmi (miE)0m) }m (4.19) (1-*j)2 (1-_n2~ In equation (4.18), the indices i,j, and m range over 1,...,M. Since f(2)ijm = f(2)imj, it can be seen that equation (4.18) thus provides M2(M+1)/2 equations in M2(M+1)/2 unknowns, which can be solved, thereby obtaining the f(2)jj terms and hence the mean waiting times. 19

5. Conclusions In this paper we introduced the non-deterministic polling system. We obtained the cycle times and the stability conditions for this system and developed conservation laws for two special cases: i) where Pij = eij, and ii) for arbitrary Pij and eij values (namely, Pij * eij) in the case of a system with two stations, both using the non-exhaustive service discipline. The mean waiting times were obtained for systems with arbitrary number of stations, where the stations could adopt either the exhaustive or the gated service discipline. The non-deterministic polling system finds application in many situations. It has been used in analyzing material handling systems, and in computer communication networks. Special cases of this system are the well-known deterministic exhaustive and non-exhaustive service systems, the Bernoulli schedule system considered by Servi, and the random polling system analyzed by Kleinrock and Levy. There are several topics for future research which need to be addressed. The development of the conservation law for non-deterministic polling systems should foster interest in obtaining approximations for mean waiting times using these laws. The conservation law for arbitrary Pij and eij values still remains an open issue for systems with more than two stations.1 1 The author thanks Jhitti Chiarawongse for his valuable suggestions which considerably helped in the presentation of this paper. The very useful comments and suggestions from the anonymous referees are much appreciated. 20

Appendix: Proof of Proposition 4.2 Note: Purely for clarity, we present the derivation for a system with non-exhaustive, exhaustive, and gated service stations. This will indicate how the derivation can, in fact, extend to consider several other service disciplines. For this system, we rewrite proposition 4.2 as follows: X ftj1 [Xmev-] + (1 - ) Xvj f(2)jjj 2+ (1-h) vj f2)ml+ svj f /i MIjj - ^ I + (-) +'-o) jeN J m jeE jeG, C, 2 j (2) C, + O j vjC + v, j m j 0j C, J J J J m j Vm0m ~'j X(~) + fj (1-) ZJjC1- (1-)S j -cj (A.1) jeE,G m jeN Proof: Differentiating equation (3.6) twice with respect to j and m, and summing over all i, at z=I we get X vif(2)ijm = vkf(2jm + Xm Qj + Xj Qm + Kjm - Vj AN) (fjm- gjm) -Vm A(mN) (fmj - gmj) i k - vj A(E) ( jm + f()jjj j),Vm A(mE) (j,m)( f(2) + f(2)mTm 1-Oj W(1-Oj)2 1 -re(1-m)2 -vj A(j,G) ( f(2)jm + f(2)ii mnj ) - Vm A(m,G) (f(2)mmm Xj Tm + 6(jm)f(2)mmj), (A.2) where nj = ~ vk(fkj(Tk+k) - gkj tk) + S Vk(fkjOk + k f(2kkj) + Vk(fkjek + tkf(2)kkj), (A.3) keN keE 1-Ok keG and Kjm = hX [F- Njm + vk f(2)kkk -k2 + vk f(2)kkk 2 ] + 2A(j,N) (j,m) jC1, (A.4) k~E (1-Ok)2 keG with r = [kC(r(k2) + 2OkTk) + Vk () + ( XkC1() (A.5) /'K k ke k (1 —k)2 and Njm = (Tj + j) Ci A(jN) + (Tm + Om) C1 A(m,N) + ( - j + Oj ) C (,AE) (1-j)2 _(2) + (6(j,m) m )Xm + 0m) C, A(mE) + A(j,G) 0j C1 + A(m,G) Om C. (A.6) (1-5m)2 21

From equation (A.2) we get 0 = Qj +Xj m + Kjnm-vj AO(N) (fjm- gm)-Vm A(mN) (fmj-gmj) - vA, )(f + _) f(2)n )__ _ - vj AG(jE) ( f(2)j ) m A(mE) (jm)( + f(2)jjj ) m (mE) (jm)( +f()mmm ) 1-Oj (1-Oj)2 1-(1-m)2 - vj A(,G) ( f(2jm + f(2)ij mj ) - Vm A(m,G) (f(2)mm hj Tm + 8(j,m)f(2)mmj). (A.7) Consider the case where m = j. Note that forj E N, gj = 0. So, from equation (A.7), 2 Xj 2j - tj + Ki = O, where (A.8) 4j = 2vj fj; j E N, (A.9.a) v f(2)jjj j e E, (A.9.b) (1-j)2 vj f(2)ij (2 *j + 1); j G, (A.9.c) We see that Qj can be expressed, from equation (A.8) as Qj = 4j / 2Xj - Kjii / 2Xj. Set aj = k fkj (k + Ok) + Vk fkj Ok - + Kj (A.10) kEN kEE,G 2 2j 2j So, from equations (A.3), (A.8) and (A.10), we can write aj = Vk k gkj - Vk f(2)kkj - - - Vkf()kkj Tk (A.11) kEN kEE keG Again, from equation (A.7), setting bjm = Vj A(jN) fjm + Vm A(mN) fmj + vj A(j,G) f(2)jjj XmXj + Vm A(m,G) f(2)mm Xj Tm + Vj A(j,E) f(2)jjj + vm A(m,E) 6(j,m) f(2)mmm -Xjm Qj- - Xj Q m - Kjm (lOi3) (1-5m)2 we can write bjn = vj A(jN) gjm + Vm A(mN) gmj - vj A(j,G) f(2)jjm - f(2). I f(2) - Vm A(m,G) Oi) f(2)mmj - Vj AE) fn - vm A(mE) (jsn) m (A. 12) 1-Oj 1-O5m 22

From equations (A. 11) and (A. 12), we observe that ~jt a i Xtj Tmjbjm - m j m>j vI f j iii j~E 1-Oj ~ j2 Vj f(2. jeG (A.13) So, from equation (A.13), after some elementary algebraic manipulation, we get x C Vm Omrj fmj - m j (1-1O)}Tj vj f jeN i - (1-') r(i vj f(2)jii jEE 2Xj (1-0j) - (1-O)'j Vj f(2)jjj (1 +j) jeG 2Xj +- + (1-0) jNC, jeN + Tj Cj, - (1-O) i - ii jeN J Z- Z 2 =0. m j (A. 14) Using equation (A.6), we can express i j 2 J = txieiOi + xij i J jeN + 2 j(2), jEE 2(1-Oj)2 (A.15) and v5j 1mNj m 2 2 2 J X. T (2) {o [X j oje+ o j TZj ~ ~) i i jEN jEE (1-E J)2.j'T (2) j6E 2(1-E-j)2 (A. 16) Substituting, in (A. 14), the values for fmj in terms of fj, as given by equation (4.5), and using equations (A.5), (A.15) and (A. 16), we get the desired result. U 23

REFERENCES Baker, J.E., and Rubin, I.(1987), "Polling with a general-service order table," IEEE Transactions on Communications, v COM-35, no 3, 1987, pp. 283-288. Boxma, O.J., and Groenendijk, W.P.(1987a), "Pseudo-conservation laws in cyclic-service systems," Journal of Applied Probability, v 24, 1987, pp. 949-964. Boxma, O.J., and Groenendijk, W.P.(1987b), "Two queues with alternating service and switching times," Rep. OS-R8712, Centre for Mathematics and Computer Science, Amsterdam. Boxma, O.J., and Meister, B. (1987), "Waiting-time approximations in multi-queue systems with cyclic service," Performance Evaluation, vol 7, 1987, pp.59-70. Boxma, O.J., Groenendijk, W.P., and Weststrate, J.A. (1988), "A pseudo-conservation law for service systems with a polling table," Rep. OS-R8813, Centre for Mathematics and Computer Science, Amsterdam. Boxma, O.J., and Weststrate, J.A. (1989), "Waiting times in polling systems with Markovian server routing," Rep. BS-R8905, Centre for Mathematics and Computer Science, Amsterdam. Bozer, Y.A., and Srinivasan, M.M.(1988), "Tandem configurations for automated guided vehicle systems and the analysis of single vehicle loops," to appear in IIE Transactions. Bux, W., and Truong, H.L. (1983), "Mean-delay approximation for cyclic service queueing systems," Performance Evaluation, v 83, 1983, pp. 187-196. 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. (1972), "Queues with periodic service and changeover times," Operations Research, v 19, no 2, March-April 1972, pp. 440-451. Everitt, D.(1986), "Simple approximations for token rings," IEEE Transactions on Communications, COM-34, no 7, July 1986, pp. 719-721. Ferguson, M.J., and Aminetzah, Y.J.(1985), "Exact results for nonsymmetric token ring systems," IEEE Transactions on Communications, COM-33, no 3, March 1985, pp. 223-231. Fuhrmann, S.W. (1985), "Symmetric queues served in cyclic order," Operations Research Letters, v 4, no 3, October 1985, pp. 139-144. Fuhrmann, S.W., and Wang, Y.T.(1988), "Cyclic service systems with limited service," Performance Evaluation, v 9, 1988, pp. 35-54. Keilson, J., and Servi, L.D., "Oscillating random walk models for GVG/1 vacation systems with Bernoulli schedules," Journal of Applied Probability, v 23, pp. 790-802. 24

Kleinrock, L. (1975), Queueing systems, Volume I: Theory, Wiley, New York, 1975. Kleinrock, L., and Levy, H.(1988), "The analysis of random polling systems," Operations Research, v 36, no 5, September-October 1988, pp. 716-732. Mapp, G.E., and Manfield, D.R.(1986), "Performance analysis of priority polling systems with complex cycles," Proc. International Councilfor Computer Communication 1986, P. Kuehn, Ed., Munich, September 1986, Elsevier, North-Holland, Amsterdam, pp. 583-588. Srinivasan, M.M.(1988), "An approximation for mean waiting times in cyclic server systems with non-exhaustive service," Performance Evaluation, v 9, pp. 17-33. Srinivasan, M.M., and Lee, H.S.(1987), "An analysis of a prioritized polling mechanism for cyclic server systems," Tech. Report 87-6, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, Michigan, January 1987. Stone, H.S., and Fuller, S.H.(1973), "On the near optimality of the shortest-latency-time-first drum Scheduling discipline," Communications of the ACM, v 16, no 6, pp. 352-353. Swartz, G.B.(1980), "Polling in a loop system," Journal of the ACM, v 27, no 1, pp. 42-59. Takagi, H. (1985), "Mean message waiting times in symmetric multi-queue systems with cyclic service," Performance Evaluation, vol 5, 1985, pp. 271-277. Takagi, H. (1986), Analysis of Polling Systems, 1986, The MIT Press, Cambridge, Mass. Takagi, H.(1988), "Queueing analysis of polling models," ACM Computing Surveys, v 20, no 1, 1988, pp. 5-28. Watson, K.S. (1984), "Performance evaluation of cyclic service strategies - a survey," Performance'84, Elsevier Publishers, New York, 1984. Wolff, R.W. (1982), "Poisson arrivals see time averages," Operations Research, v 30, 1982, pp. 223-231. 25

UNIVEF