Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published April 2016 | metadata_only
Journal Article

When Heavy-Tailed and Light-Tailed Flows Compete: The Response Time Tail Under Generalized Max-Weight Scheduling


This paper focuses on the design and analysis of scheduling policies for multi-class queues, such as those found in wireless networks and high-speed switches. In this context, we study the response-time tail under generalized max-weight policies in settings where the traffic flows are highly asymmetric. Specifically, we consider a setting where a bursty flow, modeled using heavy-tailed statistics, competes with a more benign, light-tailed flow. In this setting, we prove that classical max-weight scheduling, which is known to be throughput optimal, results in the light-tailed flow having heavy-tailed response times. However, we show that via a careful design of inter-queue scheduling policy (from the class of generalized max-weight policies) and intra-queue scheduling policies, it is possible to maintain throughput optimality, and guarantee light-tailed delays for the light-tailed flow, without affecting the response-time tail for the heavy-tailed flow.

Additional Information

© 2015 IEEE. Manuscript received March 17, 2013; revised February 19, 2014; accepted January 19, 2015; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor I. Keslassy. Date of publication March 30, 2015; date of current version April 14, 2016. The work of J. Nair and A. Wierman was supported in part by the NSF through grant CNS 0846025 and NetSE grant CNS 0911041, in part by the ARO through MURI grant W911NF-08-1-0233, and in part by Bell Labs, Alcatel-Lucent. The work of J. Nair was also supported in part by an NWO VIDI grant. The work of K. Jagannathan was supported in part by ARO MURI grant W911NF-08-1-0238 and in part by the Indo UK Advanced Technology Center (IUATC).

Additional details

August 20, 2023
August 20, 2023