Large deviations analysis of the generalized processor sharing policy |
| |
Authors: | Bertsimas Dimitris Paschalidis Ioannis Ch Tsitsiklis John N |
| |
Institution: | (1) Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA 02139, USA;(2) Department of Manufacturing Engineering, Boston University, Boston, MA 02215, USA;(3) Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA o02139, USA |
| |
Abstract: | In this paper we consider a stochastic server (modeling a multiclass communication switch) fed by a set of parallel buffers.
The dynamics of the system evolve in discrete-time and the generalized processor sharing (GPS) scheduling 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 buffer. 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 overflow probabilities. We
view the problem of finding a most likely sample path that leads to an overflow as an optimal control problem. Using ideas
from convex optimization we analytically solve the control problem to obtain both the asymptotic exponent of the overflow
probability and a characterization of most likely modes of overflow. These results have important implications for traffic
management of high-speed networks. They extend the deterministic, worst-case analysis of 25] to the case where a detailed
statistical model of the input traffic is available and can be used as a basis for an admission control mechanism.
This revised version was published online in June 2006 with corrections to the Cover Date. |
| |
Keywords: | large deviations communication networks |
本文献已被 SpringerLink 等数据库收录! |
|