THE GEOMETRIC DISTRIBUTION OF QUEUE LENGTH

**UNDER A PREEMPTIVE-RESUME**

**LAST-COME-FIRST-SERVED**

**DISCIPLINE**

** **

** **

** **

** **

** **

** **

** **

** **

** **

** **

** **

** **

** **

** **

** **

**APPROVED:**

**_________________________________**

**_________________________________**

Copyright

by

Robert Graham Landrum

1993

** **

** **

** **

**DEDICATION**

** **

This report is dedicated to my parents and the memory of Robert Todd Lapsley Liston and of Charles Adair Bledsoe. These have been the architects of my education.

**THE GEOMETRIC DISTRIBUTION OF QUEUE LENGTH**

**UNDER A PREEMPTIVE-RESUME**

**LAST-COME-FIRST-SERVED**

**DISCIPLINE**

** **

**by**

** **

**ROBERT GRAHAM LANDRUM, B.S.**

** **

** **

** **

**REPORT**

**Presented to the Faculty of the Graduate
School of**

**The University of Texas at Austin**

**in Partial Fulfillment**

**of the Requirements**

**for the Degree of**

**MASTER OF ARTS**

** **

** **

**THE UNIVERSITY OF TEXAS AT AUSTIN**

** **

** **

**MAY 1993**

**ACKNOWLEDGEMENTS**

** **

** **

The author would like to acknowledge the direction of Dr. David Fonken in the preparation of this report and the generousity of Dr. Klaus Bichteler in giving his time to this project. Dr. Georgia-Ann Klutke's contribution in reading this work is also appreciated.

– April 19, 1993

__Table
of Contents__

Chapter One: Introduction and Explanation of Notation..................................... 1

Chapter Two: The Queue Length in G/M/m Systems.......................................... 5

Chapter Three: M/G/1 (LCFS/I) Systems.......................................................... 12

Chapter Four: G/G/1 (LCFS/I) Systems............................................................ 20

Chapter Five: Conclusion.................................................................................. 29

Bibliography...................................................................................................... 31

__ __

A classic example of a queue is a group of patrons lined up to purchase concert tickets. The two parts of a queueing system consist of a serving facility (e.g. the ticket booth) and a queueing facility (e.g. the line of concert goers). In general the queueing facility may consist of a number of queues as in a supermarket's checkout lines; likewise the serving facility may have a number of servers. In this report models with one queue and mostly one server will be considered.

This kind of arrangement is often encountered; however there are other schemes that approximate other situations and have the advantage of easier calculation of relevant quantities. Once these calculations have been made, they may be transferred to a "normal" queue through a mathematical transformation. The difference in the models is in the queue discipline, which will be discussed presently.

The notation set out here is based on that of Leonard Kleinrock.[1]
The nth customer, designated by *C** _{n}*
where

*q** _{n}* = the
number of customers in the system just after

*q'*_{n}_{ }= the number of customers in the system just
before *C** _{n}* arrives.[3]

For each n the random variables *t** _{n}* and

If a sequence of random variables converges (in probability)
as *n* , then the corresponding
limiting variable is denoted with a tilde: _{}. Limiting distribution functions and their pdf's are written
without a subscript e. g. *A*(*t*) and *a*(*t*).

The following variables may now be defined for the number of customers in the system:

*p** _{k}* =

*d** _{k}* = Pr(

*r** _{k}* = Pr(

For _{}and _{} set _{}. Define the utilization factor_{} where *m *is the
number of servers. Since it is the ratio of the average arrival rate to the
average service rate for the system, 0 *r * 1 in order for an equilibrium state to occur;
otherwise the servers will not be able to handle incoming customers fast
enough.

The Laplace transform of the variable's pdf will be represented as

_{} (1.1)

where *H*(*y*) = Pr(*Y ** y*) is a distribution function.[6]
Similarly the z-transform – also called the generating function – for a
discrete random variable is

_{}_{}. (1.2)

Here *h** _{n}*
= Pr(

In order to be classified succinctly, queues are designated
with the form *A*/*B*/m where *A* and *B* stand for the distributions of the
interarrival and service times respectively and m is the number of servers in
the service facility. The distributions are denoted as follows:

G: General

M: (for Markov process) Exponential

E_{r}:
*r*-stage Erlangian

H* _{R}*:

D: Deterministic

A M/H* _{R}*/2 queue, for example, has exponentially
distributed interarrival times, services with an

How a customer progresses through the system is described by the queue discipline. The most common process is the first-come-first-served (FCFS) discipline where the next customer to be served is the one that has been in the queue the longest. This is like the concert goers buying tickets. An alternate scheme is called the last-come-first-served (LCFS) discipline. Here the next customer for service is the latest. (This is really a stack but will be called a queue.)

In this report the last-come-first-served queue discipline
with preemptive resume will be explored usually for queues with one server. Its
designation will be LCFS/I where the "I" stands for
"interrupt." Upon the arrival of a customer into such a system, the
customer in service leaves the server *immediately*
and enters the queue; the new customer takes up the position with the server.
If the customer with the server completes his service, he leaves the system,
and the last customer to have entered the queue returns to the server. This
will be the customer who was in service when the now departing one arrived.[9]

This report proceeds with a discussion of the intrinsic geometric nature of G/M/m queues. M/G/1 (LCFS/I) models are then explored through an intuitive interpretation of Beneš's inversion of the Polleczek-Khinchin Transform Equation. The last topic is G/G/1 (LCFS/I) systems with an expansion of the techniques used for the M/G/1 arrangement.

In this chapter we will discuss the geometric distribution of queue length under an arbitrary queueing discipline, but the service time will be assumed to be exponentially distributed.

The mathematical basis for this analysis is the semi-Markov
chain. Let *X** _{n}* be a random
variable that is paired with a time

_{} (2.1)

Setting * t *to leaves

_{} (2.2)

To be as general as possible, it will be assumed that there
are *m* servers. The development follows that of Kleinrock.[11]

The random variables of the sequence *q'** _{n}*}
form a semi-Markov chain, and the relationship between successive pairs is
easily established:

* q'*_{n}_{+1} = *q'** _{n}*
+ 1 -

Here *v'*_{n}_{+1}
is the number of customers who finish being served and leave between the
arrivals of *C** _{n}* and

* p** _{ij}*
= Pr(

or equivalently

*p** _{ij}* = Pr(

With the *v'** _{n}*'s
being nonnegative, it follows immediately that

* p** _{ij}*
= 0 for

We will concentrate on the situation where *i* *m*. Since the service time is exponentially distributed,

_{}. (2.7)

Now *p** _{ij}*
may be calculated for

_{} (2.8)

In this last equation the dependence on *i *and *j* is in the form *i *+ 1 -
*j*. Define *n* = *i* + 1 - *j*,
and set

_{}. (2.9)

*b** _{n}* is the probability that n customers
finish service in an interarrival time given that all

*c** _{i}*(

*s** _{k}* = E(

*g* = Pr( *c*_{k}_{+ 1} (*j*)
= 0, *j* *k*) (*k * *m* – 1)

= Pr( *c*_{k}_{+ 1 }(*k*)
= 0)

*N** _{k}*(

Note that *g* is the same regardless of the value of *k*. In order to see this, suppose that a
sequence of transitions between states results in *c*_{k}_{ + 1}(*k*) = 0 where *k ** m* – 1. Every such sequence can be matched one-to-one with a
parallel sequence having the same relative transitions but starting with *k* + 2 customers in the initial
system; furthermore this parallel sequence satisfies *c*_{k}_{ + 2}(*k + *1) = 0 and has the same
probability as the first. It is apparent that

Pr(
*c*_{k}_{+
1 }(*k*) = 0) = Pr( *c*_{k}_{+
2}(*k* + 1) = 0) *k
** m* – 1. (2.10)

The variable *s** _{k}* may be thought of as the ratio of
the times that the system is in state

_{}. (2.11)

If a(*t*) is the number of customers that have entered
the system in (0, *t*), then

_{}; (2.12)

consequently

_{}. (2.13)

From Equation 2.1 it is apparent that if a system goes from
a state *E** _{k}* to

Pr(*c** _{k}*(

We may now calculate

Pr(*c** _{k}*(

= *b*_{0}g^{n}^{ –
1}(1 – *g*), (2.15)

and

_{}_{} (2.16)

which reduces to

_{}. (2.17)

Since the right side of this equation does not depend on k, we
may drop the subscript: _{} for *k ** m – *1. (2.18)

From Equation 2.10

*r*_{k}_{+
1} = *sr*_{k}*k ** m* – 1 (2.19)

or

*r*_{k}_{ +
1} = *K**s*^{k}*k ** m* – 1. (2.20)

Here is the geometric relation, but now we need to find *K *and *s*. With *r** _{k}* being an equilibrium probability,
the vector

_{} (2.21)

Solving for *s*, we get

_{}, (2.22)

which is equivalent to

_{} (2.23)

By solving the last equation for a value in (0, 1), *s*
may be determined. *K * then follows from the fact that _{}.

**Theorem: ***The length of the queue proper given that an
arriving customer* *finds all servers
busy is geometrically distributed.*

*Proof*. Let *Q* be the event that an incoming customer
must enter the queue; then

_{} (2.24)

and

_{} (2.25)

This is the desired result.

**Theorem: ***The number of customers in a G/M/1 system is
geometrically distributed.*

*Proof*:

_{}_{} (2.26)

which may be solved to yield

*K * = 1 – *s*. (2.27)

The intended result *r** _{k}* = (1 –

The geometric nature of these systems comes from the
circumstance of *b*_{0} , *g*, and thus *s** _{k}* being independent
of

Although the material in this chapter is less general than that in the next chapter, it provides an insight into what is actually occurring with the LCFS/I discipline.

The value of the exponential distribution is that it is
memoryless – that is Pr(*t *> *s*+*t |**t *> *s*) = Pr(*t *> t).[12]
In the G/M/m case this meant that only the time between arrivals was needed to
calculate the number of departures for that period: the time between the last
departure and first arrival could be "forgotten." For M/G/1 systems
the situation is reversed: since the arrivals are exponentially distributed,
the semi-Markov chain is established on the sequence {*q** _{n}*} of departure times.

** **

For this section we need three distribution functions:

* Q*(*t*) = Pr(_{})

*S*(*t*)
= Pr(_{})

*W*(*t*)
= Pr(_{})

*Q*^{#}(*z*) can be obtained from the
Pollaczek-Khinchin Transform Equation:

_{}.[13] (3.1)

Another form of this generating function may be calculated
using the FCFS discipline. In this case all the *q** _{n}* customers in the system when

_{}. (3.2)

Integrating with respect to *s* and taking the limit as _{}, we get

_{}. (3.3)

Now we calculate[14]

_{} (3.4)

Setting *s* = l - l*z*
and combining Equations 3.1 and 3.4, we get

_{}. (3.5)

The equation _{} leads to

*S**(*s*)
= *W**(*s*)*B**(*s*), (3.6)

which may be used to get

_{} (3.7)

The residual life distribution for the service time is

_{}, (3.8)

and

_{} ;[15] (3.9)

thus

_{} (3.10)

If _{} is the *k*-fold convolution of _{}, set

_{}_{}; (3.11)

then

_{}.[16] (3.12)

From the results in Chapter Two one may calculate that *r** _{k}* = (1 –

_{}. (3.13)

Now consider a M/D/1
(FCFS) setup where _{}_{}, a constant. In this case

_{}. (3.14)

From the Pollaczek-Khinchin Transform Equation,

_{}. (3.15)

Expanding this in a Taylor series, one obtains the *d** _{k}*'s as the respective coefficients of
the

_{} (3.16)

Clearly this is not the geometric distribution intimated in
Equation 3.12; furthermore _{} and *B*(*t*)
do not generally coincide. Equation 3.12 was useful for calculating purposes
but did not seem to have an intuitive explanation.

** **

Equation 3.13, with a new interpretation for _{}, was shown to be the correct explanation by Robert Cooper
and Shun-Chen Niu in their 1986 article.[18]
The core of their calculations is in the following theorem.

**Theorem: ***The number of customers in a M/G/1 (LCFS/I)
queue is geometrically distributed with r** _{k}* = (1 –

*Proof*. Define

_{} = the residual time for the service after
being interrupted. It has distribution function _{}.

A queueing system can only reach a state *E** _{k}* directly either by beginning in

_{} (3.17)

Note that *d** _{k}*
is used as opposed to

_{} (3.18)

It now follows that

_{} (3.19)

Since a departing customer leaves the system in the same exact
condition as when he arrived, *d** _{k}*
=

_{} (3.20)

Knowing that *r*_{0} = 1 –*r* and using the normalization condition,
we find that

_{}_{} (3.21)

and

*r** _{k}* = (1 –

Equation 3.21 may be rewritten as

_{}, (3.23)

which being essentially Equation 3.9 –*l* is after all an arbitrary positive number – gives that _{}.[19]

In order to understand _{}, one needs to define the function *U*(*t*) which gives the work
time that remains to be done by the server at time *t*. If

_{} (3.24)

where

_{} (3.25)

is the heavy side step function, then

_{}. (3.26)

*U*(*t*) is a nonnegative function that jumps
up *x** _{n}* in height at each

*U*(*t*)

*t*

Figure 3.1

The form of *U*(*t*) does not depend on how the customers
are served; however in the FCFS case the remaining work time just before a
customer arrives is that customer's waiting time: _{}. One may interpret _{} as the equilibrium
remnant work time just before a customer arrives. It is now straightforward to
show that _{} in a LCFS/I system,
and Equation 3.13 then follows. Beneš's inversion of the Pollaczek-Khinchin
Transform Equation, which was developed from a FCFS discipline, is more
closely related to a LCFS/I discipline.

Without the exponential distribution analysis of queues becomes more difficult. Semi-Markov processes can not be used in the same way as they were used for the G/M/m model: besides the interarrival times the times between a preceding departure and an arrival become important. The study of G/G/1 queues centers on ascending ladder points.

Set

_{}_{}, (4.1)

where q(*t*) is again the step function.

*R*(*t*) is a function with a –1 slope that jumps up *x** _{n}* at each

Define a new sequence *n** _{k}*
starting with

In a stable queue *r* <
1 or 1/*m* - 1/*l*
< 0. This equation implies that E[*u** _{n}*]
< 0, and consequently

Suppose that *R*(*t*) reaches _{}. Since the *u** _{n}*'s
are independent identically distributed random variables, the probability that
there is a point of

Pr(*K* *k* + 1) = Pr(*K * 1 ) Pr(*K * *k*) = *s*Pr(*K * *k*). (4.2)

This leads to

Pr(*K = k*)
= (1 – *s*)*s** ^{k}*. (4.3)

For *K = k*, set

_{}, (4.4)

and

_{}. (4.5)

The _{}'s are also independent identically distributed random
variables. They represent the idle times in the dual queue[23]
where the service and interarrival distributions are swapped. Let *F*(*x*)
= Pr(_{} *x*) and designate its *n*th
convolution with itself with

_{} (4.6) _{}

For the *u** _{n}*'s
the common distribution function will be

_{}. (4.7)

It will be important to specify notation for the customers
currently in the queue. If _{} 0, then set _{} equal to the
remaining service time of the *i*th
customer still in the queue. The index *i*
ranges from *i* = 1 for the customer
that has been there longest to *i* = *k* for the most recent one.[24]

**Theorem:** *In a G/G/1 (LCFS/I) system,*

_{} (4.8)

*where **s* and *F*(*t*) *are defined in the previous section.*[25]

*Proof*. Consider what
is necessary for a stationary distribution:

_{}_{} (4.9)

For *k* = 0 and *n *> 0,

_{}. (4.10)

In the limit as *n* this leads to

_{} (4.11)

For *k* > 0 and *n* > 0,

_{} (4.12)

which, in the limit, becomes

_{}_{} (4.13)

From the preliminary material it may be deduced that

_{} (4.14)

which transforms into

_{} (4.15)

The event _{}_{} is really the event
that for *K* = *k*, _{} and _{} given that *U*_{0}
= 0. This may be restated as

_{} (4.16)

_{}This leads to

_{}_{} (4.17)

If the theorem is correct, Equation 4.8 must satisfy Equations 4.11 and 4.13. In this light Equation 4.13 becomes

_{} (4.18)

or

_{} (4.19)

which agrees with Equation 4.17. Equation 4.11 agrees with Equation 4.15 in the same way. It follows that Equation 4.8 is a stationary distribution for the system and holds true in the limit.

To show that this solution is unique, note that since *r *< 1, the state for *q' *= 0 is non-null persistent. The probability *r*_{0} = 1 - *s *is
independent of the initial state; and when the queue reaches that state the
succeeding condition of the system is independent of preceding conditions. The
queue is ergodic and can only assume the character of the given solution.

Usually the semi-Markov process is established solely on the set of arrival instances or solely on the set of departure instances. Since arrivals and departures affect the server for a LCFS/I queue, a semi-Markov process can be set up incorporating both types of events. In this light let

_{} (4.20)

In this type of system a customer need only "see" the customers who enter the queue after him. In fact he need only be concerned with the customers who immediately interrupt his service and consequently "block" his "view" until they have finished all their service time. This suggests that changes in state do not depend on the actual queue length but may be described by the following probabilities:

a_{a} = Pr(arrival | the last event was an arrival)

a_{d} = Pr(arrival | the last event was a departure)

d_{a} = Pr(departure | the last event was an arrival) (4.21)

d_{d} = Pr(departure | the last event was a departure)

These are further described by

_{}

Table 4.1

Here _{} is the residual time
of an interrupted interarrival period:

_{}[26] (4.22)

Consider the value of _{} at an arrival:

_{}. (4.23)

Using the same methods of Section 3.3, one gets

_{} (4.24)

and

_{} (4.25)

likewise

_{} (4.26)

With this,

_{} (4.27)

or

_{} (4.28)

Comparing this with Equation 4.8, one sees that

_{} (4.29)

This produces a method for calculating a constant that was previously defined abstractly.

For M/G/1 (LCFS/I) _{}, and Equation 4.29 becomes

_{}, (5.1)

which agrees with Equation 3.21. This is only natural since
the calculation of *s* is a generalization of the calculation
of *r*.

Again *s* can be calculated using Equation 4.29:

_{} (5.2)

Looking at this more closely, we see that a_{a},* *being
the probability that the last change in the system was an arrival, is
equivalently the probability that no departures have occurred in the preceding
interarrival time. a_{d} is then the event
that the system, currently in state *E** _{k}*,
was last in state

_{}. (5.3)

The material in the preceding chapter can also be used to generalize the formula for the waiting time as was developed in Chapter Three:

_{}_{} (5.4)

In form Equation 4.29 parallels the successive-state
probability ratio of other queues with geometrically distributed length. In
calculability it becomes useful in determining quantities like the waiting
time distribution. Understanding the *s* of LCFS/I queues is being used to give
information about G/G/1 FCFS systems.

.

**Bhat, U. Narayan. ***Elements of Applied
Stochastic Processes*, 2nd ed. New York: John Wiley & Sons, 1984.

**Cooper, Robert B.**, and **Niu, Shun-Chen. ** "Beneš's Formula for M/G/1-FIFO
'Explained' by Preemptive-Resume LIFO." *Journal of Applied Probability*, 23 (1986) 550-554.

**Fakinos, D. **"The G/G/1 Queueing System with a Particular Queue
Discipline." *Journal of the Royal
Statistical Society*, B 43 (1981)
190-196.

**Kleinrock, Leonard**. *Queueing Systems*, Vol. 1 New York:
Wiley-Interscience, 1975.

**VITA**

Robert Graham Landrum was born in Bristol, Tennessee, on August 9, 1966, the son of Mary Fisher Landrum, M.A. and Graham Gordon Landrum, Ph.D. After attending Tennessee High School, Bristol, Tennessee, he entered King College, also of the same town, in 1983. He attended Purdue University for the summer of 1985, and during the summer of 1986, he pursued research at Lowell Observatory. In May of 1987 he graduated from King College with the degree of Bachelor of Science. In September, 1987, he entered The Graduate School of The University of Texas at Austin.

Permanent Address: 2115 Edgemont Avenue

Bristol, Tennessee

37620-4745

This report was typed by the author.

[9]D. Fakinos, "The G/G/1 Queuing System with a
Particular Queue Discipline," *Journal
of the Royal Statistical Society B*, 43 (1981) 190.

[10]U. Narayan Bhat, *Elements
of Applied Stochastic Processes*, 2nd ed.
(New York: John Wiley & Sons, 1984), p. 290.

[18]Robert B. Cooper and Shun-Chen Niu, "Beneš's
Formula for M/G/1-FIFO 'Explained' by Preemptive-Resume LIFO," *Journal of Applied Probability*, 23
(1986) 550-554.

[25]D. Fakinos, "The G/G/1 Queueing System with a
Particular Queue Discipline," *Journal
of the Royal Statistical Society *B, 43 (1981), pp. 190-196.

[26]Kleinrock p. 172.