Multiscale Queuing Analysis
Ribeiro, Vinay Joseph
Riedi, Rudolf H.
Baraniuk, Richard G.
queuing; long range dependence; multiscale; trees; wavelets; critical time scale; time scale
We develop a new approach to queuing analysis for an infinite-length queue with constant service rate fed by an arbitrary traffic process. Our approach is particularly relevant to queues fed with long-range-dependent (LRD) traffic. We use traffic statistics at only a small fixed set of time scales and develop three approximations for the tail queue probability that are easy to implement in practice. These are non-asymptotic, that is they apply to any finite queue threshold. Simulations with LRD traffic models and Internet traces demonstrate their accuracy. Besides non-asymptotic error bounds and asymptotic decay rates for the approximations, we prove an optimality property of exponential time scales. Simulations reveal that the second-order correlation structure of traffic by itself does not determine queuing behavior and that the tails of traffic marginals at different time scales have a strong impact on queuing.