Taka Osogami, Ph.D
Department of Computer ScienceCarnegie Mellon University
5000 Forbes Avenue
Pittsburgh, PA 15213
Office: Wean Hall 7203
Email:
@cs.cmu.eduAdviser: Mor Harchol-Balter
| |
Taka Osogami, Ph.DDepartment of Computer ScienceCarnegie Mellon University 5000 Forbes Avenue Pittsburgh, PA 15213 Office: Wean Hall 7203 Email:
@cs.cmu.eduAdviser: Mor Harchol-Balter |
The analysis of stochastic processes is often difficult, and my research provides useful tools in the analysis of stochastic processes.
We have proposed an algorithm to approximate a general probability distribution by a phase type (PH) distribution. This enables us to approximate a general stochastic process by a Markov chain, which is much more analytically tractable. <See [PE04c], [TOOLS03b], [TOOLS03a]>
However, not all Markov chains can be analyzed efficiently. Researchers have developed efficient analytical methods for a class of Markov chains called quasi-birth-and-death (QBD) processes. We have proposed a new analytical method for analyzing a much broader class of Markov chains called recursive foreground-background QBD (RFBQBD) processes. In fact, we approximate (but nearly exact) an RFBQBD process by a QBD process. We refer to this analytical approach for the RFBQBD process by recursively dimensionality reduction (RDR), since it reduces an n-dimensionally infinite process (RFBQBD process) by a 1-D infinite process (QBD process). <See [RDR04], [MAMA04]>
The new analytical tools allow us to investigate the performance of interesting scheduling policies in computer/communication and service operation systems. For example, we have evaluated the performance of new task assignment policies (task assignment with cycle stealing), and we have evaluated the effectiveness of priority and threshold-based scheduling policies in multiserver systems. <See [PE04a], [SIGMETRICS03], [SPAA03], [ICDCS03], [RDR03a], [RDR03a]>
The lessons that we have learned through the performance analysis of various scheduling policies in simple (e.g., Markovian) models turn out to be quite useful in designing good scheduling policies in real world systems. For example, we provide guidelines for designing good scheduling policies in a call center, based on the analytical study of the performance of various scheduling policies in a simple call center model. Our trace driven simulation shows that the call center can reduce the mean response time by orders of magnitude by following our guidelines. <See [ALLERTON04]>
(as of December 2004)