The M/M/1 Queuing System

The M/M/1 system is made of a Poisson arrival, one exponential (Poisson) server, FIFO (or not specified) queue of unlimited capacity and unlimited customer population. Note that these assumptions are very strong, not satisfied for practical systems (the worst assumption is the exponential distribution of service duration - hardly satisfied by real servers). Nevertheless the M/M/1 model shows clearly the basic ideas and methods of Queuing Theory. Next two chapters summarize the basic properties of the Poisson process and give derivation of the M/M/1 theoretical model.

Poisson Process

The Poisson process satisfies the following assumptions, where1) **P**[one arrival in the time interval (*t, t+h*), for *h* ® 0] = l*h*, where l is a constant.

2) **P**[more than one arrivals in the interval (*t, t+h*), for *h* ® 0] ® 0.

3) The above probabilities do not depend on* t* ("no memory" property = time independence = stationarity).

Let *p _{n}*(

*p _{n}*(

(

*p*_{0}(*t+h*)* = p*_{0}(*t*)[1* - lh*]

( no arrival by *t,* no more arrival) (1)

The equations (1) may be written in this way:

, (2)

Because of small *h* the terms at the left sides of (2) may be considered as derivatives:

, (3)

Equations (3) represent a set of differential equations. To solve them let’s start by *p*_{0}(*t*):

(to prove it, compute the derivative of *p*_{0}(*t*) and compare with (3) )

Using *p _{0}*(

(prove by computing the derivative and inserting to (3) with *p*_{0}(*t*) )

Or generally (can be proved by mathematical induction):

(4)

Because of the assumption 3) the formula (4) holds for any interval (*s*, *s+t*), in other words the probability of *n* arrivals during some time interval depends only on the length of this time interval (not on the starting time of the interval).

**Number of arrivals N_{t} during some time interval t **is a discrete random variable associated with the Poisson process. Having the probabilities of the random values - (4), it is possible to find the usual parameters of the random variable

(5)

(5) gives the interpretation of the constant l , that is the __average number of arrivals per time unit__. That’s why the l is called **Arrival rate**.

(6)

(7)

Another random variable associated with the Poisson process is the **random interval between two adjacent arrivals**. Let *x* be the random interval. To find its distribution, let’s express the __Distribution function__ F(*x*):

F(*x*) = **P**[interval < *x*] = **P**[at least one arrival during the interval *x*] = 1 - p_{0}(*x*) = 1 - e^{-l x
}

Because the interval is a continuous random variable, it is possible to compute the __Probability density__ as a derivative of the Distribution function:

f(*x*) = dF(*x*)/dx = l e^{-l x
}

These two functions define the probability distribution:

F(*x*) = 1 - e^{-l x} , f(*x*) = l e^{-l x} (8)

The distribution (8) is called __Exponential__ or __Negative Exponential Distribution__. Its parameters are:

(9)

(9) gives another interpretation of the constant l .
Its inverted value is the __average interval between arrivals__. Like the number of
arrivals, the distribution of intervals between arrivals does not depend on time.
Note the big value of the standard deviation (equal to the average value). It means,
that the exponential distribution is "very random". In fact all intervals from 0 to
¥ are theoretically possible. So it may happen, that there will
be clusters of very close arrivals separated by very long intervals. Of course not all
practical distributions can be treated as exponential ones.
There is this general rule:

If a large number of independent event streams are merged together, and if events in each stream occur at a very low rate, then the resulting stream is approximately a Poisson process with exponential intervals.

This rule is more or less satisfied for arrivals in systems with large populations (each potential customer represents one low rate stream).

When applied to a service, the rate is called **Service rate **(m ). The parameter m is the average number of completed services per time unit (provided there are always customers waiting in the queue), its inverted value 1/m is the average duration of the exponential service. The variance and the standard deviation can be computed by replacing l by m in the formulae (9). Unlike arrival, exponential service is an abstraction that is hardly satisfied by real systems, because mostly it is very unlikely to have very short and/or very long services. Real service duration will be typically "less random" than the theoretical exponential distribution.

Another very important parameter of queuing systems is the ratio r of the arrival and the service rates called **Traffic rate **(sometimes called Traffic intensity or Utilisation factor):

(10)

The value of r shows how "busy" is the server. It is obvious, that for r > 1 the queue will grow permanently. Later we shall see that in fact r must not be even equal to one.

The system M/M/1

The M/M/1 system is made of a Poisson arrival (Arrival rate
*l* ), one exponential server (Service rate
m ), unlimited FIFO (or not specified queue), and unlimited customer
population. Because both arrival and service are Poisson processes, it is possible to find probabilities of various
states of the system, that are necessary to compute the required quantitative parameters. __System state__
is the number of customers in the system. It may be any nonnegative integer number. Let *p _{n}*(

*p _{n}*(

*p _{n}*(

*p*_{n-1}*(t*)[*lh*][1 - m*h*] + (*n*-1 customers at *t*, one came, no left)

*p*_{n+1}(*t*)[1* - lh*][m*h*] (*n*+1 customers at *t*, no came, one left )

*p*_{0}(*t+h*)* = p*_{0}(*t*)[1* - lh*] + (no customer at *t,* no came)

*p*_{1}(*t*)[1 - *lh*][m*h*] (one customer at *t*, no came, one left) (11)

The above equations may be written in the following way, where the terms with *h*^{2} are omitted because they are relatively very small (* h *® 0):

(12)

Because of small *h* the terms at the left sides of (12) may be considered as derivatives:

(13)

Equations (13) represent a set of differential equations called *Kolmogorov Differential Equations*. Their solution is a set of equations showing how each probability changes with time. Fortunately we actually do not need these functions. Because of the third assumption (stationarity) after some transition period the system will become stable. Of course the state will permanently change, but the probabilities of various numbers of customers in the system will be constant. So the functions *p _{n}*(

(14)

By dividing the equations (14) by m we get this set of equations that contain the only parameter r - the *traffic rate*:

(15)

In the set (15) *p*_{1} is expressed by *p*_{0}. By inserting *p*_{1} and *p*_{0} to the equation for *p*_{2}, we get:

*p*_{2} = (1+r )*p*_{1} - r *p*_{0} = (1+r )r *p*_{0} - r *p*_{0} = r ^{2}*p*_{0}

Similarly *p*_{2} and *p*_{1} may by used to express *p*_{3}, etc. which gives the general formula for *p _{n}*:

*p _{n}* = r

The value *p*_{0} can be computed by using the obvious requirement, that the sum of all probabilities must be equal to 1:

giving: (17)

In (17) the sum of geometric progression has been used. From (17) it is also obvious that __the traffic rate r must be less than 1__, otherwise the sum of probabilities would not be 1 (not even limited). Inserting (17) to (16) gives the general formula for *p _{n}*:

(18)

The equations (18) represent a very important result used later to obtain all the characteristics of the M/M/1 system. The relatively simple derivation of (18) was enabled by the Poisson process assumptions used when expressing the probabilities in (11). The equations (18) may be used directly to express these probabilities:

**P**[service idle] = **P**[not queuing on arrival] = *p*_{0} = 1 - r = 1 - l /m

**P**[service busy] = **P**[queuing on arrival] = 1 - *p*_{0} = r = l /m

**P**[*n* customers in the system] = *p _{n}* = r

**P**[*n* or more customers in the system] = r ^{n}

**P**[less than *n* customers in the system] = 1 - r ^{n}

The derivation of **P**[*n* or more customers in the system]:

Now the formula (18) will be used to derive quantitative characteristics of the M/M/1 system. (18) actually represents a distribution of a discrete random variable ** Number of customers in the system** (probabilities of all possible random values). So it is possible to compute the mean value, that is the average number of customers in the system:

(19)

In (19) the formula for geometric progression has been used. Note again, that r must be less than 1, otherwise the number of customers in the system will grow permanently. In a similar way it is possible to find the average number of customers in the queue. We assume, that the *customer being served is not a part of the queue*. So *n* customers in the system means the queue length is *n*-1.

(20)

In (20) we have used the fact, that the second sum is a complement to *p*_{0} and (17). Note, that (20) may be also used to compute *L _{Q}* provided

that looks in our case like that (for *n* ³ 2):

Using the above formula for *p _{n}/q* , we may find

(21)

The average queue length is a parameter that represents the quality of service especially from user’s point of view. Another parameters we need is the average time *W _{S}* spent in the system and the average time

*L _{S}* = l

This is the justification (not the exact proof) of the formula (22): let’s assume the average time spent in the system is *W _{S}*. During this time the average number of newcomers is

(24,25)

There is another obvious relationship between the average time spent in the system and the average time spent in the queue, because the total time spent is made of the time in the queue (that may be zero) and the time of the service:

(26)

(26) can also be obtained from (24). Using the Little’s formula, it is possible to express a similar relation between *L _{S}* and

(27)

*L*_{SERV} = r is the average number of customers being served (that of course must be less than one). For a customer it is also important to know the probability, that the time spent in the system (or in the queue) will be greater than a certain value. Together with the queue length this probability represents a quality of service from user’s point of view. Without proof (that is less trivial) these formulae may be used:

(28)

Of course the probabilities of spending less than *t* in the system (or in the queue) are complements of the above values to 1. Because the time spent is a continuous random variable, the probability of spending exactly the time *t* in system (queue) is zero, but using the formulae (28), we can compute the probability, that the time spent will be in certain range (*t*_{1}, *t*_{2}):

**P**[*spending more than t*_{1}* and less than t*_{2}] = **P**[*more than t*_{1}] - **P**[*more than t*_{2}]

And finally the variances (squares of standard deviations) of the four characteristics:

(29)