Urgency-Based Round Robin: A New Scheduling Discipline for Multiservice Packet Switching Networks

Onur ALTINTA<sg00026.gif>; Yukio ATSUMI; Teruaki YOSHIDA

Urgency-Based Round Robin: A New Scheduling Discipline for Multiservice Packet Switching Networks

Onur ALTINTA, Yukio ATSUMI, Teruaki YOSHIDA

Full Text Views

0

Cite this

Summary :

Packet scheduling is one of the key mechanisms that will be employed in the network nodes (routers and switches) for supporting multiple quality of services. In this paper we propose a new packet scheduling algorithm called Urgency-based Round Robin (URR) which computes an index for flows in order to keep track of instantaneous bursts. Basically the index is employed as a measure of the time-dependent service necessity for each flow thus making it possible to detect those flows which might be in need of momentary service. Also, we propose a novel weight allocation scheme to be used together with the scheduler with the aim of preventing network underutilization. Our algorithm can be considered as a version of Weighted Round Robin (WRR) with improved delay characteristics. We show analytically that URR has the desired capability of upper-bounding unfairness. We also show, by simulation, that URR can improve delay performance even under extremely bursty traffic conditions without bandwidth overprovisioning. We also give simulation results for network traffic which exhibits long range dependency (self-similarity) and show that URR is again more effective than a plain round robin multiplexer.

Publication: IEICE TRANSACTIONS on Communications Vol.E81-B No.11 pp.2013-2022

Publication Date: 1998/11/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Issue on Performance and Quality of Service (QoS) of Multimedia Networks)

Category: IP Networks

Cite this

Copy

Onur ALTINTA, Yukio ATSUMI, Teruaki YOSHIDA, "Urgency-Based Round Robin: A New Scheduling Discipline for Multiservice Packet Switching Networks" in IEICE TRANSACTIONS on Communications, vol. E81-B, no. 11, pp. 2013-2022, November 1998, doi: .
Abstract: Packet scheduling is one of the key mechanisms that will be employed in the network nodes (routers and switches) for supporting multiple quality of services. In this paper we propose a new packet scheduling algorithm called Urgency-based Round Robin (URR) which computes an index for flows in order to keep track of instantaneous bursts. Basically the index is employed as a measure of the time-dependent service necessity for each flow thus making it possible to detect those flows which might be in need of momentary service. Also, we propose a novel weight allocation scheme to be used together with the scheduler with the aim of preventing network underutilization. Our algorithm can be considered as a version of Weighted Round Robin (WRR) with improved delay characteristics. We show analytically that URR has the desired capability of upper-bounding unfairness. We also show, by simulation, that URR can improve delay performance even under extremely bursty traffic conditions without bandwidth overprovisioning. We also give simulation results for network traffic which exhibits long range dependency (self-similarity) and show that URR is again more effective than a plain round robin multiplexer.
URL: https://global.ieice.org/en_transactions/communications/10.1587/e81-b_11_2013/_p

Copy

@ARTICLE{e81-b_11_2013,
author={Onur ALTINTA, Yukio ATSUMI, Teruaki YOSHIDA, },
journal={IEICE TRANSACTIONS on Communications},
title={Urgency-Based Round Robin: A New Scheduling Discipline for Multiservice Packet Switching Networks},
year={1998},
volume={E81-B},
number={11},
pages={2013-2022},
abstract={Packet scheduling is one of the key mechanisms that will be employed in the network nodes (routers and switches) for supporting multiple quality of services. In this paper we propose a new packet scheduling algorithm called Urgency-based Round Robin (URR) which computes an index for flows in order to keep track of instantaneous bursts. Basically the index is employed as a measure of the time-dependent service necessity for each flow thus making it possible to detect those flows which might be in need of momentary service. Also, we propose a novel weight allocation scheme to be used together with the scheduler with the aim of preventing network underutilization. Our algorithm can be considered as a version of Weighted Round Robin (WRR) with improved delay characteristics. We show analytically that URR has the desired capability of upper-bounding unfairness. We also show, by simulation, that URR can improve delay performance even under extremely bursty traffic conditions without bandwidth overprovisioning. We also give simulation results for network traffic which exhibits long range dependency (self-similarity) and show that URR is again more effective than a plain round robin multiplexer.},
keywords={},
doi={},
ISSN={},
month={November},}

Copy

TY - JOUR
TI - Urgency-Based Round Robin: A New Scheduling Discipline for Multiservice Packet Switching Networks
T2 - IEICE TRANSACTIONS on Communications
SP - 2013
EP - 2022
AU - Onur ALTINTA
AU - Yukio ATSUMI
AU - Teruaki YOSHIDA
PY - 1998
DO -
JO - IEICE TRANSACTIONS on Communications
SN -
VL - E81-B
IS - 11
JA - IEICE TRANSACTIONS on Communications
Y1 - November 1998
AB - Packet scheduling is one of the key mechanisms that will be employed in the network nodes (routers and switches) for supporting multiple quality of services. In this paper we propose a new packet scheduling algorithm called Urgency-based Round Robin (URR) which computes an index for flows in order to keep track of instantaneous bursts. Basically the index is employed as a measure of the time-dependent service necessity for each flow thus making it possible to detect those flows which might be in need of momentary service. Also, we propose a novel weight allocation scheme to be used together with the scheduler with the aim of preventing network underutilization. Our algorithm can be considered as a version of Weighted Round Robin (WRR) with improved delay characteristics. We show analytically that URR has the desired capability of upper-bounding unfairness. We also show, by simulation, that URR can improve delay performance even under extremely bursty traffic conditions without bandwidth overprovisioning. We also give simulation results for network traffic which exhibits long range dependency (self-similarity) and show that URR is again more effective than a plain round robin multiplexer.
ER -