提高P2P覆盖搜索效率的分布式算法(IJCNIS-V4-N3-1)

I.J.ComputerNetworkandInformationSecurity,2012,3,1-7PublishedOnlineApril2012inMECS()DOI:10.5815/ijcnis.2012.03.01DistributedAlgorithmsforImprovingSearchEfficiencyinP2POverlaysChittaranjanHota1,VikramNunia1,AnttiYlä-Jääski21Dept.ofComputerScienceandInformationSystems,BirlaInstituteofTechnologyandScience-PilaniHyderabadCampus,Hyderabad,AP,India,5000782DepartmentofComputerScience&Engineering,AaltoUniversity,Helsinki,[e-mail],[e-mail],[e-mail]—Peer-to-peer(P2P)overlayisadistributedapplicationarchitectureinwhichpeerssharetheirresources.Peersareequallyprivileged,equipotentparticipantsintheapplication.SeveralalgorithmsforenhancingP2Pfilesearchinghavebeenproposedintheliterature.Inthispaper,wehaveproposedauniqueapproachofreducingtheP2Psearchcomplexityandimprovingsearchefficiencybyusingdistributedalgorithms.Inourapproachapeermountsotherpopularpeer’sfilesandalsoreplicatesotherpopularfilesorcriticalfilesidentifiedusingathresholdvalue.Onceafileismounted,fileaccessrequestscanbeservicedbytransparentlyretrievingthefileandsendingittotherequestingpeer.Replicationusedinthisworkimprovesthefileretrievaltimebyallowingparalleltransfer.Wehaveshowntheperformanceanalysisofourproposedapproachwhichshowsimprovementinthesearchefficiency.IndexTerms—Algorithm;FileSharing;Replication;Mounting;BootstrapPeer.I.INTRODUCTIONThepeertopeer(P2P)paradigmhadstartedbecomingpopularinthemiddleof2000amongstinternetmusiclovers.Sincethen,duetoitsinherentpositivecharacteristics,theterm‘P2P’hasbecomeverypopularamongstinternetusers,researchersandindustries.AsystemistobeconsideredP2Piftheelementsthatformthesystemsharetheirresourcesinordertoprovidethedesignatedservices.Theelementsinthesystemprovidebothclientandserverservicesi.e.,providingservicestootherelementsandrequestingservicesfromotherelements.Anoverlaynetworkisalogicalnetworkattheapplicationlayerprovidingconnectivity,routingandmessagingamongsttheaddressableendpoints.Theyhavetheirowntopologydifferentfromunderlyingphysicalnetwork.TheyhavetheirwayofroutingmessageswiththehelpoftheInternet.Theyhavetheirownwayofaddressingtheendpoints.Overlaynetworksarefrequentlyusedasasubstratefordeployingnewnetworkservices,orforprovidingaroutingtopologynotavailablefromtheunderlyingphysicalnetworkasshowninFig.1.P2Poverlaynetworksarecategorizedasunstructuredandstructured.AnunstructuredP2Pnetworkiscomposedofpeersjoiningthenetworkwithsomelooserules,withoutanypriorknowledgeofthetopology.Gnutella[1]andKazaa[2]areexamplesofunstructuredP2Poverlaynetworks.InstructuredP2Poverlaynetworks,networktopologyistightlycontrolledandcontentisplacednotatrandompeersbutatspecifiedlocationsthatwillmakesubsequentqueriesmoreefficient.MostofthestructuredP2PoverlaysareDistributedHashTable(DHT)based.ContentAddressableNetwork(CAN),Chord,andPastryaresomeofthewellknownexamplesofstructuredP2Poverlaynetworks.Inthiswork,wehavedevelopedauniqueapproachofreducingtheP2Psearchcomplexityandimprovingsearchefficiencybyusingdistributedalgorithmsmountingandreplication.Apeerwhichservesmorenumberofpeers(wecallitasapopularpeer)mountsheavilyusedfilesfromotherpeers.Thispopularpeerwhencontactedbyotherpeerstransparentlyretrievesthefilesandgivesthosetotherequestingpeer.Figure1.AnExampleP2POverlayNetworkThereplicationalgorithmdevelopedreplicatescriticalfilesatmultiplepeers.Acriticalfileisafilethatisaccessedmorethanathresholdlimit,whichistunable.ThepeersthatareselectedaslocationforstoringreplicasarejudiciouslydecidedonvariousfactorslikenumberofCPU,Storagecapacity,andPeerconnectiondegreeatthatpeer.Copyright©2012MECSI.J.ComputerNetworkandInformationSecurity,2012,3,1-72DistributedAlgorithmsforImprovingSearchEfficiencyinP2POverlaysTheremainderofthepaperisorganizedasfollows.SectionIIreviewstherelatedresearch.SectionIIIdiscussesmodelsandassumptions.SectionIVpresentsourproposedimplementation.InSectionV,wedescribeourdistributedalgorithms.SectionVIgivesdetailsaboutthesimulationrun.Finally,SectionVIIconcludesthepaperandpresentsfutureresearchdirections.II.RELATEDWORKSearchinanunstructuredpeer-to-peerfilesharingsystemisdependentonmanyfactorscenteredonoverlaytopology,dataplacementandrouting[3].Agoodsearchmechanismisonewhichallowsuserstoeffectivelylocatedesireddatainaresource-efficientmanner[3].Inunstructuredoverlays,thereareseveralchallengesliketheirlargesize,transitivepopulationofnodes,heterogeneity,userautonomyetc.Therearenumberofsearchalgorithmsproposedtomeetthesechallenges.Thefirstfilesharingnetwork[4]maintainedacentralizedindexofallthefiles.Searchiscarriedoutbythecentralserveritselfwithoutinvolvingothernodesinthenetwork.Butcentralservershavethesomelimitationslikesinglepointoffailure,scalability,etc.WithlitigationswithNapster,Gnutella[1]becamepopular.GnutellausesafullydecentralizedsearchmechanismwhichisknownasFloodingor,Breadth-first-search[5].Lvetal.[6]notesseverallimitationsoffloodinglikeheterogeneityissues,selectingappropriateTTL,handlingofduplicatequeries.YangandGracia-Molina[5]proposedfloodingpoli