Credit-based fair queueing (CBFQ): a simple service-scheduling algorithm for packet-switched networks
- 1 October 2001
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 9 (5) , 591-604
- https://doi.org/10.1109/90.958328
Abstract
This paper proposes a simple rate-based scheduling algorithm for packet-switched networks. Using a set of counters to keep track of the credits accumulated by each traffic flow, the bandwidth share allocated to each flow, and the size of the head-of-line (HOL) packets of the different flows, the algorithm decides which flow to serve next. Our proposed algorithm requires on average a smaller complexity than the most interesting alternative ones while guaranteeing comparable fairness, delay, and delay jitter bounds. To further reduce the complexity, a simplified version (CBFQ-F) of the general algorithm is also proposed for networks with fixed packet lengths, such as ATM, by relaxing the fairness bound by a negligibly small amount.Keywords
This publication has 11 references indexed in Scilit:
- Carry-over round robin: a simple cell scheduling mechanism for ATM networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- WF/sup 2/Q: worst-case fair weighted fair queueingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Hardware-efficient fair queueing architectures for high-speed networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Start-time fair queueing: a scheduling algorithm for integrated services packet switching networksIEEE/ACM Transactions on Networking, 1997
- Credit-based fair queueing for ATM networksElectronics Letters, 1996
- Efficient fair queuing using deficit round-robinIEEE/ACM Transactions on Networking, 1996
- Virtual spacing for flexible traffic controlInternational Journal of Communication Systems, 1994
- A generalized processor sharing approach to flow control in integrated services networks: the single-node caseIEEE/ACM Transactions on Networking, 1993
- VirtualClockACM Transactions on Computer Systems, 1991
- Analysis and simulation of a fair queueing algorithmPublished by Association for Computing Machinery (ACM) ,1989