Thesis

Takayuki Osogami, Analysis of multiserver systems via dimensionality reduction of Markov chains, Ph.D. thesis, School of Computer Science, Carnegie Mellon University, June 2005.

Thesis summary

Analysis of Multi-server Systems via Dimensionality Reduction of Markov Chains

Takayuki Osogami

June, 2005

School of Computer Science

Carnegie Mellon University

Pittsburgh, PA 15213

Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy

Thesis: PDF

Committee members

Abstract

The performance analysis of multiserver systems is notoriously hard, especially when the system involves resource sharing or prioritization. We provide two new analytical tools for the performance analysis of multiserver systems: moment matching algorithms and dimensionality reduction of Markov chains (DR).

Moment matching algorithms allow us to approximate a general distribution with a phase type (PH) distribution. Our moment matching algorithms improve upon existing ones with respect to the computational efficiency (we provide closed form solutions) as well as the quality and generality of the solution (the first three moments of almost any nonnegative distribution are matched). Approximating job size and interarrival time distributions by PH distributions enables modeling a multiserver system by a Markov chain, so that the performance of the system is given by analyzing the Markov chain. However, when the multiserver system involves resource sharing or prioritization, the Markov chain often has a multidimensionally infinite state space, which makes the analysis computationally hard.

DR allows us to closely approximate a multidimensionally infinite Markov chain with a Markov chain on a one-dimensionally infinite state space, which can be analyzed efficiently. We validate the accuracy of DR against simulation. Further, we formally define two classes of multidimensionally infinite Markov chains, called recursive foreground-background processes and generalized foreground-background processes (RFB/GFB processes), and analyze the RFB/GFB process via DR. The definition of the RFB/GFB process enables one to easily identify whether a given multiserver system can be analyzed via DR, and our analysis of the RFB/GFB process enables the immediate analysis of a multiserver system by simply modeling it as an RFB/GFB process.

These new analytical tools enable us to analyze the performance of many multiserver systems with resource sharing or prioritization for the first time. For example, we study the benefit and penalty of cycle stealing, the effectiveness of prioritization and threshold-based resource allocation policies for multiserver systems, and the impact of job size variability and irregularity of arrival processes on the response time in multiserver systems. Our analysis results in lessons on the design of good resource allocation policies for multiserver systems.

Keywords

Performance analysis, Multi-server system, Markov chain, Resource allocation, Cycle stealing, Priority, Task assignment, Phase type, Dimensionality reduction, Moment matching.

Contents

1 Introduction

1.1 Motivation

1.2 Dificulty of performance analysis of multiserver systems

1.3 Road map

1.3.1 Synopsis of Part I: Analytical tools for multiserver systems

1.3.2 Synopsis of Part II: Performance analysis of multiserver systems

1.3.3 Synopsis of Part III: Further discussion and conclusion

I Analytical tools for multiserver systems

2 Moment matching algorithm

2.1 Overview

2.1.1 Moment matching algorithms

2.1.2 Characterizing phase type distributions

2.1.3 Organization of this chapter

2.2 Brief tutorial on phase type distributions

2.2.1 Examples of PH distributions

2.2.2 Definition of PH distribution

2.2.3 Subclasses of PH distribution

2.2.4 Properties of PH distributions

2.3 State of the art in moment matching algorithms

2.4 Characterizing phase type distributions

2.5 EC distribution

2.6 Simple closed form solution

2.7 Complete closed form solution

2.8 Positive closed form solution

2.9 Concluding remarks

3 Dimensionality reduction of Markov chains

3.1 Overview

3.1.1 Analysis of priority M/M/2 queue via DR

3.1.2 Analysis of priority M/PH/2 queue via DR

3.1.3 RFB and GFB processes

3.1.4 Organization of this chapter

3.2 Brief tutorial on matrix analytic methods

3.2.1 Quasi-birth-and-death process

3.2.2 Markovian arrival process

3.2.3 Matrix analytic methods

3.3 State of the art in the analysis of multidimensional Markov chains

3.3.1 Approaches using matrix analytic methods

3.3.2 Other approaches

3.4 FB, RFB, and GFB processes

3.4.1 Definition of FB process

3.4.2 Definition of RFB process

3.4.3 Examples of RFB processes

3.4.4 Definition of GFB process

3.4.5 Examples of GFB processes

3.5 Dimensionality reduction

3.5.1 Analysis of the birth-and-death FB process

3.5.2 Analysis of the FB process

3.5.3 Analysis of the RFB process

3.5.4 Analysis of the GFB process

3.5.5 Constructing a 1D Markov chain using an approximate background process

3.6 Approximations of dimensionality reduction

3.6.1 Dimensionality reduction with partial independence assumption

3.6.2 Dimensionality reduction with complete independence assumption

3.6.3 Computational complexity of DR, DR-PI, and DR-CI

3.7 Moments of inter-level passage times in QBD processes

3.7.1 Preliminaries

3.7.2 Moments of passage time

3.7.3 Generalization

3.8 Computing various performance measures

3.8.1 Distribution and moments of the number of jobs in the system

3.8.2 Distribution and moments of response time

3.9 Validation

3.9.1 Accuracy of dimensionality reduction

3.9.2 Running time of dimensionality reduction

3.10 Concluding remarks

II Performance analysis of multiserver systems

4 Configuring multiserver systems with multiple priority classes

4.1 Introduction

4.2 State of the art in the optimal number of servers

4.3 How many servers are best in FCFS system?

4.4 How many servers are best in priority system?

4.5 New approximations for many priority classes

4.5.1 Motivation

4.5.2 Approximations for multiserver systems with multiple priority classes

4.5.3 Comparing DR-A with BB and MK-N

4.6 Concluding remarks

5 Improving traditional task assignment policies

5.1 Task assignment in server farms

5.2 State of the art in task assignment policies

5.3 Task assignment with cycle stealing

5.4 Performance of task assignment with cycle stealing

5.4.1 Summary of results

5.4.2 Stability

5.4.3 Mean response time

5.5 Concluding remarks

6 Reducing switching costs in cycle stealing

6.1 Motivation

6.2 Threshold based policy for reducing switching costs in cycle stealing

6.3 State of the art in cycle stealing

6.4 Results

6.4.1 Summary of results

6.4.2 Stability

6.4.3 Mean response time

6.5 Concluding remarks

7 Designing robust resource allocation policies

7.1 Introduction

7.1.1 Static and dynamic robustness

7.1.2 State of the art in resource allocation policies for the Beneficiary-Donor model

7.1.3 Summary of results

7.2 Static robustness and mean response time of single-threshold allocation policies

7.2.1 Single-threshold allocation policies: T1 and T2

7.2.2 Stability under single-threshold allocation policies

7.2.3 Mean response time of single-threshold allocation policies

7.2.4 Static robustness of single-threshold allocation policies

7.3 Static robustness and mean response time of multi-threshold allocation policies

7.3.1 T1T2 policy

7.3.2 The adaptive dual threshold (ADT) policy

7.4 Dynamic robustness of threshold based policies

7.5 Concluding remarks

III Further discussion and conclusion

8 Applications in contact center design

8.1 Motivation

8.2 Overview of contact center operation

8.3 Towards efficient contact center operation

8.3.1 Overview of contact center management

8.3.2 Capacity planning

8.3.3 Routing policy design

9 Conclusion

9.1 Analytical tools developed

9.2 Lessons learned in the analysis of multiserver systems

9.3 Future directions

A Proofs

B Moment matching algorithm by Bobbio, Horvath, and Telek

C Properties of Markovian arrival processes