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
Neste artigo, estudamos algoritmos de escalonamento eficientes que são adequados para redes ATM. Nas redes ATM, todos os pacotes têm um comprimento fixo pequeno de 53 bytes e são transmitidos a taxas muito altas. Portanto, a complexidade de tempo de um algoritmo de escalonamento é muito importante. A maioria dos algoritmos de escalonamento propostos até agora têm uma complexidade de O(registro N) por pacote, onde N denota o número de conexões compartilhando o link. Em contraste, o round robin ponderado (WRR) tem a vantagem de ter O(1) complexidade; entretanto, sabe-se que sua propriedade de atraso piora à medida que N aumenta. Para resolver este problema, neste artigo propomos duas novas variantes de WRR, round robin uniforme (URR) e round robin uniforme ocioso (I-URR). Ambas as disciplinas fornecem atrasos de ponta a ponta e limites de justiça que são independentes de N. A complexidade da URR, no entanto, aumenta ligeiramente à medida que N aumenta, enquanto I-URR tem complexidade de O(1) por pacote. O I-URR também funciona como um modelador de tráfego, de modo que pode aliviar significativamente o congestionamento na rede. Também introduzimos uma disciplina WRR hierárquica (H-WRR) que consiste em diferentes servidores WRR usando I-URR como servidor raiz. O H-WRR acomoda com eficiência conexões garantidas e de melhor esforço, mantendo O(1) complexidade por pacote. Se várias conexões estiverem reservando a mesma largura de banda, o H-WRR fornece limites de atraso próximos aos do enfileiramento justo ponderado.
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
Norio MATSUFURU, Kouji NISHIMURA, Reiji AIBARA, "Efficient Fair Queueing for ATM Networks Using Uniform Round Robin" in IEICE TRANSACTIONS on Communications,
vol. E83-B, no. 6, pp. 1330-1341, June 2000, doi: .
Abstract: In this paper, we study efficient scheduling algorithms that are suitable for ATM networks. In ATM networks, all packets have a fixed small length of 53 bytes and they are transmitted at very high rate. Thus time complexity of a scheduling algorithm is quite important. Most scheduling algorithms proposed so far have a complexity of O(log N) per packet, where N denotes the number of connections sharing the link. In contrast, weighted round robin (WRR) has the advantage of having O(1) complexity; however, it is known that its delay property gets worse as N increases. To solve this problem, in this paper we propose two new variants of WRR, uniform round robin (URR) and idling uniform round robin (I-URR). Both disciplines provide end-to-end delay and fairness bounds which are independent of N. Complexity of URR, however, slightly increases as N increases, while I-URR has complexity of O(1) per packet. I-URR also works as a traffic shaper, so that it can significantly alleviate congestion on the network. We also introduce a hierarchical WRR discipline (H-WRR) which consists of different WRR servers using I-URR as the root server. H-WRR efficiently accommodates both guaranteed and best-effort connections, while maintaining O(1) complexity per packet. If several connections are reserving the same bandwidth, H-WRR provides them with delay bounds that are close to those of weighted fair queueing.
URL: https://global.ieice.org/en_transactions/communications/10.1587/e83-b_6_1330/_p
Copiar
@ARTICLE{e83-b_6_1330,
author={Norio MATSUFURU, Kouji NISHIMURA, Reiji AIBARA, },
journal={IEICE TRANSACTIONS on Communications},
title={Efficient Fair Queueing for ATM Networks Using Uniform Round Robin},
year={2000},
volume={E83-B},
number={6},
pages={1330-1341},
abstract={In this paper, we study efficient scheduling algorithms that are suitable for ATM networks. In ATM networks, all packets have a fixed small length of 53 bytes and they are transmitted at very high rate. Thus time complexity of a scheduling algorithm is quite important. Most scheduling algorithms proposed so far have a complexity of O(log N) per packet, where N denotes the number of connections sharing the link. In contrast, weighted round robin (WRR) has the advantage of having O(1) complexity; however, it is known that its delay property gets worse as N increases. To solve this problem, in this paper we propose two new variants of WRR, uniform round robin (URR) and idling uniform round robin (I-URR). Both disciplines provide end-to-end delay and fairness bounds which are independent of N. Complexity of URR, however, slightly increases as N increases, while I-URR has complexity of O(1) per packet. I-URR also works as a traffic shaper, so that it can significantly alleviate congestion on the network. We also introduce a hierarchical WRR discipline (H-WRR) which consists of different WRR servers using I-URR as the root server. H-WRR efficiently accommodates both guaranteed and best-effort connections, while maintaining O(1) complexity per packet. If several connections are reserving the same bandwidth, H-WRR provides them with delay bounds that are close to those of weighted fair queueing.},
keywords={},
doi={},
ISSN={},
month={June},}
Copiar
TY - JOUR
TI - Efficient Fair Queueing for ATM Networks Using Uniform Round Robin
T2 - IEICE TRANSACTIONS on Communications
SP - 1330
EP - 1341
AU - Norio MATSUFURU
AU - Kouji NISHIMURA
AU - Reiji AIBARA
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Communications
SN -
VL - E83-B
IS - 6
JA - IEICE TRANSACTIONS on Communications
Y1 - June 2000
AB - In this paper, we study efficient scheduling algorithms that are suitable for ATM networks. In ATM networks, all packets have a fixed small length of 53 bytes and they are transmitted at very high rate. Thus time complexity of a scheduling algorithm is quite important. Most scheduling algorithms proposed so far have a complexity of O(log N) per packet, where N denotes the number of connections sharing the link. In contrast, weighted round robin (WRR) has the advantage of having O(1) complexity; however, it is known that its delay property gets worse as N increases. To solve this problem, in this paper we propose two new variants of WRR, uniform round robin (URR) and idling uniform round robin (I-URR). Both disciplines provide end-to-end delay and fairness bounds which are independent of N. Complexity of URR, however, slightly increases as N increases, while I-URR has complexity of O(1) per packet. I-URR also works as a traffic shaper, so that it can significantly alleviate congestion on the network. We also introduce a hierarchical WRR discipline (H-WRR) which consists of different WRR servers using I-URR as the root server. H-WRR efficiently accommodates both guaranteed and best-effort connections, while maintaining O(1) complexity per packet. If several connections are reserving the same bandwidth, H-WRR provides them with delay bounds that are close to those of weighted fair queueing.
ER -