Fast and Noniterative Scheduling in Input-Queued Switches

• 作者: Edwin H.-M. SHA Kevin F. CHEN S. Q. ZHENG
• 来源期刊: 通讯、网络与系统学国际期刊(英文)
• 学科: 工学
• 关键词: SWITCH ARCHITECTURE SWITCH FABRIC FABRIC SCHEDULING SRA
• 年，卷（期）: 2009,（3）
• 页码范围: 185-202
• 页数: 18页
• 分类号: TP39

摘要

Most high-end switches use an input-queued or a combined input- and output-queued architecture. The switch fabrics of these architectures commonly use an iterative scheduling system such as iSLIP. Iterative schedulers are not very scalable and can be slow. We propose a new scheduling algorithm that finds a maximum matching of a modified I/O mapping graph in a single iteration (hence noniterative). Analytically and experimentally, we show that it provides full throughput and incurs very low delay;it is fair and of low complexity;and it outperforms traditional iterative schedulers. We also propose two switch architectures suited for this scheduling scheme and analyze their hardware implementations. The arbiter circuit is simple, implementing only a FIFO queue. Only half as many arbiters for an iterative scheme are needed. The arbiters operate in complete parallel. They work for both architectures and make the hardware implementations sim-ple. The first architecture uses conventional queuing structure and crossbar. The second one uses separate memories for each queue at an input port and a special crossbar. This crossbar is simple and also has a re-duced diameter and distributed structure. We also show that the architectures have good scalability and re-quire almost no speedup.