On fast simulation techniques for queueing systems.

摘要

Communication networks have experienced dramatic growth in all dimensions: size, speed and heterogeneity etc. This poses great challenges to network modeling and performance evaluation. Various schemes have been trades off simulation fidelity for speedup. In this dissertation, we investigate simulation by utilizing special properties of queueing systems.; First we describe low and high resolution models of a simple queue via Poisson Driven Stochastic Differential Equations. Explicit formulas of evaluation errors are obtained, by which we identify the impacts of different traffic components and the utilization of the queue.; It is not new to simulate networks at a burst scale. For example, a cluster of closely spaced packets are modeled as a fluid chunk with a constant rate. In previous studies, the loss of accuracy is mainly assessed by experiments. There are fewer researches on quantitative characterization of simulation errors. We obtain error formulas for a specific queueing system. By that, we identify the occurrence of queue empty periods as a major contributor to the degradation of accuracy. This provides further understanding of the impacts of source traffic and queueing systems on the error.; Time stepped simulation (TSS) has been proposed to deal with the scalability issue encountered by event-driven fluid simulation and packet-level discrete event simulation. The systematic investigation on simulation errors is rather modest. We study the impacts of traffic short-term and long-term burstiness on the errors and show that the accuracy of TSS is related to traffic properties and system loads. In order to obtain tolerable degradation for a wider range of utilizations, we propose compensated TSS (CTSS). We also discuss the effect of traffic long-term burstiness and system load on the accuracy of TSS in capturing queue outputs, and briefly study TCP networks.; Motivated by simulation speedup, we explore decomposition phenomena in queueing systems. The original queue is converted to a new system, where a fast simulation can be applied. We prove the equivalence of the mean queue length of the two systems under certain circumstances.