ACM SIGCOMM Computer Communication Review · 1996 · 69 citations · 18 references
BusinessComputer ScienceComputer SystemsHeterogeneous ComputingQueuing TheorySchedulingLatency OptimizationQueueing NetworksQueueing SystemsQueueing TheoryResource SchedulingService SchedulingEnd-to-end DelayEnd-to-end Delay AnalysisFair QueueingFair SchedulingFairnessPerformance Bounds In QueuesThroughputWeighted Fair Queueing
We present Start-time Fair Queuing (SFQ) algorithm that is computationally efficient, achieves fairness regardless of variation in a server capacity, and has the smallest fairness measure among all known fair scheduling algorithms. We analyze its throughput, single server delay, and end-to-end delay guarantee for variable rate Fluctuation Constrained (FC) and Exponentially Bounded Fluctuation (EBF) servers. We show that SFQ is better suited than Weighted Fair Queuing for integrated services networks and it is strictly better than Self Clocked Fair Queuing. To support heterogeneous services and multiple protocol families in integrated services networks, we present a hierarchical SFQ scheduler and derive its performance bounds. Our analysis demonstrates that SFQ is suitable for integrated services networks since it: (1) achieves low average as well as maximum delay for low-throughput applications (e.g., interactive audio, telnet, etc.); (2) provides fairness which is desirable for VBR video; (3) provides fairness, regardless of variation in a server capacity, for throughput-intensive, flow-controlled data applications; (4) enables hierarchical link sharing which is desirable for managing heterogeneity; and (5) is computationally efficient.
18
Analysis and simulation of a fair queueing algorithm
Alan Demers, Srinivasan Keshav, Scott Shenker · 1989 · 1.7K citations
A self-clocked fair queueing scheme for broadband applications
S. Jamaloddin Golestani · 2002 · 1.1K citations
A control-theoretic approach to flow control
Srinivasan Keshav · 1991 · 752 citations · Full text