Performance analysis and optimization of scheduling in high speed input queuing cell switches

Abstract

This thesis investigates techniques to improve throughput and reduce delay in input-queued cell switches, particularly focusing on the Head-of-the-Line (HOL) blocking problem. While pure input queuing suffers from limited throughput due to HOL blocking, Virtual Output Queuing (VOQ) eliminates this issue by maintaining separate queues for each output. However, VOQ requires efficient scheduling algorithms to achieve 100% throughput. Two scheduling algorithms are analyzed: Parallel Iterative Matching (PIM) and Queue Length-Weighted PIM (QL-WPIM). The thesis provides a detailed analysis of PIM’s maximum throughput and approximates mean cell delay. To address hardware limitations at high port speeds, a skipping technique is proposed, where matchings are computed every k>1k > 1k>1 slots instead of every slot. Performance improvements through skipping are demonstrated under various traffic models, and a modified version of PIM is introduced to enhance its effectiveness. The thesis also addresses packet segmentation and reassembly in VOQ-based switches. A procedure is proposed for determining optimal cell size under constraints of packet delay and scheduler speed, ensuring efficient switch operation. Overall, the work contributes practical solutions for improving performance in VOQ-based switches, balancing throughput, delay, and hardware feasibility.