ACM SIGCOMM Computer Communication Review · 1996 · 125 citations · 15 references
BusinessComputer ScienceComputer SystemsDistributed SystemsQueuing TheoryServerless ComputingMulti-server QueuesPriority QueuesQueue DisciplineQueueing NetworksQueueing SystemsQueueing TheoryBandwidthFair QueueingFairnessFairness PropertiesImplementation ComplexityPerformance Bounds In QueuesQueueing Delay BoundsReal-time Networking
Hierarchical Packet Fair Queueing (H-PFQ) algorithms have the potential to simultaneously support guaranteed real-time service, rate-adaptive best-effort, and controlled link-sharing service. In this paper, we design practical H-PFQ algorithms by using one-level Packet Fair Queueing (PFQ) servers as basic building blocks, and develop techniques to analyze delay and fairness properties of the resulted H-PFQ servers. We demonstrate that, in order to provide tight delay bounds in a H-PFQ server, it is essential for the one-level PFQ servers to have small Worst-case Fair Indices (WFI). We propose a new one-level PFQ algorithm called WF 2 Q+ that is the first to have all the following three properties: (a) providing the tightest delay bound among all PFQ algorithms; (b) having the smallest WFI among all PFQ algorithms; and (c) having a relatively low implementation complexity of O(log N). We show that practical H-PFQ algorithms can be implemented by using WF 2 Q+ as the basic building block and prove that the resulting H-WF 2 Q+ algorithms provide similar delay bounds and bandwidth distribution as those provided by a H-GPS server. Simulation experiments are presented to evaluate the proposed algorithm.
15
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