ChristopherB.MayerK.Selc¸ukCandan
VenkateshSangamComputerScienceandEngineeringDepartment
ArizonaStateUniversity
e-mail:chris.mayer,candan,venkatesh.sangam@asu.edu
Abstract
Werecentlyintroducedanovelmethodforcreatingreplicationsystemswherethereplicatedobjects’sizesand/orper-objectservicetimesarelarge[10].Suchreplicationsystemsarewell-suitedtodeliveringmultimediaobjectsontheInternet.Assumingthatuserrequestpatternstothesystemareknown,themethodcreatesrepli-cationsystemsthatdistributereadloadfairlytoserverssothatthelikelihoodofserversoverloadingisreduced.Thus,thesystemsproducedarehighlyavailableandresponsivetouserrequests.Inthispaper,wereportonresultsthatreveal(i)howserverloadsareaffectedand(ii)theimpactoftwosystemdesignparameters(indicatorsofasystem’sloaddistributionqualities)haveonserverloadwhenuserrequestpatternsdifferfromthatforwhichasystemwasdesigned.
1Introduction
ReplicationisanacceptedmethodforimprovingavailabilityandresponsetimesofInternetcontent.Themainideabehindreplicationisthatstoringcopiesofanobject(file,database,webpage,etc.)onserversthroughoutanetworkprovidessinglepointsoffailure.Sincetheobjectisavailableatmanyservers,highdemandloadscanbemetandthefailureofanindividualserverdoesnotmaketheobjectinaccessible.
MultimediacontentcanbedeliveredovertheInternetandcanbenefitfromreplication.Inthispaper,wefocusspecificallyonsystemsfordelivering(makingavailablefordownload)multimediacontent.Whendesigningamultimediadeliverysystemthefollowingconsiderationsandconstraintsapply.
ReadLoad:Inamultimediadeliverysystem,anobjectiswrittenbyitsauthorandremainsaccessibleforsomeperiodoftimebeforeitisremoved.Sinceanobjectissupposedtobeafinishedproduct,itisrarelyupdatedonceinpublication.Therefore,theloadonasystem’sserversisduemainlytohandlingusers’readrequestsandtheloadforwritingcanbeignored.Sinceweareconcernedwithonlythereadrequestload(readload),wewillusetheterm“load”and“readload”interchangeably.
ContentSize:Multimediaobjectssuchasvideofilestendtobelarge(tensorhundredsofmegabytes)andthereforerequirespecialconsiderationwhenbeingreplicated.
Largeobjectscannotberapidlyreplicatedinresponsetofluctuatingdemand.Therefore,itissensibletopre-positionmultimediaobjects.
Whilepre-positioningisgood,over-provisioningcanbebad.Creatingtoomanycopiesofanobjecthavingrelativelylowdemandiswasteful.Replicationcostsforanobjectshouldberelativetodemandfortheobject.ServiceTimes:Evenifusersconnecttoaserveroverbroadbandconnections,deliveringamultimediaobjecttoauserrequirestheserver’sattentionforalongperiodoftime.Theselongservicetimesoccurbecausethecontentiseitherlargeorstreamed,orboth.
ServerBehavior:Acommonbehaviorofserversisthattheycansupportmultiplesimultaneousrequestswhilemaintainingacceptablequalityofservice.Onceaserver’sloadcapacityisexceeded,theserver’sservicequalityrapidlydeclines,resultinginstalledrequestsanddisappointedusers.Incombinationwiththeservicetimepropertyabove,thisbehaviorsuggeststhatthebestwaytomaintaintheavailabilityofamultimediaobjectandkeepusershappyistoensurethatserversoperatebelowtheirloadcapacities.
ThisresearchfundedbyNSFgrant998404-0010819000.
Techniquesforeasingtheloadon,orimprovetheperformanceof,multimediaservers(mainlyvideoandstreamedmediaservers)include:caching[1,6,11,14,15],protocolsforstreamanddownloadsharing[5,8,11],andcustomizedserverdesigns[4,5,7].Whilealltheseapproachesarebeneficial,theyalldependonaccesstothecontent’ssource.Thus,theyarenotapanaceaforavailabilityandresponsiveness;abundantaccesstothesourcecontent,asreplicationprovides,isrequired.
TheprofusionofspecialtechniquesforvideoandstreamedmediadeliveryareindirectsignsthatmultimediashouldbestoredanddeliveredseparatelyfromothertypesofInternetcontent.Towardsthisend,severalvideo-onlydeliveryschemeshavebeenproposed([3,12,13]forinstance).Commonweaknessesoftheseschemesarethatcontentisassumedtocomefromasinglesource(i.e.,onlyoneentityisusingthesystem)andthedeliverynetworkisatree(whichnetworksarecommonlynot).
Inapreviouswork[10],weintroducedareplicationarchitectureandanaccompanyingdesignmethodwell-suitedfordeliveryofmultimediacontent,oranyotherInternetcontentwhereservicetimesorobjectsizesarelarge.Inourapproach,serversareorganizedintowrite-setsandread-setsandrequestsarefulfilledusingaspecificreadprotocol.Oursystemstructureismoregeneralthanthatofthetree-basedvideodistributionsystemsandfreelyhandlesmultiplecontentproviders.Inoursystem,aserver’sshareofsystemloadisproportionaltotheserver’scontributiontototalsystemreadloadcapacity.Inotherwords,loadisdistributedfairlytotheservers.Fairlydistributingloadminimizestheoddsthataserverwillexceeditsloadcapacity.Sinceserversoperateundertheirloadlimit,thesystemisresponsiveandcontentishighlyavailable.
In[10],werigorouslyexaminedtheimplicationsofourserverorganizationandreadprotocolandshowedthatloadfairnessisacomplexnon-linearconditionthatcannotbesolvedeasily.Therefore,in[10]wederivedtwokeyparameters:(describinggoodrequestdistributionstrategies)and(describinggoodserverorganization)thatreflectasystem’sloadfairness.Usingand,wedevelopedandtestedadesignmethodforquicklydesigningreplicationsystemswithnearlyoptimalloadfairness.
Inthispaper,wefurthertheworkbegunin[10]withastudyof(i)serverloadsand(ii)theimportanceofandtoserverloadswhenthepatternofreadrequestsenteringasystemdiffersfromthatforwhichthesystemwasdesigned.InSection2wereviewourreplicationapproach.WethenweexplainwhydivergentrequestpatternsrequirefurtherinvestigationinSection3.Next,wedescribehowweconductedexperimentstoevaluatetheimpactofand(Section4).Section5containstheresultsofourstudyandSection6summarizes.
2AReplicationSystemSuitableforMultimediaContentDelivery
Inthissectionwedescribethefeaturesandmechanicsofourmethodforcreatingareplicationsystem.Adetailedaccountingofthematerialsummarizedherecanbefoundin[10].
2.1SystemStructure
Areplicationsystemhasasetofservers,,whichitusestoreplicateobjects.Inourapproach,weorganizetheseserversintointersectingsubsetscalledwrite-setsandread-sets.Towriteanobject,awrite-setischosenandtheobjectisreplicatedoneachserverinthewrite-set.Toreadanobject,aread-setischosenandtheobjectisdeliveredtotherequestinguserfromaserverintheselectedread-set.Itisallowableforanobjecttobewrittentomultiplewrite-sets.Weensurethateverywrittenobjectcanbeaccessedfromanyread-setbyrequiringthateachread-setandeachwrite-sethaveatleastoneserverincommon.
Althoughtherearemanywaystoconstructwrite-setsandread-setswhilemaintainingthisrequirement,welimitourselves,forsimplicityreasons,tothespecialcasewherethewrite-setsandread-setsaredeterminedbyarrangingserversinagrid.Inagridfullypopulatedwithoneserverpergridcell,rowscorrespondtowrite-setsandcolumnstoread-sets.AsFig.1aindicates,eachread-setintersectseverywrite-setwithatleastoneserver.Somereadersmaynoticethatthisgrid-basedstructureresemblesgrid-basedquorumsystems([2]and[9]forexample).Thisisintentionalsincequorumsystemsfeaturedecentralizedoperationandhavethepotentialload-balancedserveroperation.
1
DuetotheunpredictablenatureofInternetroutingandtogeneralizeforanyrequestroutingscheme,wedonotspecifyhowrequestsare
ReadProtocol
Server D split into threevirtual serversA1Write setC2B3H1B1A2C3I1C1B2A3J1D1E1F2K1D2F1E2L1D3G1G2M11.Ausergeneratesarequestforanobject(aninitial-request)whichisdirectedtooneofthesystem’sservers(aproxy).Thedistributionofaparticularuser’srequeststotheproxiesiscalledtheuserrequestpattern.1
2.Theproxyselectsaread-setusingapreset,probabilisticproxystrategy.
3.Theproxyidentifiestheserver(s)withthemostup-to-datecopy(incasetheobjecthasbeenupdated)oftheobjectinthisread-set.Ifmorethanoneserverhasthemostup-to-dateobject,oneoftheserversispickedequiprobablytoservethedata.
4.Theproxyredirectstheusertotheserverithasselected.
5.Theuserreceivestheobjectfromtheappropriateserver,thusinducingareadloadontheserver.
Figure1:Agrid-basedreplicationsystemwhererowsarewrite-setsandcolumnsareread-setsisshownin(a).Thereadprotocolforthereplicationsystemisshownin(b).
Read set(a)(b)
2.2ReadProtocol
Animportantpartofourreplicationsystemisthereadprotocolshownin1b.Notethatlocatingtheappropriateserverwithinaread-setaddstothedelayinrespondingtorequests.However,thisdelayisextremelysmallcomparedtothetimerequiredtoserveamultimediaobjectandisunlikelytodetractmuchfromtheuser’sexperience.Further,thisdelaycanbeminimizedbyusingadirectoryservice,especiallysinceobjectlocationsrarelychange.
Basedonthestructureofwrite-setsandread-setsandthereadprotocol,wenowtheissueofloadfairness.
2.3Fairness
Tominimizethelikelihoodofaserveroverloading,aservershouldexperiencealoadproportionaltoitscontributiontothesystem’stotalcapacity.Inotherwords,systemloadshouldbedistributedfairlytoservers.Thiswillensurethatnoserverispushedbeyonditscapacityunlessthewholesystemis.Thiscanbeaccomplishedby
identifyingagoodassignmentofserverstowrite-/read-sets(thusdefiningthesystem’sstructure)andselectingeffectiveproxystrategiesfordirectinginitial-requeststoread-sets.
Asafirststeptowardsfairness,wefurtherrefinethesystem’sstructurebysplittingeachserverintooneor
,isrepresentedbyitsreadloadmorevirtualservers.Eachserverinthesystem,
.Denotingabasecapacityas,wespliteachserverintovirtualservers,capacity,
.Populatingthecellsofagridwithvirtualservers(Fig.1),insteadofregularservers,
resultsinnearlyequalamountsofcapacityateachgridcell.Ifthesystemreadloadcanbedistributedequallytoeachgridcell,thenwehaveachievedthegoaloffairness.Unfortunately,theloadonthevirtualserverineachgridcell,andinturnontheservers,dependson(i)thearrangementofvirtualserversinthegrid(thegridmapping),(ii)thepolicyfordecidingtowhichwrite-setsanitemshouldbewritten(write-policy),(iii)initial-requestloadsattheproxiesdeterminedbytheuserstrategies,and(iv)theproxystrategies.Hence,loadfairnessrequiresmorethanplacingvirtualserversinthegrid.
Givenagridofwrite-sets(rows)andread-sets(columns)populatedwithvirtualservers,atotalsystemread
,is:load,,thereadloadofserver,
(1)
denotestheprobabilitythatwrite-setcontainsaserverwiththerequestedcontent;Intheaboveequation,
denotestheprobabilitythatread-setischosenbyaproxygiventhatwrite-setcontainsthecontent;
directedtoservers.Instead,werelyontheobservationthatrequestroutingissomewhatpredictableandcanbeexpressedprobabilistically.
anddenotestheprobabilitythatserverisselectedforservingtherequestgiventhatwrite-setcontainstherequestedcontentandread-setischosen.
Toobtainloadfairness,weneedtoensurethatthegridmappingandproxystrategiesdistributethetotalsystemreadloadontoindividualserversinproportiontoeachserver’scontributiontototalsystemcapacity:
(2)
Notethatthisfairnessconditionisacomplexnon-linearequation,andsolvingitdirectlyisexpensive.Also,itisnotstraightforwardtofindamappinganddetermineproxystrategiesusing(1)and(2)directly.Therefore,weuse(1)and(2)toidentifyparameters,and,thatcanbeusedtoconstructhighlyfairreplicationsystems.
2.4Deriving
and
Tobeginthederivationofand,weassumethatthewrite-policydistributesobjectstowrite-setssuchthattherequestloadforeachwrite-setisequal.Thatis,ofthesystemloadisdirectedtothevirtualserversineachwrite-set.Withthisassumption(1)becomes
(3)
Usingthisequation,wecanrewritethefairnesscondition,(2),as
(4)
andaproxychoosesread-set,thenoneoftheserversNotethat,ifarequestcanbeservedfromwrite-set
andwillbeselectedtoservethecontent.Ifthereismorethanonehavingavirtualserverintheintersectionof
serverintheintersection,theneachserverhasanequalchanceofbeingchosen.Consequently,ifwelet
bethesetofserversthathavevirtualserversinwrite-set,;i.e.,;bethesetofserversthathavevirtualserversinread-set,;i.e.,;andbethesetofvirtualserversinread-setthathaveacorrespondingserverinwrite-set;i.e.,
,
then,
.Hence,(4)becomes
(5)
and.ThefirsttermisafunctionoftheNoticethat(5)hastwotermsthatcanbemanipulated:
proxystrategiesandthelatterdependsonthegridmapping.Byisolatingthesetwoterms,wegainameasureofinsightintohowtoconstructanoptimallyfairsystem.
2.4.1IsolatingProxyStrategies:Parameter
Inordertoextractthetermrelatedtoproxystrategies,weisolatethetermin(5)relatedtoread-setselectionbyproxiestoget
(6)
shouldbeinverselyproportionaltothenumberofwhichsaysthatthefractionofrequestsdirectedtoread-set
read-sets,.Inotherwords,initialrequestsshouldbedirectedinequalamountstoeachcolumn.Thisimpliesthat
Heuristicgridstructure1Heuristicproxystrategies2Close to optimally fairreplicationFigure2:Replicationusing
and
thecombinedeffectofalltheproxystrategiesshouldensureanequaldistributionofinitialrequesttoeachcolumn.
as,orread-set-value.Theideal-Wedenotethefractionofinitialreadrequestsdirectedtoread-set
isgreater(less)thantheideal-value,then,andthevirtualserversin,willvalueforaread-setis.If
receivemore(less)thantheirfairshareofsystemload.Likewise,sinceaserver’sloadisthesumoftheloadonitsvirtualservers,thehigherthesoftheread-setsinwhichaserverhasavirtualserver(averageserver),themoreloadtheserverwillreceive.
2.4.2IsolatingtheGridMapping:Parameter
Assumingthatallread-setshavetheideal-valueof,wecanreduce(5)to
(7)
Thisequationcanbesatisfiedbyensuringthat
(8)
holds.Theleft-handsideof(7)capturesthedegreeofcontentoverlapofserverread-setsandwrite-setswith.Isolatingthisoverlapweget
withotherserversthatshareboth
(9)
,orserver-value,indicates’svulnerabilitytobeingselectedforservingareadrequest.Theidealvalue
is,thenumberofvirtualservershas.Ifistoohigh()ortoolow(),thenwillbefor
selectedtoooftenornotoftenenoughandwillnotreceiveitsfairshareofload.
Asanexampleofhowtocalculatean-value,considerserverandthesecondwrite-setandsecondread-set
and.ThreevirtualhighlightedinFig.1.Serverhasthreevirtualservers,thus
(i.e.,ifread-set2isserversinthesecondread-sethaveaserverinthesecondwrite-set,so
chosenbyaproxyandtherequestedcontentisonaserverinwrite-set2,thenthreeserverscanbeselectedfor
andonlyhaveincommon..Thus,(i.e.,givendownload).Since
thatarequestisforcontentcontainedinwrite-set2andread-set2waschosen,serverhasa1-in-3chanceofservingtherequest).Repeatingthesecalculationsforserverforallrowsandcolumnsandsummingtheresults
.showsthathasaperfect-value:
2.5ReplicationBasedon
and
Toproducethefairestsystempossible,-and-valuesmustbeasclosetotheiridealvaluesaspossible.While
andindicatehowfairasystemis,theyarederivativesofthecomplex,non-linearfairnessconditionand,therefore,cannotbeuseddirectlytoconstructareplicationsystemeither.However,theydoprovideinsightastohowafairreplicationsystemshouldlook.In[10],weexploitedandtodevelopatwo-stepheuristicapproachforcreatingareplicationsystem(Fig.2).Inthefirststep,wesetthesystem’sstructurebymappingvirtualserverstogridcellssothateachserverhasgood-values.Thisstructureisthenusedtoformulateproxystrategiesthatresultinthebestpossible-valuesforeachgridcolumn.
Givenasetofserversandagrid,
1.Puttheserversintogroupssuchthatserversineachgrouphavethesamenumberofvir-tualservers.
2.Trytofillthegridwiththegivenclusters3.Ifsuchafillingisnotpossible,breaksomeofthemintosmallerclusterstofitthemintothegrid.Theresultisaserver-to-gridmapping.
Givenaserverset,agrid,andserver-to-gridmapping,anduserstrategies,
1.Identifythelinearconstraintsfor
(a)-optimality,
(b)write-policydependence(c)fairness,and
(d)columnselectionrestrictionsontheproxies.2.Solvewhileminimizingerrortermsintheconstraints.3.Extractproxystrategiesfromthesolution.
Theproxystrategiesresultinoptimal-values.
(a)(b)
Figure3:Pseudocodefor(a)thecluster-basedmappingalgorithmand(b)producing-optimizingproxystrategies.PseudocodeformappingagridisshowninFig.3a.Thealgorithmclustersvirtualserversandthenmapstheclusterstothegrid.Clusteringlimitstheinteractionbetweenserversthatgivesimperfect-values.Ifallvirtualserverscanbemapped,whilemaintainingclusterintegrity,thenallserverswillhaveperfect-values.Notethatclustersmustsometimesbesplitintosmallerpiecesinordertofacilitateplacement.Thiscancreateimperfectionsin-values.However,asweshowedin[10],thenegativeeffectsofsplittingareminimal.
Oncethesystem’sstructureisset,weusethestructuretoformulatealinearprogram(LP)andsolvetheLPtofindproxystrategiesforthesystem.Inadditiontothesystem’sstructure,theLPconsidersotherfairness-relatedfactorssuchasthesystem’swrite-policyanduserrequestpatterns.Figure3bshowspseudocodefortheLP’sconstructionandextractionofproxystrategies.ThespecificsoftheLPcanbefoundin[10].TheoutputoftheLParetheproxystrategiesthatproducethebestpossible(closesttoideal)-valuesforeachread-set.Foreachproxy,itsparticularproxystrategygivesthefrequencyatwhichitshouldselectaread-setwhenhandlinginitial-requestsfromusers.
In[10]westudiedtheimpactofandonserverloadfairness.Weshowedthatgrid-basedreplicationsystemsconstructedusingourtwo-stepapproacharehighlyfairwhenoperatingconditionsareexactlythatforwhichthesystemwasdesigned.Inthispaper,weinvestigatewhathappenswhenuserrequestpatternsnolongermatchthepatternsforwhichthesystemwasdesigned.Specifically,weexamine(i)theimportanceofandtoloadfairnessand(ii)howserverloadsareaffecteduserrequestpatternsdeviatefromexpectations.
3DivergentInitial-RequestLoads
Sinceproxiesredirectclientinitial-requeststoservers,theperformanceofthereplicationsystemdependsontheexpecteddistributionoftheusers’initial-requeststoproxies.Asexplainedearlieraspartofthereadprotocol,theprobabilitythatagivenuser’sinitial-requestsarriveatacertainproxy,isgivenasadistributionfunctioncalledtheuserrequestpattern.Userrequestpatterns(oratleasttheircumulativeeffectontheproxies)areaninputtothelinearprogram(LP)thatissolvedtogettheproxystrategiesforselectingread-sets.Thus,areplicationsystemistailoredfortheuserrequestpatternsinputintotheLP.Sinceuserrequestpatternsarewillchangeovertime,usingafixeduserrequestpatterntoconstructareplicationsystemisapotentialweaknessofourapproach.Ifrequestpatternschangetoomuch,serverloadfairnesscouldbelostandthesystemwouldperformpoorly.
Intheremainderofthispaper,wepresenttwokindsofresults,obtainedexperimentally,aboutourproposedreplicationsystem.
Weshowtheimportanceofandtoloaddistributionwhenuserrequestpatternsdeviatefromthoseforwhichthesystemwasdesigned.
Weshowthatsystemsbuiltusingourtwo-stepconstructionapproach(seeprevioussection)areresilienttochangesinuserrequestloads.
4ExperimentalSetup
Inordertotesttheperformanceofreplicationsystemsthatuseourwrite-/read-setstructureandreadprotocol,wehaveconstructedatestbedsystemthatusesrealwebservers.Theuseofrealserversaddsadegreeofrealismthat
ordinarysimulationdoesnotprovide.Becauseofspaceconstraintswecannotgointothedetailsofthetestbedsysteminthispaper.However,wedodescribetheconditionsforconductingexperiments.
Toprepareforanexperiment,serversarearrangedintotheirwrite-setsandread-setsusingthegridstructureandgiventheirproxystrategies(calculatedinadvancebasedonexpectedloads).Adifferentobjectiswrittentoeachwrite-set(arowofthegrid).Alldataitemshavethesamesizeandhencethesamedownloadtimes.Havingeachobjectbethesamesizeandhavingeachwrite-setcontainasingleobjectcapturestheeffectsofaperfectlytunedwrite-policy.Thedownloadtimeofanobjectissimulatedbyhavingserversexecuteasleepoperationof5seconds.Therunningtimeforanexperimentis40timesthesleeptime,or200seconds.Thisistheminimumtimeneededforanexperimenttoshowlong-termloadingbehavior.Oncethesetupstageiscomplete,theexperimentcanbegin.
Performinganexperimentconsistsofgeneratinguserrequestsforobjectsandthehandlingofthoserequestsbythesystem.Userrequestsareregularly-spacedoverasecondtomeetaspecifiedrequestrate.Forexample,iftherequestrateis10requests/sec,thenanewrequestisgeneratedeverytenthofasecond.Uniformrequestgeneration,whilesimple,isadequatesinceobjectsizes,andhencedownloadtimes,arerelativelylargecomparedtorequestinter-arrivaltimes.Foreachrequest,anobjectisselecteduniformlyatrandom.Theproxyserverthatwillreceiveanewlygeneratedinitial-requestisselectedatrandomusingaprobabilitydistributionthatmodelstheeffectsoftheuserrequestpatterns.
Experimentswereperformedusing20setsofservers.Aserversetistheserversavailableforusebyareplicationsystem.Serversetsweregeneratedsothatthenumberofvirtualserversineachsetequalled64andwouldfillan8x8grid.Thenumberofvirtualserversperserverwasrandomlygeneratedaccordingtothefollowingdistribution:
oftheservershave1,have2,have3,have4,andhave5virtualservers.
Inordertoobservetheeffectofasrequestpatternschange,wemapaserversettoagridusingtwodifferentmappingstrategies:
Random.Thisstrategyrandomlymapsvirtualserverstoagrid.Thisresultsinserver-valuesthatdiffergreatly,bothupanddown,fromtheirideals.
Cluster.GridsaremappedusinganalgorithmbasedontheclusteringpseudocodeofFig.3a.Clusteringresultsinidealornearlyideal-valuesforallserversinagrid.
Toobservetheeffectof,weusedtwomethodsforformulatingproxy-strategiesthatresultinfavorableandunfavorable-values.
Not-optimized.Eachproxyredirectsinitial-requestsequiprobablytotheread-sets(gridcolumns)inwhichithasvirtualservers.Assuch,read-setscanvarygreatly,beinghighlyinfluencedbythesystem’sstructure.-optimized.Herealinearprogramisformulatedandsolvedtoobtainproxy-strategiesthatproduceoptimals.Aswiththeabovenon--optimizedstrategy,proxiescanonlyredirectinitial-requeststoread-setsinwhichtheproxyhasvirtualservers.Evenwiththisrestriction,resultingsareclosetoidealregardlessofmappingstrategy.
Mixingmappingandproxystrategiesresultsinfourreplicationsystems(mapping/proxysystemsorMP-systems)foreachserverset.Themixofgoodandbad-and-valuesinthefoursystemsallowsustoobservetheinfluenceofandonserverloadasinitial-requestloadsattheproxiesvaryinresponsetochanginguserrequestpatterns.WerefertoanMP-systembythemappingmethodusedandthepresenceof-optimizationasshowninFig.4andlistedbelow.
RANDOM:not-or-optimized
CLUSTER:-optimized,butnot-optimized
RANDOM-:not-optimized,but-optimizedCLUSTER-:-and-optimized.
Forthetests,abaselineloadof6.4requestspersecondisthearrivalrateofinitial-requeststoeachproxy(256requestsperproxydividedbythe40secondexperimentlength).Thus,the-optimizedsystemswereconstructedforuserrequestpatternswhosecumulativeeffectisthateachproxyisequallyloadedwithinitial-requests.
Inordertosystematicallyexploretheeffectsofvaryinguserrequestpatterns,werandomlyselectedsubsetsofproxiesineachserversetandsubjectedthemtoincreasedinitial-requestloads.2Werefertothecombination
Notethatweonlyincreaseinitial-requestloadsatproxies.SinceInternetdemandonlygrowsovertimeandunevenly,thisisareasonablethingtodo.
2
cluster mappingfor optimized NClustered Gridsno σ optimizationCLUSTERCLUSTER-σσ optimizationServer Setsno σ optimizationRandom Gridsrandom mappingfor non-optimized Nσ optimizationRANDOMRANDOM-σFigure4:Namingconceptforthefourtypesofreplicationsystemscreatedfromaserverset.
ofproxiesselectedtoreceiveextraloadandtheextraloadtheyaregivenasaninitial-request-combination(IR-combo).Foragivenserverset,therearesevenIR-comboswhichformaninitial-request-set(IR-set).AnIR-setisbuiltasfollows.ThefirstIR-combointhesetiseachproxyreceivingthebaselineloadInthiscombination,0%oftheproxiesreceive0%extraload.Wecallthisthe0%-0%IR-comboorthebaselinesystem.Next,three
,,andofthenumberofproxiesintheserversetareformed,withtheproxysubsetsofsizes
largersubsetsreusingserversfromthesmallerones.Theproxiesinthesesubsetswillreceive25%andthen50%extrainitial-requestloadabovethebaselineload.CombiningtheproxysubsetsizesandextrarequestpercentagesproducestheremainingsixIR-combosinanIR-set:10%-25%,10%-50%,20%-25%,20%-50%,40%-25%,and40%-50%.
Example4.1Wenowillustratehowtocreateaninitial-request-set.Consideraserversetwiththirtyserversnum-bered1through30andabaselineinitial-requestloadof10requestspersecond(req/sec).
1.The0%-0%combinationisallproxiesreceiving10req/sec.
2.Forthe10%proxysubsetwepickthreeproxies,say5,9,and21.Forthe10%-25%combination,weincreasethenumberofrequeststothesethreeproxiesby25%;theywilleachreceive12.5req/sec.Proxiesnotinthesubsetstillgetonly10req/sec.Tocreatethe10%-50%combination,initial-requestsareincreasedby50%to15req/secatthethreeproxies.
3.Tobuildthe20%subset,2,5,9,11,21,29,the10%subsetisaugmentedbythreemoreservers:2,11,and29.Combinations20%-25%and20%-50%arecreatedbyincreasingtheinitialloadsattheseproxiesby25%and50%,respectively.
4.The40%subsetisthe20%subsetplusservers1,15,17,23,24,and28.Increasingtheinitial-requestsby25%and50%attheselectedproxiesgivescombinations40%-25%and40%-50%.
ByrunningaserversetthrougheachofitsfourMP-systemsandeachofitssevenIP-combos(eachserversetisrun28times),wecandetecttrendsinserverreadloadsandcomparetheinfluenceofandonserverloadasuserrequestpatternsvary.
5ResultsandObservations
Inthissection,weanswersixquestionsabouttheeffectsofandwheninitial-requestloadstoproxiesdivergefromtheirexpectedvalues.Todothis,weobservetheextraloadexperiencedbyaserverwhenoperatingaspartofthefourMP-systemscreatedfromtheserversetofwhichtheserverisamember.Extraloadisthedifferenceinaserver’sreadloadinanexperimentwhereuserrequestpatternshavechangedandinanexperimentwhereuserrequestpatternsareexactlywhatthesystemwasdesignedfor(the0%-0%IR-comboorbaselinesystem).Serverreadloadistheaveragenumberofreads(downloads)experiencedbyaserverineachsecondofanexperiment.Forexample,ifserverhadaloadof5readrequestspersecondinabaselinesystemexperimentandthenhadaloadof7requestspersecondina20%-50%combinationthen’sextraloadis2,anincreaseof40%.
TheevidencesupportinganswerstoQuestionsOnethroughFourinvolvetwentydifferentserversets.QuestionsFiveandSixareansweredusingresultsfromfourroundsofrepeatedexperimentsonthesecondofthetwentyserversets.Inthefourrounds,theinitial-request-setswerenotchanged.Sincespaceislimited,wepresentevidencerepresentingbehavioraltrendsseenthroughoutalltheexperiments.
Figure5:Differencesinpercentageofextraserverload,RANDOMstrategies.
,as
-valueschangebetweentheCLUSTERand
(a)
(b)
,asaverageserverFigure6:Differencesinthepercentageofextraserverload,
RANDOMandCLUSTERsystemsand(b)theCLUSTERandCLUSTER-systems.
changesbetween(a)the
5.1QuestionsandAnswers
QuestionOne:Ifaserver’s-valueincreasesordecreasesbetweendifferentmappingstrategies,doestheextrareadloadexperiencedbytheserveralsoincreaseordecrease?
,experiencedbyserversastheir-Figure5displaysthedifferenceinthepercentageofextrareadload,
,valuesimproveunderdifferentmappingstrategies.Thex-axisshowsthedifferenceinaserver’s-value,
whencluster-mapped(CLUSTERsystems)versusrandomly-mapped(RANDOMsystems).Eachdatapointrepresentsaserver.Weseethatapositive(negative)moveinaserver’s-valuecausesalikewisechangeinextraloadattheserver.Inallexperiments,thecorrelationinmovementinandextraloadisbetween83%and86%.Thisbehaviorindicatesthat,afunctionofthegridstructure,hasastronginfluenceonwhereextraloadisdistributed.
QuestionTwo:Ifthesofaserver’sreadsetsincreaseordecreaseunderdifferentproxystrategies,doestheextrareadloadexperiencedbytheserveralsoincreaseordecrease?
,asafunctionofYes,however,thetrendisnotaspronouncedasitwasfor.Figures6aand6bshow
,intheaverage-valuesofaserver’sread-sets(averageserver),underdifferentlyformulatedthedifference,
proxystrategies.Figure6acomparesRANDOMandCLUSTERsystemswhereasFig.6bcomparesCLUSTERandCLUSTER-systems.Notethatthetiltoftheregressiontrend-linesinbothofthesefiguresislessthanthetiltcausedbychangesin(Fig.5),suggestingthatthetrendisnotasstrongasitwasfor.Indeed,thecorrelationbetweenchangesinaverageserverandextraloadrangedfromonly61%to65%inallexperiments.Furthermore,inFigs.6aand6bthedatapointsarespreadtoallfourquadrantsofthegraph,whereasinFig.5datapointsaremostlyintheall-positiveorall-negativequadrants.Thissuggeststhathasamorepronouncedeffectthan.Note
(a)(b)
(c)
,between(a)theCLUSTERandFigure7:Histogramsshowingdifferencesinpercentageofextraserverload,
RANDOMsystems(b)theRANDOM-andRANDOMsystems,and(c)theCLUSTER-andCLUSTERsystems.
thatthedatapointsaremorewidelyspreadinFig.6athanin6bindicatingthat’seffectonextraloaddistributionismorevisibleonlyafterthegridisalreadyoptimizedfor.
QuestionThree:Howisextrareadloaddistributedinsystemswithgood-valuesversussystemswithbad-values?
TheanswertothisquestioncanalreadybeenseeninFigs.5and6awhichcompareextraloadsinrandomly-mappedgrids(largeerrors)withthoseofclusteredgrids(smallerrors).InFig.6a,itappearsthatthedatapoints
region.Ahistogramshowingthedistributionofvaluesconfirmsthisobservationaremostlyinthe
(Fig.7a).Whenclustermappingisused,alargeportion(anaverageof63%acrossallexperiments)oftheserversgethigheramountsofextraloadthanwhenrandomlymapped.Thisindicatesthatsystemswithgood-valuesmoreevenlydistributeextraloadtoservers.
QuestionFour:Howisextrareadloaddistributedinsystemsthatare-optimizedversusnon--optimized?
Loaddistributionisminimallyaffectedbyoptimizingfor.Whencomparingrandomly-mappedgridsbefore
to(Fig.7b).Similarlyforclusteredandafteroptimization,extraloadchangesforaserverrangefrom
to(Fig.7c).Comparatively,loadshiftsintherangeofgrids,theextraloadchangesrangefrom
towereobservedforrandomlymappedgridsversusclusteredgridswithoutoptimizingfor(Fig.7a).Thus,theshiftinloadisduemainlytochangesinserver-values.CombinedwiththebehaviorseenintheanswerstoQuestionsOnethroughThree,weconcludethatgridstructure,ascapturedby-values,andnotproxystrategies,whichdetermines,isthemainfactorinwhereextrareadloadisdistributed.
Also,notethatunlikeinFig.7a,thehistogramsinFigs.7band7carecenteredonzeroloaddifference.Thismeansthattheoveralleffectofoptimizationonextraloaddistributionisminimal.
QuestionFive:Whatdoesaserver’s-valueindicateaboutitsextrareadload?
WehavealreadypartiallyansweredthisinQuestionsOneandThree,butprovideadditionalanalysishere.
,experiencedbyserversforthe20%-25%and20%-50%Figure8showsthepercentageofextrareadload,
initial-request-combinations(IR-combos).Figure8ashowsresultsfortheRANDOMstrategyandFig.8bshowstheCLUSTER-strategy.TrendlineshelpdistinguishbetweenthetwoIR-combos.Inbothgraphsweseethatsmaller-valueshavehighlyvariableextrareadloads.Thisimpliesthatsystemscouldbemaderobusttovariancesininitial-requestloadsbymaking-valueslarge.However,increasing-valueswouldnegativelyaffectloadfairness.
Notealsothatextrareadloadhardlychangesfromthatofabaselinesystemforthe20%-25%proxy/loadcombi-line).However,readloadsjumpnoticeablynationinFig.8(i.e.,thelinearregressionlineliesrightonthezero
forthe20%-50%combination.Sincethisbehaviorappearsregardlessofmappingstrategy,thissuggeststhatthegridstructureandreadprotocolhasagooddealofresiliencetovariationsininitial-requestloadsandthatbeyondacertainthresholdperformancesignificantlydegrades.
QuestionSix:Whatdothesofaserver’sread-setsindicateabouttheserver’sextrareadload?
(a)
Figure8:Percentdifferencesinserverloadsplottedbyserversystemand(b)CLUSTER-system.
(b)
-valuesforthesecondserverset’s(a)RANDOM
(a)
Figure9:Percentdifferencesinserverloadsplottedbyaverageserversystemand(b)theCLUSTER-system.
(b)
forthesecondserverset’s(a)RANDOM
Results,arrangedbytheaverage-valuesofaserver’sread-sets(averageserver)forthesecondserverset’sRANDOMsystemareinFig.9aandresultsforthesecondserverset’sCLUSTER-systemareinFig.9b.Inboth
,occurwhenaverageserverequalstheidealforfigures,weseethatthelargestswingsinextrareadload,
thegrid(whichis0.125)andisthesolefactorinserverloading.TheRANDOMsystemalsohaslargedifferences
errorsarelargeintheinextraloadforotheraverages(mostnotablyat0.136).Thisisduetothefactthat
randomly-mappedsystems,makingnearlyirrelevanttoserverloading.
NoticethatintheRANDOMsystemextraloaddecreasesasaverageserverincreases,whichiscountertoourexpectations.Theexplanationforthisbehavioristhat,forthisparticularserverset.theproxiesreceivingextrainitial-requestsallhaveaverageserversthatarelessthantheidealof0.125.Therefore,theextrareadrequestsaredirectedmostlytoread-setswithlessthanidealcausingtheserversinthoseread-setstoreceivethebulkoftheextraload.
5.2SummaryofResults
Overall,theexperimentsrevealthefollowingnotableobservationsabouttheproposedreplicationsystemwhenuserrequestpatternsdeviatefromthatforwhichasystemwasoriginallydesigned.
,whichisafactorofthegridstructure,hasthegreatestinfluenceonwhereextraserverloadisdistributed.canalsohaveaneffect.However,’simpactisoftenmaskedby.
Systemswithgood-valuesmoreevenlydistributeextraloadtoserversthandosystemswithbad-values.
Serversinsystemsbuiltaccordingtoourconstructionmethodandoperatingprotocolscanbeinsulatedfromreadloadincreaseswheninitial-requestloadsincreaseatasubsetoftheproxies.
6Conclusion
In[10]weproposedandvalidatedanapproachfordevelopingreplicationsystemswhichspecializeinhostinglargeobjects,orwhereuserrequestshavelongservicetimes,orboth.Thereplicationstrategyattemptstopreventserversfromoverloadingbyfairlydistributingreadloadstoserversbasedontheirrelativecapacities.Ourapproachtodevelopingafairreplicationstrategydependsonoptimizingtwokeyparameters,and.In[10]weshowedthatsystemsdesignedaccordingtoourapproacharehighlyload-fairwhenuserrequestpatterns(thearrivalrateofusers’initial-requests)toserversinthesystemmatchthatforwhichthesystemwasdesigned.
Inthispaperwefurtherstudiedtheperformanceofsystemsconstructedwithourapproach.Weshowedtheinfluenceandhaveonserverloadwhenuserrequestpatternsvaryfromthatforwhichasystemwasdesigned.Experimentalresultsindicatethatsystemstructure,capturedby,hasthemostinfluenceonloaddistribution.alsoaffectsloaddistribution,butnotasmuchas.Wealsosawthatserverloadingisrelativelyunaffectedbymildtomoderateshiftsinuserrequestpatterns.
References
[1]J.M.Almeida,D.L.Eager,andM.K.Vernon.Ahybridcachingstrategyforstreamingmediafiles.InMMCN,
pages200–212,2001.
[2]S.Y.Cheung,M.H.Ammar,andM.Ahamad.Thegridprotocol:Ahighperformanceschemeformaintaining
replicateddata.IEEETransonKnowledgeandDataEng,4(6):582–592,1992.
[3]I.Cidon,S.Kutten,andR.Soffer.Optimalallocationofelectroniccontent.InINFOCOM,pages1773–1780,
2001.
[4]J.Gemmell,H.M.Vin,D.D.Kandlur,P.V.Rangan,andL.A.Rowe.Multimediastorageservers:Atutorial.
IEEEComputer,28(5):40–49,1995.
[5]S.GhandeharizadehandR.R.Muntz.Designandimplementationofscalablecontinuousmediaservers.
ParallelComputing,24(1):91–122,1998.
[6]K.Guo,M.M.Buddhikot,Y.Chae,andS.Suri.Rcache:Designandanalysisofscalable,faulttolerant
multimediastreamcachingschemes.InScalabilityandTrafficControlinIPNetworks,2001.
[7]S.Harizopoulos,C.Harizakis,andP.Triantafillou.Hierarchicalcachingandprefetchingforhighperformance
continuousmediaserverswithsmartdisks.IEEEConcurrency,8(3):16–22,2000.
[8]K.A.HuaandS.Sheu.Skyscraperbroadcasting:Anewbroadcastingschemeformetropolitanvideo-on-demandsystems.InSIGCOMM,pages89–100,1997.
[9]A.Kumar,M.Rabinovich,andR.K.Sinha.Aperformancestudyofgeneralgridstructuresforreplicateddata.
InICDCS,pages178–185,1993.
[10]C.Mayer,K.S.Candan,andV.Sangam.Constraints,parameters,andstrategiesforreplicatinglargecontent
forwebdelivery.TechnicalReportTR-02-007,ComputerScienceandEngineeringDepartment,ArizonaStateUniversity,2002.
[11]S.Sen,J.Rexford,andD.F.Towsley.Proxyprefixcachingformultimediastreams.InINFOCOM,pages
1310–1319,1999.
[12]C.Shahabi,M.Alshayeji,andS.Wang.Aredundanthierarchicalstructureforadistributedcontinuousmedia
server.InIDMS,pages51–664,1997.
[13]C.Vassilakis,M.Paterakis,andP.Triantafillou.Videoplacementandconfigurationofdistributedvideosys-temsbasedoncableTVnetworks.MultimediaSystems,8(2):92–104,2000.
[14]B.Wang,S.Sen,M.Adler,andD.Towsley.Optimalproxycacheallocationforefficientstreamingmedia
distribution.InINFOCOM,2002.
[15]K.-L.Wu,P.S.Yu,andJ.L.Wolf.Segment-basedproxycachingofmultimediastreams.InWWW,pages
36–44,2001.
因篇幅问题不能全部显示，请点此查看更多更全内容