Dear reader, I'm not updating these pages anymore. If you have tc or ip related questions, you can post them on the LARTC mailing list.



From help-file :
CBQ packet scheduler
CONFIG_NET_SCH_CBQ
  Say Y here if you want to use the Class-Based Queueing (CBQ) packet
  scheduling algorithm for some of your network devices. This
  algorithm classifies the waiting packets into a tree-like hierarchy
  of classes; the leaves of this tree are in turn scheduled by
  separate algorithms (called "disciplines" in this context).
 
  See the top of net/sched/sch_cbq.c for references about the CBQ
  algorithm.
 
  CBQ is a commonly used scheduler, so if you're unsure, you should
  say Y here. Then say Y to all the queueing algorithms below that you
  want to use as CBQ disciplines. Then say Y to "Packet classifier
  API" and say Y to all the classifiers you want to use; a classifier
  is a routine that allows you to sort your outgoing traffic into
  classes based on a certain criterion.
 
  This code is also available as a module called sch_cbq.o ( = code
  which can be inserted in and removed from the running kernel
  whenever you want). If you want to compile it as a module, say M
  here and read Documentation/modules.txt.

From source-files :
Class-Based Queueing (CBQ) algorithm.
=======================================

Sources: [1] Sally Floyd and Van Jacobson, "Link-sharing and Resource
         Management Models for Packet Networks",
     IEEE/ACM Transactions on Networking, Vol.3, No.4, 1995

         [2] Sally Floyd, "Notes on CBQ and Guaranted Service", 1995

         [3] Sally Floyd, "Notes on Class-Based Queueing: Setting
     Parameters", 1996

     [4] Sally Floyd and Michael Speer, "Experimental Results
     for Class-Based Queueing", 1998, not published.
 
-----------------------------------------------------------------------
 
Algorithm skeleton was taken from NS simulator cbq.cc.
If someone wants to check this code against the LBL version,
he should take into account that ONLY the skeleton was borrowed,
the implementation is different. Particularly:
 
--- The WRR algorithm is different. Our version looks more
    reasonable (I hope) and works when quanta are allowed to be
    less than MTU, which is always the case when real time classes
    have small rates. Note, that the statement of [3] is
    incomplete, delay may actually be estimated even if class
    per-round allotment is less than MTU. Namely, if per-round
    allotment is W*r_i, and r_1+...+r_k = r < 1

delay_i <= ([MTU/(W*r_i)]*W*r + W*r + k*MTU)/B

In the worst case we have IntServ estimate with D = W*r+k*MTU
and C = MTU*r. The proof (if correct at all) is trivial.


--- It seems that cbq-2.0 is not very accurate. At least, I cannot
interpret some places, which look like wrong translations
from NS. Anyone is advised to find these differences
and explain to me, why I am wrong 8).

--- Linux has no EOI event, so that we cannot estimate true class
idle time. Workaround is to consider the next dequeue event
as sign that previous packet is finished. This is wrong because of
internal device queueing, but on a permanently loaded link it is true.
Moreover, combined with clock integrator, this scheme looks
very close to an ideal solution.