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.029
Subjects: Computer Hardware, Architecture and Distributed Computing, Applied probability and stochastic networks
Image View Extract Fullview: Text View | Enlarge Image ‹ Previous Chapter ›Next Chapter
In Chapter 21, we saw one application for phase-type (PH) distributions: If we need to analyze a system whose workload involves distributions that are non-Exponential (e.g., high-variability workloads), then we can use a PH distribution to at least match 2 or 3 moments of that workload distribution. This allows us to represent the system via a Markov chain, which we can often solve via matrix-analytic methods.
In this chapter we see another application of PH distributions. Here, we are interested in analyzing networks of Processor-Sharing (time-sharing) servers (a.k.a. PS servers). It will turn out that networks of PS servers exhibit product form solutions, even under general service times. This is in contrast to networks of FCFS servers, which require Exponential service times. Our proof of this PS result will rely on phase-type distributions. This result is part of the famous BCMP theorem [16].
Review of Product Form Networks
So far we have seen that all of the following networks have product form:
We have also seen (see Exercise 19.3) that Jackson networks with load-dependent service rates have product form. Here the service rate can depend on the number of jobs at the server. This is useful for modeling the effects of parallel processing.
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
No references available.