{ "content": [ { "type": "text", "text": "# CBQ (info)\n\n## NAME\n\nCBQ - Class Based Queueing\n\n## SYNOPSIS\n\ntc qdisc ... dev dev ( parent classid | root) [ handle major: ] cbq\navpkt bytes bandwidth rate [ cell bytes ] [ ewma log ] [ mpu bytes ]\ntc class ... dev dev parent major:[minor] [ classid major:minor ] cbq\nallot bytes [ bandwidth rate ] [ rate rate ] prio priority [ weight\nweight ] [ minburst packets ] [ maxburst packets ] [ ewma log ] [ cell\nbytes ] avpkt bytes [ mpu bytes ] [ bounded isolated ] [ split handle &\ndefmap defmap ] [ estimator interval timeconstant ]\n\n## DESCRIPTION\n\nClass Based Queueing is a classful qdisc that implements a rich\nlinksharing hierarchy of classes. It contains shaping elements as well\nas prioritizing capabilities. Shaping is performed using link idle time\ncalculations based on the timing of dequeue events and underlying link\nbandwidth.\n\n## Sections\n\n- **NAME**\n- **SYNOPSIS**\n- **DESCRIPTION**\n- **SHAPING ALGORITHM**\n- **CLASSIFICATION**\n- **CLASSIFICATION ALGORITHM**\n- **LINK SHARING ALGORITHM**\n- **QDISC**\n- **CLASSES**\n- **SOURCES**\n- **SEE ALSO**\n- **AUTHOR**\n\nUse structuredContent.sections for detailed options, examples, and full documentation.\n" } ], "structuredContent": { "command": "CBQ", "section": "", "mode": "info", "summary": "CBQ - Class Based Queueing", "synopsis": "tc qdisc ... dev dev ( parent classid | root) [ handle major: ] cbq\navpkt bytes bandwidth rate [ cell bytes ] [ ewma log ] [ mpu bytes ]\ntc class ... dev dev parent major:[minor] [ classid major:minor ] cbq\nallot bytes [ bandwidth rate ] [ rate rate ] prio priority [ weight\nweight ] [ minburst packets ] [ maxburst packets ] [ ewma log ] [ cell\nbytes ] avpkt bytes [ mpu bytes ] [ bounded isolated ] [ split handle &\ndefmap defmap ] [ estimator interval timeconstant ]", "tldr_summary": null, "tldr_examples": [], "tldr_source": null, "flags": [], "examples": [], "see_also": [ { "name": "tc", "section": "8", "url": "https://www.chedong.com/phpMan.php/man/tc/8/json" } ], "section_outline": [ { "name": "NAME", "lines": 2, "subsections": [] }, { "name": "SYNOPSIS", "lines": 9, "subsections": [] }, { "name": "DESCRIPTION", "lines": 6, "subsections": [] }, { "name": "SHAPING ALGORITHM", "lines": 46, "subsections": [] }, { "name": "CLASSIFICATION", "lines": 25, "subsections": [] }, { "name": "CLASSIFICATION ALGORITHM", "lines": 49, "subsections": [] }, { "name": "LINK SHARING ALGORITHM", "lines": 22, "subsections": [] }, { "name": "QDISC", "lines": 40, "subsections": [] }, { "name": "CLASSES", "lines": 105, "subsections": [] }, { "name": "SOURCES", "lines": 12, "subsections": [] }, { "name": "SEE ALSO", "lines": 2, "subsections": [] }, { "name": "AUTHOR", "lines": 4, "subsections": [] } ], "sections": { "NAME": { "content": "CBQ - Class Based Queueing\n", "subsections": [] }, "SYNOPSIS": { "content": "tc qdisc ... dev dev ( parent classid | root) [ handle major: ] cbq\navpkt bytes bandwidth rate [ cell bytes ] [ ewma log ] [ mpu bytes ]\n\ntc class ... dev dev parent major:[minor] [ classid major:minor ] cbq\nallot bytes [ bandwidth rate ] [ rate rate ] prio priority [ weight\nweight ] [ minburst packets ] [ maxburst packets ] [ ewma log ] [ cell\nbytes ] avpkt bytes [ mpu bytes ] [ bounded isolated ] [ split handle &\ndefmap defmap ] [ estimator interval timeconstant ]\n", "subsections": [] }, "DESCRIPTION": { "content": "Class Based Queueing is a classful qdisc that implements a rich\nlinksharing hierarchy of classes. It contains shaping elements as well\nas prioritizing capabilities. Shaping is performed using link idle time\ncalculations based on the timing of dequeue events and underlying link\nbandwidth.\n", "subsections": [] }, "SHAPING ALGORITHM": { "content": "Shaping is done using link idle time calculations, and actions taken if\nthese calculations deviate from set limits.\n\nWhen shaping a 10mbit/s connection to 1mbit/s, the link will be idle\n90% of the time. If it isn't, it needs to be throttled so that it IS\nidle 90% of the time.\n\nFrom the kernel's perspective, this is hard to measure, so CBQ instead\nderives the idle time from the number of microseconds (in fact,\njiffies) that elapse between requests from the device driver for more\ndata. Combined with the knowledge of packet sizes, this is used to ap-\nproximate how full or empty the link is.\n\nThis is rather circumspect and doesn't always arrive at proper results.\nFor example, what is the actual link speed of an interface that is not\nreally able to transmit the full 100mbit/s of data, perhaps because of\na badly implemented driver? A PCMCIA network card will also never\nachieve 100mbit/s because of the way the bus is designed - again, how\ndo we calculate the idle time?\n\nThe physical link bandwidth may be ill defined in case of not-quite-\nreal network devices like PPP over Ethernet or PPTP over TCP/IP. The\neffective bandwidth in that case is probably determined by the effi-\nciency of pipes to userspace - which not defined.\n\nDuring operations, the effective idletime is measured using an exponen-\ntial weighted moving average (EWMA), which considers recent packets to\nbe exponentially more important than past ones. The Unix loadaverage is\ncalculated in the same way.\n\nThe calculated idle time is subtracted from the EWMA measured one, the\nresulting number is called 'avgidle'. A perfectly loaded link has an\navgidle of zero: packets arrive exactly at the calculated interval.\n\nAn overloaded link has a negative avgidle and if it gets too negative,\nCBQ throttles and is then 'overlimit'.\n\nConversely, an idle link might amass a huge avgidle, which would then\nallow infinite bandwidths after a few hours of silence. To prevent\nthis, avgidle is capped at maxidle.\n\nIf overlimit, in theory, the CBQ could throttle itself for exactly the\namount of time that was calculated to pass between packets, and then\npass one packet, and throttle again. Due to timer resolution con-\nstraints, this may not be feasible, see the minburst parameter below.\n", "subsections": [] }, "CLASSIFICATION": { "content": "Within the one CBQ instance many classes may exist. Each of these\nclasses contains another qdisc, by default tc-pfifo(8).\n\nWhen enqueueing a packet, CBQ starts at the root and uses various meth-\nods to determine which class should receive the data. If a verdict is\nreached, this process is repeated for the recipient class which might\nhave further means of classifying traffic to its children, if any.\n\nCBQ has the following methods available to classify a packet to any\nchild classes.\n\n(i) skb->priority class encoding. Can be set from userspace by an\napplication with the SOPRIORITY setsockopt. The skb->priority\nclass encoding only applies if the skb->priority holds a ma-\njor:minor handle of an existing class within this qdisc.\n\n(ii) tc filters attached to the class.\n\n(iii) The defmap of a class, as set with the split & defmap parame-\nters. The defmap may contain instructions for each possible\nLinux packet priority.\n\nEach class also has a level. Leaf nodes, attached to the bottom of the\nclass hierarchy, have a level of 0.\n", "subsections": [] }, "CLASSIFICATION ALGORITHM": { "content": "Classification is a loop, which terminates when a leaf class is found.\nAt any point the loop may jump to the fallback algorithm.\n\nThe loop consists of the following steps:\n\n(i) If the packet is generated locally and has a valid classid en-\ncoded within its skb->priority, choose it and terminate.\n\n(ii) Consult the tc filters, if any, attached to this child. If these\nreturn a class which is not a leaf class, restart loop from the\nclass returned. If it is a leaf, choose it and terminate.\n\n(iii) If the tc filters did not return a class, but did return a clas-\nsid, try to find a class with that id within this qdisc. Check\nif the found class is of a lower level than the current class.\nIf so, and the returned class is not a leaf node, restart the\nloop at the found class. If it is a leaf node, terminate. If we\nfound an upward reference to a higher level, enter the fallback\nalgorithm.\n\n(iv) If the tc filters did not return a class, nor a valid reference\nto one, consider the minor number of the reference to be the\npriority. Retrieve a class from the defmap of this class for the\npriority. If this did not contain a class, consult the defmap of\nthis class for the BESTEFFORT class. If this is an upward ref-\nerence, or no BESTEFFORT class was defined, enter the fallback\nalgorithm. If a valid class was found, and it is not a leaf\nnode, restart the loop at this class. If it is a leaf, choose it\nand terminate. If neither the priority distilled from the clas-\nsid, nor the BESTEFFORT priority yielded a class, enter the\nfallback algorithm.\n\nThe fallback algorithm resides outside of the loop and is as follows.\n\n(i) Consult the defmap of the class at which the jump to fallback\noccurred. If the defmap contains a class for the priority of the\nclass (which is related to the TOS field), choose this class and\nterminate.\n\n(ii) Consult the map for a class for the BESTEFFORT priority. If\nfound, choose it, and terminate.\n\n(iii) Choose the class at which break out to the fallback algorithm\noccurred. Terminate.\n\nThe packet is enqueued to the class which was chosen when either algo-\nrithm terminated. It is therefore possible for a packet to be enqueued\n*not* at a leaf node, but in the middle of the hierarchy.\n", "subsections": [] }, "LINK SHARING ALGORITHM": { "content": "When dequeuing for sending to the network device, CBQ decides which of\nits classes will be allowed to send. It does so with a Weighted Round\nRobin process in which each class with packets gets a chance to send in\nturn. The WRR process starts by asking the highest priority classes\n(lowest numerically - highest semantically) for packets, and will con-\ntinue to do so until they have no more data to offer, in which case the\nprocess repeats for lower priorities.\n\nCERTAINTY ENDS HERE, ANK PLEASE HELP\n\nEach class is not allowed to send at length though - they can only de-\nqueue a configurable amount of data during each round.\n\nIf a class is about to go overlimit, and it is not bounded it will try\nto borrow avgidle from siblings that are not isolated. This process is\nrepeated from the bottom upwards. If a class is unable to borrow enough\navgidle to send a packet, it is throttled and not asked for a packet\nfor enough time for the avgidle to increase above zero.\n\nI REALLY NEED HELP FIGURING THIS OUT. REST OF DOCUMENT IS PRETTY CER-\nTAIN AGAIN.\n", "subsections": [] }, "QDISC": { "content": "The root qdisc of a CBQ class tree has the following parameters:\n\nparent major:minor | root\nThis mandatory parameter determines the place of the CBQ in-\nstance, either at the root of an interface or within an existing\nclass.\n\nhandle major:\nLike all other qdiscs, the CBQ can be assigned a handle. Should\nconsist only of a major number, followed by a colon. Optional.\n\navpkt bytes\nFor calculations, the average packet size must be known. It is\nsilently capped at a minimum of 2/3 of the interface MTU. Manda-\ntory.\n\nbandwidth rate\nTo determine the idle time, CBQ must know the bandwidth of your\nunderlying physical interface, or parent qdisc. This is a vital\nparameter, more about it later. Mandatory.\n\ncell The cell size determines he granularity of packet transmission\ntime calculations. Has a sensible default.\n\nmpu A zero sized packet may still take time to transmit. This value\nis the lower cap for packet transmission time calculations -\npackets smaller than this value are still deemed to have this\nsize. Defaults to zero.\n\newma log\nWhen CBQ needs to measure the average idle time, it does so us-\ning an Exponentially Weighted Moving Average which smooths out\nmeasurements into a moving average. The EWMA LOG determines how\nmuch smoothing occurs. Defaults to 5. Lower values imply greater\nsensitivity. Must be between 0 and 31.\n\nA CBQ qdisc does not shape out of its own accord. It only needs to know\ncertain parameters about the underlying link. Actual shaping is done in\nclasses.\n", "subsections": [] }, "CLASSES": { "content": "Classes have a host of parameters to configure their operation.\n\nparent major:minor\nPlace of this class within the hierarchy. If attached directly\nto a qdisc and not to another class, minor can be omitted.\nMandatory.\n\nclassid major:minor\nLike qdiscs, classes can be named. The major number must be\nequal to the major number of the qdisc to which it belongs. Op-\ntional, but needed if this class is going to have children.\n\nweight weight\nWhen dequeuing to the interface, classes are tried for traffic\nin a round-robin fashion. Classes with a higher configured qdisc\nwill generally have more traffic to offer during each round, so\nit makes sense to allow it to dequeue more traffic. All weights\nunder a class are normalized, so only the ratios matter. De-\nfaults to the configured rate, unless the priority of this class\nis maximal, in which case it is set to 1.\n\nallot bytes\nAllot specifies how many bytes a qdisc can dequeue during each\nround of the process. This parameter is weighted using the\nrenormalized class weight described above.\n\npriority priority\nIn the round-robin process, classes with the lowest priority\nfield are tried for packets first. Mandatory.\n\nrate rate\nMaximum rate this class and all its children combined can send\nat. Mandatory.\n\nbandwidth rate\nThis is different from the bandwidth specified when creating a\nCBQ disc. Only used to determine maxidle and offtime, which are\nonly calculated when specifying maxburst or minburst. Mandatory\nif specifying maxburst or minburst.\n\nmaxburst\nThis number of packets is used to calculate maxidle so that when\navgidle is at maxidle, this number of average packets can be\nburst before avgidle drops to 0. Set it higher to be more toler-\nant of bursts. You can't set maxidle directly, only via this pa-\nrameter.\n\nminburst\nAs mentioned before, CBQ needs to throttle in case of overlimit.\nThe ideal solution is to do so for exactly the calculated idle\ntime, and pass 1 packet. However, Unix kernels generally have a\nhard time scheduling events shorter than 10ms, so it is better\nto throttle for a longer period, and then pass minburst packets\nin one go, and then sleep minburst times longer.\n\nThe time to wait is called the offtime. Higher values of min-\nburst lead to more accurate shaping in the long term, but to\nbigger bursts at millisecond timescales.\n\nminidle\nIf avgidle is below 0, we are overlimits and need to wait until\navgidle will be big enough to send one packet. To prevent a sud-\nden burst from shutting down the link for a prolonged period of\ntime, avgidle is reset to minidle if it gets too low.\n\nMinidle is specified in negative microseconds, so 10 means that\navgidle is capped at -10us.\n\nbounded\nSignifies that this class will not borrow bandwidth from its\nsiblings.\n\nisolated\nMeans that this class will not borrow bandwidth to its siblings\n\nsplit major:minor & defmap bitmap[/bitmap]\nIf consulting filters attached to a class did not give a ver-\ndict, CBQ can also classify based on the packet's priority.\nThere are 16 priorities available, numbered from 0 to 15.\n\nThe defmap specifies which priorities this class wants to re-\nceive, specified as a bitmap. The Least Significant Bit corre-\nsponds to priority zero. The split parameter tells CBQ at which\nclass the decision must be made, which should be a (grand)parent\nof the class you are adding.\n\nAs an example, 'tc class add ... classid 10:1 cbq .. split 10:0\ndefmap c0' configures class 10:0 to send packets with priorities\n6 and 7 to 10:1.\n\nThe complimentary configuration would then be: 'tc class add ...\nclassid 10:2 cbq ... split 10:0 defmap 3f' Which would send all\npackets 0, 1, 2, 3, 4 and 5 to 10:1.\n\nestimator interval timeconstant\nCBQ can measure how much bandwidth each class is using, which tc\nfilters can use to classify packets with. In order to determine\nthe bandwidth it uses a very simple estimator that measures once\nevery interval microseconds how much traffic has passed. This\nagain is a EWMA, for which the time constant can be specified,\nalso in microseconds. The time constant corresponds to the slug-\ngishness of the measurement or, conversely, to the sensitivity\nof the average to short bursts. Higher values mean less sensi-\ntivity.\n", "subsections": [] }, "SOURCES": { "content": "o Sally Floyd and Van Jacobson, \"Link-sharing and Resource Manage-\nment Models for Packet Networks\", IEEE/ACM Transactions on Net-\nworking, Vol.3, No.4, 1995\n\no Sally Floyd, \"Notes on CBQ and Guarantee Service\", 1995\n\no Sally Floyd, \"Notes on Class-Based Queueing: Setting Parame-\nters\", 1996\n\no Sally Floyd and Michael Speer, \"Experimental Results for Class-\nBased Queueing\", 1998, not published.\n", "subsections": [] }, "SEE ALSO": { "content": "tc(8)\n", "subsections": [] }, "AUTHOR": { "content": "Alexey N. Kuznetsov, . This manpage maintained by\nbert hubert \n\niproute2 8 December 2001 CBQ(8)", "subsections": [] } } } }