2021/11/14 by Arsalan Sharifnassab, John N. Tsitsiklis, Sharifnassab, Arsalan +1
Business, Management and Accounting · Computer Science · Decision Sciences · #Advanced Queuing Theory Analysis #FOS: Electrical engineering #FOS: Mathematics #Petri Nets in System Modeling #Probability (math.PR) #Simulation Techniques and Applications #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2111.07420
openalex publication_date 2021/11/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We say that a random variable is light-tailed if moments of order\n2+\ε are finite for some \ε>0; otherwise, we say that it is\nheavy-tailed. We study queueing networks that operate under the Max-Weight\nscheduling policy, for the case where some queues receive heavy-tailed and some\nreceive light-tailed traffic. Queues with light-tailed arrivals are often delay\nstable (that is, expected queue sizes are uniformly bounded over time) but can\nalso become delay unstable because of resource-sharing with other queues that\nreceive heavy-tailed arrivals.\n Within this context, and for any given "tail exponents" of the input traffic,\nwe develop a necessary and sufficient condition under which a queue is robustly\ndelay stable, in terms of jumping fluid models - an extension of\ntraditional fluid models that allows for jumps along coordinates associated\nwith heavy-tailed flows. Our result elucidates the precise mechanism that leads\nto delay instability, through a coordination of multiple abnormally large\narrivals at possibly different times and queues and settles an earlier open\nquestion on the sufficiency of a particular fluid-based criterion. Finally, we\nexplore the power of Lyapunov functions in the study of delay stability.\n