The search functionality is under construction.

The search functionality is under construction.

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

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.

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 -