Urgency-Based Round Robin : A New Scheduling Discipline for Multiservice Packet Switching Networks (Special Issue on Performance and Quality of Service (QoS) of Multimedia Networks)

概要

論文の詳細を見る
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.
社団法人電子情報通信学会の論文
1998-11-25