Unix/Linux Go Back    


Linux 2.6 - man page for tc-cbq-details (linux section 8)

Linux & Unix Commands - Search Man Pages
Man Page or Keyword Search:   man
Select Man Page Set:       apropos Keyword Search (sections above)


CBQ(8)					      Linux					   CBQ(8)

NAME
       CBQ - Class Based Queueing

SYNOPSIS
       tc  qdisc ... dev dev ( parent classid | root) [ handle major: ] cbq avpkt bytes bandwidth
       rate [ cell bytes ] [ ewma log ] [ mpu bytes ]

       tc class ... dev dev parent major:[minor] [ classid major:minor ] cbq allot bytes [  band-
       width rate ] [ rate rate ] prio priority [ weight weight ] [ minburst packets ] [ maxburst
       packets ] [ ewma log ] [ cell bytes ] avpkt bytes [ mpu bytes ] [  bounded  isolated  ]	[
       split handle & defmap defmap ] [ estimator interval timeconstant ]

DESCRIPTION
       Class  Based  Queueing is a classful qdisc that implements a rich linksharing hierarchy of
       classes.  It contains shaping elements as well as prioritizing capabilities.   Shaping  is
       performed  using  link  idle  time  calculations based on the timing of dequeue events and
       underlying link bandwidth.

SHAPING ALGORITHM
       Shaping is done using link idle time calculations, and actions taken if these calculations
       deviate from set limits.

       When  shaping  a 10mbit/s connection to 1mbit/s, the link will be idle 90% of the time. If
       it isn't, it needs to be throttled so that it IS idle 90% of the time.

       From the kernel's perspective, this is hard to measure, so CBQ instead  derives	the  idle
       time from the number of microseconds (in fact, jiffies) that elapse between  requests from
       the device driver for more data. Combined with the  knowledge of  packet  sizes,  this  is
       used to approximate how full or empty the link is.

       This  is rather circumspect and doesn't always arrive at proper results. For example, what
       is the actual link speed of an interface that is not really  able  to  transmit	the  full
       100mbit/s  of  data,  perhaps because of a badly implemented driver? A PCMCIA network card
       will also never achieve 100mbit/s because of the way the bus is designed - again,  how  do
       we calculate the idle time?

       The  physical  link bandwidth may be ill defined in case of not-quite-real network devices
       like PPP over Ethernet or PPTP over TCP/IP. The effective bandwidth in that case is proba-
       bly determined by the efficiency of pipes to userspace - which not defined.

       During operations, the effective idletime is measured using an exponential weighted moving
       average (EWMA), which considers recent packets to be  exponentially  more  important  than
       past ones. The Unix loadaverage is calculated in the same way.

       The calculated idle time is subtracted from the EWMA measured one, the resulting number is
       called 'avgidle'. A perfectly loaded link has an avgidle of zero: packets  arrive  exactly
       at the calculated interval.

       An  overloaded  link has a negative avgidle and if it gets too negative, CBQ throttles and
       is then 'overlimit'.

       Conversely, an idle link might amass a huge avgidle, which would then allow infinite band-
       widths after a few hours of silence. To prevent this, avgidle is capped at maxidle.

       If overlimit, in theory, the CBQ could throttle itself for exactly the amount of time that
       was calculated to pass between packets, and then pass one packet, and throttle again.  Due
       to  timer  resolution  constraints,  this  may not be feasible, see the minburst parameter
       below.

CLASSIFICATION
       Within the one CBQ instance many classes may exist. Each of these classes contains another
       qdisc, by default tc-pfifo(8).

       When  enqueueing  a  packet,  CBQ starts at the root and uses various methods to determine
       which class should receive the data. If a verdict is reached, this process is repeated for
       the recipient class which might have further means of classifying traffic to its children,
       if any.

       CBQ has the following methods available to classify a packet to any child classes.

       (i)    skb->priority class encoding.  Can be set from userspace by an application with the
	      SO_PRIORITY  setsockopt.	 The  skb->priority  class  encoding  only applies if the
	      skb->priority holds a major:minor handle of an existing class within  this qdisc.

       (ii)   tc filters attached to the class.

       (iii)  The defmap of a class, as set with the split & defmap parameters.  The  defmap  may
	      contain instructions for each possible Linux packet priority.

       Each  class  also has a level.  Leaf nodes, attached to the bottom of the class hierarchy,
       have a level of 0.

CLASSIFICATION ALGORITHM
       Classification is a loop, which terminates when a leaf class is found. At  any  point  the
       loop may jump to the fallback algorithm.

       The loop consists of the following steps:

       (i)    If  the  packet  is  generated  locally  and has a valid classid encoded within its
	      skb->priority, choose it and terminate.

       (ii)   Consult the tc filters, if any, attached to this child. If  these  return  a  class
	      which  is not a leaf class, restart loop from the class returned.  If it is a leaf,
	      choose it and terminate.

       (iii)  If the tc filters did not return a class, but did return a classid, try to  find	a
	      class with that id within this qdisc.  Check if the found class is of a lower level
	      than the current class. If so, and the returned class is not a leaf  node,  restart
	      the  loop  at  the  found  class.  If it is a leaf node, terminate.  If we found an
	      upward reference to a higher level, enter the fallback algorithm.

       (iv)   If the tc filters did not return a class, nor a valid reference  to  one,  consider
	      the  minor  number  of  the reference to be the priority. Retrieve a class from the
	      defmap of this class for the priority. If this did not contain a class, consult the
	      defmap  of this class for the BEST_EFFORT class. If this is an upward reference, or
	      no BEST_EFFORT class was defined, enter the fallback algorithm. If  a  valid  class
	      was  found,  and	it is not a leaf node, restart the loop at this class. If it is a
	      leaf, choose it and terminate. If neither the priority distilled from the  classid,
	      nor the BEST_EFFORT priority yielded a class, enter the fallback algorithm.

       The fallback algorithm resides outside of the loop and is as follows.

       (i)    Consult  the  defmap  of	the  class  at which the jump to fallback occured. If the
	      defmap contains a class for the priority of the class (which is related to the  TOS
	      field), choose this class and terminate.

       (ii)   Consult  the map for a class for the BEST_EFFORT priority. If found, choose it, and
	      terminate.

       (iii)  Choose the class at which break out to the fallback algorithm occurred. Terminate.

       The packet is enqueued to the class which was chosen when either algorithm terminated.  It
       is  therefore possible for a packet to be enqueued *not* at a leaf node, but in the middle
       of the hierarchy.

LINK SHARING ALGORITHM
       When dequeuing for sending to the network device, CBQ decides which of its classes will be
       allowed	to  send. It does so with a Weighted Round Robin process in which each class with
       packets gets a chance to send in turn. The WRR process starts by asking the highest prior-
       ity  classes (lowest numerically - highest semantically) for packets, and will continue to
       do so until they have no more data to offer, in which case the process repeats  for  lower
       priorities.

       CERTAINTY ENDS HERE, ANK PLEASE HELP

       Each  class is not allowed to send at length though - they can only dequeue a configurable
       amount of data during each round.

       If a class is about to go overlimit, and it is not bounded it will try to  borrow  avgidle
       from siblings that are not isolated.  This process is repeated from the bottom upwards. If
       a class is unable to borrow enough avgidle to send a packet, it is throttled and not asked
       for a packet for enough time for the avgidle to increase above zero.

       I REALLY NEED HELP FIGURING THIS OUT. REST OF DOCUMENT IS PRETTY CERTAIN AGAIN.

QDISC
       The root qdisc of a CBQ class tree has the following parameters:

       parent major:minor | root
	      This  mandatory  parameter  determines the place of the CBQ instance, either at the
	      root of an interface or within an existing class.

       handle major:
	      Like all other qdiscs, the CBQ can be assigned a handle. Should consist only  of	a
	      major number, followed by a colon. Optional.

       avpkt bytes
	      For calculations, the average packet size must be known. It is silently capped at a
	      minimum of 2/3 of the interface MTU. Mandatory.

       bandwidth rate
	      To determine the idle time, CBQ must know the bandwidth of your underlying physical
	      interface,  or parent qdisc. This is a vital parameter, more about it later. Manda-
	      tory.

       cell   The cell size determines he granularity of packet transmission  time  calculations.
	      Has a sensible default.

       mpu    A  zero  sized  packet may still take time to transmit. This value is the lower cap
	      for packet transmission time calculations - packets smaller  than  this  value  are
	      still deemed to have this size. Defaults to zero.

       ewma log
	      When  CBQ needs to measure the average idle time, it does so using an Exponentially
	      Weighted Moving Average which smoothes out measurements into a moving average.  The
	      EWMA  LOG  determines  how much smoothing occurs. Defaults to 5. Lower values imply
	      greater sensitivity. Must be between 0 and 31.

       A CBQ qdisc does not shape out of its own accord. It only needs to know certain parameters
       about the underlying link. Actual shaping is done in classes.

CLASSES
       Classes have a host of parameters to configure their operation.

       parent major:minor
	      Place  of  this class within the hierarchy. If attached directly to a qdisc and not
	      to another class, minor can be omitted. Mandatory.

       classid major:minor
	      Like qdiscs, classes can be named. The major number must be equal to the major num-
	      ber  of  the qdisc to which it belongs. Optional, but needed if this class is going
	      to have children.

       weight weight
	      When dequeuing to the interface, classes are tried for  traffic  in  a  round-robin
	      fashion. Classes with a higher configured qdisc will generally have more traffic to
	      offer during each round, so it makes sense to allow it to dequeue more traffic. All
	      weights  under  a  class are normalized, so only the ratios matter. Defaults to the
	      configured rate, unless the priority of this class is maximal, in which case it  is
	      set to 1.

       allot bytes
	      Allot  specifies	how  many  bytes  a  qdisc  can  dequeue during each round of the
	      process. This parameter is weighted using the renormalized class	weight	described
	      above.

       priority priority
	      In  the  round-robin  process, classes with the lowest priority field are tried for
	      packets first. Mandatory.

       rate rate
	      Maximum rate this class and all its children combined can send at. Mandatory.

       bandwidth rate
	      This is different from the bandwidth specified when creating a CBQ disc. Only  used
	      to  determine  maxidle  and  offtime,  which  are  only  calculated when specifying
	      maxburst or minburst. Mandatory if specifying maxburst or minburst.

       maxburst
	      This number of packets is used to calculate maxidle so  that  when  avgidle  is  at
	      maxidle, this number of average packets can be burst before avgidle drops to 0. Set
	      it higher to be more tolerant of bursts. You can't set maxidle directly,	only  via
	      this parameter.

       minburst
	      As mentioned before, CBQ needs to throttle in case of overlimit. The ideal solution
	      is to do so for exactly the calculated idle time, and pass 1 packet. However,  Unix
	      kernels  generally  have	a hard time scheduling events shorter than 10ms, so it is
	      better to throttle for a longer period, and then pass minburst packets in  one  go,
	      and then sleep minburst times longer.

	      The  time  to  wait  is  called the offtime. Higher values of minburst lead to more
	      accurate shaping in the long term, but to bigger bursts at millisecond timescales.

       minidle
	      If avgidle is below 0, we are overlimits and need to wait until avgidle will be big
	      enough  to  send	one packet. To prevent a sudden burst from shutting down the link
	      for a prolonged period of time, avgidle is reset to minidle if it gets too low.

	      Minidle is specified in negative microseconds, so 10 means that avgidle  is  capped
	      at -10us.

       bounded
	      Signifies that this class will not borrow bandwidth from its siblings.

       isolated
	      Means that this class will not borrow bandwidth to its siblings

       split major:minor & defmap bitmap[/bitmap]
	      If  consulting  filters  attached  to  a class did not give a verdict, CBQ can also
	      classify based on the packet's priority. There are 16  priorities  available,  num-
	      bered from 0 to 15.

	      The  defmap  specifies which priorities this class wants to receive, specified as a
	      bitmap. The Least Significant Bit corresponds to priority zero. The split parameter
	      tells CBQ at which class the decision must be made, which should be a (grand)parent
	      of the class you are adding.

	      As an example, 'tc class add ... classid 10:1 cbq .. split 10:0 defmap c0'  config-
	      ures class 10:0 to send packets with priorities 6 and 7 to 10:1.

	      The  complimentary  configuration would then be: 'tc class add ... classid 10:2 cbq
	      ... split 10:0 defmap 3f' Which would send all packets 0, 1, 2, 3, 4 and 5 to 10:1.

       estimator interval timeconstant
	      CBQ can measure how much bandwidth each class is using, which tc filters can use to
	      classify	packets  with.	In order to determine the bandwidth it uses a very simple
	      estimator that measures once every  interval  microseconds  how  much  traffic  has
	      passed. This again is a EWMA, for which the time constant can be specified, also in
	      microseconds. The time constant corresponds to the sluggishness of the  measurement
	      or,  conversely,	to  the sensitivity of the average to short bursts. Higher values
	      mean less sensitivity.

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

       o      Sally Floyd, "Notes on CBQ and Guarantee Service", 1995

       o      Sally Floyd, "Notes on Class-Based Queueing: Setting Parameters", 1996

       o      Sally  Floyd  and  Michael  Speer, "Experimental Results for Class-Based Queueing",
	      1998, not published.

SEE ALSO
       tc(8)

AUTHOR
       Alexey N. Kuznetsov,  <kuznet@ms2.inr.ac.ru>.  This  manpage  maintained  by  bert  hubert
       <ahu@ds9a.nl>

iproute2				 8 December 2001				   CBQ(8)
Unix & Linux Commands & Man Pages : ©2000 - 2018 Unix and Linux Forums


All times are GMT -4. The time now is 03:52 PM.