A Caltech Library Service

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

Nair, Jayakrishnan and Jagannathan, Krishna and Wierman, Adam (2016) When Heavy-Tailed and Light-Tailed Flows Compete: The Response Time Tail Under Generalized Max-Weight Scheduling. IEEE/ACM Transactions on Networking, 24 (2). pp. 982-995. ISSN 1063-6692.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription ItemConference Paper
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).
Funding AgencyGrant Number
NSFCNS 0846025
NSF NetSECNS 0911041
Army Research Office (ARO)W911NF-08-1-0233
Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO)UNSPECIFIED
Army Research Office (ARO)W911NF-08-1-0238
UK Advanced Technology Center (IUATC)UNSPECIFIED
Subject Keywords:First come first served, heavy-tailed traffic, large deviations, last come first served, light-tailed traffic, maximum weight scheduling, response time tail, stability
Issue or Number:2
Record Number:CaltechAUTHORS:20160527-135934012
Persistent URL:
Official Citation:J. Nair, K. Jagannathan and A. Wierman, "When Heavy-Tailed and Light-Tailed Flows Compete: The Response Time Tail Under Generalized Max-Weight Scheduling," in IEEE/ACM Transactions on Networking, vol. 24, no. 2, pp. 982-995, April 2016. doi: 10.1109/TNET.2015.2415874
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:67464
Deposited By: Tony Diaz
Deposited On:27 May 2016 21:07
Last Modified:03 Oct 2019 10:06

Repository Staff Only: item control page