Scheduling Algorithms for CIOQ Switches
The changing traffic conditions in the Internet have created a need for high capacity, scalable switches. Most scalable switches are required to buffer packets at both their inputs and outputs to overcome the slow memory speeds of packet queues. Such switches are called Combined Input and Output Queued (CIOQ) switches.
This thesis deals with the design of scheduling algorithms for CIOQ switches to maintain their throughput under the most demanding traffic conditions.
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 CIOQ switches, we introduce a novel mechanism called distributed scheduling. Distributed scheduling is similar 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. We believe that the results presented in this thesis are of immediate consequence and utility to most commercially designed routers.