Heavy Traffic Analysis of Approximate Max-Weight Matching Algorithms for Input-Queued Switches
Yu Huang, Longbo Huang · ACM SIGMETRICS Performance Evaluation Review · 2021
In this paper, we propose a class of approximation algorithms for max-weight matching (MWM) policy for input-queued switches, called expected 1-APRX. We establish the state space collapse (SSC) result for expected 1-APRX, and characterize its queue length behavior in the heavy-traffic limit.