Virtual minimum potential queuing

Abstract

We propose Virtual Minimum Potential Queuing (VMPQ) which provides a simple virtual time update function with O(1) complexity. While Weighted Fair Queuing (WFQ) provides low latency and good fairness, the virtual time update function has O(V) complexity for serving V busy flows. Start Potential Fair Queuing (SPFQ), which updates virtual time with a reduced complexity of O(log V), provides a fairness index very close to WFQ. Some other algorithms reduce virtual time update complexity further, but they degrade the fairness index significantly. VMPQ recalibrates virtual time using a virtual minimum potential, which is calculated with only a pre-computed constant and the finish time of the packet selected for transmission. This method requires O(1) complexity for the recalibration. Additionally, it does not affect the maximum latency and keeps fairness index to be almost identical to SPFQ.