Queueing Systems 43, 129–146, 2003 2003 Kluwer Academic Publishers. Manufactured in The Netherlands.
A Two Priority Queue with Crossover Feedback E.M. JEWKES
[email protected] Department of Management Sciences, University of Waterloo, Waterloo, ON, Canada N2L 3G1 D.A. STANFORD
[email protected] Department of Statistics and Acturial Sciences, University of Western Ontario, London, ON, Canada N6A 5B7
Received 27 October 2000; Revised 5 August 2002
Abstract. This paper considers the delay distributions in a two-class non-preemptive priority queue with crossover feedback. Specifically, there are two priority classes, and the Poisson arrival process for each class can be subdivided into two groups: one group which only requires service at the priority level to which it arrives, and another group which requires subsequent service after it feeds back to the other queue. Our main result is the determination of explicit expressions for the distribution of delay until final service commences for each the four types of customers. Keywords: priority queues, feedback, level crossing analysis, Laplace–Stieltjes transform
1.
Introduction
This paper considers the delay distributions in a two-class non-preemptive priority queue with crossover feedback. Specifically, there are two priority classes, and the Poisson arrival process for each class can be subdivided into two groups: one group which only requires service at the priority level to which it arrives, and another group which requires subsequent service after it feeds back to the other queue. This model has applications in processor sharing models where jobs consist of several prioritized tasks and in manufacturing systems where different classes of products may require one or two tasks to be performed in a specified order, and where the system operates with a preference (namely, a priority arrangement) for one task over the other. Literature related to the present paper falls into two categories. In the first, researchers determine optimal operating policies for queues with customers that feed back for multiple phases of service. Tcha and Pliska [14] used a semi-Markov decision formulation of an M/G/1 feedback model with linear costs and discounted rewards to find the optimal service policy for the server. The optimal policy is to serve customers according to a strict priority ordering of the customer classes. A similar priority ordering was proved by Klimov [9,10] where customers require service in a series of phases, with one queue for each phase. Customers are routed from one phase (queue) to the next ac-
130
E.M. JEWKES AND D.A. STANFORD
cording to a fixed probability rule and are served on a non-preemptive basis by a single server. Klimov minimized the expected average reward per unit time to solve for the optimal service policy rule. Many of these papers have been summarized in the chapter on arm-acquiring bandits in Walrand [15]. Though these results give the optimal operating policies, they do not give waiting or flow time characteristics generated from the optimal policies. In the second category of related work, a priority ordering of customers’ service phase requirements is assumed and waiting or flow time characteristics are derived. These papers have in common the idea that customers require up to K phases of service, and feed back after each stage with phase-dependent probabilities. Daigle and Houstis [4] and Daigle [3] study an M/G/1 model of a multi-priority queueing system. Each job consists of a set of K tasks that are completed in a prescribed order and each has an arbitrary priority index. Tasks are served on a priority basis in a preempt resume fashion. Daigle and Houstis [4] examined a single job type with K task types and Daigle [3] extend the model to C job types. In both papers, the authors derived mean sojourn times for an arriving job and showed how the results could be applied to the design of communication processing systems. Jewkes and Buzacott [7] derive the Laplace–Stieltjes transform for waiting time distributions in an M/G/1 system in which each arrival feeds back with phase dependent probabilities for up to K unique phases of service. Customers are served on a FCFS basis within priority class. Simon [13] used Little’s law to find mean queue lengths in queuing systems where customers require several stages of service and feed back one or more times to receive service. Other work on priority feedback queues assumes that when a customer receives service, it feeds back with a given probability no matter how many times it has been served before. For example, Fontana [5] and Fontana and Berzosa [6] find stationary queue-length distributions for a two class M/G/1 system with such feedback. In the present paper, we look at a single server queue in which four types of customers are processed. Each customer type requires one, or two phases of service. Our main result is the determination of exact explicit expressions for the distribution of delay until final service commences for each the four types of customers. This task turns out to be complicated by the detailed interactions of the various customer types, the priority discipline, and the feedback mechanism – a complication apparently recognized by the previous work which almost entirely addresses the question of average delay. In order to reveal the complexity of the system’s operation, we initially focus on the derivation of explicit, tractable formulas for the average delay for all customer types in section 3. The relationship between two of the average delays is explored. Numerical examples investigate the sensitivity of the average delays to various factors and confirm previous results for the optimal priority ordering of the classes to minimize the average delay. We then turn our attention in section 4 to characterizing the Laplace–Stieltjes transforms of all of the delay distributions.
TWO PRIORITY QUEUE WITH CROSSOVER FEEDBACK
131
Figure 1. Illustration of feedback queuing system.
2.
System description
Consider the single server queueing system depicted in figure 1. There are four different customer types, each of which arrives according to a Poisson process. They are distinguished by their processing needs. ‘HA’ arrivals require only a high priority service (phase A) before they leave the system. ‘HB’ customers require a high priority service first, and then re-enter the system as low priority customers for a second, low priority service time (phase B). ‘LA’ customers require a low priority service time only (phase A), while ‘LB’ customers require a low priority service first, before being fed back for a high priority service time (phase B). These four customer types arrive at rates λHA , λHB , λLA and λLB , respectively. The aggregate external arrival rate for each priority class is λi = λiA + λiB , i = H, L, and the overall arrival rate is λ = λH + λL . Customers are served on a non-premptive, first-come-first-served basis within each priority class so that a low priority service can only begin when there are no customers waiting in the high priority queue. The high priority service time H is a random variable with mean E(H ), second moment E(H 2 ), CDF GH (x) and Laplace–Stieltjes ∞ Transform (LST) gH∗ (s) = 0 e−sx dGH (x). Similarly, a low priority service time L is a random with mean E(L), second moment E(L2 ), CDF GL (x) and LST ∞ variable ∗ −sx gL (s) = 0 e dGL (x). The expected processing time for a random customer, E(S), is defined by (λL + λHB ) (λH + λLB ) E(H ) + E(L), λ λ where we assume that ρ = λE(S) < 1 to ensure system stability. In this paper, we are interested in finding the mean and distribution of the waiting time for each of the four different customer types from the point of their external arrival to the system to the time at which they begin their terminal service time in the system. E(S) =
132
E.M. JEWKES AND D.A. STANFORD
In the next section, we determine the expected time each type of arrival waits in the system prior to its terminal service. Following this, we move to a level crossing analysis of queues and to delay busy period analysis to characterize the LST of the waiting time distributions. In carrying out the level crossing analysis, we point out several characteristics of this queueing system which make it difficult to analyze in an exact manner. 3.
Derivation of mean delay times with Little’s law
In this section, we derive the mean time a random customer spends queued and waiting for service by using Little’s Law. A similar analysis for more general feedback queues can be found in [13]. His solution, however, is in terms of a set of linear equations to be solved numerically, whereas ours is in terms of a set of explicit equations that provide insight about the system operation. We start with HA customers, and as it is convenient, move to the feedback delay experienced by LB customers, and then, finally, we turn to HB and LA customers. 3.1. Expected delay in the high priority queue for an HA or HB customer Let wiA and wiB refer to the average time a random customer spends waiting from its external arrival epoch to its first (A) and second (B) phase of service i, i = H, L. Furthermore, we use the notation qiB to denote the mean time an HB or LB customer spends waiting in the queue for its second phase of service so as to distinguish it from the overall waiting time wiB = wiA + E(i) + qiB , i = H, L. Upon arrival to the system, a random arrival observes, on average, the following numbers of customers in the high and low priority queues: • • • • • •
λH wHA customers waiting for their first (high priority) service, λLB qLB customers waiting for their second (high priority) service, λL wLA customers waiting for their first (low priority) service, λHB qHB customers waiting for their second (low priority) service, a high priority service in process with probability (λH + λLB )E(H ), and a low priority service in process with probability (λL + λHB )E(L).
The mean time until an H customer (i.e. HA or HB) begins its high priority service time, wHA , can be determined in a directly analogous fashion to Kleinrock [8]. It consists of the average time w0 until the customer in service (if any) has finished service, plus the time to serve the work that the arrival finds in the high priority queue ahead of it. The conditional average remaining delay given a type i service is encountered is the mean forward recurrence time E(i 2 )/2E(i), i = H, L. Therefore w0 is given by w0 =
(λL + λHB )E(L2 ) + (λH + λLB )E(H 2 ) . 2
(1)
TWO PRIORITY QUEUE WITH CROSSOVER FEEDBACK
133
It follows immediately that wHA is given by wHA = w0 + E(H )(λH wHA + λLB qLB ),
(2)
(1 − ρH )wHA = w0 + λLB E(H )qLB ,
(3)
so that
where ρH = λH E(H ). To complete the solution for wHA , we need to know qLB , the average time an LB customer spends waiting in the high priority queue before it gets its high priority service. 3.2. Expected delay in the high priority queue for an LB customer Prior to determining the remaining delays in the system, we note that qLB and qHB represent delays measured from a feedback instant, whereas wHA and wLA are measured from arrival instants. This is a major reason behind the difference in notation we employ. From the PASTA property, we know that the latter delays equal their time averaged equivalents. The delays qLB and qHB are best viewed as delays embedded at feedback instants, or related to a set of “Palm probabilities” at such transition instants. Serfozo [11] defines the “Palm probability” of a transition of interest as a ratio of relevant transition intensities embedded at key transition instants. Of note is the fact that we have no need to actually calculate the Palm probabilities. Rather, by an analysis of what is in the queues at a key instant in time, we are able to determine the specified delays. In the case of qLB , we exploit the fact that the high-priority queue is empty when the LB customer commences its low-priority service. In the case of both wLA and qHB , we are able to assess what was expected to be in the system upon arrival, and in the latter case, how the system is expected to have evolved up to the instant that the HB customer feeds back. We now turn to deriving the expected delay in the high priority queue for an LB customer. When an LB customer first enters the system, it must wait until all the LA and fed back HB customers in the low priority queue ahead of it are served, and then for all remaining HA and LB customers in the high class queue to be processed. When it commences its low priority service, there will be no high priority customers in the system. While the LB customer is obtaining its low priority service, the expected number of high priority arrivals to enter the system is λH E(L). Finally, when the LB customer finishes its low priority service and feeds back as a high priority customer, these customers will be the only ones to delay the LB customer from getting its high priority service. Hence, qLB = λH E(L)E(H ),
(4)
w0 λLB E(H )2 λH E(L) + . 1 − ρH 1 − ρH
(5)
and therefore we have wHA =
This completes the derivations of wHA and qLB .
134
E.M. JEWKES AND D.A. STANFORD
3.3. Expected delay in the low priority queue for an HB customer The mean delay an HB customer encounters while waiting for its low priority service, qHB , can be found by examining the average number of customers in the system at the conclusion of the high priority service time of an HB customer. Below, we distinguish among customers according to the queue they are in at the moment the HB customer feeds back. In the high priority queue we expect to find the following number of customers: • λH (wHA + E(H )) high priority customers who arrived after the tagged HB arrival. • With probability λLB E(L), there was an LB customer in its first service at the HB’s external arrival epoch, and it will have fed back into the high priority queue. The expected number of customers in the low priority queue is as follows: • With probability λHB E(H ), another HB customer was in service at the tagged HB’s external arrival epoch, and it will have fed back into the low priority queue. • The λL wLA + λHB qHB customers present in the low priority queue upon arrival of the tagged HB customer will still be there. • The λHB wHA HB customers present in the high priority queue upon arrival of the tagged HB customer will now be in the low priority queue, and • λL (wHA + E(H )) new low priority customers are expected to have arrived during the tagged HB customer’s sojourn time in the high-priority queue. The delay that an HB customer encounters in the low priority queue is the sum of 1. the time required to serve all the customers ahead of it in the high and low priority queues listed above, including the high class service time of LB customers found in the low class queue at the internal feedback epoch of the HB customer, and 2. the time required for the high priority services of the H customers who enter the high class queue while the HB customer is still in the low priority queue (i.e. a delay busy period induced by 1). Thus, qHB =
1 1 − λH E(H ) × λL E(L) + λLB E(H ) wLA + λHB E(L)qHB + λLB E(L)E(H ) + λHB E(L) + λH E(H ) + λL E(L) + λLB E(H ) wHA + E(H )
(6)
or qHB =
[ρL+ wLA + λHB E(L)qHB + λLB E(L)E(H ) + ρ(wHA + E(H ))] , 1 − ρH
(7)
where ρH+ = λH E(H ) + λHB E(L) and ρL+ = λL E(L) + λLB E(H ) are the total utilizations of the server by H customers and L customers, respectively. We observe that ρ = ρH+ + ρL+ is the total utilization of the server.
TWO PRIORITY QUEUE WITH CROSSOVER FEEDBACK
135
In (7), the terms in the square bracket represent the time to complete 1 above. This is then divided through by (1 − ρH ) to account for a delay busy period of high priority services [2]. After rearranging to isolate qHB , we obtain qHB =
ρL+ wLA + ρ(wHA + E(H )) + λLB E(L)E(H ) . (1 − ρH+ )
(8)
Notice that qHB is in terms of wHA , which is known, and wLA , which is not. A derivation similar to that for qHB will be used in the next section to find wLA . Substitution into (8) yields qHB . Since we wish to find the total mean delay to the start of the terminal service time for an HB customer, we ultimately have wHB = wHA + E(H ) + qHB .
(9)
3.4. Expected delay in the low priority queue for an LA or LB customer Consider a tagged external LA or LB arrival. It sees the same mean number of customers in the queues as an HA arrival (see the discussion of wHA ), but these customers will delay the tagged arrival from obtaining its low priority service differently. The L arrival will wait for everything an HA arrival would wait for, and more. The common terms are: • the completion of the residual processing time of the customer in service w0 , and • the service time for all customers currently in the high priority queue. The extra delay that an L arrival will experience includes the following: • if the customer in service at the external arrival epoch is an LB customer receiving its L service, the H service time of this customer, plus • the total service time of all customers already in the low priority queue (which includes the high priority service times for LB customers); and • all high priority customers that arrive while the LA customer is waiting for its low priority service (a delay busy period similar to that of section 3.3). The sum of all of these delays has the following expected value: wLA =
[wHA + λLB E(L)E(H ) + ρL+ wLA + λHB E(L)qHB ] . 1 − ρH
(10)
After reorganising terms to isolate wLA we get wLA =
[wHA + λHB E(L)qHB + λLB E(L)E(H )] . 1 − ρH − ρL+
(11)
Note that wLA is in terms of wHA , which is known, and qHB , which is not known. By solving (8) and (11) simultaneously to obtain wLA and qHB , we get wLA =
δβ + ελHB E(L) αβ − λHB E(L)ρL+
(12)
136
E.M. JEWKES AND D.A. STANFORD
and qHB =
δρL+ + εα , αβ − λHB E(L)ρL+
(13)
where α = (1 − ρL+ − ρH ), β = (1 − ρH+ ), γ = λLB E(H )E(L), δ = wHA + γ , and ε = ρ(wHA + E(H )) + γ . An alternate method for determining wLA and qHB which provides additional insight consists of identifying identical terms in both expressions. Denoting the sum of these identical terms by Y , we find that Y = ρL+ wLA + λHB E(L)qHB + λLB E(H )E(L)
(14)
which depends upon both wLA and qHB . Straightforward manipulation in terms of Y in the equation for wLA yields the simple expression wLA =
wHA + Y . 1 − ρH
The corresponding expression for qHB is 1 Y + ρ wHA + E(H ) . qHB = 1 − ρH
(15)
(16)
In (14), Y represents the average amount of work present in the low priority queue at a random customer arrival instant. The first term represents the average amount of LA and LB work (including H service times for LB customers), the second term represents the L service times for HB customers present in the low priority queue, and the third term is the delay caused an L arrival if it finds an LB customer receiving its L service. Equation (15) shows how we can compare the mean delays seen by two fictitious arrivals, one being an LA customer and the other HA. First, the work presently in service or in the high priority queue will be served (namely, wHA ), during which the work represented by Y will remain unchanged. Apart from the later high priority arrivals that further contribute to wLA (which are accounted for in the denominator), the server is free to attend to the work comprised in the Y term once wHA is finished. We can explain qHB similarly. Note that all of the components of Y likewise contribute to qHB . The other components that contribute are due to the L and H customers that arrive to the system prior to the feedback of the HB customer (this has mean value (ρL+ + ρH )(wHA + E(H ))), and the other HB customers present upon arrival who feed back ahead of the tagged customer (this has mean value λHB (wHA + E(H ))E(L)). The total of these terms is ρ(wHA + E(H )). Consider the following examples where λH = λL = 0.10 customers per minute, λHB /λH = 0.05, λLB /λL = 0.05 and CV H = CV L = 1. Figure 2 illustrates the waiting times for example 1 where E(L) = 5 minutes, and E(H ) ranges from 1 to 3.5 minutes. Figure 3 shows the waiting times for example 2 where E(H ) = 5 minutes and E(L) ranges from 1 to 3.5 minutes. As expected, wHA is not much affected by the increase in traffic intensity, nor is qLB . However, as would be expected, the delay to customers waiting in the low class queue is dramatically affected by increased traffic intensity.
TWO PRIORITY QUEUE WITH CROSSOVER FEEDBACK
Figure 2. Illustration of expected waiting times for example 1.
Figure 3. Illustration of expected waiting times for example 2.
137
138
E.M. JEWKES AND D.A. STANFORD
It can also be observed, by (16), that qHB is typically a bit greater than wLA when E(H ) is larger than E(L). Figure 2 shows, however, that for small values of E(H ) relative to E(L), wLA exceeds qHB . Our tests also confirmed that while the difference between the two usually grows in absolute terms as the occupancy increases, these average delays approach each other in percentage terms. One other note from the two figures is worth mentioning. If the mean delay to a randomly arriving customer is computed for each of the alternatives in figures 2 and 3, it can be observed that the mean delay to an arriving customer in figure 3 is higher than in figure 2 (for the comparable mean service times for high and low class services). This arises because the priority assignment for the two phases of service is optimal for figure 2 and not for figure 3. Tcha and Pliska [14] and Klimov [9,10] show that for a feedback queue with given service times and feedback probabilities, the service policy which minimizes the mean delay to a random arrival is a strict priority ordering of the customer classes. In the present model, the mean delay to a random arrival is minimized if the highest priority is given to the customer class which has the lowest expected remaining processing time. This is the case with figure 2. We note that our initial formulation assumes that the priorities are fixed, however, one could seek to find which priority ordering produces the minimum mean delay. Daigle and Houstis [4] and Daigle [3] look at this issue in a processor-sharing environment. This concludes the derivation of the expected waiting times for each customer type. We note that while it was straightforward to determine wHA and qLB , the solutions for wLA and qHB were inter-related. As we present in the next section, this gives rise to some complications in deriving the LST of these waiting time distributions. 4.
The Laplace–Stieltjes transformations of the delay distributions
In this section, we make use of a combination of level crossing analysis and standard delay cycle analysis to determine the LST of the distribution of the delays described in section 3. 4.1. The LST of the HA delay distribution We begin by deriving the LST of the distribution of the waiting time until an HA or HB customer receives their high priority service. We note that a busy period of the server consists of a series of delay busy cycles (see [2]), the first beginning with the arrival that finds an empty system, and each subsequent one starting at the instant when the high priority queue has been emptied and the server is free to begin processing the low priority queue. We will henceforth refer to these points in time as “L instants”. Every HA or HB customer that is delayed arrives during one of three distinct types of delay cycles, each ending at an “L instant”. These distinct cycle types are “H cycles”, which commence whenever an H arrival finds an empty system, “L cycles”, commencing whenever an LA or HB customer start their low priority service and “LB cycles”, which start whenever
TWO PRIORITY QUEUE WITH CROSSOVER FEEDBACK
139
∗ an LB customer starts its low priority service. We can condition wHA (s), the LST of the waiting time distribution for an HA customer, on the type of cycle observed upon arrival: ∗ ∗ (s) = π0 + πi wHA (s|i), (17) wHA i
where πi is the probability of arriving during a type i delay cycle, π0 is the probability ∗ (s|i) is the conditional LST of the HA delay distribution of not being delayed and wHA given that the arrival entered the system during a type i delay cycle. We calculate πi as follows: both H and L cycles start with the appropriate service time and continue until there are no high priority customers left in the system. Hence the expected duration of an i cycle is mi = E(i)/(1 − ρH ), i = H, L. Since a fraction (1 − ρ) of the class-H arrivals initiate these cycles, it follows that πH =
λH (1 − ρ)E(H ) ρH (1 − ρ) = . 1 − ρH 1 − ρH
(18)
In like fashion, L cycles occur at rate λLA + λHB , so that πL = (λLA + λHB )E(L)/ (1 − ρH ). Finally, since π0 = 1 − ρ, we have πLB = 1 − π0 − πL − πH =
λLB (E(H ) + E(L)) . 1 − ρH
(19)
∗ (s|i) for We now employ level crossing techniques to simultaneously derive wHA i = H, L. While delay cycle analysis on its own would suffice for present purposes, level crossing techniques will be used to determine the LA delay distribution in the next section and that exposition is made easier if level crossing is first introduced here. Define vt to be the time an HA or HB customer would have to wait for its high class service if it were to enter the system at time t. It equals the virtual waiting time for an HA or HB customer at time t. In the case of H delay cycles, the arrival initiating the delay cycle causes vt to jump from 0 by the high priority service time of the external arrival. In the case of L delay cycles, vt jumps from 0 by the low priority service time of the arrival. During the delay cycle, each external high priority arrival causes the workload to jump by an amount equal to the high priority service time of the arrival. Between arrivals, the workload declines as the server processes the customers. An illustration of H, L and LB delay cycles can be found in figure 4. Let vHA (x|i) be the conditional density function for the virtual waiting time for a high priority customer given that the system is in a type i delay cycle, i = H, L. Level crossing analysis of queues (e.g., [1,12]) tells us that vHA (x|i) is the rate of downcrossings of the virtual waiting time process over the level x during a type i delay cycle. Defining E(Dx |i) (respectively E(Ux |i)) to be the conditional expected number of downcrossings (respectively upcrossings) over the level x during a type i delay cycle. Assuming an ergodic system, we have E(Dx |i) = E(Ux |i) and hence,
vHA (x|i) =
E(Dx |i) E(Ux |i) = . mi mi
(20)
140
E.M. JEWKES AND D.A. STANFORD
Figure 4. Illustration of the virtual waiting time process, H and L and LB cycles.
The expected number of upcrossings over the level x during a type i delay cycle is the probablility that the first jump in the delay cycle causes an upcrossing, plus the expected number of upcrossings due to external H arrivals during the delay cycle: x wHA (y|i) 1 − GH (x − y) dy, (21) E(Ux |i) = 1 − Gi (x) + λH mi y=0
where wHA (y|i) is the conditional HA waiting time probability density function. High priority customers arrive according to a Poisson process, so from [16], they observe time averages, and we have wHA (y|i) = vHA (y|i). Substituting (21) into (20) and taking LSTs, we find ∗ (s|i) = wHA
(1 − gi∗ (s)) λH ∗ wHA (s|i) 1 − gH∗ (s) , + smi s
i = H, L.
(22)
∗ (s|i), the final result is obtained: When this expression is rearranged to isolate wHA ∗ (s|i) = wHA
(1 − ρH )(1 − gi∗ (s)) , E(i) s − λH + λH gH∗ (s)
i = H, L.
(23)
∗ ∗ ∗ (s|LB) differs slightly from wHA (s|H ) and wHA (s|L) in that The analysis for wHA one more upcrossing may occur when the LB customer finishes its low priority service and feeds back as a high priority customer. At this time, the virtual waiting time is simply the amount of high priority work that has arrived during the L service. Let η∗ (s) be the LST of the distribution of this work. The jump in the workload at this time is equal to the high priority (HP) service time of the LB customer. Now, paralleling the derivation of (22), we obtain ∗ (s|LB) = wHA
(1 − gL∗ (s)) η∗ (s)(1 − gH∗ (s)) λH ∗ wHA (s|LB) 1 − gH∗ (s) . + + smLB smLB s
(24)
TWO PRIORITY QUEUE WITH CROSSOVER FEEDBACK
141
After substituting for η∗ (s) = gL∗ (λH − λH gH∗ (s)) and rearranging, we get ∗ (s|LB) = wHA
(1 − ρH )[(1 − gL∗ (s)) + gL∗ (λH − λH gH∗ (s))(1 − gH∗ (s))] , (E(L) + E(H ))(s − λH + λH gH∗ (s))
(25)
where we have made use of the fact that mLB = (E(L) + E(H ))/(1 − ρH ). Remark. Equations (23) and (25) can also be obtained by following the derivation of waiting time presented in [2, pp. 152–155] for waiting times instead of flow times. In an LB cycle, however, the delay cycle T1 represents the time to serve the H arrivals during the initial delay T0 plus the LB customer itself who has now fed back to the HP queue. The unconditional LST of the waiting time for an HA customer that results when (23) and (25) are substituted into (17) is ∗ (s) = wHA
(1 − ρ)s + λL (1 − gL∗ (s)) + λLB gL∗ (λH − λH gH∗ (s))(1 − gH∗ (s)) . s − λH + λH gH∗ (s)
(26)
The usual task of differentiating (26) and applying L’Hopital’s rule to obtain the mean delay wHA yields an equivalent expression to equation (5). 4.2. Derivation of the LA delay distribution In this section, we use level crossing analysis to find the LST of the distribution for the time an LA or LB customer spends in the queue prior to its low priority service. In this section, vt refers to the virtual waiting time for an LA customer – the delay prior to starting its low priority service if it were to enter the system at time t. If an arriving LA customer were to find an idle system, it would begin its low priority service immediately. The first arrival in the busy period introduces an additional delay to an arriving LA customer where the length of the delay depends on the type of customer initiating the busy period. An HA or HB arrival will cause the virtual waiting time to jump by the length of a delay cycle initiated by the high priority service, and continued by a delay busy period in which high class customers, and their successors are served. This has an LST fH∗ (s) = gH∗ (s + λH (1 − fH∗ (s))). Similarly, if an LA customer initiates the busy period, vt jumps by an amount that has an LST fL∗ (s) = gL∗ (s + λH (1 − fH∗ (s))). Finally, if an LB customer initiates the busy period, the LST of the jump in vt is fL∗ (s)fH∗ (s) as both its low and high priority services induce delay busy periods. During the busy period, HA arrivals will not cause the virtual waiting time for an LA customer to jump, as the work they add to the system has been accounted for in a previous delay busy period. HB customers do not cause an immediate jump in vt , but once their high class service has been completed, vt jumps by fL∗ (s). While the high priority service is accounted for in an earlier delay busy period, the delay busy period induced by the HB customer’s low priority service will only impact a virtual LA arrival if the latter enters the system after the high priority service of the HB customer has been completed, but not before. Similarly, LA arrivals during the busy period cause vt to jump by fL∗ (s) and LB arrivals, by fL∗ (s)fH∗ (s).
142
E.M. JEWKES AND D.A. STANFORD
Following the previous delay distribution derivations, we find that the LST of the virtual delay distribution for an LA customer, given the system is busy, is ∗ (s|b) = vLA
λH (1 − fH∗ (s)) + λLA (1 − fL∗ (s)) + λLB (1 − fL∗ (s)fH∗ (s)) sλE(BP ) ∗ ∗ (s|b)(1 − fL∗ (s)) + λLB wLA (s|b)(1 − fL∗ (s)fH∗ (s)) λLA wLA + s ∗ ∗ λHB z (s)(1 − fL (s)) . + sλE(BP )(1 − ρ)
(27)
In equation (27), z∗ (s) represents the LST of the amount of work left in the system at the completion epoch of a high priority service for an HB customer. The expected number of such service completions during a busy period is λHB E(BP ) + λHB /λ = λHB /λ(1 − ρ), the expected number of HB arrivals during the busy period plus the probability that the first arrival during the busy period is an HB customer. As before, we have that ∗ ∗ (s|b) = wLA (s|b) and hence, after some reorganisation we find vLA (1 − ρ) (λHB /(1 − ρ))z∗ (s)(1 − fL∗ (s)) + λH (1 − fH∗ (s)) ∗ (s|b) = wLA ρ s − λLA (1 − fL∗ (s)) − λLB (1 − fL∗ (s)fH∗ (s)) λLA (1 − fL∗ (s)) + λLB (1 − fL∗ (s)fH∗ (s)) . (28) + s − λLA (1 − fL∗ (s)) − λLB (1 − fL∗ (s)fH∗ (s)) Unconditioning on the system state yields the final expression ∗ (s) = wLA
(1 − ρ)(s + λH (1 − fH∗ (s))) + λHB z∗ (s)(1 − fL∗ (s)) . s − λLA (1 − fL∗ (s)) − λLB (1 − fL∗ (s)fH∗ (s))
(29)
∗ (s). The simplest verification of this is We note that z∗ (s) is not equal to wLA the fact that the mean delays qHB and wLA are different. From our numerical work, the discrepancy is typically not large, and improves in percentage terms in heavy traffic. ∗ (s) for z∗ (s) in (29) above, it would often provide a credible If one were to substitute wLA ∗ approximation for wLA (s). Exact results are available, however, when λHB = 0. In this case, there are no instants when customers feed back from the high priority to the low priority queue. The last term in the numerator of (29) then vanishes, and we obtain the exact solution ∗ ∗ (s) = wLA (s|b)ρ + (1 − ρ) wLA (1 − ρ)(s + λH (1 − fH∗ (s))) . = s − λLA (1 − fL∗ (s)) − λLB (1 − fL∗ (s)fH∗ (s))
(30)
To conclude this section, we point out a seemingly attractive, but erroneous, ap∗ (s). In many priority queues, fresh arrivals from the lowest proach to determine wLA priority class see a delay that initially consists of all of the work present in the system (namely, the server’s total unfinished workload), supplemented by a delay busy period of later-arriving customers that require high priority services. Standard delay cycle analy-
TWO PRIORITY QUEUE WITH CROSSOVER FEEDBACK
143
sis can usually solve such systems fairly readily. Unfortunately, LA and LB arrivals in our system do not initially see a delay equal to the server’s total unfinished work, as the latter includes the low priority service requirements of HB customers present in the high priority queue, so this approach cannot be used here. 4.3. Derivation of the LB delay distribution The LST of the LB delay distribution is easily obtained by recognizing its relationship to the LA delay distribution. While the LB customer is obtaining its low priority service, high priority arrivals will enter the system and they will obtain high priority service ahead of the LB customer. The time between the end of the LB customer’s low priority service and the start of its high priority service equals the amount of high priority work that enters during a low priority service, whose LST is η∗ (s) = gL∗ (λH − λH gH∗ (s)). The distribution of the LB delay consists of the LA delay, the low priority service, and the feedback delay discussed above. Note, however, that the latter two quantities are dependent. Proceeding in the standard way we obtain ∗ ∗ (s) = wLA (s)gL∗ s + λH − λH gH∗ (s) . (31) wLB 4.4. Derivation of the HB delay distribution In this section, we derive the distribution of the delay that a HB arrival encounters prior to its low priority service. The distribution will be denoted by wHB (x), and the LST of ∗ (s). As in the previous section, some preliminary remarks are in the distribution by wHB order before we present the level crossing analysis. It is useful to examine what the delay will be to an arriving HB customer who finds the system empty. It will be delayed by: 1. its own high priority service time, 2. the total (aggregate) service requirement for all LA and LB arrivals during 1, and 3. a delay busy period in which HA and HB arrivals during 1 and 2, and their successors, each receive their high priority service. The time to render 1 and 2 has the LST ∞ ∞ (λL t)n ∗ ∗ ∗ gLAGG (s)n dGH (t) = gH∗ s + λL 1 − gLAGG e−st e−λL t (s) , gHL (s) = n! 0 n=0 (32) where λLA ∗ λLB ∗ ∗ (s) = gL (s) + g (s)gH∗ (s) gLAGG λL λL L
144
E.M. JEWKES AND D.A. STANFORD
is the LST of the aggregate service requirements of an L customer. The LST of the delay cycle induced by 1 and 2 (and the LST of the waiting time for an HB customer that enters an empty system) is ∗ (33) s + λH 1 − fH∗ (s) . h∗H (s) = gHL Now, for an HB arrival that enters a busy system, the delay prior to its L service will consist of: 1. the work it finds in the system upon arrival, 2. its own high priority service time, 3. the total service requirement for all LA and LB arrivals during 1 and 2, and sojourn as a high priority customer, and 4. a delay busy period in which HA and HB arrivals during 1, 2, and 3, and their successors, receive their high priority service. The last of these terms can be handled in the usual way via delay cycle analysis. Similarly, the number of L arrivals occurring during 1 and 2 are independent, so we can effectively write ∗ (s) = +∗HB (s)h∗H (s). wHB
(34)
In other words, we can write the LST of the HB delay distribution as the product of a term for the total delay ultimately due to its own high priority service time (which has the LST h∗H (s)), and another term +∗HB (s) that represents the LST of the distribution of the following amount of work: 1. the work it finds in the system upon arrival, 2. the total service requirement for all LA and LB arrivals during the tagged customer’s waiting time as a high priority customer, and 3. a delay busy period in which HA and HB arrivals during 1 and 2, and their successors, receive their high priority service. To determine +∗HB (s), we will account for these terms in a similar fashion to what has been done earlier. We momentarily ignore the delay busy cycle represented by 3 above. Although an HB customer must wait for the total service requirements of all customers it finds in the system, there is a complication in that we must distinguish those L customers who arrive during its sojourn as a high-priority customer, as any later L arrivals will exert no influence on the tagged HB customer. Let U ∗ (s, t) = Ee−sXU −t XL represent the two-dimensional joint LST of the amount of work in the system, where XU represents the portion a high priority customer would be delayed by, and XL the remainder. In a similar fashion to the discussion above, the LST ∗ (s) , s (35) UL∗ (s) = U ∗ s + λL 1 − gLAGG
TWO PRIORITY QUEUE WITH CROSSOVER FEEDBACK
145
accounts for the LA and LB customers who arrive during the tagged HB customer’s time waiting in the high priority queue. Therefore UL∗ (s) is the LST of the total amount of time that an HB customer would be delayed if there were no later high priority arrivals. To account for these arrivals, each of which will receive their H service before the tagged HB customer starts its L service, we apply the standard delay cycle argument to obtain (36) +∗HB (s) = UL∗ s + λH − λH fH∗ (s) . We note in closing that U ∗ (s, t) can be expressed in terms of a multivariate generating function, as the corresponding embedded Markov chain may turn out to provide the last piece of the solution in the future, instead of directly finding the bivariate unfinished workload process U ∗ (s, t) itself. Consider (37) GB (w, x, y, z, v) = E w NH x NL y NB zI v J |Busy , where NH = the stationary number of HA, HB, and LB customers present in the HP queue during a busy period, NL = the stationary number of LA and LB customers present in the LP queue queue during a busy period, NB = the stationary total number of HB customers present in either queue or in A service queue during a busy period, I = an indicator random variable (R.V.) as to whether the customer in service is receiving an H or L service (I = 1 denotes an L service), J = an indicator R.V. for the event that an LB customer is receiving it’s L service. After a straightforward analysis, it can be shown that ∗ (t), gL∗ (s), gL∗ (s)/gH∗ (s), gH (t) , U ∗ (s, t) = (1 − ρ) + ρgH∗ (s)GB gH∗ (s), gLAGG
(38)
where gi∗ (s) = (1 − gi∗ (s))/(sE(i)) is the LST of the residual service time of the customer presently in service, i = H, L. 5.
Conclusions
In this paper, we studied a two-priority queue where each class has the possibility of feedinq back to the other queue. Explicit, tractable formulas for the average delay have been found for all customer types. The LST of all the delay distributions were also characterized. The close relationship between two of the average delays has been explored in detail, namely the delay seen by a low priority customer upon arrival, and that seen by a high priority customer who feeds back to the low priority queue. Numerical examples showed the sensitivity of the average delays to various factors and confirmed previous results for the optimal priority ordering of the classes to minimize the average delay. In future work, we hope to derive explicit expressions for the delay distribution in the low
146
E.M. JEWKES AND D.A. STANFORD
priority queue at HB customer feedback instants, and the two-dimensional LST U ∗ (s, t) which is needed for the HB delay distribution. Acknowledgements This research has been financially supported by the NSERC operating grants of both authors. The authors would like to thank an anonymous referee for helpful suggestions. References [1] P. Brill, An embedded level crossing technique for dams and queues, J. Appl. Probab. 16 (1979) 174–186. [2] R.M. Conway, W. Maxwell and L. Miller, Theory of Scheduling (Addison-Wesley, Reading, MA, 1967). [3] J. Daigle, Task-oriented queueing: An analysis tool for software design of communication processing systems, IEEE Trans. Commun. 34 (1986) 250–256. [4] J.N. Daigle and C. Houstis, Analysis of a task oriented multi-priority queueing system, IEEE Trans. Commun. 29 (1981) 1669–1677. [5] B. Fontana, Queue with two priorities and feedback: Joint queue-length distribution and response time distributions for specific sequences, in: ITC, Vol. 10, Montreal, 1983. [6] B. Fontana and C.D. Berzosa, Stationary queue-length distributions in an M/G/1 queue with two non-preemptive priorities and general feedback, in: IFIP, 1984, pp. 333–347. [7] E. Jewkes and J. Buzacott, Flow time distributions in a K class priority feedback queue, Queueing Systems 8 (1991) 183–202. [8] L. Kleinrock, Queueing Systems, Vol. 1 (Wiley, New York, 1975). [9] G.P. Klimov, Time-sharing service systems I, Theory Probab. Appl. 19 (1974) 532–551. [10] G.P. Klimov, Time-sharing service systems II, Theory Probab. Appl. 23 (1978) 314–321. [11] R. Serfozo, Introduction to Stochastic Networks (Springer, New York, 1999). [12] G. Shanthikumar, Some analysis on the control of queues using level crossings of regenerative processes, J. Appl. Probab. 17 (1980) 814–821. [13] B. Simon, Priority queues with feedback, J. Appl. Comput. Math. 31 (1984) 134–149. [14] D. Tcha and S.R. Pliska, Optimal control of single server queueing networks and multi-class M/G/1 queues with feedback, Oper. Res. 25 (1977) 248–258. [15] J. Walrand, An Introduction to Queueing Networks (Prentice-Hall, Englewood Cliffs, NJ, 1988). [16] R.W. Wolff, Poisson arrivals see time averages, Oper. Res. 30 (1982) 223–231.
