Discrete Modeling

Two Views of Traffic

Traffic can be studied with two different kinds of models, and this chapter leans on both. A discrete model tracks individual, countable objects — data packets hopping between machines, customers stepping up to a counter. A continuous model smears those objects into a flowing quantity — a density of cars along a road that thins and thickens like a fluid.

Both kinds of model describe the same handful of quantities: the throughput (how much traffic passes through per unit time), the maximum throughput (the most the system can handle per unit time), the capacity (how many jobs can be in service at once), and the filling (how much is inside right now). We make each of these precise later in the chapter. What separates the two views is not what they measure but the mathematics used to get at it.

• Discrete consideration — data traffic in computing systems. A computing system moves data packets between components, and we model it as a network of queues, analyzed with probability theory, stochastic processes, and random variables. This is the subject of the present chapter.
• Continuous consideration — traffic flow. Road traffic is modeled as a continuous medium, described with integrals, derivatives, and partial differential equations. That is the subject of Traffic Flow Models.

It helps to keep both pictures in mind at once — internet data traffic and road traffic — because the same optimization questions (push more through, avoid jams) recur in both.

The Modeling Problem

The goal is to describe — and then optimize — a computing system built from several service units, each with its own functionality, and to model and simulate the traffic of data packets flowing through the network they form. “Optimize” here is concrete: improving an existing system, or designing a better one from scratch.

The road-traffic analogy makes the aims tangible. In the city, traffic lights are controlled to maximize the throughput of the intersections; on highways, a traffic-management system heads off congestion before it forms. The same two goals — move more traffic, avoid jams — carry straight over to data packets moving through a network.

We model such a system as a queuing network: queues sitting in front of service units, studied with probability theory, queues, and stochastic processes. Why bring in randomness at all? Because the model is inherently stochastic, for two reasons:

• The events are unpredictable when we can see only part of the system’s components.
• We rarely need the exact fate of every individual packet — what we want are mean values and averages: the average waiting time, the average throughput, and so on.

A Simple Example: The Post Office

Before touching computers, it helps to look at an everyday system with exactly the same structure. The classic one is a post office — or, just as well, a single shop: one facility with its own queues and counters, serving a stream of arriving customers. That single shop is the right unit for now. Later, when many such shops are wired together so that a job is split into partial tasks and routed through several shops in turn — each shop handling a different part — the picture grows into a whole shopping center, and that network of shops is exactly what a queuing network will be. We are not there yet; for this first example, one shop is enough.

A post office has one entrance $E$, one exit $A$, one or several counters $S$ where customers are served, and one or several queues $W$ where they wait. The aim is to make everyone — customers and employees — happy.

But “happy” pulls in two directions, and that tension is the whole problem:

• Customers want a short average waiting time.
• The operator wants a short expected idle time for the personnel — staff standing around with no one to serve is wasted money.

These two aims conflict. Idle time is smallest with a single employee, who is then almost never idle — but that lone counter makes the average customer wait the longest. Push the other way, opening a counter for every customer, and nobody waits while the staff sit idle most of the day. What makes the trade-off genuinely hard is the randomness in when customers arrive and how long each one takes: the stochasticity is unavoidable.

To turn this into a model, we pick out the objects involved and the parameters that describe each:

• customers — type of job, frequency and intervals of arrival, execution time;
• counters — open or closed;
• employees — functionality (which jobs they can handle), promptness, reliability.

The same post office can also be laid out in two different ways, and the choice matters:

• one queue per counter — each arriving customer picks a line and commits to it (the classic supermarket layout);
• a single shared queue — everyone waits in one line, and whoever is at the front goes to whichever counter frees up next (the modern bank or airport layout).

Both are built from the same entrance, queues $W$, and counters $S$, yet they behave differently — a difference we come back to once we can measure waiting times.

Interfaces to the Environment

A post office cannot be modeled as a stand-alone system. It sits inside a wider context — the town, people’s daily routines, the surrounding economy — that is impossible to capture completely. So we restrict the model to the interfaces between the system and its environment, and decide what has to happen at each. Three tasks fall out.

Modeling the environment

The environment supplies the system’s input, and two questions define it: how often, and at what intervals, do customers arrive, and what exactly do they want? Arrival patterns are not uniform — different kinds of customer show up at different times of day. There are two ways to feed this into the model:

• Use measured data directly. Take empirical measurements — the famous “car counters” stationed along highways are the canonical example — and drive the simulation straight from the recorded samples.
• Fit a distribution and synthesize. Use the same measurements to derive a probability distribution, then generate fresh, synthetic input data that is statistically representative of the real thing.

The second route is the more flexible one: instead of replaying the recording verbatim, we extrapolate it into a distribution and sample new data from that. It also raises a question we return to at length later — how do you get a computer to generate randomness in the first place?

Modeling the system behavior

With the input pinned down, the real object of interest is the system behavior — what happens inside the post office once customers are through the door. This is where the modeling effort goes, and it is what the rest of the chapter builds toward.

Analyzing the results

Reading answers off a run is not the end. The output of a stochastic simulation is itself random, so the analysis leans on statistics: running suitable tests and checking that the observations are independent of one another before trusting any average computed from them.

Some effects are genuinely hard to pin down — the feedback effects, where the system’s own performance changes the demand it faces:

• If word gets around that a post office serves people quickly, more customers travel in from other districts — which slows it back down.
• Customers keep switching lines, convinced the other line always moves faster than their own.

These loops are the hardest part to model faithfully, precisely because cause and effect run in a circle.

The Instruments: Random Variables

Everything the model deals with is random events happening in time, and therefore time intervals of random length — the gap between one customer arriving and the next, the time a counter spends serving one job. Before building anything, we need the vocabulary for describing such a quantity. It all hangs off a single object and the two functions attached to it.

It is worth being clear about which of these two functions is which, because the picture that usually comes to mind belongs to only one of them. The famous bell curve of the normal distribution is a graph of the density $f_T$, not the distribution $F_T$: its defining feature is that the whole area underneath it equals $1$, which is exactly the normalization $\int f_T = 1$. The density is a local statement — the area under a stretch of the curve is the probability that $T$ lands in that stretch, so where the bell is tall the values are likely and where it flattens into the tails they are rare. The distribution $F_T$ is the running total of that same area: sweep from left to right accumulating the density as you go, and $F_T(t)$ is how much has piled up by the time you reach $t$. That accumulating curve starts at $0$, only ever climbs, and levels off at $1$ once all the area is behind it. So the two functions carry the same information in two shapes — the density says how likely each value is at a point, and the distribution says how much probability sits at or below that point.

The random variables here measure durations, so almost always $T \ge 0$, and the effective lower bound of every integral is then $0$ rather than $-\infty$.

Single-number summaries

A whole density is more information than we usually want. From it we pull out a few single numbers — its moments — that capture the distribution’s location and spread. The first-order moment is the one everybody knows.

The two numbers answer different questions. The expected value is your best guess for the size of $T$ — where the value will land on average. The variance and standard deviation tell you how much to trust that guess: a small spread means $T$ is nearly deterministic, a large one means it scatters widely around the mean.

If the integral form looks unfamiliar, it is the continuous version of the variance you would compute by hand from a finite list of measurements, $\frac{1}{n}\sum_i (t_i - \bar{t})^2$. There, each of the $n$ data points chips in its squared deviation with the same weight $1/n$. In the integral the density takes over that weighting job: the factor $f_T(t)\,dt$ stands in for $1/n$, so each squared deviation $(t - E(T))^2$ is scaled by how likely that value is before being accumulated across all $t$. It is the same averaging operation, lifted from a finite sample to a continuous distribution — and the expected value $\int t \, f_T(t)\,dt$ reads the same way, as the continuous counterpart of the plain average $\frac{1}{n}\sum_i t_i$.

There is a catch with the standard deviation, though: it is an absolute figure. Told that a measured length has a standard deviation of two kilometers, you cannot say whether that is a lot or a little without knowing the typical length being measured — two kilometers is enormous for a footpath and negligible for a continent. Normalizing the spread against the expected value fixes this.

Because it divides one length by another, $\varrho(T)$ is a pure number with no units — a scale-free measure of relative spread that can be compared across completely different quantities. It becomes a running yardstick later on.

The dynamical view

The summaries above look at $T$ from the outside, as a finished quantity. The queuing model needs a second, dynamical view: given that we have already been waiting a while, how likely is the interval to end now? That question is built from a conditional probability.

Picture a hot-dog stand: what is the probability that a customer walks up in the next five seconds, given that nobody has come for the last ten minutes? The numerator $F_T(t + \Delta t) - F_T(t)$ is the chance the interval ends inside the little window $(t,\,t + \Delta t]$; the denominator $1 - F_T(t)$ is the chance it survived past $t$ in the first place, which is what “given no one has come yet” restricts us to.

Now shrink the window. As $\Delta t \to 0$ the conditional probability itself goes to zero — wait a short enough instant and nothing happens in it — so the bare limit tells us nothing. The fix is exactly the one that defines a derivative: divide by $\Delta t$ before taking the limit, turning a vanishing probability into a finite rate.

It helps to read the final form back in words. The numerator $f_T(t)$ is the chance per unit time that the interval ends right around $t$, taken over all intervals. Dividing by $1 - F_T(t)$, the fraction that have survived past $t$, restricts that to the survivors: of the intervals still running at time $t$, what fraction finish per unit time right now? A high hazard rate means the end is imminent given how long the interval has already lasted; a low one means it is in no hurry to finish. It is a conditional failure rate, and it turns out to be the most telling fingerprint of a distribution — the two examples that follow are told apart entirely by the shape of their hazard rate.

A Simple Example: The Uniform Distribution

The plainest instrument is the one where nothing is favored: every outcome in a range is equally likely.

A natural scenario is the remaining rotation time of a spinning disk: after a task arrives at a random moment, the wanted block is equally likely to be anywhere along its circular path, so the latency until it passes under the read head is spread evenly from $0$ up to one full revolution $a$.

Its summaries work out to

The expected latency sits at the midpoint $a/2$, as symmetry demands. The coefficient of variation is the interesting one: it comes out to $\varrho(T) = 1/\sqrt{3} \approx 0.577$ with no $a$ in sight. Widening the interval scales the spread and the mean by the same factor, so their ratio is fixed — every uniform distribution has the same relative spread regardless of size.

The hazard rate exposes the distribution’s character:

As $t$ climbs toward $a$ the denominator $a - t$ shrinks and the hazard rate runs off to infinity: the longer the interval has already lasted, the more certain it is to end at any moment. It is the mood of the days before a fixed date on the calendar — the closer Christmas comes, the greater the chance from one day to the next that it is finally here. This rising hazard is exactly the behavior the next example strips away.

A More Exciting Example: Constant Hazard Rate

Turn the previous question around: what must a distribution look like for its hazard rate to stay constant, $h_T(t) = \vartheta$, never rising or falling with $t$?

A constant hazard means the risk of the event sits at the same level for all time. In particular it does not depend on the interval’s own past — how long we have already waited says nothing about how much longer we must wait. That is a property worth naming.

Read the two sides against each other: the left is the chance of lasting an additional $s$ given the interval has already run to $t$, while the right is the chance that a fresh interval lasts $s$ at all. Setting them equal says the elapsed $t$ drops out completely — the clock effectively resets, and only the extra duration $s$ matters. (This is why the right side is $p(T > s)$ and not $p(T > t + s)$: it describes a brand-new interval, not the original one carried further.)

Back at the hot-dog stand: whether you have stood through five quiet hours or just served twenty-five customers in the past hour, the chance that the next customer appears in the next five seconds is exactly the same. The distribution keeps no memory of what came before. A constant hazard is realistic whenever an event can be sourced to many independent, individually unlikely causes — the time until the next system error or user login, the time until an atom’s next spontaneous decay, even the time until the next death in the Prussian army from a horse’s kick, the data set that first popularized this distribution.

Working out which density holds the hazard rate flat produces a familiar pair.

The exponential times the intervals between events. Its discrete companion counts how many events land in a fixed stretch of time.

The two describe the same memoryless stream from opposite ends: the negative exponential distribution measures the time between successive events, while the Poisson distribution counts how many fall inside a window. Their characteristic values are

The coefficient of variation lands exactly on $\varrho(T) = 1$. That makes the exponential a natural reference point for the yardstick introduced above: distributions with $\varrho < 1$ are more regular than the memoryless case, those with $\varrho > 1$ burstier — a comparison we return to once random processes enter the picture.

Stochastic Processes

The instruments from the previous section each describe a single random quantity — one interval, one latency, one wait. But traffic is never a single event; it is the same event happening over and over: customer after customer arrives, task after task finishes, error after error strikes. To model such a stream we need not one random variable but a whole sequence of them.

There are two ways to pin a stream down: by the points in time at which events happen, or by the spacings between them — the gaps from one event to the next. The second is almost always the better handle. A list of absolute timestamps says little on its own, but the gaps between them recur under the same conditions, and a recurring quantity is one you can fit a distribution to. So from here on the object of study is the inter-arrival time, the interval between consecutive events, rather than the raw clock reading.

When the intervals share not just a common nature but a common rule, the process is especially well-behaved.

The name is apt: what stays stationary is not the individual outcomes — those still vary from one interval to the next — but the underlying probability law. Every interval is drawn from the same distribution, and no interval carries information about its neighbors.

Plenty of real streams break one of the two conditions:

• Cars passing a checkpoint are famously companionable: a single slow car gathers a pack behind it, so a long gap tends to be followed by a cluster of short ones. The intervals are not independent — a jam remembers itself.
• The daily average temperature across a year is not identically distributed: a July reading and a January reading come from visibly different distributions, so the law drifts with the season.

One stationary process matters more than any other here — the one whose intervals are memoryless.

Because its intervals are exponential, the Poisson process inherits their defining trait: memorylessness. That single property — the process forgets how long it has already been waiting — has consequences that run squarely against intuition, as the next example shows.

The Hitchhiker’s Paradox

A hitchhiker stands at the roadside. Twenty minutes pass with no car. Surely, they reason, a car must be due any moment now — the longer the drought, the closer the next arrival ought to be. If cars pass as a Poisson process, this reasoning is exactly wrong, and pinning down why is worth doing slowly.

Fix attention on a single gap between two consecutive cars. The length of that gap is the random variable $T$: some gaps are short, some long, and each new gap draws its own $T$ from the same distribution. Now the hitchhiker arrives just as a car goes by and starts waiting somewhere inside one such gap. Write $t_0$ for how long they have waited so far with still no car. That wait tells us one thing for certain: the gap they are stuck in must be longer than $t_0$ (in symbols, $T > t_0$) — otherwise the next car would already have come.

What the hitchhiker actually wants to know is about the rest of the wait, and we get at it by asking how the full gap length $T$ is distributed once we condition on knowing $T > t_0$. Call that conditional distribution $F_{T \mid T > t_0}(t)$: the probability that the gap’s whole length turns out to be at most $t$, given that it already exceeds $t_0$. So the threshold $t$ is a candidate value for the total length, and only values $t \ge t_0$ make sense — we have already ruled out every gap shorter than what has elapsed. The first line below just restates this; the remaining lines evaluate it for the exponential gap:

The first three lines are general — the definition of conditional probability, then its rewrite through the distribution function $F_T$. From the fourth line on we plug in the negative-exponential form $F_T(t) = 1 - e^{-\vartheta t}$: the survival term collapses to $1 - F_T(t_0) = e^{-\vartheta t_0}$, and dividing through leaves a single exponential in $t - t_0$.

The result reads most clearly once you name the leftover explicitly. Since $t$ is the mark measured from the start of the gap and $t_0$ is how much has already elapsed, $t - t_0$ is the time still to come from the moment the hitchhiker checks. Writing that remaining time as its own random variable $R = T - t_0$, the last line says that for any leftover duration $r$,

the leftover $R$ has exactly the same distribution as a brand-new gap $T$. The elapsed $t_0$ only shifts where the clock starts; it does not reshape the distribution, which simply begins again from $t_0$.

This is not the much stronger — and false — claim that every remaining wait is equally likely. Keep the same gap and say the hitchhiker has already waited $t_0 = 10$ minutes. The chance the gap ends by its $t = 15$ mark, i.e. within $5$ more minutes, is $F_T(5) = 1 - e^{-5\vartheta}$, fairly modest; the chance it ends by the $t = 100$ mark, within $90$ more, is $F_T(90) = 1 - e^{-90\vartheta}$, all but certain. A longer remaining wait is still far likelier to have finished than a shorter one, exactly as for a fresh gap — the shape of $F_T$ is unchanged. What memorylessness removes is only the dependence on how long you have already waited: whether that is $10$ minutes or $1000$, the odds of lasting another $5$ come out identical. That is precisely the hitchhiker’s error: the wait already endured says nothing about the wait still to come. The expectation says the same thing plainly:

Given that you have already waited $t_0$, the expected total is $t_0$ plus a full mean interval — not the mean minus what you have already endured. The hitchhiker’s twenty minutes buy nothing; the expected remaining wait is still the whole $E(T) = 1/\vartheta$.

This invites a sharper question. Drop an outside observer onto the timeline at a random moment — not synchronized to the events in any way — and ask: how long until the next event, and how long since the last?

Track these two clocks across the timeline of events at $\dots, t_{i-1}, t_i, t_{i+1}, \dots$ with intervals $T_i = t_i - t_{i-1}$. Over each interval the forward recurrence time starts at the full interval length the instant after an event and ramps down to zero as the next event approaches — a downward ramp of slope $-1$. The backward recurrence time is its mirror image: it starts at zero and ramps up to the full interval length, slope $+1$. Plotted over the whole timeline, the forward recurrence time traces a row of right-triangular “saw teeth,” one per interval, each of height and width $T_i$. The observer, arriving at a random instant, lands somewhere under these teeth, and the recurrence time they measure is the height of the tooth at that point.

Now the setup that gives the paradox its bite. Imagine two restaurants on the same street. The first records the true intervals between its own customers — the full $T_i$. A rival across the road does something subtly different: at scattered moments it starts a stopwatch and times how long until the next customer walks in, sampling the forward recurrence time. How does the rival’s average compare to the true average interval?

Intuition says the rival must measure less: each of its stopwatch readings is only the tail end of some interval, a piece of a $T_i$ rather than the whole of it. So the rival’s average ought to fall below the true mean. That intuition is about to be tested — and for bursty traffic it fails outright.

The Outside Observer

Whatever the observer’s intuition, the actual average forward recurrence time is fixed by the distribution of $T$, and it comes out equal to the average backward recurrence time:

The three forms are one number written three ways. The middle step uses $E(T^2) = \sigma^2(T) + (E(T))^2$ — the second moment splits into variance plus mean-squared — and the last collects everything into the coefficient of variation $\varrho(T) = \sigma(T)/E(T)$, which is where the entire answer concentrates.

Read through $\varrho$, the formula sorts every process into three regimes against the true mean $E(T)$:

• uniform distribution on $[0, a]$ ($\varrho \approx 0.577$, so $\varrho^2 = 1/3$): the observer sees $E(\text{FRT}) = \frac{E(T)}{2}(1 + \tfrac{1}{3}) = \frac{a}{3}$, which is less than $E(T) = a/2$. Here intuition holds — the rival really does measure below the true mean.
• Poisson process ($\varrho = 1$): $E(\text{FRT}) = \frac{E(T)}{2}(1 + 1) = E(T)$ exactly. The observer measures neither more nor less than the true average.
• any process with $\varrho > 1$: $E(\text{FRT}) > E(T)$. The outside observer measures more than the average interval — the “subset” intuition is not just wrong but backward.

The Poisson case is the one to hold onto, and memorylessness explains it in a sentence. Because the process forgets, the instant the observer arrives is statistically no different from an instant just after an event: the remaining time is distributed like a whole fresh interval, so its mean is the whole $E(T)$ — exactly what the hitchhiker’s conditional expectation already told us. Landing mid-interval gains the observer nothing and costs them nothing.

The $\varrho > 1$ case is the genuinely strange one, and its resolution is worth spelling out. A large coefficient of variation means the intervals are wildly uneven — many short gaps punctuated by a few very long ones. The true average weights every interval equally, short and long alike. But the outside observer does not sample intervals equally: dropping in at a uniformly random instant, they are far more likely to land inside a long interval than a short one, simply because a long interval occupies more of the timeline. The observer oversamples exactly the intervals that stretch out and undersamples the brief ones that flicker past, so their average is dragged above the true mean. The stochasticity is quietly misleading them.

Model Parameters

With the random-variable toolkit in hand, we can go back into the post office — a single shop, one facility with its own counters and queues — and give its parts and its timings precise names. Everything that follows is a shared vocabulary of model parameters: the quantities any such facility is described by, whether it is a post office, a disk drive, or a processor.

Start with what the facility is built from. Its building blocks are all functional units, and they split into two kinds by what they do.

Bundle several of these together and the bundle is itself a unit.

With the parts named, we can measure them. The first quantity is a duration.

The next three quantities describe flow rather than contents.

The dwelling time defined above quietly bundles two very different intervals together, and separating them matters.

The service time is what the dwelling time collapses to when there is nothing to wait for. Concretely, when the filling is $f = 1$ — the job is the only one in the system — there is no queue to sit through, so the waiting time is $w = 0$ and the dwelling time is exactly the service time, $y = b$. Waiting appears only once jobs pile up and compete for a unit; it is a consequence of the crowd, not of the counter.

Little’s Law

One relation ties the flow quantities together so generally that it is the central law of traffic theory. It connects three of the parameters just defined — the filling, the throughput, and the dwelling time — and it holds with no assumption at all about how jobs arrive or in what order they are served. That generality is what makes it worth its name.

The relation is easiest to feel with a concrete rate. Picture a car plant that completes $d = 10$ cars per hour, where each car spends $\bar y = 5$ hours on the line from first weld to drive-off. At any given moment the line must hold $\bar f = 10 \cdot 5 = 50$ cars in progress — that is simply what it takes to keep finishing ten every hour when each one needs five hours inside. Speed the completions up, or make each car take longer, and the number simultaneously on the line rises in exact proportion.

The law sharpens into something even simpler for the smallest interesting case. Take a service unit on its own and make it simple ($k = 1$). Inside such a unit a job is always being processed rather than waiting — the queueing happens outside, in the canal — so its dwelling time is exactly its service time, $E(Y) = E(B)$. The stochastic law then collapses into a short chain:

Read it left to right. Substituting $E(Y) = E(B)$ gives the first equality. A simple unit can finish jobs no faster than one per mean service time, so its maximum throughput is $c = 1/E(B)$ (a job needing six minutes caps the unit at ten per hour), which turns $E(D) \cdot E(B)$ into $E(D)/c$. That last ratio is the expected utilization: $R$ is the stochastic counterpart of $r = d/c$, so $E(R) = E(D)/c$. For a simple unit, then, the average filling is nothing but its utilization.

An Intuitive Proof

The operational form is not an assumption but a piece of bookkeeping, and the picture that proves it is worth carrying. Track two running counts across the window: let $n_z(t)$ be the number of jobs that have arrived by time $t$, and $n_a(t)$ the number that have departed — completed — by time $t$. Both are step functions that jump up by one at each event; plotted together they trace two rising staircases, the arrival staircase $n_z$ always on or above the departure staircase $n_a$. Because the system is empty at both ends of the window, the two staircases meet there: $n_z(t_1) = n_a(t_1)$ and $n_z(t_2) = n_a(t_2)$.

At any instant the vertical gap between the staircases is the filling — the jobs that have arrived but not yet left:

The area trapped between the two staircases can be read two ways. Swept vertically, column by column, it is the filling accumulated over time. Swept horizontally, row by row, each job contributes a strip whose width is its own dwelling time $y$. So the same area equals both the time-integral of the filling and the sum of every job’s dwelling time. Dividing that area by the elapsed time gives the average filling,

and dividing the very same area by the number of jobs that completed in the window gives the average dwelling time,

Because the two share that integral, dividing the first by the second cancels it outright:

The ratio that survives is the number of completions per unit time — exactly the throughput $d(t_1, t_2)$ — and rearranging leaves Little’s law, $\bar f = d \cdot \bar y$.

One theme is worth carrying forward out of all this. Every case above is governed by a single number, the coefficient of variation $\varrho(T)$. When $\varrho$ is small the process is tame — the outside observer and the true average nearly agree, and intuition mostly works. When $\varrho$ is large the same intuition breaks down: averages diverge, and the system becomes hard to reason about. Variation is the troublemaker. The smaller it is, the friendlier and more predictable the traffic; the larger it is, the more the randomness confounds our expectations. This is the first hint of a lesson that returns whenever stochasticity meets a system we are trying to run well.

Elementary Queuing Systems

A single service unit on its own is a dull object: jobs arrive, get served one after another, and there is little to optimize. The interesting behavior — queues forming, counters sitting idle, the tug-of-war between waiting time and idle time — appears only once a service unit is wired together with somewhere for jobs to wait. That assembly is a queuing system.

The simplest such system worth studying has exactly one of each part.

To turn this into something we can analyze, two things have to be pinned down: how jobs come in, and how they are handled once inside. Both are governed by chance, so both are modeled as stochastic processes — the incoming stream specified from outside the system, the processing from within.

Arrival and Service Processes

The two processes describe the two halves of a job’s life: getting in, and getting served.

For each process, the distribution of its governing time falls into one of three classes, and these three letters become the alphabet everything downstream is written in:

• D — deterministic: the time is constant, nothing is left to chance. Jobs arrive exactly every so many seconds, or every job takes exactly the same service time.
• M — Markovian: the time is negative-exponentially distributed, with distribution $1 - e^{-\lambda t}$ and expected value $1/\lambda$. This is the memoryless middle ground — general enough to be realistic, simple enough to compute with.
• G — general: the time follows an arbitrary distribution. Very powerful, but very complex to analyze.

The M class is the one to dwell on, and it comes with a named rate for each process.

The Poisson Counting Process

The M class deserves a closer look, because its rate parameter is an old friend in disguise. Memorylessness already told us that a negative-exponential time has a constant hazard rate: at every instant, no matter how long we have already waited, the chance of the event landing in the next tiny slice of time is the same. That constant is exactly the rate just named.

So the answer to “why does the hazard rate reappear here as something else” is that it is not something else. The event rate, the arrival rate, the service rate, and the constant hazard rate of a memoryless time are one quantity seen from several angles. A Markovian process with rate $\vartheta$ is precisely a Poisson process, and the alternative name counting process says what it does: it counts events. The number of arrivals falling in an interval of fixed length is Poisson-distributed, which is where the whole family gets its name.

One consequence is worth stating plainly, because it draws the line between a system that copes and one that jams. As long as jobs arrive slower than the system can clear them — arrival rate below the maximum throughput, $\lambda < c_\mathrm{QS}$ — the throughput simply matches the arrival rate:

Everything that comes in goes out at the same average pace, and nothing accumulates. Push $\lambda$ past $c_\mathrm{QS}$, though, and the picture breaks: the system can no longer keep up, a waiting line builds without bound, and the throughput stops tracking the arrival rate altogether — it saturates at the most the servers can manage while the queue behind them grows. Throughput reflects arrivals only while there is spare capacity to absorb them.

For all its convenience, M is a model, not reality, and it does not always fit. Its memorylessness is exactly what real traffic often violates: cars on a road travel in packs rather than independently, and at a hot-dog stand the feeling that “it’s been five minutes, someone is bound to come” is precisely the kind of memory a Poisson process forbids. M is popular because it is often realistic enough and easy to analyze — but the fit has to be checked, not assumed.

Classifying Elementary Queuing Systems

With arrival and service processes each sorted into D, M, or G, an entire elementary queuing system can be summarized in a compact shorthand.

A few standard cases show the range, from the friendliest to the intractable:

• M | M | 1: negative-exponential arrivals and service, a single service unit. Simple and analytically treatable, though only of limited realism.
• M | G | 1: negative-exponential arrivals, arbitrarily distributed service, one service station. More complicated, but often quite realistic — a good model for a CPU.
• G | M | 1: general arrivals, Markovian service. Complicated, with less potential for applications.
• G | G | n: general arrivals and service, $n$ stations. Hardly treatable analytically at all.

The trade-off is clear: every step away from M toward G buys realism at the cost of tractability.

Sequence Planning: Service Strategy

The parameter $D$ hides a design question of its own — once several jobs are waiting, which one does a freed server take next? The rule that decides is the service strategy, and while we lean on just one of them throughout, it is worth seeing the menu.

Non-preemptive strategies never interrupt a job once its service has begun — their advantage is that no work is ever thrown away:

• random: the next job is chosen at random;
• FCFS: first-come-first-served, the job that has waited longest goes next;
• LCFS: last-come-first-served, the newest job goes next;
• priority based: each job carries a priority and the highest goes next;
• SJN: shortest job next, the job with the smallest service time goes next.

Preemptive strategies may suspend a job in service to start another — their advantage is that they can react to service time without knowing $B$ in advance:

• round robin: jobs are served in turn, each for a fixed time slice;
• LCFS-preemptive: a newly arriving job is taken up immediately;
• priority first: an arriving job of higher priority displaces the one in service;
• SET: shortest elapsed time, the job served least so far wins;
• SERPT: shortest (expected) remaining processing time.

Preemption is powerful but costly to model: interrupting and resuming jobs makes the service and waiting times far harder to compute. To keep the analysis tractable we take the queue discipline to be FCFS unless stated otherwise — the plain, fair, first-come-first-served line of the post office.

First Results

A handful of quantities for the elementary queuing system now follow with almost no work, straight from Little’s law and the parameters already in hand. That none of them is surprising is itself the point — the machinery is consistent.

The formulas below reuse the letters introduced earlier, so a quick reminder before they arrive. Every capital is the stochastic (random-variable) counterpart of a lowercase operational quantity, and each subscript marks which part of the system it refers to:

• $B$: service time, the net time in service; $W$: waiting time spent in the canal; $Y$: dwelling time, the two together, $Y = W + B$.
• $D$: throughput, jobs completed per unit time; $F$: filling, jobs currently inside; $R$: utilization, $R = D/c$; and $c$: maximum throughput, the sustainable ceiling.
• Subscripts SS, SU, WP, QS: a single simple service station (capacity $1$), the service unit (its $n = k_\mathrm{SU}$ stations together), the waiting pool, and the whole queuing system.

Start with the maximum throughput. A single simple station finishes at most one job per mean service time, so its maximum throughput is $c_\mathrm{SS} = 1/E(B)$; a service unit of $n$ such stations working in parallel is $n$ times as fast:

The expected utilization of the service unit is then its throughput measured against that ceiling:

Little’s law applies just as well to the waiting pool on its own — its average filling equals throughput times average waiting time — and to the whole system, whose dwelling time is waiting plus service:

And because a job in the system is either waiting or being served, the two fillings simply add:

Useful as these are, the elementary queuing system is ultimately too small a model to carry the whole load. A real computing system is not one shop with one queue but many specialized shops wired together — a shopping center — with a job threading from one to the next, splitting and rejoining along the way. The next step is to connect elementary queuing systems into queuing networks: systems assembled from elementary queuing systems plus a model for how jobs are routed between them, which is where the theory starts to earn its keep.

Queuing Networks

The natural way to wire shops together is a graph. Each shop keeps its own counters and its own line, and the streets between them say where a customer may go next.

Whether jobs may enter and leave at all splits the networks into two families, and the distinction decides which analysis is available.

A closed network is the shopping center with its doors locked and a fixed crowd inside, wandering from shop to shop forever. That sounds artificial, but it is the right idealization for a computing system running a fixed number of concurrent processes, and it is far easier to analyze — which is why the asymptotic analysis below is built on it.

There is one casualty of the move from one shop to many. In an elementary queuing system, “a job arrives” told us everything we needed; a job was an indivisible lump of work that a single server would eventually finish. In a network that description no longer suffices, because it leaves three questions open: does the job split into several subjobs? How many service stations does each subjob need, and for how long? And in what order must the subjobs run — which of them must wait for which?

Load and Task Streams

Answering those three questions is what the incoming stream has to specify. So the arrival description grows a second component: alongside when work shows up, it must now say what that work is.

The resource declaration gets its own compact notation. Writing

packs all three facts into one symbol: the subscript names the subjob and the service unit it claims, and the superscript gives the length of that claim. The letter itself names the task type the subjob belongs to.

Several task streams may feed the same network at once, and the whole demand it faces is their collection.

Parameters in a Queuing Network

Take a network with $m$ elementary queuing systems as its vertices. Every parameter from the single-shop vocabulary survives, now carried by each vertex separately and tagged with its index: vertex $i$ has an arrival rate $\lambda_i$, a throughput $D_i$, a maximum throughput $c_i$, a utilization $R_i$, a service time $B_i$, and so on. These are the local quantities.

Alongside them stand the same quantities read off the network as a whole, the system quantities, marked by a subscript $S$:

Only the arrival rate composes by plain summation — the rest are genuinely new, network-level quantities that the local ones do not simply add up to, as the counter-example at the end of this section makes uncomfortably clear. In a closed network nothing arrives from outside at all, so $\lambda_i = \lambda_S = 0$, and the filling is pinned to a constant, $F_S = f_S$.

The one genuinely new parameter counts how often a single job passes through a given vertex.

The name is easier to trust with the shopping center in view. If $100$ customers pass through the center while the restrooms record $200$ visits, then $\nu_i = 2$: on average every customer went twice. A vertex with $\nu_i = 1/4$ is one that only a quarter of the customers ever enter. So $\nu_i$ is not restricted to whole numbers, and it may sit on either side of $1$.

Because the ratio is fixed by the routing rather than by the load, raising the system throughput $E(D_S)$ raises every local throughput $E(D_i)$ in exact proportion, and with them every local utilization $E(R_i)$. Push more customers through the doors and every shop gets busier by the same factor. That observation is what makes the next definition inevitable.

Push more customers into the center and every shop’s utilization climbs in lockstep. One shop hits $1$ before the others, and from that moment on it cannot serve anyone faster; the queue in front of it grows, and everything downstream starves. The network’s ceiling is set by its busiest vertex, not by its average one.

Locating the Traffic Bottleneck

The bottleneck can be pinned down in two ways, and they turn out to name the same vertex. The first reads straight off the definition, using $R_i = D_i / c_i$:

The second comes at it from the network’s maximum throughput. A vertex $i$ visited $\nu_i$ times per job can support at most $c_i / \nu_i$ jobs per unit time through the network, and the network can only go as fast as its slowest such constraint:

That the maximizing vertex of the first expression is the minimizing vertex of the second is a one-line substitution. Replace each local throughput by $E(D_i) = E(D_S) \cdot \nu_i$ and the system throughput, being the same for every vertex, factors straight out of the maximum:

What is left inside the maximum is $\nu_i / c_i$, whose largest value picks out exactly the vertex whose $c_i / \nu_i$ is smallest. The most heavily utilized vertex and the one that caps the network are one and the same.

Asymptotic Analysis of Closed Networks

The popular way to get at a network’s behavior without solving it exactly is to watch what happens at the two ends of the filling range and connect them. Throughout this section the network is closed — a fixed crowd $f_S$ circulating inside — the model is stochastic, and every vertex is a simple elementary queuing system, so that its maximum throughput is the reciprocal of its mean service time,

Now run the thought experiment. Lock the doors of an empty shopping center and let customers in one at a time, watching the dwelling time $Y_S$ and the throughput $D_S$ as the crowd grows.

A single job, $f_S = 1$. With nobody else inside there is nothing to queue behind, so wherever the customer goes they are served immediately. The dwelling time is exactly the service time, and the throughput is one job per that time:

Very little filling. With two or three or five customers in a whole shopping center, collisions are rare. The dwelling time is still essentially the service time — which, summed over the visits a job makes to each vertex, is

The throughput expression is just Little’s law with $E(Y_S) \approx E(B_S)$ substituted in. Read it as the headline of this regime: dwelling time stays largely constant, and throughput grows linearly with the filling. Twice the customers, twice the business, and nobody waits any longer than before.

Gradually increasing filling. Now the shops start colliding with each other. Waiting time appears, so the dwelling time $Y_S$ begins to climb above the service time, and for that same reason the throughput $D_S$ can only keep growing at a reduced rate. The linear regime is over.

Filling tending to infinity. Jam. Jobs pile up at the traffic bottleneck, whose utilization saturates at the absolute maximum $1$ while the rest of the network waits on it. The throughput can no longer grow at all; it settles on the network’s ceiling, and Little’s law then forces the dwelling time to grow linearly in its place:

Physically the last line is the whole story of a congested system. Pour more jobs in and the output does not react, so everything you add simply accumulates inside — the system gets fuller, and each job’s stay gets proportionally longer.

The Saturation Bend

Both diagrams that these limits describe have the same shape: a straight line out of the origin that eventually surrenders to a horizontal ceiling.

For the throughput, plotted against the filling $f_S$, the small-filling limit $E(D_S) \approx f_S / E(B_S)$ is a straight line through the origin — every job you add contributes its full share of business. The large-filling limit $E(D_S) \to c_S$ is a horizontal line at the network’s maximum throughput. Both are asymptotes, which is worth saying plainly since only one of them looks like the asymptote of school geometry: the line is what the curve hugs as $f_S \to 0$, the ceiling is what it hugs as $f_S \to \infty$. The real curve leaves the line, bends over, and flattens onto the ceiling.

For the dwelling time the picture is the mirror image. The desired behavior is the constant $E(Y_S) = E(B_S)$, a job’s stay being nothing but its own service; the actual curve departs from that floor and settles onto the rising straight line $E(Y_S) \to f_S / c_S$, whose slope is $\nu_\mathrm{TB} / c_\mathrm{TB}$.

Two things are worth noticing about the bend that joins the asymptotes. First, without any stochasticity the curve would not bend at all: throughput would track the straight line exactly and then turn a sharp corner onto the ceiling at the instant the bottleneck saturated. The rounding of that corner is the randomness — with arrivals and service times scattered, some jobs collide and wait long before the network is on average full, so the curve starts losing ground to the ideal line well ahead of the corner. Second, the same softening is what makes the corner’s location a matter of convention rather than a fact you can point at.

Setting the linear asymptote $f_S / E(B_S)$ equal to the ceiling $c_S$ and solving for $f_S$ is all the formula is. Past $f_S^*$ there is no point admitting more jobs — the network finishes them no faster, and every newcomer merely lengthens everyone’s wait. Because the real curve is rounded rather than cornered, though, calling that particular filling the saturation point is in a certain sense an arbitrary determination of the intersection, and its usefulness depends on how sharp the bend actually is. It is sharpest when the service times are narrowly distributed and when the network has a single clear bottleneck; scattered service times, or several vertices competing for the bottleneck, blur the corner and the asymptotes approximate the truth less well.

Service Time and Maximum Throughput

One relation from the single-shop world does not survive the move to a network, and it is tempting enough to deserve a warning. For each simple service unit the reciprocal relation holds exactly,

and it is natural to expect the same at the system level. But the two system quantities are built by different operations. The mean service time sums the per-visit costs,

while the maximum throughput takes a minimum over the vertices,

A sum of reciprocals is not the reciprocal of a minimum, so

is false in general. The reason is structural: $E(B_S)$ averages the work a job does everywhere in the network, while $c_S$ is dictated by the single worst vertex and ignores all the others.

What the Asymptotics Tell Us

The analysis leaves three findings worth carrying away, and they are about how a system responds to being asked to do more at once.

Moving from sequential processing — filling $1$, one job in the network at a time — to simultaneous processing improves throughput and traffic while the filling is small. This is the linear regime, and it is where concurrency pays: the shops sit mostly idle, so an extra customer costs nobody anything and adds their full share of business.

With large filling those gains simply evaporate, because waiting prevails. Past the saturation bend the bottleneck is already running flat out; additional jobs contribute no throughput at all and only extend the queue in front of it. The benefit of concurrency is not a property of the system but of the regime it is operating in.

The most striking application of this is thrashing — the collapse of a computing system’s useful work when too many processes compete for too little memory, so that each of them spends its time fetching pages from disk rather than computing. The network model captures it exactly. As the degree of multiprogramming rises, the number of disk visits per job grows in proportion to the thrashing probability, which is to say $\nu_\text{disk}$ climbs with the filling. Since the disk’s ceiling is $c_\text{disk} / \nu_\text{disk}$, a growing $\nu_\text{disk}$ drives that ratio down until the disk becomes the traffic bottleneck. Beyond a certain degree of multiprogramming it ruins the throughput of the whole system — not because the disk got slower, but because every job started visiting it more often.

Stochastic Processes Revisited

The queuing-network model already earns its keep: from a handful of stochastic ingredients it produces a genuinely useful description of data traffic, and it stays a sound starting point for performance analysis even of present-day systems. But it can be pushed further, especially toward open networks, and doing that pays to look harder at what a stochastic process actually is.

The push is motivated by three facts about computing systems. Their state space is discrete and finite — a machine sits in one of finitely many configurations, countable rather than smeared out. Every state is (perhaps only indirectly) reachable from every other, the rare exceptions being a deadlock or a crash that traps the system. And the probability of moving from one state to another depends only on the two states involved, not on how the system got there or on the clock. A process with all three traits is a homogeneous Markov process in continuous time, and building up to that object is the work of this section.

Processes, Time, and State

When stochastic processes first appeared, a process was a sequence of random variables indexed by position. The broader picture makes the index explicit as time: a stochastic process is a random variable $X$ whose value depends on time $t$, so its distribution carries a time argument,

Two independent choices classify every such process — what values $X$ may take, and which instants $t$ are allowed:

• continuous process: the values are real, $X(t) \in \mathbb{R}$ for all $t$;
• discrete process (or chain): the values are integers, $X(t) \in \mathbb{N}$ or $\mathbb{Z}$ for all $t$;
• process in continuous time: $t$ ranges over $\mathbb{R}$;
• process in discrete time: $t$ takes only countably many values.

Because the two axes are independent, they give $2 \times 2 = 4$ combinations. The one that matters most here is the discrete process in continuous time — the filling of a service unit is exactly this, an integer count that jumps at random instants strung along a continuous clock.

Since the distribution now carries a time argument, so do the quantities read off it: the density and every moment — mean, variance, and the rest — are in general functions of $t$.

That time dependence is exactly what a stationary process lacks. A process is stationary when its distribution does not change with time, which at the level of the mean reads

the expected value is the same whatever instant you sample it at. Rolling a die over and over is stationary, and so is the running sum of your last ten rolls — the recipe never changes. The average daily temperature across a year is not: a July reading and a January reading come from visibly different distributions, so the law drifts with the season. Even a process that starts out non-stationary often settles down, approaching a stationary limit process as $t \to \infty$ — the way a damped oscillation forgets its initial swing and relaxes toward steady behavior.

From Independence to the Markov Property

The strongest way a process can be well-behaved is for its present to ignore its past entirely.

Rolling a die is independent, and so is a lottery draw — yesterday’s numbers have no bearing on today’s. The running sum of the last hundred rolls is not: it plainly leans on what came before, and so does the filling of an M | M | 1 queue, where the number in the system a moment from now is the number now plus or minus one. (For processes in continuous time, independence is at best approximate, holding only when the two instants $t_2 - t_1$ are far enough apart.)

Independence and stationarity are different demands, easy to run together. The running sum of recent rolls is stationary yet not independent: its distribution never changes, but each value still leans on the ones before it. Stationarity constrains the law; independence constrains the memory.

Between total independence and full history-dependence sits the compromise that makes the whole theory work: the process may remember, but only its most recent state.

The reading is practical: a new state depends only on the current one, and the quality of a forecast cannot be improved by looking further back than the present. Over a discrete state space a Markov process is drawn as a state graph, states as nodes and possible transitions as arrows. Every independent process is trivially Markov — if the future ignores even the present, it certainly ignores everything before it — so the Markov processes form the wider class. The running sum of the last ten dice rolls, by contrast, is not Markovian: to predict the next sum you need the ten most recent rolls, not just the current total, so a single state fails to summarize the past.

Homogeneity and Birth–Death

A Markov process pins down how much history matters. One more condition pins down whether the rules drift with time.

It is worth pausing on how a homogeneous Markov process differs from a stationary one, because the two “nothing changes with time” conditions govern different things. Stationarity holds the state distribution fixed — the odds of finding the process in a given state stay put. Homogeneity holds the transition law fixed — the odds of a given move stay put — while the state distribution is free to drift.

An M | M | 1 queue makes the gap concrete. Take one with inter-arrival times averaging $1.5$ and service times averaging $3$, so the arrival rate is $\lambda = 1/1.5 = 2/3$ and the service rate is $\mu = 1/3$. Its filling is not stationary: jobs arrive faster than they can be served, the queue grows without bound, and the state distribution shifts steadily toward higher fillings. Yet the filling is a homogeneous Markov process, because the transition probabilities never change — from any occupied state the next event is an arrival with probability $\lambda/(\lambda + \mu) = 2/3$ and a departure with probability $\mu/(\lambda + \mu) = 1/3$, whatever the clock says. Homogeneous, not stationary.

Homogeneous Markov processes are everywhere in the modeling of computing systems, and elsewhere too — the running sum of dice rolls, or the jittering of a particle in Brownian motion. A special case earns its own name when the state can only inch up or down.

The Family Tree

These conditions nest. Every birth–death process is a homogeneous Markov process (it just restricts the steps to $\pm 1$); every homogeneous Markov process is a Markov process (it just freezes the transition law); and the Markov processes sit inside the still-wider class of all stochastic processes. One more relative rounds out the picture: the random walk, a Markov process whose increments are independent, treated on its own further below.

Cutting across this hierarchy is the stationary / non-stationary divide, which is independent of it — a process at any level of the tree may or may not be stationary. A few examples locate the corners, each tagged by whether its time and its state are continuous ($c$) or discrete ($d$), written time-then-state: