Delay Bounds for Approximate Maximum Weight Matching Algorithms for Input Queued Switches

Input Queued (IQ) switch architecture has been of interest due to its low memory bandwidth requirement. A scheduling algorithm is required to schedule the transfer of packets through cross-bar switch fabric at every time slot. The performance, that is throughput and delay, of a switch depends on the scheduling algorithm. The maximum weight matching (MWM) algorithm is known to deliver 100% throughput under any admissible traffic. Leonardi et. al. (2001) obtained a nontrivial bound on the delay for the MWM algorithm under admissible Bernoulli i.i.d. traffic. There has been a lot of interesting work done over time to analyze throughput of scheduling algorithms. But apart from the work of Leonardi et al. there has not been any work done to obtain bounds on delay of scheduling algorithms. The MWM algorithm is perceived to be a very good scheduling algorithm in general and simulations have suggested that it performs better than most of the known algorithms in terms of delay. But it is very complex to implement. Hence many simple to implement approximations to MWM have been proposed. In this paper, we study a class of approximation algorithms to MWM, which always obtain a schedule whose weight W differs from the weight of MWM schedule W* by at most f(W*), where f(.) is a sub-linear function. We call this difference in weight as “approximation distance” of algorithm from MWM. We denote this class of algorithms by 1-APRX. We prove that any 1-APRX algorithm is stable, that is, it delivers upto 100% of throughput under any admissible Bernoulli i.i.d. input traffic. Under any admissible Bernoulli i.i.d. traffic, we obtain bounds on the average queue length(equivalently delay) of the 1-APRX algorithms using a Lyapunov function technique, which was motivated in Leonardi et al. The delay bounds obtained for the 1-APRX algorithm are linearly related with the “approximation distance”, which matches the intuition that the better the weight of the schedule, the better the algorithm will perform. Interestingly, simulations show a linear relationship between the average queue length (equivalently delay) and the “approximation distance”. Thus, the “approximation distance” of a scheduling algorithm can serve as a metric to differentiate between the performance of different stable algorithms, even though throughput may be same for these algorithms. We also obtain a novel heuristic tighter bound on the average queue length (equivalently delay) under uniform Bernoulli i.i.d. traffic for MWM using a very simple argument.