Throughput-otimal LIFO policy for bounded delay in the presence of heavy-tailed traffic

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

S. C. Lin, P. Wang, I. F. Akyildiz and M. Luo, "Throughput-Optimal LIFO Policy for Bounded Delay in the Presence of Heavy-Tailed Traffic," 2016 IEEE Global Communications Conference (GLOBECOM), Washington, DC, 2016, pp. 1-7


Scheduling is one of the most important resource allocation for networked systems. Conventional scheduling policies are primarily developed under light-tailed (LT) traffic assumptions. However, recent empirical studies show that heavy-tailed (HT) traffic flows have emerged in a variety of networked systems, such as cellular networks, the Internet, and data centers. The highly bursty nature of HT traffic fundamentally challenges the applicability of the conventional scheduling policies. This paper aims to develop novel throughput-optimal scheduling algorithms under hybrid HT and LT traffic flows, where classic optimal policies (e.g., maximum-weight/backpressure schemes), developed under LT assumption, are not throughput-optimal anymore. To counter this problem, a delay-based maximumweight scheduling policy with the last-in first-out (LIFO) service discipline, namely LIFO-DMWS, is proposed with the proved throughput optimality under hybrid HT and LT traffic. The throughput optimality of LIFO-DMWS gives that a networked system can support the largest set of incoming traffic flows, while guaranteeing bounded queueing delay to each queue, no matter the queue has HT or LT traffic arrival. Specifically, by exploiting asymptotic queueing analysis, LIFO-DMWS is proved to achieve throughout optimality without requiring any knowledge of traffic statistic information (e.g., the tailness or burstiness of traffic flows). Simulation results validate the derived theories and confirm that LIFO-DMWS achieves bounded delay for all flows under challenging HT environments.

Table of Content
Click on the DOI link to access the article (may not be free).