The search functionality is under construction.

The search functionality is under construction.

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.

- Publication
- IEICE TRANSACTIONS on Communications Vol.E83-B No.6 pp.1330-1341

- Publication Date
- 2000/06/25

- 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

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

Copy

@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},}

Copy

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 -