Minimizing Congestion in General Networks_免费下载

MinimizingCongestioninGeneralNetworksHaraldR¨acke∗HeinzNixdorfInstituteandDepartmentofMathematicsandComputerSciencePaderbornUniversity,Germanyharry@ractAprincipletaskinparallelanddistributedsystemsistore-ducethecommunicationloadintheinterconnectionnetwork,asthisisusuapaperweintroduceaframeworkforsolvingon-lineproblemsthataimtominimizethecongestion(imumloadofanetworklink)ythisframeworktotheproblemofon-hscenariosweachieveacompetitiveratioofO(log3n)-linealgorit,thepousroutingstrategiescaneasilybeimplementedindistributedenvironmentsandhav,thefirstobliviouspathselectionalgoritore,aprincipletaskforthesesystemsistodesigndistributedapplicationr,itmaynotbesuffi,thetotaltrafficinthenetwork,tion,,themaximumtakenoverallnetworklinksofthepaperweintroduceageneralframeworkformin-imiziameworessfulityieldsasolu,meworkisbasedonreprestreetopologyisverysimplemanyonlineproblemscanbesolvedeffiiningatreesolutionofanonlineproblemandthetreerepresentationofthenetwork,theframemeworkisevaluatedbyapplyfi[2,10]).Inthisproblemroutingrequestsconsistingofasourceandadestinationpoint,hrequesttheroutingalgoondproblemisadatamanagementproblemthatwasintroducedin[11].Here,tan-agementalgorithmforthisproblemhastodecidewheretoplacecopiesofsharedobjectsinthenetwoructionInlargeparallelanddistributedsystems,suchasnetworksofworkstationsortheInternet,thebandwidthoftheinter-connectionnetworkusuallduetothefactthatitisoftenmoreexpensiveormoredifficulttoin-creasethebandwidthoftheinterconnectionnetworkthtedbyDFG-Sonderforschungsbereich376“Massive¨t:Algorithmen,Entwurfsmethoden,Anwendungen”andbyParallelitatheISTProgrammeoftheEUundercontractnumberIST-1999-14186(ALCOM-FT)∗Partially

finitionofthemodelWemodelthenetworkbyaweightedgraphG=(V,E)of|V|=nnodesand|E|esrepresenttheprocessors,theedgesrepresentthelinksandthefunctionb:E→R+-quenceσofrequests,writerequeststosharedobjects,areirtoobtainasimpleanduna,σi+1isnotissuedbeforeσweverthatthealgorithmsthatwewilldevelopforthissequentialmodelcanhandleparallelandoverlappingrequests,formanceofanonlinealgorithmAisevaluatedbycomparingittoanoptimalofflinealgorithmOPT,whichhasfninputsequenceσ,letCA(σ)andCOPT(σ)denotethecongestionproducedbyAandOPT,respectively,whenprocessingσ.AlgorithmAiscalledc-competitiveifthereexistsaconstanta(independentofσ)suchthatCA(σ)≤c·COPT(σ)+a,foranysequenceσ.Thealgorithmissaidtobestrictlycompetitiveifa=caseitmustfulfilltheaboveboundwithhighprobability.1Intheframeworkofcompetitiveanalysistheinputse-quenceisviewedaschosenbyanadversaryinordertore-fl,therequestsequencvenalgorithmandaninputsequenceσwedefinethe(absolute)loadofalinke∈Etobetheamountofdatathatmustbetransferredbythisconnectionwhenσfiy,wedefinethecontmetricsfortheonlineroutingandthedatamanagementproblemaredefinlineroutingproblehrequestapathconnectingthecorrespondingnodesinthenetworkhastobespecifiatamanagementproblemtheranagementstrategyisallowedto1Throughoutthepaper,congestionC,w.h.p.(withhighprobability)meanscongestionatmostC+x,withprobabilityatleast1−2−Ω(x).migrate,methatanymessage,includingmessagesformigratingcopies,messagesforlocatingcopiesinthenetworkaswellasmessagesforinvalidatingcopies,attheaboveuniformdefinitionoftheloadassociatedwithmessagesisoultscaneasilybeextendedtonon-uniformdefinitions,usworkandnewresultsAcentralized,O(logn)-competitiveonlineroutingalgorithmwasfi[2].tingrequestoccursthealgorithmchoosesashortestpathbetwpetitiveratiwbackofthisalgorithmisthatitiscentralizedandthchandAzar[4],ointheirscenarioitisstilldifficultforadistributedimplementationtopaperweshowthesomehowsurprisingresultthatknowledgeofthecurrentloadinthenetworkisnotneededinordertoachieveapolylogarithmiccompetitiveratio,,aroutingalgorithmwherethepathselectedforthei-threquestσidoesnotdependonroutingdecisionsmadeforotherrequestsσj,j=,thepathmayonlydependonthesourceoftherequest,atrandomizationisessential,forthedesignofanobliviousroutingalgorithmwithlowcompetitivera-tio,sincethereexistlargelowerboundsfordeterministicroutingprotocols(see[5,7]).Obliviousroutingstrategiescaneasilybeimplementedindistributedenvironmentsandthereforeman[12,14]).In[1]nowledgethisworkisthefirstanainedatamanagementproblemwiththegoalofminimizingthecongestionofthenetworklinkswasinves-tigatedin[11].rmore,theyshowhowtoachieveanO(logn)-competitivealgorithmformeshesviaa

[13]itisclaimedthatthisapproachcanbeextendedtoothernet-worksbyprovidingasuitable,paperwedefinetheexactpropertiesthatthehierarchicaldecompositionhastofulfillvesanO(log3n)-eoftheframeworkInthefollowingwesketchthegeneralconceptforsolmeworkisbasedonabi-simulationbe-tweenatargetnetworkG=(V,E)andanassociatedtreenet-workTG=(Vt,Et),tworksareweightedwithb:E→R+andbt:Et→R+describingthebandwidthofedgesinEandEt,fi,anyrequestsequenceσforanonlineproblemthatproducescongestionCwhenitisprocessedonGcanbeprocessedonTGwithcongestionC,ssimulationwewillpresentamappingπ1:V→ssorv∈VofGisthensimulatedbyitscounterpartπ1(v)atthisfirstsimulatioondsimulationstepweshowforcertainonlineproblemsthatthenetworkGcansimulatethetreeTGinsuchawaythattncretely,ifarequestsequenceσcanbeprocessedonthetreewithcongestionCt,thenitcanbeprocessedonGwithcongestionc·Ct+K,w.h.p.,whereKisaconstantindependentofσ.Forthissimulationanodev∈VmayhavetosimulateseveralnodesofVt,sinceusually|Vt|>|V|.Wedenotethe(randomized)mappingusedforthesecondsimulationstepπ2:Vt→onallyforthissimulationstepwedescribehowtheroutingbetweenhostnodesinGthatsimulateadjacenttreenodesisperformed.(NotethatthisiseasyforthefirstsimulationsinceTGisatree.)Theexactdescriptionoftheroutingandthedefinitionsofπ1andπpurposeofthissectionitisonlyimportantthatπ2(π1(v))=vholdsforeachv∈hesesimulationresultshelpusinsolvingcongestion-basedonlineproblemsongeneralnetworks?Aconditionforourframeworkisthattheonlineproblemcanbesolvedeffi,supposethatthereisact-competitivealgorithmforthetreeTG(forsomevaluect).ewearegivenasequenceσt(G)andCopt(TG)denotetheoptimalcongestionifσisprocessedonGandTG,respectively.(ForprocessingσonTGweassumethatarequestoriginallyissuedatanodev∈Visissuedatπ1(v)∈Vt,instead.)Furthermore,letConl(TG)denotethecongestionproducedbytheonlinetreestrategywhenprocessingσfirstsimulationstepandthect-competitivenessyieldCopt(G)≥Copt(TG)≥1c·Conl(TG)−Ktt,whereKtissomeconstantthatdoesnotdependonσ.Now,wecansimulatel(G)denotethecongestionofthisstrategyforrequestsequenceσ.Notethatsinceπ2(π1(v))=vforeveryv∈Vthebi-simulationdoesnotreorderthenodesofVandinparticu-lardoesnotchangetherequestsequenceσ.(Forthefirstsimulationsteprequestsfromanodev∈Varemappedtoπ1(v)∈secondsimulationsucharequestismappedtoπ2(π1(v))=v.)LetConl(G)denotethecongestionofthisstrategyforrequestsequenceσandletcdenoteonl(G)≤ct·c·Copt(G)+Kt+,theonlinestrategyforGisct·cialpartoftheproofistochooseTGinsucollowingsectionwewilldescribethegeneralmethodforchoosingTGanddefinecertainparametersforTGthatmainlyinflion3wewillthenshowthatgivenadecompositiontreeTGwith“good”ywewillshowinSection4thatforanynetworkGthereisatreeTGsuchthatallparametersrelevantforthesimulationshave“good”ompositiontreeInthissectionwedescribethegeneralmethodforchoosingthedecompositiontreeTGforanetworkG=(V,E)ompositiontreeTGcorthefolsetsXandYarecalledintersectingifneitherofXY,YXandX∩rmore,alaminarsetsystemofsubsetsofViscompleteifitcontainsthesetVandallsets{v},v∈completelaminarsystemScontainingsubsetsofVweconstructadecompositiontreeTG=(Vt,Et)hS∈

lbelsintherightfigureindicatethebandwidthoftherespectiveedge.(Edgesintheleftfigurehavebandwidth1.)callSthesetortheclustercorrespondingtovt,andvtthe(tree)ollowingtheclustercorrespondingtoanodevt∈esutandvtinTGareconnectedifSut⊂SvtorSut⊃SvtandifthereisnoS∈SsuchthatSut⊂S⊂SvtorSut⊃S⊃Svt,atbythisdefinitionTGisindeedatree,meTGtoberootedatthenodecorrespondingtotheclusterV,definitiontheleavesofTGcorrespondtosets{v},v∈,finetheroottobeonlevel0ofTGandallnodeswhoseparentsareonlevel