Logarithmic Heavy Traffic Error Bounds in Generalized Switch and Load Balancing Systems

DOI10.1017/JPR.2021.82MaRDI QIDQ6336911arXivFDO

Authors Daniela Hurtado-Lange, Sushil Mahavir Varma, Siva Theja Maguluri

Publication date 17 March 2020

Published in arXiv

Full work available at URL https://doi.org/10.1017/JPR.2021.82

Mathematics Subject Classification ID

Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Queues and service in operations research (90B22)

arXiv classification

math.OCmath.PR

Abstract: Motivated by application in wireless networks, cloud computing, data centers etc, Stochastic Processing Networks have been studied in the literature under various asymptotic regimes. In the heavy-traffic regime, the steady state mean queue length is proved to be $O(frac1epsilon)$ where $epsilon$ is the heavy-traffic parameter, that goes to zero in the limit. The focus of this paper is on obtaining queue length bounds on prelimit systems, thus establishing the rate of convergence to the heavy traffic. In particular, we study the generalized switch model operating under the MaxWeight algorithm, and we show that the mean queue length of the prelimit system is only $Oleft(logleft(frac1epsilonight)ight)$ away from its heavy-traffic limit. We do this even when the so called complete resource pooling (CRP) condition is not satisfied. When the CRP condition is satisfied, in addition, we show that the MaxWeight algorithm is within $Oleft(logleft(frac1epsilonight)ight)$ of the optimal. Finally, we obtain similar results in load balancing systems operating under the join the shortest queue routing algorithm.

This page was built for publication: Logarithmic Heavy Traffic Error Bounds in Generalized Switch and Load Balancing Systems

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