Crossbar scheduling algorithms for input-queued switches

Abstract

Many of today's switches and routers adopt an input-queued crossbar architecture to interconnect the input ports with the output ports. Such a switch needs to compute a crossbar schedule, or a matching, between the input ports and the output ports during each switching cycle, or time slot. A key research challenge in designing large (in number of input/output ports N) input-queued crossbar switches is to develop crossbar scheduling algorithms that can compute high-quality matchings -- i.e., those that result in high switch throughput (ideally 100%) and low queueing delays for packets -- yet have a very low time complexity to support high link speeds. Indeed, there appears to be a fundamental tradeoff between the time complexity of the crossbar scheduling algorithm and the quality of the computed matchings (crossbar schedules). This dissertation research consists of two aspects. The first aspect is to investigate crossbar scheduling algorithms that are low in time complexities (preferably O(1) and definitely no more than O(logN) per port), yet have excellent throughput (ideally equal or close to 100%) and delay performances. The second aspect is to analyze the throughput and the delay performance guarantees of some of the proposed algorithms using Lyapunov stability analysis techniques. Along the first aspect, we have proposed four algorithms. The first algorithm, called SERENADE (SERENA, the Distributed Edition), is a parallel iterative algorithm that can provably, with a time complexity of only O(logN) per port, exactly emulate SERENA, a centralized algorithm with O(N) time complexity, which can attain 100% throughput and acceptable delay performance. The second algorithm, called Queue-Proportional Sampling (QPS), is an "add-on" approach that generates superior starter matchings than all other known strategies, yet incurs only O(1) additional time complexity at each input/output port. We use QPS to augment two existing crossbar scheduling algorithms, namely SERENA and iSLIP. The augmented algorithms, which we call QPS-SERENA and QPS-iSLIP, outperform the original algorithms by a wide margin, under various load conditions and traffic patterns. Building upon QPS, we propose the third algorithm, which we call QPS-r, a parallel iterative crossbar scheduling algorithm with O(1) time complexity per port. We have shown that QPS-3 (r=3 iterations) has comparable empirical throughput and delay performances as maximal matching algorithms that have much higher time complexities. The last algorithm, call Small-Batch QPS (SB-QPS), is a batch (crossbar) scheduling algorithm that builds upon and significantly improves the throughput performance of QPS-r, yet has a time complexity of O(1) per port (per time slot). Along the second aspect, we have proved, using Lyapunov stability analysis, that QPS-SERENA can achieve 100% throughput and that using matchings generated by QPS-r (even when r=1) as crossbar schedules results in at least 50% switch throughput and order-optimal (i.e., independent of the switch size N) average delay bounds for various traffic arrival processes.