Throughput Optimal Scheduling in the Presence of Heavy-Tailed Traffic

https://conf.papercept.net/conferences/conferences/ALLER10/program/ALLER10_ContentListWeb_2.html#tha5_02We investigate the tail behavior of the steady-state queue occupancies under throughput optimal scheduling in the presence of heavy-tailed traffic. We consider a system consisting of two parallel queues, served by a single server. One of the queues receives traffic that is heavy-tailed (the “heavy queue”), and the other receives light-tailed traffic (the “light queue”). The queues are connected to the server through time-varying ON/OFF links. We study a generalized version of max-weight scheduling, called the max-weight-α policy, and show that the light queue occupancy distribution is heavy-tailed for arrival rates above a threshold value. We also obtain the exact `tail coefficient' of the light queue occupancy distribution under max-weight-alpha scheduling. Next, we show that the policy that gives complete priority to the light queue guarantees the best possible tail behavior of both queue occupancy distributions. However, the priority policy is not throughput optimal, and can cause undesirable instability effects in the heavy queue. Finally, we propose a log-max-weight (LMW) scheduling policy. We show that in addition to being throughput optimal, the LMW policy guarantees that the light queue occupancy distribution is light-tailed, for all arrival rates that the priority policy can stabilize. Thus, the LMW scheduling policy has desirable performance on both fronts, namely throughput optimality, and the tail behavior of the light queue occupancy distribution.National Science Foundation (U.S.) (Grant CNS-0626781)National Science Foundation (U.S.) (Grant CNS-0915988)National Science Foundation (U.S.) (Grant CCF-0728554)United States. Army Research Office (ARO Muri grant number W911NF-08-1-0238