Technical Report Number
Most scalable switches are required to buffer packets at both their inputs and outputs to overcome the slow memory speeds of packet queues. This thesis deals with the design of scheduling algorithms for such Combined Input and Output Queued (CIOQ) switches. For crossbar based CIOQ switches, we demonstrate the underperformance of commercially used scheduling algorithms under overload traffic conditions using targeted stress tests and present ideas to develop robust, stress resistant versions of these algorithms that are still simple enough to be implemented in high speed switches. To regulate the flow of traffic in buffered, multi-stage switches, we introduce a novel mechanism called distributed scheduling. Distributed scheduling is similiar to crossbar scheduling used in switches with small port counts, but is both distributed and coarse-grained to enable high-speed implementations of scheduling algorithms in high capacity, high performance switches. In this thesis, we comprehensively study and evaluate distributed scheduling.
Pappu, Prashanth and Turner, Jonathan S., "Scheduling Algorithms for CIOQ Switches" Report Number: WUCSE-2004-42 (2004). All Computer Science and Engineering Research.