Asymptotic buffer overflow probabilities in multiclass multiplexers: an optimal control approach

• Published in: IEEE transactions on automatic control 1998-03, Vol.43 (3), p.315-335
• Main Authors: Bertsimas, D., Paschalidis, I.C., Tsitsiklis, J.N.
• Format: Article
• Language: English
• Subjects: Applied sciences; Bandwidth; Buffer overflow; Communication system traffic control; Exact sciences and technology; Global Positioning System; H infinity control; Multiplexing; Optimal control; Systems, networks and services of telecommunications; Tail; Telecommunications; Telecommunications and information theory; Teletraffic; Traffic control; Upper bound
• ISSN: 0018-9286; 1558-2523
• DOI: 10.1109/9.661587

We consider a multiclass multiplexer with support for multiple service classes and dedicated buffers for each service class. Under specific scheduling policies for sharing bandwidth among these classes, we seek the asymptotic (as the buffer size goes to infinity) tail of the buffer overflow probability for each dedicated buffer. We assume dependent arrival and service processes as is usually the case in models of bursty traffic. 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 introduce a novel optimal control approach to address these problems. In particular, we relate the lower bound derivation to a deterministic optimal control problem, which we explicitly solve. Optimal state trajectories of the control problem correspond to typical congestion scenarios. We explicitly and in detail characterize the most likely modes of overflow. We specialize our results to the generalized processor sharing policy (GPS) and the generalized longest queue first policy (GLQF). The performance of strict priority policies is obtained as a corollary. We compare the GPS and GLQF policies and conclude that GLQF achieves smaller overflow probabilities than GPS for all arrival and service processes for which our analysis holds. Our results have important implications for traffic management of high-speed networks and can be used as a basis for an admission control mechanism which guarantees a different loss probability for each class.