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
Dans cet article, nous étudions des algorithmes de planification efficaces adaptés aux réseaux ATM. Dans les réseaux ATM, tous les paquets ont une petite longueur fixe de 53 octets et sont transmis à un débit très élevé. La complexité temporelle d’un algorithme de planification est donc très importante. La plupart des algorithmes d'ordonnancement proposés jusqu'à présent ont une complexité de O(Journal N) par paquet, où N désigne le nombre de connexions partageant le lien. En revanche, le round robin pondéré (WRR) présente l’avantage d’avoir O(1) complexité ; cependant, on sait que sa propriété de retard s'aggrave à mesure que N augmente. Pour résoudre ce problème, nous proposons dans cet article deux nouvelles variantes de WRR, le round robin uniforme (URR) et le round robin uniforme au ralenti (I-URR). Les deux disciplines fournissent des délais de bout en bout et des limites d'équité qui sont indépendantes de N. La complexité de l'URR augmente cependant légèrement à mesure que N augmente, tandis que I-URR a une complexité de O(1) par paquet. I-URR fonctionne également comme un modérateur de trafic, ce qui lui permet de réduire considérablement la congestion du réseau. Nous introduisons également une discipline WRR hiérarchique (H-WRR) composée de différents serveurs WRR utilisant I-URR comme serveur racine. H-WRR prend en charge efficacement les connexions garanties et au mieux, tout en conservant O(1) complexité par paquet. Si plusieurs connexions réservent la même bande passante, H-WRR leur fournit des limites de délai proches de celles d'une file d'attente équitable pondérée.
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.
Copier
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
Copier
@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},}
Copier
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 -