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

Masayoshi NABESHIMA, Naoaki YAMANAKA

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

• Publication: IEICE TRANSACTIONS on Communications Vol.E83-B No.2 pp.182-189
• Publication Date: 2000/02/25
• Type of Manuscript: Special Section PAPER (IEICE/IEEE Joint Special Issue on Recent Progress in ATM Technologies)
• Category: ATM Switch and System Development

Authors

Masayoshi NABESHIMA
Naoaki YAMANAKA

Keyword

input-queued ATM switch,  scheduling algorithm,  throughput,  cell delay time