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


IEICE TRANSACTIONS on Communications   Vol.E81-B   No.11   pp.2013-2022
Publication Date: 1998/11/25
Online ISSN: 
Print ISSN: 0916-8516
Type of Manuscript: Special Section PAPER (Special Issue on Performance and Quality of Service (QoS) of Multimedia Networks)
Category: IP Networks
packet scheduling,  quality of service,  real-time communication,  

Full Text: PDF>>
Buy this Article

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.