Comparative Evaluation of Dependability Characteristics for Peer-to-Peer Architectural Styl

StylesbySimulation󰀃

LudgerBischofs,SimonGiesecke,MichaelGottschalk,WilhelmHasselbring∗,TimoWarns,StefanWiller

SoftwareEngineeringGroup

CarlvonOssietzkyUniversityOldenburg

26111Oldenburg,Germany

Abstract

Animportantconcernforthesuccessfuldeploymentofadependablesystemisitsqualityofservice(QoS),whichissignificantlyinfluencedbyitsarchitecturalstyle.Weproposethecomparativeevaluationofarchitecturalstylesbysimulation.Ourapproachintegratesarchitecturalstylesandconcretearchitecturestoenableearlydesign-spaceexplorationinordertopredicttheQoSofpeer-to-peersystems.Weillustratetheapproachviatwocasestudieswhereavailabilityofresourcesandperformanceofpeer-to-peersearchmethodsareevaluated.Basedonourexperiencewiththesesimulationenvironments,wesketchtoolsupportforsimulatingarchitec-turalchangesatruntime.

Keywords:ArchitecturalStyle,Dependability,Peer-to-PeerSystem

󰀁ThisworkissupportedbytheGermanResearchFoundation(DFG),grantGRK1076/1,andbytheEUNetworkofExcellenceDELOS,contractnr.507618.∗Correspondingauthor.Telephone:+49-441-798-2992,Fax:+49-441-798-2196Emailaddresses:ludger.bischofs@informatik.uni-oldenburg.de(LudgerBischofs),simon.giesecke@informatik.uni-oldenburg.de(SimonGiesecke),michael.gottschalk@informatik.uni-oldenburg.de(MichaelGottschalk),hasselbring@informatik.uni-oldenburg.de(WilhelmHasselbring),timo.warns@informatik.uni-oldenburg.de(TimoWarns),stefan.willer@informatik.uni-oldenburg.de(StefanWiller).

PreprintsubmittedtoElsevierScience6February2006

1Introduction

Architecturesofpeer-to-peersystemsareconstrainedbyarchitecturalstylesthatarespecializationsoftheabstractpeer-to-peerstyle.Theselectedconcretearchitecturalstyleforaspecificsystemhasacrucialimpactontheemergentdependabilitycharacteristicsoftherealizedsystemservices.Thedecisionforanarchitecturalstyleisoneoftheearliestdesigndecisions.Achangeofsuchadecisionisusuallynotfeasiblewithreasonableeffort,becausethisdecisionimpactsallsubsequentdevelopmentphases.Therefore,differentarchitecturalstylesshouldberigorouslyassessedearlyinthedevelopmentprocess.Differentalternativesmustbeevaluatedtoenablesuchdesigndecisions.Theevaluationisdifficultinsuchacontext,becauseformalanalysisorobservationofreal-worldsystemsisstillanunsolvedproblemforlarge-scalepeer-to-peersystems.Thedynamicevolutionofapeer-to-peertopologyisanadditionalobstacle.Evenifsystemswithacomparablestylearealreadydeployed,theymaynotallowforappropriatemeasurements.Developingaprototypesystemanddeployingitformeasurementsinaproductionenvironmentrequireshighefforts.

AccordingtotheISO/IEC14598-1(1999)standard,wefollowthetermino-logicalconventions:Acharacteristic(e.g.,performance)isahigh-levelqualitypropertyofasoftwaresystem,whichisrefinedintoasetofsub-characteristics(e.g.,timeefficiency),whichareagainrefinedintoqualityattributes(e.g.,throughput).Qualityattributescanbemeasuredusingaqualitymetric.Ametricisameasurementscalecombinedwithaproceduredescribinghowmeasurementshouldbeconducted(e.g.,numberofprocessedjobspersec-ond).Theapplicationofaqualitymetrictoaspecificsoftwaresystemyieldsmeasurements.

Aviˇzienisetal.(2004)structuredependabilityofcomputingsystemsbythethreatstodependability,thecharacteristics1ofdependability,andthemeanstoattaindependability.Dependabilityengineeringaimsatdeliveringsys-temservicesthatcanbejustifiablytrusted.Dependabilityintegratestheba-siccharacteristicsavailability,reliability,safety,confidentiality,integrity,andmaintainability.Thecharacteristicsavailability,reliability,andperformancedeterminetheQualityofService(QoS)ofasystem.

1

Aviˇzienisetal.(2004)callthecharacteristicsattributes.Wefollowthedifferentia-tionamongcharacteristicsandattributesoftheISO/IEC14598-1(1999)standard;thususethetermcharacteristic.

2

Anysoftwaresystemhasasoftwarearchitecturethatmayormaynotbede-scribedexplicitly(MedvidovicandTaylor,1998).WerefertothedefinitionofsoftwarearchitectureasgivenintheANSI/IEEEStandard1471-2000(Maieretal.,2001):

“Thefundamentalorganizationofasystemembodiedinitscomponents,theirrelationshipstoeachother,andtotheenvironment,andtheprinciplesguidingitsdesignandevolution.”(IEEE,2000)

Theunderlyingprinciplesforthearchitectureofsomeconcretesoftwaresys-temincludeconstraintssuchasarchitecturalstyles(Garlanetal.,1994).Peer-to-peersystemsdeserveparticularattentionindependabilityengineeringastheyareincreasinglydeployedinapplicationdomainswithhighdependabil-ityrequirements.Usually,peer-to-peersystemsarelargeastheymayconsistofseveralthousandpeers.Thus,itisunrealistictoevaluatetheiremergentqualitycharacteristicsonlyanalyticallybymeansofformalreasoning.Com-plementarytoanalyticalreasoning,weproposethecomparativeevaluationofarchitecturalstylesbymeansofsimulation.Apeer-to-peersystemmaydynamicallychangeitsarchitectureatruntimeaspeersjoinorleavethesys-tem.However,thesearchitecturalchangesareconstrainedbythearchitecturalstylesimposedonthesystem.Weidentifybasiccharacteristicsofarchitecturalstylesforpeer-to-peersystemsandusearchitecturaldescriptionsasinputforsimulationtoolstopredicttheQoSofreal-worldsystems.

Thecontributionofthispaperisasimulation-basedapproachthatsupportsearlydesigndecisionsofarchitecturalstylesforpeer-to-peersystems.Simula-tionallowstoevaluatearchitecturalstylesforsystemswithalargenumberofparticipatingpeers.Itallowstotaketheevolutionofthetopologyofthesys-temunderdevelopmentintoaccountandenablesusefulmeasurements.Theapproachintegratespeer-to-peerarchitecturalstyles,architectures,systems,andqualitycharacteristics.Wedemonstratetheusefulnessoftheapproachbypresentingtwoexamplesimulationsystems.Futureworkwillemphasizethesimulationofarchitecturalchangesatruntime,basedonourhithertoexistingexperiencewithdifferentsimulationsystems.

Thepaperisorganizedasfollows.Section2introducesthebasicsofpeer-to-peersystemsandpeer-to-peerarchitecturalstyles.Section3illustratestheproposedapproachtosimulation-basedevaluationofarchitecturalstylesandpresentstheresultsoftwocasestudiesthatevaluatedifferentarchitecturalstyleswithrespecttotheirinfluenceonavailabilityandperformance.Sec-tion4describesthearchitecturesofourcurrentandfuturesimulationenvi-ronments.Section5discussesrelatedwork.Section6drawssomeconclusionsandindicatesdirectionsforfuturework.

3

2Peer-to-PeerArchitecturalStyles

Thepeer-to-peerstyleisanextensiontotheclient-serverstyleforarchitectingdistributedsystems.Inaclient-serversystem,eachnodehasafixedroleofeitheractingasaclientorasaserver.Inapeer-to-peersystem,anynodemayactbothasaclientandasaserver,thatis,anynodemayprovideandconsumeservices.Schollmeier(2001)callsnodestakingbothroles“servents”,whichcombinestheterms“server”and“client”.

Apeer-to-peerarchitecturalstyleisaspecializationofthegenericpeer-to-peerstyleanddefinesafamilyofpeer-to-peersystems.Peer-to-peerarchitecturalstylescanbecharacterizedbythetypeofdecentralization,typeofstructure,andthetypeofcommunication.

Thetypeofdecentralizationcanessentiallybedecentralized,hybrid,orsuper-peer.Inadecentralizedsystem,allservicesaredecentralizedandcanbeofferedbyanypeer.Forexample,thedevelopersoftheGnutella(Gnutella,2006)file-sharingsystememployadecentralizedstyleallowingeachpeertois-suesearchrequests,toanswersearchrequests,andtosharerequestedfiles.Inahybridsystem,someservices,suchasdirectoryservices,arecentrallyofferedbydedicatedservers,whichdonotactasregularpeers.Incontrasttoclient-serverarchitectures,otherservicesremaindecentralized.Forexample,Napster(Napster,2006)isahybridfile-sharingsystemwithcentralizedserversthatmaintainindexesoffilestoanswersearchrequests.Regularpeerssearchforfileswiththehelpoftheseservers.LikepeersofGnutella,theysharetheirfilesdecentrally.Inasuper-peersystem,somepeersareelevatedtoadistinguishedstatus,eitherbyconfigurationorbyself-organizedelection.Thesesuper-peershelpstructuringthetopologyandofferadditionalservices.Figure1illustratesanarchitecturewithasuper-peerstyle.Forexample,thefile-sharingsystemKaZaa(Kazaa,2006)isasystemwithsuper-peersthatprovideanindexingservicefordataresources.KaZaapeerswithhigh-bandwidthnetworkconnec-tionsautomaticallybecomesuper-peersandhostindexesforregularpeers.Thetypeofdecentralizationhasanimpactonthetypesofnodesandontheconstraintsforrun-timeevolutionofthetopology.

Thetypeofstructureimposesglobalconstraintsonthetopology.Apeer-to-peerarchitecturalstylemayimposecertainrestrictionsonthetopology.Forexample,peersmayorganizethemselvestoformatree,mesh,orring.Astructurecanbeutilizedtoimprovetheperformanceofasystem,forexamplebyreducingcommunicationoverheadforsearching.Thecoststomaintainatopologyfollowingstructuralconstraintscanbehighwhenpeersenterandleavethesystemfrequentlyandneedtofindtheirpositionwithinthetopology.Forexample,Stoicaetal.(2001)presentthearchitectureChordwherethepeersareorganizedtoformaring.Eachpeermaintainsinformationaboutthe

4

ringtoimprovetheperformanceofsearchoperations.Mostsuper-peersystemsandmanysystemswithanunstructuredtopologyexhibittheso-calledsmall-worldphenomenon.Originally,Milgram(1967)examinedthisphenomenoninsociology.Thephenomenonmeansthatthereexistsashortchainofsocialacquaintancesforanytwohumans.WattsandStrogatz(1998)usethetermfornetworksthathaveanytwonodesconnectedbyashortpathofintermediatenodes.Networkswithsuchstructuralconstraintsarehighlyscalable,becausecommunicationisefficientinspiteofalargenumberofnodes.Forexample,Clarkeetal.(2000)presentthefile-sharingsystemFreenetthatexhibitsthesmall-worldphenomenonthroughtheuseofadaptiveroutingstrategies.Thetypeofcommunicationmayessentiallybedistinguishedintodirectandindirectcommunication.Communicationisdirectifpeersonlyhavedi-rectconnectionsoftheunderlyingnetworklayerbetweenthem.Forexample,thepeersoftheGnutellasystemonlyusedirectcommunication.Thecommu-nicationisindirectifpeerscancommunicateviaintermediatepeers.Interme-diatepeersmediatethecommunicationbetweenend-to-endcommunicationpartners.Forexample,thepeer-to-peerprotocolJXTA(JXTA,2006)enablespeerstorelaymessagesviaintermediatepeers.Thechoiceofacommunicationtypedeterminesthetypeofcommunicationlinksandinfluencestherulesforcreatingnewcommunicationlinks.

Oftenaconcretepeer-to-peerarchitecturalstyleimpliestrade-offsamongdif-ferentqualitycharacteristics.Forexample,thedevelopersofGnutellasac-rificedperformanceforimprovingresilience.Theyemployedanarchitectural

PeerPeerPeerPeerPeerSuperSuperPeerPeerClusterPeerClusterSuperPeerPeerClusterPeerFig.1.Examplearchitectureinasuper-peerstyle.Aregularpeerisconnectedtoasinglesuper-peer.Asuper-peerformsaclusterwithitsregularpeers.Eachpairofsuper-peersisconnectedbyalink.Indirectcommunicationisallowedamongregularpeersalongthelinks.

5

styleofcompletedecentralizationwithoutanysingle-point-of-failuretoachievehighresiliencedespiteofnodefailures.However,searchinginGnutellatendstobeinefficientastheemployedalgorithmsfloodthenetworkwithquerymes-sages.Developersofothersystems,suchasNapster,madeadifferenttrade-offinfavorofperformancebychoosingastylewithcentralserversthatmaintaincompleteindexes.

Apeer-to-peerarchitecturalstylealsoconstrainstherun-timeevolutionofthenetworktopology,whichisnotincludedintheclassificationscheme.Forexample,whenpeersjoinorleaveasystem,otherpeersmayneedtochangetheirlinksinordertosatisfyconstraintsofthearchitecturalstyle.

3SimulationofPeer-to-PeerStyles

Figure2illustratesoursimulationapproachtotheevaluationoftheinfluenceofpeer-to-peerarchitecturalstylesonthequalitycharacteristicsofserviceswithinconcretearchitecturesandsystems.Wedefineconcretearchitecturesofpeer-to-peersystemsbasedonthestyleandbasedonfaultcharacteristicsoftheparticipatingpeersandconnections.Thisdefinitionisbasedonobserva-tionsofsimilarreal-worldsystemsandonassumptionsaboutfuturesystems.Thearchitecturalstyleconstrainspeers’interconnections.Furthermore,thesystemisinfluencedbyfaultcharacteristicsthatdescribewhenandhowpeersandconnectionsfail.Thesecharacteristicsdeterminetheperiodsofcorrectser-viceandoutage.Areal-worldsystemcorrespondstoaconcretearchitecture.Wepredictthequalitycharacteristicsofthereal-worldsystembyperformingmeasurementsonasimulatedsystemthatcorrespondstothesamearchitec-tureasthereal-worldsystem.Thevalidityofthepredictionisdeterminedbytheaccuracyandtheprecisionofthemeasurementsofthesimulation.

Fig.2.Overviewofourevaluationapproach.Concretearchitecturesaredefinedbasedonthestyleandonfaultcharacteristics.Thesimulatedsystemcorrespondstosuchanarchitectureandmodelsareal-worldsystemconformingtothesamearchitecture.Thereal-worldsystemmaynotreadilyexist,e.g.,whenstylesforfuturesystemsareevaluated.Qualitycharacteristicsaremeasuredforthesimulatedsystemtopredictcharacteristicsofthereal-worldsystem.

6

Inthenexttwosubsections,twoexploratorycasestudiesarepresentedtoillus-trateourapproachtothecomparativeevaluationofpeer-to-peerarchitecturalstyles.Thefirstcasestudyevaluatestheavailabilityofaccesstoreplicatedresources.Thesecondcasestudyevaluatestheperformanceofsearchinginpeer-to-peersystemswithdifferentarchitecturalstyles.

3.1CaseStudytoEvaluateAvailability

Inourfirstcasestudy,wecomparetheavailabilityofaccesstoreplicatedre-sourcesfor(1)threedifferentarchitecturalstyles,(2)twotraditionalvoting-basedreplicationstrategies,(3)twomappingsofreplicastopeers,and(4)threedifferentpeerfailuredistributions.Manypeer-to-peersystemsof-fersystemservicessuchassearchingfordataresources.Aservicedependsonresourcesheldbycertainpeers.Ifasinglepeerownsaresourcethatisrequiredbyasystemservice,afailureofthispeerleadstoafailureoftheserviceasawhole.Inotherwords,theservicejointlyfailswiththepeersowningtherequiredresources.Theoverallsystemneedstobeabletotoleratefaultssuchaspeerandconnectionfailurestoimprovethedependabilityofitsservices.Exemplarily,weconsiderasystemofferingaservicethatenablesaccesstoaresource.

Weassumetheavailability,whichisthereadinessforcorrectservice(Aviˇzienisetal.,2004),tobeequivalenttotheavailabilityofaccesstoaresourcethatistheprobabilitythatthereplicatedresourcecanbeaccessedsuccessfully.Weusethenumberofsuccessfulaccessesperoverallnumberofattemptsasthemetricforavailability.Availabilityofaccessisimpairedbyfailuresofpeersandconnections,forexampleifthefailureofanintermediatepeerrenderscommunicationbetweentwootherpeersimpossible.

Intraditionaldistributedsystems,theproblemthatthefailureofindividualnodesdisablestheaccesstoresourcesisaddressedbyreplicationtechniques.Replicationisrealizedbycreatingreplicas,whicharecopiesofdataresources,andbymaintainingtheirconsistency.Thetechniquesthatrealizeconsistencyrequireaccesstomorethanonereplicaforreadandwriteoperations.There-fore,readingandwritingaresourcewithinapeer-to-peersystemrequiresaccesstomorethanonepeerowningareplica,respectively.Thesepeersmaynotbeaccessibledirectlyifthepeer-to-peersystememploysindirectcommu-nication.Hence,otherpeersmaybeusedtorealizecommunicationamonghostingpeers.Theavailabilityofaccesstothereplicatedresourcedependsontheavailabilityofallpeersandconnectionsthatareinvolved.Asthearchi-tecturalstyledetermineshowpeersareconnectedandcommunicate,ithasamajorimpactontheavailabilityofaccesstoaresource.

7

Manywidelydistributedpeer-to-peersystemssufferfromtheeffectthatpeersleavethesystemanddonotreturnatall.Therateofpeersthatleavethesystempermanentlyiscalledthechurnrateofapeer-to-peersystem.Tra-ditionalreplicationstrategiesarestaticinnature,thatis,replicasremainhostedonthesamenodesoverthewholelifetimeofthesystem.Therefore,theyarenotverywellsuitedforpeer-to-peersystems,becauseapermanentlyleavingpeermayhaveparticipatedinthereplicationstrategy.Iftoomanyofsuchpeersfail,thereplicatedresourcebecomesinaccessibleforever.However,Bhagwanetal.(2003)observedthatthedistributionofpeerfailureswithinareal-worldfilesharingsystemcanbedescribedbyanoverlayofashort-termandalong-termdistribution.Thelong-termdistributionreflectsthechurnrateandtheshort-termdistributionreflectstime-of-dayeffects.Withinourcasestudy,wefocusedontraditionalreplicationstrategiesthatmaytoleratefailurescausedbyshort-termtime-of-dayeffects.Peersleavethesystemforshortperiodsoftimeperday.Ifsuchoutagesdonotaffecttoomanypeers,traditionalreplicationstrategiesareabletotoleratethepeerfailures,becauseasufficientnumberofreplicasisalwaysavailable.Toleratinglong-termeffectsrequiresotherstrategieswithrelaxedconsistencyconstraintsortechniquesforrelocatingreplicasamongpeers.

SimulationScenarios

Theinputparametersforasimulationrunaredefinedinascenario.Asce-narioisanabstractionofaglobalviewonapeer-to-peersystemforacertainperiodoftime.Itdefinestheinputsthatarerequiredtoperformasimulationsuchthatmeaningfulmeasurementsarepossible.Forourcasestudy,asce-nariodefinessetsofpeersandlinks,theirfailuredistributions,andamappingofreplicastopeers.Thearchitectureofsuchascenarioconformstoaspecificarchitecturalstyle.Usually,astyledoesnotrestrictthenumberofparticipat-ingpeers,butthepossibletopologies.However,ascenariodefinesalimitednumberofparticipatingpeers.Therefore,astyleimpliesaninfinitenumberofdifferentscenarios.Inthispaper,weexemplarilyevaluateonescenarioperstyle.

Section2discussesseveraloptionsforpeer-to-peerarchitecturalstyles.Man-ifoldarchitecturescanbecombinedfromtheseoptionsfordesign-spaceex-ploration.Thetypeofdecentralizationdeterminesthepossibledistributionofservices.Exemplarily,weconsiderdecentralizedandsuper-peerarchitectures.Thetypeofcommunicationdetermineswhetherpeersmaycommunicatein-directlywitheachother.Weonlyconsiderarchitecturesthatofferindirectcommunication.Thetypeofstructuredeterminestherestrictionsonthenet-worktopology.AsillustratedinFigure3,weconsiderunstructured,mesh-like,andatypeimposedbyasuper-peerapproachforthetypeofstructure:

8

•Unstructuredstylesonlyimposefewrestrictionsonthetopology.Inthescenario,thepeersareconnectedrandomlyby2to5connectionsperpeer.

•Styleswithmesh-likestructureshavetheirpeersconnectedtoformamesh,wherebyeachpeerisconnectedtofourneighboringpeers.

•Thesuper-peerstructureisformedasfollows:Thesuper-peersformaninnerringwithinthesystem.Eachsuper-peerisconnectedtoitstwosucceedingandtwopreviousneighboringpeersonthering.Eachregularpeerisconnectedtoonesuper-peeronly,i.e.,thereisnoredundancyofsuper-peersforaclientpeer.Thisarchitectureexhibitsthesmall-worldphenomenon.

Inreal-worldsystems,peerswithvaryingfailuredistributionsjoinasystem.Thisneedstobereflectedintheinputforthesimulation.Ascenariodescribesthefailuredistributionsofindividualpeersandconnectionsbythemeantimetofailure(MTTF)andmeantimetorepair(MTTR)values.Weassumecrash-recoveryfailuresforpeersandconnectionsonly,thatis,peersandconnectionsmayhaltandrecover.Thefailuredistributionitselfisassumedtobeexponen-tial.WeemploythreedifferentassignmentsofMTTFandMTTRvaluestopeerandlinksforeachscenario.Thefirstassignmentgivesconstantgoodval-ues(MTTF=3days,MTTR=6seconds)toeachpeertoindicatehighoverallavailability.Thesecondassignmentgivesconstantmediumvalues(MTTF=17hours,MTTR=12minutes)toeachpeertoindicateworseavailabilitythanbefore.Thethirdassignmentemploysanormaldistributionofvalues(MTTF=38hours,σ=22hours,MTTR=72minutes,σ=44minutes).Hence,fewpeersexhibitlowavailability,fewpeersexhibithighavailability,andmostpeersexhibitmediumavailability.Thevaluesarederivedfromtheobservationofasimilarreal-worldsystemfromBhagwanetal.(2003),whofoundthatapeerjoinsandleavestheOvernetsystem6.4timesperdayon

(a)(b)(c)

Fig.3.Illustrationofscenarios.Thegraph(a)exemplarilyshowsaunstructurednetwork.Thepeersareconnectedrandomly.Thegraph(b)exemplarilyshowsafullyconnectedmesh-likearchitecture.Eachpeerisconnectedtofourneighboringpeers.Thegraph(c)showsasuper-peerarchitecture.Eachregularpeerisconnectedtoonesuper-peeronly.Eachsuper-peerisconnectedtofourothersuper-peers.

9

average.Therefore,anoverallMTTFof24h/6.4≈225mincanbeassumedforpeerswithintheOvernetsystem.Weassumehighervaluesasthesimulationismeanttoevaluatesystemsdeployedinalocalareanetworkinwhichthepeerscanbeassumedtobemorereliable.

Amappingmustbedefinedthatassignsreplicastohostingpeers.Forthecasestudy,eachmappingisdefinedtobestatic,thatis,thenumberandplacementofreplicasdonotchangeduringthesimulation.Ourdecisionwheretoplacethereplicasisbasedontheavailabilityofthepeers.Thefirstassignmentofthemappingisdonebyassigningthereplicastopeerswiththehighestavailabilityvalues.ThesevaluesaredeterminedbythepredefinedMTTFandMTTR.Thesecondassignmentproceedsaccordingtoanormaldistribution.Therefore,mostreplicasarehostedbypeersthathavemediumavailability.

Fig.4.Activitydiagram“Peerhandlesmessage”.Thecorrespondingeventtohandleamessagebyapeereitherdefinestoprocessortosendthemessage.Ifitneedstobesent,thecorrespondingactivityisinvoked.Otherwise,thesimulatorcheckswhetherthepeer,forwhichthemessageisscheduled,isthedestinationpeerofthemessage.Inthiscase,thecorrespondinghandlingactivityisinvokedwhileseparatingerrormessagesandnon-errormessages.Ifthepeerisnotthedestinationpeerofthemessage,thepeeractsasamediatorandforwardsthemessage.

10

SimulationModel

Wedevelopedadiscrete-eventsimulatorforasimulationmodelthatapproxi-matesthebehaviorofpeersinreal-worldsystemslikeFreenetasdescribedbyClarkeetal.(2000).Duetospacelimitations,wecannotdescribethesimu-lationmodelinfulldetail.Exemplarily,Figure4illustrateshowasinglepeerhandlesamessagewhenthesimulatorprocessesamessageevent.Thisactivityisembeddedinamoregeneralcontextofhowthesimulatorhandleseventsandhowtoperformthesimulationingeneral.Itrequiresmorerefinedactivi-tiesforbehaviorlikepeersendsmessage.Forsimplicity,weassumeaconstanttransittimeof0.1secondsforallmessagetransfersandaconstantservicetimeof0.3secondsforthehandlingofamessagebyapeer.Inadditiontothebehaviorofreal-worldpeers,thesimulationmodelcoverstwotraditionalreplicationstrategies,thatis,thepeersofferaccesstoareplicatedresourceasaservice.

EachscenarioissimulatedwithreplicationstrategiesthatarespecialinstancesoftheWeightedVotingreplicationstrategy,whichwasintroducedbyGifford(1979).Anumberofvotesisassignedtoeachnodeofaspecificsetofnodes.Usually,anodeisinthesetifandonlyifithostsareplicaoftheresource,butotherstrategiesarepossible.Forsimplicity,weassignonevotetoeachpeerthathostsareplica.Atransactionthattriestoaccessthereplicatedresourcemustcollectaquorumofreadvotesforareadoperationandaquorumofwritevotesforawriteoperationfromthenodeswithassignedvotes.Inordertopreserveone-copyequivalence,apeerthatupdatesaresourcesynchronouslywritesintoallreplicasthatarehostedbythepeersofthecollectedwritequorum.ThestrategiesexemplarilyusedforthesimulationareRead-One-Write-All(ROWA)andMajorityConsensus:

•TheROWAstrategyrequiresatransactiontocollectasinglevoteforareadoperationandallvotesforawriteoperation.

•Thomas(1979)introducedMajorityConsensus,whichrequiresatransac-tiontocollectasimplemajorityofvotesforareadresp.awriteoperation.RefertoBernsteinetal.(1987)foramoredetaileddescriptionofthestrategies.Additionally,eachscenarioissimulatedwithoutanyreplicationtocomparetheseresultstotheresultswithreplication.SimulationResults

Combining(1)thereplicationstrategies,(2)differentmappingsofreplicas,(3)faultdistributions,and(4)peer-to-peerstylesfromaboveyields36sce-nariostosimulate.Table1showstheresultsforeachscenario.Therelativeinfluenceofthereplicationstrategiescomparedtothescenarioswithoutrepli-cationisillustratedinFigure5.

11

Weformulatedsomefundamentalexpectationsforthereplicationstrategiesinadvancetoshowthatthesimulationsetupisreasonable.Forexample,weexpectedROWAtoimprovetheavailabilityofreadingforallscenarios.Theresultsconfirmourexpectationswithminordeviations.Bothreplicationstrategiesimprovetheavailabilityofreadoperations,ROWAimpairswriteoperations,andMajorityConsensusimproveswriteoperations.Withasignif-icancethresholdof1%,thedeviationsfromfundamentalexpectations(e.g.,MajorityConsensusimprovesreadingmorethanROWAforscenarioclass2)arenotsignificant.However,itissurprisingthattheinfluenceofROWAisalmostequaltotheinfluenceofMajorityConsensusformostscenarios.Ascouldbeexpected,theinfluenceofMajorityConsensusisalmostequalforreadingandwritingasthesamenumberofvotesmustbecollected.Availabil-ityforwritingintheROWAstrategysignificantlydecreasesforthenormaldistributioncomparedtotheconstantvalues,becausesomepeersthathostreplicasrequiredforthewritequorumhavelowavailability.

Forscenarioswithhighavailabilityofpeers,thereplicationstrategieshavealmostnoinfluenceforanyarchitecturalstyle.Formediumavailabilityofpeers,thereplicationstrategiesinfluencereadingresp.writing,butthereisnosignificantdifferenceforthedifferentarchitecturalstyles.Foranormaldistributionofpeerfailuresandareplicadistributiontopeerswithhighestavailability,thesystemswithamesh-liketopologyshowworseavailability

󰀁󰀂󰀃󰀄󰀅󰀆󰀇󰀈󰀉󰀊󰀋󰀌󰀇󰀅󰀌󰀍󰀇󰀅󰀇󰀆󰀎󰀏󰀐󰀑󰀒󰀁󰀂󰀌󰀓󰀇󰀈󰀉

󰀙󰀌󰀄󰀅󰀆󰀒󰀘󰀇󰀃󰀆󰀑󰀇󰀍󰀄󰀆󰀇󰀐󰀈󰀔󰀂󰀃󰀕󰀍󰀆󰀃󰀍󰀜󰀂󰀂󰀇󰀔󰀂󰀃󰀕󰀍󰀆󰀃󰀍󰀐󰀄󰀇󰀌󰀖󰀙󰀁󰀂󰀋󰀙󰀆󰀏󰀚󰀌󰀕󰀍󰀋󰀛󰀔󰀂󰀃󰀕󰀍󰀆󰀃󰀍󰀜󰀂󰀂󰀇󰀔󰀂󰀃󰀕󰀍󰀆󰀃󰀍󰀐󰀄󰀇󰀌󰀖󰀙󰀁󰀂󰀋󰀙󰀆󰀏󰀚󰀌󰀕󰀍󰀋󰀛󰀔󰀂󰀃󰀕󰀍󰀆󰀃󰀍󰀜󰀂󰀂󰀇󰀔󰀂󰀃󰀕󰀍󰀆󰀃󰀍󰀐󰀄󰀇󰀌󰀖󰀙󰀁󰀂󰀋󰀙󰀆󰀏󰀚󰀌󰀕󰀍󰀋󰀛

󰀝󰀃󰀕󰀍󰀋󰀖󰀞󰀍󰀖󰀋󰀄󰀇󰀁󰀂󰀔󰀅󰀇󰀕󰀌󰀆󰀇󰀐󰀈󰀒󰀖󰀐󰀈󰀆󰀑󰀐󰀅󰀒󰀗󰀆󰀑󰀌󰀆󰀂󰀉󰀎

󰀁󰀂󰀃󰀄

󰀁󰀂󰀔󰀅󰀇󰀕󰀌󰀒󰀘󰀇󰀃󰀆󰀑󰀇󰀍󰀄󰀆󰀇󰀐󰀈󰀗󰀄󰀕󰀍󰀓󰀘󰀄󰀄󰀋󰀕

󰀁󰀂󰀋󰀙󰀆󰀏󰀓󰀚󰀌󰀕󰀍󰀋󰀛

󰀅󰀄󰀆󰀇󰀈󰀉󰀃󰀄󰀈󰀊󰀋󰀌󰀍󰀄󰀈󰀎󰀏󰀏󰀁󰀂󰀔󰀅󰀇󰀕󰀌󰀒󰀘󰀇󰀃󰀆󰀑󰀇󰀍󰀄󰀆󰀇󰀐󰀈󰀗󰀄󰀕󰀍󰀓󰀘󰀄󰀄󰀋󰀕

󰀁󰀂󰀋󰀙󰀆󰀏󰀓󰀚󰀌󰀕󰀍󰀋󰀛

󰀐󰀆󰀑󰀂󰀋󰀌󰀍󰀒󰀓󰀔󰀂󰀃󰀕󰀄󰀃󰀕󰀖󰀕󰀁󰀂󰀔󰀅󰀇󰀕󰀌󰀒󰀘󰀇󰀃󰀆󰀑󰀇󰀍󰀄󰀆󰀇󰀐󰀈󰀗󰀄󰀕󰀍󰀓󰀘󰀄󰀄󰀋󰀕

󰀁󰀂󰀋󰀙󰀆󰀏󰀓󰀚󰀌󰀕󰀍󰀋󰀛

󰀁󰀂󰀃󰀄󰀅󰀆󰀇󰀈󰀉󰀊󰀋󰀌󰀍󰀇󰀅󰀍󰀎󰀇󰀅󰀇󰀆󰀏󰀐󰀑󰀒󰀊󰀓󰀒󰀇󰀆󰀇󰀈󰀉

󰀙󰀍󰀄󰀅󰀆󰀊󰀘󰀇󰀃󰀆󰀒󰀇󰀎󰀄󰀆󰀇󰀑󰀈󰀔󰀂󰀃󰀕󰀍󰀆󰀃󰀍󰀜󰀂󰀂󰀇󰀔󰀂󰀃󰀕󰀍󰀆󰀃󰀍󰀐󰀄󰀇󰀌󰀖󰀙󰀁󰀂󰀋󰀙󰀆󰀏󰀚󰀌󰀕󰀍󰀋󰀛󰀔󰀂󰀃󰀕󰀍󰀆󰀃󰀍󰀜󰀂󰀂󰀇󰀔󰀂󰀃󰀕󰀍󰀆󰀃󰀍󰀐󰀄󰀇󰀌󰀖󰀙󰀁󰀂󰀋󰀙󰀆󰀏󰀚󰀌󰀕󰀍󰀋󰀛󰀔󰀂󰀃󰀕󰀍󰀆󰀃󰀍󰀜󰀂󰀂󰀇󰀔󰀂󰀃󰀕󰀍󰀆󰀃󰀍󰀐󰀄󰀇󰀌󰀖󰀙󰀁󰀂󰀋󰀙󰀆󰀏󰀚󰀌󰀕󰀍󰀋󰀛

󰀝󰀃󰀕󰀍󰀋󰀖󰀞󰀍󰀖󰀋󰀄󰀇󰀁󰀂󰀔󰀅󰀇󰀕󰀍󰀆󰀇󰀑󰀈󰀊󰀖󰀑󰀈󰀆󰀒󰀑󰀅󰀊󰀗󰀆󰀒󰀍󰀆󰀂󰀉󰀏

󰀁󰀂󰀃󰀄

󰀁󰀂󰀔󰀅󰀇󰀕󰀍󰀊󰀘󰀇󰀃󰀆󰀒󰀇󰀎󰀄󰀆󰀇󰀑󰀈󰀗󰀄󰀕󰀍󰀓󰀘󰀄󰀄󰀋󰀕

󰀁󰀂󰀋󰀙󰀆󰀏󰀓󰀚󰀌󰀕󰀍󰀋󰀛

󰀅󰀄󰀆󰀇󰀈󰀉󰀃󰀄󰀈󰀊󰀋󰀌󰀍󰀄󰀈󰀎󰀏󰀏󰀁󰀂󰀔󰀅󰀇󰀕󰀍󰀊󰀘󰀇󰀃󰀆󰀒󰀇󰀎󰀄󰀆󰀇󰀑󰀈󰀗󰀄󰀕󰀍󰀓󰀘󰀄󰀄󰀋󰀕

󰀁󰀂󰀋󰀙󰀆󰀏󰀓󰀚󰀌󰀕󰀍󰀋󰀛

󰀐󰀆󰀑󰀂󰀋󰀌󰀍󰀒󰀓󰀔󰀂󰀃󰀕󰀄󰀃󰀕󰀖󰀕󰀁󰀂󰀔󰀅󰀇󰀕󰀍󰀊󰀘󰀇󰀃󰀆󰀒󰀇󰀎󰀄󰀆󰀇󰀑󰀈󰀗󰀄󰀕󰀍󰀓󰀘󰀄󰀄󰀋󰀕

󰀁󰀂󰀋󰀙󰀆󰀏󰀓󰀚󰀌󰀕󰀍󰀋󰀛

󰀁󰀂󰀃󰀃󰀃󰀄󰀁󰀂󰀃󰀅󰀇󰀈󰀁󰀂󰀃󰀋󰀅󰀁

󰀁󰀂󰀃󰀋󰀇󰀉

󰀁󰀂󰀃󰀃󰀃󰀅󰀁󰀂󰀃󰀉󰀅󰀊󰀁󰀂󰀃󰀅󰀅󰀆

󰀁󰀂󰀃󰀅󰀆󰀉

󰀁󰀂󰀃󰀃󰀃󰀆󰀁󰀂󰀃󰀉󰀅󰀃󰀁󰀂󰀃󰀅󰀉󰀊

󰀁󰀂󰀃󰀅󰀆󰀈

󰀁󰀂󰀃󰀃󰀃󰀄󰀁󰀂󰀃󰀇󰀈󰀉󰀁󰀂󰀃󰀊󰀇󰀁

󰀁󰀂󰀃󰀊󰀈󰀇

󰀁󰀂󰀃󰀃󰀅󰀃󰀁󰀂󰀃󰀄󰀃󰀈󰀁󰀂󰀃󰀊󰀃󰀃

󰀋󰀁󰀂󰀈󰀉󰀅󰀄

󰀁󰀂󰀃󰀃󰀃󰀆󰀁󰀂󰀃󰀅󰀇󰀃󰀋󰀁󰀂󰀃󰀇󰀅󰀌

󰀁󰀂󰀃󰀇󰀆󰀉

󰀙󰀌󰀄󰀅󰀆󰀒󰀘󰀇󰀃󰀆󰀑󰀇󰀍󰀄󰀆󰀇󰀐󰀈󰀙󰀍󰀄󰀅󰀆󰀊󰀘󰀇󰀃󰀆󰀒󰀇󰀎󰀄󰀆󰀇󰀑󰀈󰀁󰀂󰀃󰀃󰀃󰀉󰀁󰀂󰀃󰀅󰀆󰀈󰀁󰀂󰀃󰀇󰀃󰀈

󰀁󰀂󰀃󰀄󰀉󰀅

󰀁󰀂󰀃󰀃󰀃󰀉󰀁󰀂󰀃󰀉󰀉󰀇󰀁󰀂󰀃󰀅󰀋󰀁

󰀁󰀂󰀃󰀅󰀋󰀅

󰀁󰀂󰀃󰀃󰀃󰀇󰀁󰀂󰀃󰀃󰀃󰀈󰀁󰀂󰀃󰀇󰀆󰀁󰀁󰀂󰀃󰀈󰀃󰀁

󰀁󰀂󰀃󰀉󰀅󰀅

󰀁󰀂󰀃󰀃󰀅󰀌󰀁󰀂󰀃󰀄󰀇󰀌󰀁󰀂󰀃󰀄󰀄󰀁

󰀁󰀂󰀈󰀉󰀆󰀃

󰀁󰀂󰀃󰀃󰀃󰀅󰀁󰀂󰀃󰀅󰀆󰀅󰀁󰀂󰀃󰀇󰀇󰀅

󰀁󰀂󰀃󰀇󰀉󰀁

󰀜󰀋󰀌󰀇󰀈󰀟󰀌 󰀄󰀗󰀆󰀑󰀄󰀕󰀆󰀄󰀑󰀂󰀁󰀂󰀃󰀉󰀆󰀉󰀁󰀂󰀃󰀅󰀉󰀁

󰀁󰀂󰀃󰀅󰀄󰀈

󰀗󰀆󰀒󰀄󰀕󰀆󰀄󰀒󰀂󰀜󰀋󰀌󰀇󰀈󰀟󰀌 󰀄󰀙󰀌󰀄󰀅󰀆󰀒󰀘󰀇󰀃󰀆󰀑󰀇󰀍󰀄󰀆󰀇󰀐󰀈󰀙󰀍󰀄󰀅󰀆󰀊󰀘󰀇󰀃󰀆󰀒󰀇󰀎󰀄󰀆󰀇󰀑󰀈󰀁󰀂󰀃󰀃󰀃󰀋󰀁󰀂󰀃󰀇󰀈󰀉󰀁󰀂󰀃󰀈󰀁󰀃

󰀁󰀂󰀃󰀁󰀃󰀃

󰀁󰀂󰀃󰀃󰀃󰀅󰀌󰀁󰀂󰀃󰀅󰀉󰀆󰀁󰀂󰀃󰀋󰀃󰀄

󰀌󰀁󰀂󰀃󰀋󰀉󰀇

󰀁󰀂󰀃󰀃󰀃󰀅󰀁󰀂󰀃󰀃󰀃󰀊󰀁󰀂󰀃󰀈󰀄󰀇󰀁󰀂󰀃󰀄󰀁󰀇

󰀁󰀂󰀃󰀁󰀃󰀅

󰀋󰀁󰀂󰀃󰀃󰀅󰀉󰀁󰀂󰀃󰀈󰀄󰀇󰀁󰀂󰀈󰀈󰀌󰀄

󰀁󰀂󰀈󰀌󰀁󰀈

󰀁󰀂󰀃󰀃󰀃󰀃󰀁󰀂󰀃󰀇󰀈󰀁󰀋󰀁󰀂󰀃󰀊󰀇󰀌

󰀁󰀂󰀃󰀄󰀃󰀇

!󰀖\"󰀄󰀋󰀈󰀘󰀄󰀄󰀋󰀁󰀂󰀃󰀅󰀇󰀊󰀌󰀁󰀂󰀃󰀋󰀅󰀁

󰀁󰀂󰀃󰀈󰀃󰀃

Table1

Resultingavailabilityvaluesofthefirstcasestudy.Thetableisseparatedintothreemainrowsforeachstructureofapeer-to-peersystem:unstructured,mesh-like,andsuper-peer.Eachmainrowisseparatedintothreesubrowsforfaultdistributionsforthepeers:constantgood,constantmedium,andnormaldistribution.Furthermore,thetableisseparatedintothreemaincolumnsforeachreplicationstrategy:noreplication,ROWA,andMajorityConsensus.Eachmaincolumnisseparatedintotwosubcolumnsforthemappingsfromreplicastopeers:mappingtomostavailablepeersandaccordingtoanormaldistribution.Asbothyieldthesamedistributionfortheconstantavailabilityvalues,theirsubcolumnsaremerged.

12

!󰀖\"󰀄󰀋󰀈󰀘󰀄󰀄󰀋valuesthantheothers.Onereasonisthat,althoughmanyredundantpathsbetweenanytwopeersexist,fewpeerfailuresmakeshortpathsunavailable.Thesimulationmodelincorporatesafixedhoplimitformessagessuchthattheremaininglongerpathscannotbeutilizedforcommunication.Forthesuper-peerarchitectureinscenarioclass12,ROWAyieldsthelargestimprovementofthewholecasestudyandsignificantlyimprovesreadingbetterthanMajorityConsensus.Onereasonisthebenefitoftheshortpathsofthesuper-peerarchitecture.Theabsenceofredundancyofsuper-peersmayhavecausedtheworseresultsforMajorityConsensus.

Thevalidityandfurthergeneralizationsoftheresultsarelimitedforseveralreasons.Besidesgenerallimitationsofsimulation,asinglesystemissimulatedforeacharchitecturalstyleonly.Othersystemsadheringtothesamearchi-tecturalstylemayyielddeviatingresults.Theconvergenceofresultsacrossdifferentsystemsforonearchitecturalstyleisatopicforfutureresearch.

ReadingWriting

Scenarios1234

Unstructured,ConstantGoodUnstructured,ConstantMediumUnstructured,Norm.Distr.,BestPeersUnstructured,Norm.Distr.,Norm.Distr.

5678

Mesh,ConstantGoodMesh,ConstantMediumMesh,Norm.Distr.,BestPeersMesh,Norm.Distr.,Norm.Distr.

9101112

SuperPeer,ConstantGoodSuper-Peer,ConstantMediumSuper-Peer,Norm.Distr.,BestPeersSuper-Peer,Norm.Distr.,Norm.Distr.

Fig.5.Relativeinfluenceforreadingresp.writing.TheleftchartshowstherelativeinfluenceofROWAandMajorityConsensusontheavailabilityofreadoperationscomparedtosimulationswithoutreplication.Therightchartshowstherelativeinfluenceforwriteoperations.

13

3.2CaseStudytoEvaluatePerformance

UnlikethepresentedcasestudyinSection3.1,thefollowingemphasisestheperformancecharacteristicofasoftwaresystem:theperformancebehaviorofsearchmethodsinpeer-to-peersystems.

Peer-to-peersearchmethodsareessentialforthedesignandimplementationofrobustandscalablepeer-to-peersystems.AsurveyandaclassificationofsuchmethodsaregivenbyWangandLi(2003).Accordingtothissurvey,thefirstgenerationofsearchmethodsincludesprotocolslikeNapsterandGnutella,whicharebasedonunstructuredarchitectures.Manymethodsfromthesecondgenerationusedistributedhash-tables(DHTs)toachieveloadbalancingandlogarithmiclook-uptimes.Thethirdgenerationaimstoincreasetheresilienceandavailabilityofnodes.

BischofsandSteffens(2005)introduceanewapproachforaclassofpeer-to-peersystemsbasedonorganization-orientedsuper-peerarchitectures,whichareabletomaporganizationalstructurestopeer-to-peer-systems.Theselec-tionofadequatesearchmethodsforsuchnew,notyetexistingsystemsisdifficult.ThereforetheeaSimsimulator(describedinSection4.1)hasbeendeveloped.Inthefollowingperformancestudy,simulationresultsofsearchmethodsforthevirtuallayeroforganization-orientedpeer-to-peerarchitec-turesaredescribed.Thevirtuallayercontainstypicalpeer-to-peernetworksandrequiresefficientsearchmethodstosupportthetop-levelorganizationallayer(BischofsandSteffens,2005).SimulationScenarios

Inthiscasestudy,weevaluateseveralcombinationsofarchitecturalstyles(Section2)andsearchmethodswithrespecttotheirperformance.Wegiveabriefdescriptionoftheinputsettingsandmetricsanddiscusssomeresults.Bothdecentralizedandsuper-peerstylesareconsidered.Thetopologiesofthedecentralizedsystemsaremesh-like,random,orring-based.Peersinamesh-liketopologyareconnectedtofourneighborsinanundirectedway,whereasrandomlyconnectedpeers(createdbyyEd(2006))haveonetofourconnections.Thering-basedstructurewasadaptedfromStoicaetal.(2001).Allpeersareplacedonaringandobtainfivepointerstootherpeerswithanexponentialdistance.Allsimulatedtopologiescontain1024peers.Forthesuper-peerscenarios,32super-peersarepresent;theremainingregularpeersareuniformlyassignedtothesuper-peers.

Thebehaviorofeachsimulatedpeerisdefinedbyasearchmethod.Inthisstudy,weevaluatetwodifferentapproaches.ThefirstisbasedonRandom

14

WalksaspresentedbyLvetal.(2002).Anyincomingmessageisforwardedtoapredefinedmaximumnumberofneighborsandamaximumhopdepth.Ahistorycanbeusedforbacktracking,ifthemaximumhopdepthisnotexceeded.ThesecondmethodisbasedontheChordprotocol(Section2)andisinspiredbyMizraketal.(2003).Onlysuper-peersareplacedontheChordring.Aspecialneighborhood(finger-table)guaranteesaroutingtimeinO(logS),whereSisthenumberofsuper-peers.Eachsuper-peer,asapartoftheChord-ring,isresponsibleforallresourcesmappedtoauniqueidentifier.Usingadistributedhash-table,thenearestsuper-peercanbedetermined.Themaintainedindexofthissuper-peerprovidesthenecessaryinformationaboutthehostingpeer.

Suitablemetricsneedtobedefinedtoevaluatethesimulatedbehaviorand,therefore,enableausefulsimulationrun.Exemplarily,themeasurementsforfourmetricsareshownintheFigures6to9.Theyvisualizethesuccessrate,theaggregateandindividualnetworkload,andtheresponsetimesforretrievinganswersofcombinedinputsettings:

•Thequerysuccessrateindicateshowmanyansweredqueriesarriveovertime.Itshowstheshareofansweredqueriesandthetimewhenarequiredthresholdhasbeenachieved.

•Theaggregateloadreportsthesumofallactuallyprocessedmessagesateachsimulationstep.Itdisplaystheglobalimpactofmessageoccurrenceinthenetwork.

•Theaveragequeuesizerepresentstheindividualloadofeachnode,mea-suredbytheaveragesizeofeachincomingmessagequeue.Thissizeisanindicatorforthenodeactivity.

•Oneofthemostimportantcriteriaforcharacterizingsearchmethodsisthetimeforretrievingananswer,whichisgivenbythehopsperanswer.Ateachofthefirsttensimulationsteps,twoquerymessagesareinitiatedfromrandomlychosenpeers.Thesearchcriterionisauniquepeername.InitialqueriesarerandomlydistributedtoparticipatingpeerschosenviaalinearcongruencemethodfromKnuth(1997).Allmessagesareterminatedafteratmosttenvisitedhops,suchthatafter20simulationstepsnomorequerymessagesareinthesystem.Afterthishop-to-lifelimitonlythereceivedresponseswillberoutedthereversepath.

ThesearchmethodsbasedonRandomWalkssendthreewalkersforeachfor-wardedmessageatmost.TheChord-basedmethodonlyforwardstheoriginalmessagetoanearernodeonthering.Thereceivernodeiscomputedbyahashfunction.Thisfunctionprovidesanumberforagivenpeername,whichrepresentstheplaceontheringwherethesearchednodeisplaced.

15

SimulationModel

Thesimulationiseventdrivenandtimediscrete.Therespectivesimulationelementsandmessagesaremodeledasentities.Alloccurringmessagesareenduedwithtimestampsandaninitialsendingpeer.Ateachspecifiedtime,theyareplacedintotheprocessingqueuebyaglobaldispatcher.Thesimu-lationmodelconsistsofthreelayers(Figure10inSection4),whereateachlayeramessagewithaspecificheadercanstart.Toreducethedevelopmenteffortofsearchmethods,eachlayercanbesimulatedseparatelyorincombina-tion(adjacentones).Tocombineadjacentlayers,astaticmappingisdefinedtomapeachelementfromthehigherlayertoanotherofthelowerone.Thesearchbehaviorofanelementisstrictlyseparatedfromitsstate.Moreover,foreachelementtypeofanarchitecturalstyleonlyonesearchstrategyexists.Fulfillingthis,astaticstrategyandadynamicelementstateareconnectedviatheVisitorpatternbyGammaetal.(1995).

Ateachsimulationstep,allmessagesfromapeer‘sincomingmessagequeueisprocessed.Theparallelismofmessagesisrealizedviaaninnercycle.Toretrievesimulationresultsatruntime,thespecifiedmetricsaremeasuredandvisualizedstepbystep.SimulationResults

ThesimulatoreaSim(seeSection4.1)isusedinthiscasestudy.Weevalu-atefourcombinationsofarchitecturalstylesandsearchmethodswithstatictopologies.

•sprwrandom:All32super-peersarerandomlyconnected.Theremain-ingpeersareequallydistributedoverthe32clusters.Super-peersusetheRandomWalksmethod,whichforwardsaquerytoatmostthreedirections.

•spchordring:Thesuper-peersareplacedonaringandfollowtheChord-basedapproach.

•p2prwrandom:1024peersarerandomlyconnectedundirectionallytoaveragefourneighborsandusetheRandomWalkssearchmethod.

•p2prwmesh:Peersaremesh-structuredwithtwotofourundirectededges.

First,weexplaintheirregularbehaviorinthefirsttensteps,asseeninFig-ure6.Asdescribedbefore,anewmessageisinitiatedateachofthesesteps,suchthatthesuccessratecanbehigher.Thenumberofqueriesincreases.Thecombinationofthepeer-to-peerarchitecturalstyleswithmeshorrandomtopologiesandthesearchmethodRandomWalkscausetheworstresults.Inthemeshlikesystemonly20%oftheinitiatedquerieswereansweredby

16

sendingover700messages,whereasintherandomversionover5000messagesareneededfor90%ofthequeries.Insidethesuper-peertopologiesthenumberofmessagesissignificantlyreducedandmostqueriesaresatisfied.TheChord-basedsearchmethodevenensuresatheoreticalmaximumquerysuccessrate.Despitethegoodperformancebehaviorofthesuper-peerarchitectures,Figure8showsemergingbottlenecks,becausethesuper-peersactasagatewayfortheircluster.TheChord-basedapproachobviouslyshowsthebestperformanceofthiscomparison.However,ifthedynamicwithinthenetworkisconsidered,themaintenancecostofthedistributedhash-tableincreases.

Fig.6.Timetomatchaqueryde-pictedasquerysuccessrate.Fivecombinationsofarchitecturalstylesandsearchmethodsareshown.

Fig.8.Themaximumqueuesizeateachsimulationsteptomeasuretheindividualload.

Fig.7.Resultingmessagesasaggre-gateloadcausedbyteninitialqueriesinthefirsttensimulationsteps.Fivecombinationsofarchitecturalstylesandsearchmethodsareshown.

Fig.9.Averagenumberofhopsforeachsuccessfulmessageincludingtheone-hopreversepath.

17

4ToolSupport

ThecasestudiespresentedinSection3employedtwospecializedsimulationenvironments.Exemplarily,wepresenttheeaSimtoolinSection4.1,whichisusedinSection3.2.ThistoolisavailablefromSourceforge(eaSim,2006).WedonotonlyuseeaSimforresearchpurposes,butalsoforteachingourstudentsinevaluatingcomplexsoftwaresystems.Forinstance,itisusedinthepracticalassignmentsinthecourseSoftwareSystemsEngineeringattheUniversityofOldenburg.Section4.2sketchesourfutureEclipse-basedsimulationenviron-ment,thatwillbebasedonourexperiencewiththecasestudiesinSection3.Thisnewtoolallowsforsimulatingarchitecturalchangesatruntime.4.1TheeaSimSimulationTool

TheeaSimsimulationtoolisatimediscrete,event-basedpeer-to-peersimula-torbasedonDESMO-J,aframeworkdevelopedbyPageandKreutzer(2005).Unlikeotherpeer-to-peersimulators,whicharediscussedinSection5,eaSimfollowsalayeredapproachforsimulatingeachlayerseparatelyandincom-bination(seeFigure10).Thestateandthebehaviorofapeeraremodeledindependentlytoallowexchangingthesearchandroutingbehaviour.Wiz-ardsassisttheuserduringthesimulationprocess.Figure11showsthechoice,configurationandeditingoptionsforelementtypebasedbehavior.Predefinedmetricscanbeactivatedandvisualizeddirectlyatsimulationtime(seeFig-ure12).

4.2FutureEclipse-basedSimulationEnvironment

Wearecurrentlydevelopinganewintegratedmodelingandsimulationenvi-ronmentforpeer-to-peersystemsbasedonEclipse(2006)inordertosupportourframeworkwithadditionaltools(seeFigure13).Themostdistinctivefea-turewillbethemodelingcomponentprovidingmeansforspecifyingarchitec-turalstyleswithastate-chart-likenotation.Theaimistosimplifythecreationofnewarchitecturesandtosupportfastmodificationstoexistingones.Itwillbepossibletodefinethebehaviorandthepropertiesofthesimulatednodesinascenario.Thisincludesthepossibilityofdynamicallychangingthenetworkstructureduringasimulationrun,whichwasnotfeasiblewitheaSim.Inordertosupportthecomparisonofdifferentarchitectures,thesamescenariocanbesimulatedwithdifferentarchitecturalmodels.Thevisualizationcomponentwillbeabletocomparetheresultsofsimulationsusingdiagramsandtablesofdata.

18

Fig.10.ThearchitectureofeaSimisdividedintothreesimulationlayersontheleftandthefunctionalityontheright.Atthelowestlayerthephysicalhostsarecon-nected.Themiddlelayerdescribesthelogicalinterconnectionofthe(super-)peers.Intheupperlayertherelationshipsamongorganizationalunitscanbeseen.Fur-thermorealladjacentlayersareconnected,suchthateachelementofthehigherlayerishostedonanelementofthelowerone.Eachelementisdividedintoonestatelesspartformodelingthebehaviorandonestatefulpartformodellingtheelementspecificinformationlikeneighborhood,cacheandresources.Eachelementtypebehaviorcanbeassignedtoasetofelements.

Fig.11.Thedisplayedwizardenablestheusertoselectandconfigurethesearchbehaviorofeachelementtype.Viaintrospectiontheconfigurationparametersaredisplayeddynamically,suchthatthebehaviorspecificationisstrictlyseparatedfromthevisualization.Furthermoreeachbehaviorcanbemodifiedwithanintegratededitorandsubsequentlycompiledanddeployed.

19

Fig.12.EachselectedmetriccanbeevaluatedandisdisplayedimmediatelyatruntimebyJFreeChart(2006).Thestatusbarshowsthesimulationtime,therealexecutiontimeandtheprogressofthecurrentsimulationrun.

Extension tothe functionalityPlug−ins realizing thecore functionalityPlug−ins of theEclipse Rich Client PlatformBasic modules of theEclipse Rich Client PlatformModelingGraphicalEditingFrameworkSimulationDesmoJVisualizationJFreeChartHelpFormsResourcesGeneric WorkbenchJFaceSWTPlatform RuntimeFig.13.Layeredarchitectureofourfuturemodelingandsimulationenvironment.Allmoduleswithawhitebackgroundarere-usedcomponents.TheEclipseRichClientPlatformwaschosensinceitprovidesapowerfulfoundation.Itsplug-inconceptisusedinternallytoseparatethethreepartsoftheprogramandisalsousedtoprovideextensibilityoftheapplication.Themodeledarchitectures,scenarios,andthesimulationresultsaremanagedbytheresourceplug-in.Astate-chart-likeeditorisimplementedwiththeGraphicalEditingFramework.Furthermore,DESMO-JisusedasasimulationframeworkandchartsarevisualizedwithJFreeChart.

20

5RelatedWork

Simulation-basedapproachestotheevaluationofpeer-to-peersystemscanbecharacterizedonthebasisoftheirsimulationmodel.Joseph(2003)di-videssimulatorsintofourcategories:numerical,flow-based,event-based,andpacket-based.Relatedtoourworkareevent-basedapproaches.Severalpeer-to-peerprojectssuchasPastry(FreePastry,2006;RowstronandDruschel,2001)andFreenet(Freenet,2006)developedtheirowndedicatedsimulators.Someexamples:

•Joseph(2003)developedthesimulatorNeuroGridtocompareFreenet,Gnutella,andhisownprotocols.ExtensibilityinNeuroGridisachievedbymeansofanobject-orientedframeworkthatcanbeusedviainheritancefromabstractclasses.

•AsapartoftheIRISproject(IRIS,2006)thepeer-to-peersimulatorp2psimwasdeveloped.Thecreationofnewpeer-to-peerprotocolsissup-portedtoimplementjoinandlookupmethods.Sofar,p2psimsupportsvariousstructuredpeer-to-peerprotocolslikeChord(Stoicaetal.,2001),Tapestry(Zhaoetal.,2004),andKademlia(MaymounkovandMazieres,2002).Otherarchitecturalstructuresarenotsupportedyet.

Althoughthesesystemsallowtosimulatedifferentpeer-to-peerprotocols,theyarenotprimarilyconcernedwitharchitecturalstyles.Theyfocusonconcretesystemsanddonotaddresstheunderlyingarchitecturalstyles.Somemoregeneralapproachestosimulatingpeer-to-peersystemsexist:•TingandDeters(2003)designedalayeredtime-discretepeer-to-peersim-ulatorandaimedtoincreaseextensibilityandusabilitybasedonaneval-uationofseveralexistingsimulators.Asolutiontotheseproblemsisproposedbyalayeredapproachwithnetwork,protocol,anduserlayers.Messageroutingandprocessor/networkdelaymodelingaresupported.•Garc´ıaetal.(2005)developedPlanetSim,anobject-orientedJava-basedsimulationframeworkforoverlaynetworks.Theyfollowahierarchicalthreelevelapproachwithphysical,virtual,andapplicationlayers.ThelatterlayerisdefinedbyasharedAPI(Dabeketal.,2003)toofferawell-formedinterface.

Thesegenericapproachescouldbeusedtosimulatedifferentarchitecturalstyles,butsofarthereexistsnopublicationsonsuchwork.

21

6ConclusionsandFutureWork

Wepresentedanewapproachtosimulation-basedcomparativeevaluationofpeer-to-peerarchitecturalstyles.Withrespecttopeer-to-peersystems,weidentifiedbasiccharacteristicsofvariouspeer-to-peerarchitecturalstyles.Exemplarily,weillustratedoursimulationapproachbymeansoftwocasestudiesthatevaluatedifferentarchitecturalstyleswithrespectto(1)theirin-fluenceonavailabilityofresourcesand(2)performanceofpeer-to-peersearchalgorithms.Thetwostudiessatisfiedpredefinedexpectationsandgaveinsightintosimulationofpeer-to-peersystemsforassessmentofdesigndecisionsonarchitecturalstyles.

Withrespecttotoolsupport,wepresenttheeaSimtool.Basedonourexperi-encewiththisandothersimulationenvironments,weindicateourfuturetoolsupportforevaluatingpeer-to-peerarchitecturalstyles.BasedontheEclipseplatform(Eclipse,2006),wearedevelopinganintegratedsimulationenviron-menttosupportoursimulationwithappropriatetools.Thisnewtoolallowsforsimulatingarchitecturalchangesatruntime.Withournewtoolarchitecture,weareabletore-usealotoffunctionalityoftheEclipseplatform,ofDESMO-JandofJFreeChart.OtherEclipse-basedenvironmentscanalsointegrateourplug-ins,whichmayenlargethepotentialusercommunitysignificantly.Futureworkonevaluationofpeer-to-peerarchitecturalstyleswillemphasizethesimulationofarchitecturalchangesatruntime,basedonourhithertoex-istingexperiencewithdifferentsimulationsystems.Thecharacteristicsforvariousarchitecturalstyleswillbefurtherelaboratedandinvestigated.

References

Aviˇzienis,A.,Laprie,J.-C.,Randell,B.,Landwehr,C.E.,2004.Basicconceptsandtaxonomyofdependableandsecurecomputing.IEEETransactionsonDependableandSecureComputing1(1),11–33.

Bernstein,P.A.,Hadzilacos,V.,Goodman,N.,1987.ConcurrencyControlandRecoveryinDatabaseSystems.Addison-Wesley.

Bhagwan,R.,Savage,S.,Voelker,G.M.,2003.Understandingavailability.In:Peer-to-PeerSystemsII,SecondIntl.Workshop.Vol.2735ofLectureNotesinComputerScience.Springer,pp.256–267.

Bischofs,L.,Steffens,U.,2005.Organisation-orientedsuper-peernetworksfordigitallibraries.In:Agosti,M.,Schek,H.-J.,T¨urker,C.(Eds.),Peer-to-Peer,Grid,andService-OrientationinDigitalLibraryArchitectures:6thThe-maticWorkshopoftheEUNetworkofExcellenceDELOS,S.Margherita

22

diPula,Cagliari,Italy,24-25June,2004.RevisedSelectedPapers.Vol.36ofLectureNotesinComputerScience.Springer,pp.45–62.

Clarke,I.,Sandberg,O.,Wiley,B.,Hong,T.W.,2000.Freenet:Adistributedanonymousinformationstorageandretrievalsystem.In:Federrath,H.(Ed.),ProceedingsoftheWorkshoponDesignIssuesinAnonymityandUnobservability.Vol.2009ofLectureNotesinComputerScience.Springer,pp.46–66.

Dabek,F.,Zhao,B.Y.,Druschel,P.,Kubiatowicz,J.,Stoica,I.,2003.TowardsacommonAPIforstructuredpeer-to-peeroverlays.In:Kaashoek,M.F.,Stoica,I.(Eds.),Peer-to-PeerSystemsII,SecondInternationalWorkshop,IPTPS2003,RevisedPapers.Vol.2735ofLectureNotesinComputerSci-ence.Springer,pp.33–44.

eaSim,2006.easim-p2psimulator.Lastcheckedon2006-01-25.URLhttp://sourceforge.net/projects/easimEclipse,2006.Eclipse.Lastcheckedon2006-01-23.URLhttp://www.eclipse.org/

Freenet,2006.TheFreeNetworkProject.Lastcheckedon2006-01-23.URLhttp://freenet.sourceforge.net

FreePastry,2006.Pastry–asubstrateforpeer-to-peerapplications.Lastcheckedon2006-01-23.

URLhttp://freepastry.org/

Gamma,E.,Helm,R.,Johnson,R.,Vlissides,J.,Mar.1995.DesignPatterns–ElementsofReusableObject-OrientedSoftware.Addison-Wesley.Garc´ıa,P.,Pairot,C.,Mond´ejar,R.,Pujol,J.,Tejedor,H.,Rallo,R.,2005.Planetsim:Anewoverlaynetworksimulationframework.In:SoftwareEn-gineeringandMiddleware,4thInternationalWorkshop,SEM2004,Linz,Austria,September20-21,2004,RevisedSelectedPapers.Vol.3437ofLec-tureNotesinComputerScience.Springer,pp.123–136.

Garlan,D.,Allen,R.,Ockerbloom,J.,1994.Exploitingstyleinarchitecturaldesignenvironments.In:SIGSOFT’94:Proceedingsofthe2ndACMSIG-SOFTsymposiumonFoundationsofsoftwareengineering.ACMPress,pp.175–188.

Gifford,D.K.,1979.Weightedvotingforreplicateddata.In:SOSP’79:Pro-ceedingsoftheSeventhACMSymposiumonOperatingSystemsPrinciples.ACMPress,pp.150–162.

Gnutella,2006.Gnutella.Lastcheckedon2006-01-23.URLhttp://www.gnutella.com/

IEEE,2000.IEEERecommendedPracticeforArchitecturalDescriptionofSoftware-IntensiveSystems.IEEE,IEEEStandard1471-2000.

IRIS,2006.Iris:Infrastructureforresilientinternetsystems.Lastcheckedon2006-01-23.

URLhttp://project-iris.net/

ISO/IEC14598-1,1999.ISO/IEC14598-1:Informationtechnology–Softwareproductevaluation–Part1:Generaloverview.ISO/IEC,publishedstan-dard.

23

JFreeChart,2006.Jfreechart.Lastcheckedon2006-01-25.URLhttp://www.jfree.org/jfreechart

Joseph,S.,Nov.2003.AnextendibleopensourceP2Psimulator.P2PJournal,1–15.

JXTA,2006.JXTA.Lastcheckedon2006-01-23.URLhttp://www.jxta.org/

Kazaa,2006.Kazaa.Lastcheckedon2006-01-23.URLhttp://www.kazaa.com/

Knuth,D.E.,1997.TheArtofComputerProgramming,Volume2:Seminu-mericalalgorithms.Addison-Wesley.

Lv,Q.,Cao,P.,Cohen,E.,Li,K.,Shenker,S.,2002.Searchandreplicationinunstructuredpeer-to-peernetworks.In:ICS’02:Proceedingsofthe16thinternationalconferenceonSupercomputing.ACMPress,pp.84–95.

Maier,M.W.,Emery,D.,Hilliard,R.,2001.Softwarearchitecture:IntroducingIEEEStandard1471.Computer34(4),107–109.

Maymounkov,P.,Mazieres,D.,2002.Kademlia:Apeer-to-peerinformationsystembasedontheXORmetric.In:Peer-to-PeerSystems,FirstInter-nationalWorkshop,IPTPS2002,Cambridge,MA,USA,March7-8,2002,RevisedPapers.Vol.2429ofLectureNotesinComputerScience.Springer,pp.53–65.

Medvidovic,N.,Taylor,R.N.,1998.Separatingfactfromfictioninsoftwarearchitecture.In:Proc.3rdIntl.SoftwareArchitectureWorkshop(ISAW3).ACMPress,pp.105–108.

Milgram,S.,1967.Thesmallworldproblem.PsychologyToday(2),60–67.Mizrak,A.T.,Cheng,Y.,Kumar,V.,Savage,S.,2003.Structuredsuperpeers:Leveragingheterogeneitytoprovideconstant-timelookup.In:WIAPP’03:ProceedingsoftheTheThirdIEEEWorkshoponInternetApplications.IEEEComp.Soc.Pr.,Washington,DC,USA,pp.104–111.Napster,2006.Napster.Lastcheckedon2006-01-23.URLhttp://www.napster.com/

Page,B.,Kreutzer,W.,2005.TheJavaSimulationHandbook:SimulatingDiscreteEventSystemswithUMLandJava.BerichteausderInformatik.Shaker.

Rowstron,A.I.T.,Druschel,P.,2001.Pastry:Scalable,decentralizedobjectlocation,androutingforlarge-scalepeer-to-peersystems.In:Guerraoui,R.(Ed.),Middleware2001,IFIP/ACMInternationalConferenceonDis-tributedSystemsPlatformsHeidelberg,Germany,November12-16,2001,Proceedings.Vol.2218ofLectureNotesinComputerScience.Springer,pp.329–350.

Schollmeier,R.,Aug.2001.Adefinitionofpeer-to-peernetworkingfortheclassificationofpeer-to-peerarchitecturesandapplications.In:FirstIntl.Conf.onPeer-to-PeerComputing(P2P2001).IEEEComp.Soc.Pr.,pp.101–102.

Stoica,I.,Morris,R.,Karger,D.,Kaashoek,M.F.,Balakrishnan,H.,2001.Chord-ascalablepeer-to-peerlookupserviceforinternetapplications.In:

24

Proceedingsofthe2001ConferenceonApplications,Technologies,Archi-tectures,andProtocolsforComputerCommunications.ACMPress,pp.149–160.

Thomas,R.H.,1979.Amajorityconsensusapproachtoconcurrencycontrolformultiplecopydatabases.ACMTrans.DatabaseSyst.4(2),180–209.Ting,N.S.,Deters,R.,2003.3LS–apeer-to-peernetworksimulator.In:P2P’03:Proceedingsofthe3rdInternationalConferenceonPeer-to-PeerComputing.IEEEComp.Soc.Pr.,pp.212–213.

Wang,C.,Li,B.,2003.Peer-to-peeroverlaynetworks:Asurvey.Tech.rep.,DepartmentofComputerScience,TheUniversityofScienceandTechnology,.

Watts,D.J.,Strogatz,S.H.,Jun.1998.Collectivedynamicsofsmall-worldnetworks.Nature393,440–442.

yEd,2006.yed-JavaGraphEditor.Lastcheckedon2006-01-25.URLhttp://www.yworks.com/

Zhao,B.Y.,Huang,L.,Rhea,S.C.,Stribling,J.,Joseph,A.D.,Kubiatow-icz,J.D.,Jan.2004.Tapestry:Aresilientglobal-scaleoverlayforservicedeployment.IEEEJournalonSelectedAreasinCommunications22(1),41–53.

25