TC(8) Linux TC(8) NAME sfq−StochasticFairnessQueueing SYNOPSIS tcqdisc...[divisorhashtablesize][limitpackets][perturbseconds][quantumbytes][ flowsnumber][depthnumber][headdrop][redflowlimitbytes][minbytes][max bytes][avpktbytes][burstpackets][probabilityP][ecn][harddrop] DESCRIPTION StochasticFairnessQueueingisaclasslessqueueingdisciplineavailablefortrafficcontrolwiththe tc(8)command. SFQdoesnotshapetrafficbutonlyschedulesthetransmissionofpackets,basedon’flows’.The goalistoensurefairnesssothateachflowisabletosenddatainturn,thuspreventinganysingle flowfromdrowningouttherest. ThismayinfacthavesomeeffectinmitigatingaDenialofServiceattempt. SFQiswork-conservingandthereforealwaysdeliversapacketifithasoneavailable. ALGORITHM Onenqueueing,eachpacketisassignedtoahashbucket,basedonthepacketshashvalue.This hashvalueiseitherobtainedfromanexternalflowclassifier(usetcfiltertosetthem),ora defaultinternalclassifierifnoexternalclassifierhasbeenconfigured. Whentheinternalclassifierisused,sfquses (i)

Sourceaddress (ii)

Destinationaddress (iii)

SourceandDestinationport Iftheseareavailable.SFQknowsaboutipv4andipv6andalsoUDP,TCPandESP.Packets withotherprotocolsarehashedbasedonthe32bitsrepresentationoftheirdestinationandsource. AflowcorrespondsmostlytoaTCP/IPconnection. Eachofthesebucketsshouldrepresentauniqueflow.Becausemultipleflowsmaygethashedto thesamebucket,sfqsinternalhashingalgorithmmaybeperturbedatconfigurableintervalsso thattheunfairnesslastsonlyforashortwhile.Perturbationmayhowevercausesomeinadvertent packetreorderingtooccur.Afterlinux-3.3,thereisnopacketreorderingproblem,butpossible packetdropsifrehashinghitsonelimit(numberofflowsorpacketsperflow) Whendequeuing,eachhashbucketwithdataisqueriedinaroundrobinfashion. Beforelinux-3.3,thecompiletimemaximumlengthoftheSFQis128packets,whichcanbe spreadoveratmost128bucketsof1024available.Incaseofoverflow,tail-dropisperformedon thefullestbucket,thusmaintainingfairness. Afterlinux-3.3,maximumlengthofSFQis65535packets,anddivisorlimitis65536.Incaseof overflow,tail-dropisperformedonthefullestbucket,unlessheaddropwasrequested. PARAMETERS divisor Canbeusedtosetadifferenthashtablesize,availablefromkernel2.6.39onwards.The specifieddivisormustbeapoweroftwoandcannotbelargerthan65536.Defaultvalue: 1024. limit UpperlimitoftheSFQ.Canbeusedtoreducethedefaultlengthof127packets.After linux-3.3,itcanberaised. iproute2 24January2012 1 TC(8) Linux TC(8) depth Limitofpacketsperflow(afterlinux-3.3).Defaultto127andcanbelowered. perturb Intervalinsecondsforqueuealgorithmperturbation.Defaultsto0,whichmeansthatno perturbationoccurs.Donotsettoolowforeachperturbationmaycausesomepacket reorderingorlosses.Advisedvalue:60Thisvaluehasnoeffectwhenexternalflowclassificationisused.Itsbettertoincreasedivisorvaluetolowerriskofhashcollisions. quantum Amountofbytesaflowisallowedtodequeueduringaroundoftheroundrobinprocess. DefaultstotheMTUoftheinterfacewhichisalsotheadvisedvalueandtheminimum value. flows Afterlinux-3.3,itispossibletochangethedefaultlimitofflows.Defaultvalueis127 headdrop DefaultSFQbehavioristoperformtail-dropofpacketsfromaflow.Youcanaskahead-dropinstead,asthisisknowntoprovideabetterfeedbackforTCPflows. redflowlimit ConfiguretheoptionalREDmoduleontopofeachSFQflow.RandomEarlyDetection principleistoperformpacketmarksordropsinaprobabilisticway.(mantc-redfor detailsaboutRED) redflowlimitconfiguresthehardlimitonthereal(notaverage)queuesizeperSFQflowinbytes. min Averagequeuesizeatwhichmarkingbecomesapossibility.Defaultstomax/3 max Atthisaveragequeuesize,themarkingprobabilityismaximal.Defaultstoredflowlimit /4 probability Maximumprobabilityformarking,specifiedasafloatingpointnumberfrom0.0to1.0. Defaultvalueis0.02 avpkt Specifiedinbytes.Usedwithbursttodeterminethetimeconstantforaveragequeuesize calculations.Defaultvalueis1000 burst Usedfordetermininghowfasttheaveragequeuesizeisinfluencedbytherealqueuesize. Defaultvalueis: (2*min+max)/(3*avpkt) ecn REDcaneither’mark’or’drop’.ExplicitCongestionNotificationallowsREDtonotify remotehoststhattheirrateexceedstheamountofbandwidthavailable.Non-ECNcapa-blehostscanonlybenotifiedbydroppingapacket.Ifthisparameterisspecified,packets whichindicatethattheirhostshonorECNwillonlybemarkedandnotdropped,unless thequeuesizehitsdepthpackets. harddrop Ifaverageflowqueuesizeisabovemaxbytes,thisparameterforcesadropinsteadofecn marking. EXAMPLE&USAGE Toattachtodeviceppp0: #tcqdiscadddevppp0rootsfq PleasenotethatSFQ,likeallnon-shaping(work-conserving)qdiscs,isonlyusefulifitownsthe queue.Thisisthecasewhenthelinkspeedequalstheactuallyavailablebandwidth.Thisholds forregularphonemodems,ISDNconnectionsanddirectnon-switchedethernetlinks. Mostoften,cablemodemsandDSLdevicesdonotfallintothiscategory.Thesameholdsfor whenconnectedtoaswitchandtryingtosenddatatoacongestedsegmentalsoconnectedtothe switch. Inthiscase,theeffectivequeuedoesnotresidewithinLinuxandisthereforenotavailablefor iproute2 24January2012 2 TC(8) Linux TC(8) scheduling. EmbedSFQinaclassfulqdisctomakesureitownsthequeue. Itispossibletouseexternalclassifierswithsfq,forexampletohashtrafficbasedonlyon source/destinationipaddresses: #tcfilteradd...flowhashkeyssrc,dstperturb30divisor1024 Notethatthegivendivisorshouldmatchtheoneusedbysfq.Ifyouhavechangedthesfqdefault of1024,usethesamevaluefortheflowhashfilter,too. ExampleofsfqwithoptionalREDmode: #tcqdiscadddeveth0parent1:1handle10:sfqlimit3000flows512divisor16384 redflowlimit100000min8000max60000probability0.20ecnheaddrop SOURCE o PaulE.McKenney"StochasticFairnessQueuing",IEEEINFOCOMM’90Proceedings, SanFrancisco,1990. o PaulE.McKenney"StochasticFairnessQueuing","Interworking:ResearchandExperience",v.2,1991,p.113-131. o Seealso:M.ShreedharandGeorgeVarghese"EfficientFairQueuingusingDeficitRound Robin",Proc.SIGCOMM95. SEEALSO tc(8),tc-red(8) AUTHORS AlexeyN.Kuznetsov,<kuznet@ms2.inr.ac.ru>,EricDumazet<eric.dumazet@gmail.com>. Thismanpagemaintainedbyberthubert<ahu@ds9a.nl> iproute2 24January2012 3