Abstract:
Input-queuing is a widely adopted switching fabric in high-speed switching systems, such as data center switches and Internet routers. The scheduling algorithms are primarily responsible for determining the order of packet transmission, with the objective of optimizing throughput, reducing delay, and fairness. This paper discusses the impact of input-queued scheduling algorithms on the performance of high-speed switching systems and summarizes research in this area. Firstly, the fundamental architecture of input-queued switches and their key performance metrics are elucidated in detail. Secondly, three classical input-queued scheduling algorithms are analyzed (maximal weight matching, maximal matching, and random matching). Finally, the approximate algorithm of maximum weight matching and the maximum matching algorithm are analyzed in the high-traffic scenario, and the recent related studies are systematically sorted out and summarized.