Stability of the Maximum Size Matching

摘要

Among scheduling algorithms used in input queued switches, it is known that the Maximum Size Matching (MSM) algorithm maximizes the instantaneous throughput. Although there have been results on the stability of some specific types of MSMs for scheduling traffic, the question of how it performs under uniform traffic remains open. Simulations suggest the stability of MSM algorithms under uniform traffic but there have been no analytical results proving the same. In this article, we introduce a new Lyapunov function in order to prove that under uniform arrival traffic MSM algorithm achieves 100% throughput and also to find a stability region for the arrival rates.