A Survey and Comparison of Peer-to-Peer Overlay Ne

IEEECOMMUNICATIONSSURVEYANDTUTORIAL,MARCH20041ASurveyandComparisonofPeer-to-PeerOverlayNetworkSchemesEngKeongLua,JonCrowcroft,MarceloPias,RaviSharmaandStevenLimAbstract—OvertheInternettoday,computingandcommuni-cationsenvironmentsaresignificantlymorecomplexandchaoticthanclassicaldistributedsystems,lackinganycentralizedorga-nizationorhierarchicalcontrol.TherehasbeenmuchinterestinemergingPeer-to-Peer(P2P)networkoverlaysbecausetheyprovideagoodsubstrateforcreatinglarge-scaledatasharing,contentdistributionandapplication-levelmulticastapplications.TheseP2Pnetworkstrytoprovidealonglistoffeaturessuchas:selectionofnearbypeers,redundantstorage,efficientsearch/locationofdataitems,datapermanenceorguarantees,hierarchicalnaming,trustandauthentication,and,anonymity.P2Pnetworkspotentiallyofferanefficientroutingarchitecturethatisself-organizing,massivelyscalable,androbustinthewide-area,combiningfaulttolerance,loadbalancingandexplicitnotionoflocality.Inthispaper,wepresentasurveyandcompar-isonofvariousStructuredandUnstructuredP2Pnetworks.Wecategorizethevariousschemesintothesetwogroupsinthedesignspectrumanddiscusstheapplication-levelnetworkperformanceofeachgroup.IndexTerms—Peer-to-Peer,DistributedScalableAlgorithms,LookupProtocols,OverlayRouting,OverlayNetworks.I.INTRODUCTIONPEER-TO-PEER(P2P)overlaynetworksaredistributedsystemsinnature,withoutanyhierarchicalorganizationorcentralizedcontrol.Peersformself-organizingoverlaynetworksthatareoverlayedontheInternetProtocol(IP)networks,offeringamixofvariousfeaturessuchasrobustwide-arearoutingarchitecture,efficientsearchofdataitems,selectionofnearbypeers,redundantstorage,permanence,hier-archicalnaming,trustandauthentication,anonymity,massivescalabilityandfaulttolerance.Peer-to-peeroverlaysystemsgobeyondservicesofferedbyclient-serversystemsbyhavingsymmetryinroleswhereaclientmayalsobeaserver.Itallowsaccesstoitsresourcesbyothersystemsandsupportsresource-sharing,whichrequiresfault-tolerance,self-organizationandmassivescalabilityproperties.UnlikeGridsystems,P2Pover-laynetworksdonotarisefromthecollaborationbetweenestablishedandconnectedgroupsofsystemsandwithoutamorereliablesetofresourcestoshare.WecanviewP2Poverlaynetworkmodelsspanningawidespectrumofthecommunicationframework,whichspecifiesafully-distributed,cooperativenetworkdesignwithpeersbuild-ingaself-organizingsystem.Figure1showsanabstractP2Poverlayarchitecture,illustratingthecomponentsintheoverlayManuscriptreceivedMarch31,2004;revisedNovember20,2004.EngKeongLua,JonCrowcroftandMarceloPiasarewiththeUniversityofCambridge,ComputerLaboratory.RaviSharmaiswiththeNanyangTechnologicalUniversity.StevenLimiswiththeMicrosoftAsia.!#$%&’$(()*+,-+$*./-0!%12!%3-0$4!.5-*-6!(!*/-0!%7!-)%!.5-*-6!(!*/-0!%8!%2+,!.9.:!,+;+,/-0!%::3+,-+$*93!2!3/-0!%Fig.1.AnAbstractP2POverlayNetworkArchitecturecommunicationsframework.TheNetworkCommunicationslayerdescribesthenetworkcharacteristicsofdesktopma-chinesconnectedovertheInternetorsmallwirelessorsensor-baseddevicesthatareconnectedinanad-hocmanner.Thedynamicnatureofpeersposeschallengesincommunicationparadigm.TheOverlayNodesManagementlayercoversthemanagementofpeers,whichincludediscoveryofpeersandroutingalgorithmsforoptimization.TheFeaturesManagementlayerdealswiththesecurity,reliability,faultresiliencyandaggregatedresourceavailabilityaspectsofmaintainingthero-bustnessofP2Psystems.TheServicesSpecificlayersupportstheunderlyingP2Pinfrastructureandtheapplication-specificcomponentsthroughschedulingofparallelandcomputation-intensivetasks,contentandfilemanagement.Meta-datade-scribesthecontentstoredacrosstheP2Ppeersandthelocationinformation.TheApplication-levellayerisconcernedwithtools,applicationsandservicesthatareimplementedwithspecificfunctionalitiesontopoftheunderlyingP2Poverlayinfrastructure.So,therearetwoclassesofP2Poverlaynetworks:StructuredandUnstructured.ThetechnicalmeaningofStructuredisthattheP2Poverlaynetworktopologyistightlycontrolledandcontentareplacednotatrandompeersbutatspecifiedlocationsthatwillmakesubsequentqueriesmoreefficient.SuchStructuredP2Psys-temsusetheDistributedHashTable(DHT)asasubstrate,inwhichdataobject(orvalue)locationinformationisplaceddeterministically,atthepeerswithidentifierscorrespondingtothedataobject’suniquekey.DHT-basedsystemshavea2IEEECOMMUNICATIONSSURVEYANDTUTORIAL,MARCH2004DistributedStructuredP2POverlayApplicationDistributedHashTablePeerPeerPeerPeerValueFig.2.ApplicationInterfaceforStructuredDHT-basedP2POverlaySystemspropertythatconsistentlyassigneduniformrandomNodeIDstothesetofpeersintoalargespaceofidentifiers.Dataobjectsareassigneduniqueidentifierscalledkeys,chosenfromthesameidentifierspace.Keysaremappedbytheoverlaynetworkprotocoltoauniquelivepeerintheoverlaynetwork.TheP2Poverlaynetworkssupportthescalablestorageandretrievaloffkey,value