Performance Modeling and Design of Computer Systems: Queueing Theory in Action
Computer systems design is full of conundrums: •Given a choice between a single machine with speed s, or n machines each with speed s/n, which should we choose?
•If both the arrival rate and service rate double, will the mean response time stay the same?
•Should systems really aim to balance load, or is this a convenient myth? •If a scheduling policy favors one set of jobs, does it necessarily hurt some other jobs, or are these "conservation laws" being misinterpreted?
•Do greedy, shortest-delay, routing strategies make sense in a server farm, or is what's good for the individual disastrous for the system as a whole?
•How do high job size variability and heavy-tailed workloads affect the choice of a scheduling policy?
•How should one trade off energy and delay in designing a computer system?
•If 12 servers are needed to meet delay guarantees when the arrival rate is 9 jobs/sec, will we need 12,000 servers when the arrival rate is 9,000 jobs/sec?
Tackling the questions that systems designers care about, this book brings queueing theory decisively back to computer science. The book is written with computer scientists and engineers in mind and is full of examples from computer systems, as well as manufacturing and operations research. Fun and readable, the book is highly approachable, even for undergraduates, while still being thoroughly rigorous and also covering a much wider span of topics than many queueing books. Readers benefit from a lively mix of motivation and intuition, with illustrations, examples, and more than 300 exercises - all while acquiring the skills needed to model, analyze, and design large-scale systems with good performance and low cost. The exercises are an important feature, teaching research-level counterintuitive lessons in the design of computer systems. The goal is to train readers not only to customize existing analyses but also to invent their own.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Queueing Theory Terminology
Necessary Probability Background
Generating Random Variables for Simulation
Sample Paths Convergence and Averages
WhatIf for Closed Systems
From Markov Chains to Simple Queues
High Variability and Heavy Tails
PhaseType Distributions and MatrixAnalytic Methods
Networks With TimeSharing PS Servers BCMP
The MIG1 Queue and the Inspection Paradox
Task Assignment Policies for Server Farms
MIG1 Transform Analysis
Power Optimization Application
Google Aloha and Harder Chains
Exponential Distribution and the Poisson Process
Transition to ContinuousTime Markov Chains
Multiserver Multiqueue Systems
Capacity Provisioning for Server Farms
TimeReversibility and Burkes Theorem
Networks of Queues and Jackson Product Form
Classed Network of Queues
Closed Networks of Queues
Other editions - View all
analysis Answer arrival process arrival rate assume balance equations busy period chapter classed networks closed system computer systems Consider CTMC deﬁned Deﬁnition derive disk DTMC ergodic example Exercise Exp(A expected number Exponentially distributed FCFS servers ﬁle ﬁnd ﬁnite ﬁrst ﬂips fraction given host independent interarrival intuition irreducible Jackson network job in service job size distribution job size variability job’s jobs arrive jobs at server Laplace transform limiting distribution limiting probabilities Little’s Law load Markov chain mean number mean response mean slowdown non-preemptive number of jobs number of servers Observe packets Pareto distribution Poisson process priority priority queueing problem process with rate proof Question queueing theory random variables rate of transitions sample paths scheduling policy server farm service rate setup shown in Figure SITA solve Speciﬁcally SRPT stationary distribution stationary equations Suppose task assignment policies Theorem throughput time-reversibility z-transform