An efficient scheduling algorithm for CIOQ switches with space-division multiplexing expansion
Ming Yang, S. Q. Zheng · 2004
Recently, CIOQ switches have attracted interest from both academic and industrial communities due to their ability of achieving 100% throughput and perfectly emulating OQ switch performance with a small speedup factor S. To achieve a speedup factor S, a conventional CIOQ switch requires the switch matrix and the memory to operate S times faster than the line rate. In this paper, we propose to use a CIOQ switch with space-division multiplexing expansion and grouped inputs/outputs (SDMG CIOQ switch for short) to achieve speedup while only requiring the switch matrix and the memory to operate at the line rate. The cell scheduling problem for the SDMG CIOQ switch is abstracted as a maximum bipartite k-matching problem. Using fluid model, we prove that any maximal size k-matching algorithm on an SDMG CIOQ switch with an expansion factor 2 can achieve 100% throughput assuming input arrivals satisfy the strong law of large numbers and no inputs/outputs are oversubscribed. We further propose an efficient and starvation-free maximal size k-matching scheduling algorithm, kFRR, for the SDMG CIOQ switch. Simulation results show that kFRR achieves 100% throughput with an expansion factor 2 under two SLLN traffic models, uniform traffic and polarized traffic, confirming our analysis.