Medium Starting Potential Fair Queueing for High-Speed Networks

Dong-Yong KWAK  Nam-Seok KO  Hong-Shik PARK  

IEICE TRANSACTIONS on Communications   Vol.E87-B    No.1    pp.188-191
Publication Date: 2004/01/01
Online ISSN: 
Print ISSN: 0916-8516
Type of Manuscript: LETTER
Category: Network
packet scheduling,  fair queueing,  

Full Text: PDF(263.8KB)>>
Buy this Article

This paper proposes an efficient fair queuing algorithm, called Medium Starting Potential Fair Queuing (MSPFQ), which has O(1) complexity for the virtual time computation while it has delay and fairness properties similar to Starting-Potential Fair Queueing (SPFQ). The key idea of MSPFQ algorithm is that it recalibrates the system virtual time to the medium value of the minimum possible virtual start times of HOL packets in each backlogged session. We show that MSPFQ belongs to the class of Rate-Proportional Server (RPS). In addition, we analytically prove that our algorithm has good delay and fairness properties.