.png){kind=icon}
.png){kind=icon}
Return
Low-Complexity Switch Scheduling Algorithms: Delay Optimality in Heavy Traffic
.png){kind=icon}
OA
AI
DOI：10.1109/TNET.2021.3116606.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Switches
Throughput
Schedules
Job shop scheduling
Complexity theory
Delays
Scheduling algorithms
Data centers
MaxWeight
scheduling
state space collapse
power-of-d
bipartite matching
Journal
I
IF:
3.6
Papers:
4.4K
Citations:
9.5K