Large Deviation Methods for QoS Guarantee in Commmunication Networks

Nowadays real-time multimedia applications such as IP telephony, voice over IP and IP-TV become more and more widespread. These applications impose strict limits on delay and packet dropping probability. In other words, a certain level of quality of service (QoS) should be guaranteed. Obviously, in absence of network congestion, QoS mechanism is not required, but if the network capacity is insucient, QoS guarantees turn out to be very important. The Large Deviation Theory (LDT) deals with rare events probabilities. By classical theory, rare event probability converges to zero (as a rarity parameter goes to a limit), and LDT allows usually to the rate of the convergence. LDT shows that in typical situations rare event probability turn out to have exponential form, and moreover gives an approach to calculate required exponent.

The main advantage of LDT is its generality and applicability to a wide class of queueing systems describing real-life communication networks. LDT methods allow to answer some questions about QoS in computer networks. For instance, how much would be loss-ratio for given bandwidth and bur size? Which ective bandwidth guarantees the loss-ratio is less than a given level? What is the probability that (stationary) waiting time exceeds a given (high) value?

It is important to note that LDT methods are asymptotic and by this reason can be applied to rather complicated systems that are dicult to be investigated by pure analytical methods. Moreover LDT approach allows to calculate estimators of QoS parameters using experimental data describing input ow.

In the present talk, we discuss above mentioned problems with focus on applications of LDT methods to calculation of overow (and related) probabilities.