2002 · 1.1K citations · 21 references
BusinessComputer ScienceComputer SystemsDistributed SystemsMobile SystemsQueuing TheoryCongestion ControlCongestion ManagementQueueing NetworksQueueing ProcessesQueueing SystemsQueueing TheoryEnd-to-end DelayFair QueueingFair Resource AllocationPerformance Bounds In QueuesProcessor Sharing DisciplineProcessor Sharing QueuesQueueing ModelsWeighted Fair Queueing
GPS guarantees bounded delay for leaky‑bucket constrained traffic and fair bandwidth allocation regardless of constraints, but its ideal fluid model is unrealizable, leading to packet approximations such as WFQ, which is considered the most accurate. The authors propose a new packet‑level GPS approximation called worst‑case fair weighted fair queueing (WF²/Q). WF²/Q is a packet‑based algorithm that limits the service difference from GPS to at most one maximum‑size packet. While WFQ’s delay bound is within one packet of GPS, significant discrepancies can arise that harm congestion‑control algorithms; in contrast, WF²/Q’s service is almost identical to GPS, differing by no more than one maximum‑size packet.
The generalized processor sharing (GPS) discipline is proven to have two desirable properties: (a) it can provide an end-to-end bounded-delay service to a session whose traffic is constrained by a leaky bucket; (b) it can ensure fair allocation of bandwidth among all back logged sessions regardless of whether or not their traffic is constrained. The former property is the basis for supporting guaranteed service traffic while the later property is important for supporting best-effort service traffic. Since GPS uses an idealized fluid model which cannot be realized in the real world, various packet approximation algorithms of the GPS have been proposed. Among these, weighted fair queueing (WFQ) also known as packet generalized processor sharing (PGPS) has been considered to be the best one in terms of accuracy. In particular, it has been proven that the delay bound provided by WFQ is within one packet transmission time of that provided by GPS. We show that, contrary to popular belief there could be large discrepancies between the services provided by the packet WFQ system and the fluid GPS system. We argue that such a discrepancy will adversely effect many congestion control algorithms that rely on services similar to those provided by GPS. A new packet approximation algorithm of GPS called worst-case fair weighted fair queueing (WF/sup 2/Q) is proposed. The service provided by WF/sup 2/Q is almost identical to that of GPS, differing no more than one maximum size packet.
21
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