CS Knowledge Base

References on CBQ (Class-Based Queueing)

• Floyd, S., and Jacobson, V., Link-sharing and Resource Management Models for Packet Networks (compressed postscript, pdf). IEEE/ACM Transactions on Networking, Vol. 3 No. 4, pp. 365-386, August 1995. Abstract.
  This paper focuses mainly on the link-sharing mechanisms in CBQ.
  
  
• Hoffman, D., Implementation report on the LBL/UCL/Sun CBQ kernel, Toronto IETF, July 1994.
  
  
• Wakeman, I., Ghosh, A., Crowcroft, J., Jacobson, V., and Floyd, S., Implementing Real Time Packet Forwarding Policies using Streams, Usenix 1995 Technical Conference, January 1995, New Orleans, Louisiana, pp. 71-82.
  This paper describes a Streams implementation of CBQ, and proposes a flexible and extensible mechanism for packet classification. Usenix also maintains an archival copy for Usenix members.
  
  
• Floyd, S., Notes on CBQ and Guaranteed Service. Draft document, July 1995.
  This note discusses one way of implementing guaranteed service using the CBQ framework.
  Floyd, S., Notes on the relationship between CBQ and RSVP. Draft note, October 1997.
  
  

Other References on Hierarchical Link-Sharing

• Jon C.R. Bennett and H. Zhang, Hierarchical Packet Fair Queueing Algorithms. To appear in IEEE/ACM Transactions on Networking. Also in Proceedings of SIGCOMM'96, Aug, 1996.
  The Hierarchical Packet Fair Queueing (H-PFQ) algorithm approximates the idealized Hierarchical Generalized Processor Sharing (H-GPS) model, which simultaneously supports hierarchical link-sharing and fair queueing.

• Ion Stoica, Hui Zhang, and T. S. Eugene Ng, A Hierarchical Fair Service Curve Algorithm for Link-Sharing, Real-Time and Priority Service. Proceedings of SIGCOMM'97.
  The Hierarchical Fair Service Curve (H-FSC) algorithm improves on H-PFQ by supporting priority service in addition to hierarchical link-sharing and fair queueing.

Publically-Available CBQ Implementations

• LBNL's CBQ code v1.1 , November 1995. This is a research prototype, designed to be easy to graft onto an existing system running BSD networking code. (The 11/95 changes to the original distribution are only to comments, not to the code itself.)

  The LBNL/SUN CBQ code v2.0 first released in May 1997 incorporates top-level link-sharing and weighted-round-robin scheduling within priority levels, and includes supporting user-level scheduling daemon and kernel code. The current release is v2.0h. The CBQ v2 code is primarily for Solaris, but the rm_class.[ch] files can also be compiled for SunOS 4.X. Notes on the CBQ Code and occasional bug-fixes to the v2 code are still in progress. The LBNL/SUN CBQ v2.0 distribution also includes a note on Using CBQ with RSVP.
  

• Linux has CBQ support in the 2.1-2.4 kernels, written by Alexey Kuznetsov, and based on the work in the ns simulator.
  
  
• Cho, K., ALTQ: Alternate Queueing for FreeBSD . This is a release of Alternate Queueing for BSD Unix, with many features, including CBQ, RED, WFQ, and RSVP stubs for CBQ. The archive of the altq mailing list includes a series of discussions about the implementation details of CBQ. Some of the bugs found are likely to be common to the LBNL CBQ implementations.
  
  
• F. Risso and B. Gevros, Operational and Performance Issues of a CBQ Router , CCR, October 1999.
  This paper gives a solid experimental evaluation of the ALTQ/CBQ implementation, including a discussion of parameter sensitivities, and several suggested modifications to the ALTQ kernel.

• Floyd, S., Notes of Class-Based Queueing: Setting Parameters (ps, PDF). . Informal notes, September 1995. These are informal notes about how to set the class parameters for CBQ.
  
  
• Hoffman, D., and Speer, M., An early access experimental release of Solaris RSVP/CBQ.
  This is a Solaris port of the ISI RSVP release, including the CBQ v2.0 packet scheduler.
  
  

Commercial CBQ Implementations

• Xedia (later acquired by Lucent) incorporates CBQ in their Access Point products for managed broadband access to the Internet.

• The Sitara Networks QoSWorks product line implements CBQ as one of four traffic management techniques.

Other CBQ-Related Papers

• K.M. Nichols and M. Laubach, On Quality of Service in an ATM-based HFC Architecture, IEEE ATM Workshop 96, San Franciso, August 1996.
  This paper discusses simulations with SCBQ (Schredded CBQ), a modified version of CBQ for an ATM network that schedules shreds of packets.

• C. Fragouli, V. Sivaraman and M. Srivastava, "Controlled Multimedia Wireless Link Sharing via Enhanced Class-Based Queueing with Channel-State-Dependent Packet Scheduling," in Proceedings of the Conference on Computer Communications (IEEE Infocom), pp. 572, March/April 1998.
  To address the controlled sharing of bandwidth on a wireless link, this paper combines a modified version of CBQ with Channel-State Dependent Packet Scheduling to address bandwidth sharing on wireless links that are subject to highly dynamic bandwidth variations.

CBQ Talks

• Floyd, S., Link-sharing and Resource Management Models for Packet Networks (viewgraphs). (postscript, pdf), February 7, 1995.
  
  
• Jacobson, V., Flexible, efficient resource management for datagram networks . Sun Microsystems, October 12, 1993.
  
  

CBQ Implementors.

Web pages on other scheduling algorithms

• Core-Stateless Fair Queueing.

Return to [Sally Floyd].
Last modified: January 2001. Links checked March 2008.