Next:
1. Introduction
1. Introduction
1.1 Contributions
1.2 Organization
2. Background
2.1 Basic notation
2.1.1 Kendall Notation
2.2 Random variables
2.2.1 Exponential distribution
2.2.2 Variations of exponential distribution
2.3 Heavy tailed distributions
2.4 Markov processes
2.4.1 Discrete time Markov chains (DTMCs)
2.4.2 Continuous time Markov chains (CTMCs)
2.5 Markov chains with repetitive structure
2.5.1 Quasi birth-death processes
2.5.2 GI/M/1-type processes
2.5.3 M/G/1-type processes
2.5.4 GI/G/1-type processes
2.6 Phase-type distributions
2.6.1 Fitting algorithms for PH distributions
2.6.1.1 EM Algorithm
2.6.1.2 Feldmann-Whitt (FW) Algorithm
2.7 Markovian Arrival Process
2.7.1 Fitting techniques for MAPs
2.8 Aggregation techniques
2.8.1 Exact aggregation and decomposition
2.8.2 Stochastic complementation
2.9 Chapter summary
3. Matrix-Analytic Methods
3.1 Matrix geometric solutions for GI/M/1-type and QBD processes
3.1.1 Additional measures of interest
3.2 Why does a geometric relation hold for QBD processes?
3.3 Generalization: geometric solution for the GI/M/1 processes
3.4 Why M/G/1 processes are more difficult
3.5 Example: a
queue
3.6 Generalization: derivation of Ramaswami's recursive formula
3.7 General solution of M/G/1-type processes
3.7.1 Ramaswami's formula
3.7.2 Explicit computation of
3.7.3 Fast FFT Ramaswami's formula
3.8 Explicit computation of
for QBDs
3.9 Conditions for stability
3.10 Chapter summary
4. Data Fitting Algorithms
4.1 Long-tailed behavior
4.2 D&C EM
4.2.1 D&C EM experimental results
4.2.1.1 Traces
4.2.1.2 D&C EM statistical analysis
4.2.2 D&C EM queueing system analysis
4.2.3 Computational efficiency of D&C EM
4.2.4 Refined D&C EM fitting algorithm
4.2.4.1 Results with the refined D&C EM
4.3 D&C MM
4.4 MAP fitting algorithm
4.4.1 Hidden Markov model for parameter estimate
4.4.2 Generation of MAP from HMM output
4.4.3 Experimental results
4.4.3.1 Traces
4.4.3.2 Experimental setting
4.4.3.3 Peak Traffic Period (Trace A)
4.4.3.4 Off-Peak Traffic Period (Trace B)
4.4.3.5 Strong Long-Range Dependence (Trace C)
4.5 Chapter summary
5. E
TAQA
Methodology
5.1 E
TAQA
-M/G/1
5.1.1 Computing measures of interest for M/G/1-type processes
5.1.2 Time and storage complexity
5.2 E
TAQA
-GI/M/1
5.2.1 Computing measures of interest for GI/M/1-type processes
5.2.2 Time and storage complexity
5.3 E
TAQA
-QBD
5.3.1 Computing measures of interest for QBD processes
5.3.2 Time and storage complexity
5.4 Computational efficiency
5.5 Numerical stability of the method
5.6 MAMSolver
5.6.1 MAMSolver input and output
5.7 Chapter summary
6. Aggregate Solutions of GI/G/1-type Processes
6.1 Non-disjoint coupling
6.2 Pseudo-stochastic complementation
6.3 GI/G/1 solution (High-level idea)
6.4 GI/G/1 solution - General approach
6.5 Determining the upper and lower sets
6.6 Determining a gate state
6.7 Generation of the new ``upper'' process
6.8 Generation of the new ``lower'' process
6.9 Multiple upper-lower classes
6.10 Application: parallel scheduling in the presence of failures
6.11 Chapter summary
7. Load Balancing on Clustered Web Servers
7.1 Clustered Web servers architectures
7.2 Load balancing policies on clustered Web servers
7.3 World Cup 1998 workload
7.3.1 Fitting request sizes into a distribution
7.3.2 Fittings using FW algorithm
7.4 Sized-based load balancing policy
7.5 E
QUI
L
OAD
7.5.1 Performance of E
QUI
L
OAD
7.5.2 Locality awareness of E
QUI
L
OAD
7.5.3 Behavior of E
QUI
L
OAD
policy in a dynamic environment
7.6 A
DAPT
L
OAD
7.6.1 Transient characteristics of World Cup workload
7.6.2 A
DAPT
L
OAD
: the algorithm
7.6.3 Performance analysis of A
DAPT
L
OAD
7.6.4 A
DAPT
L
OAD
vs. JWSQ
7.6.5 Scalability of A
DAPT
L
OAD
7.6.6 Improving A
DAPT
L
OAD
7.7 Chapter summary
8. Conclusions and future work
8.1 Future directions
A. Feldman-Whitt Fitting Algorithm
B. (B)MAP/PH/1 queues
C. Newton-Raphson Fitting Technique
D. Examples of MAMS
OLVER
input
Bibliography
About this document ...
Alma Riska 2003-01-13
queue
for QBDs
