CBQ(8) Linux CBQ(8) NAME CBQ−ClassBasedQueueing SYNOPSIS tcqdisc...devdev(parentclassid|root)[handlemajor:]cbq[allotbytes]avpkt bytesbandwidthrate[cellbytes][ewmalog][mpubytes] tcclass...devdevparentmajor:[minor][classidmajor:minor]cbqallotbytes[bandwidthrate][raterate]priopriority[weightweight][minburstpackets][maxburst packets][ewmalog][cellbytes]avpktbytes[mpubytes][boundedisolated][split handle&defmapdefmap][estimatorintervaltimeconstant] DESCRIPTION ClassBasedQueueingisaclassfulqdiscthatimplementsarichlinksharinghierarchyofclasses.It containsshapingelementsaswellasprioritizingcapabilities.Shapingisperformedusinglinkidle timecalculationsbasedonthetimingofdequeueeventsandunderlyinglinkbandwidth. SHAPINGALGORITHM Whenshapinga10mbit/sconnectionto1mbit/s,thelinkwillbeidle90%ofthetime.Ifitisn’t, itneedstobethrottledsothatitISidle90%ofthetime. Duringoperations,theeffectiveidletimeismeasuredusinganexponentialweightedmovingaverage(EWMA),whichconsidersrecentpacketstobeexponentiallymoreimportantthanpastones. TheUnixloadaverageiscalculatedinthesameway. ThecalculatedidletimeissubtractedfromtheEWMAmeasuredone,theresultingnumberis called’avgidle’.Aperfectlyloadedlinkhasanavgidleofzero:packetsarriveexactlyatthecalculatedinterval. Anoverloadedlinkhasanegativeavgidleandifitgetstoonegative,CBQthrottlesandisthen ’overlimit’. Conversely,anidlelinkmightamassahugeavgidle,whichwouldthenallowinfinitebandwidths afterafewhoursofsilence.Topreventthis,avgidleiscappedatmaxidle. Ifoverlimit,intheory,theCBQcouldthrottleitselfforexactlytheamountoftimethatwascalculatedtopassbetweenpackets,andthenpassonepacket,andthrottleagain.Duetotimerresolutionconstraints,thismaynotbefeasible,seetheminburstparameterbelow. CLASSIFICATION WithintheoneCBQinstancemanyclassesmayexist.Eachoftheseclassescontainsanother qdisc,bydefaulttc-pfifo(8). Whenenqueueingapacket,CBQstartsattherootandusesvariousmethodstodeterminewhich classshouldreceivethedata. Intheabsenceofuncommonconfigurationoptions,theprocessisrathereasy.Ateachnodewe lookforaninstruction,andthengototheclasstheinstructionrefersusto.Iftheclassfoundisa barrenleaf-node(withoutchildren),weenqueuethepacketthere.Ifitisnotyetaleafnode,we dothewholethingoveragainstartingfromthatnode. Thefollowingactionsareperformed,inorderateachnodewevisit,untilonesendsustoanother node,orterminatestheprocess. iproute2 16December2001 1 CBQ(8) Linux CBQ(8) (i)

Consultfiltersattachedtotheclass.Ifsenttoaleafnode,wearedone.Otherwise, restart. (ii)

Consultthedefmapforthepriorityassignedtothispacket,whichdependsontheTOS bits.Checkifthereferralisleafless,otherwiserestart. (iii)

Askthedefmapforinstructionsforthe’besteffort’priority.Checktheanswerforleafness,otherwiserestart. (iv)

Ifnoneoftheabovereturnedwithaninstruction,enqueueatthisnode. Thisalgorithmmakessurethatapacketalwaysendsupsomewhere,evenwhileyouarebusy buildingyourconfiguration. Formoredetails,seetc-cbq-details(8). LINKSHARINGALGORITHM Whendequeuingforsendingtothenetworkdevice,CBQdecideswhichofitsclasseswillbe allowedtosend.ItdoessowithaWeightedRoundRobinprocessinwhicheachclasswithpackets getsachancetosendinturn.TheWRRprocessstartsbyaskingthehighestpriorityclasses(lowestnumerically-highestsemantically)forpackets,andwillcontinuetodosountiltheyhaveno moredatatooffer,inwhichcasetheprocessrepeatsforlowerpriorities. Classesbydefaultborrowbandwidthfromtheirsiblings.Aclasscanbepreventedfromdoingso bydeclaringit’bounded’.Aclasscanalsoindicateitsunwillingnesstolendoutbandwidthby being’isolated’. QDISC TherootofaCBQqdiscclasstreehasthefollowingparameters: parentmajor:minor|root ThismandatoryparameterdeterminestheplaceoftheCBQinstance,eitherattheroot ofaninterfaceorwithinanexistingclass. handlemajor: Likeallotherqdiscs,theCBQcanbeassignedahandle.Shouldconsistonlyofamajor number,followedbyacolon.Optional,butveryusefulifclasseswillbegeneratedwithin thisqdisc. allotbytes Thisallotmentisthe’chunkiness’oflinksharingandisusedfordeterminingpackettransmissiontimetables.Theqdiscallotdiffersslightlyfromtheclassallotdiscussedbelow. Optional.Defaultstoareasonablevalue,relatedtoavpkt. avpktbytes Theaveragesizeofapacketisneededforcalculatingmaxidle,andisalsousedformaking sure’allot’hasasafevalue.Mandatory. bandwidthrate Todeterminetheidletime,CBQmustknowthebandwidthofyourunderlyingphysical interface,orparentqdisc.Thisisavitalparameter,moreaboutitlater.Mandatory. cell Thecellsizedetermineshegranularityofpackettransmissiontimecalculations.Hasa sensibledefault. mpu Azerosizedpacketmaystilltaketimetotransmit.Thisvalueisthelowercapforpacket transmissiontimecalculations-packetssmallerthanthisvaluearestilldeemedtohave thissize.Defaultstozero. iproute2 16December2001 2 CBQ(8) Linux CBQ(8) ewmalog WhenCBQneedstomeasuretheaverageidletime,itdoessousinganExponentially WeightedMovingAveragewhichsmoothsoutmeasurementsintoamovingaverage.The EWMALOGdetermineshowmuchsmoothingoccurs.Lowervaluesimplygreatersensitivity.Mustbebetween0and31.Defaultsto5. ACBQqdiscdoesnotshapeoutofitsownaccord.Itonlyneedstoknowcertainparameters abouttheunderlyinglink.Actualshapingisdoneinclasses. CLASSES Classeshaveahostofparameterstoconfiguretheiroperation. parentmajor:minor Placeofthisclasswithinthehierarchy.Ifattacheddirectlytoaqdiscandnottoanother class,minorcanbeomitted.Mandatory. classidmajor:minor Likeqdiscs,classescanbenamed.Themajornumbermustbeequaltothemajornumber oftheqdisctowhichitbelongs.Optional,butneededifthisclassisgoingtohavechildren. weightweight Whendequeuingtotheinterface,classesaretriedfortrafficinaround-robinfashion. Classeswithahigherconfiguredqdiscwillgenerallyhavemoretraffictoofferduringeach round,soitmakessensetoallowittodequeuemoretraffic.Allweightsunderaclassare normalized,soonlytheratiosmatter.Defaultstotheconfiguredrate,unlessthepriority ofthisclassismaximal,inwhichcaseitissetto1. allotbytes Allotspecifieshowmanybytesaqdisccandequeueduringeachroundoftheprocess. Thisparameterisweightedusingtherenormalizedclassweightdescribedabove.Silently cappedataminimumof3/2avpkt.Mandatory. priopriority Intheround-robinprocess,classeswiththelowestpriorityfieldaretriedforpacketsfirst. Mandatory. avpkt SeetheQDISCsection. raterate Maximumratethisclassandallitschildrencombinedcansendat.Mandatory. bandwidthrate ThisisdifferentfromthebandwidthspecifiedwhencreatingaCBQdisc!Onlyusedto determinemaxidleandofftime,whichareonlycalculatedwhenspecifyingmaxburstor minburst.Mandatoryifspecifyingmaxburstorminburst. maxburst Thisnumberofpacketsisusedtocalculatemaxidlesothatwhenavgidleisatmaxidle, thisnumberofaveragepacketscanbeburstbeforeavgidledropsto0.Setithighertobe moretolerantofbursts.Youcan’tsetmaxidledirectly,onlyviathisparameter. iproute2 16December2001 3 CBQ(8) Linux CBQ(8) minburst Asmentionedbefore,CBQneedstothrottleincaseofoverlimit.Theidealsolutionisto dosoforexactlythecalculatedidletime,andpass1packet.However,Unixkernelsgenerallyhaveahardtimeschedulingeventsshorterthan10ms,soitisbettertothrottlefora longerperiod,andthenpassminburstpacketsinonego,andthensleepminbursttimes longer. Thetimetowaitiscalledtheofftime.Highervaluesofminburstleadtomoreaccurate shapinginthelongterm,buttobiggerburstsatmillisecondtimescales.Optional. minidle Ifavgidleisbelow0,weareoverlimitsandneedtowaituntilavgidlewillbebigenough tosendonepacket.Topreventasuddenburstfromshuttingdownthelinkforaprolongedperiodoftime,avgidleisresettominidleifitgetstoolow. Minidleisspecifiedinnegativemicroseconds,so10meansthatavgidleiscappedat-10us. Optional. bounded Signifiesthatthisclasswillnotborrowbandwidthfromitssiblings. isolated Meansthatthisclasswillnotborrowbandwidthtoitssiblings splitmajor:minor&defmapbitmap[/bitmap] Ifconsultingfiltersattachedtoaclassdidnotgiveaverdict,CBQcanalsoclassifybased onthepacket’spriority.Thereare16prioritiesavailable,numberedfrom0to15. Thedefmapspecifieswhichprioritiesthisclasswantstoreceive,specifiedasabitmap. TheLeastSignificantBitcorrespondstopriorityzero.ThesplitparametertellsCBQat whichclassthedecisionmustbemade,whichshouldbea(grand)parentoftheclassyou areadding. Asanexample,’tcclassadd...classid10:1cbq..split10:0defmapc0’configuresclass 10:0tosendpacketswithpriorities6and7to10:1. Thecomplimentaryconfigurationwouldthenbe:’tcclassadd...classid10:2cbq...split 10:0defmap3f’Whichwouldsendallpackets0,1,2,3,4and5to10:1. estimatorintervaltimeconstant CBQcanmeasurehowmuchbandwidtheachclassisusing,whichtcfilterscanuseto classifypacketswith.Inordertodeterminethebandwidthitusesaverysimpleestimator thatmeasuresonceeveryintervalmicrosecondshowmuchtraffichaspassed.Thisagain isaEWMA,forwhichthetimeconstantcanbespecified,alsoinmicroseconds.Thetime constantcorrespondstothesluggishnessofthemeasurementor,conversely,tothesensitivityoftheaveragetoshortbursts.Highervaluesmeanlesssensitivity. BUGS Theactualbandwidthoftheunderlyinglinkmaynotbeknown,forexampleinthecaseofPPoE orPPTPconnectionswhichinfactmaysendoverapipe,insteadofoveraphysicaldevice.CBQ isquiteresilienttomajorerrorsintheconfiguredbandwidth,probablyathecostofcoarsershaping. Defaultkernelsrelyoncoarsetiminginformationformakingdecisions.Thesemaymakeshaping iproute2 16December2001 4 CBQ(8) Linux CBQ(8) preciseinthelongterm,butinaccurateonsecondlongscales. Seetc-cbq-details(8)forhintsonhowtoimprovethis. SOURCES o SallyFloydandVanJacobson,"Link-sharingandResourceManagementModelsfor PacketNetworks",IEEE/ACMTransactionsonNetworking,Vol.3,No.4,1995 o SallyFloyd,"NotesonCBQandGuaranteedService",1995 o SallyFloyd,"NotesonClass-BasedQueueing:SettingParameters",1996 o SallyFloydandMichaelSpeer,"ExperimentalResultsforClass-BasedQueueing",1998, notpublished. SEEALSO tc(8) AUTHOR AlexeyN.Kuznetsov,<kuznet@ms2.inr.ac.ru>.Thismanpagemaintainedbyberthubert <ahu@ds9a.nl> iproute2 16December2001 5