Leap Forward Virtual Clock: An O(loglogN) Fair Queuing Scheme with Guaranteed Delays and Throughput Fairness

We describe an efficient fair queuing scheme, Leap Forward Virtual Clock, that provides end-to-end delay bounds almost identical to that of PGPS fair queuing, along with throughput fairness. Our scheme can be implemented with a worst-case time O(loglogN) per packet guaranteed delay and throughput fairness. As its name suggests, our scheme is based on Zhang\u27s virtual clock. While the original virtual clock scheme does not achieve throughput fairness, we can modify it with a simple leap forward mechanism that keeps the server clock from lagging too far behind the packet tags. We prove that our scheme guarantees a fair share of the available bandwidth to each of the backlogged users, while precisely matching the delay bounds of PGPS schemes. In order to improve computational efficiency, we introduce a coarsened version of our scheme in which all tags assume values from a set of O(N) integers. We then use approximate sorting and a finite-universe priority queue to achieve O(loglogN) processing time per packet. We can show that the coarsening of tags increases the delay bound by a very small additive constant. Finally, our proofs are based on a dual version of the algorithm called Leap Backward, whose behavior is identical to the Leap Forward but that admits a simpler analysis