
For FullText 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.

InputQueued Switches Using Two Schedulers in Parallel
Masayoshi NABESHIMA
Publication
IEICE TRANSACTIONS on Communications
Vol.E85B
No.2
pp.523531 Publication Date: 2002/02/01 Online ISSN:
DOI: Print ISSN: 09168516 Type of Manuscript: PAPER Category: Switching Keyword: input queued switch, scheduling algorithm, maximum throughput, number of iterations, starvation problem,
Full Text: PDF>>
Summary:
It has been shown that virtual output queuing (VOQ) and a sophisticated scheduling algorithm enable an inputqueued switch to achieve 100% throughput for independent arrival process. Several of the scheduling algorithms that have been proposed can be classified as either iterative scheduling algorithms or symmetric crossbar arbitration algorithms. iOCF (oldestcellfirst) and TSA (two step arbiter) are wellknown examples of iterative scheduling algorithms and symmetric crossbar arbitration algorithms, respectively. However, there are drawbacks in using these algorithms. iOCF takes long time to find completely a conflictfree match between input ports and output ports because it requires multiple iterations. If iOCF cannot find a conflictfree match completely, the switch throughput falls. TSA has the possibility that it finds a conflictfree match faster than iOCF because it does not need any iterations. However, TSA suffers from the starvation problem. In this paper, we propose a new scheduling algorithm. It uses two schedulers, which we call scheduler 1 and scheduler 2, in parallel. After cells were transmitted, the information that input port i granted the offer from output port j in scheduler 2 is mapped to scheduler 1 if and only if input port i has at least one cell destined for output port j. If the information is moved, input port i and output port j are matched in scheduler 1 at the beginning of the next time slot. Our proposed algorithm uses one scheduler based on TSA and the other scheduler based on iOCF. Numerical results show that the proposed scheduling algorithm does not require multiple iterations to find a conflictfree match completely and suffer from the starvation problem for both uniform and bursty traffic.

