Scalable schedulers for high-performance switches

Scheduler and switching fabric are two major hardware components of a cell switch. For a switch using a non-blocking switching fabric, the performance of the switch depends on the performance of its cell scheduler. We introduce the concepts of relative and universal scheduler scalabilities. Informally, a scheduler is relatively scalable with respect to a switching fabric if its structure is not more complex than the structure of its associated non-blocking switching fabric. A scheduler is universally scalable if its structural complexity is not larger than the structural complexity of any non-blocking switching fabric. Based on algorithm-hardware co-design, we present a universally scalable scheduler with O(N log N) interconnection complexity. We show by simulation that the performance of the proposed scheduler is almost the same as non-scalable schedulers.