A quantitative comparison of iterative scheduling algorithms for input-queued switches

In this paper we quantitatively evaluate three iterative algorithms for sch eduling cells in a high-bandwidth input-queued ATM switch. In particular, w e compare the performance of an algorithm described previously - parallel i terative matching (PIM) - with two new algorithms: iterative round-robin ma tching with slip (iSLIP) and iterative least-recently used (iLRU). We also compare each algorithm against FIFO input-queueing and perfect output-queue ing. For the synthetic workloads we consider, including uniform and bursty traffic, iSLIP performs almost identically to the other algorithms. Cases f or which PIM and iSLIP perform poorly are presented, indicating that care s hould be taken when using these algorithms. But, we show that the implement ation complexity of iSLIP is an order of magnitude less than for PIM, makin g it feasible to implement a 32 X 32 switch scheduler for iSLIP on a single chip. (C) 1998 Elsevier Science B.V. All rights reserved.