Title :
Minimum-delay self-clocked fair queueing algorithm for packet-switched networks
Author :
Chiussi, Fabio M. ; Francini, Andrea
Author_Institution :
High-Speed Networks Res. Dept., AT&T Bell Labs., Holmdel, NJ, USA
fDate :
29 Mar-2 Apr 1998
Abstract :
The minimum-delay self-clocked fair queueing (MD-SCFQ) algorithm that we present in this paper is the first algorithm that achieves the same delay bounds as the packet by packet version of generalized processor sharing (P-GPS), has fairness properties similar to P-GPS, and uses a system-potential function of 0(1) complexity. To prove that MD-SCFQ achieves the same delay bounds of P-GPS, we have shown that the fluid version of MD-SCFQ belongs to the class of rate proportional server (RPS) schedulers; thus, its packet-by-packet version inherits all the well-known single-node and multiple-node delay properties of P-RPS schedulers. We have also computed the fairness index of MD-SCFQ, and show that is very close to that of P-GPS. Because of the properties of its system potential, MD-SCFQ, when combined with a shaper which declares packets eligible for scheduling according to their virtual starting times, is a work-conserving worst-case fair scheduler
Keywords :
computational complexity; delays; packet switching; processor scheduling; queueing theory; MD-SCFQ; RPS schedulers; complexity; delay bounds; fairness properties; fluid version; minimum-delay self-clocked fair queueing algorithm; multiple-node delay properties; packet-by-packet version; packet-switched networks; rate proportional server schedulers; shaper; single-node delay properties; system-potential function; work-conserving worst-case fair scheduler; Bandwidth; Clocks; Computer networks; Delay; Global Positioning System; High-speed networks; Scheduling algorithm; Sorting; Telecommunication traffic; Traffic control;
Conference_Titel :
INFOCOM '98. Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE
Conference_Location :
San Francisco, CA
Print_ISBN :
0-7803-4383-2
DOI :
10.1109/INFCOM.1998.662923