The Sliding-Window Queue-Proportional Sampling (SW-QPS) Algorithm | Technology Licensing

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.