Highest Rank First: A New Class of Single-Iteration Scheduling Algorithms for Input-Queued Switches

Abstract

In this paper, we study a new class of single-iteration scheduling algorithms for inputqueued switches based on a new arbitration idea called highest rank first (HRF). We first demonstrate the effectiveness of HRF by a simple algorithm named Basic-HRF. In Basic-HRF, virtual output queues (VOQs) at an input port are ranked according to their queue sizes. The rank of a VOQ, coded by log(N +1) bits, where N is the switch size, is sent to the corresponding output as a request. Unlike all existing iterative algorithms, the winner is selected based on the ranks of the requests/grants. We show that the rank-based arbitration outperforms the widely adopted queue-based arbitration. To improve the performance under heavy load and maximize the match size, Basic-HRF is integrated with an embedded round-robin scheduler. The resulting HRF algorithm is shown to beat almost all existing single-iteration algorithms. But, the complexity of HRF is high due to the use of multi-bit requests. A novel request encoding/decoding mechanism is then designed to reduce the request size to a single bit while keeping the original performance of HRF. A unique feature of the resulting coded HRF (CHRF) algorithm is that the single-bit request indicates an increase or decrease of a VOQ rank, rather than an empty VOQ or not. We show that the CHRF is the most efficient single-bitsingle-iteration algorithm.

Keywords

• High-speed networks
• scheduling algorithm
• switches