Efnisyfirlit

• Cover
• Half Title
• Title Page
• Copyright
• Dedication
• Epigraph
• Table of Contents
• Preface
• Acknowledgments
• I Introduction to Queueing
• 1 Motivating Examples of the Power of Analytical Modeling
• 1.1 What Is Queueing Theory?
• 1.2 Examples of the Power of Queueing Theory
• 2 Queueing Theory Terminology
• 2.1 Where We Are Heading
• 2.2 The Single-Server Network
• 2.3 Classification of Queueing Networks
• 2.4 Open Networks
• 2.5 More Metrics: Throughput and Utilization
• 2.6 Closed Networks
• 2.6.1 Interactive (Terminal-Driven) Systems
• 2.6.2 Batch Systems
• 2.6.3 Throughput in a Closed System
• 2.7 Differences between Closed and Open Networks
• 2.7.1 A Question on Modeling
• 2.8 Related Readings
• 2.9 Exercises
• II Necessary Probability Background
• 3 Probability Review
• 3.1 Sample Space and Events
• 3.2 Probability Defined on Events
• 3.3 Conditional Probabilities on Events
• 3.4 Independent Events and Conditionally Independent Events
• 3.5 Law of Total Probability
• 3.6 Bayes Law
• 3.7 Discrete versus Continuous Random Variables
• 3.8 Probabilities and Densities
• 3.8.1 Discrete: Probability Mass Function
• 3.8.2 Continuous: Probability Density Function
• 3.9 Expectation and Variance
• 3.10 Joint Probabilities and Independence
• 3.11 Conditional Probabilities and Expectations
• 3.12 Probabilities and Expectations via Conditioning
• 3.13 Linearity of Expectation
• 3.14 Normal Distribution
• 3.14.1 Linear Transformation Property
• 3.14.2 Central Limit Theorem
• 3.15 Sum of a Random Number of Random Variables
• 3.16 Exercises
• 4 Generating Random Variables for Simulation
• 4.1 Inverse-Transform Method
• 4.1.1 The Continuous Case
• 4.1.2 The Discrete Case
• 4.2 Accept-Reject Method
• 4.2.1 Discrete Case
• 4.2.2 Continuous Case
• 4.2.3 Some Harder Problems
• 4.3 Readings
• 4.4 Exercises
• 5 Sample Paths, Convergence, and Averages
• 5.1 Convergence
• 5.2 Strong and Weak Laws of Large Numbers
• 5.3 Time Average versus Ensemble Average
• 5.3.1 Motivation
• 5.3.2 Definition
• 5.3.3 Interpretation
• 5.3.4 Equivalence
• 5.3.5 Simulation
• 5.3.6 Average Time in System
• 5.4 Related Readings
• 5.5 Exercise
• III The Predictive Power of Simple Operational Laws: “What-If” Questions and Answers
• 6 Little’s Law and Other Operational Laws
• 6.1 Little’s Law for Open Systems
• 6.2 Intuitions
• 6.3 Little’s Law for Closed Systems
• 6.4 Proof of Little’s Law for Open Systems
• 6.4.1 Statement via Time Averages
• 6.4.2 Proof
• 6.4.3 Corollaries
• 6.5 Proof of Little’s Law for Closed Systems
• 6.5.1 Statement via Time Averages
• 6.5.2 Proof
• 6.6 Generalized Little’s Law
• 6.7 Examples Applying Little’s Law
• 6.8 More Operational Laws: The Forced Flow Law
• 6.9 Combining Operational Laws
• 6.10 Device Demands
• 6.11 Readings and Further Topics Related to Little’s Law
• 6.12 Exercises
• 7 Modification Analysis: “What-If” for Closed Systems
• 7.1 Review
• 7.2 Asymptotic Bounds for Closed Systems
• 7.3 Modification Analysis for Closed Systems
• 7.4 More Modification Analysis Examples
• 7.5 Comparison of Closed and Open Networks
• 7.6 Readings
• 7.7 Exercises
• IV From Markov Chains to Simple Queues
• 8 Discrete-Time Markov Chains
• 8.1 Discrete-Time versus Continuous-Time Markov Chains
• 8.2 Definition of a DTMC
• 8.3 Examples of Finite-State DTMCs
• 8.3.1 Repair Facility Problem
• 8.3.2 Umbrella Problem
• 8.3.3 Program Analysis Problem
• 8.4 Powers of P: n-Step Transition Probabilities
• 8.5 Stationary Equations
• 8.6 The Stationary Distribution Equals the Limiting Distribution
• 8.7 Examples of Solving Stationary Equations
• 8.7.1 Repair Facility Problem with Cost
• 8.7.2 Umbrella Problem
• 8.8 Infinite-State DTMCs
• 8.9 Infinite-State Stationarity Result
• 8.10 Solving Stationary Equations in Infinite-State DTMCs
• 8.11 Exercises
• 9 Ergodicity Theory
• 9.1 Ergodicity Questions
• 9.2 Finite-State DTMCs
• 9.2.1 Existence of the Limiting Distribution
• 9.2.2 Mean Time between Visits to a State
• 9.2.3 Time Averages
• 9.3 Infinite-State Markov Chains
• 9.3.1 Recurrent versus Transient
• 9.3.2 Infinite Random Walk Example
• 9.3.3 Positive Recurrent versus Null Recurrent
• 9.4 Ergodic Theorem of Markov Chains
• 9.5 Time Averages
• 9.6 Limiting Probabilities Interpreted as Rates
• 9.7 Time-Reversibility Theorem
• 9.8 When Chains Are Periodic or Not Irreducible
• 9.8.1 Periodic Chains
• 9.8.2 Chains that Are Not Irreducible
• 9.9 Conclusion
• 9.10 Proof of Ergodic Theorem of Markov Chains*
• 9.11 Exercises
• 10 Real-World Examples: Google, Aloha, and Harder Chains*
• 10.1 Google’s PageRank Algorithm
• 10.1.1 Google’s DTMC Algorithm
• 10.1.2 Problems with Real Web Graphs
• 10.1.3 Google’s Solution to Dead Ends and Spider Traps
• 10.1.4 Evaluation of the PageRank Algorithm
• 10.1.5 Practical Implementation Considerations
• 10.2 Aloha Protocol Analysis
• 10.2.1 The Slotted Aloha Protocol
• 10.2.2 The Aloha Markov Chain
• 10.2.3 Properties of the Aloha Markov Chain
• 10.2.4 Improving the Aloha Protocol
• 10.3 Generating Functions for Harder Markov Chains
• 10.3.1 The z-Transform
• 10.3.2 Solving the Chain
• 10.4 Readings and Summary
• 10.5 Exercises
• 11 Exponential Distribution and the Poisson Process
• 11.1 Definition of the Exponential Distribution
• 11.2 Memoryless Property of the Exponential
• 11.3 Relating Exponential to Geometric via δ-Steps
• 11.4 More Properties of the Exponential
• 11.5 The Celebrated Poisson Process
• 11.6 Merging Independent Poisson Processes
• 11.7 Poisson Splitting
• 11.8 Uniformity
• 11.9 Exercises
• 12 Transition to Continuous-Time Markov Chains
• 12.1 Defining CTMCs
• 12.2 Solving CTMCs
• 12.3 Generalization and Interpretation
• 12.3.1 Interpreting the Balance Equations for the CTMC
• 12.3.2 Summary Theorem for CTMCs
• 12.4 Exercises
• 13 M/M/1 and PASTA
• 13.1 The M/M/1 Queue
• 13.2 Examples Using an M/M/1 Queue
• 13.3 PASTA
• 13.4 Further Reading
• 13.5 Exercises
• V Server Farms and Networks: Multi-server, Multi-queue Systems
• 14 Server Farms: M/M/k and M/M/k/k
• 14.1 Time-Reversibility for CTMCs
• 14.2 M/M/k/k Loss System
• 14.3 M/M/k
• 14.4 Comparison of Three Server Organizations
• 14.5 Readings
• 14.6 Exercises
• 15 Capacity Provisioning for Server Farms
• 15.1 What Does Load Really Mean in an M/M/k?
• 15.2 The M/M/∞
• 15.2.1 Analysis of the M/M/∞
• 15.2.2 A First Cut at a Capacity Provisioning Rule for the M/M/k
• 15.3 Square-Root Staffing
• 15.4 Readings
• 15.5 Exercises
• 16 Time-Reversibility and Burke’s Theorem
• 16.1 More Examples of Finite-State CTMCs
• 16.1.1 Networks with Finite Buffer Space
• 16.1.2 Batch System with M/M/2 I/O
• 16.2 The Reverse Chain
• 16.3 Burke’s Theorem
• 16.4 An Alternative (Partial) Proof of Burke’s Theorem
• 16.5 Application: Tandem Servers
• 16.6 General Acyclic Networks with Probabilistic Routing
• 16.7 Readings
• 16.8 Exercises
• 17 Networks of Queues and Jackson Product Form
• 17.1 Jackson Network Definition
• 17.2 The Arrival Process into Each Server
• 17.3 Solving the Jackson Network
• 17.4 The Local Balance Approach
• 17.5 Readings
• 17.6 Exercises
• 18 Classed Network of Queues
• 18.1 Overview
• 18.2 Motivation for Classed Networks
• 18.3 Notation and Modeling for Classed Jackson Networks
• 18.4 A Single-Server Classed Network
• 18.5 Product Form Theorems
• 18.6 Examples Using Classed Networks
• 18.6.1 Connection-Oriented ATM Network Example
• 18.6.2 Distribution of Job Classes Example
• 18.6.3 CPU-Bound and I/O-Bound Jobs Example
• 18.7 Readings
• 18.8 Exercises
• 19 Closed Networks of Queues
• 19.1 Motivation
• 19.2 Product-Form Solution
• 19.2.1 Local Balance Equations for Closed Networks
• 19.2.2 Example of Deriving Limiting Probabilities
• 19.3 Mean Value Analysis (MVA)
• 19.3.1 The Arrival Theorem
• 19.3.2 Iterative Derivation of Mean Response Time
• 19.3.3 An MVA Example
• 19.4 Readings
• 19.5 Exercises
• VI Real-World Workloads: High Variability and Heavy Tails
• 20 Tales of Tails: A Case Study of Real-World Workloads
• 20.1 Grad School Tales … Process Migration
• 20.2 UNIX Process Lifetime Measurements
• 20.3 Properties of the Pareto Distribution
• 20.4 The Bounded Pareto Distribution
• 20.5 Heavy Tails
• 20.6 The Benefits of Active Process Migration
• 20.7 Pareto Distributions Are Everywhere
• 20.8 Exercises
• 21 Phase-Type Distributions and Matrix-Analytic Methods
• 21.1 Representing General Distributions by Exponentials
• 21.2 Markov Chain Modeling of PH Workloads
• 21.3 The Matrix-Analytic Method
• 21.4 Analysis of Time-Varying Load
• 21.4.1 High-Level Ideas
• 21.4.2 The Generator Matrix, Q
• 21.4.3 Solving for R
• 21.4.4 Finding
• 21.4.5 Performance Metrics
• 21.5 More Complex Chains
• 21.6 Readings and Further Remarks
• 21.7 Exercises
• 22 Networks with Time-Sharing (PS) Servers (BCMP)
• 22.1 Review of Product-Form Networks
• 22.2 BCMP Result
• 22.2.1 Networks with FCFS Servers
• 22.2.2 Networks with PS Servers
• 22.3 M/M/1/PS
• 22.4 M/Cox/1/PS
• 22.5 Tandem Network of M/G/1/PS Servers
• 22.6 Network of PS Servers with Probabilistic Routing
• 22.7 Readings
• 22.8 Exercises
• 23 The M/G/1 Queue and the Inspection Paradox
• 23.1 The Inspection Paradox
• 23.2 The M/G/1 Queue and Its Analysis
• 23.3 Renewal-Reward Theory
• 23.4 Applying Renewal-Reward to Get Expected Excess
• 23.5 Back to the Inspection Paradox
• 23.6 Back to the M/G/1 Queue
• 23.7 Exercises
• 24 Task Assignment Policies for Server Farms
• 24.1 Task Assignment for FCFS Server Farms
• 24.2 Task Assignment for PS Server Farms
• 24.3 Optimal Server Farm Design
• 24.4 Readings and Further Follow-Up
• 24.5 Exercises
• 25 Transform Analysis
• 25.1 Definitions of Transforms and Some Examples
• 25.2 Getting Moments from Transforms: Peeling the Onion
• 25.3 Linearity of Transforms
• 25.4 Conditioning
• 25.5 Distribution of Response Time in an M/M/1
• 25.6 Combining Laplace and z-Transforms
• 25.7 More Results on Transforms
• 25.8 Readings
• 25.9 Exercises
• 26 M/G/1 Transform Analysis
• 26.1 The z-Transform of the Number in System
• 26.2 The Laplace Transform of Time in System
• 26.3 Readings
• 26.4 Exercises
• 27 Power Optimization Application
• 27.1 The Power Optimization Problem
• 27.2 Busy Period Analysis of M/G/1
• 27.3 M/G/1 with Setup Cost
• 27.4 Comparing ON/IDLE versus ON/OFF
• 27.5 Readings
• 27.6 Exercises
• VII Smart Scheduling in the M/G/1
• 28 Performance Metrics
• 28.1 Traditional Metrics
• 28.2 Commonly Used Metrics for Single Queues
• 28.3 Today’s Trendy Metrics
• 28.4 Starvation/Fairness Metrics
• 28.5 Deriving Performance Metrics
• 28.6 Readings
• 29 Scheduling: Non-Preemptive, Non-Size-Based Policies
• 29.1 FCFS, LCFS, and RANDOM
• 29.2 Readings
• 29.3 Exercises
• 30 Scheduling: Preemptive, Non-Size-Based Policies
• 30.1 Processor-Sharing (PS)
• 30.1.1 Motivation behind PS
• 30.1.2 Ages of Jobs in the M/G/1/PS System
• 30.1.3 Response Time as a Function of Job Size
• 30.1.4 Intuition for PS Results
• 30.1.5 Implications of PS Results for Understanding FCFS
• 30.2 Preemptive-LCFS
• 30.3 FB Scheduling
• 30.4 Readings
• 30.5 Exercises
• 31 Scheduling: Non-Preemptive, Size-Based Policies
• 31.1 Priority Queueing
• 31.2 Non-Preemptive Priority
• 31.3 Shortest-Job-First (SJF)
• 31.4 The Problem with Non-Preemptive Policies
• 31.5 Exercises
• 32 Scheduling: Preemptive, Size-Based Policies
• 32.1 Motivation
• 32.2 Preemptive Priority Queueing
• 32.3 Preemptive-Shortest-Job-First (PSJF)
• 32.4 Transform Analysis of PSJF
• 32.5 Exercises
• 33 Scheduling: SRPT and Fairness
• 33.1 Shortest-Remaining-Processing-Time (SRPT)
• 33.2 Precise Derivation of SRPT Waiting Time*
• 33.3 Comparisons with Other Policies
• 33.3.1 Comparison with PSJF
• 33.3.2 SRPT versus FB
• 33.3.3 Comparison of All Scheduling Policies
• 33.4 Fairness of SRPT
• 33.5 Readings
• Bibliography
• Index