1Exact GPS Simulation and Optimal Fair Scheduling with Logarithmic Complexity

Abstract — Generalized Processor Sharing (GPS) is a fluid scheduling policy providing perfect fairness over both constant-rate and variable-rate links. The minimum deviation (lead/lag) with respect to the GPS service achievable by a packet scheduler is one maximum packet size. To the best of our knowledge, the only packet scheduler guaranteeing the minimum deviation is Worst-case Fair Weighted Fair Queueing (WF2Q), which requires on-line GPS sim-ulation. Existing algorithms to perform GPS simulation have O(N) worst-case computational complexity per packet transmission (N being the number of competing flows). Hence WF2Q has been charged for O(N) complexity too. However it has been proven that the lower bound complexity to guarantee O(1) deviation is Ω(logN), yet a scheduler achieving such a result has remained elusive so far. In this paper we present L-GPS, an algorithm that performs exact GPS simulation with O(logN) worst-case complexity and small constants. As such it improves the complexity of all the packet schedulers based on GPS simulation. We also present L-WF2Q, an implementation of WF2Q based on L-GPS. L-WF2Q has O(logN) complexity with small constants, and, since it achieves the minimum possible deviation, it does match the aforementioned complexity lower bound. Furthermore, both L-GPS and L-WF2Q comply with constant-rate as well as variable-rate links. We assess the effectiveness of both algorithms by simulating real-world sce-narios