Input-Queued Switches Using Two Schedulers in Parallel

Masayoshi NABESHIMA

Input-Queued Switches Using Two Schedulers in Parallel

Masayoshi NABESHIMA

Full Text Views

0

Cite this

Summary :

It has been shown that virtual output queuing (VOQ) and a sophisticated scheduling algorithm enable an input-queued 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. i-OCF (oldest-cell-first) and TSA (two step arbiter) are well-known examples of iterative scheduling algorithms and symmetric crossbar arbitration algorithms, respectively. However, there are drawbacks in using these algorithms. i-OCF takes long time to find completely a conflict-free match between input ports and output ports because it requires multiple iterations. If i-OCF cannot find a conflict-free match completely, the switch throughput falls. TSA has the possibility that it finds a conflict-free match faster than i-OCF 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 i-OCF. Numerical results show that the proposed scheduling algorithm does not require multiple iterations to find a conflict-free match completely and suffer from the starvation problem for both uniform and bursty traffic.

Publication: IEICE TRANSACTIONS on Communications Vol.E85-B No.2 pp.523-531

Publication Date: 2002/02/01

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Switching

Cite this

Copy

Masayoshi NABESHIMA, "Input-Queued Switches Using Two Schedulers in Parallel" in IEICE TRANSACTIONS on Communications, vol. E85-B, no. 2, pp. 523-531, February 2002, doi: .
Abstract: It has been shown that virtual output queuing (VOQ) and a sophisticated scheduling algorithm enable an input-queued 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. i-OCF (oldest-cell-first) and TSA (two step arbiter) are well-known examples of iterative scheduling algorithms and symmetric crossbar arbitration algorithms, respectively. However, there are drawbacks in using these algorithms. i-OCF takes long time to find completely a conflict-free match between input ports and output ports because it requires multiple iterations. If i-OCF cannot find a conflict-free match completely, the switch throughput falls. TSA has the possibility that it finds a conflict-free match faster than i-OCF 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 i-OCF. Numerical results show that the proposed scheduling algorithm does not require multiple iterations to find a conflict-free match completely and suffer from the starvation problem for both uniform and bursty traffic.
URL: https://global.ieice.org/en_transactions/communications/10.1587/e85-b_2_523/_p

Copy

@ARTICLE{e85-b_2_523,
author={Masayoshi NABESHIMA, },
journal={IEICE TRANSACTIONS on Communications},
title={Input-Queued Switches Using Two Schedulers in Parallel},
year={2002},
volume={E85-B},
number={2},
pages={523-531},
abstract={It has been shown that virtual output queuing (VOQ) and a sophisticated scheduling algorithm enable an input-queued 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. i-OCF (oldest-cell-first) and TSA (two step arbiter) are well-known examples of iterative scheduling algorithms and symmetric crossbar arbitration algorithms, respectively. However, there are drawbacks in using these algorithms. i-OCF takes long time to find completely a conflict-free match between input ports and output ports because it requires multiple iterations. If i-OCF cannot find a conflict-free match completely, the switch throughput falls. TSA has the possibility that it finds a conflict-free match faster than i-OCF 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 i-OCF. Numerical results show that the proposed scheduling algorithm does not require multiple iterations to find a conflict-free match completely and suffer from the starvation problem for both uniform and bursty traffic.},
keywords={},
doi={},
ISSN={},
month={February},}

Copy

TY - JOUR
TI - Input-Queued Switches Using Two Schedulers in Parallel
T2 - IEICE TRANSACTIONS on Communications
SP - 523
EP - 531
AU - Masayoshi NABESHIMA
PY - 2002
DO -
JO - IEICE TRANSACTIONS on Communications
SN -
VL - E85-B
IS - 2
JA - IEICE TRANSACTIONS on Communications
Y1 - February 2002
AB - It has been shown that virtual output queuing (VOQ) and a sophisticated scheduling algorithm enable an input-queued 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. i-OCF (oldest-cell-first) and TSA (two step arbiter) are well-known examples of iterative scheduling algorithms and symmetric crossbar arbitration algorithms, respectively. However, there are drawbacks in using these algorithms. i-OCF takes long time to find completely a conflict-free match between input ports and output ports because it requires multiple iterations. If i-OCF cannot find a conflict-free match completely, the switch throughput falls. TSA has the possibility that it finds a conflict-free match faster than i-OCF 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 i-OCF. Numerical results show that the proposed scheduling algorithm does not require multiple iterations to find a conflict-free match completely and suffer from the starvation problem for both uniform and bursty traffic.
ER -