The i-QOCF (Iterative Quasi-Oldest-Cell-First) Scheduling Algorithm for Input-Queued ATM Switches

摘要

This paper proposes the iterative quasi-oldest- cell-first (i-QOCF) scheduling algorithm, a new scheduling algo- rithm for input-queued ATM switches with virtual output queu- ing (VOQ). In the i-QOCF scheduling algorithm, each input port and each output port maintains its own list. The length of the list can be N, 2 × N, ... , B × N, where B is the size of the separate queue for an output port at input ports, and N is the number of output ports. The list maintained by an input port contains the identifiers for those output ports to which that input port will send a cell. The list maintained by an output port contains the identifiers for input ports that have a cell destined for that output port. If we use a list whose length is B × N, then the identifiers in the list appear in the oldest order, and i-QOCF gives preference to cells that have been waiting for the longest time. If we use a list whose length is less than B × N, then the identifiers in the list appear in the quasi-oldest order, and i-QOCF gives preference to cells that have been waiting for the quasi-longest time. We de- termine the performance of i-QOCF in a comparison with i-OCF in terms of cell delay time. We find that an input-queued ATM switch with i-QOCF and VOQ can achieve 100% throughput for independent arrival processes. Under uniform traffic, 3-QOCF is enough to achieve convergence during one cell time. If we use 3- QOCF, the list length is 3 × N, then its cell delay time is almost the same as that of 4-OCF (Oldest-Cell-First).