• 高速交换系统中输入排队调度算法研究综述

    A review of input-queued scheduling algorithms in high-speed switching systems

    • 在数据中心交换机和Internet路由器等高速交换系统中,输入排队被广泛采用作为首选的交换结构。其中的调度算法主要负责数据包传输顺序的决策,目标在于优化吞吐量、降低延迟,并确保数据传输的公平性。深入探讨了输入排队调度算法对高速交换系统性能的影响,并对该领域的研究进行了综述。首先,详细阐述了输入排队交换机的基本架构及其关键性能指标。其次,深入分析了3种具有代表性的经典输入排队调度算法:最大权重匹配、极大匹配和随机匹配,从多个角度对它们进行了比较。最后,在大流量场景下分析了最大权重匹配的近似算法和极大匹配算法,并对近期的相关研究进行了系统性的梳理和总结。

       

      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.

       

    /

    返回文章
    返回