基于P2P网络环境下的副本一致性维护算法

36120091ComputerScienceVol.36No.1Jan.2009:2008202228(06JJ2090),(60703096,60703097),(05GK3048)(1982-),,,P2P,E2mail:[e-mail];(1956-),,,,CCF,;(1978-),,,P2P;(1978-),,,P2P(410082)P2P,,,,,owner,,,,,,,/TP393ReplicationConsistencyMaintenanceAlgorithminUnstructuredP2PSystemsGUOXiao2meiLIRen2faWENJi2gangXIEKun(CollegeofComputerandCommunication,HunanUniversity,Changsha410082,China)AbstractReplicationisaprevalentwaytoimprovetheperformanceandextensionaswellastoreducethequeryre2spondingtimeinP2Psystem.Becausecurrentnetworkmaybedynamicwithnodesfrequentlyjoinsandleavesandob2jectsupdatedhighlyforadaptingtooperationdevelopmented,maintainingconsistencyofreplicationsismorechallengingintheseenvironmented.Thispaperpresentedaregionpushthenpullalgorithminhighlydynamicnetworks.Itisbasedonpercentageofofflinenodesandthetransformratiobetweenreplicatednodesandun2replicatednodestodecidethenodeswhichareresponsibleofeasingtheburdenofowner.Besides,itcanlargelyreducethenumberoftheduplicatedmessages.Theexperimentalresultsshowthatthenewalgorithmhasexcellentconsistencyandlowermessagesoverheadespeciallyindynamicenvironments,whichisbetteradaptedtotheextensionofdynamicP2Psystems.KeywordsConsistency,Peer2to2peer,Highlydynamic,Region,Pull/push1P2P,,P2PP2P,,,,,,,,P2PQoS,P2P,C/SP2P(Chord,CAN),,,Hash;P2P(Gnutella,Freenet),,,(RumorGossip)[1],,Ru2mor[2],,,[3]TTL,pullP2P34,/,,,Scope[4],,/,,2/2.1GnutellaP2P,,,,,,11)(owner):,2):(responsibility):,TTR,owner,pushTTL:pushTTR[5]TTR,pull3.:TTL(),::ownerid,ownerownerd,dnm,,,1/p,rK,:r=(m(1-1/p)+(n-m)1/p)/nK(1)ownerowner,1:,n3n2,n2n3n2n1,n1n2ownern3n22.2,owner,,P2P,,,pull:TTR,TTR,(1)TTR:TTR=TTRold+C,versionchangedTTRoldDotherwise(2)C0,D=VNnew-VNold+a(VNnew,VNold,a0)TTR,,TTR,(TTR/D)TTR,TTR(TTR+C),TTR(2)Gnutella,TTR,pull(2)TTR:TTR=TTR+(1+Nconn-NavgconnNavgconn)3h(3)TTR,,,TTR,,,,TTR,TTRTTR=max(TTRmin,min(TTRmax,TTR))3,,,2(a)owner,,,(b)(c)2,,,r((1)),,,44,,,(2.1)rnew,,,,,[6],r44.1RPTP,,RPTP11Lsim10hRf50%If5minDf2h5005000,20/80,20%80%,95%7,TTL822TTRmaxTTR1hTTRminTTR5minNavgconn4p1/3K1/2CTTR,110minaTTR,20.5hTTR,3104.2RPTP:Mumr(missedupdatemessagesratio)Ofmu(overheadofmessagesperupdate)5%50%3,,FloodingRPTP,FloodingRPTP,Flooding,,RPTP,,4,,(2002000)FloodingRPTPFlooding,,RPTP,,,Flood2ingP2P,,,Flooding,,,,,[1]DattaA,HauswirthM,AbererD.Updatesinhighlyunreliable,replicatedp2psystems[C]Proc.of23thIEEEInternationalConferenceonDistributedComputingSystems.ProvidenceRhodeisland,USA,2003:76285[2]WangZ,KumarM.Updatepropagationthroughreplicachainindecentralizedandunstructuredp2psystems[C]Proc.ofthe4thInternationalConfernceonp2pComputing.2004.1730Mas2sachusettsAve.,NWWashington,DCUSA:IEEEComputerSociety,Aug.2004:64271[3]DuvvuriV,ShenoyP,TewariR.AdaptiveLeases:AStrongConsistencyMechanismfortheWorldWideWeb[J].IEEETransactionsonKnowledgeandDataEngineering,2003,15(5):126621276[4]ChenXin,RenShansi,WangHaining,etal.SCOPE:scalableconsistencymaintenanceinstructedP2Psystems[C]Proc.ofIEEEINFOCOM2005Confernce.Miami,Florida.March2005,3:150221513[5]LanJiang,LiuXiaotao,ShenoyP,etal.ConsistencyMainte2nanceinPeer2to2PeerFileSharingNetwork[C]Proc.ofTheThirdIEEEWorkshoponInternetApplications(WIAPP03).June2003:90294[6]WangXiaofan,ChenGuanrong.Complexnetworks:smallworld,scale2freeandbeyond[J].IEEECircuitsandSystemsMagazine,2003,3(1):622054