improvep2pover

EfficientGnutella-likeP2POverlayConstructionYunhaoLiu1,LiXiao2,LionelM.
Ni1andBaijianYang31DepartmentofComputerScience,HongKongUniversityofScienceandTechnology,Kowloon,HongKong,Chinani@cs.
ust.
hk2DepartmentofComputerScienceandEngineering,MichiganStateUniversity,EastLansing,MI48824,USAlxiao@cse.
msu.
edu3DepartmentofIndustryandTechnology,BallStateUniversity,Muncie,IN47306,USAbyang@bsu.
eduAbstract.
Withoutassuminganyknowledgeoftheunderlyingphysicaltopol-ogy,theconventionalP2Pmechanismsaredesignedtorandomlychooselogi-calneighbors,causingaserioustopologymismatchproblembetweentheP2Poverlaynetworkandtheunderlyingphysicalnetwork.
ThismismatchproblemincursagreatstressintheInternetinfrastructureandadverselyrestraintstheperformancegainsfromthevarioussearchorroutingtechniques.
Inordertoal-leviatethemismatchproblem,reducetheunnecessarytrafficandresponsetime,weproposetwoschemes,namely,location-awaretopologymatching(LTM)andscalablebipartiteoverlay(SBO)techniques.
BothLTMandSBOachievetheabovegoalswithoutbringinganynoticeableextraoverheads.
More-over,bothtechniquesarescalablebecausetheP2Pover-laynetworksareconstructedinafullydistributedmannerwhereglobalknowledgeofthenetworkisnotnecessary.
ThispaperdemonstratestheeffectivenessofLTMandSBO,andcomparestheperformanceofthesetwoapproachesthroughsimulationstudies.
1IntroductionAsanemergingmodelofcommunicationandcomputation,peer-to-peersystemsarecurrentlyunderintensivestudy[6,10,12,15,16].
ThispaperfocusesonunstructuredP2Psystems,suchasGnutella[2]andKaZaA[4],sincetheyaremostcommonlyusedintoday'sInternet.
Fileplacementisrandominthesesystems,whichhasnocorrelationwiththenetworktopology.
Thetypicalsearchmechanismadoptedwillblindly"flood"aquerytothenetworkamongpeers(suchasinGnutella)oramongsupernodes(suchasinKaZaA).
Thequeryisbroadcastedandrelayeduntilacertaincriterionissatisfied.
Ifaninquiredpeercanprovidetherequestedobject,aresponsemessagewillbesentbacktothesourcepeeralongtheinverseofthequerypath.
ThefloodmechanismensuresthatthequerymessagescanreachasmanypeersaspossiblewithinashortperiodoftimeinaP2Poverlaynetwork.
Studiesin[15]and[14]haveindicatedthatP2Psystems,suchasFastTrack(in-cludingKaZaAandGrokster)[1],Gnutella,andDirectConnect,contributethelargestportionoftheInternettraffic.
AmongthoseP2Ptraffic,aconsiderableportionoftheH.
Jinetal.
(Eds.
):NPC2004,LNCS3222,pp.
146-153,2004.
IFIPInternationalFederationforInformationProcessing2004EfficientGnutella-likeP2POverlayConstruction147loadiscausedbytheinefficientoverlaytopologyandtheblindflooding,whichalsomakestheunstructuredP2Psystemsfarfrombeingscalable[13].
Aimingatalleviatingthemismatchproblem,reducingtheunnecessarytraffic,andaddressingthelimitsofexistingsolutions,weproposelocation-awaretopologymatching(LTM)andscalablebipartiteoverlay(SBO)scheme.
InLTM,eachpeerissuesadetectorinasmallregionsothatthepeersreceivingthedetectorcanrecordrelativedelayinformation.
Basedonthedelayinformation,areceivercandetectandcutmostoftheinefficientandredundantlogicallinks,andaddclosernodesasitsdirectneighbors.
SBOtakesanotherapproachwhereGnutella-likepeer-to-peerover-laysareoptimizedbydisconnectingredundantconnectionsandchoosingphysicallyclosernodesaslogicalneighbors.
OursimulationstudiesrevealthatthetotaltrafficandresponsetimeofthequeriescanbesignificantlyreducedbybothLTMandSBOwithoutshrinkingthesearchscope.
Therestofthepaperisorganizedasfollows.
Section2introducesrelatedwork.
Section3discussesunnecessarytrafficandtopologymismatchproblems.
Section4outlinesthedesignsofLTMandSBOschemes.
Simulationandperformanceevalua-tionoftheLTMandSBOarepresentedinSection5,andweconcludeourworkinSection7.
2RelatedWorkManyeffortshavebeenmadetoavoidthelargevolumeofunnecessarytrafficin-curredbytheflooding-basedsearchindecentralizedunstructuredP2Psystems.
Ingeneral,threetypesofapproacheshavebeenproposedtoimprovesearchefficiencyinunstructuredP2Psystems:forwarding-based,cache-basedandoverlayoptimiza-tion.
Theabovethreedifferentapproachesarenotexclusiveandcanbeintegratedtoachievebetterresults.
Inforwarding-basedapproaches,insteadofpassingonthequerymessagestoallbutincominglogicalneighbors,apeerselectsasubsetofitsneighborstorelaythequery.
Thesecondapproachiscache-basedsearch,whichincludesdataindexcach-ingandcontentcaching.
CentralizedP2Psystemsprovidecentralizedindexserverstokeepindicesofsharedfilesofallpeers.
KaZaAutilizescooperativesuperpeers,eachofwhichisanindexserverofasubsetofpeers.
Somesystemsdistributethefunctionofkeepingindicestoallpeers[11].
Thethirdsearchstrategyisoverlaytopologyoptimization,whichinspirestheworkwearepresentinginthispaper.
Endsystemmulticast,Narada,proposedin[7],con-structsshortest-path-spanningtreesontopofarichconnectedgraph.
Eachtreerootedatthecorrespondingsourceemploysthewell-knownDVMRProutingalgorithm.
Naradahasproventobeasoundoverlaysystemwhenthenumberofparticipantsisnotsignificant.
However,becauseitssystemoverheadsareexponentialtothesizeofthemulticastgroup,itisnotsuitablefortheP2Psystem,whichisnormallyverydy-namicandinvolvesagoodmanynodescrossingawideareaofnetworks.
Recently,researchersin[17]haveproposedtomeasurethelatencybetweeneachpeertomulti-plestableInternetserverscalled"landmarks".
Themeasuredlatencycanthenbeservedtodeterminethedistancebetweenpeers.
Thismeasurementisconductedina148Y.
Liuetal.
globalP2Pdomain.
Incontrast,wechooseacompletelydistributedapproachwheredistancemeasurementismanagedinmanysmallregions.
Asaresult,ourschemescansignificantlyreducethenetworktrafficwhileretaininghighaccuracy.
3UnnecessaryTrafficandTopologyMismatchInaP2Psystem,allparticipatingpeersformaP2Pnetworkoveraphysicalnetwork.
MaintainingandsearchingoperationsofaGnutellapeeraredescribedin[3].
WhenjoiningaP2Pnetwork,anewpeer-nodegetstheIPaddressesofalistofexistingpeersfromabootstrappingnode.
Itthenattemptstoconnectitselftothesepeersastheirneighbors.
OncethenewpeergetsconnectedwithaP2Pnetwork,itwillperi-odicallypingthenetworkconnectionstoobtaintheIPaddressesofsomeotherpeersinthenetwork.
Unfortunately,thejoinmechanismspecifiedinaP2Pnetwork,thedynamicsofpeermemberships,andthenatureoffloodingwouldendupwithamis-matchedoverlaynetworkstructureandthusincuralargeamountofunnecessarytraffic[12].
Fig.
1.
AnexampleoftopologymismatchproblemAnexampleoftopologymismatchisillustratedinFig.
1,wheresolidlinesrepre-senttheunderlyingphysicalconnectionsanddottedlinesdenotetheoverlayconnec-tionsinaGnutella-likeP2Psystem.
ForaquerymessagesentalongtheoverlaypathACB,nodeBisvisitedtwice.
AlthoughBisapeeringnode,Bisfirstvisitedasanon-peeringnodewhenAtriestoreachC.
Becauseofthemismatchproblem,thesamemessagemaytraversethesamephysicallinks,suchasBE,EFandFCinFig.
1,multipletimes,causingalargeamountofunnecessarytrafficandincreasingtheP2Pusers'querysearchlatencyaswell.
ToquantitativelyevaluatehowseriousthetopologymismatchproblemisinGnutella-likenetworks,wesimulate1,000,000queriesondifferentGnutella-liketopologieswithaveragenumberofneighborsbeing4,6,8and10.
Inthissimulation,wetracktheresponseofeachquerymessagetocheckiftheresponsecomesbackalongamismatchedpath.
Wecountapathasamismatchedpathifapeeringnodeonthepathhasbeenvisitedmorethanonce.
Resultshowsmorethan70%ofthepathsaresufferedfromthetopologymismatchproblem.
EfficientGnutella-likeP2POverlayConstruction149Wealsohavethefollowingobservationsfromthesimulation.
First,aquerymaybefloodedtomultiplepathsthataremergedtothesamepeer.
Second,twoneighbor-ingpeersmayforwardthesamequerymessagetoeachotherbeforetheyreceiveitfromtheotherone.
Inbothcases,redundantquerymessagesaregeneratedevenamonglogicallinks.
Existingstudiesonoverlayoptimizationconnectphysicallyclosernodesasover-layneighborsusingdifferenttechniques.
However,thesekindsofapproachesmaydestroytheconnectivityoftheoverlayandthuscreatemanyisolatedislandsintheP2Psystem.
ThereforetheyarenotfeasibleinunstructuredP2Psystems.
4LTMandSBOOptimizinginefficientoverlaytopologiescanfundamentallyimproveP2Psearchefficiency.
Inthissection,wepresentoursolutions,LTMandSBO.
4.
1LTMIfthesystemcandetectanddisconnectthelowproductivelogicalconnectionsandswitchtheconnectionofACtoABasshowninFig.
1,thetotalnetworktrafficcouldbesignificantlyreducedwithoutshrinkingthesearchscopeofqueries.
Thisisthebasicprincipleofourproposedlocation-awaretopologymatchingtechnique[8].
Lo-cation-awaretopologymatchingconsistsofthreeoperations:TTL2detectorflooding,lowproductiveconnectioncutting,andsourcepeerprobing.
BasedonGnutella0.
6P2Pprotocol,wedesignanewmessagetypecalledTTL2-detector.
InadditiontotheGnutella'sunified23-byteheaderforallmessagetypes,aTTL2-detectormessagehasamessagebodyintwoformats.
Theshortformatisusedinthesourcepeer,whichcontainsthesourcepeer'sIPaddressandthetimestamptofloodthedetector.
Thelongformatisusedinaone-hoppeerthatisadirectneighborofthesourcepeer,whichincludesfourfields:SourceIPAddress,SourceTimestamp,TTL1IPAddress,TTL1Timestamp.
ThefirsttwofieldscontainthesourceIPaddressandthesourcetimestampobtainedfromthesourcepeer.
ThelasttwofieldsaretheIPaddressofthesourcepeer'sdirectneighborwhoforwardsthedetectorandthetime-stampwhenforwardit.
Inthemessageheader,theinitialTTLvalueis2.
Thepayloadtypeofthedetectorcanbedefinedas0x82.
EachpeerfloodsaTTL2-detectorperiodically.
Weused(i,S,v)todenotetheTTL2-detectorwhohasthemessageIDofiwithTTLvalueofvandisinitiatedbyS.
WeuseN(S)todenotethesetofdirectlogicalneighborsofS,anduseN2(S)tode-notethesetofpeersbeingtwohopsawayfromS.
ATTL2-detectorcanonlyreachpeersinN(S)andN2(S).
Weusenetworkdelaybetweentwonodesasametricformeasuringthecostbetweennodes.
Theclocksinallpeerscanbesynchronizedby150Y.
Liuetal.
currenttechniquesinanacceptableaccuracy1.
ByusingtheTTL2-detectormessage,apeercancomputethecostofthepathstoasourcepeer,andoptimizesthetopologybyconductinglowproductioncuttingandsourcepeerprobingoperations.
4.
2SBOInsteadoffloodingqueriestoallneighbors,SBOemploysanefficientstrategytoselectqueryforwardingpathandlogicalneighbors[9].
ThetopologyconstructionandoptimizationofSBOconsistoffourphases:bootstrappinganewpeer,neighbordistanceprobingandreporting,forwardingconnectionscomputing,anddirectneighborreplacement.
Phase1:bootstrappinganewpeer.
WhenanewpeerisjoiningtheP2Psystem,itwillrandomlytakeaninitialcolor:redorwhite.
Apeershouldkeepitscoloruntilitleaves,andagainrandomlyselectacolorwhenitrejoinsthesystem.
Thus,eachpeerhasacolorassociatedwithit,andallpeersareseparatedintotwogroups,redandwhite.
InSBO,abootstraphostwillprovidethejoiningpeeralistofactivepeerswithcolorinformation.
Thejoiningpeerthentriestocreateconnectionstothediffer-entcolorpeersinthelist.
Insuchaway,allthepeersformabipartiteoverlay,inwhicharedpeerwillonlyhavewhitepeersasitsdirectneighbors,andviceversa.
Phase2:neighbordistanceprobingandreportingbywhitepeers.
Weusenet-workdelaybetweentwopeersasametricformeasuringthetrafficcostbetweenpeers.
WemodifytheLimewireimplementationofGnutella0.
6P2Pprotocol[3]byaddingoneroutingmessagetypeforapeertoprobethelinkcosttoitsneighbors.
Eachwhitepeerbroadcastthismessageonlytoitsimmediatelogicalneighbors,formsaneighborcosttable,andsendsthistabletoallitsredneighbors.
Fig.
2.
AnexampleofSBOoperations1CurrentimplementationofNTPversion4.
1.
1inpublicdomaincanreachthesynchronizationaccuracydownto7.
5milliseconds[5].
Anotherapproachistousedistancetomeasurethecommunicationcost,suchasthenumberofhopsweightedbyindividualchannelbandwidth.
EfficientGnutella-likeP2POverlayConstruction151Phase3:forwardingconnectionscomputingbyredpeers.
Basedontheobtainedneighborcosttables,aminimumspanningtree(MST)canbebuiltbyeachredpeer,suchasPinfig.
2-(b).
SincearedpeerbuildsaMSTinatwo-hopdiameter,awhitepeerdoesnotneedtobuildaMST.
ThethicklinesintheMSTareselectedasfor-wardingconnections(FC),whilethethinlinesarenon-forwardingconnections(NFC).
QueriesareforwardedonlyalongtheFCs.
Phase4:directneighborreplacementbywhitepeers.
Afterphase3whereaMSTwithintwohopsdistanceisconstructed,aredpeerPisabletosenditsqueriestoallthepeerswithinthisrange.
Somewhitepeersbecomenon-forwardingneighbors,suchasEinFig.
2.
Inthiscase,forpeerE,Pisnolongeritsneighbor.
Inthephaseofdirectneighborreplacement,anon-forwardingneighbor,E,willtrytofindanotherredpeerbeingtwohopsawayfromPtoreplacePasitsnewneighbor.
5PerformanceEvaluationToevaluatetheeffectivenessofLTMandSBO,wegeneratebothphysicalnetworktopologiesandlogicaltopologiesinoursimulation.
ThephysicaltopologyshouldrepresenttherealtopologywithInternetcharacteristics.
Thelogicaltopologyrepre-sentstheoverlayP2Ptopologybuiltontopofthephysicaltopology.
AllP2Pnodesareinasubsetofnodesinthephysicaltopology.
Inourfirstsimulation,westudytheeffectivenessofLTMandSBOinastaticP2Penvironmentwherethe8,000peersdonotjoinandleavethesystem.
Figures3and4showthetrafficcostreductionofLTMandSBO,respectively.
Inthesefigures,thecurveof'cn-neigh'showstheaveragetrafficcostcausedbyaquerytocoverthewholenetworkandtheaveragenumberoflogicalneighborsisdenotedascn.
WecanseethatthetrafficcostdecreaseswhenLTMandSBOareconductedmultipletimes.
Theybothreachathresholdafterseveralstepsofoptimization.
LTMmayreducetrafficcostbyaround80-85%whileSBOreducestrafficcostbetween85%and90%.
However,LTMconvergesinaround2-3stepswhileSBOneeds4-5steps.
Thesimu-lationresultsinFig.
5andFig.
6showthatLTMreducesresponsetimebymorethan60%in3stepsbutSBOneeds8stepstoreduce60%oftheresponsetimeinastaticenvironment.
02468100102030405060708090100LTMoptimization(steps)Averagetrafficcostperquery(105)4neigh6neigh8neigh10neigh24681012140102030405060708090100SBOoptimizationstepsTrafficcostperquery(105)10neighbors8neighbors6neighbors4neighborsFig.
3.
Trafficreductionvs.
optimizationstepinLTMFig.
4.
Trafficreductionvs.
optimizationstepinSBO152Y.
Liuetal.
02468108101214161820222426LTMoptimization(steps)Averageresponsetimeperquery4neigh6neigh8neigh10neigh02468101268101214161820222426SBOoptimization(steps)averageresponsetimeperquery4neigh6neigh8neigh10neighFig.
5.
AverageResponsetimevs.
opt.
stepinLTMFig.
6.
AverageResponsetimevs.
opt.
stepinSBO510152025300102030405060Queries(105)averagetrafficcostperquery(105)Gnutella-likeLTMSBO510152025300510152025Queries(105)Responese-timeperqueryGnutella-likeLTMSBOFig.
7.
AveragetrafficcostcomparisonofLTMandSBOinadynamicP2PenvironmentFig.
8.
AverageresponsetimecomparisonofLTMandSBOinadynamicP2PenvironmentP2Pnetworksarehighlydynamicwithpeersjoiningandleavingfrequently.
Theobservationsin[15]haveshownthatover20%ofthelogicalconnectionsinaP2Plast1minuteorless,andaround60%oftheIPaddresseskeepactiveinFastTrackfornomorethan10minuteseachtimeaftertheyjointhesystem.
WefurtherevaluatetheeffectivenessofLTMandSBOindynamicP2Psystems.
Inthissimulation,weassumethatpeeraveragelifetimeinaP2Psystemis10minutes;0.
3queriesareis-suedbyeachpeerperminute.
Fig.
7showstheaveragetrafficcostperqueryofGnutella-likeP2Psystems,LTMenabledGnutellaandSBOenabledGnutella.
Herethetrafficcostincludesalltheoverheadneededintheoptimizationsteps.
SBOandLTMdroptheaveragecostby85%and80%,respectively.
Fig.
8plotstheaveragequeryresponsetimeofeachsystem.
Withthehelpofourcarefullydesignedtheop-timizationalgorithms,theLTMreducestheresponsetimeto30%andSBOdecreasetheresponsetimeto35%.
EfficientGnutella-likeP2POverlayConstruction1536ConclusionWehaveevaluatedourproposedLTMandSBOoverlaytopologymatchalgorithmsinstaticaswellasdynamicenvironments.
Bothschemesarefullydistributedandscalableinthateachpeercanconductthealgorithmindependentlywithoutrequestinganyglobalknowledge.
TheotherstrengthofLTMandSBOisthattheyarecomple-mentarytocache-basedandforwarding-basedapproachessothatfurtherimprove-mentscanbemadewhendeployedtogether.
LTMshowsitsadvantagesinconvergentspeedbutslightlycreatesmoreoverheadthanSBO.
Italsodemandssynchronizedtimeamongpeers,whichimpliesthatanadditionaloverheadisneededtorunaclocksynchronizationprotocol,suchasNTP.
References[1]Fasttrack,http://www.
fasttrack.
nu[2]Gnutella,http://gnutella.
wego.
com/[3]TheGnutellaprotocolspecification0.
6,http://rfc-gnutella.
sourceforge.
net[4]KaZaA,http://www.
kazaa.
com[5]NTP:TheNetworkTimeProtocol,http://www.
ntp.
org/[6]Y.
Chawathe,S.
Ratnasamy,L.
Breslau,N.
Lanham,andS.
Shenker,"MakingGnutella-likeP2PSystemsScalable,"ProceedingsofACMSIGCOMM,2003.
[7]Y.
Chu,S.
G.
Rao,andH.
Zhang,"ACaseforEndSystemMulticast,"ProceedingsofACMSIGMETRICS,2000.
[8]Y.
Liu,X.
Liu,L.
Xiao,L.
M.
Ni,andX.
Zhang,"Location-AwareTopologyMatchinginUnstructuredP2PSystems,"ProceedingsofIEEEINFOCOM,2004.
[9]Y.
Liu,L.
Xiao,andL.
M.
Ni,"BuildingaScalableBipartiteP2POverlayNetwork,"Proceedingsof18thInternationalParallelandDistributedProcessingSymposium(IPDPS),2004.
[10]Y.
Liu,Z.
Zhuang,L.
Xiao,andL.
M.
Ni,"ADistributedApproachtoSolvingOverlayMismatchProblem,"Proceedingsofthe24thInternationalConferenceonDistributedComputingSystems(ICDCS),2004.
[11]D.
A.
MenasceandL.
Kanchanapalli,"ProbabilisticScalableP2PResourceLocationServices,"ACMSIGMETRICSPerformanceEvaluationReview,vol.
30,pp.
48-58,2002.
[12]M.
Ripeanu,A.
Iamnitchi,andI.
Foster,"MappingtheGnutellaNetwork,"IEEEInternetComputing,2002.
[13]Ritter,WhyGnutellaCan'tScale.
No,Really,http://www.
tch.
org/gnutella.
html[14]S.
Saroiu,K.
P.
Gummadi,R.
J.
Dunn,S.
D.
Gribble,andH.
M.
Levy,"AnAnalysisofInternetContentDeliverySystems,"Proceedingsofthe5thSymposiumonOperatingSys-temsDesignandImplementation,2002.
[15]S.
SenandJ.
Wang,"AnalyzingPeer-to-peerTrafficAcrossLargeNetworks,"Proceed-ingsofACMSIGCOMMInternetMeasurementWorkshop,2002.
[16]C.
Wang,L.
Xiao,Y.
Liu,andP.
Zheng,"DistributedCachingandAdaptiveSearchinMultilayerP2PNetworks,"Proceedingsofthe24thInternationalConferenceonDistrib-utedComputingSystems(ICDCS),2004.
[17]Z.
Xu,C.
Tang,andZ.
Zhang,"BuildingTopology-awareOverlaysUsingGlobalSoft-state,"Proceedingsofthe23rdInternationalConferenceonDistributedComputingSys-tems(ICDCS),2003.