THE UNIVERSITY OF MICHIGAN INDUSTRY PROGRAM OF THE COLLEGE OF ENGINEERING SINGLE-SERVER QUEUEING SYSTEMS WITH FEEDBACK; Gilles R. Davignon. A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the University of Michigan Department of Industrial and Operations Engineering 1974 April, 1974 IP-855

Ir)

ABSTRACT SINGLE-SERVER QUEUEING SYSTEMS WITH FEEDBACK by Gilles Roland Davignon Chairman: Ralph L. Disney This investigation is concerned with queueing systems in which units may return to the waiting lines for another period of service. Units of different types arrive to the system according to a Markov renewal process. The service process is renewal-type where the probability distribution of service times depends only on the type of unit. After a service completion, the unit either leaves the system or feeds back at the end of the lines according to a stochastic rule. In the case where there are several types of units present at the same time in the system, the service discipline uses priority rules. The objective throughout the dissertation is the characterization of the operating processes: the queue length, the busy cycle, the output process and the departure process. Under stationary conditions, results are of two kinds. In some cases, there exists an equivalence between queueing systems with feedback and queues without feedback. In the case of no such equivalence, queueing systems with feedback are modelled directly. Another objective is to relate queueing systems with feedback to some applications. At present, queueing systems with feedback are used to model computer time-sharing systems. Other applications can be found within health care systems and in the manufacturing industries.

"How can it be that mathematics, being after all a product of human thought independent of experience, is so admirably adapted to the object of reality?" Albert Einstein

To Monique, My Parents and Lea iii

PREFACE This dissertation was stimulated by widespread interest in mathematical modelling as a method. for the solution of operational problems. I came to believe that model-building is to operations research as laboratory experimentation is to physical sciences. For that, I am indebted to several instructors and mentors who contributed to my graduate education at The University of Michigan. It was during repeated informal seminars in the office of Professor Ralph L. Disney that I developed special interests toward waiting-line theory. Professor Disney introduced me to concepts involved in my specialization; his guidance and availability were appreciated throughout my research. Moreover, this dissertation could not have been written without his advice and encouragement. Therefore, my sincerest appreciation and gratitude are extended to Professor Disney. I had several informative discussions with Professors Baum, Hall, and Murty; and I would like to thank them for their assistance. This research was supported in part by the US Office of Naval Research under contracts N00014-67-A-0181-0046(NR 364-071) and N00014-67 -A-0181-0047(NR 042-296). Reproduction in whole or in part is permitted for any purpose of the United States Government. The Industry Program of the College of Engineering at The University of Michigan has provided help in the preparation of this manuscript. In particular, the excellent work of Kathie Reed, who did the typing, is gratefully acknowledged. iv

TABLE OF CONTENTS LIST OF ILLUSTRATIONS..................... vii LIST OF SYMBOLS......................... viii CHAPTER 1. INTRODUCTION........ 1 1.1. Background Remarks................. 1 1.2. Description of the Problem.............. 4 1.3. Literature Review................. 6 1.4. Main Results.................... 8 1.5. Organization................... 10 CHAPTER 2. THE FEEDBACK PROBLEM........ 12 2.1. Assumptions of the Model... 12 2.2. The Existence of an Equivalent System without Feedback. 17 2.3. An Illustration: The M/G/1 Queue with Feedback.. 21 2.4. The Problems of the Waiting Time Process...... 29 2.5. Conclusions.................... 31 CHAPTER 3. THE QUEUEING MODEL... 33 3.1. The Output Process................. 34 3.2. Queue Length Process and Generating Functions.... 54 3.3. The Busy Period................... 63 3.4. Decomposition of the Output Process......... 68 3.5. Conclusions..................... 70 CHAPTER 4. PARTICULAR QUEUEING SYSTEM WITH FEEDBACK..... 71 4.1. Specific Assumptions................ 71 4.2. Stationary Conditions................ 73 4.3. The Busy Period Process............... 82 4.4. The Output Process................ 84 4.5. The Departure Process................ 89 4.6. Applications to Computer Modelling......... 90 4.7. Conclusions..................... 94

TABLE OF CONTENTS (CONT'D) CHAPTER 5. DISCUSSION. 96 5.1. Summary....................... 96 5.2. Future Studies.................... 98 5.3. Related Topics.................... 100 5.4. Concluding Comments................. 101 APPENDIX. SOME DERIVATIONS.................. 103 A.1. System of Generating Functions............. 103 A.2. The Embedded Markov Chain...l........... 106 A.3. A Sub-Class of Arrival Processes........... 116 REFERENCES........................... 120 vi

LIST OF ILLUSTRATIONS Figure Page 1.1. A queueing system with feedback........... 3 2.1. The total service process {Tm}........ 22 m 3.1. The process with an idle period.......... 34 3.2. The process without an idle period.. 35 3.3. Set of arrivals associated with the arrival process.... 36 4.1. Particular queueing system with feedback......... 73 4.2. Round-robin model..................... 91 4.3. Foreground-background model................ 93 A.l. Busy period of type-1 units... 110 A.2. Service time preceding the busy period......... 111 A.3. Busy period without an idle period........... 112 vii

LIST OF SYMBOLS Symbol Definition Page T Arrival epoch of the m-th unit............ 13 Z Type of the m-th arrival. 13 m b Number of types of arrivals........... 13 X Time between the (m-l)-st and m-th arrival.13 m Ahk(-) Transition probabilities of {Z,X }.13 Bh(') Probability distribution of X given Zm l=h..... 13 a Transition probabilities of {Z }.. 13 hk m MRb Markov renewal process over a state space of b elements................ 14 GI General independent arrival process......... 14 Mb Process of b independent Poisson streams....... 14 M Poisson process.................. 14 X Arrival rate of type-c units............. 14 c S Time of the n-th service............... 14 n Z' Type of the unit receiving the n-th service..... 14 n Hc(') Probability distribution of S given Z' = c..... 14 c n n Sc Mean of Sn given Z' = c.............. 14 c n n V Variance of S given Z' = c............ 14 c n n Gb Renewal-type process {S IZ}............14 b n G Renewal service process {S }...... O...... 14 viii

Symbol Definition Page H(') Probability distribution of S............ 14 n t Service completion epoch of the n-th unit..14 n N Vector of queue lengths at t + 0... 14 -l n Nc Queue length of type-c units at t + 0........ 14 n n Y Output status of the n-th unit.. 14 n 6.. Kronecker number (=1 if i = j, =0 otherwise)..15 T Total service time of the m-th departure....... 22 m.i Summation sign for i = 0 to oo..23 f Integral sign for y = 0 to ~............. 23 F Number of feedbacks of the m-th departure..25 m FT(') The probability distribution of the random variable T.25 F (i ) The i-fold convolution of FT(.) with itself.. 25 Vector of queue length just after the m-th departure. 26 v Vector of stationary queue length probabilities for................. 26 FT(') The Laplace-Stieltjes transform of FT(').... 27 T FT() 27 I Length of the m-th idle period........ 28 m B Length of the m-th busy period............ 28 m G(*) Probability distribution of B........... 28 m D Time between the (m-l)-st and m-th departure.... 29 m R Reentry point for fed back units...... 29 W Waiting time of the m-th departure... 29 m V Queueing time of the m-th departure.. 30 m K Type of the last arrival prior to t......... 34 ix

Symbol Definition Page U Time since the last arrival measured from t.34 n m 0 Time between the (m-l)-st and n-th output. 34 n Zb Summation sign for c = 1 to b...........35 c 6(x) Heaviside function (=1 if x > 0, =0 otherwise).... 37 P Matrix of transition probabilities for the queue length process.................... 55 IT Stationary probability vector associated with P... 55 'J Conditional stationary probability vector.. 55 t' Departure epoch of the m-th unit.......... 69 m K' Type of the last arrival prior to t'. 69 m m U' Time since the last arrival measured from t'.69 m m Pv(r) Probability for a type-r unit to take output status v. 72 Pr Probability for a type-r unit to feed back...... 72 Pr Product of Xr by S................. 74 Z Type of the m-th departure... 89 m RR Round-robin model............... 90 FB Foreground-background model.............. 90 qr Quantum of service for type-r units........ 93 Zt Summation of Xk for k = 1 to b........... 116 ac Quotient of Xc by ZX................. 116 c c~~~~~~~~

CHAPTER 1 INTRODUCTION This dissertation explores the characterization of a particular queueing system. In the first section, the framework is established together with the motivation leading to the kind of analysis used. Then, section 1.2 states the problem and enumerates the random processes to be studied. A literature survey follows, establishing the originality of the work. In section 1.4, the main results are stated in relation to the ones already known. The chapter ends with a word on the organization used throughout. 1.1. BACKGROUND REMARKS A queueing network is a collection of service facilities, decomposition switches and recomposition nodes, interrelated by a set of paths which direct the flow of units. The arrivals of units to the network are subjected to random variations. In general, they form a random process. Services are also subjected to random variations. Again, the sequence of service time in each facility is represented by a random process. The behavior of decomposition switches and recomposition nodes can be probabilistic. The main purpose of studying queueing networks is to characterize their behavior through operating processes. There are basically four

operating processes: the queue length process, the departure process, the busy cycle process and the waiting time process. From these operating processes, one is able to obtain operating measures such as means and variances. In the analysis of queueing networks, there are two basic approaches. On one hand, the network is considered as one entity. The object is to characterize the behavior of units throughthe different parts of the network (Benes [1962a,1962b]), On the other hand, the network is first broken down and separated into subnetworks and then each part is studied independently with the understanding that a departure stream from a subnetwork becomes the input stream to another subnetwork. To carry out this analysis, through separation, one needs to characterize explicitly the departure process from every subnetwork. Basically, the separation of a queueing network generates three classes of problems. The first one is a classical queueing theory problem: given the arrival process and the service process, one studies the operating processes of each service facility (Takacs [1962], Saaty [1961], Cohen [1969]). The second group of problems is related to the stochastic decomposition of a stream into several other streams; here one characterizes the decomposed processes (linlar [1965]). The third class of problems analyzes the recomposition of streams; in the case where the streams are independent Markov renewal processes and the recomposition takes the form of a superposition, the problem has been fully analyzed by Cherry [1972].

A particular queueing network or subnetwork obtained by a first separation could be a single server queueing system with a feedback mechanism. In such a subnetwork, units to be served wait in front of the server and are given service one by one according to a service discipline. After being served, units encounter the feedback mechanism, which either recycles the unit for another service or discharges it into the departure stream. The feedback mechanism is considered to be a stochastic decomposition switch. Figure 1l1 illustrates the situation. feedback process arrival input queues server processA process B process feedback mechanism superposition node Figure 1.1. A queueing system with feedback There are several levels of complexity among feedback mechanisms. The simplest one is a Bernoulli switch, where the probability for a unit to receive another service is independent of any other event. The next level of difficulty is a Markovian switch, where the probability for a unit to feed back or not depends only on whether or not the previous unit fed back or not. Other levels of complexity are such that the decision whether or not to feed back a particular unit is based on the increments in the queue length, the amount of service the unit has just received and possibly the type of unit being switched. Possibly, there are two ways to analyze queueing systems with feedback. On one hand, there might exist an "equivalence" between

a queueing system with feedback and a queue without feedback. In this case, one could use known results to analyze the system completely. This possibility will be fully explored in chapter 2. On the other hand, one could analyze the queueing system with feedback directly. This approach will be taken in chapter 3. The main objective throughout this dissertation is the characterization of the operating processes of a queueing system with feedback. This objective is motivated mainly from a queueing network point of view. If one separates a network into subnetworks, one needs to characterize the flow in every subnetwork in order to say something about the flow throughout the network. A secondary objective is to relate queueing systems with feedback to some applications. At present, queueing systems with feedback are often used to model computer time-sharing systems. Other applications can be found within health care systems and in the manufacturing industries. 1.2. DESCRIPTION OF THE PROBLEM Figure 1.1 illustrates the flow of units through a queueing system with feedback and the following discussion refers to that figure. A formal description of the problem will be given in section 2.1. The arrival process is assumed to be a Markov renewal process over a finite state space. Two particular cases of this arrival process

will be considered: the case when there is only one type of unit and the case when the arrival process is composed of independent Poisson streams. The sequence of service times is assumed to form a renewal process for each type of unit. This will be defined to form a renewaltype process. Moreover, the times to perform services are independent of any other event. Units are given service one by one. Upon completion of service, units join the output stream. While a unit is in the output stream, one would refer to it as an output. At feedback mechanism B, a decision is made whether or not to feed back a particular output. This decision is stochastic in nature and depends on the increments in the queue length, the amount of service the unit has just received, the type of unit and whether the previous output had fed back or not. If an output does feed back, it joins the feedback stream and immediately reenters the queues at recomposition node A. If the output does not feed back, it joins the departure stream and leaves the system forever. When the output leaves the system, it is referred to as a departure. The feedback is assumed to be instantaneous; that is, there is no delay between the decision to feed back at B and the reentry at A. Moreover, since service times are considered to form a renewal-type process, it follows that the output epochs are convenient places to embed the random processes describing the behavior of the-system.

This study is concerned with the characterization of the flow of units, under stationary conditions, through the queueing system described above. More specifically, the output process is fully analyzed. From the output process, one studies the queue length process, the departure process and the feedback processes. The busy cycle process is also investigated. The waiting time process presents special difficulties, which are discussed in section 2.4. 1.3. LITERATURE REVIEW The concept of a queue with feedback was introduced by Takacs [1963]. Queueing systems with feedback were also treated earlier, but in very special cases. This was the case for Finch [1959] and Jackson [1957,1963]. In fact, published research on queues with feedback has been very limited in the area of queueing theory. Models of computer time-sharing systems are applications where studies of queues with feedback have generated interest in the last eight years. Early studies of queueing networks which include feedback seem to be those of Jackson [1957,1963]. Considering a finite number of service facilities, arrivals are assumed to be Poisson streams, with possible arrivals to each service facility from outside the network. The service times are exponentially distributed with parameter u. for server i. All waiting capacities are infinite. When a unit completes its service at service facility i, it is sent to service facility j with probability Pi. independent of any history of the network, For i=j, the service facility i can be considered a particular case of our

queueing system with Bernoulli feedback. In his paper, Jackson [1963] considers the arrival parameters and service parameters of each service facility to depend on the state of that server. It is shown that the state probabilities for the network can be written as the product of the state probabilities for each service facility as though each service facility had Poisson arrivals and exponential service times. This is not surprising, due to Burke's theorem (Burke [1956]) and the superposition and decomposition of Poisson streams. In this model, the forgetfulness property of the exponential distribution plays an important role. Finch [1959] describes cyclic queues in which units pass in turn through a series of servers to return to the initial server. Moreover, there is an upper limit on the number of units in the system at any time. The concept of feedback is related to this system in two different ways. First, there is the terminal feedback; that is, when a unit completes service at the last server there is a probability p. that the unit will return to the queue at the j-th server. Second, there is the service feedback; that is, on completion of a service at station j, there is a probability pj that the unit will return to the queue at the j-th server. In the analysis of these two kinds of feedback, Finch assumes Poisson arrivals and exponential service times. Under stationary conditions, he finds the joint probability of the number of units at every service stage. The fundamental assumption of his paper is that the p.'s are independent of the state of the system and of any event.

A somewhat more theoretical development is made by Takacs [1963], who considers a general probability distribution for service times and Poisson arrivals. Basically, the model considered by Takacs is the one shown in figure 1.1. Again, it is assumed that after being served, each unit either feeds back with probability p or departs with probability 1-p. Moreover, these events are independent of any event involved. In his paper, Takacs finds the stationary distribution of the queue length and the conditions under which such a distribution exists. In the area of computer systems, several models have been proposed, two of which are particular cases of queueing systems with feedback: round-robin models and foregound-background models. McKinney [1969], Chang [1970] and more recently Wyszewianski [1974] reviewed in detail the literature concerning these models. It suffices to glance through the Journal of ACM from 1971 to 1973 to be convinced that these models appear in literature with increasing frequency. An extended discussion of them will be presented in section 4.6. 1.4. MAIN RESULTS The literature review of the preceding section raises two considerations. First, published reports on queueing systems with a feedback mechanism are rare outside of the computing literature. Second, the structuring models needed to characterize operating processes of queueing systems with feedback are also nonexistent. Therefore, this

dissertation proposes a unifying structure that can be used to analyze queueing systems with feedback. Moreover, the structure can be used to treat priority queues, queueing systems with complex feedback mechanism and more importantly, departure processes from these queueing. systems. Necessary, and sufficient conditions are found for the existence of an "equivalent" single-server queueing system without feedback. Moreover, it is found that there is only a limited number of queueing systems with feedback for which there are such equivalent systems. The queueing model studied by Takacs [1963] is one such system. The model for queueing systems with feedback developed in this dissertation is a generalization of both the arrival process and the feedback mechanism of the model studied by Takacs [1963]. Moreover, by particularizing our results, we obtain Takacs results and some new ones: the busy cycle process and the output process, as well as the departure process. The importance of studying departure processes has been stressed in section 1.1. One may recall that the characterization of the departure process from queueing systems is useful in the study of queueing networks. Moreover, it is found that the characterization obtained here is a generalization of results published by Vlach [1969]. This dissertation presents also a model for priority queues when the arrival process is composed of independent Poisson streams. Hence, by particularizing the model studied here to the no feedback case, we obtain results previously found by Miller [1960]. Furthermore, our model gives a characterization of the departure process for priority queues, which appears to be new.

10 The structure of the feedback mechanism in our model is such that it can be particularized to study some computer time-sharing systems. Among these models for computer time-sharing systems there are the round-robin feedback studied by Coffman [1968] and the foregroundbackground feedback (McKinney [1969]). From the formulation presented here, we obtain the same results previously found by Coffman and some new ones. 1.5. ORGANIZATION This dissertation is organized into five chapters and one Appendix. Each chapter is divided into sections. In order to keep track of chapters and sections, a two-part numbering scheme n.m is used throughout where n indicates the chapter and m the section. The Appendix is divided into two sections, labelled A.1 and A.2. Definitions, lemmas, propositions, remarks and theorems are numbered consecutively in each chapter and the Appendix. The numbering scheme n.p where n indicates the chapter or the Appendix and p the entity in question is used. Figures are also numbered consecutively in each chapter and the Appendix with the same numbering scheme. Equations, which appear solely in the statement of a theorem or in its proof, are referenced, whenever needed, by a number enclosed within parentheses, appearing at the left of the equations. Assumptions for the queueing model are identified by the capital letters A through H; they are listed in section 2.1 and are referred to by these letters. Bibliographic references are indicated by the name of the author followed by the

11 year of publication enclosed within brackets. In the case of multiple publications in a single year, a lower case letter is used as a further identifier. In chapter 2, the problem of queueing systems with feedback is formally introduced. After a description of the assumptions, the question of the existence of an "equivalent" system without feedback is addressed. An illustration of a case where such an equivalence exists is presented. The problems raised in studying the waiting time process are discussed. In the last section, the random processes to be studied further are described. In chapter 3, analysis of queueing systems with a general feedback mechanism is presented. First, the output process is explored at length and several known processes are studied from it. Second, the important particular case in which the arrival process is composed of independent Poisson streams is studied. A method to determine the stationary conditions is given. Chapter 4 illustrates the method introduced in the preceding chapter for two independent Poisson streams. Results concerning the round-robin feedback and the foreground-background feedback are given. In chapter 5, a summary of the results obtained on queueing systems with feedback is presented. Future studies and related topics are briefly discussed. Finally, the dissertation concludes on the value of the research.

CHAPTER 2 THE FEEDBACK PROBLEM This chapter formally introduces the feedback problem encountered in queueing systems. The concept of feedback that was introduced in chapter 1 is formally defined together with the arrival process and the service process. In the first section, basic assumptions about the queueing model are stated. Section 2.2 investigates the existence of an equivalent queueing system without feedback. It is shown that such an equivalence exists for only a limited number of queueing systems. As will be shown, the M/G/1 queue with state-dependent feedback is an example for which there exists an equivalent queueing system without feedback. A difficult problem in the analysis of queueing system with feedback is the waiting time process. In section 2.4, the problem is discussed for a somewhat restricted case. The chapter concludes with a summary of the random processes to be analyzed in chapter 3. 2.1. ASSUMPTIONS OF THE MODEL For the model to be considered in this dissertation, arrivals are distinguished on the basis of their type. Different types of units receive different services and will be subject to different stochastic 12

13 feedback decisions. It is possible, therefore, to consider the queueing system as having several queues served by a single server, each queue being formed by units of the same type in the order of their arrival. For convenience, only a finite number of types is considered. A service discipline is established by using the type of arrivals as a priority rule. Figure 1.1 gives an illustration of the flow of units through the queueing system with feedback. Because of the stochastic switch, the order of units in the arrival stream is not necessarily the same as in the input stream. This observation also holds for the departure stream. Furthermore, the decision whether or not to feed back a unit after its service suggests the sequence of service completion epochs as convenient places to embed the operating processes. The basic notations and assump-. tions of the queueing system with feedback follow. Units arrive at epochs T<T2< <T <.... If Z denotes the type of the m-th arrival and X = T -T represents the time between the m m m-l (m-l)-st and the m-th arrivals with TO = 0, then the sequence {Zm,X } will be called the arrival process. The different types of arrivals form the state space of the arrival process. Assumption A. The arrival process {Zm,X } is a Markov renewal process m m over the ergodic state space {1,2,...,b}. Moreover, the stationary transition probability, Ahk(x) = Pr{Zm=k,Xm<xiZ -= hi is such that Ak(x) exists for all x>O, Ak(O+) = 0 and ZkAhk() = 1 for h,k=1,2,...,b. Let the probability distribution of the interarrival time X be m Bh(x) = bAhkb(x) for h = 1,2,..,b. Furthermore, let ahk = Ahk(o) be the transition probabilities of the underlying Markov chain {Z }.

14 We denote this arrival process by MRb. There are two important particular cases of the above arrival process. In the case b=l, there is only one type of arrival and the arrival process is then renewal (GI). There is also the case where the arrival process is the superposition of b independent Poisson streams with parameters Ak(k=1,2,...,b); one denotes this arrival process by Mb. Let S be the length of the n-th service and Z' be the type of n n the unit which received the n-th service. The sequence {S jZ'} will be called the service process. Assumption B. The service process {S |Z'} is a renewal-type sequence n n over the state space {1,2,...b}. Moreover, the stationary probability, H (x) = Pr{S <xlZ'=r}, is such that H (0+) = 0, H.(o) = 1, r n- n r r Sr = E[S nZ'=r]<o and V = V[S IZ'=r]<~ for r = 1,2,...,b. r n n r n n One denotes the service process by Gb. When b=l, the service process becomes renewal (G) and the probability distribution is then noted by H(-). Let service completions occur at epochs tl<t2<...<t <... n {t } is the sequence of output epochs. One defines N = N(t +0) to be n — n - n the vector of queue lengths at t +0, the entry N- denotes the number of n n type-c units in the system, excluding the fed back unit whenever the n-th output feeds back. Associated with the n-th output, the random variable Y is defined n as follows: if the n-th output departs; n units (v=1,2,...,b).

15 The value that Y takes is referred to as the output status of the n-th output. The state of the system at t +0 is Y = u and N = i = [i ], n n - - c with the understanding that the queue length of type-c units is 6 +i UC C The sequence {Y }is called the switching process and is determined by the following Assumption C. The output status depends only on the previous output status, the increments in the queue lengths, the amount of service the unit has just received and the type of unit receiving the service. Moreover, P0v (J'r;y) if u=O &i=, Pr{=vY vY=U'N=jN =iS y,Z'=r}= n- -n -n- 1 -n n pu(e,r;y) otherwise; where e = [j +6 -6 -i ], are such that the following three conditions are satisfied: 1. p 0(0,r;y)>0 for some y>0, u=0,1,...,b and r=l,2,...,b; 2. for every vector e, there exists a vector d>e such that p 00(d,r;y)>O for some y>O and r=l,2,...,b; 3. for every v=1,2,...,b, there exists a vector e 2 0 such that p0v(e,r;y)>0 for some y>O and r=l,2,...,b. Condition 1 implies that there is a non-zero probability of a unit departing. Otherwise, every unit would feed back. If p u0(e,r;y)=l for every u,e,r,y, one obtains queueing systems without feedback. Without loss of generality, take one vector e, in condition 3, to be

16 the zero vector; in which case, conditions 1, 2 and 3 guarantee that every state of the process will be visited. To be explicit, one would use the term state-dependent feedback to mean a dependency on the queue lengths N and N. Otherwise, -n-l -n the term feedback would mean that there might be or not a dependency on these queue lengths. Concerning the time between service completions and the reentry of a fed back unit, one states Assumption D. There is no delay in feeding back a unit. After a service completion, the next unit to be served is chosen according to the following service discipline. Assumption E. Whenever there is no unit in the system just after the (n-l)-st output, the server remains idle until the first arrival; which arrival determines the type of unit receiving the n-th service, Z'. In the case where the system does not become empty after t n nthe next unit to be served is chosen from the non-empty queue having the lowest type index; that is, Z'=r where r=min{c:6 +i >0,c=1,2,...,b}. n uc c Among units of the same type, the service discipline is first-come firstserved. The additional three assumptions are also made. Assumption F. At epoch t0, a service completion occurred and the corresponding unit left the system. Moreover, the initial queue length probabilities are given to be Pr{N=iIY0=u} = 6u0q0(i). Assumption G. There exists an infinite capacity for each type of unit in front of the server.

17 Assumption H. There is only one server. From now on, the queueing system with feedback to be referred to throughout this dissertation is the model which satisfies the above assumptions. Therefore, one states Definition 2.1. An Mb /Gb/1 queue with feedback is a queueing system satisfying assumptions A through H. 2.2. THE EXISTENCE OF AN EQUIVALENT QUEUEING SYSTEM WITHOUT FEEDBACK Given the MRb/Gb/l queues with feedback defined in section 2.1, one would like to study the existence of an equivalent queueing system without feedback such that operating processes of the former system and operating processes of the latter system give the same measures. As will be shown, the existence of such an equivalent queueing system without feedback depends first on the operating process itself and second on the particular queueing system with feedback. If the operating process is the queue length process or the busy cycle process or the departure process, then this process is independent of the service discipline stated in assumption E and fed back units may be given service priority. Hence, the service process and the feedback mechanism can be joined together to constitute a new service facility. In this way, one can produce a queueing system without feedback which is equivalent to the feedback case with respect to these operating processes. Two definitions are now in order. Definition 2.2. A G-server queue is a queueing system such that the sequence of service times form a renewal process and is independent of the arrival process.

18 Definition 2.3. Two queueing systems are said to be equivalent with respect to an operating process whenever the operating process of one can be derived from the operating process of the other. In the case where there exists an equivalent queueing system without feedback, we will say that there exists a transformation which converts a given operating process for a queueing system with feedback into a corresponding operating process for the equivalent queueing system without feedback. When the operating process is the waiting time process, it does not appear possible to obtain an equivalent queueing system without feedback. In section 2.4, the waiting time process for a particular queueing system with feedback will be studied to further illustrate this point. In the case where a transformation does exist, it is explicitly characterized by finding the probability distribution of total service times. The total service time is the sum of all service times received by a single unit. This characterizes the service process of the equivalent queueing system without feedback. Therefore, one can study operating processes of this equivalent system and the results can be transformed back in terms of the service process and the feedback mechanism of the original queueing system. However, this method does not give any properties for either the output process or the feedback process. In section 2.3, an illustration is presented and the transformation is explicitly found.

19 To characterize the total service times of the new service facility, one needs to convolve several service times which depends on the type of unit being served. In turn, the type of unit might also be an output status. Furthermore, the output status might depend on the type of unit being served as well as on the increment in the queue lengths. Therefore, one can state the following important result. Therorem 2.4. When the operating process is either the queue length, the busy cycle or the departure process; any MRb/Gb/l queue with feedback is equivalent to a G-sever queue without feedback if and only if all of the following three conditions are satisfied: 1. the service process is independent of the type of unit being served, that is Pr{S <xlZ'=r} = Pr{S <x}; n- n n2. the feedback mechanism is independent of the type of unit to be switched, that is Pf{Y =vIYn lu,N 11i,N =j,S =y,Z=r} = Pr{Y n=vi Yn N-u,N-1_1 =in= Sy}; 3. either a) the feedback mechanism is independent of N n and N, or b) the arrival process is Nb for b>l. Since one needs heavy notations and tools that have not been introduced yet to prove theorem 2.4, its proof will be delayed until

20 section 3.2, when the queue length process will be analyzed. The remainder of this section is devoted to an exploration of some of the consequences of the theorem. Corollary 2.5. In the class of GI/G/1 queues with state-dependent feedback, only the queueing system with Poisson arrivals can be transformed. Proof: Since the arrival process of GI/G/1 queues has only one type of units, the first two conditions of theorem 2.4 are always satisfied. From the definition of state-dependent feedback, the feedback mechanism is dependent on Nnl and N; therefore the arrival process must be a Poisson stream. Q.E.D. Corollary 2.6. In the class of MR/Gb/l queues with feedback depending on the type of units and such that bZl, there exist no transformation. Proof: This is immediate from theorem 2.4. Q.E.D. In the previous corollaries, it is found that the class of queues with feedback for which there exists an equivalent queueing system without feedback is small. Even in the case where there exists an equivalent queueing system without feedback, there are reasons to justify a direct method of analysis, where the service process and the feedback mechanism are kept separate. A direct method of analysis will permit one to study the output process and the feedback processes, while the method of

21 equivalent queueing systems without feedback will give no information on these processes. For example, the mean and variance of times between outputs may be important to design a particular system. Furthermore, to characterize completely the input process one needs to know the feedback process, which together with the arrival process and the superposition node (figure 1.1) determine the input process. A formal analysis of MRb/Gb/l queues with feedback, following the direct method, will be presented in chapter 3. In the next section an illustration is given of how a particular queueing system with feedback is transformed into queues without feedback. Results on three operating processes are derived. Later, they will be compared with the same result obtained using the direct analysis of chapter 3. Since the waiting time process is much more difficult, a discussion of it is presented in section 2.4 of this chapter. Thereafter, the waiting time process is dismissed for the rest of the dissertation. 2.3. AN ILLUSTRATION: THE M/G/1 QUEUE WITH FEEDBACK As an indication on how a transformation can be carried out, we consider the M/G/1 queue with the state-dependent feedback mechanism stated in assumption C. That feedback mechanism will be defined as: I PoV(j;Y) if u+i = 0, Pr{Y=vYn 1=UNl,Ni=jS, = y} = p (k;y) if u+i > 0; UV

22 where k = j+l-u-i; for u,v = 0,1 and i,j = 0,1,.... The arrival process is assumed to be Poisson with parameter A. Whenever one considers the queue length process, the busy cycle process and the departure process, the service discipline stated in assumption E has no effect. Therefore, one can consider this queueing system with the above feedback where the service is given to fed back units in a continuous sequence of service periods. That is, output feeds back at the head of the line. Since there is no feedback delay, another period of service is given to the same unit immediately. This feedback procedure continues until the unit departs. When the output becomes a departure, the next unit to be served is selected under the service discipline stated in assumption E. Hence, if one denotes by T the total service m time associated with the m-th departure, {T } would be called the total service time process. m jS ~- - - --- + — $ Sn+1- -S -~ n n+l n+k Y Y Y Y n-l n n+l n+k-l n+k Figure 2.1. The total service process {T } m In figure 2.1, the underlying service process is the sequence {S } introduced in assumption B, while Y is associated with the output: n n either a departure (+) or a feedback (p).

23 Propostition 2.7. For the M/G/1 queue with the above state-dependent feedback mechanism, the sequence {Y } is a Markov process over the state n space {0,1}. Proof: Since there is only one type of arrival, the range of each Y is {0,1}. The Markov property is established as follows: n (1) Pr{Y =vIY1=uY,.. -= Z.f Pr{Y =v,N l=iNn =j,S y nl=u. dy i j y n n-ln n n-l u, ZZ.f Pr{Y =vjY =u,.;N =iN =j,S =y} i j y n n-l ' n-l ' n n *Pr{N =jY _U,; =iS y};Pr{N l=iY =u, }Pr{S =yYn ==U u. dy. n-l n-l ''n n-l. dy Now, applying assumptions A, B, and C, one obtains (2) = Zijlf Pr{Y v n_l u,N =i,N j,S =y} ~(2) i j y {n VYn-l uNnl iNn= ny} 'Pr{N =jiY u,N =iS =y} n n-l=u n-l n ~Pr{N n_ IYn-2 }Pr{Sn=y}dy, where p (j;y) if u+i=O, Pr{Y =VJYn uN =iN =jS =y}= n nl 'n-1 'n n p(j+l-u-i;y) if u+i>O; and F ]! if u+i=O; Pr{N jIlY =u,N =iS y}=( 0 if j+l<u+i#0; -n n-i n-i n 1)! i p flv.n)

24 Then, equation (2) can be evaluated and it follows that n nl-' n-2' n n ' Pr{YvjYluY 2,..* = Pr{Y=vIY =u}, for u,v=O,l; which establishes the Markovian property. Q.E.D. Corollary 2.8. The stationary transition probabilities for the Markov chain {Y I are given by n Pr{Y =VYn=u} guv where f = (j;y)e (y) dH(y) guv j 3yP uv dH(y) for u,v = 0,1. Proof: Using equation (2) of proposition 2.7, this is immediate. Q.E.D. Proposition 2.9. The total service process {T } is a renewal process m with the stationary distribution k (k+2) () FT(x) = 00H(x)+g0110 ZkgllH ( with the mean E[T] = S(l+g01/glO), and the variance — (] 2(~+g01/g10)fg)+(ig1 )-2 /210 V[T] = V(l+g01/g10)+g01 (2-g10-g01)S /g10

25 Proof: The service process {S } is assumed.to form a renewal process, n hence by adding a random number of service periods Sn, to get T, n m the renewal property is still retained and {T } is a renewal process m with stationary distribution. In order to find the probability distribution of Tm let F be the number of feedbacks of the m-th m m departure. First, the probability of F can be written as m (1) Pr{F =k Pr{F =kY == Pr{+k=1, Y Y nl Ynl=0} m n+k n+k-1 ' ''' for k =0,1,.... From proposition 2.7 and its corollary, equation (1) becomes i00 if k=0 (2) Pr{F =k = g00 m k-l g01g11 10 f k>l If one denotes by FT(*) the stationary distribution of T, one easily finds (3) FT(x) = ZkPr{T <xIF =k}Pr{F =k}. T k m- m m Now, using the definition of T, together with equation (2), equation m (3) becomes F ('x) = Pfs<k Pr{S +s +. +s <x} T(x) = gPr{S <x}+ Zkg01l 10 r{n+ n+l n+k+l —' or k (k+2) FT (x) = g00H(x)+g01g10ZkgllH (x) Here, H(i)(x) represents the i-fold convolution of H(x) with itself.

26 One obtains the stationary mean and variance from equation (4) in the usual way. Q.E.D. An immediate property of the total service process {T } is the m following Corollary 2.10. In terms of the underlying service process we have the following relationships: S = EN[T] < E[T], V V VN[T] < V[T]; where the subscript N indicates the no feedback case. Now, using proposition 2.7 and its corollary, the operating processes of the M/G/1 queue with state-dependent feedback can be found easily. From classical M/G/1 queueing theory, one has Proposition 2.11. The M/G/1 queue with state-dependent feedback has stationary behavior if and only if XS(l+g01/g10) < i, where g is given in corollary 2.8. Now, if Q denotes the queue length just after a departure, then {Qm} would characterize the queue length process. So, if v(j) denotes the stationary queue length probability, with v = [v(j)] in vector form, then one can state without proof,

27 Proposition 2.12. The probability generating function of the queue length probabilities is JV(O) (-1) -) EjV(j)g = ~<1; where v(O) = 1-AS(l+g01/g10), F*(s g00+(l-g001-g1)H (s) FT(s) = H (s) Re{s}>l. -gllH (s) Proof: Using proposition 2.9 and known results from M/G/1l queues, one easily obtains the desired result. Q.E.D. Corollary 2.13. The steady state probability of an idle system is 1 - AS(i+g0o/gl0). Proof: This is immediate, using Poisson arrivals. Q.E.D. In the particular case where the feedback mechanism is Bernoulli, the above result simplifies to the one found by Takacs [1963]. Using standard methods from the M/G/1 queueing theory, it is possible to find the steady state mean queue length: Corollary 2.14. X2(V[T]+(E[T])2) E[Q] = XE[T] + 2(1-XE[T]) ion 2. where E[T] and-V[T] are given in proposition 2.9.

28 If EN[Q] denoted the mean queue length in the particular case where there is no feedback, one can easily verify the following Corollary 2.15. EN[Q] < E[Q]. Another operating process is the busy cycle process. Each busy cycle is composed of an idle period followed by a busy period. If one denotes by I the time interval between the departure of the m (m-l)-st unit which leaves the system idle and the arrival of the m-th unit, the idle period process {I I form a Poisson process. m Now, if one denotes by B the length of the m-th busy period and m by G(') its probability distribution, one states Proposition 2.16. Under stationary conditions, the Laplace-Stieltjes transform of the probability distribution of busy periods is *e 2 * * g01g10 [H (e)] G (s) = g00H (e) + -g H (e) where e = s+X-%G (s). From proposition 2.16, one easily finds the mean of busy periods to be: S(glo+g) E[B] = g10- XS(g10+go01 A third operating process that can be obtained from the transformed M/G/1l queue with state-dependent feedback is the departure process. From known results together with proposition 2.12 one can state

29 Proposition 2.17. Under stationary conditions, the probability distribution of inter-departure times, Dm, has the following LaplaceStieltjes transform *k g01 01 FD (S) = [1-(Sl+ ----) FT(s)+( -- )FT (s) g10 s T where FT(-) is given in proposition 2.12. T 2.4. THE PROBLEMS OF THE WAITING TIME PROCESS In the waiting time process, the service discipline and any priority rules have a significant effect. In an attempt to illustrate the problems that we encounter with this operating process, we consider the M/G/l queue with the state-dependent feedback defined in section 2.3. In addition to the service discipline stated in assumption E, it is also possible to distinguish between units which have already been fed back and the others. Hence, a priority rule can be designed as follows: a fed back unit rejoins the queue at the point where it will be, at most, the R-th unit in the queue, including the one in service. This priority rule is called "feedback at entry R". A particular case is R = 1, which correponds to the case in which fed back units are given priority. Here, the waiting time is simply the sum of the queueing time and a series of consecutive service times. Hence, if one denotes by W the waiting time of the m-th unit of the m departure stream, it follows that

30 W =V + S +S +...+S m m m1 m2 mF + m where V = queueing time of the m-th departure, m S = service time of the m-th departure at its i-th m. period of service, F = number of feedbacks associated with the m-th departure. m If one denotes by Fw( ) the stationary probability distribution of the waiting time, the following theorem characterizes its LaplaceStieltjes transform. Theorem 2.18. Under stationary conditions, the probability distribustion of the waiting time of units is given by * * * g01g10H (s) Fw(s) = Fv(s)H (s)[g00 + * ]) 1-gYH (s) where FV(.) is the probability distribution of the queueing time in a M/G/1 queue without feedback whose service times distribution is given in proposition 2.9. Proof: Consider the probability distribution of the waiting time W: m (1) FW (x) ZkPr{V +S +..+S <x IF =k}Pr{F =k}. m mF +1 m From equation (2) in proposition 2.9, recall Pr{F =k} = g00 if k 0, m k-l1 g01g11 g10 if k > 1;

31 now by taking the Laplace-Stieltjes transform in equation (1), one obtains J* * * k * k+2 Fw (s) g0 F (s)H (s) + kg01gllg10 (s)[H (s)] n n n Under stationary conditions, the above equation is rewritten into the desired result. Q.E.D. For the case R = co, fed back units are no longer given priority. Here, the waiting time of a particular unit consists of a series of waiting times, each one being the waiting time for a unit to get a period of service. In this case, the determination of the probability distribution of the waiting time is very complex. Nevertheless, for the M/G/1 queue with Markovian feedback, a procedure was developed (Davignon [1972]) to evaluate the probability distribution of the waiting time. Since no closed form for the distribution could be found, it is therefore not instructive to present this procedure here. 2.5. CONCLUSIONS This chapter stated the feedback problem in queueing systems. It was found that only a limited number of queueing systems with feedback can be transformed into queueing systems without feedback. In fact it was shown that the existence of a transformation depends on the operating process used as well as on the particular queueing system under consideration. The condition that the service process

32 is independent of the type of unit, the feedback mechanism is independent of the type of unit and either the arrival process has the forgetfulness property or the feedback mechanism is independent of the queue lengths are necessary and sufficient for the existence of a transformation. Therefore, the M/G/1 queues with state-dependent feedback mechanism can be transformed into G-server queues without feedback; this case was treated as an illustration in section 2.3. In section 2.4, one found the probability distribution of the waiting time in the case where priority is given to the fed back unit. Difficulties with the waiting time process were then pointed out. For the queueing systems with feedback that cannot be transformed, a direct analysis must be carried out. Furthermore, even when the transformation can be carried out there are still reasons to study queues with feedback as such. Among the reasons, one can mention the characterization of the output process as well as the feedback process. In the next chapter, a model for the Mb/Gb/l queues with feedback will be investigated. Results concerning several particular queueing systems will be derived. From the output process, one would obtain the characterization of the queue length process and of the departure process. The busy cycle process will also be investigated.

CHAPTER 3 THE QUEUEING MODEL The feedback problem was introduced in chapter 2. It was then stated that only a small class of queueing systems with feedback can be transformed into queueing systems without feedback. For queueing systems with feedback that cannot be transformed, a direct study must be carried out. Therefore, this chapter contains the analysis of MRb/Gb/l queues with feedback. Assumptions concerning this queueing system are stated in section 2.1. Section 3.1 presents a characterization of the output process together with its main properties. The queue length process is obtained from the output process and is studied in section 3.2. The busy cycle is analyzed in section 3.3. The output process is decomposed by the feedback mechanism into the departure process and feedback processes. It is the object of section 3.4 to investigate these decomposed processes. Throughout the chapter particular cases are mentioned. For instance, when the Markov renewal arrival process is composed of a finite number of Poisson streams and there is no feedback, one obtains a model studied by Miller [1960]. Also, if the Markov renewal arrivals contain only one type and when there is no feedback, the output process studied in this chapter becomes the departure process analyzed by Vlach [1969]. 33

34 3.1. THE OUTPUT PROCESS As was mentioned in section 2.5, the output process gives rise to the queue length process as well as the departure process. Therefore, this section develops the main properties of the output process. Since the queueing system is considered only at output epochs tn, one must carry extra information on the arrival process, in order that the arrival process be completely known at service completion times. Hence, one denotes by K the type of the last arrival before n tn and by U the time since the last arrival measured from t. Moreover, if one sets O to be the output interval between output epochs t and n n-l tn with 0 0, the sequence {Y,N,K,Un,On} specifies the output process. The. state space of such random process is the cross product of a denumerable set and the non-negative real numbers. Denote by I the idle period associated with the n-th output. n Notice that whenever the system does not become empty after the service completion tn1 I = O; in this case, one says that the idle period n-l n I does not exist. n Later on, we will need to establish relationships among the random variables N,Kn,U,Sn and In for different output epochs t 's. Figures 3.1 and 3.2 below illustrate some of the relationships. Z' n 0+ -- I lt- ~ S -— + S >, > n An _ n-3:$' 1 —U- -i' t t K n-1 K n n-1 n Fgr3..Te-n-i prcs iha depro Figure 3.1. The process with an idle period

35 t tnn iK —I -n Un-l ' t....I n-l N N -n Figure 3.2. The process without an idle period Recall that Z' represents the type of the n-th service or n-th n output. Notice that in the case where the system becomes idle just after t (figure 3.1), and only in this case, Z' is also the type n- - ', --— n of the m-th arrival for some m; therefore 7' = Z. In the case where n m the system does not become idle after t (figure 3.2), Z' is completely K-1 n nn specified by assumption E. n n n-L -n- n-l n- l Proof: If one sets to u the value taken by the random variable Yn-ig then the total number of units in the system just after t is given by E (6 +N )' represents the summation sign for c uc n-i c c = 1 to b. Therefore, the system is idle or not depending on this last quantity; consequently, one considers two cases. i) E = 0: assumption A and figure 3.1 enable us to derive that N, K and U depends only on S and Z'. n n n n ii) E > 0: in this case there is no idle period and the service starts immediately on a new unit. According to assumption E, this new unit is of type Z = r whera re

36 r = min{c:6 +N > 0 c = 1,2,. b} uc n-L Again, using assumption A and from figure 3.2, one states that N K and U depends only on Sn, Y-l' N Kn1 and Un-l Q.E.D. For the particular cases to be treated later, the joint probability of N, K and U will be explicitly evaluated. Therefore, — n n n some notation is introduced in the following Remark 3.2. Denote by f (e,y-tls) the joint probability of N nk' — n K and U illustrated in figures 3.1 and 3.2. This is the probability n n of a set of arrivals associated with the Markov renewal arrival process {Z,X } defined in assumption A. In words, this is the probability m m for a set e = [e ] of arrivals in an interval of length y-t with the last one of type k and no other arrival duringca length t given that prior to that interval of length y-t the last arrival was of type h and occurred at a distance s from the beginning of the interval of length y-t. If one denotes by i = el+e2+...+eb the total number of arrivals in the length y-t, figure 3.3 below illustrates this probability. [ec] arrivals C Z h Z -* n-1l n Figure 3.3. Set of arrivals associated with the arrival process

37 Formally, the above probability can be written as follows: fhk(e,y-ts) = PrZ =kX +..l+ +X m+i=y-t+s with hk m+l m+l M+i e type-c arrivals, Xm+i+l>tlz =h,X >s}. For the case where e = 0, the above probab ility is found to be 1-Bh (t) fhk(O'y-tts) = 6hk6(s+y-t)l-Bh(s) since there is no arrival in the length y-t, one must have t = s+y and the last arrival of type h. For the case where e. O, there is some arrival and t must be smaller or equal to y. Otherwise, one sets fhk(e,y-t|s) = 0. In the case where b = 1; that is, when there is only one type of unit in the arrival process; the above notation is simplified to f(e,y-t s). Proposition 3.3. Whenever the idle period I exists, it depends n only on Z' Kn- and U -l and its probability distribution is given by Ahr(s+x)-Ahr(s) Pr{I <xlZ'=rKn =hU =s} = r(s) n- n n- ' n-l ahrAhr(s) for r,h = 1,2,...,b and x,s > 0. Proof: The situation is illustrated in figure 3.1; and from assumption A, one derives that I depends only on Z', K and U n n n-i n-l

38 Furthermore, it follows that Pr{Z'=r,U sl=,I <XlKn=h} (1) Pr{I <x[Z' r K l=hU sn n Prn- nn ' n-h n-1 PrZ=sK=h} n Un-l 1 By considering the arrival process defined in assumption A, one finds Pr{Z'=r,U s,In <xlKn l=h} =Ahr(S+X)-Ah(S), n ' n- - and Pr{Z'rUn Kn-1h} ahr Ahr(); which after substitution in equation (1), gives the desired result. Q.E.D. Proposition 3.4. The type of the n-th output, Z', depends only on n Y 1N 1 Knl and Un; and its probability distribution is given by ahk-Ahk (s) 1-Bh (s) if u=0 & i=0, Pr{Z'=klY u,N1 =iK =hU =Sif0, n n-1 Z_ n-' n-1 6rk otherwise; where r = min{c:6 +i >0, c =1,2,...,b}. uc c Proof: Again there are two cases to consider; i) u=O & i=0: in this case the system becomes idle just after the output epoch t 1; the situation is illustrated in figure 3.1. From

39 assumption A, the next arrival which becomes the n-th output depends only on K and U Furthermore, its probability distribution is n-1 n-l' derived as follow: Pr{Z'=k,U -slK -=h) (1) Pr{Z'=klK l=hU = s} = Pr{Un=SIKn=h} n-l n-1 By the arrival process of assumption A, one computes (2) Pr{Z'=k,U1 =SlK =h} = ahkAk(S) and (3) Pr{Unl=slKn h} = -Bh(s). Substituting equations (2) and (3) into equation (1), one obtains the first part of the desired result. ii) u # 0 or i O0: in this case the system remains busy after t n-l and the next unit to be served is chosen with respect to assumption E. Therefore, the type of the n-th output is Z' = r, where n r = min{c:6 +i >0, c = 1,2,...,b}. uc c Then, the second part of the desired result follows. Q.E.D. Now, one can state and prove the following important result. Theorem 3.5. The output process {Y,N,K,U,0 } is Markov renewal n -n n n n over the state space l,...,b 0,1,2,...b {O,1,...,b}X{O,1,2,...} X{l,2,...,bX[O,oo).

40 Proof: By definition, the range of the random variable Y is n {0,l,...,b} and by considering the range of the other random variables, one obtains the state space specified. Whenever the n-th idle period I exists, the output interval n 0 can be written as I + S if (6 +N 0, O n n c uc n-l n - S otherwise; n where u is the value taken by the random variable Y n-l' The above relationship gives two cases; i) zb(d +Nc ) = 0: this case corresponds to the situation where i) c uc n-l the (n-l)-st output departs from the system leaving the server idle. Therefore, a unit of unknown type must arrive to initiate the service period S. Let Z be the type of this new arriving unit. This unit n m will also be the n-th output; therefore Z' = Z, and one can derive n m the following: (1) nPr{YN,NK O <x[IY;N...;U,;....;U...; k n n-1 n n- n n— N>n n' n- ';n-l'; n-l' + n-l';y 'k n-l' I +S <x S =yZ=k} n-l"' n n- n n

41 *Pr{I+SXn n — Yl n-l' n-l' 0n- '..;S =y,Z'=k} ~Pr{S YlI Y1... N _ y-K n*U 1 ~n-l';Zn } PrnZ'=k-lY...;N l,..;K..; n -n- 1' 'I n) n-l'; n-l' }dy. Using assumption C, the first probability term on the right hand side of equation (1) is simplified to Pr{Y |Y _,N n,N n-1,Sn=y,Zn=k} n nn Together with propositions 3.1, 3.3, 3.4 and assumption B, equation (1) becomes: n,KUn n-<xIYi -n-' ''' n ' n-1' (2) n' —n' n Un ~n-Xl~n-l;N _1 s..............................On,K ~.. U n-l ZPr{Y Yn-lN N S =y,Z =k} 0k l' —n- n 'Pr{N,K,UIS =y,Z'=k} Pr{I <x-YIKn_ Un_l S y,Z'=k n _ n — n n -Pr{S =y Z'=k} n n *Pr{Z'=kjKn_, U dy. n n n-l

42 Equation (2) can now be rewritten as nn n T n-i' - n-' n- n-l nP K UnN' ~ <x U YnOl 1 'N1 _K 1,U ii) Cb (d+Nc ) > 0: in this case, there is no idle period and the c uc n-l service immediately starts on a new unit of type Z' = r, where r = min{c:6 +N > 0, c = 12,...,b}. uc n-i One derives the following: (4) Pr nY K U O Y;Nl....;K...;U.; n n n n- n-l -l n-l' n-l' = Pr{YIY!Y**.;N,...;K...;;U,..0n,. ~0 n Zv=r} -Pr{N Kn U iY.;...; — n n nn-l';N- n n-l';n-l' n-l' S =y,Z'r} n n ~ Pr{S =y;N..;Kn..;..; n Yn1 n-1 'l n-, ~ ~~;Z'=r}dy, using the fact that 0 = S in this case. In the above equation, the n n first probability term on the right hand side is simply

43 Pr{YnIYl,'N 1N S =y,Z'=r}, using assumption C. The second term is simplified upon using proposition 3.1 and for the third term, one notes that S depends only on Z' = r from assumption B. n n Hence equation (4) becomes: (5) Pr n n nXlYn _...N l....;K 3...;U...; -n'n n n- n-l";' n' 1 ' 1' n-l' n-' n-XPr{y IY I,Nn-,N,S yZ'=r} Jo 30 n In-1 1 NSn=Y ' Zi n ~Pr{N Kn,U n I Y,K U S y,Z'=r} -*P n, n-l'N -K n-l' n n *Pr{S =YZ'=r}dy. n n Equation (5) can be rewritten as equation (3) above and one concludes that {Y,_n,Kn,Y,O} has the Markov renewal property. Q.E.D. Corollary 3.6. The stationary transition probabilities for the Markov renewal process {Y,N,Kn,Un,O} are given by AUV[(i,h,s),(i,k,t);x] = Pr{Y =v,N =j,K =k,U =t,O <x IY =u N 1 Kn =h n n ' -- n-1 ' —n- 'n-l U =S } where

44 f aPv(I,'a;y) fak (lY-tJ 0) Aha(S+x-y)-Aha(s) [ lBha(s) ]dH (Y) if u=O & i0O, A [(i,h,s),(j,k,t);x] = if e < 0 for some c, C fPuv(e r;Y )fhk(e,y-t ts)dH (y), otherwise; with e = [e ] and e = j +6rc 6u - i; for r = min{c:6 +i > 0, c c c rc uc c uc c c = 1,2,...,b}. Proof: From theorem 3.5, there are two cases to consider; i) u=O & i=0: here equation (2) of theorem 3.5 can be applied and after using assumption C, one finds PrY =vIYn- =0, N =0 N =j, =y,Zn=a} = P0v(j a;y) From remark 3.2, it follows that Pr{N =j,K =k,U =tIS =y,Z'=a} (j -ak( t 0) — n --- n n n n ak Furthermore, from proposition 3.3, one writes Pr{ I <x-y =a K l=h un l=} a (s) n- ' - ' annha-Aha() and from assumption B, one denotes Pr{S =ylZn=a}dy = dH (y). n n a

45 Finally, from proposition 3.4, Pr{Z'=alK =h 3U =s} = (S) rn Kn-l n-l 1-B (s) Then A v[(O,k,s), (I,h,t);x] = aPov(a;y)fah(j,y-tlo) Aha(S+x-y) -Aha (S) Ah1 Y-Bh(s) ]dH (y). h ii) u>O or i#O: here one computes r = min{c:6 +i > 0, c = 1,2,...,b}, uc C for the type of unit to be served and one can apply equation (5) of theorem 3.5 to get ~x (1) A [(i,h,s),(j,k,t);x] = (er;y)f (ey-tJs)dH (Y uv - PUV hk r where e = [e ] with e = j +6 -6 -i representing the set of the c c c uc uc c required number of arrivals. Notice that for the case where some components j +6 -6 -i are negative, the transition probabilities c rc uc c given by equation (1) are zero. Q.E.D. Proposition 3.7. The joint probability distribution of Z' and O n n depends only on Yn-l' n Kn U an d is given byn n-1 V n-l'

46 Pr{Z'=k,O <XYn_ =u,NN,Kn =hU ls} - n-1 — n-' nAhk(s+x-y) -Ahk(s) o [ lh(S) ]dHk(y) if u=0 & i=0, { rk (X) if u>O or i#0; where r = min{c:6 +i > 0, c 1,2,...,b}. uc.C Proof: Using theorem 3.5 and proposition 3.4, one can establish the correct dependence. The explicit probability is found by using corollary 3.6; note that in the case u=0 & _i=Q, a unit of type-k must arrive. Q.E.D. Proposition 3.8. If b = 1, then the output process {Y,N,U,0 } n n n n is Markov renewal over the state space {O,l}X{0,1,2,...}X[O,oo) with stationary transition probabilities given by A [(i,s), (j,t);x] l-A(s) Jo Pov(j;y)f(j,y-tlo)[A(s+x-y )-A(s)]dH(y) if u+i= 0, = <0 if j+l<u+i # 0, sHuvy (j+l-u-i;y)f(j+l-u-i;y-t s)dH(y ) otherwise. Proof: In the case where the Markov renewal arrival defined in assumption A contain only one type, the arrival process becomes a renewal process and the random variable K always takes the same n value. Hence, if one sets A(x) = Akh(x), then Bk(s) = A(s).

47 Similarly, one could set f(e,y-tls) = fhk(e,y-tls)Substituting these quantities in the transition probabilities of corollary 3.6, the desired result is obtained. Q.E.D. Corollary 3.9. If b = 1 and there is no feedback, the output process becomes the departure process of the GI/G/1 queue, denoted by {Nn,U,O }, with the stationary transition probabilities given by n n A[(i,s),(j,t);x] = Pr{Nn=j,U =t,On<XINn =iUl=s} where A[ (i,s),(j,t);x] 1 A(s) f f(j,y-t0) [A(s+x+y)-A(s)](dH(y ) if i=0, I-A(s) = ~ 0 if j+l < i#0, O if j+l < i0O, f (j+l-i;y-t s)dH(y) if j+l > i#O. Proof: To obtain the no feedback case, one sets u() PV(;Y) - 0v' for all u,v=0,l; j = 0,1,...; and y > 0. Substituting equation (1) in proposition 3.8, one gets the desired result. Q.E.D.

48 Note that corollary 3.9 gives the result found by Vlach [1969]. Rather than continuing the investigation along the line where there is only one type of arrival, the particularization will be made where the arrival process is composed of several independent Poisson streams. Some results concerning this arrival process are stated in section A.3. Proposition 3.10. If MR, = Mb, then 6 6(y+s-t)e- (t-s)X if e=0, fhk(e y-tls) = - ((y-t) e -6 h' r r rk x e 1r if e~_0; r rk ' for e = [ec] and e = 0,1,2,.... Ir denotes the product sign for r = 1 to b. Proof: From remark 3.2, there are two cases to consider: for e-0, one uses proposition A.8 and obtains fhk(e'Y-t t s) = hhk (t-s-y)e(ts) Fro e0O, figure 3.3 applies. Therefore, one needs a set e = [e ] of arrivals, where e denotes the number of type-c arrivals. Using c lemma A.10, the number of arrivals of each type in an interval of length y-t is Poisson distributed, and since one wants a type-k arriving at the end of the interval of length y-t and no arrival for a length t, remark 3.2 gives -Xy e e ek-l e [ (Y'] %k (y-t) -%k(Y-t) fhk(ey-tis) i= E( ) rwk which is the desired result. Q.E.D.

49 Proposition 3.11. If MRb = Mb, then the output process is characterized by {Y,N ',O} and its stationary transition probabilities are given by A (i,I;x) = Pr{Y =v,N =, <XIYnl=u,N=i} where -y j C C.dHh(y) if u=O & i=, A_ (iI;X) = 0 if e < O for some c, UV C -X y *e (x e (X y) c Ij Xp(e,r:;v)j C ~ dH(y) U C otherwise; with e [e ' ec = jc+6c-6uc-ic; for r = min{c:6 +i > 0, c = 1,2,.. c = 1,2,...b}. Proof: Since-one has the forgetfulness property whenever the arrival process is composed of independent Poisson streams (lemma n n A.10), th[e information on the arrival process carried by Kn and Un becomes unnecessary and can be removed. Hence, in this case, the output process {Y,N,Kn,U,On} can be reduced to {Yn,N On}. This n-n n n n n-an reduction is accomplished bycomputing the transition probabilities (1) AU [(i,h,s)(j,-,-);x] = ktAv [(i,h,s),(j,k,t);x]dt.

50 Conlsi. der two ('-.8ss: i) u=O & i=O; from corollary 3.6, equation (1) becomes A[(O,h,s),(j,, = Izbzbf p (ja;y)f k(j y-tI0)dt Aha (s+x-y)-Aha (s) ' [ Bh(S) ]dH (y). 1-Bh(s) From lemma A.10, one obtains Aha (s+x-y) -Aha (s) -(XY)ZX. 1-Bh (s) a Also, from proposition 3.10, one finds -tZX 6(y-t)e j 0 (2) kfak( Yt10) c kfak(j'y-t [0) b | Re-y(I (ee )(y-t) j R O; where R = bEi j Then Av[ (0,h, s), (0,,);x] = X >a p (O,a,y)(l-e(XY))e dH (y) and for j j Q, A [(O,h,s), (=, );x ] -X y j -- c a Jc'

51 Since the right hand side does not depend on h and s, one can write (3) AV (O,j;x) 0o aaP0v(J,a;y)(l-e - c(x-y) a ii) u > 0 or i # 0; again from corollary 3.6,equation (1) becomes A [i= h,fs)f,(jP );x] = uv(er;y)fhk(e,y-ts)dt rdH (y), r where r = min{c:6 +i > O0 c = 1,2,...b}; uc c using equation (2) and integrating out t, one obtains: -X y e O c ~x e (Xy) (4) A [(i,h,s),(j,.,.);x] = c dH (y) since -A y e c c e (Xy) c fY b c J0h fhk(e,ytst = lscde hvi';- c P C(eryn e! dR(y). oO.c for e = [ec] with e = j +6 -6 -i > 0. Since the right hand side c c c rc uc c of equation (4) does not depend on h and s(5) one can rewrite it as rx e (X)E.D. (5) A (ij;x) p(ery)l dH (y). uv — '.P uv — ' c e.! r c Equations (3) and (5) prove the proposition. Q.E.D.

52 Proposition 3.12. If MR = Mb, then the joint probability distribution of Z' and 0 is given by n n Pr{Z =k, O <x |Y u,N -i} n n- n —I%J1k - (1"-e ( )dH k(y) if u=0 & i=0, rkHk(X) if u>0 or i0Q; where r = min{c:6 +i > 0, c = 1,2,...,b}. uc C Proof: Use prepositions A.8 and 3.7. Q.E.D. Corollary 3.13. If M% = Mb, then Z' depends only on Y and N-_ Corollary N" Nb' n n- n 1 and its probability is given by if u=0 & i=0, Pr{Z'=klY l=u,N =i} = n n-l n n 16rk if u>0 or i_, where r = min{c:6 +i > 0, c = 1,2,...,b}. uc c Proof: Use limit as x goes to oo in proposition 3.12. Q.E.D. Proposition 3.14.. If M% =, then Yn,Z, n depend on Ynand N Moreover, its joint probability distribution is given by Pr{Y =vZ=k,N Nj,O <x Y =u N =i} n n -n n- n-i -n-iCy j 1c c e ( ) y) (1-e y))POv(jk;Y)lc C dHk(y) eke- (Ox-y)Z% 0v c j3 k if u=O & i=0, -X y e e C ( Y) C JrO Pv(-;y) c C d~H (y) if u>O or _O; PuvOe C r

53 where e = [e ] with e = j +6 -6 -i and r = min{c:6 +i > O, - c c c rc uc c uc c c = 1,2,...,b}. Proof: Using propositions 3.11 and 3.12, it follows that Y, Z' N and 0 depends only on Y and N Depending whether or n -n n-1 '-nnot the system becomes idle just after t, there are two cases to n-l consider; i) u=O & i=O: here, one notices that to have Z' = k, the first n arrival after t must be a type-k unit. Therefore, following the development used in the proof of proposition 3.11, one obtains the first part of the desired result. ii) u>O or i#0: here, the type of the next unit to serve is given by Z' = r where n r = min{c:6 +i > 0, c = 1,2,...,b}, uc c using assumption E. Similarly, one obtains the second part of the desired result. Q.E.D. The above propositions enables us to find the stationary probability for the type of output and the stationary distribution of output interval lengths. In the case of no feedback, proposition 3.12 characterizes the departure process for priority queues. This is a new development for the queueing system studied by Miller [1960]. It is also worthwhile to note that in the case where there is only one Poisson stream and no feedback, proposition 3.12 gives the departure process from the M/G/1 queues.

54 3.2. QUEUE LENGTH PROCESS AND GENERATING FUNCTIONS From theorem 3.5 and its corollary, one obtains the following theorem and corollary 3.16, using well-known results from Markov renewal theory. Theorem 3.15. The queue length process {Yn,N,KnU } is Markovian n n n over the state space {O,1,...,b}X{O,l,... }bX1,2,...b}X[O,oo). Corollary 3.16. The stationary transition probabilities for the Markov process {Y,N,K,U} are given by A [(i,h,s),(j,k,t)] UV - Pr{Y =v,N =i,K=k,Un=tl =UN iK =hU =s}, n — n n n n- n-1 ' n-1 where lAh(s) af p ( —a;y)fak(Jy-tl0)[-Bh( *dH (y) if u=O & i=0, a A [(i,h,s),(j,k,t)] = 0 if e <0 some c, UV - C fyPu (e,r;Y)f (e,y-t Is)dH (y), y uv - - r' if e >0 all c; cwith e = [e ] for e =j+6 -6 -i, c c c rc uc c r = min{c:6 +i > 0, c = 1,2,...,b}, and fhk(e,y-tIs) given in remark 3.2.

55 Denote by P the matrix whose entries are the transition probabilities given in corollary 3.16 and by m' the row vector whose entries are the stationary probabilities r(v;j,k,t) = lim Pr{Y =v,N =jKn=k,U =t}. -- n n The conditional stationary probabilities are denoted by T (j,k,t) = lim Pr{N =,K =k,U =tjYn v}, v- -- n n n n-+co and in vector form T = [ (j k,t)]. Assume there exists stationary conditions under which the probabilities given in the above equations exists and can be derived by solving Tr = 7P. In the second chapter of Cherry [1972], conditions for the existence of such stationary probabilities are discussed. Because of the complexities caused by the general switching rules, we have been unable to find simple conditions for these equations to be satisfied in general. Later on in this dissertation, the arrival process is particularized and then explicit conditions for the existence of stationary probabilities are found. We are now in a position to prove theorem 2.4 of chapter 2.

56 Proof of Theorem 2.4: As indicated in section 2.2; whenever the operating process is either the queue length, the busy cycle or the departure process, fed back units may be given service priority. Let F be the number of feedbacks associated with the m-th unit and T m m be the total service time of the m-th unit. One can write (1) Pr{T <x} = ZPr{T <xF kPrF =k}. Im- k m- m m Furthermore, Pr{F =k} involves the transition probabilities (2) guv= Pr{Y =vIY =u}, for u,v = 0,1,...,b. Under stationary conditions, consider the following two cases: i) u=0: upon introducing the random variables associated with output epochs t and t in the probability of equation (2) and using n n-1 remark 3.2 and corollary 3.6, one obtains (3)v Ehf sayPO (j a;y),y(;yaO)dH (y) s 0(hs) a(Ohs)ds a 0 + ii f llyPv(er;y) y(e;yhs)dHr(y)0(iths)ds, i>O e0O where V (h,s) = Pr{Z alK nl=h,U =s} (e;,hs) n-1 y(e;y,h,s) = Zkftfhk(e,y-tls)dt,

57 and the index r of the second term of equation (3) is given by r = min{k:ik > O,k = 1,2,...,b}. ii) u>O: again by introducing the same random variables and using the same remark 3.2 and corollary 3.5, one obtains (4) guv= 7 h sfy uv(e,r;y)y(e;y,h,s)dHr(Y)Tu(ih,s)ds, i>0 eO where y(e;y,h,s) is defined above and the index r is given by r = min{k:6uk+ik > O, k = 1,2,...,b}. Notice that y(e;y,h,s) is independent of h and s, noted Y(e;y), if and only if the arrival process has the forgetfulness property stated in definition A.9. This is so, after considering proposition A.8. Moreover, from lemma A.10, a necessary and sufficient condition for the forgetfulness property is to have the arrival process Nb. To prove the necessary part, there are two cases to consider: a) If neither the service process nor the feedback mechanism depends on the type of unit and if the arrival process is Nb for b > 1, then equation (3) becomes (5) g = Z fyPov(j;Y)Y(j;Y)dH(y) Similarly, equation (4) becomes (6) guv f yPuv(;y) Y(j;y)dH(y). UV ~Q.

58 The transition probabilities of equations (5) and (6) depend only on known quantities; therefore, one computes Pr{F =k}. Moreover, m condition 1 implies that Pr{T <slfF k} = H(k) (x)..M- m Now, under stationary conditions, the sequence of total service times {T } form a renewal process whose probability distribution is m given in equation (1). Therefore, using definition 2.2, one obtains a G-server queue without feedback. Hence, one can characterize anyone of the above three operating processes using the G-server queue and then derive the corresponding operating process in the MR/Gb/l queue with feedback. Then, from definition 2.3, one obtains the first part of the desired result. b) If conditions 1, 2, and 3a are satisfied, then similarly, equations (3) and (4) becomes: (7) gOv f P (y)dH(y), and (8) gu yPv (y)dH(y) respectively. Again, the transition probabilities of equations (7) and (8) depend only on known quantities and one obtains the same conclusions as in part a) above. To establish the sufficiency, one notes that if any one of conditions 1, 2 or 3 is not satisfied, then the transition probabilities guv found in equations (3) and (4) would depend on the stationary

59 probabilities T0(i,k,s). From definition 2.2, one is then unable to obtain a G-server queue without feedback in this case. Thus the MRb/Gb/l queues with feedback which do not satisfy conditions 1, 2 and 3 are never equivalent to G-server queues without feedback. Q.E.D. Notice that in the case where there is only one type of arrivals, that is b = 1, theorem 3.15 together with its corollary gives a characterization of the queue length process for the GI/G/l queue with state-dependent feedback. Instead of particularizing along that direction, we will keep several types of arrival, but assume a Poisson stream for each type. Hence, proposition 3.11 gives directly Proposition 3.17. If MR% =, then the queue length process {Y,N } is Markovian and its stationary transition probabilities n -n are given by A (i, j) Pr{Y =v,N jlYnl =u _i} uv- n n n-l=u -n where c if u=O & i=0, A (i,) O0 if e <O for some c, UV C -XkY ek e (Aky) f p (er; y)lk e! dH (y) otherwise; -- [ k e r with e = [e ], e = j +6 -6 -i for r = min{c:6 +i >0,c = 1,2,...,b. -- c c c rc uc c uc c

60 Corollary 3.18. The Markov chain {Y,N } is aperiodic and n -n irreducible. Proof: Considering the stationary transition probabilities given in proposition 3.17 and the conditions on p (e,r;y) given in assumption C, one obtains the desired result. Q.E.D. Remark 3.19. Consider the matrix P whose entries are the transition probabilities A (i,j) given in proposition 3.17 and m the UV stationary probability vector whose entries are 7r(v;j) = lim Pr{Y =v,N =j1, n -- for v 0= O,l,...,b and j [jc]; j = 0,1,..., and c = 1,2,...,b. Using corollary 3.18, the states of the Markov chain {Y,N } are n -n ergodic if and only if there exists a stationary probability vector af to the matrix equation (1) n = rP. Introduce the generating functions V(~) = E ~T(v;i) and (2) G (~;r) = ~Jrp (jr;y) dH (y), uuv =- uv' f>o =.=.nok' for u,v = 0,i,..,b and r = 1,2,...,b. The notation ~' would denote

61 i~1- ~ J2- '~bJb with j~ <1 for c = 1,2,...,b. Later on, it will 1 2 ' c be necessary to consider states where there is no type-k unit in the system just after an output, for k < r. Thus, one defines the following generating functions: (3) Vr = L ~ i —r (v;i ), v -- — v / i ~0 -r where ~ = [ll,..,l,~, rr+l' 'sb] k < 1; (4) -r 1; (4) i = [o,,0,',i,i.,ib]. Notice that in equation (3) the index r takes value in the set {1,2,...,b+l}. For r = 1, the vectors ~ and i are the usual ~ and i, therefore one can write v (l) = V (~). For r = b+l, the vectors ~ and i become the vector of ones -b+l and the vector of zeros respectively, thus b+l V (~ = ((v;O0). v -(b+l For v = 1,2,...,r-l, if one considers states of the form given in equation (4), the generating functions Vr(~ ) do not exist since V -r these generating functions are defined whenever there is no type-k unit in the system (k < r). Therefore, the range of the index v depends on the value of r; in fact v = O,r,r+l,...,b.

Now, section A.1 can be used to find the system of generating functions: b (5) v(- E [ Cv(;t) ((o;o)+Ul (v ( u +l~ M v Ov u v 0 (~)-0 -U+l] u=l u-1 + u G(~;k)~k'[V k -Vk+l (~ )]+G (~;u)Vu( U uv k u uk u k UV - u k=l for v = 0,1,...,b. There are still unknown generating functions in equation (5); these are defined in equation (3). For every r = 2,3,...,b, one finds V (~r) as follows: consider the embedding of a new Markov chain V r 1 2 r-l r b {Y,N =0,N =O,...,N =0,N,...,N } in the original Markov chain mm m m m m {Y,N }. One then finds the transition probabilities of this new n — n Markov chain, which involve only the busy period of type-k units, for k = 1,2,...,r-1. Then, one can find explicitly the generating functions given by equation (3). The determination of the generating functions V (~r) is done V for the case where b = 2 and a restricted feedback mechanism in chapter 4. As it will be seen, finding these generating functions involves computational difficulties. Thus, it is assumed that given a specific feedback mechanism, one can find the generating functions Vr(~r) for v = O,r,r+l,...,b and r = 2,3,...,b. V -r Substituting these generating functions in equation (5), one obtains a system of b + 1 equations and b + 1 unknown generating

63 functions Vv(~). This system is then studied for the possibility of finding solutions V (~)(v =,l1,...,b), for fixed ~ such that 0 < < 1 (c = 1,2,...,b) C - Using the fact that lim [VO(~) + bv (~)] = 1, — v v where u is the vector whose entries are all one; together with L'Hospital's rule, it is believed that an expression for 7r(0;0) could be found, whenever it exists. Necessary and sufficient conditions for the states to be ergodic would be Tr(0;0) > 0. The above relation would impose conditions on the arrival process, the service process and the feedback mechanism such that the states of queue length process are ergodic. These are stationary conditions. 3.3. THE BUSY CYCLE In this section, the occupation of the server is analyzed. This occupation alternates between busy and idle periods. A busy period followed by an idle period constitutes a busy cycle. If I denotes the length of the m-th idle period, one can recall that m the sequence {I } was characterized by proposition 3.3. Here, two m corollaries can be derived from that proposition.

64 Corollary 3.20. If b = 1, then the idle period Im depends only on U. Furthermore, the probability distribution of I given rn-1 m Um_1 is given by Pr{I <xU s} A(s+x)-A(s) mr- m-i l-A(s) where A(') is the probability distribution associated with the arrival process. Notice that the above result is independent of the feedback mechanism. -This is not surprising, since the length of an idle period depends only on the arrival process. Moreover, corollary 3.20 agrees with results from Vlach [1969]. Corollary 3.21. If MR = b, then the idle period process {I } is Poisson with parameter ZX. Proof: This is immediate upon using lemma A.10. Q.E.D. Now, turning our attention to the busy period process, let B be the length of the m-th busy period length and G(-) its probm ability distribution under stationary conditions. Theorem 3.22. If MR = Mb, then, under stationary conditions, the probability distribution of busy period lengths is given by: * =b -1 G (s) = Za [L (s;r) + ZbzbL (s;r)(I-J(s)) LvO (S;V )] r r 00 u v Ou Uv v

65 where -kY * Jk e (XkyG (s)) L (s;r) = E e Syp (j,r;y)k dH (y); UV y UV -- ' r ~0 and J(s) is the matrix [L (s;u)] from which the first row and the first column has been removed. Proof: The busy period is independent of the service discipline stated in assumption E. Moreover, the order of service is immaterial to the busy period as long as it does not increase the time spent in service. Hence, one can give priority to a fed back unit; that is a unit is given successive period of service until it departs from the system. If one calls the originator, the unit which initiates the busy period, the busy period of the system can be written as follows: 1 K (1) B S +S +...+S +B +...+B, m n n+ l n+F m m m where S the (i+l)-th service period of the originator, F = number of feedbacks of the originator, m b k K E= N number of units in the system when the k n+F m originator departs, k Nk+i = queue length of type-k units just after the (i+l)-th service completion of the originator, Bj = busy period initiated by the j-th arrival during the m service periods of the originator

The index n refers to a count on the number of services by the server. The service period Sn4i depends only on the type Z'+i for i = 1,2,...,F which in turn depends on Yn+i Hence given the m n+i-l' output type Yn+i-1 the service periods S '+is are independent. Furthermore, during the total period of service of the originator, S +Sn +..+ F S there has been K arrivals divided among b different n n+1' n+F' types. Since the arrival process is Mb, the sequence of types of these K arrivals consitutes an independent process. Moreover, each of these K arrivals will be the originator of the busy period BJ for m some j = 1,2,...,K. Therefore, all B3's are independent and have the same probability distribution that B has, G(-). Moreover, each busy period Bj is independent of the above service periods, S m n+Ji If Z denotes the type of the originator, then the probability m distribution of the busy period B is derived as follows: G(x) Pr{B <x} = Zba Z Pr{B <x,F =klZ =r} r r k m — m m (2) = Ca Z Gk(x;r). Using equation (1), the probability term for k = 0 in equation (2) is: 1 K (3) G0(x;r) = Pr{S +B +...+B <xY =0Y =0,N =0,Z =r = n m G — n n-l -n m -ky e (%kY) - I ( hG (x-y)P00(j;y), dH(y);

where h = Zkjk. Considering the Laplace-Stieltjes transform of the probability distribution given in equation (3), one gets (4) GO(s;r) = LOO(s;r); using an appropriate change of variables and the notation -ky * k -s y e (AkyG (s)) (5) e (s;r) f (j,r;y)lk i - dH (y), uv y uv -r'k Jk r j>0 for u,v = 0,l,...,b. For the case k = 1, the term on the right hand side of equation (2) is: b 1 K G1(x;r) = ZbPr{S +Sn++Bm+...+B <xY =v =01Y =0 v n n+l m m- n n'l N -=0,Z =r} m - E JxJyE G(h) (x-y-Z) ( V Y) -ky k-ik XkY ik e (XkY) e (AkY) 'k (Jk-ik) ' dH (Z)POv(ir;Y)kll ~dH (y), r where h = jk. Now, taking the Laplace-Stieltjes transform of the k k above distribution, and by an appropriate change of variables, one finds (6) G1(S;r) = bLv(S;r)nv0(S;V); (6)using notation given in equatiL(s)Lon (sv) using notation given in equation (5).

68 Now, for k -= 2, one could find G (s;r) = ZbZbL (s;r)J (s)L (s;v) 2 u v Ou UV L v where J(s) is the matrix [L (s;u)] from which the first row and uv the first column has been removed. It also follows that for k > 1 *7) Gb b k-1 (7) G (s;r) = Z L (s;r)(J (s)) )uvLv (s;v). k u v Ou Uv vO For fixed s with Re{s} > 0, the matrix J(s) is such that O < L (s;u) < 1 and Z L (s;u) < 1, using the definition of L (s;u) UV V UV UV and condition 1 of assumption C. Thus, all the eigenvalues of J(s) have moduli less than 1, using a result from Lancaster [1969]. Therefore, kJk (s) converges and is equal to (I-J(s))-. Hence, summing equation (7) over k from 1 to c, one obtains r (s;r) TM b.EkGk+l z E bL (s;r)([I-J(s) )uvLvo (s;v), k k+l UV uOu Uv vo together with equation (4), equation (2) gives the desired result. Q.E.D. Notice that when the arrival process MR is considered, the busy periods Bj and Bh for j # h are no longer independent. m m 3.4. DECOMPOSITION OF THE OUTPUT PROCESS The output process is decomposed by the feedback switch into two types of processes: the feedback processes and the departure process. The feedback switch acts like a filter on the state space of the output process.

69 If one filters the states with Y = v for fixed v = 0,l,...,b, n the resulting process is either the feedback stream going into the type-v units whenever v = 1,2,...,b or the departure-stream whenever v = 0. Using results from Cherry [1972], one can state without proof. Theorem 3.23. The decomposed process {Y =v,N,Kn UnO } is Markov n -n n n n renewal for every v = 0,1,...,b over the state space {0,l,... }bX{1,2,..,b}X[0,o). In the above process, the index n no longer represents a count on the number of services but a count on the number of jumps into states with output status equal v. To remove ambiguity, note by {Y =v,N,K,U mO } the decomposed process for every v = 0,1,2,...b. m -n m M m Hence, the length 0 represents the interval length between two consecutive outputs with Y =v. It is also worthwhile to note that the decomposed process is a kind of first passage time. Therefore, one could, in theory, find the stationary transition probabilities for every decomposed process. Now, let us turn our attention to one particular decomposed process, the departure process. In fact when v = 0, the corresponding output leaves the system. If one denotes by t' the epoch of the m-th m departure; by D the interval length between the (m-l)-st and the m m-th departure; by Q the queue length at t'+O; by K' the type of -inL m m the last arrival prior to t' and by U' the time since the last arrival m m measured from t', then the process {Q,K',U',D m} represents the departure process and is Markov renewal, using theorem 3.23.

70 3.5. CONCLUSIONS In this chapter it was shown that the output process from the MRb/Gb/l queues with feedback is Markov renewal on a state space which is the cross product of denumerable sets and the non-negative real numbers. Theorem 3.5 and corollary 3.6 characterize the structure of the output process. This characterization of the output process was used to derive the queue length process as well as the departure process. The busy cycle of such a queueing system was also analyzed. In the next chapter, the formulation considered above will be illustrated in the case of two Poisson streams forming the arrival process with a feedback mechanism depending on the type only. Explicit stationary conditions will be found and then applied to two computer time-sharing models.

CHAPTER 4 PARTICULAR QUEUEING SYSTEM WITH FEEDBACK In chapter 2 the problem of queueing systems with feedback was introduced. One thing proved there was that if the feedback mechanism depends on the type of unit then the queueing system with feedback cannot be transformed into an equivalent system without feedback. The content of chapter 3 enabled us to analyze directly a queueing system with a general feedback rule. It is the object of this chapter to illustrate the analysis of the preceding chapter using a particular queueing system with feedback. Specifically, the system to be considered assumes two independent Poisson streams as the arrival process and the feedback mechanism depends only on the type of unit. 4.1. SPECIFIC ASSUMPTIONS The queueing system with feedback considered in this chapter is a particular model of the one stated in section 2.1. Therefore, we will particularize the appropriate assumptions, namely A and C and leave unchanged the others. Whenever the arrival process {Z,X } is composed of two indepenmm dent Poisson streams of parameters X1 and A2 respectively; proposition 71

72 A.8 with b = 2 gives the transition probabilities Ahk(s) = Ok(l-e ), for h,k=1,2 and x > 0. Here, the feedback mechanism is assumed to depend only on the type of the unit being directed and furthermore whenever there is feedback, the unit joins the queue of type-2 units. Therefore, associated with the n-th output, the random vaiable Y is defined n as follow: JO0 if the n-th output departs, n 2 if the n-th output feeds back. Thus, assumption C concerning the probabilistic structure of the feedback mechanism is particularized to Pr{Y =vjYn_...;Nn,...;S;Z'=r} = Pr{Y =vlZ'=r}, n n-i' n n n n for v = 0,2 and r = 1,2. Therefore, puv (,r;y) - (6 0+6u2)Pv(r) for u,v=0,1,2; and without loss of generality, it can be written that Pv(r)= Pr62v+(l-Pr) 0v, where P1 and P2 vary in the interval [0,1).

73 The above queueing system with feedback is best visualized by figure 4.1 below. {Z =2P Queue of type-2 H2(0) m 1-P I{Z,Xm} one server z =l Queue of type- 1 m ~ 11~1(0) l-P1 Figure 4.1. Particular queueing system with feedback 4.2. STATIONARY CONDITIONS In this section, we study in detail the queue length process 1 2 {Y,N,N } and determines its stationary conditions. Using proposition n n n N2 3.17 the queue length process {Y,N Nn} is Markovian over the state space {0,2}X{0,1,...}X{0,1,...}. Furthermore, one has the following result: Proposition 4.1. The stationary transition probabilities for the 1 2 Markov chain {Y,N,N2} are given by n n n Auv [(i1 i2),(j1, 2)] = Pr{Y vN 1 2 n n l'Nn2 n-l n- '1 ' N n-= 2 with A[(i~i2),(ijj)] = J k kPv(k)gk(JlJ2) if u+il+i2=0, uv ' 1' 2 UV Pv(r)gr(jl+ rl-lj2+6 u-6 -i2) otherwise;

74 where r = min{c:6 +i >0, c=1,2}, uc c -e y e ( y ) c C gk(ili2) = f j! d k(y) ' and set gk(i,j) 0 O whenever i or j is negative. Furthermore, from proposition 3.14, another result is obtained. Proposition 4.2. The joint probability distribution of Y, Z', N1, n n 2 and N is given by m 2 2 Pr{Y =vZ'=k,N j,N j Yn- =uN' N i n n 'n 1' n 21Yn-lnn-l =iNn-2l= ktp(k)gk(jl 2 I2 if u+il+i2=0, l rkPv(r)gr(jl+6rl-iliJ2+6 — 6-i ) otherwise; rk~v r I+6rl lJ2+r2 u2 2 where r = min{c:6 +i >0,c=1,2} and gk(i,j) is given in proposition 4.1. uc C From proposition 4.1 and the feedback switch defined in section 1 2 4.1, the Markov chain {Y,N,N } is irreducible and aperiodic. We are now ready to make use of the method stated in remark 3.19 to find explicitly the stationary conditions for the particular queueing system with feedback. In the process of doing so, we need several additional results; which are given in section A.2. Theorem 4.3. The states of the queue length process {Y,N,N} n ~ n n are ergodic if and only if P1+P2+P2(1-Pl)+Pl1XS2 < 1, where p =. S for r = 1,2. r rr

75 Proof: Using equation (5) of remark 3.19 with b = 2, V (~1~2 = V (~ ~2) and V3(0,0) = (O;O,O), one obtains -1 2 V (~,~ ) = G (~,~;17)[~l (0;0,0)+~-, ~ ) 2 1 2 0v 1 2 1 (v0(~l2-V0(0'~2))] +Gov(~1,2;2) [a27(O;OO)+~ 2 (V0 (0,~2)-(0;o,o)] +~G 2v(~1,~2; 1)~1 ( ~ )-V 2 2(~;2)V2 (0, ~ for v = 0,2. For this particular model V1(~1,~2) = O, since v cannot take the value 1. One needs to evaluate V2(0,~2). As mentioned in remark 3.19, V 2 the probabilities 7r(v;O,i) can be found by embedding a second Markov 1 2 chain within the original one, {Y,N,N }. This has been done in n n n section A.2 and the generating function R (~) = r7(v;O,i)~i has been v i found and evaluated for ~ = 1. Since the second Markov chain is to be viewed as embedded within the first, one can use proposition A.7 and write 2 V (O,~ ) =Rv( )' v 2 v 2' for v = 0,2. Also, from equation (2) of remark 3.19 and the specific assumptions of section 4.1, it follows that (2) GU (~,~2;r) = Pv(r)Hr(l- ~1 12+%- 22).

If one denotes by A (~1,~ ) the coefficient of p (r) on the r 2 v right hand side of equation (2); and if one uses the above substitutions, equation (1) can be rewritten as 2 1 (3) V (~ ~ ) = 7(0;0,0)[Zr rPv(r)Ar(~l2)pv( 2 2 1 vi' / 1' 2 2 +R0(~2)[P (2)~2 A (~ ~2)-v(1)~ A (~,~2)] +R2(~2) [Pv(2)A2(~1~2)-pv(1)~1 2A1(~1~2)] +Pv(l)~1 A(~1, ~2)V 0(~1,~2) +pv(1)~ 1 ~2A(~1 1~2)V2 V~1 2)' fpr v = 0,2. Denoting by bv(~1 ~2) the first three terms of equation (3) and by Bv(~1~2) and Yv(~11~2) the coefficients of V0(~1,~2) and V2(~19~2) respectively, one can solved equation (3) with respect to V (~ 0 2 and V2(~1,~2); it is verified that (1-~2(~~2 ))b0(~ 2) (~ ~ 2)b 2(~,~2 (4) V0 (~1' 2) l-B0 20(~1' ~ 2)+C(~1,~2) and (1-B0( 1~ ))b2(~1~ )+ B2(~ ~2) b (~9 2) 0 2 1 2 2 1 2) (5) V2(~1 ~2) (-B0 (~1,V~2)-y2(~1,~2)+C(~1, ~2) where C(~1,~2) = Y2(~1~2)B (~ l~2) - 0(~l,~ 2) B2( ~ l~2). Using proposition A.7, there exist a function X (~) such that (6) R(~) = v (0; 0,)Xv(~2)

77 for v = 0,2; therefore, it is verified that (7) b (~~ 0;,0) 2= rarP(r)Ar( ~~2) (2)~2 A2( 1'2) vi 2 ' rrvrr(~'2)-Pv(2)2 2 -1A -1 + X0(~2)[Pv(2)~2 A2(~1,~2)-P v(l)~1 A(~,~2)] -1 + X2(~2)[Pv(2)A2(~~2)-p(Pv()~ ~2A1(~1,~2)]} for v = 0,2. If one denotes by f (~1~2) the coefficient of r(0;0,0). on the right hand side of equation (7), equations (4) and (5) become (1-y (~ ~2))f 0(~1, ~2) y(~1, ~2)f (~ ~2) ~~V(8 ~~) V0(~1,~2) = 2(0;0,0) 2 1 2 1-B0(~' ~)- 2 ( ~1' ~2)+C( ~I ~2) (l-B0(~ ~> ))f (~ 2 ~)+B2( ~ ~B )f (~ ~ ) (9) V (~,~2) = (0;0 0) 2 2 0 2 (1-B(~i, ~2)_ (~1, ~ 2)+C(~1,~2) Now, using the fact that V (~1~2) are monotone and bounded v 1 2 functions, one can set rim V (~ 2) lim lim V (~ ~ ). v 1 ' v 1' 2 ~ ~+1 ~+1 ~2+1 1~1 2 Furthermore, adding equations (8) and (9) and setting ~2 = 1, one obtains f0 (~,1)+f2 (~ 1,1) (10) V (~1,1)+V2(~1,1) = T(0;0,0) Bo(~1,1)_Y2(~1,1) where -1 BV(~, l) = Yv(~ )~ = p((~ 11) fv(~1) r= ZrrPv(r)Ar(~ 1) -Pv(2)A2(~1 1) + [X0 (1)+X2(l)] {Pv(2)A2 (~l)-s P(1) A1(~1,1), for v = 0,2.

78 Now letting ~1+l in equation (10) and using L'Hospital's rule; it follows that (X S2+l-P1) [X (1)+X2 (l)-l ]+C1 (11) VO(1,)+V2(1,1 (0;OO) = (0;0l0) 1 1 0 '2 1-P1 where P= A S1' From equation (6) and proposition A.7, 12+PlI 1 2 (12) X0(1)+X2(l)- 1+2 [ (lX 2)( lPl)p2Pll Using equation (12) together with the fact that Vo(1,1) + V2(1,1) = 1, equation (11) gives (13) ( +)[(1-P2)(1-P1)-P2-P 1X1S2] (13) Tr (0;0, 0) lI(i+Pl-P2)+ %2 A necessary and sufficient condition for the states to be ergodic is n(0;0,0) > 0, or Pl P2+P2 (1-P)+PlAlS 2 < 1, which proves the theorem. Q.E.D. Proposition 4.4. Under stationary conditions, the joint probability of Y and Z' is given by n n Pr{Y =v,Z'=k}=7(0;0,0){ckP v p(k)+A(62k (2)-6kP))-62kp(2)} n n kP) 2 +6kPv (1),

79 where f(0;0,0) is given by equation (13) of theorem 4.3 and A - 1 _ 1(1P _P2___P2(_ _ P1))+X2 _P1 1S2 1 (1-P2)(1-P1)2-P 2-P1X1S 1 l+X2 0 (lP2 ) (Pl)_ 2 _ Pl- 1 2 Proof: Under stationary conditions, one can write (1) Pr{Y =v,Z'=k} = li2(u; i1'i2) n n 2 1 2 u=0,2 ~Pr{Y =v,Z'=kly =u Nn =i N2 =i} n n -l1 n-1 n-12 now, using proposition 4.2, equation (1) becomes n n u=0,2 u+i +i2>0 where r = min{c:6 +i >O,c=1,2}. Evaluating the second term on the right hand side of equation (2), it follows that Pr{Y =v,Z'=k}=7(0;0,0) p(k)+6 P (2)7(0;0 0) (X(1)+X2(1)n n kv 2kv 02 + lkPv(1)[1-(XO(1)+X2(l))f(0;0,0) ], where Xv(~) has been introduced in the proof of theorem 4.3. Now, using proposition A.7, one obtains the desired result. Q.E.D. From the above joint probability, one can find the marginal with respect to Y. In particular, the probability that the n-th output n departs is given by the following Corollary 4.5. Under stationary conditions, (P1+r2) (I-P2) Pr{Y=0}) -=(l+p —P)+1

80 Corollary 4.6. Under stationary conditions, the probability of an idle system is P2+PllS2 1-p - P2 1 2 Proof: The system becomes idle whenever N 0 and N 0, knowing that n n the n-th output departs. Hence, 1 2 Pr{idle system} = Pr{N=0 N =O=OY = 0} n n n = 7T(0;0,0) / Pr{Y =0}, n and then use corollary 4.5 and theorem 4.3. Q.E.D. Theorem 4.3 specifies stationary conditions for the M2/G2/1 queueing system with the feedback mechanism stated in section 4.1. Under stationary conditions, the means queue lengths are found as follow: First, for the mean queue lengths of type-1 units, one derives E[N ] = ZjZ (u;jk) jk u=0,2 - lim [V0 1 where V(~,11) can be evaluated by equations (8) and(9) of theorem 4.3. Second, for the mean queue lengths of type-2 units, one also derives 2 2 E[Yn+N] = E[Y ] + E[N ] n n n n

81 for E[Y ] = Pr{Y =2}, n n and E[N2] =im [ur 1 ( )+V(19~ )]; n V0 2 2 2 1 where V (1,~2) can be evaluated by equations (8) and (9) of theorem u 4.3. Theorem 4.7. Under stationary conditions, the probability that there is no type-1 units in the system is xl(l-P1-P2+P-P 2 (1-P1))+X2-PXS2 X1(1-P1P2) + 2 Proof: Consider the following for large value of n; (1) Pr{N =O} E ZT(u;O,k). n k u=0,2 Using proposition A.7 and theorem 4.3, equation (1) becomes (2) Pr{Ni=O} = RO(1) + R2(1) 2 — (O;O,O) (1- l-P2+Pl-P2(1-Pl))+X2-PlXlS %1+X2 (l-P2)(1-1)-Pll l2 Finally, making use of equation (13) of theorem 4.3, equation (2) gives the desired result. Q.E.D.

82 Notice that for = P = P2 0, theorems 4.3-4.7 give the corresponding results forM/G/l queues without feedback. Moreover, if one sets P1 = P2 = 0 in the above theorems, results on priority queues by Miller [1960] follow. If A = 0 in the above model, one obtains the M/G/1 queue with Bernoulli feedback. In fact, theorem 4.3 gives p2 < 1 - P2 as stationary conditions. This result has been first found by Takacs [1963] and can also be derived from proposition 2.11 using the method of transformation. 4.3. THE BUSY PERIOD PROCESS Here, the distributions of idle periods and busy periods are immediately found from corollary 3.21 and theorem 3.22 respectively. Proposition 4.8. The idle periods I 's are exponentially distributed m with parameter XA + X2. Proposition 4.9. Under stationary conditions the probability distribution of busy periods is given by * * 2 * H(e) G (s) = E [l-pr-(p -p )H(e)] 1-p2H2(e) where e S+X+X2 (1+X2)G (s). Proof: Using theorem 3.22 and the specific assumptions of section 4.1, one obtains

83 Luv(s;r) = (6uO+6u2)Pv(r)H (e) for u,v = 0,1,2. Therefore J(s) =,. 0 P2H2 (e) Substituting in the expression for G (s), one gets * * * -2 Pr (1-P2)H2 (e) * G (s) r l +.. Hr (e) r r r and then the desired result follow. Q.E.D. Notice that in the case of no feedback, one could obtain Miller [1960]'s results. Furthermore, if there is only one arrival stream (X1=0), one obtains results in the case of Bernoulli feedback, which are extensions of Takacs [1963]'s results and can be also found from proposition 2.16. Corollary 4.10. under stationary conditions, the mean of busy period lengths is 1 p+P2+P1X1S2-P2P m X+X 1-p-p-p- )<ST+pp [Bm] 2 2-P-P 1 12 2 1 Proof: In the usual way, one differentiates the Laplace-Stieltjes transform given in proposition 4.9, then set s = 0 and note that O (0) = - E[Bm]. Q.E.D.

84 4.4. THE OUTPUT PROCESS For the particular queueing system stated in section 4.1, several properties of the output process are now derived. From proposition 3.11, one states 1 2 Proposition 4.11. The output process {Y,N,N,O } is Markov renewal and its stationary transition probabilities are given by AUV[(ili2 ) (j l i2);x] u 2 1 2 Pr{Y =vNj,N=j O <xY =u Nn = N n n 1i n 230 n- nXIY_ n 1=iN2 =i }2 where x;f Z2kkPv(k) (le- ((x- )) e c )c e (X y) C e dHk(y) c' if +i+i2=0, A [(il 9i2) (J J 2);x]= 0 if ek< 0 some k, -cy ec x e (X y) p p~(r~n~ b dH (y) 0Pv(r) c e r if ek>0 all k; with e =j +6 -6 -i (c=l,2);r=min{c:6 +i >O,c=1,21. c c rc uc c uc c

85 Furthermore, from proposition 3.14, one states 1 2 Proposition 4.12. The random variables Y Z,N, and 0 depends n n n n n 1 2 only on Y n' N and N Moreover, its joint probability distribution is given by Pr{Y =v,Z'=k,Ni= 2 1o <x =uN-l2 = n n n 1 n - n-l1=il n-li2 fX ckpv(k)(l-ek(x Y)X)11 ( C ) dH (y) -Xy e x e ( y ) C- CC - uc c c c rc uc c Proposition 4.13. Under stationary conditions, output interval lengths 0 's are identically distributed. n Proof: Using conditional probabilities, the distribution of output interval lengths can be written as (1) Pr l 1Z.2jPr{n+l <xYn=u3N =iN2= (n) (U nl L ijrn+liXI-n nn n u0,2 where one defined the state probability just after the n-th output to be (2) r(n)(u;i,j)=PrY =u,N =i,N =j}. n n n When n tends to infinity and under stationary conditions, the state probability defined in equation (2) become

86 (n) (3) 'i(u;i,j) = lim ( (u;ij), n->oo and is independent of n. Now, from proposition 4.12 the conditional probability in equation (1) is independent of n and is found to be: ka1 (1-e ) dH(y) if u+i+j=0, (4) (4) Pr{O +l<x1Y =uN =iN =j}= H (x) if u+i+j>0; r where r=l whenever i>O and r=2 otherwise. Then, the probability distribution of On given in equation (1) is independent of n. Q.E.D. Considering proposition 4.13 and the output process {Y nNnN,On}, one can state without proof the following property. Proposition 4.14. The sequence {O } of output interval lengths forms! n a collection of mutually conditionally independent random variables given {Y l'Y, N N1N 2 N2N. g n-l nn nn-l l n Theorem 4.15. Under stationary conditions, the probability distribution of output interval lengths is * * AT F (s) [ (s+) +2 )T(O;0,0)+l-A'(0;0,0) ] 1 2 * A2 + H2(s)[(s+A+ )T2(0;0,0)+(A-1)7(0;0,0) ], 1 2 where T(0;0,0) is given by equation (13) of theorem 4.3 and A by proposition 4.4.

87 Proof: From proposition 4.13, one can write 1 2 (1) F0(x)= Zi.jPr{On+l<lYn =uNn=i,N =ji}f(u;i,j), u=0,2 after the notation F(x) = lim Pr{O <x}. 0n - Taking the Laplace-Stieltjes transform of the probability distribution given in equation (1) and using equation (4) of proposition 4.13, one obtains, as a first step, A1 2 2 (2) F!(s)= (0;0,0)(++ 2 * 2 k u0,2 j r u+i+j >O where r=l whenever i>O and r=2 otherwise. The second term on the right hand side of equation (2) is evaluated as follow: Z l.Z.H (s)f(u;i,j) u=0,2 u+i+j >O =H2(s)Zj T(0;0,ij+l)+H1(s).iZiT(0;i+li) +H2(s)Zj (2;0,j)+Hl(S) Zi Zj(2.;i+l,j) =H2(s){Zj(.(0;0,j)+lr(2;0,j) )-Tr(0;0,0)} +H1(s) {ZZ(Tr(0;i+l,ji)+7T(2;i+l,j))} =H2 (s){R( ( 1)+R ()- (0;0,0) }+H1 (s){-Ro()-R 2 (1)} using theorem 4.3. Now using proposition A.7, one obtains

88 =H2 (s) {A-l} I(0;0,0)+ 1(s) {l- (O;O,O)A}, where f(0;O,0) is given by equation (13) of theorem 4.3 and A by proposition 4.4. Then, from equation (2), one finally obtains the desired result. Q.E.D. Notice that in the case where the service periods have the same probability distribution regardless of the type of unit being served, one can state from theorem 4.15, Corollary 4.16. If H(x) - H2(x), then the probability distribution of output interval lengths is Fo(s) = H (s)( ++2 )T (o;0,)+1-(o;o,o where 'w(O;O,O) is given by equation (13) of theorem 4.3. Theorem 4.17. Under stationary conditions, the mean of the output interval lengths is: E l+pL+P2:E[O] = [ 1+p2 - +A(S2-S1 +(O;O,O)+S, where A and 'rr(O;O,O) are given in theorem 4.15. Proof: From theorem 4.15, using standard techniques, one obtains the desired result. Q.E.D. Corollary 4.18. If H (x) - H(x), then the mean of output interval lengths is

89 I+pl+p2. E[O] = X1+X2 T(0O;,0)+S, where Tr(0;0,0) is given in corollary 4.16. Notice that in the case of only one Poisson stream (X1=O), corollary 4.16 characterizes the output interval lengths for the M/G/1 queue with Bernoulli feedback. This result is new for the model first studied by Takacs [1963]. 4.5. THE DEPARTURE PROCESS Once the output process is known, it is a matter of filtering the state space to get the departure process. If one notes by D the m interval length between the (m-1)-st and the m-th departure, and by Qm the queue length of type-k units just after the m-th departure, the 1 2 sequence {Q,Q,D } would be the departure process. By definition, it 1 2 is the process {Y =,N,N,On}, obtained by filtering the states 1 2. (Y =-0,N=i,N =j) for ij=0,1,. Results from Anderson [1967] on n n filtered Markov renewal process, enable us to state Theorem 4.19. The departure process {QiQ2,D } is Markov renewal over the state space {0,1,...}X{0,1,...}. Proposition 4.20. Under stationary conditions; if Z denotes the m type of the m-th departure, then the probability of Z is given by m Pr{Z =k} 1 m k +X 6+lkXl(lp +2k(X2+Pll) +2k2+ for k=, 2 for k=l,2.

90 Proof: Under stationary conditions, one derives Pr{Y =0,Z'=2} (1I) P =2} n n P.r{Z =2} = m Pr{Y =O0 n for some n. The terms on the right hand side of equation (1) are given in proposition 4.4 and in corollary 4.5. Furthermore, one obtains Pr{Z =1} from l-Pr{Z =2}. m m Q.E.D. Notice that the random process {Z,D } could also be characterized. m m 1 20 One would need to filter the process {Y,Z',N',N,O } and then convolve n n n n n the probability distribution given in proposition 4.12. Since the convolution involves a random number of terms, one would expect the result to be messy. 4.6. APPLICATIONS TO COMPUTER MODELLING In this section, the queueing system with feedback is particularized further to a specific application: the modelling of computer time-sharing systems. Basically, there are two kinds of models: round-robin (RR) and foreground-background (FB). Each kind of model will be described and theorems from above will be used to derive results concerning these models. These results will be found identical to those previously published, whenever they could be found in literature. Notice that the emphasis in this dissertation was on building a probabilistic structure for feedback problems rather than on specific

91 results that could be obtained from RR and FB models. It so happened that our structure also fits the one used in computer modelling. Moreover, the waiting time process has been disregarded at the end of chapter 2, hence no attempt is made here to characterize the waiting time process related to these computer models; although, this constitutes one of the main interests in computer modelling. In the round-robin model (figure 4.2), jobs are taken from the queue on a first-come first-served basis and are provided with a quantum q of service. If a specific job is completed within the time interval allocated, then it is simply released from the system. On the other hand, if the specific job requires more time than the quantum, then it is removed from the service and returned to the end of the queue.- In the latter case, this job waits until all the jobs in front of it get through the processor before it gets another quantum of service. The process continues this way for all jobs. Service incomplete Service completed Jobs arri q Processor -. Figure 4.2. Round-robin model

92 Assume that jobs arrive according to a Poisson process with parameter X and that the sequence of service times form a renewal process with the partial probability distribution H(x)=l-Exp(-px). Furthermore, there is a quantum of size q>O. Here, there is only one type of unit, therefore the model of figure 4.1 can be used with X=0. Since services are exponential, the probability for a unit to feed back is given by = Pr{S>q} = e-q. For this simple model, proposition 4.1 is applied and the queue length process {Y,N } is Markovian. Furthermore the states are ergodic n n if and only if p < l-Exp(-Pq), using theorem 4.3. These results were previously obtained by Coffman [1968] for the M/M/1 queue with RR discipline. Notice that the model developed in this dissertation enables us to find much more than the results from Coffman [1968]. On one hand, one could obtain also the characterization of busy period process as well as output process for these RR model. On the other hand, one could analyze system where service times are represented by a general distribution. It is also worthwhile to note that such a RR model could be analyzed by the method of transformation illustrated in section 2.3.

93 In the foreground-backgroulnd model (figure 4.3), jobs to be processed form two queues. First, the arriving jobs form a line on a first-come first-served basis and then, one at a time, they are given a quantum ql of service. Again, if a specific job is completed within this period of time, it leaves the system. If, on the other hand, the specific job requires additional time, it is placed at the end of the second queue where it must wait, along with all similar jobs, for another quantum q2 of service. After this quantum is exhausted, if the job needs more time, it is put at the end of the second queue in a round-robin fashion. In such a model, priority is given to the first queue. Moreover, this model can be generalized to allow any number of queues, where at the end of a quantum the unfinished job is placed at the end of the next lower priority queue. In fact, this generalization has been done by Schrage [1967] where he allows a count. able number of these queues. Service incomplete Background queue q2 Service Processor- - completed Jobs arrival completed Foreground queue ql Figure 4.3. Foreground-background model

94 Assume that jobs arrive according to a Poisson process with parameter A. Moreover, suppose that the service times given to arriving jobs is exponentially distributed with parameter '1 and quantum size ql; while the service times given to the background jobs is exponentially distributed with parameter p2 and quantum size q2. Since all arrivals are of the same type, one can use the model of figure 4.1 with A2=0. The probabilities for units to feed back are pi Pr{Si>q} Exp( -iqi) for i=1,2. Again for this model, proposition 4.1 can be used and the 1 2 queue length process {YN,N } is a Markov chain. Furthermore, the "ue '"ge n n n states are ergodic if and only if Xl Exp(-lql) < 2(O1-A)[1-Exp(-2q 2)] after using theorem 4.3. 4.7. CONCLUSIONS In this chapter, a queueing model with two Poisson streams as arrival and a particular feedback mechanism was analyzed. The queue length process was completely characterized and stationary conditions explicitly found from theorems of chapter 3. As a by-product, results from Miller [1960] were obtained by considering the no feedback case. Moreover, the results of this chapter can be particularized to obtain those already known for the M/G/l queue. The probability distribution

95 of busy period lengths found in this chapter can be simplified, by considering the no feedback case, to the results found by Miller [1960]. Moreover, the treatment of the output process is completely new as far as priority queues are concerned and therefore can be viewed as an extension of results from Miller [1960]. As expected, the departure process is proved to be Markov renewal. In section 4.6, results were further particularized to the RR and FB models of computer time-sharing systems. For the RR feedback, theorem 4.3 gave the same stationary conditions previously found by Coffman [1968]. For the FB feedback, stationary conditions are also derived; these results are new as far as the author could find out.

CHAPTER 5 DISCUSSION This dissertation was concerned with the analysis of queueing systems with feedback. A literature survey revealed very few research reports in that area. In chapter 2, such systems were analyzed with a view to finding an equivalent queueing system without feedback. In chapter 3, a more general model was introduced and several properties derived. The model was then particularized in chapter 4 to the case where the arrival process is formed by two independent Poisson streams. 5.1. SUMMARY The primary contribution of this dissertation consists in the establishment of a model capable of analyzing queueing systems with feedback. The class of queueing systems is characterized by the MR /Gb/l queues; that is Markov renewal arrivals over a finite state space and renewal-type service process with one server. The feedback mechanism depends stochastically on the increment in queue length, the amount of service the unit has just received, the type of unit and whether or not the previous unit has fed back. In chapter 2, we derived necessary and sufficient conditions for the existence of an equivalence between a queueing system with feedback and a G-server queue without feedback. In the case where 96

97 such an equivalence exists, one can transform certain operating pro — cesses for queueing systems with feedback into corresponding operating processes for G-server queues without feedback. It was then found that in the class of all MRb/Gb/l queues with feedback, systems with one type of unit and Poisson arrivals are equivalent to some G-server queues without feedback. Therefore, if one studies the queue length process, the busy cycle process or the departure process for the M/G/1 queues with feedback and one type of unit, then one could use known results and make the appropriate transformation. Chapter 3 developed a model to analyze directly queueing systems with feedback. We consider the sequence of output epochs as embedding points. The queue length process was characterized by a Markov chain over a many-dimensional state space. The output process together with the departure process were proved to be Markov renewal. It turns out that this model is rich enough to generate a large number of known results for single-server queueing systems. Thus the model of chapter 3 permits us to derive results obtained by Vlach [19691] on the departure process from GI/G/l queues; results by Miller [1960] on priority queues and finally results by Takacs [1963] on the M/G/1 queue with Bernoulli feedback. In addition, the model of chapter 3 permits some extensions for the queueing systems studied by the above authors: the departure process from M2/G2/1 queues with priority and M/G/1 queues with state-dependent feedback.

98 A secondary objective is to relate queueing systems with feedback to some applications. One area of applications that uses queueing systems with feedback is the computer time-sharing modelling. The main two models used, the RR and FB models, turned out to be special cases of the model developed in chapter 4. In section 4.6, a particular case for each model is worked out, results are obtained and are shown to be the same as those previously published, whenever they already appeared in the literature. 5.2. FUTURE STUDIES The most significant assumption made in this investigation is that there is no delay for a unit to feed back. This assumption makes possible, when there is only one unit in the system, for the unit to receive two consecutive periods of service without having the server idle between the two periods. It will be a significant contribution to analyze several of the random processes introduced in this dissertation, taking into account a delay. This delay could be deterministic as well as stochastic. Moreover, it could depend on the type of unit and might affect the order of units in the feedback process. In section 2.4, it was shown that any priority rule of the kind "feedback at entry R" affects the waiting time process. In this dissertation, the waiting time process for a particular queueing system has been analyzed with R=1. In some applications, it would be advantageous to characterize the waiting time process in a queueing system with feedback for all positive values of R. Such a waiting time process might be used in the RR and RB models.

99 The busy period process analyzed in section 3.3 considered the arrival process Mb only. When the arrival process MR is considered, the busy periods generated by arrivals during the service periods of the originator become dependent. Consequently, the analysis of the busy period process in MRb/Gb/l queues has to take into account these dependencies. Nevertheless, it is believed that such an analysis can be carried out. The random process {Y,Z',N On } was characterized in proposin n -nn tion 3.14 for the arrival process Mb. In the case where the arrival process is MR, we conjecture that Y,Zn,N,KUn and On depend only on Yn_,Nn_,Kn_,Un. Furthermore, the process {Y,Z,N,Kn U, } n-l'-n-1n-n-l n n-n n n n can be used to characterize the sequence of types and the time between types in the departure stream. The sequence {O } was characterized in theorem 4.15 for the arrival process M. We conjecture that a necessary condition for {0 } ~~2'~~~~~ n to be a renewal process is to have only one Poisson arrival stream. Then, one can use results from Disney, Farrell and DeMorais [1973] to characterize completely the departure process. In section A.3 the arrival process Mb was introduced as a particular case for the arrival process ME. An arrival process more general than N but still a particular case of MR. is obtained when the arrival process is composed of b dependent Poisson streams. The dependence is such that the type of an arrival depends only on the type of the previous arrival and the time between the two arrivals

100 is exponentially distributed. We conjecture that proposition A.8 and lemma A.10 can be generalized to that arrival process. As pointed out earlier, the analysis of the busy period process will be more complicated for this new arrival process. 5.3. RELATED TOPICS The distribution of service times was assumed to depend only on the type of unit to be served, throughout the dissertation. A possible generalization would be to make the sequence of service times Markov renewal over the state space formed by all types of units to be served. We conjecture that most of the results will still hold with minor modifications. These modifications might be applied to set-up time problems. The arrival process assumed here was a Markov renewal process over a finite state space. A possible extension would be to consider a countable state space or even arbitrary state spaces (ginlar [1969]). At present, very little is known about queueing systems with feedback in which there are more than one server. The model introduced in chapter 3 uses the embedding at output epochs. It is not yet known to the author how this model can be adapted to the study of queueing systems with feedback which contain several servers. A queueing system such as the one defined in section 1.1 might contain a decomposition switch, located after a service facility, which may either feed back units to aprevious service facility or feed forward units to some further service facility. At present, it is not

101 known if a technique such as the one introduced in chapter 3 could be used to analyze either case. Nevertheless, it is believed that it will be preferable to separate the queueing network and analyze each component separately. Otherwise, the main difficulty would be to handle two or more service facilities simultaneously. Again in section 1.1, the technique of separation of queueing network into components was introduced. If we try to use this method in the analysis of queueing systems with feedback, another problem will appear. The input process in figure 1.1 is formed by the superposition of the arrival process and the feedback process. A preliminary investigation showed that these two processes are in general dependent. Therefore, one needs to study the superposition of two dependent Markov renewal processes. The analysis of the superposition of two independent Markov renewal processes has been carried out (Cherry [1972]) and proved to be complicated. Hence, it is not obvious how one should model the superposition of Markov renewal processes related by the feedback mechanism of assumption C. 5.4. CONCLUDING COMMENTS Having characterized several operating processes for queueing systems with feedback, two observations are appropriate. First, the framework underlying this dissertation suggests many more investigations. A few of these investigations are mentioned in section 5.2. Second, the basic structure assumed in section 2.1 can be generalized. Some of these generalizations are introduced in section 5.3.

102 A detailed analysis, involving particular cases, could have been done in chapter 3, but the desire for generality and the dissertation's main stream of development prevailed. There are many investigations that could be pushed further for the different random processes introduced in chapter 3. Thus, this dissertation presents only the beginning of several research topics, which hopefully will be continued. If one measures the challenge of a topic by the number of new developments which it generates, the "queueing network" topic has certainly achieved a very high score —for the author at least!

APPENDIX SOME DERIVATIONS A.1. SYSTEM OF GENERATING FUNCTIONS Lemma A.1. The generating functions for the queue length process are given by the following system: -1 u u+l Vv(~)= )[Gv(;u)[ 7T(O;0)+~ (V( )-V (~)) v - LJLV u u 0 -u O -u+l u=lu-l + ~~% G (~;k)~kl[Vk(Y)-V ( )]+G (~;u) (~)] U UVuk u -k u -k+l uv U — u for v = 0,1,...,b. Proof: Using the definition of generating function V (~) and proV - position 3.17, equation (1) of remark 3.19 becomes (1) V ((~) =; (0; O) ~JAv (0 Ji)+ E (u;i) ~-A (i j), v- Ov UV _0>O A j > for v = 0,1,...,b. The index set A is defined to be A={(u;i)(0;0O):u=0,1,,..,b,=[i ],i 0,1,...;c=l,2,.,b}. c c Let A and B be the first and the second term respectively of equation(l). Using generating functions G0v(~;h), defined in equation O.' (2) of remark 3.19, one can write (2) A = (O;O)hahG0v(~;h) 103

104 In the evaluation of the term B, one first partitions the index set into sets representing the different value of u. Hence, the term B can take the form (3) B = B + B. 0 U u On one hand, one recalls (4) Bo= rr(0;i). ~ A0v(i,j) i>O i1>0 The above summation can be further partitioned into b terms with respect to ik > 0, for k = 1,2,...,b. Let B0k denote each of the terms, with the meaning that for the term ik > 0, one also has il=i2=...=i k _l=0. Thus, one can rewrite equation (4) as (5) B = B where (6) BOk = k+l ib -k k k -=k k k+l b for ik = [O,~.0,ik'ik+l... i b] From assumption E, the type of the unit to be served is found from r=min{c:i >O,c=1,2,...,b}, t therefore r= k and the number of arrivals of each type is given by:

105 (J j for c=1,2,...,k-1; e = j +l-i for c=k; jc-ic for c=k+l,...,b. Now, using the expression for A0 (ik,J) given in proposition 3.17, equation (6) becomes -1 k k+l BOk = Go(~;k)~ (V( Vo (~ )-V where the generating functions V (~ ) are defined in remark 3.19. Hence equation (5) becomes b -1 k k+l (7) BO = zkGov(S;k)~k (V (0 )-V 0 On the other hand, for u=1,2,...,b; the term B of equation (3) can be written as (8) Bu = 7 (u;i) ~ JA (i,j). Again, the above summation can be partitioned into two groups of terms. A first group contains u-1 terms and are identified with respect to ik > 0 for k = 1,2,...,u-1. Use Buk to denote each of these terms, with the meaning that for the term with ik > 0, one also has il-...= ik =0. The second group contains only one term and is denoted kby B; it is characterized by il=i2..=i =0 i >O. Thus, equation (8) can be rewritten as (9) B =kB U k uk'

106 where (10) Bk _ i-..a ik+~J-A (i k l) k+l b with a = 1-6 uk Similarly to the logic used in evaluating equation (6), it follows that -1 k+l uv (~;k)~k ~u(Vk(k)-v (k+)) if k < u, B uk G (~;u)VU(~ ) if k = u. UV U _U Therefore, equation (9) is found to be U11) ) UV k U k u ~UV u 1 ( 11-) B = (7) (~;k) ~ (Vk(~) Vk +l (+~;u)vu(!~), k=l for u = 1,2,...,b. Combining equations (2), (3), (7) and (11) into equation (1), one obtains the desired result. Q.E.D. A.2. THE EMBEDDED MARKOV CHAIN Definition A.2. If B(';') denotes the joint probability distribution of the number of service completions and the length of the busy period of type-1 units, one defines its transform to be i+lf B (~;s) = ~+ e-sYdB(i+l;y), with I~|<1 and Re{s}>O.

107 Lemma A.3. For k > 1, Sye~'~'d{ (k) -k * k e -Yd() (k+i;y) = l[l (i;s)l; i y with ~:<1 and Re{s}>0. Proof: For k=l, this is simply a restatement of definition A.2 above. Here, we will show the statement for k=2; for k>3 the proof is similar. Recall B(2) (2+i;y) = B(2+i-j;y-t)dB(j;t). Hence, one is able to write Z~ if e SYdB (k+i;y) 1 y oo i+l ~= ~E ~ ~S e YdB(2+i-j;y-t)dB(j;t), i=-0 j=l1 now with an appropriate change of variables and change of summationindexes, one obtains the desired results. Q.E. D. Lemma A.4. Whenever the length of the busy period is finite; if F(~) = B (~pl+l-pl;X2-~X2), then F(1)=l and F)(1) = (pl+X2sl)/(-xlSl). Proof: From the definition of B (-;-), it is immediate that F(1)=l. Now, using the change of variable u = ~pl+l-pl and v = A2-~X2, the derivative of F(-) becomes (1) F' (~) p B (u;v) -- B (u;v). iu (U a

108 Note that when ~+1 then u-xl and v+0; therefore, one computes (2) lim ur B (u;v) = Zk(k+-l)B(k+l;oo). ual v+O and (3) lim B (u;v) = -f y'dZkB(k+l;y). u-*l v+O If one denotes by B1 the length of busy period of type-1 units and by A the number of services during B1, then the right hand side of equation (2) become E[A], while the right hand side of equation (3) is -E[B1]. Consequently, equation (1) is rewritten into (4) F'(1) = plE[A] + X2E[B1]. The busy period can be written as A (5) B1 = si i=l where S. represents the length of the i-th service of type-1 units. Since {S I forms the renewal process introduced in assumption B, n Wald's theorem can be used to transform equation (5) into (6) E[B1] = E[A]-S1; E[A]<oo, since the length of busy periods are finite under stationary conditions.

109 Using equation (6), the quantity given in equation (4) becomes (7) F'(1) = (P1/S1+X2)E[B1]. Since type-l units cannot feed back into type-i units in this particular case, E[B1] can be evaluated from known results of M/G/1 queues; that is, (8) [L1E[B1]= S/(1-lS1). Substituting the expression of equation (8) into equation (7), one obtains the desired result. Q.E.D. Lemma A.5. The stationary transition probabilities of the Markov 2 1 chain {Y,N IN =0} are given by 1II~ m 2 1 2 Q (i,j) = PrYm=v,Nj IYm u,Nm=O,Nml where {Qpv(l)A( l 2Dv(Oj) if u+i=0, Q (i,j) uv i Dv (d,j) if u+i>O; with d = i+6 -1. In addition, u2 D (dj)=pv(2)g 2(0j-d) 00 f + E P(2) E g 2(k' h-d)pv(1)A(f'kh),'

110 A(jskjh)= ( )p (1-p a=0 c=O -2y ji-h-c e 2) (k) f 2 dB (k+a;y) such that f=j-62 Moreover, the above transitions are defined for u,v=0,2 and i,j=0,1,.... The quantity g2(-,o) is given in proposition 4.1. Proof: The random process {Y,N IN =0} is a second Markov chain m m m embedded in the original one, {Y,N1,N2}, where one considers the states 1 (u;O,i) such that Nn=0, that is, whenever there is no type-I unit in the system just after a service completion. Thus, the one-step transition probabilities can be denoted by 2 1 2 (1 ) QUv (i,j)=Pr{Ym=v, Nm=JYm uN=O,N =i}, uv ' m m i-i m nm-' for u,v=0,2 and i,j=0,1,... In finding these transition probabilities there are two cases to consider; i) u+i=0: In this case, the system becomes idle just after some output epoch t' Let Z be the type of the first arrival after m-l' m tm-' thus equation (1) becomes 22 2. 1= 2 (2) Qov(O,j)= ZrarPr{Ym=v,Nm= JYm- Nl1=0 m Nm = m=r} type-l x B1X —B. -* m-l m (o0;0o,o) (v; O,j) Figure A.1. Busy period of type-l units

111 In the case of an arrival of type-1, one needs only to consider the busy period of type-1 units, denoted by B1, with an appropriate number of arrivals of type-2 during B1; thus from figure A.1, it is readily verified that (3) Pr{y vN2 jly =O,Nm=j m l=0, N21} m m m-lm r-' m -X2y j-c 00(l) CCX~a~n - (e XJY 2Y ) =pv (.1) E (ca)pcl ( -p1 )acre 2 dB(a+l;y), a=0 c=0 where B(;-) represents the joint probability distribution of the number of service completions and the length of the busy period of type-i units introduced in definition A.2. type-2 |e --- S2 --- —----- B....... S - ' t' t t' m-l n m (0;0,0) (e;k,h) (v;O,j) Figure A.2. Service time preceding the busy period In the event that an arrival of type-2 comes first, one needs to consider its service time S2 and then possibly the busy period generated by the k arrivals of type-1 during S2. Then, from figure A.2, it follows that 2 1 2 Pr{Y =vN Ym- =0, =0 21 (4) PrmY vN'm=Y3 - 1 2,mZ =2} Tn m n7"- 00 f v(2()+Pv(1)' Pe(2 ) k1 g2(khh)A(f'k'h)' e=0,2 k=l h=0

112 where oo f-h A(fkhk+al c k+a-1-c ~)p C 1P (1-p1 a=O c=O f-h-c JX2Y (A2Y) (k) (f-h-c)! dB (k+a;y) y (f-h-c)! with f=j-6e2 and gr(-,-) was introduced in proposition 4.1. ii) u+i>O: In this case, a unit of type-2 enters into service facility immediately after t therefore, a service time S2 is m-l' 2 first considered; the situation can be illustrated in figure A.3 below. ~Br ~(k) I t' t t'xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx m-l n m (u;o,i) (e;k,h) (v;0,j) Figure A.3. Busy period without idle period This case is similar to the one in figure A.2 with no idle period; therefore, one can use equation (4), to write (5) Q (i,j)=p (2)g2 (Oj-d) uv 00 f +p(1) Z Pe(2) Z g2(kh-d)A(fk,h), e=0,2 k=l h=d where d=i+6u2-1 and f=j-2; this is for j>i+62-1.

113 For j<i+6 2-1, Q (i,j)=O since both terms on the right hand side of equation (5) becomes zero. Now, combining equations (3), (4) and (5) through equation (2), equation (1) gives the desired result. Q.E.D. Lemma A.6. For the embedded Markov chain {Y,N N1=O}, the generating m' m m m functions G.(~) = ZjTf(v;j)~J(~l <1 and v=0,2) are such that 2 — m~ F(0; 0) = (1-P1- 2+Pl-P 2 1-l)>+2-Plsj GO(1)+G2(i) = 01+ 2 (1-P2)(1-Ol)-02- P 11S! where pk=XkSk for k=l,2. T0(v;j) denotes the stationary probabilities for this Markov chain. Proof: Associated with the embedded Markov chain {Y,Nm I N=O0}, let the stationary probabilities be 2. 1 T0(v;j) = lim Pr{Y =v,N N =0}, 0 n n nn which are such that (1) vJ 0T(v;j) (= i Zi0(u;i)Q (i'j)' u=0,2 where the transition probabilities Q (i,j) are given in lemma A.5. UV Now, multiplying equation (1) by ~J and summing over for j=0,1,..., one obtains (2) G (O;)v Q v(0')j+)+ Tf0(U;i)j JQu(i'J) ' u=0,2 i=O u+i>0

114 Using lemma A.5, the first term of equation (2) can be rewritten as (3) (Ogj) oq0v(O')dJ B (dl;d) + a2{pv(2)H2(a)+p v()d2d1 (H2(b)-H2(a))}, and the last term of equation (2) is evaluated by the following two equations: (4) Eri0E (0;i+l)Z~JQ0v(i+lj)=~ ((~)-i0)(0;0)){pv(2)H2(a) + Pv(1)d2dl (H2 (b)-H2(a)) } i 0 (2;i)j ~JQ2v (i, j )=G2 (~) {Pv (2) H2 (a) + P (l)d2dl (H2(b)-H2(a))}. Collecting equations (3), (4) and (5) together, equation (2) becomes (6) Gv(~) = T (O;O)A (~)+[~ (G(~)-(0;0))+G(~)]Bv(~) v 0 ' 0 2 for v=0,2, where A (~) is the right hand side of equation (3) and V B (~) is the coefficient of G2(~) on the right hand side of equation v (5); while a = 1 2 - ~X2' c = 2 - 2' b = a - X1B(dl;ck k k' for k = 1,2; B (-;-) has been introduced in definition A.2.

115 Solving equation (6) for G0(~) and G2(~), it is readily verified that (l-B2(~))A0(~)+(A2 (~)-1)Bo(~) G0(~) = M 0(0;) -l l-B2(~)-~ Bo(~) -1 A2(~ )-~ B2 (~)+A2 (~)B(~)-Ao(~)B2(~)] G(~) = 0(~0;) - 1l-B2(~)-~ Bo(~) Adding G0(~) and G2(~); using L'Hospital's rule with ~+1-, and finally substituting the expression found in lemma A.4, one obtains the desired result. Q.E.D. 1 2. Proposition A.7. For the embedded Markov chain {Ym,N=0,N1m}, the generating functions R (~) = EZ.(v;O,j)BJ(~I<<l and v=0,2) are such that 2- - 0(1)+R(0;0,0) 1l (1-p1-P2+P1-P2 (1-p )))+ +X2-pPx1SS2 R (1) +R (1) X1+T I (1-P2)(1-Pl)-p2-PlS 2 where pk=kkSk for k=0,2. w(v;O,j) denotes the stationary probabilities for this Markov chain. 1 2 Proof: Consider the two embedded Markov chains {Y,Nm=0,N2} and {Y,N N =0}. On one hand, if states (v;O,j) are filtered from the 12 1 2 process {Y N1,N }, on obtains the filtered Markov chain {Y,N =O,NM}. mm m m m m 1 2 On the other hand, if one conditions the process {Y,N,N } by the n n n event N = 0, the Markov chain {YmNINm =O} is obtained. Consequently, n ' m' m the sets of sample paths generated by {Y, N=O,N2} and {Y,N 21N=O} are identical. Therefore, the stationary probabilities of these Markov chains are the same; thus

116 g0(v;j) = 7(v;0,j), for v=0,2 and j=0,1,.... Then, from lemma A.6, it follows that R (~) _G (~), v V for v=0,2; and one obtains the desired result. Q.E.D. A.3. A SUB-CLASS OF ARRIVAL PROCESSES Proposition A.8. MR = b if and only if the arrival process stated in assumption A has the stationary transition probability distributions given by Ahk(X) = k(l-e ), where ak = Xk/EX for h,k = 1,2,...,b and x>O. ZX represents the summation of Ak for k going from 1 to b. Proof: The necessary part is easily obtained by considering results from McFadden [1962] and Cherry [1972]. The sufficiency is first proved for b=2; let Tk be the time interval between two arrivals of type-k units for k=l,2. If N denotes the number of arrivals necessary to obtain a second type-k unit, then N is a random variable with the range {1,2,..}. Now, the probability distribution of T1 is derived as follow: 00 (1) FT (x) = Pr{Tl<xN=n}, 1 nl 00 OO

117 Assumption A is used to find (2) * All (S) if n=l, F (s n) T 7f; J1C n-2 * 1 ' A12(s)[A22(s)] A21(s) if n=2,3,...; where *k (3) (S) Ahk(s) = — +s, for h,k=1,2. Thus, using equations (2) and (3) into equation (1), one obtains F (s) i+s that is, T1 is exponentially distributed with parameter %1. Similarly, one can show that T2 is also exponentially distributed with parameter Since the stationary transition probability distribution, Ahk() does not depend on h, the types of two consecutive arrivals are independent. Also, since Tk(k=l,2) has the usual forgetfulness property, the arrival process is M2. For the case b>2, one can form two groups: X1 and X' = 1 2 A2 +. + X+ b and use the method above to show that Tk(k=1,2...,b) has the usual forgetfulness property. Therefore, the arrival process is Mb. Q.E.D.

118 The forgetfulness property is well-defined in the context of renewal processes. Since the arrival process considered in this paper is Markov renewal, let us extend the forgetfulness property to more general random processes. Definition A.9. A Markov renewal process {Z,S } such that n n Pr{Z =k, X<x+ylZ lh, X>x=Pr{Z =k, Xn<y}, is said to have the forgetfulness property. Remark that whenever the Markov renewal process {Z,X } has m m only one type, definition A.9 becomes the usual forgetfulness property. Lemma A.10. A Markov renewal process {Z,X } over the finite n n ergodic state space {1,2,...,b} has the forgetfulness property if and only if the transition probabilities are given by -xZe Ahk(x) =k(l-e ), for h,k=l,2,...,b. Proof: On one hand, if the transition probabilities of {Zn,X } is the one specified above, the equation of definition A.9 is obviously satified and one obtains the forgetfulness property. On the other hand, if {Z,X } satisfies the forgetfulness pron n perty, then from definition A.9, one obtains Ahk (x+y) -Ahk( x) = buA(y) (1) CuA (y)$ 1-Bh (x) r r rk where ur is the stationary probability associated with the Markov chain {Z } given in assumption A. m

119 From assumption A, the transition probabilities satisfy Ahk(O+)=O, hence equation (1) can be rewritten as Ahk (x+y) -Ahk(x) b Ark (y) -Ark (O+) Y = (1-Bh (x))Zrr y By taking the limit as y goes to O+ in the above equation, one gets (2) Ahk(x) (l-Bh(x))urArk+) these derivatives exist from assumption A. Notice that a particular solution of the differential equation given by equation (2) is precisely Ahk(x) = k(l-e ) The boundary condition Ak(0+)=O is satisfied by the above solution; therefore, this solution is unique and one obtains the desired result. Q.E.D.

REFERENCES ANDERSON, L.B. [1967] "Filtered Semi-Markov Process," Master Thesis, Northwestern University, Evanston. BENES, V.E. [1962a] "Heuristic Remarks and Mathematical Problems Regarding the Theory of Connecting Systems," Bell System Technical Journal, Vol. 41, No.4, pp. 1201-1248. [1962b] "Algebraic and Topological Properties of Connecting Networks," Bell System Technical Journal, Vol. 41, No. 4, pp. 1249-1274. BURKE, P.J. [1956] "The Output of a Queueing System," Operations Research, Vol. 4, No. 4, pp. 699-704. CHLANG W. [1970] "Single-Server Queueing Processes in Computing Systems," IBM Systems Journal, Vol. 9, No. 1, pp. 36-71. CHERRY, W.P. [1972] "The Superposition of Two Independent Markov Renewal Processes," Ph.D. Dissertation, The University of Michigan, Ann Arbor. SINLAR, E. [1965] "Analysis of Systems of Queues in Parallel," Ph.D. Dissertation, The University of Michigan, Ann Arbor. [1969] "On Semi-Markov Processes on Arbitrary Spaces," Proceedings of the Cambridge Philosophical Society, Vol. 66, pp. 381-392. COFFMAN, E. G., JR. [1968] "An Analysis of Computer Operations Under Running Time Priority Disciplines," Proceedings of ACM Symposium on Interactive Systems for Experimental and Applied Mathematics, Ed. M. Kleser, Academic Press, New York. COHEN, J.W. [1969], The Single Server Queue, Wiley, New York. DAVIGNON, G.R. [1972] "Queues with Dependent Feedback," Technical Report No. 72-11, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor. DISNEY, R.L.; FARRELL, R.L.; DeMORAIS, P.R. [1973] "A Characterization of M/G/1/N queues with Renewal Departure Processes," Management Science, Vol. 19, No. 11, pp. 1222-1229. FINCH, P.D. [1959] "Cyclic Queues with Feedback," Journal of the Royal Statistical Society B, Vol. 21, No. 1, pp. 153-157. 12n

121 JACKSON, J.R. [1957] "Networks of Waiting Lines," Operations Research, Vol. 5, No. 4, pp. 518-521. [1963] "Jobshop-Like Queueing Systems," Management Science, Vol. 10, No. 1, pp. 131-143. LANCASTER, P. [1969] Theory of Matrices, Academic Press, New York, pp. 288-298. McFADDEN, J.A. [1962] "On the Lengths of Intervals in a Stationary Point Process," Journal of the Royal Statistical Society B, Vol. 24, No. 2, pp. 364-382. McKINNEY, J.M. [1969] "A Survey of Analytical Time-Sharing Models," Computing Surveys, Vol. 1, No. 2, pp. 105-116. MILLER, R.G. [1960] "Priority Queues," Annuals of Mathematical Statistics, Vol. 31, No. 1, pp. 86-103. SAATY, T.L. [1961] Elements of Queueing Theory, McGraw-Hill Book Company, New York. SCHRAGE, L.E. [1967] "The Queue M/G/1 with Feedback to Lower Priority Queues," Management Science, Vol. 13, No. 2, pp. 466-474. TAKACS, L. [1962] Introduction to the Theory of Queues, Oxford University Press, New York. [1963] "A Single-Server Queue with Feedback," The Bell System Technical Journal, Vol. 42, pp. 505-519. VLACH, T.L. [1969] "The Departure Process from the GI/G/1 Queue," Ph.D. Dissertation, The University of Michigan, Ann Arbor. WYSZEWIANSKI, R.J. [1974] "Feedback Queues in the Modelling of Computer Systems: A Survey," Technical Report No. 74-1, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor.

UNIVERSITY OF MICHIGAN 3 0111111119 7255 3 0502519 7255