Back to Search
Start Over
Low-Complexity Switch Scheduling Algorithms: Delay Optimality in Heavy Traffic.
- Source :
- IEEE/ACM Transactions on Networking; Feb2022, Vol. 30 Issue 1, p464-473, 10p
- Publication Year :
- 2022
-
Abstract
- Motivated by applications in data center networks, in this paper, we study the problem of scheduling in an input queued switch. While throughput maximizing algorithms in a switch are well-understood, delay analysis was developed only recently. It was recently shown that the well-known MaxWeight algorithm achieves optimal scaling of mean queue lengths in steady state in the heavy-traffic regime, and is within a factor less than 2 of a universal lower bound. However, MaxWeight is not used in practice because of its high time complexity. In this paper, we study several low complexity algorithms and show that their heavy-traffic performance is identical to that of MaxWeight. We first present a negative result that picking a random schedule does not have optimal heavy-traffic scaling of queue lengths even under uniform traffic. We then show that if one picks the best among two matchings or modifies a random matching even a little, using the so-called flip operation, it leads to MaxWeight like heavy-traffic performance under uniform traffic. We then focus on the case of non-uniform traffic and show that a large class of low time complexity algorithms have the same heavy-traffic performance as MaxWeight, as long as it is ensured that a MaxWeight matching is picked often enough. We also briefly discuss the performance of these algorithms in the large scale heavy-traffic regime when the size of the switch increases simultaneously with the load. Finally, we perform empirical study on a new algorithm to compare its performance with some existing algorithms. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 10636692
- Volume :
- 30
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- IEEE/ACM Transactions on Networking
- Publication Type :
- Academic Journal
- Accession number :
- 155332864
- Full Text :
- https://doi.org/10.1109/TNET.2021.3116606