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. https://resolver.caltech.edu/CaltechAUTHORS:20160527-135934012
Full text is not posted in this repository. Consult Related URLs below.
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20160527-135934012
Abstract
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: |
| ||||||||||||||||||
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). | ||||||||||||||||||
Funders: |
| ||||||||||||||||||
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: | https://resolver.caltech.edu/CaltechAUTHORS:20160527-135934012 | ||||||||||||||||||
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 | ||||||||||||||||||
Collection: | CaltechAUTHORS | ||||||||||||||||||
Deposited By: | Tony Diaz | ||||||||||||||||||
Deposited On: | 27 May 2016 21:07 | ||||||||||||||||||
Last Modified: | 03 Oct 2019 10:06 |
Repository Staff Only: item control page