Using CBT

The Theory

CBT (Class Based Thresholds) is a set of modifications to the behavior of the outbound IP queues in a router. In principle, CBT has multiple configurable classes. The basic idea of CBT is that each class is allocated a share of the outbound link. This allocation is achieved by setting thresholds on the average number of packets each class can have enqueued.

There are several equations used to calculate the parameters of CBT. Although the description below should suffice to show how it is done, there is a "notes" document (PDF) that discusses the derivation of the CBT equations. To get it, click here. It is only intended as added information and shouldn't be necessary to use CBT.

To set these thresholds, one must know the desired target latency, the desired bandwidth allocation for the class, and average packet size for each class. The target latency applies to all classes (as it limits the overall depth of the queue). It is the maximum average queue-induced latency that is tolerable. The bandwidth allocation for the classes must sum to the capacity of the outbound link. When you know the desired latency (L), bandwidth (B(j)), and packet-size (P(j)) for a given class, j, you can calculate the packet threshold (Th(j)) using the following equation.


In addition to the threshold parameter, each class must be configured with a weight (w(j)) which determines the amount of influence each new measurement of the queue's size has on the average. The average packet size (P(j)) for the class is also an input parameter.

NOTE: P(j) is used along with the threshold value to compute the drain-rate of the given class from queue. This drain-rate value is used to update the average when the class has no packets enqueued (to predict how many samples would have been recorded during the idle interval.)

The Implementation

CBT is implemented as one of queueing alternatives within the infrastructure provided by ALTQ. In this implementation, it has 3 classes. The classifiers for these classes are hard-coded in the kernel. It would be nice to extend these classifiers to be configurable to do some pattern matching based on a configuration file, but that is not currently the case so you are limited to these classes. These classes are TCP (all TCP packets), multimedia (UDP packets sent to ports 5000-5009), and other (everything else). Additionally, the drop policy for each class is *actually* implemented as a RED policy, with multiple modes including probabilistic drops. HOWEVER, in actual use we always set ThMin and ThMax to the same value for the classes multimedia and other. This gives the appearance of a binary policy, with packets enqueued if the average is below the threshold and packets dropped if the average is above the threshold.

How CBT runs

The ALTQ design includes many alternative queueing techniques within a given kernel. By default, the kernel simply uses traditions FIFO (drop-tail) queueing. To activate a given queueing technique one runs a daemon program (as root) to make the necessary system calls to configure and activate that technique. In the case of CBT, this program is called cbtd. The actual command line to activate the daemon looks like:

# cbtd -l 240 -w 256 -p 10 -t 30 -T 80 -F cbtd.conf.sample -d xl0 >& cbtd.out &

The relevant arguments to the program are:

-l length of the queue (number of packet buffers to allocate)
-w weighting for the RED average (for TCP)
-p 1/maxp (for RED)
-t th_min
-T th_max
-f the input file defining the class based thresholds (SEE BELOW)
-d daemon mode (run in the background)
< > xl0  The last argument is the name of the interface to attach to.

(-w, -p, -T, and -t specify defaults that are overridden by values from the input file so you can ignore them - just use the values given above.)

After running your experiment, either look up the PID of the cbt process and do a "kill -2 " OR use the "end" command to send a kill signal of "2" to cbtd. It looks up the command in the ps table to find the pid and then kills the process. (You want to use 2, not 9 though.) For example:

end 2 cbtd

The Input File:

The input file to the CBT daemon specifies the parameters for each class. This is where you specify the threshold values and average packet sizes for each class. There is one line for each class plus a "default" class which is irrelevant in this implementation since "other" catches any packets not classified as TCP or Multimedia. The classes are numbered as shown in the comment section of the sample file below. The line to configure a class is a comma delimited list of parameters. They are:

class_number, avg_pktsize, weight, inv_p, min_th, max_th, maxqlen

A sample configuration for the class TCP might look like:


The parameters shown mean:
  1. TCP is class 3.
  2. The average packet size is 1507 bytes (including packet headers).
  3. The weight factor when computing the average is 1/256.
  4. In probabilistic mode, maxp = 1/10, expressed her as 1/maxp = 10.
  5. The min_th is 5 and
  6. The max_th is 49.47.
  7. The maximum queue length is 240.

NOTE: just use 5 for min_th for any TCP class. max_th is the one computed as Th(TCP).

For the clases "other" and "multimedia", inv_p is irrelevant and min_th should equal max_th and be set to Th(j) as calculated using the equations discussed above.

The weight value must be a power of 2. I have no good rule for how to set the weight parameter. My heuristic is to set the weight for TCP to 1/256 because I expect TCP packets to arrive frequently so know single packet needs to carry too much weight. Because multimedia represents a small fraction of the capacity, packet arrivals should be less common so I want more recent samples to count for more so the weight is 1/16. Finally, to guard against other's frequent arrivals, I want to closely associate the current behavior with the average so it's weight is 1/4.

This is what an input file looks like:

# -*- perl -*-
# (Above is just to get a mode that highlights comments in emacs)
# <-- Comments MUST have a # sign as the FIRST character.
# the first column is the class number these parameter settings are for.
# class 0 is default 
# class 1 is multimedia
# class 2 is other 
# class 3 is TCP
# class, avg_pktsize, weight, inv_p, min_th, max_th, maxqlen
# Blank lines are not ok, but blank comment lines are. 
# Default - default settings don't really come into play because the other 
# three classes cover EVERYTHING.
# MULTIMEDIA - setting min and max to the same value eliminates the early drop mode.
# Note the weight of any sample for multimedia is 1/16
# OTHER - weight of a sample is 1/4
# TCP - weight is 1/256 (with all of the other traffic mixed in this seemed more 
# reasonable
# No blank lines after this!


To actually use CBT, obtain the tar file: /usr/dirt/tar-files/CBT.tgz

In this bundle you should find the following files which you will need in order to use CBT:

cbtd.README.html	<-- this file
kernel.CBT.1000		<-- the kernel binary with CBT extensions
cbtd			<-- the cbt daemon to activate and configure CBT
cbtd.conf.sample	<-- a sample configuration file
end			<-- a tool to kill processes by name, not PID

It also includes these two files which are simply there for completeness. You should not need to unpack them:

sys-altq.tgz		<-- Src for kernel with CBT extensions 
altq-1.1.3-CBT.tgz	<-- Src for ALTQ tools including cbt-tools 

To run an experiment with CBT:

  1. Install the kernel on the router you intend to run CBT on and reboot.
  2. Place the cbtd, cbtd.conf, and cbtd.conf.sample on the machine's local disk. (I usually use /usr/tmp/parris/.)
  3. Compute the desired threshold values for each class as described above.
  4. Update your copy of cbtd.conf.sample to have the correct average packet sizes and threshold values. I do NOT recommend changing the queue size, weights, or inv_p unless you really know why you want to.
  5. Invoke cbtd (as root)with a command line similar to:
    cbtd -l 240 -w 256 -p 10 -t 30 -T 80 -F cbtd.conf.sample -d xl0 >& cbtd.out &
    You should use full path names wherever possible since you are running as root.
  6. Start your traffic generators (configured to send to the appropriate ports to match the desired classes) and run your measurements.
  7. Shutdown your traffic generators.
  8. Stop cbtd with a INTR signal using "kill -2 " or "end 2 cbtd".

Other DiRT documents
Author: Mark Parris