Notes on FEC supported congestion control for one to many reliable multicast. Working Draft

ANGEWANDTEMATHEMATIKUNDINFORMATIK

UNIVERSIT¨ATZUK¨OLN

ReportNo.98.334

FECSupportedCongestionControlinOnetoManyReliableMulticast

by

FrankBrockners

August,1998

CenterforParallelComputing(ZPR)

UniversityofCologne

Weyertal80,D–50923K¨olnKeywords:CongestionControl,ForwardErrorCorrection(FEC),ReliableMulticastFECSupportedCongestionControl

inOnetoManyReliableMulticast

FrankBrockners

CenterforParallelComputing(ZPR)

UniversityofCologne

brockners@zpr.uni-koeln.de

TechnicalReportZPR-TR98-334

August,1998

Abstract

ThispaperdescribesthedesignofanewFECfueledrateand

congestioncontroller(RCR)whichistargetedprimarilyatone

tomanyreliablebulkmulticastdatatransfer.Theconceptof

RCRisvalidatedbyanalyticalandsimulationresults.The

heuristicanalysisisbasedonanewextendedmodelforflows,

whichimplementacongestioncontrolalgorithmsimilarto

TCP.ThemaingoalwastodevelopanalgorithmwhichisTCP-

friendlyandcompeteswiththecontrolloopofTCP.Largede-

laysinthecontrolcircuit,scalingissuesandhighpacketloss

probabilitiesareamongthemajorchallengesofareliablemul-

ticastratecontrollerimplementingTCP-faircongestioncon-

trol.Thecontrollerpresentedinthispapershowsthatlayered

forwarderrorcorrection(FEC)redundancycodingnotonlyre-

ducesthecontrol-andretransmissionsinreliablemulticasten-

vironmentsusingautomaticrepeatrequests(ARQ)totrigger

retransmissionsbutalsohelpsacongestioncontrollertocom-

petewithTCP.FECpermitsthereceiverstotoleratelossesina

waythattheyonlyneedtosignalizelosslevelswhicharesig-

nificantforthem.Thishigh-passfilteringofthelosssignalre-

vertsthedisadvantageofreactingslowlytolossintoanadvan-

tageindirectcomparisontoTCP.Thegreaterresponsiveness

withrespecttorateincrementensuresthatTCPalwaysreceives

itsshareofthetotalavailablebandwidth.Simulationsandana-

lyticalanalysisformulticastaswellasunicastsetupsshowthat

alreadyaverymoderatelevel(some%)ofredundancysuffices

tostrengthenaconnectionsufferingfromlongdelaysandhigh

lossprobabilities.

Keywords:CongestionControl,ForwardErrorCorrection,

ReliableMulticast.1Introduction

Congestioncontrolisvitalfortheinternetandisevenmore

importantforreliablemulticastsetups.Besidesfairnessand

throughputconsiderations,flowandcongestioncontrolhas

beenrecognizedasamajorproblemforreliablebulkmulticast

datatransfer.

Existingapproachesforcongestioncontrolschemesinreliable

multicastcanbedevidedintoclosed-loopandopen-loopcon-

trolschemes.Allclosedloopcontrolschemeshaveincommon

thatreceiverssendsomekindoffeedbackinformation(either

positiveornegativeacknowledgements)backtothesource.

Thesourceevaluatesthefeedbackinformationandaccordingly

adjustsitsemissionrate.Agreatvarienceofthepresentre-

liablemulticastframeworksuseclosed-loopcongestioncon-

trol.Inopen-loopscenariosacontrolpathfromthereceiversto

thesourcedoesnotexist.Open-loopsolutionsemployapre-

configuredrate,highlevelsofredundancycodingorrepeated

transmissions.Repeatedtransmissionsdenotesthesendingof

thesameinformationelementsmultipletimes.Thismayei-

therbeatdifferenttimesortodifferentmulticastgroups.The

controllerpresentedinthispaperprimarilyreliesonclose-loop

congestioncontrolbutalsoemploysaspectsofopen-loopcon-

trol,asitutilizesredundancycodingtoincreaseprotocoleffi-

ciency.

Wetakeashortglanceatthedifferentapproachesforflow

andcongestioncontrolforreliablemulticastbeforestudy-

ingourapproachwhichintegratesTCP-fairnessandTCP-

competitiveness.

Sender-initiatedapproachesforflowcontrolthatuseposi-

tiveacknowledgments(ACKs)alwaysfacetheACKimplo-

sionproblemwhilereceiverorientedschemesdosotoointhe

absenceofanNAKaggregationorsuppressionscheme.In

[1]Towsleyetal.demonstratedthatreceiver-initiated(NAK

1based)errorrecoveryusuallyissuperiortosender-initiateder-

rorrecovery.Dependingonthewayhowreceiverinitiatedpro-

tocolssolvetheNAKimplosionproblem,theycanbedivided

into(1)timerbased,(2)deterministicand(3)structure(tree-

)basedapproaches.ExamplesincludeSRM[2]foratimer

based,DTRM[3]fordeterministicandRMTP[4]aswellas

TMTP[5]fortreebasedapproaches.

Ineachoftheseapproachestheemissionrateiseitherre-

strictedtoasmalltolerableleveloraTCP-likecongestion

controlisimplementedinordertopreventorresolveconges-

tion.RMP[6]andRMTPserveasexamplesforTCP-like

windowcontrolledcongestioncontrolschemes.Bothrelyon

positiveACKs,eithertothetokesite(RMP)ortothedesig-

natedreceivers(RMTP).NAKbasedschemessignificantlyre-

duceprotocolcontroltrafficbutlackacontrolsignaltoclock

themselves(likeACKsinTCPdo).Insteadtheyusuallyem-

ploysomekindofofratecontrol.Explicitrateadjustmentis

commonformostoftheapproaches.Beitclose-loopcon-

gestioncontrol(RMTP[4],TMTP[5])oropen-loopcon-

trolwithafixedemissionratelikeSRM.Layeredmulticast

schemes,includingtheonebasedonFECwhichtransfersthe

TCP-principlesofcongestionwindowincreaseanddecrease

togroupjoinsandleavesofthereceivers[7]areexamplesfor

open-loopcongestioncontrol.Aproblemcommontoallcon-

trollersinterpretinglossasacongestionsignalis,thatpacket

lossisverylikelytooccur:Foraheuristicargumentonemay

thinkofuncorrelatedflowsondisjointpathsinthenetwork,

eachwithapacketlossprobabilityof1%.Theoverallpacket

lossprobabilityamountstoasmuchas40%.Lossratesofthis

magnitudedestroyanykindofTCP-likecongestioncontrol[8]

–Aratecontrollerwouldendupwiththeminimumemission

ratepermitted.[9]and[10]giveanindepthanalysisoftheloss

patternoftheMBone.Apossiblesolutionofthisproblemisto

tolerateacertainamountofloss.[11]discussesamonitoring

basedapproachwhereasLTRC[12]directlymeasurestheloss

rateandadjuststherateincrease-decreasefunctionofthecon-

troller.

Theflow-andcongestioncontrollerRCRpresentedinthispa-

peralsousesaTCP-likeemissionratecontrolandredundancy

(FECcoding)toimplementlosstolerance.FECenableseach

receivertofilterthelosssignallocallyandtoreacttotheoc-

curanceoflossindividually.Theactiveuseofredundancyin

thecontrolcircuitcompromisesbetweenTCP-friendlinessand

TCP-competitiveness.

Thispaperisstructuredasfollows:Afterashortoverview

aboutthedistributionmodel,section2focusesonsomeaspects

ofreliablecongestioncontrolanddiscussesthefairnessaspect.

Thediscussionofthedesignofthecontrollerinsection3is

followedbyananalyticalmodelofthecontrollerforthelater

analysisinsection5.Section5comparestheresultsobtainedfromthemodelwiththoseofaprototypicalimplementation

withinthens-2[13]networksimulationtool.

1.1Overviewofthedistributionmodel

Wefollowourprotocoldesigngivenin[14]ofaonetomany

distributionmodelwhichrunsontopoftheIP-multicastser-

viceandistreebased.Itisreliableinawaythatareceiver

eitherreceivesalldatacorrectlyorisabletodetectanunre-

coverablesituation.Theprotocolachievesreliabilitybyusing

both-redundancycoding(FEC)andautomatedrepeatrequests

(ARQ).Itfollowsacompletereceiverinitiatedretransmission

schemeandusesthettlhopcounttoformlocalgroups.The

burdenforcorrectreceptionofallpacketsiscarriedbythere-

ceivers.Bymeansofanexpandingringsearcheachreceiver

findsaso-calledleader,whoisclosertothesourceandhasthe

capabilitytolocallyretransmitpacketswithalimitedhopcount

value.ThisimpliesthattheIPmulticasttreehastobesymmet-

ric.Receiverfeedback(e.g.ARQ)issenttotheleaderonly,

whodecideswhethertoforward,takeactions,orsimplydis-

cardit.Thesenderdoesnotkeepanystateinformationabout

thesetofreceivers.

Thecontrollerthispaperisaboutonlyuses[14]asframework.

Thetinyandstraightforwardratecontrolalgorithmdescribed

in[14]wascompletelyreplaced.Therefore,theresultsand

conclusionsofthispapercaneasilybetransferredtoothermul-

ticastandevenunicastscenarios.

2Somedesignissues

2.1Fairnessconsiderations

Stabilityandrobustnessoftheinternetheavilydependoncon-

gestioncontrolledflows.Acontrollerhastointerpretpacket

lossasacongestionsignalandbackoffitsemissionrateincon-

ditionsofloss.Withaconstantlygrowinginternet,end-to-end

congestioncontrolbecomesavitalfactor.In[15]Floydand

Fallshowthenegativeeffectsofflowswhichareunrespon-

sivetolossandemphasizetheneedforcontinuingtheuseof

end-to-endcongestioncontrol.Therefore,theyproposerouter

mechanismstorestrictthebandwidthofbesteffortflowstoa

disproportionateshareoftheoverallavailablebandwidth.Up

to90%oftoday’sinternetWANtrafficusesTCP[16]astrans-

portprotocol.ThismotivatesnewprotocolstotakeTCPasref-

erenceandadjusttheircongestioncontroltobeTCP-friendly.

[15]definesaflowtobeTCP-friendly,ifthearrivalrateof

theflowdoesnotexceedthebandwidthofacorresponding

TCPconnectionunderthesamecircumstances.Basicallythis

maybeachievedbyacontrolalgorithmsimilartothemethod

employedbyTCP,i.e.byreducingtheemissionratetohalf

2