Queueing Systems, Volume 1¶
Kleinrock, L. (1975). Queueing Systems, Volume 1: Theory. Wiley.
Cited by¶
18 citations across 18 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Backpressure
- The same algebra is queueing theory's stability condition \(\rho = \lambda/\mu < 1\): when the arrival rate \(\lambda\) (producer) exceeds the service rate \(\mu\) (consumer), queue length grows without bound, so a stable system must hold \(\lambda \le \mu\) — which an explicit backpressure channel enforces by clamping \(\lambda\) to the consumer's \(\mu\).
This sourceEstablishes the stability condition ρ = λ/μ < 1, under which queue length stays bounded only when arrival rate does not exceed service rate.
Supported in partVerified against the work's full text
Kleinrock supports the queueing half: stability requires rho < 1 (capacity above arrival rate), with congestion otherwise; the backpressure clamp is not in the book.
“the mean capacity of the system must exceed the average flow requirements if chaotic congestion is to be avoided”
- The same algebra is queueing theory's stability condition \(\rho = \lambda/\mu < 1\): when the arrival rate \(\lambda\) (producer) exceeds the service rate \(\mu\) (consumer), queue length grows without bound, so a stable system must hold \(\lambda \le \mu\) — which an explicit backpressure channel enforces by clamping \(\lambda\) to the consumer's \(\mu\).
- Buffering
- Queueing theory model: A single-server queue M/M/1 with arrival rate λ and service rate μ receives jobs according to a Poisson process, the canonical model Kleinrock (1975) develops in detail.
This sourceStandard queueing-theory reference: develops the M/M/1 model (Poisson arrivals, exponential service, single server), deriving steady-state buffer occupancy ρ/(1−ρ) and characterizing stability, blocking, and delay.
SupportedVerified against the work's full text
Kleinrock defines the queueing model the sentence names: "the celebrated M/M/1 queue" denotes "a single-server queue with a Poisson arrival process and an exponential distribution for service time", the memoryless system he introduces as perhaps the simplest interesting model of a queueing system. That definition is what the sentence attributes to the work. The passage supplies the definition rather than the detailed development, and does not display the arrival and service rates under the symbols the sentence uses.
“the notation denotes a single-server queue with a Poisson arrival process and an exponential distribution for service time”
- Queueing theory model: A single-server queue M/M/1 with arrival rate λ and service rate μ receives jobs according to a Poisson process, the canonical model Kleinrock (1975) develops in detail.
- Client Server Model
- Recognizing a system as client–server makes four standard structural moves available. Capacity reasoning: because the server is a shared resource, the apparatus of queueing theory, load shedding, admission control, and fairness across clients applies directly — a clinic with one specialist serving many patients has the same capacity equation as a server with one processing unit serving many connections.
This sourceFoundational treatment of queueing theory — admission control, load, and fairness across many clients contending for one shared server.
Supported in partVerified against the work's full text
Kleinrock treats any demand on a finite-capacity resource as a queueing system, even using a doctor's office, but this text does not cover admission control, load shedding or client fairness.
“conflicts for the use of the resource will arise and queues of waiting customers will form”
- Recognizing a system as client–server makes four standard structural moves available. Capacity reasoning: because the server is a shared resource, the apparatus of queueing theory, load shedding, admission control, and fairness across clients applies directly — a clinic with one specialist serving many patients has the same capacity equation as a server with one processing unit serving many connections.
- Interference and Contention
- Contention is not inherently a design flaw—many systems intentionally multiplex shared resources—but it produces measurable degradation: increased latency, reduced throughput, dropped transactions, or quality loss, as Kleinrock (1975) developed quantitatively in queueing-theoretic terms.
This sourceStandard queueing-theory reference: develops the M/M/1 model (Poisson arrivals, exponential service, single server), deriving steady-state buffer occupancy ρ/(1−ρ) and characterizing stability, blocking, and delay distributions.
Supported in partVerified against the work's full text
Kleinrock treats resource conflicts as queueing and quantifies delay and customer loss, but never discusses contention as a design choice or throughput loss.
“then conflicts for the use of the resource will arise and queues of waiting customers will form”
- Contention is not inherently a design flaw—many systems intentionally multiplex shared resources—but it produces measurable degradation: increased latency, reduced throughput, dropped transactions, or quality loss, as Kleinrock (1975) developed quantitatively in queueing-theoretic terms.
- Logistic Growth
- And in software systems, queue lengths, cache fill, and throughput-versus-load curves show sigmoidal saturation as capacity is consumed.
This sourceStandard reference for the theory of queues, deriving how queue lengths and delay grow without bound (and throughput saturates) as offered load approaches finite system capacity — the sigmoidal load-versus-throughput behavior of software systems. ISBN 978-0-471-49110-1.
- And in software systems, queue lengths, cache fill, and throughput-versus-load curves show sigmoidal saturation as capacity is consumed.
- Markov Process
- Birth–death models of population dynamics and many models of molecular evolution share this structure. Queueing / operations: Birth–death and M/M/1 models assume memoryless arrivals and service (exponential inter-event times), making the present queue length a sufficient state for the future and rendering the system analytically tractable.
This sourceStandard queueing-theory reference: develops the M/M/1 model (Poisson arrivals, exponential service, single server), deriving steady-state buffer occupancy ρ/(1−ρ) and characterizing stability, blocking, and delay distributions.
Supported in partVerified against the work's full text
Kleinrock develops birth-death and M/M/1 models with constant birth and death coefficients and exponentially distributed interarrival and service times. He states that a memoryless state requires continuous-time Markov chains to have "exponentially distributed state times", and that a process's past influences its future only through "the current state of the process", with the number in the system serving as that state in elementary queueing theory. Those are the assumptions and the sufficiency the sentence asserts. The passages show the solvable birth-death and M/M/1 structure rather than the derivation that the sentence's claim of analytic tractability points to.
“Because the Markov property insists that the past history be completely summarized in the specification of the current state”
- Birth–death models of population dynamics and many models of molecular evolution share this structure. Queueing / operations: Birth–death and M/M/1 models assume memoryless arrivals and service (exponential inter-event times), making the present queue length a sufficient state for the future and rendering the system analytically tractable.
- Queueing
- Not free of instability near saturation:
This sourceStandard reference developing the M/M/1 model and showing wait time W = 1/(μ−λ) diverges as utilization → 1, characterizing instability near saturation.
SupportedVerified against the work's full text
Kleinrock shows M/M/1 queue length and delay grow without bound as utilization nears 1, calling it an extreme penalty typical of almost every queueing system.
“we pay an extreme penalty when we attempt to run the system near (but below) its capacity”
- Not free of instability near saturation:
- Tempo Mismatch
- From queuing and process control, service-rate-versus-arrival-rate matching, buffering, and admission control are applied re-pacing remedies.
Supported in partVerified against the work's full text
Kleinrock gives the stability condition (capacity must exceed flow) and finite-storage systems that refuse entry, but never presents them as re-pacing remedies or ties them to process control.
“we obviously require that R < C on each channel in the network”
- From queuing and process control, service-rate-versus-arrival-rate matching, buffering, and admission control are applied re-pacing remedies.
- Thundering Herd
- Standard queueing results (e.g., the M/M/1 model) assume the arrivals are independent, giving bounded expected waiting time.
This sourceStandard reference for queueing theory, including the M/M/1 model and the independent-arrivals (Poisson) assumption that a correlated, synchronized release violates.
SupportedVerified against the work's full text
Kleinrock defines M/M/1 by Poisson (independent-increment) arrivals and derives a finite mean time in system whenever utilization is below one.
“When we consider Poisson arnvals in nonoverlapping intervals, we are considering independent events whose joint probability may be calculated as the product of the individual probabilities (t e , the Poisson process has independent increments)”
- Standard queueing results (e.g., the M/M/1 model) assume the arrivals are independent, giving bounded expected waiting time.
- Unevenness Waste
- The nonlinear-interaction role is precisely this term: at \(\rho = 0.5\) the queue holds one job on average, at \(\rho = 0.9\) it holds nine, at \(\rho = 0.99\) it holds ninety-nine.
This sourceStandard derivation of the M/M/1 queue, giving L = ρ/(1−ρ) and the 1/(1−ρ) blow-up of queue length and delay as utilization approaches one.
Supported in partVerified against the work's full text
Kleinrock's M/M/1 section says average number in system grows without bound as utilization nears one, with a simple pole at rho = 1; the 1, 9, 99 figures are not printed.
“we pay an extreme penalty when we attempt to run the system near (but below) its capacity”
- The nonlinear-interaction role is precisely this term: at \(\rho = 0.5\) the queue holds one job on average, at \(\rho = 0.9\) it holds nine, at \(\rho = 0.99\) it holds ninety-nine.
Domain-specific¶
- Customs-Clearance Delay
- The queueing substructure matters: clearance facilities are constrained-capacity service stations, and arrival-rate spikes — post-holiday parcel surges, sudden tariff-schedule changes, emergency-response shipments — produce non-linear queue blow-up disproportionate to the shortfall in clearance throughput
This sourceThe standard reference for the equilibrium queueing results behind this convex delay growth; only the volume's contents, not the relevant passage, could be consulted for this check, and the customs-specific surge behaviour is not treated there.
- The queueing substructure matters: clearance facilities are constrained-capacity service stations, and arrival-rate spikes — post-holiday parcel surges, sudden tariff-schedule changes, emergency-response shipments — produce non-linear queue blow-up disproportionate to the shortfall in clearance throughput
- Offered load
- Overburden Waste (Muri)
- Output barely rises between 80% and 95% loading, yet the queue — and thus recovery time from any disruption — nearly quintuples
This sourceKleinrock's single-server queueing result that the average time in the system depends on the utilization (traffic-intensity) factor.
Supported in partVerified against a saved copy of the source
“This dependence of average time on the utilization factor p is shown in Figure 3.4.”
- Output barely rises between 80% and 95% loading, yet the queue — and thus recovery time from any disruption — nearly quintuples
- Random Variable
- Probability theory and statistical inference — the foundational object: estimators, test statistics, p-values, likelihood ratios, and posteriors are all random variables, and the X-versus-x discipline plus sampling distributions are the working apparatus. Finance and risk — returns, portfolio P&L, default indicators, and value-at-risk as a quantile are random variables, with copulas and stochastic processes built on top. Operations research and queueing — arrival times, service times, and queue lengths are modeled as random variables with specified distributions (Poisson arrivals, exponential service)
This sourceThe standard development of interarrival times, service times and queue lengths as random variables with specified distributions, with Poisson arrivals and exponential service as the canonical M/M/1 case.
SupportedVerified against the source
- Probability theory and statistical inference — the foundational object: estimators, test statistics, p-values, likelihood ratios, and posteriors are all random variables, and the X-versus-x discipline plus sampling distributions are the working apparatus. Finance and risk — returns, portfolio P&L, default indicators, and value-at-risk as a quantile are random variables, with copulas and stochastic processes built on top. Operations research and queueing — arrival times, service times, and queue lengths are modeled as random variables with specified distributions (Poisson arrivals, exponential service)
Mechanisms¶
- Message Queue Drain
- It misleads when inflow isn't truly held: if producers keep publishing, lag may never reach zero, and "draining" is just normal operation that never ends — the archetype's central trap, a queue refilled faster than it empties
This sourceEstablishes that a queue need not empty when incoming work exceeds service capacity.
- It misleads when inflow isn't truly held: if producers keep publishing, lag may never reach zero, and "draining" is just normal operation that never ends — the archetype's central trap, a queue refilled faster than it empties
- Resource Pooling
- There is also a hard nonlinearity: as a shared pool's utilization approaches full, waiting time doesn't rise gently, it explodes, so a pool run "efficiently" at 95% utilization can deliver terrible service from small fluctuations.
This sourceShows in the classical queueing model that expected delay grows nonlinearly and becomes unbounded as utilization approaches one.
- There is also a hard nonlinearity: as a shared pool's utilization approaches full, waiting time doesn't rise gently, it explodes, so a pool run "efficiently" at 95% utilization can deliver terrible service from small fluctuations.
- Surge Queue
- Because it will hold almost anything, a surge queue can absorb a sustained imbalance for a long time — wait times growing quietly — so "the queue is up, we're fine" masks the fact that arrivals persistently exceed service and the backlog will never drain.
This sourceExplains that a queue is stable only when service capacity exceeds sustained arrivals; otherwise backlog and delay grow without a finite draining steady state.
- Because it will hold almost anything, a surge queue can absorb a sustained imbalance for a long time — wait times growing quietly — so "the queue is up, we're fine" masks the fact that arrivals persistently exceed service and the backlog will never drain.
- Utilization Ceiling and Headroom Rule
- Where there is queueing or contention it is not optional: utilization near 100% drives waiting time toward infinity, so the headroom buys stability, not merely safety.
This sourceShows that queueing delay grows without bound as utilization approaches full service capacity.
- Where there is queueing or contention it is not optional: utilization near 100% drives waiting time toward infinity, so the headroom buys stability, not merely safety.
Verification¶
Does it exist? Confirmed. This work's ISBN resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Read against the text for 11 of 18 citations: 4 supported, 7 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Links previously used in the corpus¶
Before the registry existed this work was also linked 7 other ways.
- https://www.wiley-vch.de/en/areas-interest/mathematics-statistics/queueing-systems-978-0-471-49110-1 ×3
- https://search.worldcat.org/title/1095854 ×1
- https://search.worldcat.org/title/1631500 ×1
- https://www.wiley-vch.de/en/areas-interest/mathematics-statistics/statistics-16st/queuing-theory-16st9/queueing-systems-978-0-471-49110-1 ×1
- https://www.wiley.com/en-us/Queueing+Systems%2C+Volume+1%3A+Theory-p-9780471491101 ×1
- https://www.wiley.com/en-us/Queueing+Systems%2C+Volume+I-p-9780471491101 ×1
- https://www.wiley.com/en-us/Queueing+Systems,+Volume+I-p-9780471491101 ×1
Registry ID ref:b70423ad9ad9 · see in the full table