Many-Sources Large Deviations for Max-Weight Scheduling

DOI10.1109/TIT.2011.2110850zbMATH Open1366.90110arXiv0902.4569MaRDI QIDQ5280975FDOQ5280975

Authors: Vijay Subramanian, Tara Javidi, Somsak Kittipiyakul 

Publication date: 27 July 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: In this paper, a many-sources large deviations principle (LDP) for the transient workload of a multi-queue single-server system is established where the service rates are chosen from a compact, convex and coordinate-convex rate region and where the service discipline is the max-weight policy. Under the assumption that the arrival processes satisfy a many-sources LDP, this is accomplished by employing Garcia's extended contraction principle that is applicable to quasi-continuous mappings. For the simplex rate-region, an LDP for the stationary workload is also established under the additional requirements that the scheduling policy be work-conserving and that the arrival processes satisfy certain mixing conditions. The LDP results can be used to calculate asymptotic buffer overflow probabilities accounting for the multiplexing gain, when the arrival process is an average of emph{i.i.d.} processes. The rate function for the stationary workload is expressed in term of the rate functions of the finite-horizon workloads when the arrival processes have emph{i.i.d.} increments.

Full work available at URL: https://arxiv.org/abs/0902.4569

Mathematics Subject Classification ID

Applications of statistics in engineering and industry; control charts (62P30) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Stochastic scheduling theory in operations research (90B36)

This page was built for publication: Many-Sources Large Deviations for Max-Weight Scheduling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5280975)