M/M/1 Queue

Q: Why does the wait grow so fast near full load?

Because the spare capacity $\mu - \lambda$ shrinks. When the server is 99% busy, $W$ is 100 times the service time $\frac{1}{\mu}$, since $\frac{W}{1/\mu} = \frac{\mu}{\mu - \lambda} = \frac{1}{1 - \rho} = \frac{1}{1 - 0.99} = 100$.

Q: What if the arrivals are not random?

The formula assumes random arrivals and exponential service times. If the pattern is very different, such as fixed-length jobs that arrive in bursts, the real waits can differ, and another queueing model may fit better.

Q: How is $W$ different from $L$?

$W$ is the time one item spends in the system. $L$ is the number of items in the system at one moment. Little's law connects them: $L = \lambda W$.

In one sentence: The M/M/1 formula tells you the average time an item spends in a line with one server, based on how fast items arrive and how fast the server works.

$W = \frac{1}{\mu - \lambda}$

Read it out loud: “W equals one divided by the quantity mu minus lambda. W is the average time one item spends in the system, from arrival until it is finished. Mu is the service rate, how many items the server finishes per unit of time. Lambda is the arrival rate, how many items arrive per unit of time. Mu minus lambda is the spare capacity, and it must be greater than zero. Both rates must use the same time unit, such as minutes.”

Before you start

The ideas and signs this page uses, explained from zero. For powers of ten, Greek letters and other notation in general, see Math basics.

Rates: how many per unit of time: A rate tells you how many things happen in each unit of time. The arrival rate $\lambda$ of 8 per minute means 8 customers arrive in an average minute. The service rate $\mu$ of 10 per minute means the server can finish 10 customers in a minute if it never stops. Both rates must use the same time unit, or the numbers cannot be compared.
Greek letters $\lambda$ , $\mu$ and $\rho$: The Greek letter $\lambda$ is called lambda (said LAM-duh). The letter $\mu$ is mu (said MEW). The letter $\rho$ is rho (said ROH). Greek letters are only names, because the Latin alphabet runs out of letters fast. In this formula $\lambda$ is the arrival rate and $\mu$ is the service rate. The letter $\rho$ is used on this page for the utilization, the share of time the server is busy.
Queue, server and the name M/M/1: A queue is a line of items waiting to be served, such as customers at a checkout. The server is the worker or machine that serves them. The name M/M/1 has three parts. The first M means the arrivals are random. The second M means the service times are random too. The 1 means there is one server.
Random arrivals and the exponential pattern: A probability distribution is a rule that says how likely each possible value is. Random arrivals are described by a Poisson process, a standard model in which the time between one arrival and the next is unpredictable, though its average is known. The service times follow an exponential pattern, in which most jobs are quick and a few take much longer. These are the usual assumptions of the M/M/1 model.
Utilization, written $\rho$: The utilization, written $\rho$ , is the fraction of time the server is busy. It equals the arrival rate divided by the service rate: $\rho = \lambda \div \mu$ . A utilization of 0.8 means the server is busy 80% of the time. It has no unit, and it must be below 1, because a server busy all the time cannot clear a line that keeps growing.
Little’s law, $L = \lambda W$: Little’s law is a general rule for any waiting system. It says the average number of items inside equals the arrival rate times the average time each item spends inside, written $L = \lambda W$ . For example, 8 customers per minute, each spending half a minute in the shop, means that on average $8 \times 0.5 = 4$ customers are inside at any moment.

What each symbol means

Symbol	Meaning
$W$	The average time one item spends in the system, from its arrival until it is served and finished. It includes any waiting in the line. It is measured in the same time unit as the rates, such as minutes or seconds. The example gives 0.5 minutes, which is 30 seconds.
$\lambda$	The arrival rate: how many items arrive per unit of time, such as customers per minute. It must be smaller than the service rate, or the line grows without limit. The example uses 8 customers per minute.
$\mu$	The service rate: how many items the server can finish per unit of time, in the same units as the arrival rate. It is the server’s speed. A larger service rate means shorter waits. The example uses 10 customers per minute.
$\rho$	The utilization: the fraction of time the server is busy, found as the arrival rate divided by the service rate. It has no unit and lies between 0 and 1. The example uses 0.8, which means the server is busy 80% of the time.
$L$	The average number of items in the system at one moment, counting those waiting and those being served. It is a count with no unit. The example gives an average of 4 customers inside the shop.

The formula piece by piece

$\lambda$: Start with the arrivals. $\lambda$ is how many items come in per unit of time, such as customers per minute. Arrivals fill the line, so a bigger $\lambda$ means a longer line for the same server. In the example $\lambda = 8$ per minute.
$\mu$: The server’s speed: how many items it can finish per unit of time. $\mu$ is the server’s capacity, which clears the line. In the example $\mu = 10$ per minute, so the server could clear the line faster than customers arrive, on average.
$\mu - \lambda$: The spare capacity, the gap between what the server can do and what arrives. In the example $10 - 8 = 2$ customers per minute of spare capacity. A small gap means the line clears slowly, so each item waits a long time.
$\frac{1}{\mu - \lambda}$: One divided by the spare capacity. Dividing 1 by a rate gives a time, because 1 divided by customers per minute is minutes per customer. In the example $1 \div 2 = 0.5$ minutes, which is 30 seconds.
$W = \frac{1}{\mu - \lambda}$: The whole formula as one sentence: the average time an item spends in the system equals one divided by the service rate minus the arrival rate. The formula is written for a single line with one server, where $\lambda$ is smaller than $\mu$ .
$L = \lambda W$: Little’s law, a related rule for the same queue. The average number of items in the system equals the arrival rate times the average time each item spends there. In the example $8 \times 0.5 = 4$ customers, which matches the count from the formula $L = \frac{\rho}{1 - \rho}$ .

What the formula is doing, and why

An M/M/1 queue has one server, one line, and items that arrive at random. The first M means the arrivals follow a random pattern called a Poisson process. The second M means the service times follow an exponential pattern, where most jobs are quick and a few are long. The 1 means there is one server. Real queues are rarely this neat, but the model gives a useful first estimate.

Two rates describe the line. $\lambda$ is how fast items arrive, and $\mu$ is how fast the server can finish them. Their ratio is the utilization, $\rho = \frac{\lambda}{\mu}$ , which is the share of time the server is busy. If $\rho = 0.5$ , the server is busy half the time and free the other half.

Why this shape? The average time in the system, $W$ , has two parts. One is the time spent being served, which is $\frac{1}{\mu}$ for one item with no line in front of it. The other is the time spent waiting in the line, which is $\frac{\rho}{\mu - \lambda}$ . Added together, they give $W = \frac{1}{\mu - \lambda}$ . The gap $\mu - \lambda$ is the spare capacity. The wider the gap between the service rate and the arrival rate, the shorter the average time.

When does it break? The formula works only when $\lambda < \mu$ . If items arrive faster than the server can finish them, the line grows without limit, and the average has no finite value. As $\lambda$ gets close to $\mu$ , both $W$ and $L = \frac{\rho}{1 - \rho}$ grow very fast. That is why queues blow up near full load. A server kept 99% busy has very long waits.

A check on the answer. The average number of items, $L$ , agrees with Little’s law, $L = \lambda W$ . Multiplying the arrival rate by the average time gives the same number of items in the system. Doing this check after each calculation is a good way to catch mistakes.

An everyday picture

Think of a checkout with one cashier. Shoppers arrive at random, and the cashier works at a steady pace. The gap between how fast shoppers arrive and how fast the cashier works is the spare capacity. When that gap is wide, the line is short. If shoppers arrive almost as fast as the cashier can serve them, the spare capacity is tiny, the line grows long, and each new shopper waits far longer than the time the checkout itself takes to serve one shopper.

Worked example: A coffee shop with one barista

A coffee shop has one barista. Customers arrive at random, at an average rate of $\lambda = 8$ per minute. The barista can serve $\mu = 10$ customers per minute. Both rates use minutes, so the time that comes out of the formula is in minutes. The numbers are made up for this example, and the M/M/1 model is only a first estimate.

Write the rates in one unit. Arrivals come at $\lambda = 8$ customers per minute, and service runs at $\mu = 10$ customers per minute. Both rates use the same unit, minutes, so the time from the formula will also be in minutes. Mixing a per-second rate with a per-minute rate would give a wrong answer.
Find the utilization. $\rho = \frac{\lambda}{\mu} = \frac{8}{10} = 0.8$ . The barista is busy 80% of the time and free for the other 20%. Utilization is a share, so it has no unit, and it is always between 0 and 1.
Find the spare capacity. $\mu - \lambda = 10 - 8 = 2$ customers per minute. On average the barista can serve 2 more customers each minute than arrive. That gap is what clears the line, so it is the number to watch.
Find the average time in the shop. $W = \frac{1}{\mu - \lambda} = \frac{1}{2} = 0.5$ minutes. Dividing 1 by a rate gives a time, because 1 divided by customers per minute is minutes per customer. Multiplying by 60 turns minutes into seconds, so $0.5 \times 60 = 30$ seconds.
Find the average number of customers inside. $L = \frac{\rho}{1 - \rho} = \frac{0.8}{0.2} = 4$ customers. The term $1 - \rho = 0.2$ is the free share of the barista’s time. On average, the shop holds about 4 customers at any moment, counting those in the line and the one being served.
Check with Little’s law. The count should equal the arrival rate times the average time, so $L = \lambda W = 8 \times 0.5 = 4$ . This matches step 5, which is a good sign that both numbers are right.
See how a modest rise changes the wait. Suppose customers arrive at 9.5 per minute. Then $\mu - \lambda = 10 - 9.5 = 0.5$ per minute, and $W = \frac{1}{0.5} = 2$ minutes, which is 120 seconds. The arrivals rose by about 19%, from 8 to 9.5, but the average wait went up four times, from 0.5 minutes to 2 minutes.

Answer: The barista is busy 80% of the time, each customer spends about 30 seconds in the shop on average, and about 4 customers are inside at any moment. If arrivals rise to 9.5 per minute, the average time in the shop jumps to 2 minutes.

The numbers in this example are recomputed by script every time the site is built.

Common mistakes

Using the formula when $\lambda \geq \mu$ . The server cannot keep up, so the line never settles, and the formula gives a meaningless negative or undefined answer.
Treating $W$ as only the waiting time. $W$ also includes the time being served, so it is always larger than the time spent in the line.
Mixing rates in different units, such as arrivals per minute and service per second. Convert them to one unit first, or the answer will be wrong by a factor of 60.
Treating $\rho$ as a count of items. Utilization is a fraction between 0 and 1, the share of time the server is busy.

Where you will meet it

Estimating response times for a single web server under a steady load, where requests arrive at random and the server handles them one at a time.
Early estimates for a help desk with one agent, or a checkout with one cashier.
Network design, to estimate the delay at one network link, where data waits in a queue before it is sent.
Teaching queueing theory, the study of waiting lines, since this is the simplest model that shows how waiting time grows near full load.

Questions people ask

Why does the wait grow so fast near full load?

Because the spare capacity $\mu - \lambda$ shrinks. When the server is 99% busy, $W$ is 100 times the service time $\frac{1}{\mu}$ , since $\frac{W}{1/\mu} = \frac{\mu}{\mu - \lambda} = \frac{1}{1 - \rho} = \frac{1}{1 - 0.99} = 100$ .

What if the arrivals are not random?