An queueing system is the simplest non-trivial queue where the requests arrive according to a Poisson process with rate , that is the interarrival times are independent, exponentially distributed random variables with parameter . The service times are also assumed to be independent and exponentially distributed with parameter . Furthermore, all the involved random variables are supposed to be independent of each other. Let denote the number of customers in the system at time and we shall say that the system is at state if . Since all the involved random variables are exponentially distributed, consequently they have the memoryless property, is a continuous-time Markov chain with state space 0, 1, ... .

In the next step let us investigate the transition probabilities during time . It is easy to see that

By using the independence assumption the first term is the probability that during one customer has arrived and no service has been finished. The summation term is the probability that during at least customers has arrived and at the same time at least has been serviced. It is not difficult to verify the second term is due to the property of the Poisson process. Thus

Similarly, the transition probability from state into state during can be written as

Furthermore, for non-neighboring states we have

In summary, the introduced random process is a birth-death process with rates

That is all the birth rates are , and all the death rates are . As we notated the system capacity is infinite and the service discipline is FIFO.

To get the steady-state distribution let us substitute these rates into formula 10.1 obtained for general birth-death processes. Thus we obtain

By using the normalization condition we can see that this geometric sum is convergent iff

and

where . Thus

which is a modified geometric distribution with success parameter .

In the following we calculate the main performance measures of the system

1. Mean number of customers in the system

Variance

2. Mean number of waiting customers, mean queue length

Variance

3. Server utilization

By using Theorem 10.1 it is easy to see that

where a is the mean busy period length of the server, is the mean idle time of the server. Since the server is idle until a new request arrives which is exponentially distributed with parameter . Hence

and thus

In the next few lines we show how this performance measure can be obtained in a different way.

To do so we need the following notations.

Let , denote the mean number of customers that have arrived, departed during the mean busy period of the server, respectively. Furthermore, let enote the mean number of customers that have arrived during a mean service time. Clearly

and thus after substitution we get

Consequently

4. Distribution of the response time of a customer

Before investigating the response we show that in any queueing system where the arrivals are Poisson distributed

where denotes the probability that at time the system is in state , and denotes the probability that an arriving customers find the system in state at time . Let

denote the event that an arrival occurs in the interval . Then

Applying the definition of the conditional probability we have

However, in the case of a Poisson process event does not depends on the number of customers in the system at time and even the time is irrespective thus we obtain

hence for birth-death processes we have

That is the probability that an arriving customer find tha system in state is equal to the probability that the system is in state .

In stationary case applying formula (10.2) with substitutions we have the same result.

If a customer arrives it finds the server idle with probability hence the waiting time is . Assume, upon arrival a tagged customer, the system is in state This means that the request has to wait until the residual service time of the customer being serviced plus the service times of the customers in the queue. As we assumed the service is carried out according to the arrivals of the requests. Since the service times are exponentially distributed the remaining service time has the same distribution as the original service time. Hence the waiting time of the tagged customer is Erlang distributed with parameters , and the response time is Erlang distributed with , . Just to remind you the density function of an Erlang distribution with parameters , is

Hence applying the theorem of total probability for the density function of the response time we have

Its distribution function is

That is the response time is exponentially distributed with parameter .

Hence the expectation and variance of the response time are

Furthermore

5. Distribution of the waiting time

Let denote the density function of the waiting time. Similarly to the above considerations for we have

Thus

Hence

The mean waiting time is

Since , in addition and are independent we get

thus

that is exactly .

Notice that

Furthermore

Relations (11.1), (11.2) are called Little formulas or Little theorem, or Little law which remain valid under more general conditions.

Let us examine the states of an system at the departure instants of the customers. Our aim is to calculate the distribution of the departure times of the customers. As it was proved in (10.3) at departures the distribution is

In the case of Poisson arrivals , hence .

Now we are able to calculate the Laplace-transform of the interdeparture time . Conditioning on the state of the server at the departure instants, by using the theorem of total Laplace-transform we have

since if the server is idle for the next departure a request should arrive first. Hence

which shows that the distribution is exponential with parameter and not with as one might expect. The independence follows from the memoryless property of the exponential distributions and from their independence. This means that the departure process is a Poisson process with rate .

This observation is very important to investigate tandem queues, that is when several simple queueing systems as nodes are connected in serial to each other. Thus at each node the arrival process is a Poisson process with parameter and the nodes operate independently of each other. Hence if the service times have parameter at the th node then introducing traffic intensity all the performance measures for a given node could be calculated. Consequently, the mean number of customers in tha network is the sum of the mean number of customers in the nodes. Similarly, the mean waiting and response times for the network can be calculated as the sum of the related measures in the nodes. Similarly, the mean waiting and response times for the network can be calculated as the sum of the related measures in the nodes.

Now, let us show how the density function can be obtained directly without using tha Laplace-transforms. By applying the theorem of total probability we have

Now let us consider an system and we are interested in under which service time distribution the interdeparture time is exponentially distributed with parameter . First prove that the utilization of the system is . As it is understandable for any stationary stable queueing system the mean number of departures during the mean busy period length of the server is one more than the mean number of arrivals during the mean busy period length of the server. That is

where denotes the mean interarrival times. Hence

where . Clearly

Thus the utilization for an system is . It should be noted that an system , that is why our question can be formulated as

thus

which is the Laplace-transform of an exponential distribution with mean . In summary, only exponentially distributed service times assures that Poisson arrivals involves Poisson departures with the same parameters.

Example 11.1. Let us consider a small post office in a village where on the average 70 customers arrive according to a Poisson process during a day. Let us assume that the service times are exponentially distributed with rate 10 clients per hour and the office operates 10 hours daily. Find the mean queue length, and the probability that the number of waiting customer is greater than 2. What is the mean waiting time and the probability that the waiting time is greater than 20 minutes?

Solution:

Let the time unit be an hour. Then , ,