The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Foi demonstrado que o enfileiramento de saída virtual (VOQ) e um algoritmo de escalonamento sofisticado permitem que um switch enfileirado de entrada atinja 100% de rendimento para processo de chegada independente. Vários dos algoritmos de escalonamento propostos podem ser classificados como algoritmos de escalonamento iterativos ou algoritmos de arbitragem de barra cruzada simétrica. i-OCF (célula mais antiga primeiro) e TSA (árbitro de duas etapas) são exemplos bem conhecidos de algoritmos de escalonamento iterativo e algoritmos de arbitragem de barra cruzada simétrica, respectivamente. No entanto, existem desvantagens no uso desses algoritmos. i-OCF leva muito tempo para encontrar uma correspondência completamente livre de conflitos entre as portas de entrada e as portas de saída porque requer múltiplas iterações. Se i-OCF não consegue encontrar uma correspondência completamente livre de conflitos, a taxa de transferência do switch cai. A TSA tem a possibilidade de encontrar uma correspondência livre de conflito mais rapidamente do que i-OCF porque não precisa de nenhuma iteração. No entanto, a TSA sofre com o problema da fome. Neste artigo, propomos um novo algoritmo de escalonamento. Ele usa dois escalonadores, que chamamos de escalonador 1 e escalonador 2, em paralelo. Depois que as células foram transmitidas, as informações que a porta de entrada i concedeu a oferta do porto de saída j no agendador 2 é mapeado para o agendador 1 se e somente se a porta de entrada i tem pelo menos uma célula destinada à porta de saída j. Se as informações forem movidas, a porta de entrada i e porta de saída j são correspondidos no agendador 1 no início do próximo intervalo de tempo. Nosso algoritmo proposto usa um escalonador baseado em TSA e outro escalonador baseado em i-OCF. Os resultados numéricos mostram que o algoritmo de escalonamento proposto não requer múltiplas iterações para encontrar uma correspondência completamente livre de conflitos e sofre do problema de fome tanto para tráfego uniforme quanto para tráfego em rajadas.
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.
Copiar
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
Copiar
@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},}
Copiar
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 -