High performance schedulers for network switches and routers

This dissertation studies the cell scheduling problem for input queueing (IQ) and combined input and output queueing (CIOQ) switches with virtual output queues (VOQs) and focuses on constructing high performance schedulers for network switches and routers. To provide efficient and practical solutions, we take algorithm and hardware codesign as the theme of the dissertation. We propose several scheduler solutions, each consisting of scheduling algorithms, designs of special hardware components which can be used to build up schedulers based on these algorithms, and necessary switch architectures and queueing schemes.; We summarize the results obtained in this dissertation as follows. (1) A pipelined framework for a class of pipelined iterative maximal size matching (MSM) algorithms, which reduce the scheduling time constraint by SIS+I-1 times, where S is the speedup factor and I is the number of iterations allowed in each scheduling cycle. (2) A parallel round-robin arbiter (PRRA) design with O(log N)-gate delay and O(N) number of gates, which can be used to implement the proposed pipelined iterative MSM algorithms. (3) A new CIOQ switch architecture with space-division multiplexing expansion and grouped input/output ports (SDMG CIOQ switches for short), which only requires the switching fabric and memories to operate at the line rate. (4) Using fluid model techniques, we prove that any maximal size k-matching algorithm on an SDMG CIOQ switch with an expansion of 2 can achieve 100% throughput assuming input arrivals satisfy the strong law of large numbers (SLLN) and no input/output line is oversubscribed. (5) An efficient and starvation-free maximal size k-matching scheduling algorithm, the k-connection FIRM-based round-robin ( kFRR) algorithm, for the SDMG CIOQ switch. (6) Programmable k-selector designs which are capable of selecting k out of N requests in O(log N)-gate delay, which can be used to implement the kFRR algorithm. (7) The dynamic DiffServ scheduling (DDS) algorithm for IQ switches, which provides minimum bandwidth guarantees for EF and AF traffic and fair bandwidth allocation for BE traffic. (8) Programmable weighted arbiter (PWA) designs with O(N) gates and O(b log N)-gate delay, where b is the number of bits needed to represent the weight. The PWA designs can be used to implement the DDS algorithm.; Performance of these algorithms and designs is evaluated by either proofs or simulations. Comparisons have been made with existing best solutions.