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

Masayoshi NABESHIMA
Naoaki YAMANAKA

Publication
IEICE TRANSACTIONS on Communications   Vol.E83-B    No.2    pp.182-189
Publication Date: 2000/02/25
Online ISSN: 
DOI: 
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
Keyword: 
input-queued ATM switch,  scheduling algorithm,  throughput,  cell delay time,  

Full Text: PDF>>
Buy this Article


Summary: 
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).