Large deviations analysis of the generalized processor sharing policy

In this paper we consider a stochastic server (modeling a multiclass commun ication switch) fed by a set of parallel buffers. The dynamics of the syste m evolve in discrete-time and the generalized processor sharing (GPS) sched uling policy of [25] is implemented. The arrival process in each buffer is an arbitrary, and possibly autocorrelated, stochastic process. We obtain a large deviations asymptotic for the buffer overflow probability at each buf fer. In the standard large deviations methodology, we provide a lower and a matching (up to first degree in the exponent) upper bound on the buffer ov erflow probabilities. We view the problem of finding a most likely sample p ath that leads to an overflow as an optimal control problem. Using ideas fr om convex optimization we analytically solve the control problem to obtain both the asymptotic exponent of the overflow probability and a characteriza tion of most likely modes of overflow. These results have important implica tions for traffic management of high-speed networks. They extend the determ inistic, worst-case analysis of [25] to the case where a detailed statistic al model of the input traffic is available and can be used as a basis for a n admission control mechanism.