Affiliations: Samsung Advanced Institute of Technology, CNL, Nong-Seo-dong, Yong-In, South Korea. E-mails: jake7.lee@gmail.com, dkjeong@ee.snu.ac.kr | Department of Computer Engineering, Hongik University, Seoul, South Korea. E-mail: shim@cs.hongik.ac.kr
Note: [] Corresponding author: Chul Ki Lee, PhD, R&D Staff Member, Communication & Networking Lab., Samsung Advanced Institute of Technology, CNL, Nong-Seo-dong, Yong-In, South Korea. Tel.: +82 31 280 9534; Fax: +82 31 280 9555.
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.
Keywords: Fair queuing, virtual time update, O(1) complexity
