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

No Thumbnail Available
Issue Date
Lin, Shih-Chun
Wang, Pu
Akyildiz, Ian F.
Luo, Min

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


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 Content
Click on the DOI link to access the article (may not be free).