With the advent of the World Wide Web, everybody is thinking of their computers as servers. IBM recently re-branded their entire line to eServer (actually, the e- is supposed to be their e-business logo, but nobody seems to care about that little detail, except IBM’s legal department). So we are all supposed to write service programs that feed the net. The classical problems of response time versus system capacity and utilization are as important as ever, if not more so.

Let me start with a true war-story. About twenty years ago I worked as a consultant to Lockheed who was bidding for producing a computerized Directory Assistance System for (what was then) New York Telephone. Lockheed won the bid because the hardware was the cheapest of the competing bids. The system was configured as a distributed system with many machines serving requests (about 2 million a day). Each request took on average one-third of a second to process on a given CPU, so Lockheed figured that a CPU could serve 3 requests per second and could then calculate the number of CPUs to install by dividing the peak number of requests per second by 3. They did that and won the bid. Only later did they realize that they actually needed almost twice that amount because of the fact that if you have a load of 3 transactions per second, you need a capacity of 5.8 transactions per second to handle that load without excessive queues building up. Some simple queuing theory could have told them that. This is where I came in: my job was to speed up the processing by a factor of two, so they didn’t have to install twice as many CPUs. One way of dealing with a massive screw-up!

This counterintuitive result still hits people today. So it pays to examine why a simple-minded approach to queuing just doesn’t work. That is the purpose of this article

We consider a system receiving requests, servicing them, and consequently producing responses. The treatment is based on the assumption that the events causing requests to the system occur at random. The probability of any particular event happening is generally low and uniform, i.e. the probability of it happening in a given unit of time is the same as the probability of it happening in any other unit of time. This situation is typical of most (but not all) real-time systems. The number of arrivals of events during a given time interval can then be described by the Poisson distribution:

Where P(n) denotes the probability of having n events per unit time if the average number of events per unit time is <n>. [n!=n(n-1)(n-2)…1] In the following we shall use angle brackets <x> to denote the average of a variable x. If we have N single values x₁, x₂, ., x_N, the average value is defined as

<x> = (x₁ + x₂ + ... + x_N) / N

Probability theory shows that if the probability of one particular event occurring in a given time interval is constant (uniform distribution), then the probability of having n such events occur in a given time interval follows the Poisson distribution. The probability that times between events are less than a certain value then follows an exponential distribution:

where <t> is the mean interarrival time.

For illustration, consider a system where transactions occur at the average rate of 2 per second. The probability of having n arrivals per second is thus P(n) = (exp(-2) * 2ⁿ) / n!, since <n> = 2 per second. Using this formula for n from 0 through 9 yields:

It is possible, but very unlikely, to get more than 9 arrivals per second. On the other hand, there is a 14.3% chance that the rate will reach or exceed twice the average range. That is, rather large fluctuations can occur. The degree of these fluctuations decreases with increasing <n> as shown in the following table which shows the probability that the number of arrivals exceeds more than twice its average value for several different mean values <n>

Most systems of the type we are considering can be regarded as a facility with a certain utilization factor that we shall generally denote by u. If the system can handle five transactions per unit time and it during a certain interval handled only three transactions per unit time, it was only 3/5 = 0.6 or 60% utilized. If the facility utilization is low, system response is swift and there will be little or no queuing. The greater the utilization is, the greater the delays eventually become and the longer the queues that will build up.

As we have just seen, the utilization factor can fluctuate markedly simply because the number of events per unit time (e.g. per second) fluctuates. If a system can handle four events per second and the transaction intensity is two events per second, the system will be overloaded 14.3% of the time. The overload situation will relax shortly though because of the inherent system capacity. Experience has shown (becoming a good engineering rule of thumb) that an overloading of less than 10% is generally safe and can be absorbed by the system without noticeable penalties. In other words:

The quantity of interest here is the probability of having X or more arrivals in a time interval for which the mean arrival rate is <n>:

A sound design goal is then to ensure that

i.e. to configure the system to handle a number X of arrivals per second given the average arrival rate of <n> so that the above inequality holds. The following table gives X and the utilization u as functions of <n>:

For large <n>, X approaches the value

Also: u à 1 as <n> à infinity. But for most values found in practice, X > <n> by a significant amount. This simple fact is often difficult to accept. As an example, if <n> = 10 transactions per second, we need a capacity of X=14.7 or 47% larger in order to cope smoothly with the load. In Lockheed’s case the numbers were <n> = 3, and thus X = 5.8, almost twice as high.

At first sight there seems to be a paradox in the above considerations. If <n> = 10 per second, we need to have a capacity of X=14.7 (47% more), but if my unit of time is changed to be a "dec", which is 10 seconds (just chosen arbitrarily), then the very same real traffic volume would be <n> = 100 (namely 10*10) and according to the table we need now X=113 or only 13% overcapacity rather than 47%.

It seems that simply by arbitrarily varying my unit of time over which I measure the traffic intensity, I require different amount of capacity to handle what is really the same number of events. How can that be? The solution lies in the realization that the design criterion we used was to configure the system so that delays would not become excessive. Now, delays are measured in the same units of time as <n> is calculated over, and increasing the length of the time interval over which we measure <n> amounts to increasing the delay we will tolerate as well. The implicit assumption behind the considerations about facility overloading is in fact that we do not tolerate delays that are much longer than the servicing time (which is 1/X). You do not want to wait in line for an hour for a transaction that only takes a minute; however, waiting a few minutes would be quite acceptable.

Let us now consider a system having a single server with a queue of items awaiting service. Let t_s be the service time for one item and Sd be the standard deviation ("spread") of all the service times. Further, let w be the number of items waiting in the queue at a given time and let q be the total number of items in the system (either waiting or being served). Let t_w be the time an item waits before being served and let t_q be the total time the items spends in the system, then for each individual event we have:

t_q = t_w + t_s

and thus also for the mean values:

<t_q> = <t_w> + <t_s>.

On the average, for a steady state condition, we must have:

<w> = <n> <t_w>

If we in one second serve <n> events (in a steady state the number of transactions served equals the number of arrivals on the average) and the mean service time is <t_s>, the total time of that second used in servicing is <n> <t_s>, which is precisely the amount of time the facility is being used, hence the utilization factor becomes just that:

u = <n> <t_s>

Combining the above relations, we see that:

<q> = <n> <t_w> + <n> <t_s> = <w> + u.

The basic result of single-server queuing theory was developed by Khintchine and Pollaczek and can be expressed:

where the parameter R_s is given by

R_s = (<t_s>/Sd)²

When the service times are exponentially distributed, the standard deviation Sd is equal to the mean:

Sd = <t_s>

and then

We shall comment upon the relation <w> = <n> <t_w>. In a steady state as many items leave the queue as enter it from the other end. That number is <n>. If the queue contains <w> items and <n> leave per second, it will take <w>/<n> seconds to empty the queue and the latest arrival would the spend so many seconds in the queue, hence the time an item waits before being served is:

We can now write

thus

Using <w> = u²/(1-u), we finally get:

We have thus expressed the queuing time <t_q> in terms of the service time <t_s> and the utilization u.

The following table shows this relationship between the load factor u, the number of items in the system <q>, and the response times <t_q> in terms of the mean service time <t_s>:

It is clear that when the utilization increases to beyond 80%, the queues grow alarmingly and the system is hardly usable at all.

When we have a stream of transactions that arrive at random, the times between arrivals are exponentially distributed. But suppose that there is a two-way switch at the arrival point. The switch operates so as to send alternate transactions on alternate output "lines" for service. The result is a more uniform distribution of interarrival times. The distributions that result in this way have been studied by the Danish mathematician A.K. Erlang and are called Erlang distributions. (Erlang worked for the Copenhagen Telephone Company, which explains the terminology of traffic, switches, and lines). The exponential distribution is an Erlang-1 distribution, while the two-way switch generates Erlang-2 distributions. If we had switched the transactions down a very large number of paths - instead of just the two as above - the resulting interarrival times would become very nearly constant. An Erlang-infinity distribution of interarrival times means that these are constant.

The converse is also true: if we concentrate onto one line the traffic from many separate lines, the spread in interarrival times will increase leading to more queuing, as there will be bursts of events piling up, as well as intervals without traffic, where the server is idle and the facility is underused.

Switching down several output lines simply means having several servers handling transactions. Let us assume there are M identical servers. The mean number of items arriving per unit time is <n> as before. Thus <n>/M items go to each server. Again, let the mean service time be <t_s>. The facility utilization therefore becomes:

u = <n> <t_s> / M

And so:

<q> = <w> + M u

It can be shown that the probability that ALL servers are busy at a given time is

B = P(q>=M) = (1 - Z(M,u)) / (1 - u Z(M,u))

Where

Z(M,u) = (sum ((M u)ⁱ/i!) from i = 0 to M-1) / (sum ((M u)ⁱ/i!) from i = 0 to M)

For M = 1 the expression for B reduces to B = u. The table below explores B as a function of u and M:

The mean number of items in the queue can be shown to be

hence

and the response time becomes:

<t_q> = <q> / <n> = (<q> <t_s>) / (<n> <t_s>) = <q> <t_s> / (M u)

so that, finally:

For M = 2 we have (exactly):

The following simple formula is a good approximation for all M (exact for M <= 2):

<t_q> = <t_s> / (1-u^M)

We shall contrast the response times (in terms of the mean service time <t_s>) for various values of M and note the significant improvements when M grows larger:

It is important not to confuse the true multi-server model with one where arrivals are just distributed cyclically to each server in turn. This sort of model is really just M single-server queues in parallel and does not give the improvement in response time to the same degree as the true multi-server situation with only one queue.

Since it is important then to have only one queue, we may ask: how long could that queue become? The average number of items in the system is not the measure we want, rather it is <w>, the number of items in the queue. Using <w> = B u/(1-u) we get:

For heavy load, <w> is not very sensitive to the number of servers. It is maybe at first sight a bit surprising that the queue length does not depend on the arrival rate <n>, but only on the facility utilization u. How should the queue length be configured? Characteristic for this type of queue is its wide fluctuations: the standard deviation of the queue length is large. Queuing theory yields the result that the standard deviation of the queue length is given by:

And the queue length itself is:

Under heavy load B and u are both close to one, so:

and

I.e. the standard deviation is of the same size as the length itself. The probability that a value is more than three standard deviations removed from the mean is very low (0.001) so that the maximum queue length could be set to