This novel switching algorithm for Internet routers eliminates the batching delays that occur with widely used regular switching algorithms without sacrificing throughput performance. The Sliding-Window Queue-Proportional Sampling (SW-QPS) algorithm employs an innovative framework that computes high-quality matchings, as measured by resulting throughput and delay performances.
SW-QPS uses sliding-window switching, which combines regular switching with batch switching. In this approach, high-quality matches are computed for every time slot then move forward, allowing new matchings to be computed in the immediate next time slot. Because matchings are processed as early as possible, batching delays are eliminated.
The SW-QPS algorithm builds on the achievements of another Georgia Tech–developed batch switching algorithm called Small-Batch QPS (SB-QPS). Compared to other batch switching algorithms, SB-QPS attains a high throughput performance under various traffic load patterns, using only small-batch-size time slots. It significantly reduces both the batch size and time complexity by matching computation per port via parallelization.
The SW-QPS algorithm enhances the desirable time complexity features of SB-QPS yet offers better throughput performance and delay avoidance.
- High performance: Offers a novel switching framework that eliminates batching delays without sacrificing throughput performance
- Advanced: Computes matchings of much higher quality than state-of-the-art and widely used regular switching algorithms
- Efficient: Achieves at least 88 percent throughput with a computational complexity of just O(1) per port
- Internet routers
- Data centers
- Storage area networks (SANs)
- High-performance computing (HPC)
Many present-day switching systems in Internet routers and data centers employ an input-queued crossbar to interconnect their input and output ports. In an N x N input-queued crossbar switch, each input port can be connected to only one output port and vice versa in each switching cycle or time slot. Hence, in every time slot, the switch needs to compute a one-to-one matching (i.e., the crossbar schedule) between input and output ports.
A major research challenge of designing high-link-rate switches with a large number of ports (known as high-radix) is to develop switching algorithms that can compute high-quality matchings. These matchings result in high switch throughput and low queueing delays for packets in a short time slot.
This Georgia Tech algorithm computes higher-quality matchings than legacy regular switching algorithms that build upon the same underlying bipartite matching algorithm, making it easy to implement.
Sliding-window switching