A summary of research interests and accomplishments (September 2003)
Analysis of Cycle Stealing  We have been working on modeling and analysis of systems with cycle stealing, where two independent processors serve their own workload, but one of the processors (donor) can help the other processor with its jobs during times when the donor processor is idle. We have studied this problem under various settings: preemptive or non-preemptive, immediate dispatch or central queue, with or without threshold constraint, and with or without switching cost. With elaborate modeling, we successfully applied the matrix analytic method to these problems. Analysis was validated via simulation. Results of the analysis illuminate several interesting principles with respect to the general benefits of cycle stealing and the design of cycle stealing policies. Papers on this research was  presented at the SIGMETRICS 2003, ICDCS 2003, and SPAA 2003 [ICDCS03,SIGMETRICS03,SPAA03].
Approximating general distributions by PH distributions  A fundamental question came up through the study of cycle stealing systems.  Which distributions can be well-represented by an n-phase PH distribution in the sense that the first three moments are matched, and how can we find the minimal PT distribution that well-represents a given distribution? We formally characterized the set of distributions G which are well-represented by an n-phase PH distribution, in the sense that the Coxian distribution matches the first three moments of G. We also proposed an algorithm for mapping a general distribution G to a phase type (PH) distribution so that the PH distribution matches the first three moments of G. Since efficiency of the algorithm is of primary importance, we first defined a particular subset of the PH distributions, which we refer to as EC distributions. The class of EC distributions has very few free parameters, which narrows down the search space, making the algorithm efficient --- In fact we provided a closed-form solution for the parameters of the EC distribution. Our solution is general in that it applies to any distribution whose first three moments can be matched by a PH distribution. Also, our resulting EC distribution requires a nearly minimal number of phases, always within one of the minimal number of phases required by any PH distribution.  Papers on this research were presented at Performance TOOLS 2003 [TOOLS03a,TOOLS03b].


Modeling TCP  We have also applied the method of phase type distributions to modeling performance of TCP (transmission control protocol),  The sending rate of TCP sources is modeled by a Markov chain, and it was used in a framework of fixed point method, which allows us to predict both the throughput of the senders and  the loss rate of the network.  Our model overcomes two major limitations of other TCP models.  First, our model is the first model of TCP-Vegas that accurately predicts the operating point of the network; i.e., it predicts both the throughput and the loss rate of TCP sources.  Second, our model is the first model of TCP-Vegas for arbitrary on-off traffic; all previous work on modeling TCP-Vegas is based on the analysis of TCP-Vegas for bulk transfers.  A paper on this research is to be presented at MASCOTS 2003 [MASCOTS 2003], and we are currently further extending this research.

Currently, my primary research interest is the analysis of performance of systems with multiservers and systems with load alternating between overload and low load.
Takayuki Osogami
Department of Computer Science
Carnegie Mellon University