Premium
Class‐based weighted fair queueing: validation and comparison by trace‐driven simulation
Author(s) -
El Abdouni Khayari Rachid
Publication year - 2005
Publication title -
international journal of communication systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.344
H-Index - 49
eISSN - 1099-1131
pISSN - 1074-5351
DOI - 10.1002/dac.744
Subject(s) - computer science , rate monotonic scheduling , dynamic priority scheduling , weighted fair queueing , fair share scheduling , round robin scheduling , distributed computing , two level scheduling , scheduling (production processes) , open shop scheduling , real time computing , mathematical optimization , queueing theory , computer network , mathematics , quality of service
World‐wide web as well as proxy servers rely for their scheduling on services provided by the underlying operating system. In practice, this means that some form of first‐come‐first‐served (FCFS) scheduling is utilized. Although FCFS is a reasonable scheduling strategy for job sequences that do not show much variance, for the world‐wide web it has been shown that the requested‐object sizes do exhibit heavy tails. Under these circumstances, job scheduling on the basis of shortest‐job first (SJF) or shortest remaining processing time (SRPT) has been shown to minimize the total average waiting time. However, these methods have the disadvantage of potential job starvation. In order to avoid the problems of both FCFS and SJF we present in this paper a new scheduling approach called class‐based interleaving weighted fair queueing (CI‐WFQ). This scheduling approach exploits the specific characteristics of the job stream being served, that is, the distribution of the sizes of the objects being requested, to set its parameters such that good mean response times are obtained and starvation does not occur. In that sense, the new scheduling strategy can be made adaptive to the characteristics of the job stream being served. In this paper we compare the new scheduling approach (using trace‐driven simulations) to FCFS, SJF and the recently introduced α‐scheduling, and show that CI‐WFQ combines very good performance (as far as mean and variance of response time and blocking probability are concerned) with a scheduling complexity almost as low as for FCFS (and hence, lower than for SJF and α‐scheduling). The use of trace‐driven simulation is essential, since the special properties of the arrival process makes analytical solutions very difficult to achieve. Copyright © 2005 John Wiley & Sons, Ltd.