Performance Modeling and Design of Computer Systems
Queueing Theory in Action
By Mor Harchol-Balter
Publisher: Cambridge University Press
Print Publication Year: 2013
Online Publication Date:February 2013
Online ISBN:9781139226424
Hardback ISBN:9781107027503
Chapter DOI: http://dx.doi.org/10.1017/CBO9781139226424.026
Subjects: Computer Hardware, Architecture and Distributed Computing, Applied probability and stochastic networks
Image View Extract Fullview: Text View | Enlarge Image ‹ Previous Chapter ›Next Chapter
Part VI discusses queueing analysis where the arrival process and/or service process are generally distributed.
We start with Chapter 20, where we study empirical job size distributions from computing workloads. These are often characterized by heavy tails, very high variance, and decreasing failure rate. Importantly, these are very different from the Markovian (Exponential) distributions that have enabled the Markov-chain-based analysis that we have done so far.
New distributions require new analysis techniques. The first of these, the method of phase-type distributions, is introduced in Chapter 21. Phase-type distributions allow us to represent general distributions as mixtures of Exponential distributions. This in turn enables the modeling of systems involving general distributions using Markov chains. However, the resulting Markov chains are very different from what we have seen before and often have no simple solution. We introduce matrix-analytic techniques for solving these chains numerically. Matrix-analytic techniques are very powerful. They are efficient and highly accurate. Unfortunately, they are still numerical techniques, meaning that they can only solve “instances” of the problem, rather than solving the problem symbolically in terms of the input variables.
In Chapter 22 we consider a new setting: networks of Processor-Sharing (PS) servers with generally distributed job sizes. These represent networks of computers, where each computer time-shares among several jobs. We again exploit the idea of phasetype distributions to analyze these networks, proving the BCMP product form theorem for networks with PS servers. The BCMP theorem provides a simple closed-form solution for a very broad class of networks of PS servers.
pp. i-vi
pp. vii-xvi
pp. xvii-xxii
pp. xxiii-xxiv
I - Introduction to Queueing: Read PDF
pp. 1-2
1 - Motivating Examples of the Power of Analytical Modeling: Read PDF
pp. 3-12
2 - Queueing Theory Terminology: Read PDF
pp. 13-28
II - Necessary Probability Background: Read PDF
pp. 29-30
3 - Probability Review: Read PDF
pp. 31-69
4 - Generating Random Variables for Simulation: Read PDF
pp. 70-78
5 - Sample Paths, Convergence, and Averages: Read PDF
pp. 79-92
III - The Predictive Power of Simple Operational Laws: “What-If” Questions and Answers: Read PDF
pp. 93-94
6 - Little's Law and Other Operational Laws: Read PDF
pp. 95-113
7 - Modification Analysis: “What-If” for Closed Systems: Read PDF
pp. 114-126
IV - From Markov Chains to Simple Queues: Read PDF
pp. 127-128
8 - Discrete-Time Markov Chains: Read PDF
pp. 129-147
9 - Ergodicity Theory: Read PDF
pp. 148-189
10 - Real-World Examples: Google, Aloha, and Harder Chains: Read PDF
pp. 190-205
11 - Exponential Distribution and the Poisson Process: Read PDF
pp. 206-224
12 - Transition to Continuous-Time Markov Chains: Read PDF
pp. 225-235
13 - M/M/1 and PASTA: Read PDF
pp. 236-250
V - Server Farms and Networks: Multi-server, Multi-queue Systems: Read PDF
pp. 251-252
14 - Server Farms: M/M/k and M/M/k/k: Read PDF
pp. 253-268
15 - Capacity Provisioning for Server Farms: Read PDF
pp. 269-281
16 - Time-Reversibility and Burke's Theorem: Read PDF
pp. 282-296
17 - Networks of Queues and Jackson Product Form: Read PDF
pp. 297-310
18 - Classed Network of Queues: Read PDF
pp. 311-330
19 - Closed Networks of Queues: Read PDF
pp. 331-346
VI - Real-World Workloads: High Variability and Heavy Tails: Read PDF
pp. 347-348
20 - Tales of Tails: A Case Study of Real-World Workloads: Read PDF
pp. 349-358
21 - Phase-Type Distributions and Matrix-Analytic Methods: Read PDF
pp. 359-379
22 - Networks with Time-Sharing (PS) Servers (BCMP): Read PDF
pp. 380-394
23 - The M/G/1 Queue and the Inspection Paradox: Read PDF
pp. 395-407
24 - Task Assignment Policies for Server Farms: Read PDF
pp. 408-432
25 - Transform Analysis: Read PDF
pp. 433-449
26 - M/G/1 Transform Analysis: Read PDF
pp. 450-456
27 - Power Optimization Application: Read PDF
pp. 457-470
VII - Smart Scheduling in the M/G/1: Read PDF
pp. 471-472
28 - Performance Metrics: Read PDF
pp. 473-477
29 - Scheduling: Non-Preemptive, Non-Size-Based Policies: Read PDF
pp. 478-481
30 - Scheduling: Preemptive, Non-Size-Based Policies: Read PDF
pp. 482-498
31 - Scheduling: Non-Preemptive, Size-Based Policies: Read PDF
pp. 499-507
32 - Scheduling: Preemptive, Size-Based Policies: Read PDF
pp. 508-517
33 - Scheduling: SRPT and Fairness: Read PDF
pp. 518-530
pp. 531-540
pp. 541-548