VOL. 7, NO. 2, APRIL 1999 | Nick McKeown, Senior Member, IEEE
The paper introduces the iSLIP scheduling algorithm for input-queued switches, which are commonly used in high-performance inter-networking protocol routers and ATM switches. The algorithm aims to overcome the limitations of simple first-in-first-out (FIFO) queues, which can lead to head-of-line (HOL) blocking and reduce achievable bandwidth. iSLIP is an iterative, round-robin scheduling algorithm designed to achieve 100% throughput for uniform traffic while being simple to implement in hardware. The paper discusses the benefits of using virtual output queueing (VOQ) to eliminate HOL blocking and presents the iSLIP algorithm, which is based on the parallel iterative matching (PIM) algorithm. iSLIP is shown to achieve high throughput for uniform traffic and can adapt to bursty traffic conditions. The algorithm's performance is analyzed under benign and bursty traffic scenarios, and its implementation complexity is discussed. iSLIP has been implemented in commercial systems with aggregate bandwidths ranging from 50 to 500 Gb/s, demonstrating its effectiveness in achieving high throughput and fairness in scheduling.The paper introduces the iSLIP scheduling algorithm for input-queued switches, which are commonly used in high-performance inter-networking protocol routers and ATM switches. The algorithm aims to overcome the limitations of simple first-in-first-out (FIFO) queues, which can lead to head-of-line (HOL) blocking and reduce achievable bandwidth. iSLIP is an iterative, round-robin scheduling algorithm designed to achieve 100% throughput for uniform traffic while being simple to implement in hardware. The paper discusses the benefits of using virtual output queueing (VOQ) to eliminate HOL blocking and presents the iSLIP algorithm, which is based on the parallel iterative matching (PIM) algorithm. iSLIP is shown to achieve high throughput for uniform traffic and can adapt to bursty traffic conditions. The algorithm's performance is analyzed under benign and bursty traffic scenarios, and its implementation complexity is discussed. iSLIP has been implemented in commercial systems with aggregate bandwidths ranging from 50 to 500 Gb/s, demonstrating its effectiveness in achieving high throughput and fairness in scheduling.