CBQ(8) Linux CBQ(8) NAME CBQ−ClassBasedQueueing SYNOPSIS tcqdisc...devdev(parentclassid|root)[handlemajor:]cbqavpktbytesbandwidth rate[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 Shapingisdoneusinglinkidletimecalculations,andactionstakenifthesecalculationsdeviate fromsetlimits. Whenshapinga10mbit/sconnectionto1mbit/s,thelinkwillbeidle90%ofthetime.Ifitisn’t, itneedstobethrottledsothatitISidle90%ofthetime. Fromthekernel’sperspective,thisishardtomeasure,soCBQinsteadderivestheidletimefrom thenumberofmicroseconds(infact,jiffies)thatelapsebetweenrequestsfromthedevicedriver formoredata.Combinedwiththeknowledgeofpacketsizes,thisisusedtoapproximatehowfull oremptythelinkis. Thisisrathercircumspectanddoesn’talwaysarriveatproperresults.Forexample,whatisthe actuallinkspeedofaninterfacethatisnotreallyabletotransmitthefull100mbit/sofdata,perhapsbecauseofabadlyimplementeddriver?APCMCIAnetworkcardwillalsoneverachieve 100mbit/sbecauseofthewaythebusisdesigned-again,howdowecalculatetheidletime? Thephysicallinkbandwidthmaybeilldefinedincaseofnot-quite-realnetworkdeviceslikePPP overEthernetorPPTPoverTCP/IP.Theeffectivebandwidthinthatcaseisprobablydeterminedbytheefficiencyofpipestouserspace-whichnotdefined. 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.Duetotimer iproute2 8December2001 1 CBQ(8) Linux CBQ(8) resolutionconstraints,thismaynotbefeasible,seetheminburstparameterbelow. CLASSIFICATION WithintheoneCBQinstancemanyclassesmayexist.Eachoftheseclassescontainsanother qdisc,bydefaulttc-pfifo(8). Whenenqueueingapacket,CBQstartsattherootandusesvariousmethodstodeterminewhich classshouldreceivethedata.Ifaverdictisreached,thisprocessisrepeatedfortherecipientclass whichmighthavefurthermeansofclassifyingtraffictoitschildren,ifany. CBQhasthefollowingmethodsavailabletoclassifyapackettoanychildclasses. (i) skb->priorityclassencoding.Canbesetfromuserspacebyanapplicationwiththe SOPRIORITYsetsockopt.Theskb->priorityclassencodingonlyappliesifthe skb->priorityholdsamajor:minorhandleofanexistingclasswithinthisqdisc. (ii) tcfiltersattachedtotheclass. (iii)

Thedefmapofaclass,assetwiththesplit&defmapparameters.Thedefmapmay containinstructionsforeachpossibleLinuxpacketpriority. Eachclassalsohasalevel.Leafnodes,attachedtothebottomoftheclasshierarchy,havea levelof0. CLASSIFICATIONALGORITHM Classificationisaloop,whichterminateswhenaleafclassisfound.Atanypointtheloopmay jumptothefallbackalgorithm. Theloopconsistsofthefollowingsteps: (i)

Ifthepacketisgeneratedlocallyandhasavalidclassidencodedwithinitsskb->prior-ity,chooseitandterminate. (ii)

Consultthetcfilters,ifany,attachedtothischild.Ifthesereturnaclasswhichisnota leafclass,restartloopfromtheclassreturned.Ifitisaleaf,chooseitandterminate. (iii)

Ifthetcfiltersdidnotreturnaclass,butdidreturnaclassid,trytofindaclasswith thatidwithinthisqdisc.Checkifthefoundclassisofalowerlevelthanthecurrent class.Ifso,andthereturnedclassisnotaleafnode,restarttheloopatthefoundclass.If itisaleafnode,terminate.Ifwefoundanupwardreferencetoahigherlevel,enterthe fallbackalgorithm. (iv)

Ifthetcfiltersdidnotreturnaclass,noravalidreferencetoone,considertheminor numberofthereferencetobethepriority.Retrieveaclassfromthedefmapofthisclass forthepriority.Ifthisdidnotcontainaclass,consultthedefmapofthisclassforthe BESTEFFORTclass.Ifthisisanupwardreference,ornoBESTEFFORTclasswas defined,enterthefallbackalgorithm.Ifavalidclasswasfound,anditisnotaleafnode, restarttheloopatthisclass.Ifitisaleaf,chooseitandterminate.Ifneitherthepriority distilledfromtheclassid,northeBESTEFFORTpriorityyieldedaclass,enterthe fallbackalgorithm. Thefallbackalgorithmresidesoutsideoftheloopandisasfollows. (i)

Consultthedefmapoftheclassatwhichthejumptofallbackoccured.Ifthedefmapcontainsaclassforthepriorityoftheclass(whichisrelatedtotheTOSfield),choosethis classandterminate. (ii)

ConsultthemapforaclassfortheBESTEFFORTpriority.Iffound,chooseit,and terminate. iproute2 8December2001 2 CBQ(8) Linux CBQ(8) (iii)

Choosetheclassatwhichbreakouttothefallbackalgorithmoccurred.Terminate. Thepacketisenqueuedtotheclasswhichwaschosenwheneitheralgorithmterminated.Itis thereforepossibleforapackettobeenqueued*not*ataleafnode,butinthemiddleofthehierarchy. LINKSHARINGALGORITHM Whendequeuingforsendingtothenetworkdevice,CBQdecideswhichofitsclasseswillbe allowedtosend.ItdoessowithaWeightedRoundRobinprocessinwhicheachclasswithpackets getsachancetosendinturn.TheWRRprocessstartsbyaskingthehighestpriorityclasses(lowestnumerically-highestsemantically)forpackets,andwillcontinuetodosountiltheyhaveno moredatatooffer,inwhichcasetheprocessrepeatsforlowerpriorities. CERTAINTYENDSHERE,ANKPLEASEHELP Eachclassisnotallowedtosendatlengththough-theycanonlydequeueaconfigurableamount ofdataduringeachround. Ifaclassisabouttogooverlimit,anditisnotboundeditwilltrytoborrowavgidlefromsiblingsthatarenotisolated.Thisprocessisrepeatedfromthebottomupwards.Ifaclassis unabletoborrowenoughavgidletosendapacket,itisthrottledandnotaskedforapacketfor enoughtimefortheavgidletoincreaseabovezero. IREALLYNEEDHELPFIGURINGTHISOUT.RESTOFDOCUMENTIS PRETTYCERTAINAGAIN. QDISC TherootqdiscofaCBQclasstreehasthefollowingparameters: parentmajor:minor|root ThismandatoryparameterdeterminestheplaceoftheCBQinstance,eitherattheroot ofaninterfaceorwithinanexistingclass. handlemajor: Likeallotherqdiscs,theCBQcanbeassignedahandle.Shouldconsistonlyofamajor number,followedbyacolon.Optional. avpktbytes Forcalculations,theaveragepacketsizemustbeknown.Itissilentlycappedataminimumof2/3oftheinterfaceMTU.Mandatory. bandwidthrate Todeterminetheidletime,CBQmustknowthebandwidthofyourunderlyingphysical interface,orparentqdisc.Thisisavitalparameter,moreaboutitlater.Mandatory. cell Thecellsizedetermineshegranularityofpackettransmissiontimecalculations.Hasa sensibledefault. mpu Azerosizedpacketmaystilltaketimetotransmit.Thisvalueisthelowercapforpacket transmissiontimecalculations-packetssmallerthanthisvaluearestilldeemedtohave thissize.Defaultstozero. ewmalog WhenCBQneedstomeasuretheaverageidletime,itdoessousinganExponentially WeightedMovingAveragewhichsmoothsoutmeasurementsintoamovingaverage.The EWMALOGdetermineshowmuchsmoothingoccurs.Defaultsto5.Lowervaluesimply greatersensitivity.Mustbebetween0and31. iproute2 8December2001 3 CBQ(8) Linux CBQ(8) 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. prioritypriority Intheround-robinprocess,classeswiththelowestpriorityfieldaretriedforpacketsfirst. Mandatory. raterate Maximumratethisclassandallitschildrencombinedcansendat.Mandatory. bandwidthrate ThisisdifferentfromthebandwidthspecifiedwhencreatingaCBQdisc.Onlyusedto determinemaxidleandofftime,whichareonlycalculatedwhenspecifyingmaxburstor minburst.Mandatoryifspecifyingmaxburstorminburst. maxburst Thisnumberofpacketsisusedtocalculatemaxidlesothatwhenavgidleisatmaxidle, thisnumberofaveragepacketscanbeburstbeforeavgidledropsto0.Setithighertobe moretolerantofbursts.Youcan’tsetmaxidledirectly,onlyviathisparameter. minburst Asmentionedbefore,CBQneedstothrottleincaseofoverlimit.Theidealsolutionisto dosoforexactlythecalculatedidletime,andpass1packet.However,Unixkernelsgenerallyhaveahardtimeschedulingeventsshorterthan10ms,soitisbettertothrottlefora longerperiod,andthenpassminburstpacketsinonego,andthensleepminbursttimes longer. Thetimetowaitiscalledtheofftime.Highervaluesofminburstleadtomoreaccurate shapinginthelongterm,buttobiggerburstsatmillisecondtimescales. iproute2 8December2001 4 CBQ(8) Linux CBQ(8) minidle Ifavgidleisbelow0,weareoverlimitsandneedtowaituntilavgidlewillbebigenough tosendonepacket.Topreventasuddenburstfromshuttingdownthelinkforaprolongedperiodoftime,avgidleisresettominidleifitgetstoolow. Minidleisspecifiedinnegativemicroseconds,so10meansthatavgidleiscappedat-10us. 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. SOURCES o SallyFloydandVanJacobson,"Link-sharingandResourceManagementModelsfor PacketNetworks",IEEE/ACMTransactionsonNetworking,Vol.3,No.4,1995 o SallyFloyd,"NotesonCBQandGuaranteeService",1995 o SallyFloyd,"NotesonClass-BasedQueueing:SettingParameters",1996 o SallyFloydandMichaelSpeer,"ExperimentalResultsforClass-BasedQueueing",1998, notpublished. iproute2 8December2001 5 CBQ(8) Linux CBQ(8) SEEALSO tc(8) AUTHOR AlexeyN.Kuznetsov,<kuznet@ms2.inr.ac.ru>.Thismanpagemaintainedbyberthubert <ahu@ds9a.nl> iproute2 8December2001 6