Exact GPS Simulation and Optimal Fair Scheduling With Logarithmic Complexity

摘要

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 $({hbox{WF}}^{2}{hbox{Q}})$ , which requires on-line GPS simulation. Existing algorithms to perform GPS simulation have $O(N)$ worst-case computational complexity per packet transmission ($N$ being the number of competing flows). Hence, ${hbox{WF}}^{2}{hbox{Q}}$ has been charged for $O(N)$ complexity too. However it has been proven that the lower bound complexity to guarantee $O(1)$ deviation is $Omega(log N)$, yet a scheduler achieving such a result has remained elusive so far.