Scalable End-to-end Multicast Tree Fault Isolation

Abstract. We present a novel protocol, M3L, for multicast tree fault isolation based purely upon end-to-end information. Here, a fault is a link with a loss rate exceeding a specified threshold. Each receiver collects a trace of end-to-end loss measurement

ScalableEnd-to-endMulticastTreeFaultIsolation

TimurFriedman1,DonTowsley2,andJimKurose2

Universit´ePierreetMarieCurie

LaboratoireLiP6-CNRS

8rueduCapitaineScott

75015Paris,France

timur.friedman@lip6.fr

2UniversityofMassachusettsAmherst

DepartmentofComputerScience

140GovernorsDrive

Amherst,MA01003,USA

{towsley,kurose}@cs.umass.edu1

Abstract.Wepresentanovelprotocol,M3L,formulticasttreefaultisolationbasedpurelyuponend-to-endinformation.Here,afaultisalinkwithalossrateexceedingaspeci edthreshold.Eachreceivercollectsatraceofend-to-endlossmeasurementsbetweenthesenderanditself.Correlationsoflosseventsacrossreceiversprovidethebasisforparticipantstoinferbothmulticasttreetopologyandlossratesalonglinkswithinthetree.Notallreceivertracesareneededtoinferthelinkswithinthenetworkthatexceedthelossthreshold.M3Ltargetstheminimalsetofreceivertracesneededtoidentifythoseloss-exceedinglinks.

Whilemulticastinferenceofnetworkcharacteristics(MINC)iswellunderstood,thenoveltyofM3Lliesinthemannerinwhichonlyasubsetofthereceivertracesisused.Wemodelthisasaproblemofestablishingagreementamongdis-tributedagents,eachactinguponincompleteandimperfectinformation.Consid-eringbandwidthtobealimitedresource,wede neanoptimalagreementtobebaseduponthesmallestpossiblereceiverset.M3Lperformswellcomparedtotheoptimal.

1Introduction

Weknowthatmulticastcanserveasanactivemeasurementtool,revealingnetworktopologyotherwisehiddenfromanend-to-endperspective,andallowinginferenceoflossratesanddelaysalonginternallinks.Little,however,isknownabouthowsuchmea-surementtechniquesmightscale.Theprocessofgatheringreceivertracesintooneplaceinordertoperforminferencewouldseemtorequireaquantityofmeasurement-relatedtraf cthatislinearinthenumberofreceivers.Thispapershowshow,byrestrictingthemeasurementproblemtooneofidentifyingjustthelossiestlinks,thetraf ccanbemadetoscalesublinearly.ThepaperproposestheMulticastLossyLinkLocationpro-tocol,M3L,whichscalesaccordingtoapowerlawwithapositiveexponentlessthanone.

ThisworkwassupportedinpartbytheNSFundergrantITR-0085848.

Abstract. We present a novel protocol, M3L, for multicast tree fault isolation based purely upon end-to-end information. Here, a fault is a link with a loss rate exceeding a specified threshold. Each receiver collects a trace of end-to-end loss measurement

M3Lisdesignedtoleveragethenewly-introducedstandardstrackreportingexten-sionsfortheRTPcontrolprotocol.RTCPXR[1]isamechanismthatcanbeuseduniformlyacrossalltypesofmultimediasessionsforprovidinghighlydetailedreportson,amongotherthings,packetlosses.DatapacketsfromtheRTPmediastreamconsti-tutetheactiveprobesuponwhichmeasurementisbased.IfasessionparticipantenablesthesendingofRTCPXRLossRLEReportBlocks[1,Sec.4.1]thenitgatherstracesspecifying,foreachsequencenumber,whetherornotapacketwasreceived.Theselosstracesarecompressedbyrun-lengthencoding(RLE),and,typically,multicastalongwiththestandardRTCPReportBlocks.

InamulticastRTPsessioninwhichallreceiversoriginateRTCPXRLossRLEBlocks,eachparticipantpotentiallyobtainsafullsetofdetailedlosstraces.Thusarmed,theparticipantcanuseMINC(MulticastInferenceofNetworkCharacteristics)[2]todeduceelementsinthestructureofthemulticasttreebydiscerningbranchingpointsbetweenwhichsomelosshasoccurred,andbyestimatingthelossratesbetweenthosepoints.Knowledgeoftreestructureandlossratesisvaluableinreliablemulticastpro-tocolsthatpromotelocalrecoveryoflostpackets,aspointedoutbyRatnasamyandMcCanne[3].Aparticipantthatisanetworkmonitorcouldalsoprovideinformationthatwouldallowanetworkadministratortoperceiveandrespondtoproblemsinmulti-castdatadiffusion.Forboththereliablemulticastparticipantandthenetworkmonitor,oneaimisfaultisolation:identifyinglinksinthetreethatexperiencehighloss.

Theliteraturerevealsanumberofproposalsformulticasttreefaultisolation.Reddy,Govindan,andEstrindescribeamethod[4]thatusesmtrace[5]androuter“subcast”toidentifylossylinks.Zappaladescribesatechnique[6]thatmulticastreceiverscouldusetorequestalternateroutingpathsiftheydetect,withmtrace,thattheyliebehindabadlink.Sarac¸andAlmeroth’sMulticastRoutingMonitor(MRM)[7]employsagentswithinthenetworktosendtesttraf camongthemselvesforthepurposeoflocalizingfaults.WalzandLevine’sHierarchicalPassiveMulticastMonitor(HPMM)[8]ismadeupofasetofdaemonslocatedatroutersanddesignedtoaccomplishthesamegoalthroughpassivemonitoring.

Alloftheseprotocolsscalewell,butinordertoachievetheirgoodscalingpropertiestheyrelyupontheactivesupportofroutersorotheragentsinsidethenetwork.M3Lisfundamentallydifferentbecauseitisbaseduponthepurelyend-to-endmechanismsofRTCPXRandMINC.

Strictlyend-to-endmethodsotherthanM3L,suchasFloydetal.’sScalableReliableMulticast(SRM)[9]orXuetal.’sStructure-OrientedResilientMulticast(STORM)[10],donotaimatfaultisolationperse,somuchasformingmulticastreceiversintotopo-logicallyrelatedgroups.Thesegroupsprovidethebasisforscalablesignallingandlossrepair.Theend-to-endmechanismsatworkinSRMandSTORMareverydifferentfromthatusedbyM3L.Ratherthanloss-basedinference,SRMusesIPv4multicastpackettime-to-live(TTL)scopingtodeterminetopology.TheSTORMworkrevealsapossibleweaknessintheSRMapproach,inthatmeasurementsofmulticastpacketsrevealonlytwoTTLvalues(either64or128)actuallybeingusedinpractice,whichwouldmakescopingonthatbasisdif cult.STORMthusenhancestheTTLlocalityinformationbyaddinground-trip-time(RTT)measurements.

Abstract. We present a novel protocol, M3L, for multicast tree fault isolation based purely upon end-to-end information. Here, a fault is a link with a loss rate exceeding a specified threshold. Each receiver collects a trace of end-to-end loss measurement

Oneprotocolthatdoesuseloss-basedinferenceisRatnasamyandMcCanne’sGroupFormationProtocol(GFP)[11].Bycreatingaseparatemulticastgroupcorrespondingtoeachtopologicalgroup,andbydesignatingasinglereceivertosenditstraces,or“lossprints,”withineachgroup,GFPreducesoveralltraf c.However,duringinitialtreeformationeachreceiverisliabletosenditstracetoacommoncontrolgroup.TheGFPworkdoesnotincludeananalysisofhowrapidlyreceiversmightpeelofffromthecommoncontrolgroup,andwhetherthisprocessmightpreventtracetraf cfrombeinglinearinthenumberofreceivers.Workinthepresentpaperindicatesthatwaitingfortraceinformationtoarriveinarandomordercanresultinanearlylinearquantityoftracetraf cwhenthegoalisfaultisolation.

Thereispriorworkbythispaper’s rstauthor,alongwithothers,onscalingMINCinferenceforlosstracessharedthroughRTCPXR.OuryandFriedmanshowed[12]thatthesetracescouldbecompressedbyuptoafactorof ve,andC´aceres,Duf eld,andFriedmanexamined[13]theeffectsofthinningthetracestoaccommodatebandwidthconstraints.However,neitherofthesetechniquesbringsbetterthanlinearscalinginthenumberofreceivers.

2ProtocolOverview

ThekeytoachievingbetterthanlinearscalinginM3Listheinsightthatnotallre-ceivers’tracescontributeequallywhenthetaskisspeci callytoidentifythelossiestlinks.Similarly-situatedreceiversreportessentiallyredundantinformation.Tracesfromreceiversonlow-losspathsmightnotbenecessaryatall.M3Lemploysaheuristicthatprioritizesreportingfromcertainreceiversoverotherreceivers.ThetracesfromthosereceiversaresentusingRTCPXRpackets,andMINCinferenceisperformed,justasinthepriorworkjustcited.Butbyprioritizing,wespeedupfaultisolationforbandwidth-constrainedsituations.

Theprotocolworksbyprogressivelyre ningwhatwecallapictureuntilalllossylinkshavebeenidenti ed.Re nementtakesplaceoveraseriesofrounds.Ineachround,receiversthathavenotyetcontributedtracesdeterminewhethertheirdatamightbeusefulornot.Ifso,theybecomecandidates.OnecandidateisselectedeachroundatrandomthroughprobabilisticpollingofthesortdescribedbyNonnenmacherandBiersack[14,15,16].Theprotocolterminatesafteratmostthreeroundsinwhichnoreceiversendsatrace.

TheessenceoftheM3Lprotocolistheprocessbywhichareceiverrdecideswhetheritisacandidate.ItrequiresthetracesfromthesetofreceiversSthatcon-tributedinpriorrounds.ThoughitdoesnotknowtheunderlyingtreeT,withMINCitcaninferapictureT(S)ofpartofthattree.ItcanalsoinferasecondpicturebycombiningitsowndatawiththatfromS.ThisisthepictureT(S∪{r}).Sinceralonecaninferthispicture,wecallitr’s“privatepicture.”Bycontrast,sinceallreceiverscaninferT(S),werefertoitasthe“publicpicture.”Itisbycomparingthepublicpicturetoitsownprivatepicturethatareceivermakesitsdecision.

Fig.1showsanexampleofatreeT,apublicpictureT(S)inferredfromthetracesofthesetofnodesS={4,11,14,15},andtheprivatepictureT(S∪{7})seenbyreceiver7.Whymightreceiver7consideritselfacandidatefortransmittingitsdata?

Abstract. We present a novel protocol, M3L, for multicast tree fault isolation based purely upon end-to-end information. Here, a fault is a link with a loss rate exceeding a specified threshold. Each receiver collects a trace of end-to-end loss measurement

Fig.1.TreeT,publicpictureT(S),andprivatepictureT(S∪{7})

Therearetwopossibilities.First,receiver7mightinferthatthelink(2,7)isalossylink.(Thoughitdoesnotknowtheidentityofnode2,receiver7infersitspresence.Forsimplicity,inthistextwerefertonode2andotherinternalnodesbytheirlabels.)Sincethislinkappearsonlyinitsprivatepicture,notthepublicpicture,receiver7hasvaluableinformationtocontribute.Second,ifthepublicpictureshowsthelink(1,4)tobealossylink,receiver7’sprivatepictureshowsthatthatthatlinkcanbedividedintwo.Oneoftheresultinglinks,(1,2)or(2,4),mightprovetobealossylink,inwhichcasereceiver7’sdatahashelpedtoisolateit.Orreceiver7’sdatamightshowthatneitherislossy,inwhichcasethedatahashelpedeliminatewhatwouldotherwisebeafalsepositive.

InM3L,roundsalternatebetweeneachofthepossibilitiesjustdescribed.Thereisaround,calledanADDround,inwhichdataindicatingnewlossylinksissolicited.ThenthereisaCUTround,inwhichdataindicatingthesubdivisionofexistinglossylinksissolicited.WhenthereisanADDroundforwhichtherearenocandidatesfollowedbyaCUTroundforwhichtherearenocandidates,theprotocolhalts.Theresultantpublicpictureoughttoisolateallofthetree’slossylinks.

ToevaluatetheperformanceoftheM3Lprotocol,thispapercomparesittotheperformanceofahypotheticaloptimalprotocolthatwouldalwaysselectthesmallestpossiblesetofreceiversnecessarytoisolatethelossylinks.ThispaperalsocomparesM3Lagainstaprotocolthatdemonstrateswhatmightbeaccomplishedifnospecialknowledgeorheuristicweretobeemployedbychoosingreceiversatrandom.

3TheM3LProtocol

ThissectiondescribestheM3Lprotocolinformalterms,byshowinghowtosimulateitsoperationunderidealcircumstances(suchasperfectMINCinference).ThesettingisthatofamulticasttreeT=(V,L),withnodesV(includingrootnodeρ),andlinksL V2.Theprotocolfunctionsoveraseriesofrounds,numberedi=0,...,n.ThesetofreceiversinthemulticasttreeisR V.Aset,Si R,iscalledthesetof“in-picturereceivers”forthestartofroundi,withS0= .LetCi R\Sidesignateasetcalledthe“candidates”foraround.Each“out-of-picturereceiver”r∈R\Simakesanindependentdecisionregardingwhetheritisacandidateornot.ThetermsofthisdecisiondifferdependinguponwhethertheroundisanADDround(iiseven)oraCUTround(iisodd),aswenowdescribe.

Abstract. We present a novel protocol, M3L, for multicast tree fault isolation based purely upon end-to-end information. Here, a fault is a link with a loss rate exceeding a specified threshold. Each receiver collects a trace of end-to-end loss measurement

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20σH(T,α ){i←0S0← doquiescent←trueCi←CADD(Si,α )ifCi= wearbitrarilychooseoner∈CiSi+1←Si∪{r}quiescent←falsei←i+1Ci←CCUT(Si,α )ifCi= wearbitrarilychooseoner∈CiSi+1←Si∪{r}quiescent←falsei←i+1while¬quiescentreturnSi}

Fig.2.AlgorithmtosimulatetheM3Lprotocol

Areceivermakesitsdecisionbaseduponthepicture,T(Si)=(V(Si),L(Si)),thatisformedbythesetofin-picturereceivers.T(Si)isitselfatree,madeupofasubsetofthenodesfromT,http://www.77cn.com.cningj ktoindicatethatanodejisdescendedfromanodekinT,wede nethesetofpicturenodestobeV(Si)={ρ}∪{v∈V: s1,s2∈Si,s1=s2,s1 v,s2 v}∪Si.ThesetofpicturelinksisL(Si)={(k,j)∈V(Si)×V(Si):j k, v∈V(Si):j v k}.Apicturede nesasetof“endogenousnodes,”Vendo(Si)={v∈V: (j,k)∈L(Si),j v k},andasetof“exogenouslinks,”

Lexo(Si)={(k,r)∈(V(Si)∪Vendo(Si))×(R\Si),

r k, v∈V(Si)∪Vendo(Si):r v k}.

AreceiverusesMINCtoestimatelossratesonlinksinthepicture,andalongtheexogenouslinkthatthereceiverterminates.WeassumeaBernoullilinklossmodel.Packetsareindependentandeachpacketissuccessfullytransmittedacrosslink(k,j)with“passageprobability”α((k,j)).Athresholdvalueα determineswhetheralinkislossyornot.ThesetofcandidatesforanADDroundare

CADD(Si,α )={r∈R\Si}:(v,r)∈Lexo(Si),α(v,r) α ,

andthesetofcandidatesforaCUTroundare

CCUT(Si,α )={r∈R\Si}: (k,j)∈L(Si),

α(k,j) α ,(v,r)∈Lexo(Si),j v k.

Abstract. We present a novel protocol, M3L, for multicast tree fault isolation based purely upon end-to-end information. Here, a fault is a link with a loss rate exceeding a specified threshold. Each receiver collects a trace of end-to-end loss measurement

Fig.2de nesafunctionσH()thatreturnsthesetS RofreceiversthatresultsfromapplicationoftheM3Lprotocol.ThisfunctioncanbeappliedtosimulatethefunctioningoftheM3Lprotocol.Inthisfunction,quiescenceisdeterminedbyavari-able,“quiescent,”whichistrueiftherearenocandidatesforanADDroundandnocandidatesintheimmediatelyfollowingCUTround.ThefunctionloopsthroughADDandCUTroundsuntilquiescenceresults.

ThefunctionσH()returnswhatwecalla“solution”tothelossylinklocationprob-lem.Thisisamemberofthesetofallpossiblesolutions,de nedasfollows:

S (T,α )={S R:αmin(Lexo(S))>α ,

(k,j)∈L(S)∧α(k,j) α v∈Vendo(S):j v k}

Theproofthatasolutionindeedisolatesallofthelossylinksinthetreecanbefoundinthe rstauthor’sthesis[17].ThethesisalsodescribespossibleenhancementstotheADDandCUTrounds.

4ComparisonProtocols

TheprevioussectiondescribedtheM3Lprotocol,whichemploysaheuristicforusebyreceiversoperatingon-lineandwithlimitedinformation.ToevaluateM3L,wecompareitsperformancetoanoptimalprotocolandarandomprotocol.

Theoptimalprotocolrepresentsthebestthatcouldbedoneoperatingoff-lineandwithomniscience.ThisprotocolreturnsasetS=σ(T(k),α )thatisaminimalcardi-nalitysolution:

S minC(T,α)={S∈S(T,α):|S|=X∈S (T,α )min|X|}.

Spacedoesnotpermitadetailedtreatmentofanef cientalgorithmforcalculatingtheresultsoftheoptimalprotocol.Thedetailscanbefoundinthe rstauthor’sthesis[17,Sec.3.2].

Therandomprotocolconsistsofaseriesofrounds,i=1,....Atthebeginningofround0,thesetS0ofin-picturereceiversistheemptyset:S0= .Ineachroundi,oneout-of-picturereceiverr∈R\Siischosenatrandomandaddedtothesetofin-picturereceivers:Si+1=Si∪{r}.IfthesetSi+1constitutesasolutionforthetreeT,thatisifSi+1∈S (T,α ),thentheprotocolhalts,andSi+1isreturned.LetσR(T,α )bethefunctionthatreturnsasetarrivedatthroughsimulationoftherandomprotocol.5EmpiricalEvaluation

ThissectiondescribestheempiricalevaluationofM3L.Thisevaluationisconductedintwostages.Inthe rststage,wecompareM3Lagainsttheoptimalprotocolandtherandomprotocol.ThesecomparisonsassumethatMINCinferencereturnsperfectlyac-curateestimates.BystudyinghowwellM3LperformsundertheassumptionofperfectMINCinference,wecanestablishaboundonhowwelltheheuristiccanpotentiallyper-form.Also,itallowsustoexperimentuponlargertopologiesthanarefeasiblewhenwe

Abstract. We present a novel protocol, M3L, for multicast tree fault isolation based purely upon end-to-end information. Here, a fault is a link with a loss rate exceeding a specified threshold. Each receiver collects a trace of end-to-end loss measurement

Fanout 2

y = xrandomheuristicheuristic w/ enhanced cutheuristic w/ enhanced addenhanced heuristicoptimalFanout 3y = xrandomheuristicheuristic w/ enhanced cutheuristic w/ enhanced addenhanced heuristicoptimalFanout 4y = xrandomheuristicheuristic w/ enhanced cutheuristic w/ enhanced addenhanced heuristicoptimal100010001000

Leaves n soutonLeaves n souton100100Leaves n souton

110100

Leaves in tree10001001010101110100Leaves in tree100011110100Leaves in tree1000

(a)Treesoffanouttwo(b)Treesoffanoutthree(c)Treesoffanoutfour

Fig.3.Numberofreceiversinsolution

mustpaythecomputationalcostsofMINCinference.Inthesecondstage,weintroducethepossibilityofinaccuraciesarisingfromtheMINCinference.Inbothstageswefocusonaspecialcaseofthelossylinklocationproblem:locatingthesinglelossiestlinkinthemulticasttree,chosentofacilitatecomparisons.

5.1ExperimentalwithPerfectInference

The rststageofexperimentswasperformeduponsimulatedtreesofconstantfanout,withfanoutvaluesofeithertwo,three,orfour,anddepthsoftwo,three,orfour.Ifcom-putationalresourcespermitted,treesofgreaterdepthwerealsosimulated,toadepthofeight.Atimelimitof veminuteswasplaceduponsimulationforanygiventopology.Inthecaseoftreesoffanouttwo,thispermittedadepthofeight;fortreesoffanoutthree,adepthofseven;andfortreesoffanoutfour,adepthof ve.Increasingthetimelimittoseveralhoursdidnotpermitthegenerationoffurtherdatapoints.

Linkpassageprobabilitiesforeachlinkineachtreewerechosenindependently

fromauniformdistributionontheinterval(0,1).Foreachtopology,tenthousandtreesweresimulated.ForeachtreeT,thethresholdα wassettobethepassageprobabilityofthelossiestlink:α =αmin(L).Then,forthattree,anoptimalsetσ(T,α )andaheuristicsetσH(T,α )weredetermined,aswellasheuristicvariantswithenhancedADDandCUTrounds,and nallyarandomprotocolsetσR(T,α ).Foreachset,thecardinalitywasrecorded,leadingtoacalculationofthemean.

ResultsInFig.3(a)weseetheresultsfortreesoffanouttwo.Thisgraphisinlog-logscale.Thehorizontalaxisindicatesthenumberofleaves,whichistosayreceivers,inthetree.Sincethedepthvariesfromtwotoeight,thevaluesreporteduponare:4,8,16,32,64,128,and256.InFig.3(b)weseetheresultsfortreesoffanoutthree.Thisgraphissimilartotheprecedinggraph.Asthedepthoftreesvariesfromtwotoseven,thenumbersofreceiversinthetopologiesreporteduponare:9,27,81,243,729,and2187.InFig.3(c)weseetheresultsfortreesoffanoutfour.Thisgraphissimilartothetwoprecedinggraphs.Thedepthoftreesvariesfromtwoto ve,sothenumbersofreceiversare:16,64,256,and1024.

Abstract. We present a novel protocol, M3L, for multicast tree fault isolation based purely upon end-to-end information. Here, a fault is a link with a loss rate exceeding a specified threshold. Each receiver collects a trace of end-to-end loss measurement

Theverticalaxisindicatesthemeannumberofreceiversinasolutionforeachoftheprotocolsdescribedabove.Thestraightliney=xdepictsthetheoreticalworstcase,inwhichasolutionisonlyarrivedatwheneveryreceiverhasbeenenteredintothepicture.Thelowerthemeancardinalityofasolution,thefurtherbelowtheliney=xitappears.Thehighestsetofvaluesisfortherandomprotocol,andthelowestfortheoptimalprotocol.ValuesM3Lwithforthevariousheuristicslieinbetween.Theresultsforeveryprotocoltestedarewell ttedbystraightlinesonalog-loggraph,indicatingpowerlawscaling(thatis,wecan tthepointstoacurveoftheformy=bxa).

DiscussionWeseethattherandomprotocolperformsrelativelypoorly,thenumberofreceiversinasolutionincreasingapproximatelylinearlywiththenumberofreceiversinthetree(estimatesa =0.98,1.01,and1.02).Theresultsfortheoptimalprotocoldemonstratethatinthebestofcasesthegrowthinthenumberofreceiversinasolutioncouldbedistinctlysub-linear(a =0.52,0.47,and0.43).M3L’sbehaviormorecloselyresemblestheoptimalthantherandom.Whenemployingthebasicheuristic,weobtainestimatesfortheexponentofa =0.61,0.52,and0.45.

AlthoughwithM3Lthenumberofreceiverssendingtracesscalessub-linearly,isthisde nitivelybetterthanemployingnetworktomographywithdatafromallre-ceivers?Onereasonwhyitmightnotbeisthat,ifallreceiversaretobeheardfrom,theycouldsimplyunicasttheirtracestoasinglesite.WithM3L,thetracesthataresentaremulticast,reachingallreceivers.Forthosehoststhatdonotneedtoperforminferenceforsomeapplication-relatedpurpose,M3Lrelievessomeload(theydon’tnecessarilyhavetosendtheirtraces)whilecreatingadditionalload(thereceivingandprocessingofothers’traces).

Thereisthusatrade-off.Ingeneral,theredistributionofahighloadfromasinglepointtoaconsiderablylowerloadmorewidelysharedmightbeviewedasworthwhile,andinkeepingwiththemotivationbehindmulticastitself.However,aspecialconcernariseswhentheloadisbeingplacedonreceiversthatarebehindlossylinks.DoesM3L,bysendingthemadditionaltraf c,notexacerbatetheirsituation?

Theextentoftheproblemdependsuponhowmuchadditionaltraf cisgenerated.IftheRTPcontrolprotocolisbeingusedforsharingtraces,asinpriorwork[13],thenoverheadislimitedto5%ofsessionbandwidth,whichmaybeasuf cientlimitation.However,ifthisadditionaltraf cisgenuinelyaproblem,ahybridsystemcouldbeadopted.Areceiverthat ndsitselfinsuchasituationcouldunicastitstracetoanothersessionmember.Thisdoesnotcreateanyloadonthereceiverbeyondwhatwouldbenecessaryfortomographywithfulldata.ThentheothersessionmembercouldactasanM3Lproxyonthereceiver’sbehalf,whilethereceiverdropsoutofthemulticastgrouponwhichthetracesarebeingsent.

5.2ExperimentwithMINCInference

Thesecondstageofexperimentswasalsoperformeduponsimulatedtreesofconstantfanout,withfanoutvaluesofeithertwo,three,orfour,anddepthsoftwo,three,orfour.Withinthisrange,thecomputationalcostsofMINCinferencelimitedustotreeswithamaximumof27receivers.

Abstract. We present a novel protocol, M3L, for multicast tree fault isolation based purely upon end-to-end information. Here, a fault is a link with a loss rate exceeding a specified threshold. Each receiver collects a trace of end-to-end loss measurement

Anarrowerrangeoflinkpassageprobabilitieswasusedforthisexperiment,tobetterfocusontheproblemsofincorrectinference.Thepassageprobabilityforeachlinkineachtreewaschosenindependentlyfromauniformdistributionontheinterval(0.900001,1.0).Thenonelinkinthetreewaschosenatrandom,andreassignedalowerpassageprobability,chosenfromauniformdistributionontheinterval[0.85,0.90].Thethresholdpassageprobabilityfordeterminingthatalinkwasalossylinkwasα =0.90.Pseudo-randomnumbersweregeneratedinthesamemannerasforthe rstexperiment.

Foreachtopology,asuf cientnumberoftreeswassimulatedtoconstruct95%con- denceintervalsforthestatisticsthatwerecollected.Oneachtree,thesendingof8,192probepacketswassimulated.Thisvalueissuf cienttoobtainrelativelygoodMINCin-ference.TheheuristicsetsσH(T,α )weregenerated,employingMINCtocreatethepictures.Thisinferencewasvariouslybasedupontheoutcomesatthereceiversfromoneprobe,twoprobes,fourprobes,etc....,upto8,192probes.Thus,fourteendifferentheuristicsetsweregeneratedforeachtree.

Baseduponagivenheuristicset,eachreceiver(whetherinthesetornot)eitheridenti edthelossylinkcorrectly,oritdidnot.Thisfactwasrecorded.Acorrectidenti- cationisscoredasfollows.Asweobservingfromoff-lineknowthetruetopology,wecanidentifythesetofreceiversR(k)thatliebelowthelossylinkk.Eachreceiverj,initsinferencebasedupontheMINCdatafromthesetofreceiversS∪{j},identi esacertainnumberoflossylinksk1,k2,....EachsetR(ki)∩(S∪{j})iscomparedagainstthesetR(k)∩(S∪{j}).Ifthetwosetsareidentical,thenacorrectidenti cationisscored.

Foreachheuristicset,eachreceivermightalsomisidentifyanumberoflinksaslossylinks.Thenumberofsuchfalsepositiveswasalsorecorded.

Inaddition,foreachgivennumberofprobes,MINCinferencewasconductedusingtheentiresetofreceiversR.Asfortheheuristicset,itwasrecordedforeachreceiverwhetheritmadeacorrectidenti cationofthelossylink,aswellasthenumberoffalsepositives.

ResultsTheresultsforeachtopologywereverysimilar.Weshowresultsherefortreesofdepththreeandfanoutthree,having27receivers.Ineachofthethreegraphsshownhere,theindependentvariableisthenumberofprobesthatwereemployedinMINCinference.Thisisplottedinlogscaleonthehorizontalaxis,anditvariesfrom1to8,192.Allcon denceintervalsforthedependentvariablesareatthe95%levelorbetter.

InFig.4(a),thedependentvariableisthemeannumberofreceiversinaheuristicset.Thisnumber,plottedinlinearscaleontheverticalaxis,rangesfromalowof0.8987toahighof16.0984.Thehorizontallinelabelled“ideal”representsthemeannumberofreceiversintheheuristicsetifMINCinferencewereperfectlyaccurate.(Asthelossratesaredifferentfromthe rstexperiment,thesenumberswererecalculated,andinthiscasethenumberis14.4491.)

InFig.4(b),thedependentvariableisthemeannumberofunidenti edlossylinks.Thisvalueisplottedinlinearscaleontheinterval[0,1].Avalueofzeroisthebest.Valuesareplottedbaseduponthesetofreceiversreturnedbytheheuristic,andbaseduponuseofallthereceivers.

Abstract. We present a novel protocol, M3L, for multicast tree fault isolation based purely upon end-to-end information. Here, a fault is a link with a loss rate exceeding a specified threshold. Each receiver collects a trace of end-to-end loss measurement

Heuristic Solution Size (trees of depth 3, fanout 3)

18

16

Mean number of undentfed ossy nks14Mean number of recevers121086

4

2

0idealMINC10.90.80.70.60.50.40.30.20.10Unidentified Lossy Links (trees of depth 3, fanout 3)heuristicall110100

Number of probes100010000110100Number of probes100010000

(a)Numberofreceivers10

9

8

Mean number of fase postves76543

2

1

0(b)Numberofunidenti edlossylinksFalse Positives (trees of depth 3, fanout 3)heuristicall110100

Number of probes100010000

(c)Numberoffalsepositives

Fig.4.ResultswithMINCinference

InFig.4(c),thedependentvariableisthemeannumberoffalsepositives.This

value,plottedinlinearscaleontheverticalaxis,rangesfromalowof0toahighof

9.5036.Asinthepreviousgraph,valuesareplottedbaseduponthesetofreceiversreturnedbytheheuristic,andbaseduponuseofallthereceivers.

Thecon denceintervalsfortheseresultsaretoonarrowtoplotinthese gures.

DiscussionTheseexperimentscon rmthevalidityofusingtheheuristiceveninthefaceofinaccuraciesintroducedinthecourseofMINCinference.InFig.4(a),weseethatthenumberofreceiversthatresultswhileusingMINCinferenceisverynearlythesameasifMINCinferencewereperfectlyaccurate.Thisissooncethenumberofprobesiseightormore.

Ofcourse,manymorethaneightprobesarerequiredinorderfortheresultingin-

ferencetobeaccurate.InFig.4(b),weseethatoncethenumberofprobesentersthehundreds,thelossiestlinkiscorrectlyidenti edmostofthetime,onaverageandthisimprovesto90%oncethenumberofprobesexceedsathousand.InFig.4(c),weseethatafewthousandprobesarerequiredbeforethenumberoffalsepositivesdropsbe-lowone.Whatisstrikingaboutbothofthesegraphsisthefactthat,afteracoupleofhundredprobes,thereisalmostnoperceptiblediminutioninperformancethatresultsfromusingMINCtracesfromM3L’sheuristicsetofreceiversratherthanMINCtracesfromtheentirereceiverset.This nalresultcon rmsthevalueofM3Linreducingthebandwidthrequirementsforlossylinkidenti cation.

Abstract. We present a novel protocol, M3L, for multicast tree fault isolation based purely upon end-to-end information. Here, a fault is a link with a loss rate exceeding a specified threshold. Each receiver collects a trace of end-to-end loss measurement

Onemightaskwhathappensiflossratesshouldchangeoverthecourseofanin-ference.ThisisaquestioninherenttonetworktomographythatM3Lcannotbyitselfsolve.However,M3Lbyspeedinguptheprocess,canhelp.Andwhatshouldhappeniflossratesarenotspatiallyortemporallyindependent?Again,thisisageneralproblemfortomography.Whethersuchdependenciescreatespeci cbiasesforM3Lremainsatopicforfuturework.

6RelatedandFutureWork

Anumberofworksonfaultisolationwerementionedintheintroduction.Thispaperisthe rsttobothmakeuseoftheend-to-endfaultisolationcapabilityprovidedbyMINCinferenceandreducetheoverallamountofdatarequiredforthatinference.

Althoughthispaperdoesnotmakeuseofdelay-basedinference,itappearspossibletoadaptthetechniquesdescribedinthispapertoidentifythehigh-delaylinksinamulticasttree.Multicast-basedinferenceofnetwork-internaldelaycharacteristicsisdescribedbyLoPrestietal.(includingaco-authorofthispaper)[18].ThecombinationofbothlossanddelaymeasurementsforimprovedtopologyinferenceisdescribedbyDuf eldetal.[19].

Thestrongcorrelationsinoutcomesformulticastpacketsmakesmulticastaneffec-tivetoolforend-to-endinferenceofbehaviorinsideofanetwork.However,multicastisoftennotavailable,andwhereitisavailableitmaybeoflimiteduseforpredictinguni-castbehavior.Analternativemeasurementtoolistosendclosely-spacedunicastpacketstodifferentreceivers.Thesepacketsshouldalsoshowcorrelatedbehavior.CoatesandNowack[20]haveappliedthisprincipletolossinference.Itisnotnecessarytoactivelysendunicastpacketsformeasurementpurposes,asabundantunicasttraf cexiststhatcanbepassivelymonitored.Tsang,CoatesandNowackshow[21]howTCP owscanbemonitoredtoopportunisticallytakeadvantageofsuchclosely-spacedpacketsasdoappear.TheuseofstripedunicastpacketsfordelayinferenceisdescribedbyDuf eldetal.(includingaco-authoronthispaper)[22],andbyCoatesandNowack[23,24].TheM3Lprotocolcouldbeadaptedforunicast-basedinferencesolongasmulticastwereavailablefortracesharing.

Futureworkspeci callybuildinguponM3Lwillincludestudyofawidervarietyofscenarios.HowdoesM3Lperforminisolatingmultiplelossylinksinatreeascomparedtothecaseofasinglelossylinkstudiedinthispaper,forinstance?WearealsointerestedinapplyingM3Ltodelayinferenceandtootherformsoftomography.Finally,weplantodeployM3LintheInternet,tostudytheeffectsofsuchthingsascorrelatedlossesandthelossoftrace-bearingpackets.

References

[1]T.Friedman(ed.),R.Caceres(ed.),A.Clark(ed.),K.Almeroth,R.G.Cole,N.Duf eld,

K.Hedayat,K.Sarac,andM.Westerlund,“RTPcontrolprotocolextendedreports(RTCPXR),”InternetEngineeringTaskForce,RFC3611,Nov.2003.

aceres,N.Duf eld,T.Friedman,J.Horowitz,F.LoPresti,S.Moon,[2]A.Adams,T.Bu,R.C´

V.Paxson,andD.Towsley,“Theuseofend-to-endmulticastmeasurementsforcharacter-izinginternalnetworkbehavior,”IEEECommunicationsMagazine,May2000.

Abstract. We present a novel protocol, M3L, for multicast tree fault isolation based purely upon end-to-end information. Here, a fault is a link with a loss rate exceeding a specified threshold. Each receiver collects a trace of end-to-end loss measurement

[3]S.RatnasamyandS.McCanne,“Inferenceofmulticastroutingtreesandbottleneckband-

widthsusingend-to-endmeasurements,”http://www.77cn.com.cncom’99.

[4]A.Reddy,R.Govindan,andD.Estrin,“Faultisolationinmulticasttrees,”inProc.SIG-

COMM2000.

[5]B.Fenner,“mtrace(multicasttraceroute),”availablefromftp://http://www.77cn.com.cn/pub/net-

research/ipmulti/.

[6]D.Zappala,“Alternatepathroutingformulticast,”http://www.77cn.com.cncom2000.

[7]K.Sarac¸andK.C.Almeroth,“Monitoringreachabilityintheglobalmulticastinfrastruc-

ture,”inProc.ICNP2000.

[8]J.WalzandB.N.Levine,“Ahierarchicalmulticastmonitoringscheme,”inProc.NGC

2000.

[9]S.Floyd,V.Jacobson,C.-G.Liu,S.McCanne,andL.Zhang,“Areliablemulticastframe-

workforlight-weightsessionsandapplicationlevelframing,”IEEE/ACMTrans.onNet-working,vol.5,no.6,pp.784–803,Dec.1997.

[10]X.Xu,A.Myers,H.Zhang,andR.Yavatkar,“Resilientmulticastsupportforcontinuous-

mediaapplications,”inProc.NOSSDAV,1997.

[11]S.RatnasamyandS.McCanne,“Scalingend-to-endmulticasttransportswithatopologi-

callysensitivegroupformationprotocol,”inProc.ICNP’99.

[12]N.OuryandT.Friedman,“Compressiondestracesdepertedepaquetsmulticastssurinter-

net,”inProceedingsofJourn´eesDoctoralesInformatiqueetR´eseaux(JDIR),Nov.2000.

[13]R.C´aceres,N.Duf eld,andT.Friedman,“Impromptumeasurementinfrastructuresusing

RTP,”http://www.77cn.com.cncom2002.

[14]J.Nonnenmacher,“Reliablemulticasttransporttolargegroups,”Ph.D.dissertation,Institut

Eur´ecom,1998.

[15]J.NonnenmacherandE.Biersack,“Optimalmulticastfeedback,”http://www.77cn.com.cncom‘98.

[16]——,“Scalablefeedbackforlargegroups,”IEEE/ACMTrans.onNetworking,vol.7,no.3,

pp.375–386,June1999.

[17]T.Friedman,“Scalableestimationofmulticastcharacteristics,”Ph.D.dissertation,UMass

Amherst,May2002.

[18]F.LoPresti,N.Duf eld,J.Horowitz,andD.Towsley,“Multicast-basedinferenceof

network-internaldelaydistributions,”IEEE/ACMTrans.onNetworking,vol.10,no.6,pp.761–775,Dec.2002.

[19]N.Duf eld,J.Horowitz,andF.LoPresti,“Adaptivemulticasttopologyinference,”inProc.

Infocom2001.

[20]M.CoatesandR.Nowak,“Networklossinferenceusingunicastend-to-endmeasurement,”

inProc.ITCConf.onIPTraf c,ModelingandManagement,2000.

[21]Y.Tsang,M.Coates,andR.Nowak,“PassivenetworktomographyusingEMalgorithms,”

inProc.IEEEIntl.Conf.onAcoustics,Speech,andSignalProcessing,May2001.

[22]N.Duf eld,F.LoPresti,V.Paxson,andD.Towsley,“Inferringlinklossusingstriped

unicastprobes,”http://www.77cn.com.cncom2001.

[23]M.CoatesandR.Nowak,“Networkdelaydistributioninferencefromend-to-endunicast

measurement,”inProc.IEEEIntl.Conf.onAcoustics,Speech,andSignalProcessing,May2001.

[24]——,“Sequentialmontecarloinferenceofinternaldelaysinnonstationarycommunication

networks,”IEEETrans.SignalProcessing,vol.50,no.2,pp.366–376,Feb.2002.

本文来源：https://www.bwwdw.com/article/n0wi.html