sourcep2pover

AUtility-AwareMiddlewareArchitectureforDecentralizedGroupCommunicationApplicationsJianjunZhang1,LingLiu1,LakshmishRamaswamy2,GongZhang1,andCaltonPu11CollegeofComputing,GeorgiaInstituteofTechnology,Atlanta,GA30332,USA{zhangjj,lingliu,gzhang3,calton}@cc.
gatech.
edu2DepartmentofComputerScience,UniversityofGeorgia,Athens,GA30602,USAlaks@cs.
uga.
eduAbstract.
AlthoughunstructuredPeer-to-Peer(P2P)networksprovideeconomicalplatformsforsupportinggroupcommunicationapplications,theirad-hocnatureposessignicantchallengestotheperformanceofthegroupcommunicationservices.
ThispaperpresentsthedesignandimplementationofGroupCastautility-awaremiddlewarearchitectureforscalableandecientP2Pgroupcommunications.
TheGroupCastdesignischaracterizedbytwouniquefeatures.
First,wepresentautil-ityfunctionforquantifyingtheroleofunicastlinksinenhancingthescalabilityandeciencyofthegroupcommunicationapplications.
Sec-ond,wedevelopautility-awaredistributedspanningtreeconstructionalgorithmforecientlypropagatinggroupcommunicationmessages.
Itdynamicallycreatesandmaintainsthegroupcommunicationchannelsbyoptimizingtheutilityvalueofthegroupcommunicationspanningtrees.
Inaddition,wealsooutlineautility-basedoverlaymanagementproto-colforconstructingandmaintaininglow-diameteroverlaynetworks.
OurexperimentsshowthattheGroupCastsystemcanimprovethescalabil-ityofwide-areagroupcommunicationservicesbyonetotwoordersofmagnitude.
Keywords:Peer-to-peersystems,Overlaynetworks,Utilityfunctions.
1IntroductionMulti-partygroupcommunicationapplicationssuchasmulti-playeronlinegames,onlinecommunitybasedadvertising,real-timeconferencing[3],andinstantmes-saging[2]haveexperiencedasurgeofpopularityinthepastfewyears.
Theapplicationsarecharacterizedbyexchangesoftextualormultimediacontentsamongmultipleparticipants.
DecentralizedPeer-to-Peer(P2P)networkshaveevolvedasapromisingparadigmforprovidingopenanddistributedinformationsharingservicesbyharnessingwidelydistributed,looselycoupled,andinher-entlyunreliablecomputernodes(peers)attheedgeoftheInternet.
ThesuccessofSkype[5]hasdemonstratedboththeopportunityandthefeasibilityofuti-lizingP2Pnetworksaseconomicalinfrastructuresforprovidingwide-areagroupR.
CerqueiraandR.
H.
Campbell(Eds.
):Middleware2007,LNCS4834,pp.
410–428,2007.
cIFIPInternationalFederationforInformationProcessing2007AUtility-AwareMiddlewareArchitecture411communicationservices.
However,theoverlaynetworksinSkypeareusedonlyforservicelookupandcontrolsignaling.
Underthemulti-partyconferenceset-tings,eachnodeisrequiredtosendthepayloadsdirectlytootherparticipantsofthecommunicationgroupthroughitsIPunicastlinks[9].
Thisplacesseverelimitationsonthescalabilityofmulti-partyconferencecallsinSkype.
Thenaturalquestionsthatcomeupinclude:CanP2Poverlaysbeutilizedforimplementingscalablegroupcommunicationservicesoverwide-areanetworksIfsowhattechniquesandsystemleveloptimizationarecriticalforenhancingtheeciencyandscalabilityofdecentralizedwideareagroupcommunicationsAlthoughseveralresearchershaveexploredarelatedprobleminthecontextofdesigningapplication-levelmulticastingorend-systemmulticasting(ESM)schemes[20,22]overP2Poverlays,surprisinglymostoftheseworksaredesignedtoworkinconjunctionwithstructuredP2Pnetworks,andtheyrelyonthedistributedhashtable(DHT)abstractionsoftheP2Pnetworkforinter-peercommunicationandrouting[11,21].
However,itiswidelyrecognizedthatinenvironmentsthatexhibithighchurnratesmaintainingDHT-basedstructuresimposessevereoverheads,whichcanaecttheperformanceoftheapplicationsrunningontopofthesenetworkstoaconsiderableextent[13].
Incontrast,unstructuredP2PnetworkslikeGnutella[25]aresimpletoimplement,havelowmaintenancecosts,andprovidebetterresiliencetonetworkchurncausedbypeerentries,exits,andfailures.
Tothebestofourknowledge,veryfewgroupcommunicationapplicationshavebeenimplementedontopofunstructuredP2Pnetworks.
Wehypothesizethatcommonconcernsaboutthenon-deterministicnatureofcommunicationandservicelookupinunstructuredoverlaynetworksandtheirinecientutilizationoftheunderlyingIPnetworkresourcesarethemainreasonsforthelackofworkinthisarea.
DesigningscalablegroupcommunicationservicesontopofunstructuredP2Pnetworksposesthreemainchallenges.
Therstchallengeistotranslatewide-areagroupcommunicationapplicationrequirementssuchascommunicationeciencyandsystemscalabilityintothemetricsthatcanbeusedwhiledesigningthecommunicationstructuresandmanagingthetopologiesoftheoverlaynetworks.
Second,theunstructuredP2Pnetworkssuerfromheavymessagingoverheadsandhighservicelookuplatencies.
Thechallengeistodeviselow-costservicelookupmechanismsthatareeectiveforbothcontrolsignalingandcommunica-tiongroupmanagement.
TheresilienceofunstructuredP2Poverlaystonetworkchurnisrootedinthefactthattheydonotuseanyglobalcontrolmechanismsforregulatingresourcedistributionandthenetworktopology.
Thethirdchallengeistodesignoverlaynetworkmanagementprotocolssuchthatthefeaturescrit-icaltotheperformanceofgroupcommunicationapplicationsareincorporatedwithouttradingawaytheinherentrandomnessoftheseoverlays.
Towardsaddressingthesechallenges,thispaperpresentsGroupCast-autil-ityawaredecentralizedmiddlewarearchitectureforscalableandecientP2Pgroupcommunicationapplications.
IndesigningtheGroupCastsystem,thispa-permakestwouniquecontributions:412J.
Zhangetal.
–First,weproposeautilityfunctiontoquantifytheusefulnessofunicastlinkstotheeciencyofindividualcommunicationgroupsaswellastothescalabilityoftheentiregroupcommunicationinfrastructure.
Thisutilityfunctionprovidesacarefulcombinationofthetwomostimportantfactorsthatinuencetheperformanceofthesystem,namelynetworkproximitiesofthepeersandresourceavailabilitiesattheendhosts.
–Second,wedesignautility-awaremechanismforconstructingspanningtreesrequiredfordisseminatinggroupcommunicationpayloads.
Theobjectiveofthisschemeistooptimizetheutility-valuesoftheresultantspanningtrees.
Further,consideringthedecentralizednatureofunstructuredP2Pnetworks,thisschemehasbeendesignedtooperateinacompletelydistributedfashion,anditdoesnotrelyuponanyglobaltopologicalinformation.
Inadditiontotheabovecontributions,wealsooutlineautility-basedP2Pover-laynetworkmanagementprotocolthatusestheproposedgenericutilityfunctionforconstructinglow-diameterunstructuredP2PoverlaysthatarecomparabletostructuredP2Pnetworkintheirscalabilityandeciency.
Thispaperpresentsseveralexperimentstoevaluatetheutility-awaremiddlewarearchitectureanditscomponenttechniques.
Theresultsshowthattheproposedtechniquespro-videsignicantscalabilityandeciencybenetsforthegroupcommunicationapplications.
2TheBasicP2P-BasedGroupCommunicationFrameworkSpanningtreeformsthefundamentalstructureinmostgroupcommunicationschemes.
Thespanningtreeisanacyclicoverlayconnectingalltheparticipantsofacommunicationgroup.
Thegroupcommunicationmessages(payload)aredisseminatedthroughthespanningtreesothattheyreachalltheparticipants.
Thevariousgroupcommunicationschemesdierinthemannerinwhichtheyconstructandmaintainthespanningtrees.
Oursystememploysmulti-levelspan-ningtreesforachievingthescalabilityneededforsupportinggroupcommunica-tioninlargewide-areanetworks.
Theproposedframeworkincludescompletelydistributedstrategiesforbuildingandmaintainingspanningtreesofcommuni-cationgroups.
Weintroduceafewnotationsthatwouldbeusedintherestofthepa-per.
TheP2PnetworkisconceptualizedasadirectedgraphG,whereV={p0,p1,p2,pN1}representsthepeersinthenetworkandE={e0,e1,.
.
.
eM1}denotesthelogicallinksinthenetwork.
ThespanningtreeTPtisdenedasaconnected,acyclicsub-graphofG,wheretheparticipantsetVPtVandlinkssetEPtE.
Eachpeerisawareofonlyitsimmediateneighbors.
Further,thenetworkdoesnothaveanydistributedhashtable(DHT)abstractions.
AUtility-AwareMiddlewareArchitecture4132.
1ConstructingaDistributedSpanningTreeOneofthechallengesindevelopinggroupcommunicationsystemsistodesignacompletelydistributedschemeforbuildingspanningtree.
Severalapplicationlevelmulticast(end-systemmulticast)systemshaveaddressedaverysimilarproblem(theproblemofconstructingmulticasttrees).
However,asweexplainbelow,noneofthemaredirectlyapplicableforbuildingspanningtreesonun-structuredP2Pnetworks.
Theexistingmulticasttreeconstructionschemescanbeclassiedintothreebroadcategories.
Intherstapproach,theparticipantsofamulticastgroupexplicitlychoosetheirparentsinthemulticasttreefromalistofcandidatenodes[7,18,17].
Duetothecomplexityofthoseprotocols,thereareveryfewac-tualimplementationsofthesealgorithms.
Thesecondapproach,whichisadoptedbysystemslikeNarada[14]andScattercast[12],constructsthespanningtreeintwo-steps.
Therststepconstructsawell-connectedmeshfromthenodesinthenetwork.
Thesecondstepusesthismeshstructureandconstructsshort-estpathspanningtreesthroughwell-knowndistributedalgorithms.
However,thesesystemsdonotscalewell,especiallywhentheunderlyingnetworkex-periencesconsiderablechurn.
Thethirdapproach,representedbysystemslikeCAN-multicast[21]andSCRIBE[11],assumesthatthenodesoftheunderlyingnetworkareorganizedasastructuredP2Pnetwork[20,22].
ThemulticasttreeisconstructedusingthedeterministicroutingfunctionalitiesoftheseP2Pnet-works.
AswediscussedinSection1,DHT-basedstructuredP2Pnetworksarenotsuitableforscenarioswhereinthepeerpopulationsaretransient.
Inshort,noneofthecurrentmulticasttreeconstructionapproachesareapplicablefortheproblemathand.
Wehavedevelopedcompletelydecentralizedschemeforbuildinggroupcom-municationspanningtreesonagenericunstructuredP2Pnetwork.
Weleveragetechniquessuchasselectivemessageforwardingforreducingthecommunicationcostsofspanningtreeconstructionandmaintenance.
2.
2BuildingtheCommunicationGroupTheobjectiveofourcommunicationgroupconstructionalgorithmistoselecttheedgesorthelinksintheP2Poverlaytoformthespanningtreethatconnectsallthegroupparticipants.
Thecommunicationgroupconstructionalgorithmsusuallyincludestheimplementationoftwofunctionalities.
First,participantsshouldbeawareoftheexistenceofthecommunicationgrouptowhichtheywilljoin.
Second,anewlyjoinedparticipantshouldbeabletosetupaconnectiontotheexistingnodesinthechosencommunicationgroupforsendingandreceivingthecommunicationpayloads.
Thersttaskisusuallyaccomplishedbyappointinganodeastherendezvouspointorthemulticastsource,andpublishingthenode'sinformationatawell-knownlocationsuchasabulletinboardsystem.
Twostrategieshavebeenpro-posedforimplementingthesecondfunctionality.
TherstschemeissimilartotheDVMRPIP-multicastprotocol[16].
InsteadofusingtheIPlevelnetworkde-vicessuchasrouterstoimplementthepollingandpruningprocessesofmulticast414J.
Zhangetal.
groupmanagement,thisstrategyusesoverlaynetworksandpeers.
Thisstrat-egyisadoptedbytheScattercastsystem[12],inwhichthesourcenodesolelyadvertisesrouteinformationandeachnodeintheoverlayforwardsthisadver-tisementandbuildsthelocalroutingtableentries.
Toremoveloopsandtoavoidtheproblemofcounting-to-innity,thefullpathinformationisembeddedintotheforwardedadvertisementmessages.
WerefertothisschemeasNon-SelectiveServiceAnnouncement(NSSA)scheme.
Inthesecondstrategy,themulticastsourceismappedtoawell-knownnodeservingastherendezvouspoint,andthesubscribersusethisidentierasthekeywordintheirsubscribingrequests[11].
Thestructuredsystemtopologyandthedeterministicroutingalgorithmsdecidetheseriesofpeersthroughwhicheachsubscriptionrequestwouldbeforwardedsothatitreachestherendezvouspointoranexistingparticipantinthemulti-castgroup.
Thereverseofthispathwouldbeusedforforwardingthemulticastpayloadsdownfromthemulticastsource.
Twocharacteristicsofoursystempreventusfromdirectlyreusingtheseschemes.
First,thenatureofgroupcommunicationapplicationsisdierentfromend-systemmulticastsystems.
Inend-systemmulticastsystems,communicationpayloadsareforwardedinonedirectioninmostofthecases(fromthemulti-castsourcetoalltheothernodes),whileingroupcommunicationsystems,eachparticipantmayinitiatemessagesinadditiontoreceivingthem.
Second,theun-structurednatureofourP2Poverlaypreventsusfromdirectlyusingthereverseofthesearchingpathasthepayloadcommunicationpath.
Wehaveproposedaschemethatcombinestheadvantagesofthesetwoschemes,whileavoidingtheirdisadvantages.
WecallourschemetheSelectiveServiceAn-nouncement(SSA)scheme.
Inthisscheme,thespanningtreeforacommunica-tiongroupisestablishedinthreesteps.
Step1-ChoosingRendezvousPoint:First,apeerintheP2Poverlayischosenastherendezvouspoint.
UnliketherendezvouspointinSCRIBE[11],towhichallthemulticastpayloadsarerstforwarded,ourrendezvouspointservesasthesourceofthegroupadvertisementmessagesandwillbehaveasanormalnodeinthecommunicationspanningtree.
Thereareseveralwaystochoosesucharendezvouspoint.
Itcanbesetupasadedicatedserverdonatedbyaserviceproviderwhoinjectscontentsintothecommunicationgroup.
Forgroupsthataresetupforapplicationslikeonlineconferences,therstparticipantcaninitiatearandomwalksearchtolocateanodethathasenoughaccessnetworkbandwidthandcomputationalpowertoactasarendezvouspoint.
Step2-Advertising:Inthesecondphase,therendezvouspointadvertisesthegroupinformationtothepotentialparticipantsofthecommunicationgroup.
TheoodingschemeusedforsimilarpurposesinDVMRP[16]andScattercast[12]incursredundantmessagesintheoverlaynetwork.
OurSSAschemealleviatesthecommunicationoverheadsinthefollowingmanner.
Inourscheme,eachpeerthatreceivestheadvertisementmessagewillforwardittoafewofitsneighbors,ratherthanoodingthemessagetoallneighboringnodes.
Ourbasicgroupcommunicationframeworkusesaverysimpleapproachforselectingneighbors,AUtility-AwareMiddlewareArchitecture415namelytherandomstrategy.
Inthisalgorithm,therendezvouspointandtheothernodesreceivingtheadvertisementmessagerandomlyselectapre-speciedfractionoftheirneighborsandsendthemthemessage.
ThemessagepropagationterminateswhentheTTLbecomeszero.
However,thissimpleadvertisementschemesuersfromtwomajordrawbacks.
Wediscusstheselimitationslaterinthepaperandpresentschemesformitigatingthem.
Step3-Subscribe:Subscriptionactivitiesareinitiatedwhenapeerpidecidestojoinacommunicationgroup.
Twoscenariosneedtobeconsidered.
First,ifthepotentialservicesubscriber(peerpi)hasalreadyreceivedandroutedtheserviceadvertisement,thenitisalreadyonthemessageforwardingpathofthiscommunicationgroup.
AllitneedstodoistostartthesubscriptionprocessbysendingthejoiningmessageinthereversedirectionofincomingSSAmessage.
However,notethattheadvertisementmessagemightnotreachallpotentialsubscribers.
IncasethesubscriberhasneverreceivedtheSSAmessage,asearchmethodprovidedbytheP2PoverlayistriggeredtolookuptheneighborhoodofthepeerfordiscoveringnodesthatmighthavereceivedtheSSAadvertisementmessage.
ThesearchmethodisimplementedasaripplesearchinstandardGnutellaP2Pnetwork,withinitialTTL(TimetoLive)valuesettoaverylowvalue.
Becauseouradvertisementmechanismwouldhavealreadypushedtheserviceinformationtodierenttopologicalregionsofthenetwork,apotentialsubscribercanndanearbyneighborthathasreceivedtheSSAmessagewithhighprobability.
Ourexperimentreportsthattheaveragesuccessrateofsubscriptionsearchiscloseto100%,evenwhentheTTLofthesearchmessagesaresetto2.
Oncesuchanodeisdiscovered,thesubscriptionmessageissenttoit,whichthenforwardsinthereversedirectionoftheoriginalSSAmessage.
2.
3LimitationsoftheBasicFrameworkThebasicgroupcommunicationframeworkhastwoimportantlimitationswhichcanaectitseciencyandscalability.
Therstlimitationisthemanifestationoftheoverlay-underlaymismatchproblem.
Since,intheadvertisementphaseofthescheme,anodereceivingtheadvertisementforwardsthemessagetoarandomlychosensubsetofneighbors,theresultingtreemightnotalwaysbeecientintermsoftherelativelocationsofitsnodesonthephysicalnetwork.
Forexample,anodepilocatedinNewYorkmighthaveanodepjlocatedinAustraliaasoneofitschildren,whichin-turnmighthaveachildpllocatedinBoston.
Thishasanegativeeectonthelatenciesexperiencedbythegroupcommunicationmessages.
Similarly,thecapability(resourceavailability)ofanodepiinthespanningtreemightbecompletelydierentfromthecapabilitiesofitsparentsorchildren.
Thismismatchamongthecapacitiesoftheneighborsinthespanningtreecanresultinhighpacketlosses.
Thisagainaectstheperformanceofgroupcommunication.
Weproposetwomiddlewareleveltechniquesforovercomingtheabovedraw-backs,namelyautility-awarespanningtreeconstructionschemeanda416J.
Zhangetal.
utility-awaretopologymanagementschemefortheunderlyingP2Pnetwork.
Whilethersttechniqueaddressesthequestionastohowshouldtheconnec-tionsintheoverlaybeutilizedforgroupcommunicationapplications,thesecondtechniqueaddressesthequestionofhowthepeersshouldchooseandmaintaintheirneighborsintheoverlayHowever,itisinterestingtoobservethatthesetwoquestionsarethemanifestationsofthesamedesignissue,namelygivenalistofnodes,sayL,whatarethemetric(s)thatdictatewhichofthesenodesapeerpishouldconnecttoBoththesetechniquesrelyuponauniqueutility-function,whichassignsdierentpreferences(rankings)toeachpeerinthelistL.
Inthenextsection,weexplaintheformulationoftheutilityfunction.
Wethendescribehowthisutilityfunctionisutilizedintheproposedtechniques.
3TheUtility-AwareMiddlewareforP2PGroupCommunicationThissectionfocusesonthetwomaincomponentsoftheGroupCastdesign.
First,wedescribetheutilityfunctionweusetoquantitativelymodelthecriticalperformancemetricsofwideareagroupcommunicationapplications.
Second,wediscusshowtoemployourutilityfunctiontooptimizethegroupcommu-nicationchannelconstructionandmaintenancebydevelopingautility-awaredistributedspanningtreeconstructionalgorithmthatcanecientlypropagategroupcommunicationmessages.
Finally,wealsooutlineourutility-basedoverlaymanagementprotocolwhichprovidesthecapabilityforconstructingandmain-taininglow-diameteroverlaynetworkstofurtherenhancetheperformanceofthegroupcommunicationservices.
3.
1TheUtilityFunctionThegroupcommunicationinoverlaynetworksessentiallyoccursbyforward-ingthecommunicationpayloadthroughunicastIPnetworklinks.
Hence,thepropertiesoftheunicastlinksinterconnectingpeersintheP2Poverlaylargelydecidetheperformanceandtheeciencyofthegroupcommunicationsystem.
Ourutilityfunctionconsidersthetwoimportantfactorsthatdeterminetheper-formanceofunicastlinks,namelythenetworkproximityoftheend-nodesandthesimilaritybetweenamongthecapacitiesofthepeers.
Thenetworkproximitybetweentheend-hostsdeterminesthelatencyoftheunicastlink.
Similarly,itisknownthatmismatchbetweenthepacket-forwardingworkloadsandtheca-pacitiesofpeersintroducesbottlenecksinthecommunicationoverlayandmayresultinhighpacketlosses.
Wenotethatthesetwofactorsmightsometimesbecounteracting.
Forinstance,apeerinthelistLwhichisclosesttopi,mighthavecompletelydierentresourceavailabilitiesthanpi.
Ourutilityfunctionprovidesacarefulcombinationofthesetwofactorsbasedontheutilitypreferenceofpeerpi,aswellasthedesiredperformancepropertiesoftheentireoverlay.
Concretely,foreachnodepjinthelistL(recallthatLrepresentsalistonpotentialnodesfromwhichthepeerpichoosesasubset),weassumethattwoAUtility-AwareMiddlewareArchitecture417typesofinformationareavailable:thenodecapacityCj,andtherelativedistancebetweenpeerpiandpeerpj,denotedbyD(pi,pj).
Thecapacityofapeerismeasuredintermsofitsaccessiblenetworkbandwidth,sincetheperformanceofapeerinadistributedenvironmentlikeP2Pnetworksislargelydecidedbyitsaccessnetworkbandwidthavailableforforwardingcommunicationpayloads.
Theaccessnetworkbandwidthcanbespeciedbytheenduserintermsofthenumberof64kbpsconnectionsthenodeiswillingtosupport.
Alternatively,itcanalsobeestimatedbynetworkprobingtechniques.
Weusethenetworkcoordinatestoestimatetherelativedistancebetweenanytwopeers.
Vivaldi[15]andGNP[1]aresomeofthetechniquesproposedformeasuringthenetworkcoordinatesofnodesinwideareanetworks.
Wedenetwoutility-basedpreferencemetricsbasedonthetwoimportantperformancefactorsnamelynetworkproximityandnodecapacity.
GivenalistofpeersL,wedenetheDistancePreferenceofpeerpitopeerpj∈LastheprobabilitythatpeerpichoosespeerpjoutofL,basedonthenetworkcoordinatedistancebetweenthem.
Thecloserthepeerpjistopeerpi,themorelikelyitischosen.
TheDistancePreferenceiscomputedasindicatedinEquation1.
PDpi(L,pj)=1dpi(L,pj)αpk∈L1pdi(L,pk)α(1)whereα∈(∞,1)isatunableparameterthatindicatesthedegreetowhichpi'spreferscloserpeers.
Highervaluesofαindicatesthatpistronglypreferscloserpeersandvice-versa.
Wechooseα<1sothatthereisnonzeropreferenceoneachpj∈L.
Thefunctiondpi(L,pj)givesthenormalizeddistancebetweenpiandpj.
dpi(L,pj)isdenedasfollows:di(L,j)=D(pi,pj)MAXpk∈LD(Pi,pk)(2)Notethat0Similarly,wedenetheCapacityPreferenceutilitymetricofpeerpiwithrespecttopeerpjastheprobabilitythatpeerpichoosespeerpjoutofLbasedonthenodecapacityofpeerpj.
Thegoalistoutilizehighercapacitynodestorelaygroupcommunicationmessagestolargernumberofpeers.
Equation3givestheformulationfortheCapacityPreferenceutilitymetric.
PCpi(L,pj)=Cpjβpk∈LCpkβ(3)HereCpjisthenodecapacityofthepeerpj.
Theparameterβ∈(∞,1)playsasimilarroleasthatofαinequation1.
WhiletheCapacityPreferenceandDistancePreferenceencapsulatetheutilityofnodesinLfromtwodierentperspectives,weneedameanstocom-binethesetwoutilityparametersintoasingleutilityfunction.
Inthisregard,itisinterestingtoobservethatthepeerpiwhichwantstoselectasubsetofpeersfromLshouldalsoconsideritsownresourceavailability(capacity)while418J.
Zhangetal.
makingitschoices.
Ifthepeerpipossessesmoreresources,wewouldliketouseitasaforwardinghubintheoverlaynetworkandapplications.
Suchapeershouldbeconnectedtothosepeersthathavesimilarresourcesandplaysimilarrolesintheoverlaynetwork,whichwouldmakeitamemberofthe"core"oftheoverlaynetwork.
Onthecontrary,iftheresourcesofpeerpiarelimited,itshouldnotbeplacedintothecoreasthatwouldeasilyexhaustitsresources.
Abetterchoiceforsuchalimitedresourcepeerwouldbetoconnecttopeersthatarephysicallyclosertoitandusethemtoaccesstheoverlaynetwork.
Hence,theweightagegiventothetwoutilitymetrics(CapacityPreferenceandDistancePreference)dependsuponthecapacityofpeerpi.
Accordingly,wede-nethecombinedutilityfunctionSelectionPreferenceofpeerpitopeerpj∈LasaweightedcombinationofCapacityPreferenceandDistancePreference.
Ppi(L,pj)=γ·PCpi(L,pj)+(1γ)·PDpi(L,pj)(4)Hereγistheweightagefactorsuchthat0≤γ≤1.
Thecongurableparametersα,β,andγgivesustheexibilitytone-tunetheutilityfunctionfordierentapplicationscenarios.
Forinstance,inanoverlaynetworksupportingapplicationsthataresensitivetonetworkproximity,αcanbesettohighervaluesandγtobesettolowervalues.
Thiswouldensurethatnetworkproximityisthedominatingfactorwhenpeersmaketheirchoices.
Onthecontrary,foranoverlaynetworkthatemphasizesmoreonloadbalancing,ahighervalueforβandahighervalueforγwouldbemorepreferable.
Thevaluesofparameterα,β,andγcanbemathematicallyderivedbyusingtechniquessimilartotheonesusedbyBuandTowlsey[10].
However,thesetech-niquesrequireinformationabouttheexactnumberofpeersandtheexactdis-tributionsofthevarioussystem-levelparameters.
IndecentralizedenvironmentslikeP2Pnetworkswhereglobalstatisticalmechanismsareexpensivetoimple-ment,itisunlikelythatsuchinformationwouldbeavailable.
TheGroupCastsystemadoptsanapproximationapproachtoaddressthisproblem.
Specically,wedeneResourceLevelriasthefractionofpeersthathavelesscapacitythanpeerpiintheoverlaynetwork.
ricanbeestimatedbysamplingafewpeersthatareknowntopi.
Weusetheresourcelevelsofvariouspeerstosetthethreeparametersasα=1ri,β=ri,andγ=rln(ri)i.
Substitutingthevaluesforα,β,γ,PC,andPDintoequation4,weobtain:Pi(L,j)=rln(ri)i·Cjrik∈LCjri+(1rln(ri)i)·1di(L,j)(1ri)k∈L1di(L,k)(1ri)(5)Wenotethatthiscongurationreectsourdesignrationale.
Theβandγparametersassumehighervaluesforpeerswithhighercapacities.
Hence,thesepeerswouldgivepreferencemorepowerfulpeerswhilechoosingasubsetfromL.
Incontrast,forpeerswithlessresourcesαassumeshighervalueswhereasβandγbecomesmall.
Thus,forthesepeersthesubsetselectionispredominantlybaseduponthenetworkproximities.
Inotherwords,thelesspowerfulpeersconnecttonodesthatareclosertothem.
Further,theyavoidpeerswithlargecapacities,therebyshieldingthemselvesfromgettingoverloaded.
AUtility-AwareMiddlewareArchitecture419050100150200250300350400105104103102101100Preferencedistributionv.
s.
distancedistribution,ri=0.
05Distance(ms)Preferencepreferencesfortop20%powerfulcandidatespreferencesfor80%lesspowerfulcandidatesFig.
1.
Selectionpreferenceoflowcapacitypeervs.
distancetootherpeers050100150200250300350400103102101100Preferencedistributionv.
s.
distancedistribution,ri=0.
95Distance(ms)Preferencepreferencesfortop20%powerfulcandidatespreferencesfor80%lesspowerfulcandidatesFig.
2.
Selectionpreferenceofhighcapac-itypeervs.
distancetootherpeersToevaluatetheeectivenessoftheselectionpreferencemetric,wesimulatetheselectingprocessofthreepeers,usingasetofsyntheticdata.
Weassigneachofthemwithdierentresourcelevelvalue.
Theonewithri=0.
05representsapeerwithlowcapacity.
Similarly,theonewithri=0.
5simulatesapeerwithmediumcapacity,andtheonewithri=0.
95representsapowerfulpeer.
Foreachofthem,wegeneratedalistof1*103peers,eachofwhichisassignedacapacityvaluethatfollowsazipfdistributionwithparameter2.
0.
WeassumethatthedistancebetweeneachcandidatepeerandthepeerevaluatingthemfollowsauniformdistributionUnif(0ms,400ms).
100101102103105104103102101100Preferencedistributionv.
s.
capacitydistribution,ri=0.
05CapacityPreferencepreferencesfortop20%powerfulcandidatespreferencesfor80%lesspowerfulcandidatesFig.
3.
Selectionpreferenceoflowcapacitypeervs.
capacityofotherpeers100101102103103102101100Preferencedistributionv.
s.
capacitydistribution,ri=0.
95CapacityPreferencepreferencesfortop20%powerfulcandidatespreferencesfor80%lesspowerfulcandidatesFig.
4.
Selectionpreferenceofhighcapac-itypeervs.
capacityofotherpeersFigure1Figure4plotthesimulationresults,whichexactlyreectsourdesignrationale.
Foraweakerpeerthathasri=0.
05,theselectionpreferencetootherpeersisdominantlydecidedbyitsdistancetothem,asplottedinFigure1andFigure3.
Onthecontrary,theselectionpreferenceofapowerfulpeerislargelydecidedbythenodecapacityofpeersinthecandidatesetasshowninFigure2andFigure4.
Forpeersthathasmediumamountofresources,itequallypreferspowerfulandnearbypeers[27].
420J.
Zhangetal.
3.
2Utility-AwareSpanningTreeConstructionInthissection,wedescribeourtechniqueforinfusingutility-awarenessintospanningtreeconstructionforgroupcommunication.
Thecentralideaofthistechniqueistoensurethattheedgesinthespanningtreeshaveveryhighutilityvalues,therebyoptimizingtheoverallgroupcommunicationperformance.
IfthetopologyoftheP2Pnetworkandtheutilityvaluesofalltheunicastlinksinthenetworkweretobeavailableinacentralizedlocation,wecouldhaveusedoneoftheseveraloptimizationtechniquesforconstructingutility-awarespanningtree.
Unfortunately,duetotheverynatureofP2Psystemscollectingtopologicalandutilityinformationatacentralizedlocationwouldbeextremelyexpensive,ifnotimpossible.
Therefore,thechallengeistodesignacompletelydistributedspanningtreeconstructiontechniquethatisnotonlyeectiveinensuringhighutilityvaluesfortheedgesinthetreebutisalsoecientandlightweight.
Weobservethatthebasicspanningtreeconstructiontechniquethatweex-plainedinSection2isindeedcompletelydistributed,anditdoesnotrelyuponanycentralizedtopologicalinformation.
Therefore,thequestioniswhetheritispossibletoachievehighutilityvalueswhileretainingtheoverallspanningtreeconstructionframeworkOurutility-awarespanningtreeconstructionschemeisbaseduponthefol-lowingcrucialobservation.
Ofthethreephasesofthebasicspanningtreecon-structionscheme,theadvertisementphasehasthemostsignicantinuenceonthestructureoftheresultantspanningtree.
Inotherwords,theadvertisementdecisionsmadebyvariouspeersmoreorlessdeterminethestructureofthespanningtree.
Thisisbecause,ifanodeplreceivinganadvertisementdecidestoparticipateinthegroupbeingadvertised,theverylinksthroughwhichtheadvertisementwaspropagatedtoplfromtherendezvousnodewouldbecomeapartofthecorrespondingspanningtree.
However,inthebasicgroupcommuni-cationframework,eachpeerreceivingtheadvertisementsendsittoarandomlyselectedsubsetofitsneighbors.
Fromtheaboveobservation,weconcludethatthemostnaturalwayforin-jectingutility-awarenessintothespanningtreeconstructionprocessistoincor-porateitattheadvertisementphase.
Accordingly,intheutility-basedspanningtreeconstructiontechnique,peerreceivingtheadvertisementforwardsittoasubsetofitsneighborsbasedontheirutilityvalues.
Specically,theprobabilityofaneighborbeingincludedinthesubsetselectedforforwardingtheadvertise-mentisdirectlyproportionaltoitsutilityvalue.
Thus,aneighborthathasahigherutilityvaluehasahigherchanceofbeingincludedinthesubsetofnodestowhichtheadvertisementisforwarded.
Specically,arendezvouspointrpevaluatestheutilityvalueofitsneighborsusingEquation5.
Basedontheseutilityvalues,itchoosesthepeerseitherhavesimilarcapacitiesasrporarephysicallyclosetorp,dependingonthecapacityofrp.
Thesepeersaretheonesthataremoreusefultorp.
Theyreceivetheadvertisementandarelikelytobeincludedinthespanningtree.
UponreceivinganSSAmessage,anarbitrarypeerpkperformstwotasks.
First,peerpkusesalocalhashingtabletocheckandrecordifithasalreadyAUtility-AwareMiddlewareArchitecture421receivedthesamemessagefromanyotherneighbors.
Themessagewillbedrop-pedifitisaduplicatedone.
Otherwise,itusesasimilarmechanismasthatoftherendezvouspointtoselectneighborsforfurtherpropagatingtheSSAmessages.
Ineect,whenapeerreceivesanadvertisement,itismorelikelythatthead-vertisementtraversedapathinwhicheachlinkhadahighutilityvalue.
Ifthispeerdecidestoparticipateinthegroupbeingadvertised,thepathoftheadver-tisementbecomesapartofthecorrespondingmulticasttree.
Thus,ourschemeseamlesslyincorporatesutilityawarenessintothespanningtreeconstructionprocess.
3.
3Utility-AwareTopologyManagementOurutility-awarespanningtreeconstructionalgorithmbuildsthespanningtreefromexistingconnectionsoftheoverlay.
Thus,theperformanceoftheresultantspanningtreesdependuponthetopologyoftheunderlyingP2Pnetwork.
WiththeaimoffurtherenhancingtheperformanceoftheGroupCastmiddleware,wehavedesignedautility-awareoverlayconstructionmechanism.
Inthissection,webrieyoutlinethemechanism.
Theobjectiveoftheutility-awareoverlayconstructiontechniqueistocreateP2Pnetworksinwhichtheneighborsofanarbitrarynodepihavereasonablyhighutilityvalueswithrespecttopi.
UnlikemanyP2Pnetworksthatarebasedontheconceptofsupernodes,ourtechniqueinsertsbothhigh-capacityandlow-capacitypeersintothesameoverlay.
Ourtechniqueessentiallyworksasfollows:Whenapeerpijoinstheoverlay,itgatherstheinformationofanumberofexist-ingpeersasitsneighborcandidates.
ThenewpeercalculatestheprobabilityofconnectingtoeachcandidatebyusingtheutilityfunctiondenedinEquation5.
Theseprobabilitiesandthetotalnumberofconnectionsthatthepiintendstomaintaindeterminewhetherpiwouldestablishaconnectionwithanarbitraryneighborcandidatepeer.
Specically,ajoiningpeerpiobtainsalistofexistingpeerseitherusingitslo-calcachewhichcontainsitsP2Pnetworkneighborscarriedfromthelastsessionofactivitiesorbycontactingahostcacheserver.
Uponreceivingaqueryrequestfrompeerpi,thehostcachesortsitscachedentriesintheascendingorderbytheirnetworkcoordinatedistancestopeerpi.
Fromthetopofthissortedlist,thehostcacheselectsalistofpeersBDi.
TheyarereturnedtopeerpitogetherwithalistofrandomlyselectedpeersBRi.
StartingfromthesubsetBiofboot-strappingpeersreceiveduponitsentry,PeerpisendsaprobingmessageMprobtoeachpeerpk∈Bi.
EachpeerpkthatreceivesthisprobingmessagesendsbackarespondingmessageMprobresp,whichisaugmentedwithalistofpk'sP2PnetworkneighborsNbr(pk).
PeerpiassemblesalltheneighborinformationcontainedintheprobingrepliesandcompilesthemintoacandidatelistLCi.
Foreachuniquepeerpj∈LCi,peerpicomputestwotypesofinformation:(1)Theoccurrencefrequencyofpeerpj,whichrecordsthenumberofappearancesofpeerpjinLCi,denotedasfi(pj).
AsLCiservesasasamplingofthepeersinthenetwork,fi(pj)isthesampleofthedegreeofpeerpj.
(2)Theestimationofthe422J.
Zhangetal.
physicalnetworkdistancebetweenpeerpiandpeerpj,denotedbydi(LCi,pj),asdenedinEquation2.
Basedonthesetwosetsofinformation,thepeerpicomputestheutilityvalueofeachpeerinLCiusingtheequation6.
Dependinguponitsownitsownnodecapacity,peerpiselectsacertainnumberofpeersfromthelistLCiandaddsthemintoitsneighborlist(Nbr(pi)).
Thechancesapeerpk∈LCibeingaddedtotheneighborlistofpiisdirectlyproportionaltopksutilityvalues.
Concretely,theprobabilityofpkbeingselectedasaneighborofpiisgivenbythefollowingequation.
Pi(LCi,pj)=rln(ri)i·fi(pj)ripk∈LCifi(pk)ri+(1rln(ri)i)·1di(LCi,pj)(1ri)pk∈LCi1di(LCi,pk)(1ri)(6)Thepeerpinowsetsupitsoutgoingedges(forwardingconnections)toeachnodeinitsneighborlist.
Ittheninitiatestheprocesstosetuptheincomingedges(backlinkstopi)bysendingabackwardconnectionrequesttoeachpeerpk∈Nbr(pi).
TherequestisaugmentedwiththecapacityinformationCiofpeerpianditsnetworkcoordinates.
Apeerreceivingabackwardconnectionrequestutilizesasimilarutilityprincipletodecidewhethertoaccepttherequest.
Thisensuresthatpowerfulpeersareeasilyacceptedbyotherpowerfulpeersastheirneighborswhereasweakeronesaregoodcandidatesonlywhentheyarecloseenough.
TheGroupCastsystemalsoincludesanepoch-basedschemeformaintainingthestructureoftheP2Poverlayevenwhenthenetworkexperiencessignicantchurn[27].
4ExperimentalEvaluationWehaveimplementedadiscreteeventsimulationsystemtoevaluateGroup-Cast.
ThissystemisanextendedJavaversionofp-sim[19]system.
WeusedtheTransit-StubgraphmodelfromtheGT-ITMtopologygenerator[26]tosimulatetheunderlyingIPnetworks.
PeersarerandomlyattachedtothestubdomainroutersandorganizedintooverlaynetworksusingthealgorithmpresentedinSection3.
3.
Thecapacityofpeersisbasedonthedistributiongatheredin[23],Table1.
CapacitydistributionofpeersCapacitylevelPercentageofpeers1x20%10x45%100x30%1000x4.
9%10000x0.
1%AUtility-AwareMiddlewareArchitecture423asshowninTable1.
WeuseGNP[1]toassignnetworkcoordinatetoeachpeer.
Eachexperimentisrepeatedover10IPnetworktopologies.
EachIPnetworksupports10overlays,andeachoverlaynetworkprovidesservicefor10commu-nicationgroups.
4.
1EvaluatingtheGroupCastServiceLookupMechanismWebeginbyevaluatingtheutility-awarespanningtreeconstructionandgroupcommunicationmechanismsoftheGroupCastsystem.
Mostunstructureduseei-therscopedooding(broadcast)orrandomwalkastheircommunicationparadigm.
However,ooding-basedmechanismsareexpensiveintermsofmes-sageloadstheyimpose,whereasrandomwalksresultinlongerdelays.
TheGroupCastsystemincludesaselectiveserviceannouncement(SSA)mechanismforecientandlow-costservicelookups.
TherstexperimentevaluatestheeectivenessandeciencyoftheSSAschemebysimulatingtheserviceannouncementprocessesinanumberofover-laynetworksthataregeneratedusingeitherourutility-awareoverlayconstruc-tionmechanismorthecentralizedPLODalgorithm.
Inordertogainabetterunderstanding,wecomparetheSSAmechanismwiththenon-selectiveserviceannouncement(NSSA)scheme(seeSection2.
1).
Foreachoverlaynetwork,werandomlyselect10peersasrendezvouspoints,andinitiatetheselectiveser-viceannouncement(SSA)processandthenon-selectiveserviceannouncement(NSSA)processfromeachofthem.
ForbothSSAandNSSA,werstrecordthefractionofpeersintheoverlaythathavereceivedtheserviceannouncement.
Aswementionedearlier,whenthesepeerswanttosubscribeforthegroupcom-municationservice,theycancircumventtheservicesearchingprocess.
Forpeersthathavenotreceivedtheserviceannouncementmessage,subscriptionprocessinvolvessearchingitsneighborhoodforpeersthathavereceivedtheservicean-nouncementmessage.
Inoursimulator,thesepeersusearippleoodingsearchschemeforthispurposewithTTLbeingsetto2.
WemeasurethesuccessratesofservicelookupsforbothSSAandNSSAschemes.
Wealsorecordthetotalnumberofmessagesgeneratedbythesetwoschemes.
TheresultsinFigure5showthattheSSAschemereducesthetotalnumberofmessagesgeneratedinbothGroupCastandrandompower-lawoverlaynetworks.
TheSSAschemelimitsthenumberofsubscriptionmessagessenttoneighborsthatarenotlikelytobeapartofthecommunicationgroup.
Thisreducesthemessageloadby63%to70%whencomparedwithNSSAschemefortheGroup-Castoverlay.
Thereductionis35%to44%fortherandompower-lawoverlay.
WenoticethatthenumberofsubscriptionmessagesofSSAschemeinrandompower-lawoverlaysisalmostnegligible.
ThisisbecauseGroupCastoverlayshavelowerclustercoecientvaluesthantherandompower-lawtopologiesgeneratedusingPLOD.
Thus,SSAmessagesreachfewerpeers.
TheresultsalsoshowthattheSSAschemeperformsbetterfornetworkswithhigherconnectivityvalue.
Figure6leadstotwointerestingobservations.
First,fewerpeersinGroupCastreceivetheSSAmessagescomparedtorandompower-lawtopology.
Second,allsubscriberscanlocatetheirserviceswith100%successrateevenwhentheinitial424J.
Zhangetal.
Fig.
5.
MessageloadsofservicelookupschemesFig.
6.
SuccessrateofservicelookupinGroupCastoverlayandrandompower-lawoverlaywithSSATTLofthesubscriptionmessagesissettotwo.
Thisisessentiallybecause,intheGroupCastoverlay,theneighborsofindividualpeersarelikelytohavehigherutilityvalues.
Hence,ateachstepoftheSSAprocess,morecandidatepeersmeetutility-awareselectioncriterion.
ThisisalsothereasonfortherelativelylargenumberofserviceannouncementmessagesintheGroupCastoverlaywhencomparedwithrandompower-lawnetwork.
However,thepeerschosenbyourutility-awareselectionmechanismsaremoresuitabletothegroupcommunica-tionspanningtreesandtheyensurehighsubscriptionsuccessratesevenatverysmallTTLvalues.
Fig.
7.
LatencyofservicelookupinGroupCastoverlaynetworksandrandompower-lawoverlaynetworksusingselectiveserviceannouncementFig.
8.
Delaypenaltyofgroupcommuni-cationapplications4.
2ImprovementofApplicationPerformanceThesecondsetofexperimentsstudiestheeectsoftheproposedtechniquesonagroupcommunicationapplication.
Thegroupcommunicationapplicationweconsideristhatofend-systemmulticasting(ESM).
ESMhasbeenproposedasAUtility-AwareMiddlewareArchitecture425analternativeforIPmulticast,whichhassueredfromlackofwideacceptanceanddeployment.
Inthisapproach,peersformoverlaynetworksandimplementmulticastfunctionality.
Multicastdataarereplicatedonpeersandpropagatedthroughunicastedgesoftheoverlaynetworks.
ESMisinherentlylessecientthanIPmulticast,asESMmaysendpacketswithsamepayloadmultipletimesoverthesamephysicalnetworklink.
Moreover,theESMworkloaddistributionamongheterogeneouspeersaectstheoverallsystemperformance.
WesimulatedP2Poverlaynetworksconsistingof1*103to3.
2*104peers.
P2Poverlaynetworksareconstructedusingourutility-awaremechanismaswellasthecentralizedPLODalgorithm.
WeusedtheroutingweightsgeneratedbytheGT-ITMpackagetosimulatetheIPunicastrouting.
IPmulticastsystemsaresimulatedbymergingtheunicastroutesintoshortestpathtrees.
WeusebothSSAandNSSAforserviceannouncementandsubscriptionmanagement.
WequantifytheperformanceoftheschemesusingRelativeDelayPenaltyandLinkStressparameters,whicharethetwopopularmetricsforevaluatingtheeciencyofESMsystems.
RelativedelaypenaltyisdenedastheratiooftheaverageESMdelaytotheaverageIPmulticastdelay.
LinkstressisdenedastheratioofthenumberofIPmessagesgeneratedbyanESMtreetothenumberofIPmessagesgeneratedbyanIPmulticasttreeinterconnectingthesamesetofsubscribers.
Fig.
9.
LinkstressofgroupcommunicationapplicationsFigure8showstherelativedelaypenaltieswhenmulticastingisimplementedthroughvariouscombinationsofthetwooverlaymanagementschemes(utility-aware(GroupCast)andrandompower-law)andthetwospanningtreeconstruc-tionschemes(SSAandNSSA).
Figure9showstherespectivelinkstressvalues.
TheresultsshowthatESMimplementedonGroupCastoverlaysyieldsignicantimprovementsintermsofbothmetricswhencomparedwiththeircounterpartsimplementedonrandompower-lawnetworks.
ThedelaypenaltyofESMimple-mentedonGroupCastoverlayisaround1.
5,whichisclosetothetheoreticallowerboundof1.
ThelinkstressesofESMimplementedonGroupCastisabouttwo-thirdsthelinkstressesofESMimplementedontopofrandompower-lawnetwork.
Theimprovementsareduetothenetworkproximityawarenessofthe426J.
Zhangetal.
GroupCastoverlaynetworks.
Multicastpayloadsareforwardedthroughshorterpaths,thusgeneratingfewerIPpacketsintheunderlyingIPnetwork.
ItisinterestingtonotethattheimpactoftheSSAschemeonapplicationperformanceisalmostnegligibleinGroupCastoverlaynetworks,whereastheimpactinrandompower-lawnetworksissignicant.
WeattributethisbehaviortothefactthatGroupCastoverlaynetworksarealreadyawareofthenetworkproximityofpeers.
Thus,thepeerschosenbytheSSAschemearemostlikelybetheonesthatareactuallyusedintheinformationdisseminationspanningtree.
5RelatedWorkTheworkongroupcommunicationinP2Pnetworkshasmainlyfocusedonstruc-turedP2Pnetworks.
Researchershaveproposedseveralapplication-levelmulti-castingschemesforDHT-basedstructuredoverlaynetworks[20,22,24].
However,structuredP2Pnetworkshavehighmaintenancecosts,especiallyinhighlydy-namicenvironments.
Incontrast,theGroupCastsystemdoesnotrequireanyDHTabstractionsfromtheoverlay.
Instead,Ourtechniquesarecompletelydis-tributed,andtheyrelyonlyonlocalinformation.
Manydistributedgroupcommunicationsystemsrelyontheservicesofoverlaynetworksforoperation[7,11,14].
Usually,end-hostsinthecommunicationgroupsusetheunicastlinksofoverlaynetworkstoexchangeapplicationandmanage-mentmessages.
Researchershaveexploredvarioustechniquestooptimizethesystemperformanceattheapplicationlevelwiththeobjectiveofdesigninge-cientandscalablequeryprocessingmechanisms[13].
ApopularapproachtoimprovingP2Pnetworksistoutilizetherankingsofdierentpeersintermsoftheirnodecapacityandorganizethemintodierenthi-erarchicallayers[4,25].
However,suchpredeterminedhierarchicalstructurescanintroducesystemvulnerabilities.
Further,foreciencypurposes,thesupernodesmaintainthestateinformationofthenormalpeerstheyserve.
However,suchstateinformationisgenerallytiedtotheapplication,anditishardtodesignasupernodeoverlaylayerthatcanserveasagenericmiddlewaretosupportdierentservices.
Adaptationmechanismshavebeenstudiedinthecontextofapplication-layermulticasting[8,28].
Ourresearchiscomplimentarytotheseworks.
Thesesys-temscanutilizetheGroupCastprotocolsforconstructingwell-regulatedspan-ningtrees.
Ourprotocolcanhelpreducethenumberofadaptationsbyensuringtheeciencyofinitialspanningtrees.
TechniquessuchasRON[6]havebeendesignedforbuildinggenericoverlaysthatareindependentoftheapplicationsbuiltontopofthem.
However,unliketheseworks,theGroupCastsystemcon-structsoverlaynetworksthatincorporatenetworkproximityinformation,anditalsobuildsscale-freepower-lawtopologiesassigningconnectionsaccordingtothepeers'capacities.
Inshort,theworkpresentedinthispaperhasseveraluniquefeaturesandoursystemaddressesaproblemthatiscrucialforthesuccessofseveralmulti-partycollaborativeapplications.
AUtility-AwareMiddlewareArchitecture4276ConclusionThispaperpresentsthedesignandevaluationofGroupCastautility-awaredecentralizedmiddlewarearchitectureforscalableandecientwide-areagroupcommunications.
TheGroupCastdesignincorporatesthreenovelfeatures:(a)Autilityfunctionthatmeasurestheusefulnessofunicastlinkstothescalabilityandeciencyofthegroupcommunicationapplication;(b)Adistributedutility-awareschemeforconstructingecientspanningtreesfordisseminatinggroupcommunicationpayloads;and(c)Autility-basedoverlaymanagementprotocolforgeneratingandmaintaininglow-diameteroverlaynetworks.
OurexperimentsshowthatGroupCastprovidesanorderofmagnitudeimprovementinthescal-abilityofwide-areagroupcommunicationapplications.
AcknowledgementThisworkispartiallysupportedbygrantsfromNSFCSR,NSFSGER,NSFCyberTrust,andgrantsfromIBMSURandIBMFacultyAward,DoESciDAC,andAFOSR.
References1.
E.
Ng.
GNPsoftware(July2006),http://www.
cs.
rice.
edu/eugeneng/research/gnp/software.
html2.
GoogleTalk(July2006),www.
google.
com/talk/3.
LiveMeeting(July2006),http://www.
microsoft.
com/office/livemeeting4.
SharmannetworksLTD.
KaZaAmediadesktop(July2006),http://www.
kazaa.
com5.
Skype.
(July2006),http://www.
skype.
com6.
Andersen,D.
,Balakrishnan,H.
,Kaashoek,F.
,Morris,R.
:Resillientoverlaynet-works.
In:SOSP.
Proceedingsofthe18thACMSymposiumonOperatingSystemsPrinciples,ACMPress,NewYork(2001)7.
Banerjee,S.
,Bhattacharjee,B.
,Kommareddy,C.
:Scalableapplicationlayermul-ticast.
In:Proceedingsofthe2002ACMSIGCOMMConference,ACMPress,NewYork(2002)8.
Banerjee,S.
,Kommareddy,C.
,Kar,K.
,Bhattacharjee,B.
,Khuller,S.
:Construc-tionofanecientoverlaymulticastinfrastructureforreal-timeapplications.
In:ProceedingsofINFOCOM(2003)9.
Baset,S.
A.
,Schulzrinne,H.
:Ananalysisoftheskypepeer-to-peerinternettele-phonyprotocol.
TechnicalReportcucs-039-04,Dept.
ofComputerSci.
,ColumbiaUniv.
(2004)10.
Bu,T.
,Towsley,D.
:Ondistinguishingbetweeninternetpowerlawtopologygen-erators.
In:IEEEINFOCOM,NewYork,NY,IEEE,LosAlamitos(2002)11.
Castro,M.
,Druschel,P.
,Kermarrec,A.
,Rowstron,A.
:SCRIBE:Alarge-scaleanddecentralizedapplication-levelmulticastinfrastructure.
IEEEJournalonSelectedAreasincommunications(JSAC)(2002)12.
Chawathe,Y.
:Scattercast:AnArchitectureforInternetBroadcastDistributionasanInfrastructureService.
PhDthesis,UniversityofCalifornia,Berkeley(2000)428J.
Zhangetal.
13.
Chawathe,Y.
,Ratnasamy,S.
,Breslau,L.
,Lanham,N.
,Shenker,S.
:MakingGnutella-likeP2Psystemsscalable.
In:ACMSIGCOMM,Karlsruhe,Germany,ACMPress,NewYork(2003)14.
Chu,Y.
-H.
,Rao,S.
G.
,Zhang,H.
:Acaseforendsystemmulticast.
In:ACMSIGMETRICS2000,pp.
1–12.
ACMPress,NewYork(2000)15.
Dabek,F.
,Cox,R.
,Kaashoek,F.
,Morris,R.
:Vivaldi:Adecentralizednetworkcoordinatesystem.
In:ACMSIGCOMM,Portland,Oregon,USA,ACMPress,NewYork(2004)16.
Deering,S.
,Cheriton,D.
:Multicastroutingindatagraminternetworksandex-tendedlans.
ACMTransactionsonComputerSystems8(2)(May1990)17.
Francis,P.
:Yoid:Extendingthemulticastinternetarchitecture(1999)18.
Jannotti,J.
,Giord,D.
K.
,Johnson,K.
L.
,Kaashoek,M.
F.
,O'TooleJr.
,J.
W.
:Overcast:Reliablemulticastingwithanoverlaynetwork.
In:OSDI.
ProceedingsofSymposiumonOperatingSystemDesignandImplementation,pp.
197–212(2000)19.
Merugu,S.
,Srinivasan,S.
,Zegura,E.
:p-sim:Asimulatorforpeer-to-peernetworks.
In:MASCOTS2003.
Proc.
ofthe11thIEEEIntl.
Symp.
onModeling,Analysis,andSimulationofComputerandTelecommunicationsSystems,IEEEComputerSocietyPress,LosAlamitos(2004)20.
Ratnasamy,S.
,Francis,P.
,Handley,M.
,Karp,R.
,Shenker,S.
:Ascalablecontentaddressablenetwork.
In:ProceedingsofSIGCOMM,ACMPress,NewYork(2001)21.
Ratnasamy,S.
,Handley,M.
,Karp,R.
,Shenker,S.
:Application-levelmulticastusingcontent-addressablenetworks.
In:Crowcroft,J.
,Hofmann,M.
(eds.
)NGC2001.
LNCS,vol.
2233,Springer,Heidelberg(2001)22.
Rowstron,A.
,Druschel,P.
:Pastry:Scalable,decentralizedobjectlocation,androutingforlarge-scalepeer-to-peersystems.
In:Guerraoui,R.
(ed.
)Middleware2001.
LNCS,vol.
2218,pp.
329–350.
Springer,Heidelberg(2001)23.
Saroiu,S.
,Gummadi,P.
,Gribble,S.
:AmeasurementstudyofPeer-to-Peerlesharingsystems.
In:ProceedingsofMMCN,SanJose,CA(August2002)24.
Stoica,I.
,Morris,R.
,Karger,D.
,Kaashoek,F.
,Balakrishnan,H.
:Chord:Ascal-ablePeer-To-Peerlookupserviceforinternetapplications.
In:ProceedingsSIG-COMM,pp.
149–160.
ACM,NewYork(2001)25.
WWW.
TheGnutellaRFC(July2006),http://rfc-gnutella.
sourceforge.
net26.
Zegura,E.
W.
,Calvert,K.
L.
,Bhattacharjee,S.
:Howtomodelaninternetwork.
In:IEEEInfocom,vol.
2,pp.
594–602.
IEEE,LosAlamitos(1996)27.
Zhang,J.
,Liu,L.
,Ramaswamy,L.
,Pu,C.
:ScalableandEcientPeer-to-PeerGroupCommunication:AUtility-basedApproach.
Technicalreport,CollegeofComputing,GeorgiaTech.
(2006)28.
Zhou,Y.
,etal.
:Adaptivereorganizationofconherency-preservingdisseminationtreeforstreamingdata.
In:ICDE(2006)