Enforcing cooperative resource sharing in untrusted peer-to-peer environment

MobileNetworksandApplications10,971–983,20052005SpringerScience+BusinessMedia,Inc.ManufacturedinTheNetherlands.

DOI:10.1007/s11036-005-4453-5

EnforcingCooperativeResourceSharinginUntrustedP2PComputing

Environments

ZHENGQIANGLIANGandWEISONGSHI

DepartmentofComputerScience,WayneStateUniversity,Detroit,MI48202,USA

Publishedonline:24October2005

Abstract.Peer-to-Peer(P2P)computingiswidelyrecognizedasapromisingparadigmforbuildingnextgenerationdistributedapplications.However,theautonomous,heterogeneous,anddecentralizednatureofparticipatingpeersintroducesthefollowingchallengeforresourcesharing:howtomakepeersprofitableintheuntrustedP2Penvironment?Toaddresstheproblem,wepresentaself-policinganddistributedapproachbycombiningtwomodels:PET,apersonalizedtrustmodel,andM-CUBE,amultiple-currencybasedeconomicmodel,tolayafoundationforresourcesharinginuntrustedP2Pcomputingenvironments.PETisaflexibletrustmodelthatcanadapttodifferentrequirements,andprovidesthesolidsupportforthecurrencymanagementinM-CUBE.M-CUBEprovidesanovelself-policingandquality-awareframeworkforthesharingofmultipleresources,includingbothhomogeneousandheterogeneousresources.Weevaluatetheefficacyandperformanceofthisapproachinthecontextofarealapplication,apeer-to-peerWebserversharing.Ourresultsshowthatourapproachisflexibleenoughtoadapttodifferentsituationsandeffectivetomakethesystemprofitable,especiallyforsystemswithlargescale.

Keywords:cooperative,heterogeneous,resourcesharing,untrustedenvironment,P2P,economicmodel,trustmodel

1.Introduction

Peer-to-Peer(P2P)computing—federatedsharingofdis-persedpoolsofgeographicallydistributedcomputingre-sourcesundercoordinatedcontrol—hasbeenconsideredasapromisingplatformforsolvinglarge-scaleproblemsinscienceandengineering.However,resourcemanagementintheseenvironmentsisacomplexundertaking.Thesesystemsneedeffectivemechanismforfairsharingofcommunityre-sources,adaptabilitytodynamicchangingconditions,preven-tionofdenial-of-service(DoS)attacks,andcoordinatonofthediversepolicies,costmodels,andvaryingloadsdifferentpeers.Asonemotivatingexample,aclassical“tragedyofthecommons”forpeer-to-peerfilesharingis50to70%ofpeersarefreeriders[1],whichresultsinagreatloadimbalanceofthesystems.Resourcetradingcanenforceacooperativeapproachfortheresourcesharingandispromisingtoaddresstheaboveproblems.

Theautonomous,heterogeneous,anddecentralizednatureofparticipatingpeersacrossmultipleadministrativedomainintroducestwochallengingissuesrelatedtoresourcetrading:decentralizedtradingscheme,whichmeansthedecisionofresourceexchangeandnegotiationisdeterminedbyeachpeerbasedonitspersonalizedviewofthepartneranditsownpol-icy;self-policingpersonalizedtrustworthinessmanagement,whichmeansdifferentpeersmayhavedifferentopinionsonthetrustworthinessofthesamepeer,insteadofuniqueglobaltrustworthinessvaluelikeeBay.

Inthispaper,weproposeanapproachthatconsistsoftwomodels:M-CUBE,aMultipleCUrrencyBasedEconomicmodel,asthedecentralizedtradingscheme,andPET,aPErsonalizedTrustModel,toprovidethetrustworthinessofthepeertosupportM-CUBE.TheM-CUBEmodelprovidesageneralandflexiblesubstratetosupportmostofhighlevelresourcemanagementservicesrequiredbytheP2Pcomput-ing,suchasresourcecoallocation,qualityofservice(QoS)control,advancereservationandschedulingalgorithms.PETderivesthetrustworthinessfromthereputationevaluationandriskevaluation.ThetrustworthinessvalueprovidedbyPETwillbetreatedastheviewofthepeerbyM-CUBE.Theuniquefeatureofourapproachisseamlessintegratingthetrustworthinessanddependabilityofpeersintotheresourcetrading.

Themajorcontributionsofthispaperinclude:(1)Wepro-poseaformaltrustmodel,includingthereputationevalua-tionandriskevaluation,forcalculatingthetrustworthinessofotherpeersinaself-policingway;(2)Weproposeamultiple-currencybasedeconomicmodel,whichseamlessintegratesthetrustworthinesstoprovideaself-policingmethodtoen-forcethecooperativesharingofheterogeneousP2Presources.Regardingtothepricingproblem,wepriceresourcesaccord-ingtotheirpricesintherealeconomicmarket.Bythismean,pricesofheterogeneousresourcesarecomparable,sothathet-erogeneousresourcesharingisfeasibleinM-CUBE;(3)Wedesignanefficientresourcetradingprotocolwhichhasthecapabilitytopreventmultiplerebelliousproblemsrelatedtoresourcesharing,suchasfreerider,boaster,andapplicationDoSattack;(4)Weevaluatetheefficacyandperformanceofthisapproachinthecontextofarealapplication,peer-to-peerWebserversharing.Ourresultsshowthatourapproachis

972flexibleenoughtoadapttodifferentsituationsandeffectivetomakethesystemprofitable,especiallyforthesystemwithlargescale.

Therestofthispaperisorganizedasfollows.Wepro-videanoverviewofourapproachinSection2.ThedetailsofthePETmodelisprovidedinSection3.Section4de-pictsthedesignoftheM-CUBEmodel.InSection5wedescribeanapplicationscenarioandgivethedetailedanal-ysiswithsimulationbasedonourapproach.Finally,relatedworkandconcludingremarksarelistedinSections6and7respectively.

2.Overview

TherearefiveproblemsrelatedtoresourcesharinginanopenP2Penvironment.

(1)Heterogeneity.Theheterogeneityofresourcesmakesthe

multiple-resourcesharingdifficult,becauseoflackingaformalmetricforthetradingamongdifferentresources;(2)Untrustedness.Enforcingacooperative,adaptive,and

anti-maliciousnessP2PsharingenvironmentontopofanuntrustedandprivateP2Pcommunityisreallyachallenge;(3)Selfishness.Thepossiblethreatslaunchedbyselfishpeers,

suchascheatingandboasting,candestroythecoopera-tiveresourcesharing.Enforcingafairresourcesharingframeworktolimitthenegativeeffectoftheselfishpeersisoneofthegoalsforourapproach;(4)Autonomyandcooperation.Peersusuallybelongtodif-ferentadministrativedomainswhichmayhavedifferentlocalpolicies.Effectiveandefficientintegrationoftheselocalpoliciesandgeneralresourcesharingisachallenge;(5)Incentives.Freeridersaretheconsiderablepopulationin

theP2Pcommunity.Toattractthepeertocontributetothecommunityisanoldbutstillongoingproblem.Inthispaper,weintendtoaddressalltheseproblems.Weconjecturethatthefundamentalsolutionfortheseprob-lemsisatrustworthinessmechanismforresourcetrading,asthedependabletradingtoworldeconomics.Basedonthismechanism,alotofhighlevelresourcemanagementrelatedservices,suchasservicelevelagreements,accesscostnegoti-ation,andadvancedreservationcanbeeasilybuilt.Therefore,themajorobjectiveofthispaperistobuildatrusteddepend-abletradingapproach,whichincludetwocomponents:theM-CUBEmodelandthePETmodel.

Asshowninfigure1,theM-CUBEmodelisaflexibleuniversalinfrastructureforbuildinghigh-levelresourceman-agementrelatedservices,andprovidesacomprehensiveso-lutiontoallchallengeslistedabove.TherearefourmajormodulesinM-CUBE:thePriceRegulatordecidesthepriceoftheresources;theRatioRegulatordeterminestheexchangeratioofthecurrencybasedonthetrustworthinessvaluepro-videdbythePETmodel;theServiceDiscoverymoduleisinchargeofdiscoveringtheavailableresourcesprovidedby

LIANGANDSHI

remotepeers;finallytheCurrencyExchangemoduleenablespeerstobargainuntiltheagreementofthecurrencyexchangeisreached,andthenmakestheexchange.PETunderpinsM-CUBEthroughprovidingtheaccuratetrustworthinessvalue.Trustworthinessisservice-specific.Onepeercanhavediffer-enttrustworthinessvaluecorrespondingtodifferentservicesintheeyesofotherpeers,soPETactuallyprovidesthe(trust-worthiness,service)pairforM-CUBE.PETmodelstherep-utation,andtreatstheriskastheopinionoftheshort-termbehaviorandmakesitbequantified.

Inthedesign,weassumetheuseofPublicKeyInfrastruc-ture(PKI)fornamingandauthenticationinbothM-CUBEandPET.BeforedescribingthePETandM-CUBEmodel,wegivethebasicassumptionsfirst:

(1)EachpeerhasarelativeuniqueandstableID.Thiswill

makereputationandtrustworthinessmakesense;(2)Coordinatedaccesstodiverseandgeographicallydis-tributedresourcesisvaluableforparticipatingpeers;(3)Eachpeerhasanassociatedpublic-privatekeypairto

makeitscurrencyunforgeable;

(4)Mostpeersinthesystemneedthecooperationsoasto

gainprofitablethroughsharingtheresources;(5)Eachpeerisselfish;

(6)Eachpeerhasapairofpublic/privatekeys.

3.PETdesign

PETistheunderpinningofoursystem,whichprovidesthetrustworthinesstotriggerM-CUBEtoevolve.InPETthetrustworthinessTisdirectlyderivedfromtwoparts:reputa-tionReandriskRi,asshownintheupperrightcorneroffigure2.WReandWRiaretheweightsofReandRirespec-tively.ForacompletenewpeerwithoutanyrelatedReandRiinformation,itstrustworthinessvalueissetas0.4,arela-tivelylowervalue.ActuallyTisrelatedtoonetypeofservice.Withoutspeciallypointingout,allvariablesinoneformulaisrelatedtothesameservice.ReputationReistheaccumula-tiveopinion,whichreflectsthequalityoftargetpeerwithinalongterm.PETmodelsthereputationthroughcombiningtherecommendation(Er,alsocalledreferralorsecondhandin-formation)andinteraction-derivedinformation(Ir,alsocalledfirst-handinformation).WErandWIraretheircorrespondingweights.Recommendationistheopinionsfromotherpeers,whichiscollectedbytheFeedbackCollectioncomponentinPET.Interaction-derivedinformationistheself-opinionfromthedirectinteraction.BasicallyIristheself-knowledge,soitisreliableandself-determined.Theinteraction-derivedinfor-mationisalsothebaseoftheriskcalculation.Riskistreatedastheopinionontheshort-termbehavior.AllvaluesofT,Re,Ri,Er,andIrarevaluesfrominterval[0,1].

ThereareawiderangeofresourcecategoriesinP2PresourcesharingsuchasCPU,harddisk,andsoon.Inthecontextofheterogeneousresourcesharing,anotherpro-gramcomponentresourceclassifyinginPETisemployedto

ENFORCINGCOOPERATIVERESOURCESHARINGINUNTRUSTEDP2PCOMPUTINGENVIRONMENTS973

Figure1.Overviewoftheproposedapproach,includingtwomodels:PETandM-CUBE.

Figure2.Derivationofthetrustworthinessvalue.

identifytheresourcecategorytowhichthefeedbackandself-observationinformationbelong,thenthiscomponentadoptsdifferentstrategiestoprocesstheseinformation.Inaddition,weabstractfourgeneralbehaviors,good,low-grade,nore-sponse,andByzantinebehaviorinP2Psystems.Peerswithgoodbehavior(G)providetheserviceasgoodasexpected;peerswithlow-grade(L)behaviorprovidescorrectservices,butwithsomedegradation,e.g.,delayHTTPresponse;no-response(N)behaviorisfromtheviewofrequesters—therequestercannotgetanyresponsefromtheserviceproviderwiththiskindofbehavior;finallypeerswithByzantine(B)behaviorgivethewrong,orevenmaliciousanswertotherequester.AllthreeL,N,andBservicesarebadservices,andhaveincreasingextentofharmfulnesstothesystem.1TosimulatethedynamicsinP2Penvironment,thedynamic(D)qualityisintroducedasanadditionalquality.PeerswiththisqualitychangesitsbehaviorsamongG,L,N,andBuni-formlyandrepeatedly.WeformalizethequalitysetasQ=G,L,N,B,D.Correspondingly,thepeersprovidingGservice

1Note

iscalledG-peer,sodoL-peer,N-peer,B-peer,andD-peer.Thiscoarse-grainclassificationisflexibleenoughtoapplytoanyresourcesharing,andmoresubclassescanbeintroducedifnecessary.

Fromfigure2itcanbeenseenthatWRe=αandWRi=1−α.Whenα=1,whichmeanstheweightoftheriskis0,PETdegradestothetraditionalreputationmodelthatjustconsidersthepeer’shistoryonly.Howeveroursimulationresultsshowthatriskevaluationisaveryhelpfulcomponenttobuildthetrustmodel.Normallywhenthesystemishighlydynamicandmostnodesarenotgood,itisrecommendedtosettheriskwithahighweight(e.g.0.7),whichissupportedbythesimulationresultsinSection5.Fortheblindusers(i.e.,userswhodonotknowhowtotunetheparametersoftheunderlyingtrustmodel),α=0.3isthesaferecommendedvalue.IntegratingwithriskevaluationdistinguishesPETfromthepreviouswork[7,13,17,19].

Reputationmodel.Inthefollowing,wecallthepeertoevalu-ateotherpeersavaluer,thepeertobeevaluatedavaluee,andthepeersendingouttherecommendationtherecommender.Forexample,whenpeerAtellspeerCthetrustworthinessvalueofpeerB,AwillbethevaluerofB,andtherecom-menderofCaboutB.Correspondingly,BisthevalueeofA.

thatinourclassification,“noresponsefromtheserviceprovider”isaspecialbehavior.Wetreatthiskindofbehaviorasabadbehavior,nomatteritisbecauseofsubjectivefactor,e.g.,rejectingtheservicerequestintentionally,orobjectivefactor,e.g.,thephysicallinkgetsbroken.

974Reputationvalueisthehistoricalaccumulationforvaluee’spastbehaviorfromthevaluer’sviewpoint.Sometimessomegoodpeerswillmisbehavefornonsubjectivefactors,forex-ample,thegoodpeerrejectsthenetworkservicerequestsforthebreakdownofthephysicallink,butafterrecovery,itwillprovidegoodservicecontinually.Ifwantingtoforgivetheoc-casionalnonsubjectivemisbehavior,wecansetahighvaluetoα(e.g.,α>0.5forexample)tomakethetrustworthinesspreferringtothereputationvalue.ReputationisderivedErandIr.HereWEr=βandWIr=1−β.󰀰

from(Te)standsforthesumoftherecommendations,andNeistheamountoftherecommendations.SoEristheaveragevalueofrecommenda-tions.Irisderivedfromthepeer’saccumulativescore.Aftereachtransaction,therequesterevaluatesthequalityofthecooperation.ThepeersprovidingGservicewillleadtotheirscores(S)increase,whilepeersprovidingL,N,orBservicewillcausetheirscorestodecease.FortheD-peer,itchangesitsbehaviorsamongG,L,N,andBrepeatedlyanduniformly,so75%ofthebehaviorofD-peerisbad,anditsscoreactu-allyalsodecreasegradually.ForthevaluerthereisascorefunctionhmappingfromQtoascoreforonecooperation.Asshowninfunctionhinfigure2,thebadbehaviors(L,N,B)willleadtomoredecreaseofthescorethantheincreaseforthegoodbehavior,andtheBisthemostharmfulactionwhichcausethemostseveredecrease.Inthesimulation,hisdefinedas:h(G)=1,h(L)=−2,h(N)=−3,andh(B)=−4.ThesumofscoreisnormalizedbyathresholdvalueTgoodtoderiveIr.

SincePETaimstodeployintheP2Pcommunity,inwhichtherearemaliciousrecommendersprovidingthemisleadingrecommendations,itisgoodtolowertheroleoftherecom-mendation.Thereasonsare:

(1)Differentpeersarehardlyconsistentonthesameservice

providerbecauseoftheirdifferentcriteriaandexperi-ences.(2)Peer’sbehaviorcanchangedynamically,whilerecom-mendersneedtimetoperceivethischange,andtherearedelaysfortherecommendationtospread,sorecommen-dationssomehowinevitablydeparturefromthetruth.(3)Fraudulentrecommendation,especiallythecollusionon

therecommendationisverydifficulttohandleifthetrust-worthinesscalculationreliesmuchontherecommenda-tion.However,itisnotagoodanswertoignoretherecommen-dation.Astheknowledgefromotherpeers,therecommenda-tionishelpfultoknowmoreaboutthesystemwithoutdirectinteraction.Assigningitalowerweightβisagoodsolution,whichissupportedbythesimulationresultsinSection5.Moredetailedanalysisoftheeffectofrecommendationscanbefoundin[15].

Riskmodel.Reputationisnotsensitiveenoughtoperceivethesuddenlyspoilingpeerbecauseitneedstimetodecreasetheaccumulativescore.Riskevaluationcanhelptosolvethisproblem.Trustworthinessisatemporalvalue,becausethebehaviorofthepeerwillchangedynamically.Theoldtrust-

LIANGANDSHI

worthinessvaluemaytotallymisrateonepeeraftersometimepasses.Tosolvethisproblem,ariskwindowisemployedtolimittheassessingrange.Whilethewindowisshiftingfor-ward,theriskvaluereflectsthefreshstatisticsofthevaluee’srecentbehaviors,whichintegratesthetemporalfactorsintothetrustworthinessvalue.TocalculatetheriskRi,wefirstgetthetotalscoreofthebadservicewithinthewindow,thenmakeitnormalizedwiththeproductofh(B)andthewindowsizeSworN.Nisthenumberoftotalhistoryeventsinthequeue.NormallySwandNareequal,exceptthatatthebe-ginning,thequeueisnotfull.Whenthereisnointeractionatthebeginning,theriskvalueissettobezero,thatis,noriskforthenewstranger.ItseemsthatthisstrategyopensadoorforthenewstrangerandbringscorrespondingthreatssuchasSybilattack[8],butactuallynot.Onceapeerbehavesbadly,theriskwillincreasesignificantly,sothatthedoorwillcloseveryfastforthebadpeers,whichwillbevalidatedintheSection5.3.Toreducetheriskofthecooperation,userscanfocusmoreontheriskbyassigning1–Riahighweightbytradingofftheresourceavailability.

4.M-CUBEmodeldesign

M-CUBEmakesuseofthe(trustworthiness,service)pairpro-videdbyPETtochangetheviewonthequalityofothers,thenadjuststhecorrespondingpoliciestocontrolthecurrency.Inthissection,wefirstgiveabriefintroductionabouttheworldeconomicmodel,whichinspiresthedesignofM-CUBE,thenpresentthedetailsoftheM-CUBEmodel.Finally,theadvan-tagesofthismodelarediscussed.4.1.Currencymodel

Inspiredbythefeaturesoftheworldeconomicmodel,wepro-posetheM-CUBEmodel,whichisamultiple-currencybased,self-policing,dependableandunifiedmethodforheteroge-neousresourcesharing;however,ourapproachdiffersfromtherealeconomicmarketinthegrainofeconomicentity.Thatisinourcurrencymodel,everypeer,namelyonemachineoroneorganization,issuesandregulatesitsowncurrency,whileintherealworldeconomicmarket,eachcountry(notasingleperson)isthesmallestentitytocontroltheitscurrencyissuingandexchange.M-CUBEisbuiltuponcurrency-basedmecha-nisms,wheretheuniquenessofM-CUBEiseachpeerhasitsowncurrency.Unlikemanyofpreviouswork,inadditiontoassociatingthecurrencywithphysicalresourcesdirectly,suchasCPUanddisk,M-CUBEalsocanassociatecurrencywithapplication-levelservicesdirectly,e.g.,eachHTTPrequest.Pricingandratio.InM-CUBE,pricingisthefirstproblemtobeaddressedbeforebuildingthecurrencymodel.Sincemostcomputerusersliveinthemarket-economysociety,itisreasonableandacceptabletopriceourresourcesinthevirtualcommunityreferringtotherealpriceofthephysicaldevices.Ontheotherhand,thesharedresourceshavetheirownperiodofvalidity.Sofromtheviewoftrading,thecurrencyinthe

ENFORCINGCOOPERATIVERESOURCESHARINGINUNTRUSTEDP2PCOMPUTINGENVIRONMENTS975

M-CUBEismainlyexpressedasa3-tuple:(t,p,v),wheretisthetypeoftheresource,pisthenumberofthistyperesourcewhich$1canbuyintherealeconomicalsociety,andvisthevalidityperiodoftheresource.Inthefollowingsubsection,moredetailsabouttheformatofthecurrencyaredescribed.However,regardingtotheapplication-levelservicenotonlyrelatedtoasingledevice,forexample,onecalculationrequestinSETI@Home,itneedstoconsidermultipledevicesrelatedtothisservicetofixp.Normallythepricingnormallyisself-decided,butitalsouses$1asthebasicunittodefinep.Forexample,if$1isdecidedtobeabletobuy10requests,thenthevalueofpisequalto10.

Basedonthevalueofp,heterogeneousresourcetradingisfeasible.Hereisanexample.PeerAwantstoshareits100Gharddrive,andpeerBwantstoshareits2GHzCPU.AssumeintherealmarketA’sharddrivecost$100,andB’sCPUcost$80.ThenthevalueofpinA’scurrencyis1(unitisGB),andB’sis25(unitisMHz).2Ignoringtheconsiderationofthevalidityperiod,oneunitofcurrencyofA(CA)isexpectedtogetoneunitofcurrencyofB(CB)becauseonecurrencyiscorrespondingto$1.Inthiscase,oneCAcanbeusedtoexchangefor25MHzCPUresourcefrompeerB,oroneCBcanbeusedtoexchangefor1GharddiskfrompeerA.Twoadvantagescanbeexpectedwiththisapproach:

(1)Peoplearewillingtoacceptthisapproachbecauseitis

similartotheirdairylife;

(2)Baseonthisapproach,heterogenousresourcescanbe

easilyexchanged,becauseallcurrenciesareintroducedbasedon$1valueintherealeconomicmarket.Inordertosimplifythesystemdesign,apricingbootstrappeerwillbeintroducedinoursystem.Thebootstrappeeristakingcareofoneadditionaltasktoupdatethedeviceprice.Otherpeersinthesystemcontactthebootstrappeertogetthereferenceprice.Howeverthereferencepriceisnotmandatory;otherpeerscanpricetheirresourcesbasedontheirownexperience,disregardforthepricefromthebootstrappeer.Sothebootstrappeerisnotnecessaryinthesystem.Thereferencepricealsocanbereferredtoseewhetherthepricefromthecounterpartpeerbetweentheresourceexchangeisreasonableornot.ThemodulePriceRegulatorisemployedtomanagetheprice,whosejobiseithertocontactthepricebootstrappeerperiodicallyorself-decidethepriceaccordingtosomepricingmechanism.Alotofpreviousworkhasbeendoneonthepricing[10–12],whichcomplementstoourworkandcanbeusedforpricinginM-CUBE.

Currencyformatandmanagement.Whentwopeerex-changetheircurrencies,thereisanexchangeratioRcthattheyagreewith.Initially,sinceeverycurrencyiscorrespond-ingto$1,soRcisequaltoone.Aftersometime,Rcwillbeself-adjustedaccordingtothetrustworthinessvalueprovidedbyPET,whichisdefinedbyafunctionf:Rc=f(T,Rc).Asimpledefinitonoff,Rc=T,isadoptedinourfollowing

225MHzCPUis1of2GHzCPU.Fromtheapplicationview,itrepresents

18080CPUusage.

sections.Thatis,justusethetrustworthinessastheexchangeratio.Forexample,ifforpeerB,peerA’strustworthinessvalueis0.5,thenoneunitofA’scurrencycanjustexchangefor0.5unitofB’scurrencywhenAasksforB’scurrency.RcisregulatedbythemoduleRatioRegulatorinfigure1.WhenP1wantsP2’sservice,itmustuseP2’scurrency.ButP1musthaveitsowncurrencyfirstwhichitcanusetoexchangewithP2.OnceP1issuesitsowncurrencies,itpromisestosharethecorrespondingresourcesthosecurrenciesstandingfor.Soifonedoesn’tcontributeanyresourcetothecommunity,ithasnocurrencyforexchangesothatitwon’tgetanyservicesfromothers.TheincentivebroughtbyM-CUBEtothere-sourcesharingis:themorethecontributionapeerprovides,themoreservicesitcangetfromothers;thepeerwillgetmorebenefitsthanitsactualcontributionbecausesometimesresourcesfromotherscanhelpthepeertopullthroughthedifficultperiodsuchasoverloadedtime,whicharedefinitelymorevaluablethanthesharinginthecommonsituation.How-ever,issuingmorecurrenciesthanone’scapacityblindlyisnotagoodwayeither.Thisiswhatwecalltheboaster.Theto-talnumberofcurrenciesstandsforthepeer’soutwardservicecapacity.Theboastermayincurtrustworthinesslossbecauseitwillbeunabletoservethelegalrequestswhenmostofitscurrencyholdersaskfortheservicesatthesametime.So,thepeersmustissuethecurrencyaccordingtoitsactualservicecapacity.Onepeerwillprovideitsserviceonlywhenitre-ceivesitsowncurrencyanditmustdosoinordertomaintainitsreputationinthecommunity.Theformatofthecurrencyisshowninfigure3(a).TypeVecstandsfortypevector,tospec-ifywhichresourcethiscurrencyrelatedwith.Itshouldbemadeclearthat,thoughP1’scurrenciescanrelatetodifferentresources,theyareallP1’scurrencies.Whenwetalkaboutmultiple-currency,wearefromtheviewofdifferentpeers,notdifferentresources.Whenapeergeneratesanewcurrency,itwillfillinthisfieldtomakethecurrencytobeusedonlyforthespecifiedresource.Becausetheresourcesarelimited,thenumberofcurrenciescorrespondingtooneresourceisalsolimited.InM-CUBE,everyissuermusttakecareofthecurrencyissuingitselftoavoidtobeaboaster.ResNumisthenumberofcorrespondingresourceswhichthiscurrencycanbuy.ValiTimestandsforthevalidationtime(Time-to-Live)oftheresourcethecontributorguarantees.BasedonValiTime,thereceiverofthecurrencywillknowwhentheserviceisavailableontheissuerside.Thevalidityperiodpmentionedinaboveparagraphcanbeachievedbysubtract-ingcurrenttimefromtheValiTime.LiveTimespecifiesthevalidatetimeintervalofcurrency.IfaftertheexchangethecurrencyisnotusedwithinLiveTime,thecurrencywillex-pired,andtheissuerwillre-issuethecurrencywithanotherLiveTime.DifferentwithValiTime,LiveTimeisfromtheangleofcurrency,nottheresource.NormallyLiveTimeislessthanValiTime.IssuedTimeisthetimestampindicatingissuetimeofthecurrency.Whenanissuerreceivesitscurrency,itwillcheckifthecurrencyisvalidbycomparingtheIssuedTime+LiveTimetotheitscurrenttime,butthislimitationisnotstrictbecausethetimeisnotstrictlysynchronizedinthedistributedsystem.Throughthisway,theserviceconsumersignsa

976usagecontractwiththeserviceproviderandtakesonthedutyfortheexpirationoftheprovider’scurrencies.SeqNumisthesequencenumberofthecurrency,whichisusedfordecidingtheauthenticityofthecurrencybytheissuer.Finally,DigSigisthedigitalsignaturesignedbytheissuer.Theissuerusesthenode’sprivatekeyK−toencrypttheTypeVec,ResNum,ValiTime,LiveTime,IssuedTime,SeqNumtogeneratedigitalsignatureDigSig.Thecurrencyistotallyself-determinedandself-policing.ItmeetsthedemandofhighindependenceoftheP2Pcommunity.Inordertodecreasethespaceconsumingforthecurrencystorage,everyissuerkeepsatabletotrackwhereitscurrenciesintermsof(TypeVec,Resnum,SeqNum,Receiver),sothatcurrencyreceivercanmergethecurrencywiththesameTypeVecandissuer,justbyrequestinganewlarge-amountcurrencyfromtheissuer.Theissuerjustneedstodeletethecorrespondingsmall-amountcurrencies,andaddanewtrackingitemwithnewResnumandSeqNum.Thesimi-larprocesshappensintheprocessofcurrencyconsuming,butthedirectionischangethelarge-amountcurrencytosmall-amountcurrency.AllthecommunicationchannelsaresecureandauthenticatedwiththehelpofPKI.

Servicediscoveryprotocol.Beforeonepeerexchangescur-rencywithanother,itmustknowwhohasthecurrencyrelatedtotheresourceitwants,whichistakencarebyServiceDis-coverymoduleinfigure1.Twofunctionalitiesthemoduleperforms:

(1)Locatingthewantedcurrency,

(2)Makingsurethevalidityperiodofthewantedcurrencyis

longenough.InM-CUBE,limited-hopmulticastisusedherefortheser-vicediscovery.Therequestersendsoutarequest(Cnum,Ctype,R,V)toitscooperators(cooperatorsrefertothepeershavingthehistoryofcurrencyexchangebefore),whereCnumisthecurrencynumberitwants,Ctypeistheresourcetypetowhichthewantedcurrencyrelated,Ristheidentifieroftherequester,andVistheminimumvalidityperiodfortherequestresource.Thecooperatorswillforwardtherequesttotheircooperatorsagain.Accordingtothesocialnetworkphenomenon,itisex-pectedthatafterseveralhopsthewantedcurrencycanbedis-covered.InM-CUBEthemaximumnumberofhopsissetassix.Allthereceiverspiggybacktheresponsetotherequesterpeer.Ifallthefollowingtwoconditionsaremet,thatis,(1)Thecurrencyassociatedwiththerequestedresourceis

available,

(2)Thevalidityperiodislongenough,

thereceiverwillconfirmtherequesterpeer,andtelltherequesterpeerwhatkindofcurrencythereceiverneedsiftherequesterpeerwantstoproceedtheexchange.Oneimportantthingis,delegationpeerisallowedinM-CUBEtoimprovetheefficiencyoftheresourcesharing.Peersarenotlimitedtojustexchangewiththeissuerdirectly.Inotherwords,ifpeerAhaspeerB’scurrency,andpeerCwantspeerB’scurrency,peerCcanexchangepeerB’scurrencywithpeerA.WecallAanexchangedelegation.This

LIANGANDSHI

willimprovetheresourceavailabilityandefficiency.Con-sideringthecasethatwhenpeerBandpeerCdoesnotknoweachother,sopeerBandpeerCcannotbuildthecooperationrelationship.ButpeerCneedspeerB’sservice.Withouttheexchangedelegation,Cwon’tgetB’shelp,andB’sresourcescannotbeknownbyC.Therequesterpicksupsomepeersandbuildsthecandidatelistaccordingtothetrustworthinessofthepeerwhoissuesthewantedcurrency(notthepeerperformingtheexchange.Remembertherearedelegationshere,andthetrustworthinessjustcaresabouttheserviceprovider,notthecurrencyexchanger).Thenonepeerfromthecandidatelistischosentoproceedthecurrencyexchange.Ifthecurrencyexchangecannotbefulfilled,e.g.,theexchangeratioisveryhighfortherequester,sothatitdoesn’twanttocontinueexchanging,anotherpeerfromthelistischosentocontinuetheexchange.Whentherequesterdoesn’thavetherightcurrencyastheresponderneeds,itmusttrytogetthecurrencytheresponderwantsfirst.Inaworsecase,therequestermayhavetogetseveralintermediatecurrenciestofinallygetthewantedcurrency.Inthiscase,theexchangechainshapesup,asshownintheleftpartoffigure3(b).TheintermediatenodesintheexchangechainarethedelegationsA,B,andC.TwoendpointsofthechainareissuerPandtherequesterR.NowRwantsP’scurrency.Aftermulticast,RknowsthatpeerAhasP’scurrency.Inthisscenario,AisthedelegationofP.ButAjustacceptsthecurrencyofpeerB,whichRdoesn’thave.ThenRusesanothermulticasttofindoutwhohasB’scurrency,andBresponsesandtellsRitjustacceptsC’scurrency.Fortunately,CacceptsR’scurrency(throughanothermulticasttofindwhohasC’scurrency).NowRcanbuildanexchangechanneltoAthroughthechainR⇒C⇒B⇒A.Toimprovetheperformance,theexchangeactivitywon’thappenuntiltherequesteragreeswithallratiosfromthedelegationsinthechain.SoRrecordstheratioreportedfromA,B,andCfirst.IfRagreeswithalltheratios,theexchangechainforms:RwilltriggerthechainexchangebyexchangingwithCfirst,andthenusesC’scurrenciestoexchangewithB,andtheprocessgoesonuntilitgetsP’scurrencyfromA.Onedetailis,whenAgetsR’sexchangerequestfinally,AwillinquiryPtheratiosRP:R(ThecurrencyratioforRinP)first.ArejectstheexchangeincaseRP:Rislow,thatisR’strustworthinessinPislow(rememberR=T).IfRhasagoodreputation,AgivesRP’scurrencywithratioRP:A∗RA:B.ActuallyfinallyNunitsofR’scurrenciescanexchangeforRP:A∗RA:B∗RB:C∗RC:R∗NunitsofP’scurrencies.Currencyexchangeprotocol.Atthebeginning,onepeeronlyhasitsowncurrency.Itneedstoexchangethecurrencyfromotherpeerswhenitneedstheservicesfromothers.ThemoduleCurrencyExchangeinfigure1takescareofthisjob.Aftertheservicediscoverystagementionedinpreviouspara-graph,therequesteralreadyhasthecandidatelist,andonecandidatepeerhasbeenchosen.Inthefollowing,wewilljuststateabasicexchangeprotocolwithoutconsideringthechainexchange(actuallythechainexchangeisjustalittlebitdifferent.Whattobemodifiedistocombinetheexchangeinthechaintogether).Therequestersendsitsexchangerequest

ENFORCINGCOOPERATIVERESOURCESHARINGINUNTRUSTEDP2PCOMPUTINGENVIRONMENTS977

Figure3.Currencyformatandcurrencyexchangeprotocol.(a)Currencyformat,(b)Servicediscoveryandcurrencyexchangeprotocol.

tothecandidate,andthecandidatedecidestheexchangeamountbasedontheexchangeratio.Thepseudocodeoftheexchangeprotocolisshowninthemiddleofthefigure3(b).WeassumethatP1wantstogetNCP2(T1)(thecurrencywithservicetypeT1fromP2),andthecurrenciesofP1arerelatedtototalnkindsofresources.Herewealsodon’tconsiderthecaseofdelegation,andassumethatallcurrenciesofP1usedtoexchangeareissuedbyP1itself.Atfirst,P1willusethecurrencyCP1(T1)toaskforexchange.Ifthiskindofcurrencyisnotenough,itcanuseotherkindsofcurrenciestocon-tinuetheexchangeuntilitsrequestissatisfiedornomorekindsofcurrenciescanbeusedfortheexchange.SUBEX-CHANGEfunctionoperatesasshownintherightpartofthefigure3(b),whichillustratestheexchangeprocessforjustonekindofcurrency.P1inquiriesP2ifpossibletoexchangethecurrencywithtypeT1fromP2usingtheP1’scurrencywithtypeTi.IfP2canconducttheexchange,itsendsbacktheexchange-relatedinformationtoP1,whichincludesLc,Me,andR2:1.LcmeansP1’screditlimitinP2,whichisthetotalmaximumnumberofcurrenciesP1canaskfromP2.MeisthemaximumnumberofthecurrencyP1canaskfromP2inthisexchange.R2:1meansthecurrencyexchangeratioforCP2toCP1.Theprotocolistotallyself-policingandnego-tiable.P1canrejecttheexchangeforthelowexchangeratiospecifiedbyP2.IfP1agreestheratio,P1willsendP2itsN󰀐currenciesCP1(T1),andP2willsendbackN󰀐∗R2:1currenciesCP2(T1)toP1.HereN󰀐maybenotequaltoNafternegotia-tion.Whentheexchangeprocedurecompletes,bothP1andP2willchangetheircurrencystorage.Sincethecurrencyex-changetendstoattractmoreattacks,somespecialsecurityprotocols,e.g.Diffie-Hellmankeyexchangeprotocol,canbeusedheretoprotecttheexchange.4.2.Advantagesofthemodel

Benefitingfromthenatureofthecurrencymechanism,wecanmaketheresourcesharingcontrollable,eliminatethefree-riderandboaster,andmakethesystemanti-DoSwithourM-CUBEmodel.

Makingresourcesharingcontrollable.InM-CUBE,there-sourcesharingandtradingareundercontrolfromtheprospec-tivesofthenumberandtime,whichisimportantfortheopenP2Pcommunity.Throughtheusageofthecurrency,everypeeriscoupledwiththesystemnotonlyusingthesystem,butalsomanagingthesystembydiscoveringandpropagatingthebadpeersthroughtheratioadjustment.Thecontrollabil-ityalsoprovidesmorebenefitsoftheresourcesharingwithmorereliabilityandpredictability,whichisapotentialwaytoputP2Presourcesharingtoagooddirectionagainstthelawviolation.Everypeerhasincentivestokeepgoodreputa-tion,sothattheyalsotaketheresponsibilitytomaintainthereliabilityoftheirresourcesclaimedintheircurrencies.Thepredictabilityletpeersknowwhentheycanfindtheavailableresourcesothattheycandealwithemergencyoracomplextaskwiththeadditionalresourcefromothers.

Eliminatingfree-rider.Free-rider[1]isasevereprobleminP2Pcommunity.IntheM-CUBEmodel,nofree-ridercanexistbecausenoneofthemcangetother’scurrencywithoutexchangeitscurrencywithother.Whenone’scurrenciesareholdbyotherpeers,itwillhavetoprovidetheservicewhen-everotherpeersredeemthecurrency,otherwiseitscreditwillbedecreasedandfinallyitwillbekickedoutfromthecommunity.

DoSattackfree.Sinceeverylaw-abidingpeergeneratesitscurrencybasedonitsservicecapacity,soevenfacingtheburstoftheservicerequestsfromothers,thepeerisstillcansatisfytherequestsatthesametime.Thatis,ourcurrencymodelcanavoidtheDoSattackforthelaw-abidingpeer.Howeverfortheboaster,itisoutoftheprotectionofourmodel.ItisworthnotingthatwhenwesayDoSattackfreehere,werefertothepossibleattackresultingfromourcurrencymodelandlocatingintheapplication-level.Thenetwork-layerattacksuchastheTCP/IPSYNattackisnotourmajorconcern.Anti-boasterandinflation.In[9],boastersareconsideredaslegalanduseful.HoweverinM-CUBE,boasterareillegalbecausetheywillleadtotheuncontrollablestateofthesystem.Intherealeconomicmarket,ifthevalueoftotalcurrencies

978LIANGANDSHI

islargerthantheactualvalueofthetotalmerchandize,itwillleadtotheinflationanddisorderthemarkettrading.However,ourcurrencymechanismhasanaturalessencetosuppresstheinflation.Theboastermaybeabletoexchangeforthecurrenciesofotherpeersatfirstwithitsdevaluatedcurrencies,butthestealingactionwillbepunishedbythecommunityinthelongrun.Otherpeersholdingtheboaster’scurrencywillredeemthecurrencytoaskbackfortheservicelater.Whentheboastercannotprovideservicewithgoodqualityfacingtheburstoftheservicerequests,itstrustworthinessvaluewillbedecreased.Finally,whenthetrustworthinessdropstobelowathreshold,theboasterwillbeeliminatedfromthecommunity.SimulationresultsinSection5showthatevenmostofbadpeersinthesystemareboasters,ourapproachisstillcanmakethesystemprofitable.5.Experimentalanalysis

ThesimulationisconductedinthecontextofP2PWebserversharingapplication[18],whichisanewcontentdeliverymechanismforbothstaticanddynamicWebcontentbyfederatingparticipatingWebserverstogetherinaP2Pfashion.Itempowerstheindividualpeerwhichisautonomouswithrespecttomanagingtheresourcesandreplicaplacement.EachWebserverisapeerandservesabunchofclients.Thepeerspooltheirresourcestohelpeachotherduringindividualpeer’speakloadsand/orsystemfailures.ThemainconceptbehindtheworkabilityofthisarrangementisanunderstandingthatnotallcompanieswhichformtheP2Pnetworkwillhavepeakloadsontheirwebsitessimultaneously.PETwillbeintegratedwiththeproposedM-CUBEmodelfortheapplicationinthesimulation.Thesimulationisthread-basedandwritteninPerllan-guage.Table1givesthedetailsofthesettingsofthesimu-lation.Thereare500peerserverstobesimulated.Toshowthescalabilityofthemodel,twosizesofclientsareused:4,700clients(C1)and9,400clients(C2).Thepeerserversneedtocooperatewitheachothertomakefulluseofthespare(computing)resourcetoservetheclients.HTTPre-questsfromclientsaregeneratedusingSURGE[3].Thetotalnumberofrequestsinthesimulationisabout300,000whenusing4,700clients,and600,000whenusing9,400clients.Fiveconfigurations(fromP1-P5)areusedtosimulatediffer-entP2PcommunitiesaslistedinTable1.Inordertosimulatethemaliciousrecommenders,peerswillalsohaveasecondaryrole:sendingoutthecorrectrecommendation(M1)ormali-ciousrecommendation(M2).Inoursimulation,themaliciousrecommendationwillratethegoodpeersasbad,andbadpeersasgood.TheB-peerswillsendoutthemaliciousrecommen-dationswhenoptionM2ischosen.Finally,inordertosimulatetheworseuntrustedenvironment,wealsointroducetheroleBoasterintothesimulation.Changingtheweightsofdifferentmodelcomponentscanadjustthemodeltodifferentenviron-ments.Findingsomegoodweightsettingsthroughthesimula-tionisoneofourgoalsaswell.Toachievethisgoal,sixweightcombinations(fromW1-W6)areusedasshowninTable1.Inthefollowinganalysis,wewillmainlycomparetheper-centageofthegoodservicebroughtbythesystemtoanalyzetheeffectofdifferentcomponentsandtheimprovementorourapproachindifferentkindsofenvironments.Forallfiguresexceptfigure6,thex-axisisthefourservicecategories(G,L,N,B),andthey-axisisthepercentageoftherequestsreceivingthecorrespondingservicecategory.Infigure6therelationshipbetweenPETandM-CUBEareexplored.Duetospacelimit,

Table1

Simulationsettingsandtheirillustrations.

SettingsClientnumber

C1C2P1P2P3P4P5

Maliciousrecommendation

M1M2W1W2W3W4W5W6

4700Clients9400Clients

20%:10%:10%:30%:30%20%:0%:0%:0%:80%20%:20%:20%:40%:0%50%:10%:20%:10%:10%80%:5%:5%:5%:5%MaliciousrecommendationCorrectrecommendationα=0.3,β=0.2α=0.3,β=0.5α=0.7,β=0α=0.7,β=0.2α=0.7,β=0.5α=1,β=0.2

Illustrations

Small-sizepopulation.Large-scalepopulation.

Tosimulatethecommunitywithlessgoodpeersandallkindsofpeerscoexist.Tosimulatehighdynamiccommunitywithmanydynamicpeers.Tosimulatethestablecommunitywithoutdynamicpeers.

Tosimulateahalf-goodcommunity.Tosimulateaterrificcommunity.Spreadingthedistortedfacts.Spreadingthetruefacts.EmphasizingRiandIr.

EmphasizingRiandrelyingmoreonEr.EmphasizingReandignoringEr.EmphasizingReandIr.EmphasizingReandIr.

IgnoringRiandEmphasizingIr.

Theproportionofpeerwithdifferentquality(G:L:N:B:D)

Weightofdifferentcomponents

ENFORCINGCOOPERATIVERESOURCESHARINGINUNTRUSTEDP2PCOMPUTINGENVIRONMENTS979

wereporttheresultsofonlyonemetric.Interestedreaderspleaserefertothetechnicalreportversionofthispaper[14].5.1.Effectofdifferentcomponents

Inthispart,twointerestingissueswillbestudied.Wefirstfocusontheriskevaluationwithdifferentweights,thenturntotheeffectsofrecommendationswithdifferentweightsandpeerconstructions

(1)Riskevaluationwithdifferentweights.Infigure4(a),we

fixotheroptionsandjustchangeWRi.ThreevaluesofWRiareusedhere:W1(0.7),W4(0.3),andW6(0).Otherfixedoptionsare:C1,M2,andP1,thatisasystemwithonly20%goodpeers,butpeerssendoutthecorrectrecom-mendations.Intuitively,whentherearelargenumberofbadpeers(L,N,B,D),highvalueofWRiishelpfultofindthebadpeers.Infigure4(a),itcanbeobservedthat,withtheincreaseoftheweightWRi(W6(0)→W4(0.3)→W1(0.7)),themoregoodservicesthesystemachieves.Howeverthedifferenceisnotthatmuch.Itisbecausewechooseasmallnumberclients(C1)inthisexperiments.Fromtheanalysisofthelasttwoexperiments,wecanexpectthat,thedifferencewillbeenlargedifweselectlargernumberofclients(C2).Fromthisanalysis,ahintcomesout:intheP2Pcommunitywheremostpeersarenotgood,thehighvalueofWRiishelpfultoimprovethemodel.Aninterestingtopicwewillstudyinfigure4(b)istheabilityoftheriskmodelagainstthemaliciousrec-ommendation.WechoosetwoweightsoftheriskWRi,W1(0.7)andW4(0.3),andtakethemaliciousrecommen-dationintotheconsideration.Theotherfixedoptionsisthesamewithfigure4(a).Fromthefigure,wecanseethattheoptions(M1,W1)brings36%goodservices,muchbetterthan31%withtheoptions(M1,W4),anditisevenbetterthan35%withoptions(M2,W4),thecasewith-outmaliciousrecommendations.Fromthesedata,anotherhintcomesout:whenthemaliciousrecommendationsex-ist,settingWRiwithahighvalueisgreathelpfultoresistthemaliciousrecommendation.

(2)Selectingtheweightofrecommendation.Toselectasuit-ableweightofrecommendationisimportantforPET.Weconductthisgroupexperimentstotrytoknowhowtose-lecttheweightoftherecommendationWErtodecreasethenegativeeffectsofthemaliciousrecommendationwhilekeepingthesameperformance.WewillmixM1(Mali-ciousrecommendation)andM2(Correctrecommenda-tion),P1(20%G-peersand30%D-peers)andP2(20%G-peersand80%D-peers),andW3(WEris0),W4(WEris0.2)andW5(WEris0.5)tobuilddifferentexperiments.OtherfixedoptionincludeC1.

Let’sfocusonthelineswithM1optioninthefollowingdiscussion.Infigure4(c),withtheoptionW4,amongalltherequests,36%areservedwithgoodservice,higherthan32%fromthecasewiththeoptionW3(ignoretherecommendation).Theresultisevenalittlebithigherthanthecasewithoutmaliciousrecommendations,which

impliesthatalowervalueofWErisbettertoresistthema-liciousrecommendationsanddiscovertheG-peersthanbothignoringtherecommendation(W1)andrelyingmoreontherecommendation(W5).Fromtheaboveresults,wecanconcludethatinacommunitywithmaliciousrecom-menders,justignoringothers’recommendationsisnotagoodway.Therightsolutionisassigningitalowweighttomakeatradeoff.Fromthesimulationresults,thetradeoffcanleadtoagoodsolution.

5.2.Improvementofourapproach

Inthefollowing,wewillstudytheimprovementofourapproachthroughthreeanglesofefficacy,anti-boaster,andscalability.

Setup:TheservicerequestsofclientsaregeneratedbySURGE,whicharestoredinonefile.Therearesomeotherfilesusedtospecifythequalityofthepeerservers.Combiningthesefiles,wecangettheresultsofhowtherequestswillbeservedwithoutourapproach(wecallitthestandardresult).SincetheD-peerchangesitsqualityrepeatedlyanduniformly,weamortizeitsservicetootherfourserviceswhencalculatethestandardresult,soactuallynoDserviceexists.Inthisexperimentgroup,G:L:N:B:Dis20%:10%:10%:30%:30%.Soaftertheamortization,G:L:N:Bwillbe27.5%:17.5%:17.5%:37.5%(eachadd30%/4=7.5%).WewillusethisastheexpectedstandardresultwithoutM-CUBE,andseetheimprovementandefficacycomparetheresultswithM-CUBE.Toseetheeffectsoftheboaster,twogroupsofexperimentsareconducted:oneiswithouttheboasterandtheotherwiththeboaster.Inadditiontotheboaster,inthesecondgroupofexperimentswealsoletthebadpeersactmoreintelligently,i.e.,thebadpeersareabletochangethecoop-eratorswhichhaverecognizedtheirbadquality,andattempttofindnewcooperators,throughwhichtogainmorebenefitsfromthenewcooperators.Ourgoalistosimulateahighlyuntrustedenvironmenttotesttheeffectofourapproach.Inordertostudythescalability,twogroupsofexperimentsareconductedalso:thefirstE1iswithdifferentnumberofclients,andthesecondE2iswithdifferentnumberofpeerservers.E1studiestheeffectwhenthesystemoverloadchanges.InE1twosizesofclients(C1andC2)areusedforthecomparisonwiththesamenumberofpeerservers(500).E2istostudytheeffectwhenthesystemscalechanges.InE2,whatwetrytodo

1

oftheother.Twosizesisconstructtwosystemscale,oneis10ofpeerservers(S1=500andS2=50)aresimulated.The

1

scaleofformerone.WhenusingsettingS1lattersizeis10=500,thesizeofclientsisC1=4,700,andthetotalnumberofrequestsgeneratedisabout300,000.WhenusingsettingS2=50,thesizeofclientsis1,000,andthetotalnumberof

1

ofC1.requestsgeneratedisabout36,000,about10Discussion:Figure5showstherelatedresults,inwhichthe

x-axisisthefourservicecategories(G,L,N,B),andthey-axisisthepercentageoftherequestsreceivingthecorrespondingservicecategory.

980

0.5Percentage of ServicePercentage of ServiceLIANGANDSHI

0.5

Percentage of Service0.5M1, P1, W3M1, P1, W5M2, P3, W40.30.20.1M1, P1, W4M2, P1, W40.40.30.20.10

G

L

W1W6W40.40.30.20.10

G

M1, W1M1, W4M2, W40.4NB

0

Different Kinds of Services

LN

Different Kinds of Services

B

GLNB

Different Kinds of Services

(a)(b)(c)

Figure4.Effectofdifferentcomponents.(a)Riskevaluationwithdifferentweights,(b)Riskevaluationwiththeeffectofmaliciousrecommendations,(c)Effectofrecommendations.

1.Efficacy.First,let’sstudytheefficacyofM-CUBE.Infig-ure5(a)therearethreelines.Oneisthe“WithoutM-CUBEandPET”,whichisthestandardresultwehavediscussedinthesetuppart;oneiswithM-CUBEandPET,andsmallersizeofclientsC1;finaloneisalsowithM-CUBEandPET,butwithlargersizeofclientsC2.Therearenoboastersinthisgroupofexperiment.Whatisdesiredforourapproachistoenablemorerequeststogetthegoodservicesandde-presstheByzantineservices,becauseByzantineservicesbringmostseverelossamongthebadservices.Fromfigure5(a),wecanseethatonceapplyingourapproach,thereisgreatimprovement:withsmallscale(C1=4700),theper-centageofgoodserviceisincreasedfrom27.5%(standardresult)to35.5%(relatively29.1%improvement);whenthescaleislarger(C2=9400),thepercentageincreasessignif-icantlyto46.5%(relatively69.1%improvement).Thesup-pressiontoByzantinebehaviorisnotthatgood.WhenthesizeofclientsisC1,theserviceservedbyByzantinebehav-iorisevenmorethanthestandardresult;howeverwhenin-creasethenumberofclientstoC2,theresultismuchbetter:from42.1%withoptionC1decreaseto27.3%(relatively35.2%decrease)withoptionC2.Allthesedatatellus:(1)Ourmodelisverygoodtobringmoregoodservices

tothesystem,andwiththeincreaseofthenumberofclients(servicerequests),theimprovementisevenbetter.(2)TheeffectofsuppressingtheByzantineserviceis

notasgoodaspromotingthegoodservice.Butthe

0.5Percentage of ServicePercentage of Service0.5

effectwillappearwhenmoreservicerequestsareserved.

(3)Morerequestsmeansmoretimeandmoreinforma-tiontoletthesystemtogetconvergent,becausemorefeedbackandobservationcanbereceived.

Fromtheaboveresult,wecanseethatourapproachisconvergent,fortheresultgetsmoreimprovementwhenchoosinglargernumberofrequests,nomatterfromtheviewofincreasinggoodserviceortheviewofdepressingtheByzantineservice.

(4)Itcanexpected,whenincreasethenumberof

requests,theresultwillgetevenmorecompetent,becausewhenthesystemgetconvergent,mostpeersknowthegoodpeers,andmosttheservicerequestswillgetgoodservicefromthesegoodpeers.(2)Anti-boaster.Infigure5(b)theboasterwillexist,andthe

badpeercanactmoreintelligently.Fromfigure5(b),wecanseethatthepercentageofgoodserviceincreasesfrom27.5to32.8%(relatively19.3%improvement)withC1,andto37.5%(relative36.4%improvement)withmorerequestsC2.Theimprovementisquiteabitlessthanfigure5(a),andtheeffectonsuppressingtheByzantineserviceisevenweaker.However,considering80%peersareintelligentbadpeers,andmaliciousrecommendationsandboastersexist(ahighlyuntrustedenvironment),westillcansayourapproachiseffectiveandrobustfortheextremelyuntrustedcomputingenvironment.Thefactbe-hindthesedatais,thehighlyuntrustedenvironmentwill

0.5Percentage of Service0.40.30.20.10G

Without M-CUBE and PETWith M-CUBE and PET, C1With M-CUBE and PET, C2Without M-CUBE and PET0.40.30.20.10

With M-CUBE and PET, C1With M-CUBE and PET, C20.40.30.20.10

Without M-CUBE and PETS1S2LN

Different Kinds of Services

BG

LN

Different Kinds of Services

B1

23

Different Kinds of Services

4

(a)(b)(c)

Figure5.Improvementofourmodel.(a)Nomaliciousrecommendationsandboasters,(b)Bothmaliciousrecommendationsandboastersexist,and(c)Differentnumberofpeerservers.

ENFORCINGCOOPERATIVERESOURCESHARINGINUNTRUSTEDP2PCOMPUTINGENVIRONMENTS981

costmoretimeforthesystemtogetconvergent,butcannotpreventthetrendtoconvergency.

(3)Scalability.Infigure5(c),inadditionaltothestandard

results,twoexperimentsareconducted:oneiswithlargersizeofpeerserversS1,andtheotheriswiththesmalleroneS2.Noboastersexistinthisexperiment.Thesettingsandthereasonswhychoosethishavebeendiscussedinsetuppart.Fromthefigure5(c),wecanseethat,onlyabout25.0%goodservicethesystemgetswiththesmallscale,muchlessthantheresultwithlargerscale35.5%,andevenlessthanthestandardresult27.5%.Itisbecause

1

,thenumberwhenthenumberofpeerserverdecreaseto101

ofrequestsalsodecreaseto10.Obviouslywecanseethatinthesmallerscale,thesystemisnotconvergent,sothattheperformanceisnotgood.Butontheotherhand,thisalsotellusthatlargerscalesystemcanhelptoimprovetheperformance.Sothemodelisscalable.Ofcourse,thereshouldbeonesaturatepointfortheincreaseofthesystemscale,whichisoneofourfuturework.Fromfigure5(c),itcanbeseenthatwiththeincreasingoftheclientnumberfromC1toC2,thegoodservicepercentageincreasesfrom35%to48%.Alltheseimplythattheexperimentresultswillbebetterifthescaleofexperimentincreases.ThusweexpectthatinthelargescaleP2Pcommunity,ourapproachwillbegreatpromising.5.3.Relationshipamongtrustworthiness,reputation,risk

andratio.InPET,thetrustworthinessisderivedfromthereputationandrisk.Withthesupportofthetrustworthinessevaluation,M-CUBEcanchangetheratioofthecurrencydynamically,whichmakesourcurrencymodeleffectiveandaccurate.Inthissubsection,wewillanalyzehowthereputationandriskcombinetogethertomakethetrustworthinessmoreaccurate;wecanalsoseehowthetrustworthinessaffectsthecurrencyratio(Inthefollowingalltheratioisreferredtocurrencyratio).Setup:Wechoosethreekindsofpeersfortheconsideration:G-peer,B-peer(therepresentativeforthebadpeersincludeL-peer,N-peer,andB-peer),andD-peer.Thesethreepeersarepickedupfromonepeer’shistorytablerandomly.Discussion:Thex-axisineverysub-figureofthefigure6representsthetimeflow,andthey-axisstandsforthevalue

10.90.80.7Value10.90.80.70.60.50.40.30.20.10Timeofcomponents.Let’sfocusonthetrustworthinessfirst.FortheG-peer,thetrendofthetrustworthinessinfigure6(a)isincreasingoverall.Itcanbeenseenthattherearesomefluctu-ations.Thisisbecauseoftheaffectofrecommendations.Themaliciousrecommendationswilldisruptthetrustworthiness;eventhecorrectrecommendationswillalsodelaytheconver-gentprocess,becauseatthebeginningtheG-peer’strustwor-thinessvaluewillbelow,sotherecommendationvaluefortheG-peerwillbealsolow.However,thefluctuationstendtodis-appearastimegoeson,becausewhenmoreinteraction-basedinformationhasbeencollected,theroleoftherecommenda-tionbecomesweaker(theriskfortheG-peerisalwayszero,whichbringsnoeffectforthefluctuations).FortheB-peer,thetrendofthetrustworthinessisdecreasingearlierandsud-denlyinfigure6(b),whichisincurredbytheriskevaluation.BecausetheB-peeralwaysprovidesByzantineservices,itsriskwillalwaysbeoneforitscooperatorsoncethetheirco-operationbegins.Theriskwillmakethetrustworthinessdropsuddenlyandquickly,whichishelpfultorecognizetheB-peer.FortheD-peer(figure6(c)),thetrendisfluctuatingfirst,thendecreasinglater.DifferentfromtheG-peer,theoveralltendencyofthefluctuationisdecreasing,whileG-peer’sisincreasing.Thisisbecauseinadditiontotheeffectoftherec-ommendations,thefluctuationoftheD-peerisalsobecauseofitsdynamicchangeofthebehaviors,whichincursitsrepu-tationtodecrease.WhenthecooperationwithD-peerbegins,theriskisstartshavingeffectandmakesthetrustworthinessdropsuddenly.DifferentfromB-peer,thedropofthetrustwor-thinessislesssharp,butenoughtorevealtheD-peers.Fromtheaboveanalysis,wecanseethattheriskevaluationisgreathelpfultorecognizethebadanddynamicpeers,butnoeffectforthegoodpeers(Forthegoodpeers,ourPETmodelisthesameasthereputationmodel,becausetheriskisalwayszero.)6.Relatedwork

Thenotionof“trustmanagement”wasfirstcoinedbyBlazeetal.intheirseminalpaperondecentralizedtrustmanage-ment[4],whichaddressestheauthenticationofeachclientrequestfromtheperspectiveofservers(serviceprovider)intermsofsecuritypolicies,credentials,andtrustrelationship.Thisisdifferentfromwhatweproposed,wherethetrustwor-thinessofbothsidesareconsideredingeneral,ratherthanoneachindividualservicerequest.Inthecomputerscience

10.9ValueValue0.60.50.40.30.20.10RatioTrustworhinessReputationRiskRatioTrustworhinessReputationRisk0.80.70.60.50.40.30.20.10RatioTrustworhinessReputationRiskTimeTime(a)(b)(c)

Figure6.Relationshipamongthetrustworthiness,reputation,riskandratioThesettingoptionsofthisexperimentsare:B2,M2,P1,S2,andW4.(a)G-peers,(b)B-peers,and(c)D-peers.

982literature,Marsh(1994)isthefirstonetointroduceacompu-tationalmodelfortrustinthedistributedartificialintelligence(DAI)community[16].However,hedidnotmodelreputa-tioninhiswork.Mui[17]givesadetailedcomputationalmodeloftrustandreputation.InMui’smodel,reputationiswellmodeled,butitdoesn’ttaketheriskintoconsideration.Recently,intheP2Pdomaindecentralizedreputationman-agementschemeslikeP2Prep[7],EigenTrust[13]appear.P2PrepprovidesaprotocolcomplementingexistingP2Ppro-tocols.EigenTrustassumesthattrustistransitiveandaddresstheweaknessoftheassumptionandthecollusionproblembyassumingtherearepre-trustednodesinthesystems.However,theobjectiveofthesereputation-basedsystemsaredifferentfromthatofoureffortenforcingself-policingtrustworthinessoverotherpeers,ratherthanobtainingaglobalconsistenttrustvalueforeachotherpeer.However,webelievethatourworkwillbenefitfromthesereputation-basedsystemsverywell.Numerouseconomicmodelsincludingmicroeconomicsandmacronomicsprinciplesforresourcemanagementhavebeenproposedintheliterature[2,5,6],andvariouscriteriaareusedforjudgingeffectivenessofaneconomicmodel,includingso-cialwelfare,stability,computationefficiency.However,dif-ferentfromtheM-CUBEmodelproposedhere,noneofthemtakethetrustworthinessintoconsideration,alsotoourknowl-edge,fewofthemconsiderthedependabilityoftheeconomicmodeltopossibleDDoSattacks.Severalresearchsystemshaveexploredtheuseofdifferenteconomicmodelsfortrad-ingresourcesindifferentapplicationdomains:CPUcycles,storage,databasequeryprocessing,andcomputing.Currencyandeconomicsbasedresourcemanagementhasbeenexten-sivelystudiedinthepast[9,21].ZhaoandKaramcheti[21]giveanapproachbuildingontheconceptsofticketsandcur-renciestoexpressresourcesharingagreements.Ourworkisdifferentfromtheseduetoourfocusonthetrustandsecu-rity.Toourknowledge,theSHARPInfrastructure[9]istheclosestworkrelatedtous.Butthedetailsofhowtousethecurrencyaredifferent.Differentfrom[9],ourinfrastructuredisagreeswiththeboaster.PPay[20]isamicropayment-basedmechanismforP2Presourcesharinganditguaranteesthatallcoinfraudisdetectable,traceableandunprofitable.Thisworkcomplementsourwork.7.Summary

InthispaperwehavepresentedanoveleconomicmodelM-CUBEcombiningthetrustmodelPETtoprovideafun-damentalmechanismforP2Presourcetradinginanopenenvironment.Theuniquenessofthisapproachisinitsabilitytoseamlesslyintegratethetrustworthinessanddependabilityofpeersintocurrencyratiofloatingforresourcetrading.Ouranalysisshowthatthismodeliseffectiveandrobustundertheuntrustedcomputingenvironment.Tothisend,webelievethattheproposedmodelprovidesageneralandflexiblein-frastructuretobuildmostofhighlevelresourcemanagementrequiredbyP2Pcomputing,suchasresourcecoallocationandqualityofservice(QoS)control.

LIANGANDSHI

References

[1]E.AdarandB.Huberman,Freeridingongnutella,FirstMonday5(10)(2000).

[2]

Y.Amir,B.AwerbuchandR.Borgstrom,Acost-benefitframeworkforonlinemanagementofametacomputingsystems,in:Proc.ofthefirstInernationalConferenceonInformationandComputationalEconomy(1998).

[3]

P.BarfordandM.E.Crovella,Generatingrepresentativewebwork-loadsfornetworkandserverperformanceevaluation,in:ProceedingsofPerformance󰀐98/ACMSIGMETRICS󰀐98(1998).

[4]M.Blaze,J.FeigenbaumandJ.Lacy,Decentralizedtrustmanagement,in:IEEESymposiumonSecurityandPrivacy(1996).

[5]

R.Buyya,D.AbramsonandJ.Giddy,Acaseforeconomygridarchitectureforservice-orientedgridcomputing,in:Proceedingsofthe10thIEEEInternationalHeterogeneousComputingWorkshop(2001).

[6]

B.Chun,Market-basedclusterresourcemanagement,Ph.D.thesis,DepartmentofElectricalEngineeringandComputerScience,UCBerkeley(2001).

[7]

F.Cornelli,E.Damiani,S.D.C.Vimercati,S.ParaboschiandP.Samarati,ChoosingreputableserventsinaP2Pnetwork,in:Proc.ofthe11thInternationalWorldWideWebConference(2002).

[8]J.Douceur,TheSybilAttack,in:Proc.ofthe1stInternationalWorkshoponPeer-to-PeerSystems(IPTPS󰀐02)(2002).

[9]

Y.Fu,J.Chase,B.Chun,S.SchwabandA.Vahdat,SHARP:AnArchitectureforsecureresourcepeering,In:Proc.ofthe19thACMSymp.onOperatingSystemsPrinciples(SOSP-19)(2003).

[10]

R.GuptaandA.K.Somani,CompuP2P:Anarchitectureforsharingofcomputepowerinpeer-to-peernetworkswithselfishnodes,in:SecondWorkshopontheEconomicsofPeer-to-PeerSystems,HarvardUniversity(2004).

[11]

D.Hausheer,N.C.Liebau,A.Mauthe,R.SteinmetzandB.Stiller,Token-basedaccountinganddistributedpricingtointroducemarketmechanismsinapeer-to-peerfilesharingscenario,in:ThirdInterna-tionalConferenceonPeer-to-PeerComputing(P2P󰀐03)(2003).

[12]

H.Junseok,Theeconomicsofdynamicbandwidthtransactionservice:towardpricingmodeling,in:MSIWorkshoponModelling,UniversityCollegeLondon,(2001)pp.18–19.

[13]

S.Kamvar,M.T.SchlosserandH.Gacia-Molina:TheeigentrustalgorithmforreputationmanagementinP2Pnetworks,in:Proc.ofthe12thInternationalWorldWideWebConference(2003).

[14]

Z.LiangandW.Shi,Enforcingcooperativeresourcesharinginuntrustedpeer-to-peerenvironment,TechnicalreportMIST-TR-2004-014,DepartmentofComputerScience,WayneStateUniversity(2004).

[15]

Z.LiangandW.Shi,Analysisofrecommendationsontrustinferenceintheopenenvironment,TechnicalreportMIST-TR.-2005-002,DepartmentofComputerScience,WayneStateUniversity(2005).

[16]S.Marsh,Formalisingtrustasacomputationalconcept,Ph.D.thesis,UniversityofStirling(1994).

[17]

L.Mui,M.MohtashemiandA.Halberstadt,AComputationalmodeloftrustandreputation,in:Proceedingsofthe35thHawaiiInternationalConferenceonSystemSciences(2002).

[18]

J.Ravi,Z.LiangandW.Shi,ACaseforpeer-to-peerwebserversharing,TechnicalReportMIST-TR.-2003-010,DepartmentofComputerScience,WayneStateUniversity(2003).

[19]

Y.WangandJ.Vassileva,Trustandreputationmodelinpeer-to-peernetworks,in:ThirdInternationalConferenceonPeer-to-PeerComputing(P2P󰀐03)(2003).

[20]B.YangandH.Carcia-Molina,PPay:Micropaymentsforpeer-to-peersystems,in:ProceedingsofACMCCS󰀐03(2003).

[21]

T.ZhaoandV.Karamcheti,Enforcingresourcesharingagreementsamongdistributedserverclusters,in:Proceedingsofthe16thInter-nationalParallelandDistributedProcessingSymposium(IPDPS)(2002).

ENFORCINGCOOPERATIVERESOURCESHARINGINUNTRUSTEDP2PCOMPUTINGENVIRONMENTS983

ZhengqiangLiangisaPh.D.StudentincomputerscienceatWayneStateUniversity.Hiscurrentre-searchesfocusontrustedandcooperativeresourcesharingintheopenenvironment,andcomputereco-nomics.HereceivedhisB.Sdegreein1997andM.S.degreein2001fromHarbinInstituteofTech-nology(HIT)inChina,bothinComputerScienceandEngineering.

E-mail:sean@wayne.edu

theauthorofthebook“PerformanceOptimizationofSoftwareDistributedSharedMemorySystems”(HighEducationPress,2004).Hehasalsoservedontechnicalprogramcommitteesofseveralinternationalconferences,includ-ingthechairofpostertrackofWWW2005.HeisarecipientofMicrosoftFellowshipin1999,thePresidentoutstandingawardoftheChineseAcademyofSciencesin2000,oneof100outstandingPh.D.dissertations(China)in2002,“FacultyResearchAward”ofWayneStateUniversityin2004,the“BestPaperAward”ofICWE’04andIPDPS’05.HeisamemberofACM,USENIX,andIEEE.

E-mail:weisong@wayne.edu

WeisongShiisanAssistantProfessorofComputerScienceatWayneStateUniversity.HereceivedhisB.S.fromXidianUniversityin1995,andPh.D.degreefromtheChineseAcademyofSciencesin2000,bothinComputerEngineering.HiscurrentresearchfocusesondynamicWebcontentdelivery,trustedresourcesharinginpeer-to-peersystems,mobilecomputing,andwirelesssensornetworks.Dr.Shihaspublishedmorethan40peer-reviewedjournalandconferencepapersintheseareas.Heis