| In modern high-speed telecommunication networks, statistical multiplexing of Variable Bit Rate (VBR) sources provides a means of effectively utilizing the network resources without violating the desirable Quality of Service (QoS). QoS is quantified as the maximum allowable fraction of lost or delayed packets. To maintain QoS, a Call Admission Control (CAC) mechanism, which decides whether to admit a new call based on an estimate of the resulting buffer overflow probability, has to be implemented. Large Deviations theory provides useful approximations of the buffer overflow probability for many important classes of arrival processes, provided that an exact stochastic model for the arrival process is known.; In this work, we consider the problem of estimating buffer overflow probabilities when the statistics of the input traffic are not known and have to be estimated from measurements. In this case, a certainty equivalence approach is not adequate, since it can substantially underestimate the overflow probability. We are proposing new estimators for the overflow probability in a queue fed by a Markov-modulated process (MMP) that are less likely to lead to underestimation. To that end, we establish a theorem that can be viewed as an inverse of Sanov's theorem for Markov chains. Computing these new estimators amounts to solving nonlinear programming problems with special structure. We develop some special algorithms that take advantage of this structure to solve these problems more efficiently.; We then address the issue of optimally modeling a generic discrete-time, continuous range stochastic process as an MMP, based on a single, finite realization of the process. We investigate methods for optimal model selection using maximum likelihood techniques, including the Akaike Information Criterion .; Lastly, we develop an importance sampling technique for obtaining small buffer overflow probabilities in a queue fed by a large number of independent periodic sources, via simulation. This traffic model accommodates ON-OFF periodic traffic models and sequences of bit rates generated by actual VBR sources. We devise a heuristic change of measure and demonstrate its efficiency through numerical results. Our method is applicable in both the continuous and the discrete time case as well as for homogeneous and heterogeneous sources. |
