TC(8) Linux TC(8) NAME sfq−StochasticFairnessQueueing SYNOPSIS tcqdisc...perturbsecondsquantumbytes DESCRIPTION StochasticFairnessQueueingisaclasslessqueueingdisciplineavailablefortrafficcontrolwiththe tc(8)command. SFQdoesnotshapetrafficbutonlyschedulesthetransmissionofpackets,basedon’flows’.The goalistoensurefairnesssothateachflowisabletosenddatainturn,thuspreventinganysingle flowfromdrowningouttherest. ThismayinfacthavesomeeffectinmitigatingaDenialofServiceattempt. SFQiswork-conservingandthereforealwaysdeliversapacketifithasoneavailable. ALGORITHM Onenqueueing,eachpacketisassignedtoahashbucket,basedon (i)Sourceaddress (ii)Destinationaddress (iii)Sourceport Iftheseareavailable.SFQknowsaboutipv4andipv6andalsoUDP,TCPandESP.Packets withotherprotocolsarehashedbasedonthe32bitsrepresentationoftheirdestinationandthe sockettheybelongto.AflowcorrespondsmostlytoaTCP/IPconnection. Eachofthesebucketsshouldrepresentauniqueflow.Becausemultipleflowsmaygethashedto thesamebucket,thehashingalgorithmisperturbedatconfigurableintervalssothattheunfairnesslastsonlyforashortwhile.Perturbationmayhowevercausesomeinadvertentpacket reorderingtooccur. Whendequeuing,eachhashbucketwithdataisqueriedinaroundrobinfashion. ThecompiletimemaximumlengthoftheSFQis128packets,whichcanbespreadoveratmost 128bucketsof1024available.Incaseofoverflow,tail-dropisperformedonthefullestbucket,thus maintainingfairness. PARAMETERS perturb Intervalinsecondsforqueuealgorithmperturbation.Defaultsto0,whichmeansthatno perturbationoccurs.Donotsettoolowforeachperturbationmaycausesomepacket reordering.Advisedvalue:10 quantum Amountofbytesaflowisallowedtodequeueduringaroundoftheroundrobinprocess. DefaultstotheMTUoftheinterfacewhichisalsotheadvisedvalueandtheminimum value. EXAMPLE&USAGE Toattachtodeviceppp0: #tcqdiscadddevppp0rootsfqperturb10 PleasenotethatSFQ,likeallnon-shaping(work-conserving)qdiscs,isonlyusefulifitownsthe iproute2 8December2001 1 TC(8) Linux TC(8) queue.Thisisthecasewhenthelinkspeedequalstheactuallyavailablebandwidth.Thisholds forregularphonemodems,ISDNconnectionsanddirectnon-switchedethernetlinks. Mostoften,cablemodemsandDSLdevicesdonotfallintothiscategory.Thesameholdsfor whenconnectedtoaswitchandtryingtosenddatatoacongestedsegmentalsoconnectedtothe switch. Inthiscase,theeffectivequeuedoesnotresidewithinLinuxandisthereforenotavailablefor scheduling. EmbedSFQinaclassfulqdisctomakesureitownsthequeue. SOURCE oPaulE.McKenney"StochasticFairnessQueuing",IEEEINFOCOMM’90Proceedings, SanFrancisco,1990. oPaulE.McKenney"StochasticFairnessQueuing","Interworking:ResearchandExperience",v.2,1991,p.113-131. oSeealso:M.ShreedharandGeorgeVarghese"EfficientFairQueuingusingDeficitRound Robin",Proc.SIGCOMM95. SEEALSO tc(8) AUTHOR AlexeyN.Kuznetsov,<kuznet@ms2.inr.ac.ru>.Thismanpagemaintainedbyberthubert <ahu@ds9a.nl> iproute2 8December2001 2