SFB(8) Linux SFB(8) NAME sfb−StochasticFairBlue SYNOPSIS tcqdisc...bluerehashmillisecondsdbmillisecondslimitpacketsmaxpacketstargetpacketsincrementfloatdecrementfloatpenaltyratepacketspersecondpenaltyburstpackets DESCRIPTION StochasticFairBlueisaclasslessqdisctomanagecongestionbasedonpacketlossandlinkutilizationhistorywhiletryingtopreventnon-responsiveflows(i.e.flowsthatdonotreacttoconges-tionmarkingordroppedpackets)fromimpactingperformanceofresponsiveflows.UnlikeRED, wherethemarkingprobabilityhastobeconfigured,BLUEtriestodeterminetheidealmarking probabilityautomatically. ALGORITHM TheBLUEalgorithmmaintainsaprobabilitywhichisusedtomarkordroppacketsthatareto bequeued.Ifthequeueoverflows,themark/dropprobabilityisincreased.Ifthequeuebecomes empty,theprobabilityisdecreased.TheStochasticFairBlue(SFB)algorithmisdesignedto protectTCPflowsagainstnon-responsiveflows. ThisSFBimplementationmaintains8levelsof16binseachforaccounting.Eachflowismapped intoabinofeachlevelusingaper-levelhashvalue. Everybinmaintainsamarkingprobability,whichgetsincreasedordecreasedbasedonbinoccupancy.Ifthenumberofpacketsexceedsthesizeofthatbin,themarkingprobabilityisincreased. Ifthenumberdropstozero,itisdecreased. Themarkingprobabilityisbasedontheminimumvalueofallbinsaflowismappedinto,thus, whenaflowdoesnotrespondtomarkingorgradualpacketdrops,themarkingprobabilityquickly reachesone. Inthiscase,theflowisrate-limitedtopenaltyratepacketspersecond. LIMITATIONS DuetoSFBsnature,itispossibleforresponsiveflowstoshareallofitsbinswithanon-respon-siveflow,causingtheresponsiveflowtobemisidentifiedasbeingnon-responsive. Theprobabilityofaresponsiveflowtobemisidentifiedisdependentonthenumberofnonresponsiveflows,M.Itis(1-(1-(1/16.0))**M)**8,soforexamplewith10non-responsive flowsapproximately0.2%ofresponsiveflowswillbemisidentified. Tomitigatethis,SFBperformsperformsperiodicre-hashingtoavoidmisclassificationforpro-longedperiodsoftime. Thedefaulthashingmethodwillusesourceanddestinationipaddressesandportnumbersifpossible,andalsosupportstunnelingprotocols.Alternatively,anexternalclassifiercanbeconfigured,too. PARAMETERS rehash Timeintervalinmillisecondswhenqueueperturbationoccurstoavoiderroneouslydetectingunrelated,responsiveflowsasbeingpartofanon-responsiveflowforprolongedperi-odsoftime.Defaultsto10minutes. iproute2 August2011 1 SFB(8) Linux SFB(8) db Doublebufferingwarmupwaittime,inmilliseconds.Toavoiddestroyingtheprobability historywhenrehashingisperformed,thisimplementationmaintainsasecondsetoflevels/binsasdescribedinsection4.4oftheSFBreference.Whileonesetisusedtomanage thequeue,asecondsetiswarmedup:Wheneveraflowisthendeterminedtobenonresponsive,themarkingprobabilitiesinthesecondsetareupdated.Whentherehashing happens,thesebinswillbeusedtomanagethequeueandallnon-responsiveflowscanbe rate-limitedimmediately.Thisvaluedetermineshowmuchtimehastopassbeforethe 2ndsetwillstarttobewarmedup.Defaultstooneminute,shouldbelowerthan rehash. limit Hardlimitonthereal(notaverage)totalqueuesizeinpackets.Furtherpacketsare dropped.Defaultstothetransmitqueuelengthofthedevicetheqdiscisattachedto. max Maximumlengthofabucketsqueue,inpackets,beforepacketsstartbeingdropped. Shouldbesightlylargerthantarget,butshouldnotbesettovaluesexceeding1.5times thatoftarget.Defaultsto25. target Thedesiredaveragebinlength.Ifthebinqueuelengthreachesthisvalue,themarking probabilityisincreasedbyincrement.Thedefaultvaluedependsonthemaxsetting, withmaxsetto25targetwilldefaultto20. increment Avalueusedtoincreasethemarkingprobabilitywhenthequeueappearstobeover-used. Mustbebetween0and1.0.Defaultsto0.00050. decrement Valueusedtodecreasethemarkingprobabilitywhenthequeueisfoundtobeempty. Mustbebetween0and1.0.Defaultsto0.00005. penaltyrate Themaximumnumberofpacketsbelongingtoflowsidentifiedasbeingnon-responsive thatcanbeenqueuedpersecond.Oncethisnumberhasbeenreached,furtherpacketsof suchnon-responsiveflowsaredropped.Setthistoareasonablefractionofyouruplink throughput;thedefaultvalueof10packetsisprobablytoosmall. penaltyburst Thenumberofpacketsaflowispermittedtoexceedthepenaltyratebeforepacketsstart beingdropped.Defaultsto20packets. STATISTICS Thisqdiscexposesadditionalstatisticsvia’tc-sqdisc’output.Theseare: earlydrop Thenumberofpacketsdroppedbeforeaper-flowqueuewasfull. ratedrop Thenumberofpacketsdroppedbecauseofrate-limiting.Ifthisvalueishigh,thereare manynon-reactiveflowsbeingsentthroughsfb.Insuchcases,itmightbebetterto embedsfbwithinaclassfulqdisctobettercontrolsuchflowsusingadifferent,shaping qdisc. bucketdrop Thenumberofpacketsdroppedbecauseaper-flowqueuewasfull.Highbucketdropmay pointtoahighnumberofaggressive,short-livedflows. queuedrop Thenumberofpacketsdroppedduetoreachinglimit.Thisshouldnormallybe0. marked ThenumberofpacketsmarkedwithECN. iproute2 August2011 2 SFB(8) Linux SFB(8) maxqlen Thelengthofthecurrentlongestper-flow(virtual)queue. maxprob Themaximumper-flowdropprobability.1meansthatsomeflowshavebeendetectedas non-reactive. NOTES SFBautomaticallyenablesuseofExplicitCongestionNotification(ECN).Also,thisSFBimplementationdoesnotqueuepacketsitself.Rather,packetsareenqueuedtotheinnerqdisc(defaults topfifo).Becausesfbmaintainsvirtualqueuestates,theinnerqdiscmustnotdropapacketpreviouslyqueued.Furthermore,ifabucketsqueuehasaveryhighmarkingrate,thisimplementationwillstartdroppingpacketsinsteadofmarkingthem,assuchasituationpointstoeitherbad congestion,oranunresponsiveflow. EXAMPLE&USAGE Toattachtointerface$DEV,usingdefaultoptions: #tcqdiscadddev$DEVhandle1:rootsfb Onlyusedestinationipaddressesforassigningpacketstobins,perturbinghashresultsevery10 minutes: #tcfilteradddev$DEVparent1:handle1flowhashkeysdstperturb600 SEEALSO tc(8),tc-red(8),tc-sfq(8) SOURCES o W.Feng,D.Kandlur,D.Saha,K.Shin,BLUE:ANewClassofActiveQueueManagementAlgorithms,U.MichiganCSE-TR-387-99,April1999. AUTHORS ThisSFBimplementationwascontributedbyJuliuszChroboczekandEricDumazet. iproute2 August2011 3