selectedp2pover官网

Meghdoot:Content-BasedPublish/SubscribeoverP2PNetworksAbhishekGupta,OzgurD.
Sahin,DivyakantAgrawal,andAmrElAbbadiDepartmentofComputerScienceUniversityofCaliforniaatSantaBarbara{abhishek,odsahin,agrawal,amr}@cs.
ucsb.
eduAbstract.
Publish/Subscribesystemshavebecomeaprevalentmodelfordeliveringdatafromproducers(publishers)toconsumers(subscribers)distributedacrosswide-areanetworkswhiledecouplingthepublishersandthesubscribersfromeachother.
InthispaperwepresentMeghdoot,whichadaptscontent-basedpublish/subscribesystemstoDistributedHashTablebasedP2Pnetworksinordertoprovidescalablecontentdeliverymechanismswhilemaintainingthedecouplingbetweenthepub-lishersandthesubscribers.
Meghdootisdesignedtoadapttohighlyskeweddatasets,whichistypicalofrealapplications.
TheexperimentalresultsdemonstratethatMeghdootbalancestheloadamongthepeersandthedesignscaleswellwithincreasingnumberofpeers,subscriptionsandevents.
1IntroductionPublish/Subscribesystemsareusedtodeliverdataeventsfrompublishers(data/eventproducers)tosubscribers(data/eventconsumers)inadecoupledfashion.
Publisherscanbecompletelyunawareofthesubscribersandsimplyintroducedataeventsintothesystem.
Adataeventspeciesvaluesforasetofattributesassociatedwiththeevent.
Subscriberscanregistertheirinterestswiththesystemintheformofsubscriptionswhichactasltersthatareusedbythesystemtodeliverrelevanteventstothesubscribers.
Content-basedsubscriptionsspecifythesubscriptionbasedonattributepropertiesofthedataevents.
Thepub-lish/subscribesystem,orequivalentlythepublish/subscribemiddleware,man-agesthesubscriptionsanddeliverstheeventstothematchingsubscriptions.
Publish/subscribesystemsariseinmanyapplicationsincludingonlinestockquotes,Internetgames,andsensornetworks.
Inthestockquoteapplication,forexample,theeventsaregeneratedbyvariousstockexchangeswheretradingoc-curs.
Theeventscontaininformationabouttheopen,close,low,andhighvaluesofcompanies'stocksatvarioustimes.
Thesubscribersareclientsinterestedintrading,andtheyareusuallyinterestedinthevaluesofthestockstheytrade.
AnotherinterestingexampleisIBM'swebserviceforinformationoneventsinThisresearchwassupportedinpartsbyNSFgrantsEIA00-80134,IIS-0220152,andIIS-0223022.
H.
-A.
Jacobsen(Ed.
):Middleware2004,LNCS3231,pp.
254–273,2004.
cIFIPInternationalFederationforInformationProcessing2004Meghdoot:Content-BasedPublish/SubscribeoverP2PNetworks255the2000OlympicsatSydney.
Userscouldqueryeventsinsportsoftheirinterestoreventsrelatingtotheircountriesbycontactingthewebservice.
AccordingtoIBM[13],therewere11.
3billionhitstothewebserver.
Thisnumberisexpectedtogrowhigherinupcomingevents.
Usersareinterestedinanoticationservicethatcanallowthemtotrackeventsofinterest.
Theinformationforsucheventscanbedistributedtousersbyutilizingadistributedpublish/subscribesystem.
Currentsolutionsareeithercentralizedordistributed.
CentralizedsolutionsbasedonaDBMSusetriggers[11,6],whichhaveaninherentscalabilityproblemasthenumberofeventsinthesystemincrease.
Specializeddatastructureshavebeenproposedtoovercomethesescalabilityproblems[7].
However,toensureecientprocessing,restrictionsareplacedonthetypesofsubscriptionsthatthesystemcansupport.
Distributedsolutionsareusuallyrestrictedtospecicsubject-basedsubscriptions[5,31,19]andhencedonotsupportgeneralcontent-basedsubscriptions.
Alternatively,routingtrees[4,2]areusedtosupportmul-ticasttopreventcommunicationbottlenecks.
Peer-to-peersystemsareparticularlyattractiveforsupportingpublish/sub-scribesystemssincetheyareexible,modular,andscalable.
Insuchsystems,peersareusedbothtostoresubscriptionsandtorouteeventstootherpeerswithrelevantsubscriptions.
Peer-to-peersystemsareveryscalablesinceaddi-tionalpeerscancontributetheirmachines,thusincreasingthecomputationalandstorageresourcesinthesystem.
Traditionally,peer-to-peersystemswerede-signedtoanswerexactmatchqueries.
InthispaperwepresentMeghdoot1,aP2Pbasedpublish/subscribesystem.
Meghdootusesastructureddistributedhashtable[1]todeterminewheresubscriptionsarestoredandhowtoroutetheeventstothesubscriptions.
Meghdootisascalablearchitectureforpublish/subscribesystemsthatappliesaexiblemodelofcontent-basedpublish/subscribesystemstostructuredP2Psystems.
Aparticularchallengeinpeer-to-peersystemsinvolvesensuringauniformdistributionofloadamongthedierentpeersinthesystem.
Traditionalpeer-to-peersystemsareoblivioustothecontentofthedataandhenceuseauniformhashfunctiontodistributethedataamongthedierentpeers.
However,inacontent-basedpublish/subscribesystem,wedistributethesubscriptionsandeventsbasedontheircontent.
Mostrealworlddatasetstendtobeskewedandhencewillcauseanon-uniformdistributionofloadonthepeers.
OneimportantinnovationofMeghdootisthealternativemethodsitusestobalancetheloadamongpeers.
Ourexperimentalresultsclearlydemonstratethatevenwhenusinghighlyskewedrealworlddatasets,thesystemensuresthatnopeerisundulyloaded.
Therestofthepaperisstructuredasfollows.
Section2presentsasurveyofrelatedwork.
Section3presentsthebasicdesignofourproposedapproach.
ThisisfollowedbySection4whichpresentsstrategiesforemployingpeersinthesysteminaloadbalancedmanner,andpresentssomeoptimizations.
Section5presentstheexperimentalsetupandresults.
Section6concludesthepaper.
1ThenameMeghdootoriginatesfromanancientepicwherecloudswereusedasmessengers.
256AbhishekGuptaetal.
2RelatedWorkPublish-subscribesystemsaredesignedfordisseminatinginformation(events)toasubsetoftheclients(subscribers)whoareactuallyinterestedinthisinfor-mation.
Thedesignsforpublish/subscribesystemscanbeclassiedintotwocat-egories:Subject-basedandContent-based.
Subject-basedpublish/subscribesys-temsassigneacheventtooneofasetofpre-denedsubjects(alsoreferredtoastopics,channels,orgroups).
Theeventsthemselvesspecifythetopicsthatarerelevanttotheevent.
Aclientsubscribestoasetofsubjectsitisinterestedinandisnotiedofalltheeventsthatareassociatedwiththesesubjects.
ExamplesofthesesystemsincluderesearchproposalsISIS[3],iBus[16]andcommercialproductsTibco[26],andVitria[28].
Content-basedpublish/subscribesystemsallowmorecomplexsubscriptionsbyenablingrestrictionsontheeventcontent.
Asubscribercanspecifymultiplepredicatesasasubscriptionandonlythoseeventswhosecontentsatisesallthepredicatesarenotiedtothesubscriber.
Subscriptionsinthesesystemsaremoreexpressive,butthesystemsarehardertoimplement.
Examplesofdistributedcontent-basedsystemsincludeElvin[22],Siena[4],andGryphon[2].
Elvinusesacentralserverwhichstoresallthesubscriptionsandevaluatesthesubscrip-tionsaectedbytheevents.
Fabretetal.
[7]proposednoveldatastructuresandapplication-speciccachingpoliciesandqueryprocessingincentralizedsystemstosupporthighratesofsubscriptionsandeventsinacontent-basedsystem.
Forscalabilitypurposes,subscriptionsinthissystemmustcontainatleastoneequalitypredicate.
Othercentralizedapproacheshavebeenproposedforscal-ablematchingofpredicatesinthecontextofdatabasetriggerprocessing[11]andcontinuousqueries[6].
SienaandGryphonaredistributedsystems,inwhichanetworkofbrokernodesiscreatedandtheeventsaredistributedwithinthenetwork.
P2Psystemshaveemergedasapopulartechniqueforexchanginginforma-tionamongasetofdistributedpeers.
Initialapproachesusedacentralizedindexand/oroodingforlocatingobjectsinthesystem(e.
g.
Gnutella[9],Napster[15],KaZaA[14]).
AdvancedP2Psystemsprovidemoreecientlookupsusingstruc-tureinthelogicaloverlaynetworkformedbythepeers.
Theyimplementahashtablefunctionalitydistributedoverthepeers,andarereferredtoasDistributedHashTables(DHT's).
CAN[18],Chord[23],Pastry[20],andTapestry[30]aredierentexamplesofDHT's.
MostP2Psystemsweredesignedforlocatingin-formationbasedonexactnames,e.
g.
namesofles.
However,recentlyseveralproposalshavebeenmadetoextendP2Pfunctionalitytomorecomplexqueries,e.
g.
,rangequeries[10,21],joins[12],SQL[27],XML[8],etc.
SeveralapplicationlevelmulticastsystemshavebeenproposedemployinganunderlyingDHT,andcanbeeasilyadaptedforsubject-basedpublish/subscribe.
Thesesystemsinheritthescalabilityandfaulttolerancepropertiesfromtheun-derlyingDHTstructure.
Scribe[5]isbuiltontopofPastry[20].
ScribeassignsauniquegroupIdtoeachtopicandthenodewhosenodeIdisnumericallyclos-esttothegroupIdbecomestherendezvouspointforthistopic.
Foreachtopic,amulticasttree,thatisrootedattherendezvouspoint,iscreatedbycom-Meghdoot:Content-BasedPublish/SubscribeoverP2PNetworks257biningthepathsfromeachsubscribertotherendezvouspoint.
Themessages(events)associatedwiththegroup(subject)aredisseminatedalongthecorre-spondingmulticasttreestartingfromtheroot.
APastry[20]basedP2Poverlayisusedin[17]toprovidesupportforatypebasedpublish/subscribesystemusingsimilarrendezvousmechanismasScribe[5].
TheP2Poverlayisalsousedby[17]forinstallingcontentbasedltersclosetothepublishers.
Bayeux[31]usesTapestry[30]astheunderlyingstructure.
SimilartoScribe,eachgroupisassociatedwitharootnodebasedonitsuniqueIDandamulticasttreerootedatthatnodeisusedfordatadissemination.
CAN-basedmulticast[19]isanap-plicationlevelmulticastsystembasedonCAN.
Unliketheapproachesabove,CANmulticastdoesnotbuildadistributiontreeforeachgroup.
Instead,themembersofagroupformaseparategroupspecicCANandthemulticastingisachievedbyoodingoverthisseparateCAN.
Ourworkimplementsacontent-basedpublish-subscribesystemoveraDHTbasedonCAN[18].
Thereareseveralsimilareorts[25,24].
Terpstraetal.
[25]partitiontheeventspaceamongthepeersinthesystem.
Chord[23]isusedtobroadcasteventsandsubscriptionstoallnodesinthesystem.
Thesebroadcastsareattenuatedbyltersinstalledatpeernodesduetothesubscriptionsstoredinthesystem.
Thisapproachmayrequireallpeersinthesystemtobecontactedtoinstallasubscription.
UnlikeTerpstraetal.
,inoursolutionsubscriptionsareinstalledbyroutingthroughO(dN1d)peers,whereNisthenumberofpeersinthesystemanddisthedimensionalityofthelogicalDHTspace.
Tametal.
[24]extendanexistingsubject-basedsystem(Scribe[5]).
Orderedcollectionsofasetofselectedattributesareusedforindexingsubscriptionsintoasubject-basedpublish/subscribesystem.
Thusasubscriptioncanbesubmittedintothesystemonlyifitspeciesallattributevaluesforatleastoneoftheindices.
Thedomainsofattributevaluesarepartitionedintointervals.
Ifasubscriptionspeciesarangeoversomeattribute,itisdecomposedintosubpartsaccordingtothedomainintervals.
Meghdootisacontent-basedpublish/subscribesystemthatimposesnorestrictionsonthesubscriptionsortheevents.
ItprovidesscalabilitybyleveragingtheP2Pdesign,thusallowingexibleadditionofpeersintothesystemtomatchthedemand.
Itusesinnovativeloaddistributiontechniquestomaintaintheloadbalanceinpresenceofhighlyskewedrealworlddata.
3MeghdootDesignInthissection,westartwithadescriptionoftheschemaandtherepresentationoftheeventsandthesubscriptionsinthesystem.
Next,wedescribethestoragemodelforsubscriptionsandtheeventdeliverymechanism.
3.
1Publish/SubscribeModelinMeghdootWeconsideracontent-basedpublish/subscribesystemwithmultipleattributes.
ThemodelanddenitionsarebasedonthemodelproposedbyFabretetal.
[7].
Theschemaforthesystemcanbedescribedas:S={A1,A2,An},whereeachAicorrespondstoanattribute.
Eachattributehasaname,typeanddomain,andcanbedescribedbythetuple{Name:Type,Min,Max}.
Theattributes258AbhishekGuptaetal.
areidentiedbytheiruniquenames.
Thedatatypesweconsiderareinteger,oatingpointandcharacterstrings.
ThevaluesMinandMaxdescribetherangeofdomainvaluestakenbythegivenattribute.
Allthepeersparticipatinginthepublish/subscribesystemusethesameschemaS.
Asubscriptionisaconjunctionofpredicatesoveroneormoreattributes.
Eachpredicatespeciesaconstantvalue(using=)orarange(usingforanattribute.
Ifasubscriptionneedstospecifymultiplepredicatesoverthesameattribute,wecanmodelsuchasubscriptionasacombinationofmultiplesubscriptions,eachofwhichspeciesonecontinuousrangeovertheattribute.
Forsimplicityofpresentation,henceforth,weassumeeachsubscriptionspeciesacontinuousrangeoveranattribute.
AnexamplesubscriptionisS=(A1≥v1)∧(v2≤A3≤v3).
Aneventisasetofequalitiesovertheattributesintheschema.
Therefore,aneventcanberepresentedase={A1=c1,A2=c2,An=cn}.
Ingeneral,eventsmayspecifyvaluesforasubsetoftheattributes.
AneventematchesasubscriptionSifeachpredicateofSissatisedbythevalueofthecorrespondingattributespeciedbytheevente.
Thepub-lish/subscribesystemisrequiredtostorethesubscriptionsspeciedbytheusersandgivenanevent,ndallsubscriptionsmatchingtheeventanddelivertheeventtothesubscribers.
Theschemabasedclusteringalgorithmsin[7]requirethattherebeatleastoneequalitypredicateineachsubscription.
Applicationsmaybeinterestedinrangepredicatesoverallattributesspeciedinasubscription.
Forexample,asubscriptioninthecaseofastockquotesapplicationcanaskforallquoteswherethevolumeoftradeisgreaterthan100,000onanyday,withoutspecifyinganyequalitypredicate.
Aneventattheendofadayneedstospecifyvaluesforstockname,itsopen,high,lowandclosevalues,andthevolumeoftradeinthatday.
Ourmodelisgeneralanddoesnotrestrictthesubscriptionsandallowsthemtospecifyrangesoverallattributesorasubset.
3.
2LogicalSpaceConstructionInthissection,wedescribetheconstructionofthelogicalspaceusedformain-tainingthedistributedhashtable.
GivenaschemaS={A1,A2,An}withnattributes,wecreateacartesianspacewith2ndimensions.
ThemappingfortheconstructionofthelogicalspaceasdescribedbelowhasbeenadaptedfromSahinetal.
[21].
AttributeAiwithdomainrange[Li,Hi]correspondstodimensions2i1and2iofthecartesianspace.
Intuitively,thepredicatesofasubscriptionspecifyrangesofinterestovertheattributes,andtherangesarerepresentedbyapointinthelogicalspace.
Thestartoftherangeovertheithattributeismappedtodimension2i1correspondingtoattributeAi,andtheendoftherangeismappedtothedimension2i.
Thereforethedomainofthe2i1and2iaxesinthecartesianspaceisboundedby[Li,Hi].
Thislogicalspaceispartitionedamongthepeerspresentinthesystem,andeachpeerisresponsibleforoneofthepartitions.
Thepartitionsarereferredtoaszones,andifapeerisresponsibleforapartition,wesaythepeerownsthezone.
Meghdoot:Content-BasedPublish/SubscribeoverP2PNetworks25971H1L1H1123456L(a)2d-cartesianspaceLLLHH1111LHH2222(b)4d-cartesianspaceFig.
1.
Logicalspaceconstruction.
ThepeersmaintainamultidimensionalDistributedHashTable(DHT)asdescribedinCAN[18].
Eachpeermaintainsinformationaboutthecoordinatesofitsownzone.
Inaddition,thepeersstorecoordinateinformationoftheirneighboringzonesaswellastheIPaddressesofthepeersowningthosezones.
Thisinformationisusedforthepurposesofroutingintheoverlaynetworkformedbythepeers.
Figure1showsexamplesofthecartesianspace.
Figure1(a)isthelogicalcartesianspaceforthecasewhentheschemahasonlyoneattribute.
Theboundsofbothaxesinthiscasecorrespondtothebounds[L1,H1]oftheattribute.
Therectangularregionsformapartitioningofthespace.
Eachrectangleisazoneandisownedbyapeerinthesystem.
Figure1(b)isanexamplelogicalcartesianspacewhentheschemahastwoattributes.
Thersttwodimensionsinthegureareboundedbythedomain[L1,H1]oftherstattribute,whereasthenexttwodimensionsareboundedbythedomain[L2,H2]ofthesecondattribute.
3.
3SubscriptionInstallationAusercanspecifyasubscriptionSbydeningtherangesorvaluesoveroneormoreattributesintheschema.
AsubscriptionScanbeexpressedinthefollowingformat:S=(l1≤A1≤h1)∧(l2≤A2≤h2)ln≤An≤hn).
IfthesubscriptionisinterestedinaspecicvaluevofanattributeAithenbothliandhiaresettov.
IfthesubscriptionSdoesnotspecifyanyrangeoveranattributeAithenliandhiareconsideredtobetheboundariesLiandHiofthedomainofAi.
ThesubscriptionSismappedtothepointl1,h1,l2,h2,ln,hninthe2n-dimensionalspacewhichisreferredtoasthesubscriptionpoint.
Notethatallsubscriptionsarestoredintheupperleftsideofthediagonalhyperplane.
Thisisduetothefactthatthecoordinatevalueofthe(2i1)thdimensionissmallerthanorequaltothe(2i)thdimensionforasubscriptionpointsincetheycorrespondtothestartandendvaluesoftherangeovertheithattribute.
Thezonesinthebottomrightofthediagonalhyperplaneareprimarilyusedforroutingpurposes.
Later,weutilizethesezonesforfaulttolerance.
260AbhishekGuptaetal.
Whenauserwishestosubscribeforsomeevents,theusersubmitsthesubscriptiontoapeerinthesystem.
TheoriginpeerPomapsthesubscrip-tiontoitscorrespondingsubscriptionpointinthe2n-dimensionalspace.
ThepeerwhosezonecontainsthispointisreferredtoasthetargetpeerPt.
PoneedstoroutethesubscriptiontothepeerPt.
Inordertoroutethesub-scription,Poselectsoneofitsneighbors,whichhastheclosestEuclideandis-tanceinthe2n-dimensionalspacetothesubscriptionpoint,andforwardsthesubscriptiontoit.
Thisprocessofforwardingisrepeateduntilthesubscrip-tionreachesthepeerPt.
ThisprocessofroutingthesubscriptiontothepeerL1H1L1H1PPotSFig.
2.
Routingasubscriptiontoitsdestinationforinstallation.
responsibleformanagingittakesO(dN1d)overlayhops[18]onaverage,whereNisthenumberofpeersinthesystemanddisthedimensionalityofthecartesianspace.
WhenPtreceivesthesubscription,itstoresthesub-scriptionalongwithanidentier(e.
g.
IPad-dress,username,e-mail,etc.
).
Figure2showsanexampleroutingpathforasubscriptioninthecaseofasingleattributeschema.
Thesub-scriptionisnallystoredinthetargetzoneandthesubscriptionpointismarkedS.
3.
4EventDeliveryWhenaneventisintroducedintothesystem,Meghdootisrequiredtondallthematchingsubscriptionsinstalledinthesystem,anddelivertheeventtothesubscribers.
Consideranevente={A1=c1,A2=c2,An=cn}.
Theeventeismappedtothepointc11,c12,c21,c22,cn1,cn2inthe2n-dimensionalspace,andisreferredtoasaneventpoint.
Iftheeventspeciesavaluevfortheithattributethenci1=ci2=v,otherwiseci1=Liandci2=Hi.
Notethattheeventpointslieonthediagonalhyperplaneofthespaceifalltheattributevaluesarespecied.
AsubscriptionS=(l1≤A1≤h1)∧(l2≤A2≤h2)ln≤An≤hn)isaectedbytheeventeifthefollowingpropertyholds:i∈{1,2,n}li≤ci1∧ci2≤hiTheshadedareainFigure3showstheregionofeventpointsina2dcartesianspacecorrespondingtoasingleattributeschemathatcanaectasubscriptionS,becausealltheeventpointsintheshadedregionwillsatisfytheaboveproperty.
TheshadedregioninFigure4showstheregionofsubscriptionpointsofallsubscriptionsaectedbyanevente.
Inthe2n-dimensionalspace,eventemappingtothepointc11,c12,c21,c22,cn1,cn2aectsthehyperrectangularregiondenedbythefollowingpoints:L1,c11,L2,c21,Ln,cn1andc12,H1,c22,H2,cn2,Hn.
WhenaneventisintroducedinthesystematapeerPo,itmapstheeventtothecorrespondingeventpointandroutestheeventtothepeerPtwhichcontainstheeventpoint.
Figure4showstheroutingpathofaneventefromPotoPtandtheregionofaectedsubscriptionsofeina2dspace.
TheeventisthenpropagatedstartingfromPttoallpeerswhichareintheregionaectedbyMeghdoot:Content-BasedPublish/SubscribeoverP2PNetworks2611H1L1H1LSFig.
3.
RegionofeventsaectingasubscriptionS=l1,h1.
L1H1L1H1PPot(L,c)111(c,H)121SeFig.
4.
Regionofsubscriptionsaectedbyanevente=c1,c1.
theevent.
Ptsendstheeventtoitsimmediateneighborsintheaectedregion,whichinturnpropagatetheeventtotheirneighborsintheaectedregion.
Thisprocessrepeatsuntilallpeersintheaectedregionhavebeennotiedoftheevent.
Thebasicalgorithmforeventdeliveryisgivenbelow.
ThealgorithmDeliverEventisinitiatedatevente'stargetpeer,Pt,whichownszonez.
Lines1-4checkforallaectedsubscriptionsthatarestoredatzonezanddelivertheeventtothosesubscriptions.
PredicatematchedSubscription(S,e)istrueifthesubscriptionpointcorrespondingtosubscriptionSiscontainedintheaectedregionofeventewithinzonez.
Lines5-8ndallneighbors,n,ofzonezthatareaectedbyeventeandareintheupperleftregionofthezonezitself.
ThepredicateeventRegion(n,e)istrueiftheregionofzoneninter-sectswiththeaectedregionofevente.
ThepredicateupperleftNeighbor(n,z)evaluatestotrueifneighbornliesintheupperleftregionofzonez.
Weusethebottomrightpointofzonezasthereferencepointfortheupperleftregionofztoensurethatnoneoftheaectedneighborsaremissed.
Forexample,inFigure1(a)zones1,2,and4areintheupperleftofzone5,butzones3,6,and7arenot.
Thispredicateisrequiredtopreventbackpropagationofevents.
InFigure5,all(dashedandsolid)arrowsrepresentthepropagationoftheevent.
PredicateupperleftNeighbor(n,z)preventsmessagesfrompropagatinginthereverseorderofthearrows.
Forexample,itpreventszonez4fromsendingamessagebacktozonesz1,z2,andz3.
Theeventpropagationalgorithmcanbefurtheroptimizedtopreventthesameeventfrombeingdeliveredtoazonebymultipleneighbors.
Figure5showsonlyzonesofinterestforillustrationandthedashedregionistheregionofsubscriptionpointsaectedbyevente.
Inthegure,zonesz2andz3donotneedtosendtheeventmessagetothezonez4becausezonez1sendsthemessagetoz4.
Thesemessagescanbepreventedinthefollowingway.
Whenpropagatinganeventtoaneighborzn,azonezchecksifanyofitsbottomrightneighborscouldhavealreadydeliveredthemessagetothatneighbor,inwhichcaseitwouldnotpropagatetheeventtothatneighbor.
Inourimplementationwealsousethisoptimization.
DashedarrowsinFigure5aretheduplicatemessagesthatcanbeavoidedbythisoptimization.
262AbhishekGuptaetal.
Algorithm:DeliverEvent(z,e)/*Executedatzonezforevente.
*/1.
forallsubscriptionsSstoredatz2.
if(matchedSubscription(S,e))3.
notifySubscriber(S,e)4.
endfor5.
forallneighborsnofz6.
if(eventRegion(n,e)∧7.
upperleftNeighbor(n,z))8.
DeliverEvent(n,e)9.
endfor5Ezzzzz1234Fig.
5.
Preventingrepetitivepropagation.
3.
5ExampleApplicationsInthissection,wepresentsomeexamplesofapplicationsthatcanbeimple-mentedusingMeghdoot.
Asanexampleconsideranapplicationwheredis-tributedsensorsareusedforgatheringenvironmentalparameterssuchastem-perature,humidity,illumination,etc.
Thesensorsinvariousgeographicallo-cationssendthemeasureddatatotheirlocalbasestations.
Userscanspecifycontinuousqueriesoverthedata,andthesequeriesarestoredatthebasesta-tions.
ThisapplicationcanbemodeledusingMeghdootwherethebasestationsformaP2Pnetwork.
Theuserqueriesarestoredassubscriptionsonthebasestationsandthesensorreadingscanbedirectedtoalltheaectedqueriesusingtheeventdeliverymechanism.
Meghdootcanalsobeutilizedincriticalsystemsforeventmonitoringappli-cations,forexamplepowerdistributionsystem.
ThepowerdistributionsystemconsistsofPowerStationswhichgeneratepowerwhichissenttoTransmis-sionSubstations.
ThesetransmissionsubstationsusehighvoltagetransmissionlinestoconveypowertovariousPowerSubstationswhicharelocatedindif-ferentgeographicalareas.
Thepowersubstationsstepdownthepowervoltageanddistributeittotheresidentiallocations.
Thepowersystemhassensorsthatmeasuretheamountofpowergenerated(inMW),transmittedandconsumed(inKW)atvariouspointsinthesystem.
Sensorsalsomeasurethevoltageinthetransmissionlines.
Monitoringagentscanspecifycontinuousqueriesthatdetectanomalies,likesuddendropinvoltageovertransmissionlinesoratripinpowergeneration.
Thisenablesearlydetectionofeventsthatcanleadtoseriousprob-lems,e.
g.
poweroutages.
Accordingtoarecentreport,theAugust14th2003blackoutintheNorthEastUSAandCanada,thecauseofthelargescalefailurewasduetolackoftimelyinformationaboutindividualfailures.
4PeerManagementinMeghdootInthissectionwediscussthemechanismsusedbypeerstojoinandleavethesystem.
Westartwithadescriptionofhowapeerjoinsthesystem.
Inthesim-plestcase,anewpeerPncanusethealgorithmdescribedinCAN[18]forjoiningMeghdoot:Content-BasedPublish/SubscribeoverP2PNetworks263thesystem.
PeerPncontactssomeexistingnodePeinthesystemandrequestsPetolocatearandomlygeneratedpointinthelogicalspace.
OncethepeerPtwhosezonecontainstherandompointislocated,PnsubmitsajoinrequesttoPt.
ThepeerPtthendividesitszonespaceintotwohalvesandassignsonehalftoPn.
Thetwopeersthenupdatetheirneighborinformationandalsoinformtheneighborsofthenewzonecoordinates.
TheCANsystem[18]wasoriginallydesignedforstoringlesandmultimediaobjectswithsyntacticidentiers.
Todistributethisinformationuniformlyinthemultidimensionalidentierspace,auniformhashfunctionwasused,thusensuringabalancedloadamongthepeers.
However,inadata-drivenenvironment,asinourapproach,thedistributionofthedataamongthepeersiscontent-based.
Hence,ifasetofeventsarepopular,thenthesubscriptiondistributionwillbeskewedinthatregionofthespace.
ThisisduetothefactthatMeghdootusesthecontentofthesubscriptions,ratherthanauniformhashfunctiontoplacedataonpeers.
Furthermore,un-likeastandardDHTbasedP2Psystem,inapublish/subscribesettingadataeventneedstobeforwardedtoallsubscriptionsinterestedinthisevent.
Hence,adirectapplicationoftheoriginalCANjoinproceduretoapublish/subscribesettingcanleadtosignicantloadimbalanceamongthepeers.
Inthissection,westudythecharacteristicsofloadanddevelopstrategiesforloadbalancing.
4.
1LoadCharacteristicsThepeersinthesystemneedtostoresubscriptionsassociatedwiththesub-scribers.
Inaddition,theyneedtopropagatetheeventstoallpeersintheaf-fectedregion.
Therefore,loadonapeerisduetobothsubscriptionsandevents,andtheyhavedierentcharacteristics,whichwedescribedbelow.
Ourproposedstrategiesforadmittingnewpeersinthesystemexploitthesevaryingcharac-teristics.
Fig.
6.
Splittingazonedividessub-scriptionload.
SubscriptionLoad.
Whenauserin-stallsasubscription,thesubscriptionismappedtoitscorrespondingpoint,andisstoredatthepeerwhichownsthezonecontainingthesubscriptionpoint.
Thusazoneownedbyapeercancontainvarioussubscriptionpoints.
Sincethepeerown-ingthezoneisresponsiblefordeliveringtheeventsitreceivestotheaectedsub-scriptionsitstores,theloadonthepeerduetosubscriptionsisproportionaltothenumberofstoredsubscriptionsinthezone.
Inparticular,theloadisreducedonapeer,ifthesubscriptionsinitszonearereduced.
Therefore,theloadduetosubscriptionsonapeercanbereducedbydividingthespatialextentofazonesothatthenumberofstoredsubscriptionsisevenlydividedwiththejoiningpeer.
Figure6showsanexamplein2dspace.
EventLoad.
Aneventgeneratesloadbecauseitneedstobepropagatedtoallzonesthatareintheaectedregionofthezone.
Ifazoneisloadedbecause264AbhishekGuptaetal.
itfallsinthepropagationpathoftoomanyevents,splittingthezoneintwowillnothelp,becausethezonewillstillremaininthepathofthoseevents.
Forexample,inFigure7(a),letssaythatthezonesownedbypeernodesN1,N2,andN3areinsomeeventpropagationpath,andnodeN2isoverloadedduetoeventpropagation.
IfanewpeerN4joinsthesystemandsplitsthezoneownedbyN2,nowbothN2andN4areinthepropagationpath,andhencethissplittingdoesnotreducetheloadonN2.
Inordertoreducetheloadduetoeventpropagation,weneedtocreatealternatepropagationpathsandselectoneoftheavailablepathstopropagateeachevent.
Thus,noteveryeventwillpropagatethroughthesamesetofnodes,andoverloadthem.
Thiscanbeachievedbyreplicatingazonethatisoverloadedduetoeventpropagation.
InthecontextofP2Psystemspartitioningistypicallyusedforloaddistribution.
Ourapproachisdierent,inthat,weareproposingreplicationforloaddistribution.
EENNN123NNNN1234(a)Splittingdoesnotdivideeventpropagationload.
1NNN123NN24N3N(b)Replicatingazonedividespropaga-tionload.
Fig.
7.
Eventpropagationload.
Figure7(b)showshowthiswillbeimplemented.
Thestraightlineontoprep-resentstheoriginalsituationalongapropagationpath.
Theblackdotsrepresentthepeersowningthezonesinthepath.
PeerN2inthecenterwasoverloadedduetoeventpropagation.
WhenanewpeerN4wishestojointhesystem,itcanreplicatetheexactzoneaspeerN2alongwithallitssubscriptions.
TheneighborsN1andN3needtostoretheIPaddressesofbothpeersN2andN4associatedwiththezonecoordinates.
Eectivelytheneighborshavetwopathstopropagatetheeventthroughthereplicatedzone.
Whenaneighborneedstopropagateaneventtothezone,itpicksonereplicapeeroutofthelistofreplicasforthezoneinaroundrobinfashion.
Thiswilldistributethepropagationloadontheoldpeerresponsibleforthezone.
4.
2PeerJoinWhenanewpeerPnwishestojointhesystem,itcontactsaknownpeerPeinthesystem.
Petriestolocateaheavilyloadedpeerinthesystem.
AfterPendsaheavilyloadedpeerPh,itforwardsPntoPh.
Inordertolocateaheavilyloadedpeer,eachpeerinthesystemmaintainsinformationaboutitscurrentMeghdoot:Content-BasedPublish/SubscribeoverP2PNetworks265loadaswellasitsneighbors'loadwhenitlastheardfromthem.
Inaddition,eachpeermaintainsanestimatedlistcalledloadedPeerListofkmostheavilyloadedpeersinthesystemthattheyeverheardabout.
Thepeerscandecidealocalvalueofkdependingonavailablememory.
Peersinthesystemperiodicallyupdatetheirneighborsabouttheirloadstatistics.
ThepeersalsopropagatetheirloadedPeerListtotheirneighbors.
ApeermergesitsloadedPeerListwiththereceivedlist.
Whenrequiredtolocateaheavilyloadedpeer,theloadinformationabouttheneighborsisutilizedbythepeerstoperformadistributedhillclimbingalgorithmtolocatealocalmaxima.
Theinitiatingpeersendsaprobeforaheavilyloadednodetooneofitsneigh-borsthathastheheaviestload.
Theprobeisforwardedtotheheaviestloadedneighborbyeachreceivingpeeruntilitreachesapeerwhichhasaloadhigherthananyofitsneighbors.
Thispeerisreferredtoasalocalmaxima.
Thenewpeerisnotiedoftheheavilyloadedpeer.
Whencontactedbythenewpeer,theheavilyloadedpeerchoosestoeithersplititszoneorreplicateitbasedonitsloadconditions.
Ifthepeerisloadedduetoeventpropagationithandsoveracopyofitszonetothenewpeer,thuscreatingareplicaofthezone.
Theneighborsareinformedoftheexistenceofthisnewreplica.
Ifthepeerisloadedbecauseitismanagingtoomanysubscriptions,itsplitsitszoneinsuchawaythatthetwopartitionshaveevendistributionofsubscriptionsbetweenthem,andhandsoveronepartitiontothenewpeer.
4.
3PeerDepartureorFailureWhenapeerwishestodepartfromthesystem,itrstchecksifthereareanyreplicasforitszone.
Ifoneormorereplicasexist,itsimplyinformsitsreplicasaswellastheneighborsofitsdecisiontoleave,andleavesthesystem.
Theneighborsandreplicasupdatetheirinformation.
Iftherearenoavailablereplicasforapeerleavingthesystem,itcontactsitsneighborsandndsaneighborwillingtotakeoveritszone.
Thenittransfersallitssubscriptionstothisneighborandleavesthesystem.
S'1L1H1L1SHFig.
8.
Replicatingsubscriptionsatmirrorimage.
Sincepeersperiodicallysendloadmes-sagestotheirneighbors,aneighborthatdiscoversafailedpeerneedstoeithertakeupthezoneofthefailedpeerorndsomeotherpeertohandoverthezone.
Inthecaseoffailure,theinformationaboutthesubscriptionsstoredatthefailedpeercanbelost,unlessreplicasexistduetoeventloadbalancing.
Toavoidthisproblem,weusethefollowingreplicationscheme.
Asde-scribedinSection3.
3,allsubscriptionsarestoredintheupperleftsideofthediago-nalhyperplane.
Weexploitthispropertyofourdesignforfaulttolerance.
Wheninstallingasubscriptionatsubscriptionpointl1,h1,l2,h2,ln,hn,wealsostoreacopyofthesubscriptionatpoint266AbhishekGuptaetal.
h1,l1,h2,l2,hn,ln.
Thispointisthereectionofthesubscriptionpointinthediagonalhyperplaneofthe2n-dimensionalcartesianspace.
ThisisillustratedbyFigure8fora2dspace.
Thelleddotsrepresentthesubscriptionpointsandthecirclesaretheirreectionsinthediagonal.
Therefore,ifapeerfailsandtherearenoreplicasforthezone,thenthelostsubscriptionscanberecoveredbyqueryingthereectionofthezone'scoordinatesinthediagonalhyperplane.
Ifthereectionofasubscriptionpointfallsintothesamezone,forexamplesubscriptionSinFigure8hasitsreectionS'inthesamezone,wemovealongtheincreasingvaluesofallodddimensionsuntilwendaneighborzonewithhigherodddimensionalcoordinates,andstorethecopyatthiszone.
ForexampleS'isactuallystoredinthezonetoitsrightintheFigure8.
Incaseanyoftheodddimensionalcoordinateswraparoundbeforereachinganeighboringzone,westartagainwiththereectionpointandmovetowardsthedecreasingevendimensionalcoordinatevaluesuntilwendaneighboringzone,andstorethecopythere.
In2dimensions,thisisequivalenttorstmovingrightandifnoneighborisfound,thenmovingdownfromthereectionpoint.
Ifazonesplits,ithastoaccordinglymovethereectionsubscriptionstotheleftortopneighbors.
5ExperimentalEvaluationInthissectionweevaluateMeghdootusingamodelofstockquotesapplication.
Westartthediscussionbyexplainingtheschemaforthestockquotesapplicationandthedatasetsusedforevaluation.
Next,wepresenttheevaluationresultsforvariousmetrics.
5.
1ExperimentalSetupWedevelopedasimulatorofMeghdootinC++.
Weusedthesimulatorincon-junctionwithamodelofthestockquotesapplicationwiththefollowingschema:S={Date:STRING,2/Jan/98,31/Dec/02},{Symbol:STRING,aaa,zzzzz},{Open:FLOAT,0,500},{High:FLOAT,0,500},{Low:FLOAT,0,500},{Close:FLOAT,0,500},{Volume:INTEGER,0,310000000}Intheaboveschema,Symbolisthestocksymbolforthecorrespondingcompany.
Thesymbolsarecharacterstringsoflengths3to5.
OpenandClosearetheopeningandclosingpricesofthestockonagivenday.
HighandLowarethehighestandlowestpricevaluesattainedbythestockinthegivenday.
Volumeisthetotalamountoftradeinthisstockonthatday.
Anexamplesubscriptioninthestockmarketpublish/subscribesystemwiththeaboveschemais:{Symbol=aapl∧High≥45},whichsubscribesforanyeventsforthestockofApplewhenthehighvalueofthestockisgreaterthanorequalto$45.
Anexampleeventis{Date=30/Jan/98,Symbol=aapl,Open=18.
31,High=18.
87,Low=18.
25,Close=18.
31,Volume=1450600}.
Meghdoot:Content-BasedPublish/SubscribeoverP2PNetworks267Theinputsetsforthesimulationsconsistofsubscriptionsandeventsdrawnrandomly.
Thesubscriptionsweregeneratedusingvetemplatesubscriptions.
Atemplatewaspickedatrandomwithprobabilitypandparameterizedtogenerateasubscription.
Weassigngeneralsubscriptionslowprobabilitiesofoccurrence.
Thereasonforthischoiceisthatinarealapplicationsubscribersareusuallyinterestedinspeciceventsrelevanttotheirnarrowinterests.
Ourstandardsub-scriptionsetincluded14,029subscriptions,however,insomeoftheexperimentsweincreasedthenumberofsubscriptionstostudythescalabilityofthesystem.
Thetemplatesalongwiththeirprobabilityofoccurrencearedescribedbelow:–{(Symbol=P1)∧(P2≤Open≤P3)}.
NotifyeventsforstockP1whenitsopenvalueisbetweenP2andP3.
Probability=20%.
–{(Symbol=P1)∧(Low≤P2)}.
NotifyeventswhereacertainstockP1'svalueislessthanorequaltoP2.
Probability=35%.
–{(Symbol=P1)∧(High≥P2)}.
NotifyeventswhereacertainstockP1'svalueishigherthanorequaltoP2.
Probability=35%.
–{(Symbol=P1)∧(Volume≥P2)}.
NotifyeventswhereacertainstockP1wastradedmorethanorequaltoP2.
Probability=5%.
–{Volume≥P1}.
NotifyifastockistradedmorethanP1.
Probability=5%.
Wehaveusedtwodierentsetsofevents.
Oneoftheeventsetswascre-atedsyntheticallybygeneratinguniformlyrandomvaluesinthedomainsoftheattributes.
Thiseventsetconsistsof115,000events(againinthescalabilityex-perimentswevariedthenumberofevents).
Theothereventsetistherealstockeventdatafor100stocks.
ThedatawasobtainedfromYahoo!
Finance[29]bydownloadingthestockeventsonadailybasisstartingfrom2/Jan/1998to31/Dec/2002.
Thiseventsetcontains115,353events.
Therealeventsetishighlyskewedbecausemostofthestockpricesrangedbetweenthevaluesof$10to$30.
Thisistypicalofrealworlddatasets.
Weevaluatedthescalabilityofthesystembyrunningthesimulationwithvaryingnumberofpeersinthesystem.
Weperformedmeasurementsfor100,1000and10,000peersinthesystem.
Thesimulationswereinitializedwithonepeerinthesystem.
Anewpeerjoinsthesystemaftereachsimulationeventwithaprobabilityof10%,untilthetotalnumberofpeersreachesthebound.
Wemeasuredthenumberofpeerscontactedtodelivereachevent.
Toevaluatetheloadonthepeers,wemeasuredthetotalnumberofmessagesreceivedbyeachpeerduringtherunofthesimulation.
Thisincludesmessagesduetoroutingofeventsandsubscriptions,aswellasmessagesduetopropagationofevents.
Theseexperimentsdonotincludepeerfailure.
Inthefollowingsectionswepresenttheresultsoftheevaluation.
Firstwepresenttheevaluationresultsforthescalabilityandloadbalancingofthesystemforthesyntheticandrealeventsets.
Later,weanalyzetheeectivenessofzonereplicationinthesystem.
268AbhishekGuptaetal.
0204060801000-55-1010-1515-2020-3030-4040-5050-6060-100PercentageofEventsPercentageofPeersVisited100peers1000peers10,000peers(a)SyntheticEventSet0204060801000-55-1010-1515-2020-3030-4040-5050-6060-100PercentageofEventsPercentageofPeersVisited100peers1000peers10,000peers(b)RealEventSetFig.
9.
ScalabilityPerformanceoftheSystem.
5.
2SystemScalabilityInthissectionwepresenttheevaluationresultsforthescalabilityofthesystemwhenthenumberofpeersinthesystemisvaried.
Wealsoanalyzedtheeectofvaryingthenumberofsubscriptionsandthenumberofeventsonthesystem.
Figure9showsthedistributionofthenumberofpeersthatwerecontactedinordertodelivereventstorelevantsubscriptions.
Thex-axisintheplotrepresentsthepercentageofpeerscontactedtodeliveraneventoutofthetotalnumberofpeersthatwerepresentinthesystemwhentheeventwasgenerated.
Thebucketsonthex-axishavebeenrecalibratedbecausethevalues60-100onx-axishadnodatapoints,andtherange0-20hasbeenexpanded.
Figure9(a)showsthescalabilityofthesystemforthesyntheticeventset,wheretheeventsaredistributeduniformlyinthedomain.
Inthecaseof100peers,morethanhalfoftheeventsweredeliveredtoalltherelevantsubscriptionsbycontactingatmostupto5%ofthepeersonly.
Forthecaseof10,000peers95%oftheeventsweredeliveredtoallaectedsubscriptionsbycontactinglessthan5%ofthepeers.
Infact,almostalltheeventsweredeliveredbycontactinglessthan10%ofthepeers.
Overall,asthenumberofpeersinthesystemincreases,thepeersneededtobecontactedfordeliveringeventsscalesverywell.
Figure9(b)showstheresultsforthesimulationswiththerealeventsetwhichishighlyskewed.
Becauseoftheskeweddistributionoftheeventdata,morezonesarecreatedinthevicinityofeventpointswhichleadstoasmallincreaseinthenumberofpeerscontactedtodeliverevents.
Evenwithskewedevents,inthecasesof100and1000peers,85%-90%aredeliveredbycontactingatmost15%ofthepeers.
Fortheexperimentwith10,000peers,almostalleventsaredeliveredbycontactinglessthan10%ofthepeersand97%ofthoseeventscontactlessthan5%ofthepeers.
ThisstrengthensourconclusionthatMeghdootscalesverywellasthenumberofpeersinthesystemincrease.
Weperformedanexperimentwith10,000peersinthesystembyvaryingthenumberofsubscriptionsinstalledinthesystemfrom25,000to150,000.
Weusedthesyntheticeventsetforthisexperimentwhichcontained115,000events.
Figure10showstheresults.
Inallcasesmorethan95%oftheeventsareMeghdoot:Content-BasedPublish/SubscribeoverP2PNetworks2690204060801000-55-1010-1515-2020-3030-4040-5050-6060-100PercentageofEventsPercentageofPeersVisited25k50k100k150kFig.
10.
EectofVaryingtheNumberofSubscriptions.
0204060801000-55-1010-1515-2020-3030-4040-5050-6060-100PercentageofEventsPercentageofPeersVisited200k300k400k500kFig.
11.
EectofVaryingtheNumberofEvents.
deliveredbycontactinglessthan5%ofthepeersinthesystem.
Thereisonlyamarginaldegradationinperformanceevenasthenumberofsubscriptionsstoredinthesystemincreasesfrom25,000to150,000over10,000peers.
ThisshowsthatMeghdootscaleswellasthenumberofinstalledsubscriptionsincreases.
Inanotherexperimentwevariedthenumberofeventsfrom200,000to500,000.
Thesesimulationshad10,000peersinthesystemand50,000subscrip-tions.
Theeventssetscontaineduniformlydistributedevents.
Figure11showstheresultsoftheexperiment.
With200,000eventsinthesystemmorethan75%oftheeventsaredeliveredbycontactingatmost5%ofthepeers.
Forallcases,atmost15%ofthepeersarecontactedtodelivertheevents.
Theresultsareverysimilarinallcasesdemonstratingthatthesystemscalesverywellwiththenumberofevents.
5.
3LoadDistributionWemeasuretheloadonapeerastheratioofmessagesthepeerreceivestothetotalnumberofmessagesprocessedinthesystemsincethepeerjoinedthesystem.
Figure12showstheloaddistributiononthepeersinthesystem.
Thepeersweresortedindecreasingorderoftheload,andweregroupedbytheirrankintogroupsofsize10%each.
Theplotshowstheaverageloadoneachgroup.
01234560-1010-2020-3030-4040-5050-6060-7070-8080-9090-100PercentageofMessagesReceivedPeersRankedbyMessageLoad100peers1000peers10,000peers(a)SyntheticEventSet0123450-1010-2020-3030-4040-5050-6060-7070-8080-9090-100PercentageofMessagesReceivedPeersRankedbyMessageLoad100peers1000peers10,000peers(b)RealEventSetFig.
12.
LoadDistributionintheSystem.
270AbhishekGuptaetal.
Figure12(a)showstheloaddistributioninthesystemforthesyntheticeventsetwheretheeventsaredistributeduniformly.
Eveninthecaseof100peersthemaximumloadisonly5.
35%ofthemessages,whichisverygood.
Inthecaseof10,000peerstheloadisveryevenlydistributedamongallthepeersinthesystem.
Asthenumberofpeersincreaseinthesystem,theloadisevenlysharedbythenewpeers.
Thisshowsthatourloadbalancingschemesarequiteeective.
Figure12(b)showstheloaddistributionoverthepeersfortherealeventsetwhichishighlyskewed.
Inthecaseof100peers,themaximallyloadedpeershandlelessthan5%ofthetotalmessages.
Asthenumberofpeersincreases,theloadiswelldistributedamongthenewjoiningpeers.
Thetrendofloaddistributionisverysimilartothecaseofuniformlydistributedevents.
Therefore,ourloadbalancingstrategiesareveryeectiveandadaptverywelldynamicallytothedistributionofsubscriptionsandevents.
00.
020.
040.
060.
080.
10.
120-1010-2020-3030-4040-5050-6060-7070-8080-9090-100PercentageofMessagesReceivedPeersRankedbyMessageLoad25k50k100k150kFig.
13.
EectofVaryingtheNumberofSubscriptionsonLoadDistribution.
00.
020.
040.
060.
080.
10-1010-2020-3030-4040-5050-6060-7070-8080-9090-100PercentageofMessagesReceivedPeersRankedbyMessageLoad200k300k400k500kFig.
14.
EectofVaryingtheNumberofEventsonLoadDistribution.
Figure13showstheloaddistributioninthesystemwhenwevariedthenumberofstoredsubscriptions.
Thisexperimenthad10,000peersandusedthesyntheticeventsetwith115,000events.
Eventhemostheavilyloadedpeersreceivedonlyabout0.
123%ofthetotalmessagesgeneratedinthesystem.
Whenthenumberofstoredsubscriptionsincreases,thenumberofmessagesgeneratedincreases,butasisevidentfromthegraph,thisloadisevenlydistributedamongtheavailablepeers.
Theloaddistributionina10,000peersystemwhenthenumberofeventsisvariedfrom200,000to500,000isshowninFigure14.
Therewere50,000subscriptionsinthisexperiment.
Thedistributionoftheloadamongthepeersinthesystemremainsquitestablewiththegrowingnumberofevents.
5.
4ReplicationofZonesThesystemreplicateszonesthatareoverloadedduetoeventpropagationasamechanismtohandleload.
Thishasprovedtobeaveryeectivestrategyasisevidentfromthepreviousanalysis.
Inthissection,weanalyzetheeectthedistributionofeventshasonthedegreeofreplicationinthesystem.
Meghdoot:Content-BasedPublish/SubscribeoverP2PNetworks271Table1.
NumberofUniqueZones.
#peersSyntheticEventsRealEvents1007673100065247010,00096229323Table1summarizesthenumberofuniquezonesthatwerecreatedduringthesimulationswithrealandsyntheticeventsetswith14,029subscriptions.
Eachzoneinthesystemhasatleastonepeerassociatedwithit.
Theremainingpeersareusedforreplication.
Notethatthenumberofpeernodesusedforthereplicationofexistingzonesishigherinallcaseswhentherealeventsetisused.
Thisisthecasebecausetherealeventset,asistypicalofmanyrealworlddatasets,isveryskewedandalotofeventsarepropagatedthroughthesamezoneswhichoverloadsthem.
Therefore,newjoiningpeersaredirectedtothosezonesandtheyarereplicatedtoreducethepropagationload.
11010010001000005101520NumberofZonesNumberofReplicas100peers1000peers10000peers(a)SyntheticEventSet110100100010000051015202530NumberofZonesNumberofReplicas100peers1000peers10000peers(b)RealEventSetFig.
15.
Replicationofzones.
Figure15presentsthedistributionofthedegreeofreplicationinthesystem.
Thex-axisisthedegreeofreplicationandthey-axisisthenumberofuniquezonesthatwerereplicatedwiththatdegree.
They-axishasbeenplottedonlogscalebecauseofthelargevariationinthenumberofnon-replicatedzonesinthecasesofdierentnumberofpeersinthesimulations.
InFigure15(a)for10,000peers,therewasazonewhichwasreplicated20times.
FromFigure15(b),wecanseethatoneofthezoneswasreplicatedtoahighdegreeof27.
Asmentionedearlier,intherealeventset,moststockeventshadpricevaluesintherangeof$10-$30.
Thusalargesubsetoftheeventsmaptotheeventpointsthatfallinasmallnumberofzones.
Thesezonesthereforehaveahighdegreeofreplicationtoovercometheloadgeneratedbytheseevents.
272AbhishekGuptaetal.
6ConclusionsWepresentedMeghdoot,amiddlewareforacontent-basedpublish/subscribesystem,whichleveragespeer-to-peerbasedDistributedHashTablesforscalabledisseminationofdataeventstosubscribersdistributedacrossthenetwork.
P2Pdesignoerstheexibilityofincorporatingadditionalresources,thusprovidingperformancescalability.
Meghdootimposesnorestrictionsoversubscriptionsandallowsthemtobespeciedintermsofrangepredicatesoverallattributesinaschema.
UnlikemostotherP2Papproaches,Meghdootusesthesemanticsofthesubscriptionsandtheeventstostoresubscriptionsanddelivermatchingeventstothem.
Sincerealworlddatasetstendtobeskewed,existingpeermanagementtechniquesfailtodistributeloadwellamongthepeers.
Hence,unlikepreviouswork,weusethecharacteristicsoftheloadtodeterminehowtodistributetheload.
Subscriptionloadleadstozonesplitting,whileeventpropagationloadleadstozonereplication.
Wealsoexploittheunderlyingdistributedhashstructuretoreplicatesubscriptionsforfaulttoleranceinaninnovativeandsystematicallytransparentway.
Ourextensivesimulationexperimentshaveveriedthescala-bilityandloadbalancingaspectsofMeghdoot.
Inparticular,theexperimentsshowthatthedesignscalesverywelluptothousandsofpeersinthesystemandcanhandlelargenumbersofsubscriptionsandevents.
Theyalsodemonstratethatbothzonereplicationandsplittingtechniquesareveryeectiveinevenlydistributingtheloadamongthepeersinthesystem.
References1.
H.
Balakrishnan,M.
F.
Kaashoek,D.
Karger,R.
Morris,andI.
Stoica.
LookingupdatainP2Psystems.
CommunicationsoftheACM,46(2):43–48,Feb.
2003.
2.
G.
Banavar,T.
Chandra,B.
Mukherjee,J.
Nagarajarao,R.
E.
Strom,andD.
C.
Sturman.
Anecientmulticastprotocolforcontent-basedpublish-subscribesys-tems.
InProceedingsofthe19thICDCS,pages262–272,1999.
3.
K.
P.
Birman.
Theprocessgroupapproachtoreliabledistributedcomputing.
CommunicationsoftheACM,36(12):36–53,Dec.
1993.
4.
A.
Carzaniga,D.
S.
Rosenblum,andA.
L.
Wolf.
Designandevaluationofawide-areaeventnoticationservice.
ACMTransactionsonComputerSystems,19(3):332–383,2001.
5.
M.
Castro,P.
Druschel,A.
Kermarrec,andA.
Rowstron.
SCRIBE:Alarge-scaleanddecentralizedapplication-levelmulticastinfrastructure.
IEEEJournalonSe-lectedAreasinCommunications,20(8):100–110,2002.
6.
J.
Chen,D.
J.
DeWitt,F.
Tian,andY.
Wang.
NiagaraCQ:Ascalablecontinuousquerysystemforinternetdatabases.
InProceedingsofthe2000ACMSIGMOD,pages379–390,2000.
7.
F.
Fabret,H.
A.
Jacobsen,F.
Llirbat,J.
Pereira,K.
A.
Ross,andD.
Shasha.
Filteringalgorithmsandimplementationforveryfastpublish/subscribesystems.
SIGMODRecord,30(2):115–126,2001.
8.
L.
Galanis,Y.
Wang,S.
R.
Jeery,andD.
J.
DeWitt.
Locatingdatasourcesinlargedistributedsystems.
InProceedingsofthe29thVLDB,pages874–885,2003.
9.
Gnutella.
http://gnutella.
wego.
com/.
Meghdoot:Content-BasedPublish/SubscribeoverP2PNetworks27310.
A.
Gupta,D.
Agrawal,andA.
ElAbbadi.
Approximaterangeselectionqueriesinpeer-to-peersystems.
InProceedingsofthe1stCIDR,pages141–151,2003.
11.
E.
N.
Hanson,C.
Carnes,L.
Huang,M.
Konyala,L.
Noronha,S.
Parthasarathy,J.
B.
Park,andA.
Vernon.
Scalabletriggerprocessing.
InProceedingsofthe15thICDE,pages266–275,1999.
12.
M.
Harren,J.
M.
Hellerstein,R.
Huebsch,B.
T.
Loo,S.
Shenker,andI.
Stoica.
ComplexqueriesinDHT-basedpeer-to-peernetworks.
InProceedingsoftherstInternationalWorkshoponPeer-to-PeerSystems,pages242–250,2002.
13.
IBMNews.
http://www.
ibm.
com/ibm/history/history/year2000.
html.
14.
KaZaA.
http://www.
kazaa.
com/.
15.
Napster.
http://www.
napster.
com/.
16.
B.
Oki,M.
Puegl,A.
Siegel,andD.
Skeen.
Theinformationbus:anarchitectureforextensibledistributedsystems.
InProceedingsofthefourteenthACMSOSP,pages58–68,1993.
17.
P.
R.
PietzuchandJ.
Bacon.
Peer-to-peeroverlaybrokernetworksinanevent-basedmiddleware.
InProceedingsofthe2ndDEBS,pages1–8,2003.
18.
S.
Ratnasamy,P.
Francis,M.
Handley,R.
Karp,andS.
Shenker.
Ascalablecontent-addressablenetwork.
InProceedingsofthe2001ACMSIGCOMM,pages161–172.
19.
S.
Ratnasamy,M.
Handley,R.
Karp,andS.
Shenker.
Application-levelmulti-castusingcontent-addressablenetworks.
InProceedingsofthe3rdInternationalWorkshopofNGC,volume2233,pages14–29.
LNCS,Springer,2001.
20.
A.
RowstronandP.
Druschel.
Pastry:Scalable,distributedobjectlocationandroutingforlarge-scalepeer-to-peersystems.
InIFIP/ACMMiddleware2001.
21.
O.
D.
Sahin,A.
Gupta,D.
Agrawal,andA.
ElAbbadi.
Apeer-to-peerframeworkforcachingrangequeries.
InProceedingsofthe20thICDE,pages165–176,2004.
22.
B.
SegallandD.
Arnold.
Elvinhasleftthebuilding:Apublish/subscribenotica-tionservicewithquenching.
InProceedingsofAUUG,1997.
23.
I.
Stoica,R.
Morris,D.
Karger,M.
F.
Kaashoek,andH.
Balakrishnan.
Chord:Ascalablepeer-to-peerlookupserviceforinternetapplications.
InProceedingsofthe2001ACMSIGCOMM,pages149–160.
24.
D.
Tam,R.
Azimi,andH.
-A.
Jacobsen.
Buildingcontent-basedpublish/subscribesystemswithdistributedhashtables.
InProceedingsofInternationalWorkshoponDatabases,InformationSystemsandPeer-to-PeerComputing,2003.
25.
W.
W.
Terpstra,S.
Behnel,L.
Fiege,A.
Zeidler,andA.
P.
Buchmann.
Apeer-to-peerapproachtocontent-basedpublish/subscribe.
InProceedingoftheSecondDEBS,2003.
26.
Tibco.
http://www.
tibco.
com/.
27.
P.
TriantallouandT.
Pitoura.
Towardsaunifyingframeworkforcomplexqueryprocessingoverstructuredpeer-to-peerdatanetworks.
InFistInternationalwork-shopDBISP2P2003,pages169–183.
28.
Vitria.
http://www.
vitria.
com/.
29.
Yahoo!
Finance.
http://nance.
yahoo.
com/.
30.
Y.
B.
Zhao,J.
Kubiatowicz,andA.
Joseph.
Tapestry:Aninfrastructureforfault-tolerantwide-arealocationandrouting.
TechnicalReportUCB/CSD-01-1141,UniversityofCaliforniaatBerkeley,2001.
31.
S.
Q.
Zhuang,B.
Y.
Zhao,A.
D.
Joseph,R.
H.
Katz,andJ.
D.
Kubiatowicz.
Bayeux:anarchitectureforscalableandfault-tolerantwide-areadatadissemina-tion.
InProceedingsofthe11thACMNOSSDAV,pages11–20,2001.