Delay-based maximum power-weight scheduling with heavy-tailed traffic

No Thumbnail Available
Authors
Lin, Shih-Chun
Wang, Pu
Akyildiz, Ian F.
Luo, Min
Advisors
Issue Date
2017-08
Type
Article
Keywords
Heavy tails , Delay-based maximum weight (MaxWeight) policy , Power-weight scheduling , Fluid-limit approximations , Throughput-optimal , Switched networks
Research Projects
Organizational Units
Journal Issue
Citation
S. C. Lin, P. Wang, I. F. Akyildiz and M. Luo, "Delay-Based Maximum Power-Weight Scheduling With Heavy-Tailed Traffic," in IEEE/ACM Transactions on Networking, vol. 25, no. 4, pp. 2540-2555, Aug. 2017
Abstract

Heavy-tailed (HT) traffic (e.g., the Internet and multimedia traffic) fundamentally challenges the validity of classic scheduling algorithms, designed under conventional light-tailed (LT) assumptions. To address such a challenge, this paper investigates the impact of HT traffic on delay-based maximum weight scheduling (DMWS) algorithms, which have been proven to be throughput-optimal with enhanced delay performance under the LT traffic assumption. First, it is proven that the DMWS policy is not throughput-optimal anymore in the presence of hybrid LT and HT traffic by inducing unbounded queuing delay for LT traffic. Then, to solve the unbounded delay problem, a delay-based maximum power-weight scheduling (DMPWS) policy is proposed that makes scheduling decisions based on queuing delay raised to a certain power. It is shown by the fluid model analysis that DMPWS is throughput-optimal with respect to moment stability by admitting the largest set of traffic rates supportable by the network, while guaranteeing bounded queuing delay for LT traffic. Moreover, a variant of the DMPWS algorithm, namely the IU-DMPWS policy, is proposed, which operates with infrequent queue state updates. It is also shown that compared with DMPWS, the IU-DMPWS policy preserves the throughput optimality with much less signaling overhead, thus expediting its practical implementation.

Table of Contents
Description
Click on the DOI link to access the article (may not be free).
Publisher
IEEE
Journal
Book Title
Series
IEEE/ACM Transactions on Networking;v.25:no.4
PubMed ID
DOI
ISSN
1063-6692
EISSN