Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

1996-01-01

Filename

WUCS-96-10.PDF

Technical Report Number

WUCS-96-10

Abstract

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's 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.

Comments

Permanent URL: http://dx.doi.org/10.7936/K73F4MW8

Download

Share

COinS