MNCM a new class of efficient scheduling algorithms for input-buffered switches with no speedup
Vahid Tabatabaee, Leandros Tassiulas · 2003
In this paper, we use fluid model techniques to establish some new results for the throughput of input-buffered switches. In particular, we introduce a new class of deterministic maximal size matching algorithms that achieves 100% throughput. Dai and Prabhakar (2000) has shown that any maximal size matching algorithm with speedup of 2 achieves 100% throughput. We introduce a class of maximal size matching algorithms that we call them maximum node containing matching (MNCM) algorithms, and prove that they have 100% throughput with no speedup. We also introduce a new weighted matching algorithm, maximum first matching (MFM) with complexity O(N2.5) that belongs to MNCM. MFM, to the best of our knowledge, is the lowest complexity deterministic algorithm that delivers 100% throughput. The only assumption on the input traffic is that it satisfies the strong law of large numbers. Besides throughput, average delay is the other key performance metric for the input-buffered schedulers. We use simulation results to compare and study the delay performance of MFM. The simulation results demonstrate promising delay performance for MFM.