IEICE TRANSACTIONS on Communications
Input-Queued Switches Using Two Schedulers in Parallel
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
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
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 -
English
