Fast simulation of queues with long-range dependent traffic

Self-similar stochastic processes have been proposed as more accurate models of certain categories of traffic (e.g., Ethernet traffic, variable-bit-rate video). Analytical and simulation approaches applicable to traditional traffic models may not be applicable to these categories of traffic due to their long range dependence. Existing analytical results for the tail distribution of the waiting time in a single server queue based on Fractional Gaussian Noise and large deviation theory, are valid under a steady-state regime and for asymptotically large buffer sizes. Predicted performance based on steady-state regimes may be overly pessimistic for practical applications. Analytical approaches to obtain transient queueing behavior and queueing distributions for small buffer sizes become quickly intractable. In this paper, we develop a fast simulation approach based on importance sampling that we use to simulate the queueing behavior of self-similar processes in a multiplexer, including the estimation of very low cell-loss probabilities. We describe two heuristic approaches – a simpler one, as well as a second heuristic approach, inspired by asymptotically efficient simulation of general Gaussian processes. Our simulation experiments provide insight on transient behavior that is not possible to predict using current analytical results. Finally, our simulations show good agreement with existing results when approaching steady-state.