For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
The i-QOCF (Iterative Quasi-Oldest-Cell-First) Scheduling Algorithm for Input-Queued ATM Switches
Masayoshi NABESHIMA Naoaki YAMANAKA
IEICE TRANSACTIONS on Communications
Publication Date: 2000/02/25
Print ISSN: 0916-8516
Type of Manuscript: Special Section PAPER (IEICE/IEEE Joint Special Issue on Recent Progress in ATM Technologies)
Category: ATM Switch and System Development
input-queued ATM switch, scheduling algorithm, throughput, cell delay time,
Full Text: PDF>>
This paper proposes the iterative quasi-oldest-cell-first (i-QOCF) scheduling algorithm, a new scheduling algorithm for input-queued ATM switches with virtual output queuing (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 determine 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).