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

Abstract

It is well known that the phenomenon of Head-of-the-Line (HOL) blocking limits the maximum achievable throughput of a pure Input Queuing cell switch (in which there is only one queue at each input that buffers all the cells arriving at the input). At each input, if instead of one queue for all the outputs, one queue for each output is used, then 100% throughput can be achieved. This type of queuing, known as Virtual Output Queuing (VOQ), removes the HOL blocking problem, but in order to achieve 100% throughput requires a scheduling algorithm to determine at each slot which input cells should be matched to their outputs (a matching). We have considered two scheduling algorithms: Parallel Iterative Matching (PIM) and Queue Length-Weighted Parallel Iterative Matching (QL-WPIM). We provide an analysis of the maximum throughput of PIM, and also an approximate analysis of mean cell delay. As the port speed increases, the matching between inputs and outputs of the switch has to be found in smaller time. Hence, the speed of the scheduler has to be increased, which may not be possible owing to restrictions imposed by the hardware. We study a solution to this problem by the simple technique of skipping. In skipping, a new matching is found every Δ (> 1) slots instead of every slot. The effectiveness of skipping is shown using various traffic models. To enhance the performance of skipping, a modification is suggested in the PIM algorithm. The switch or router may receive variable-length packets. It is common practice to segment them into fixed-length packets (cells), and use a cell-based switch fabric. The cells are reassembled into packets at the output ports of the router. We also consider the problem of determining the cell size in a VOQ-based switch, and provide a procedure for determining the cell size under packet delay constraint and scheduler speed constraint.