SurveyofResearchtowardsRobustPeer-to-PeerNetworks:
SearchMethods
JOHNRISSONANDTIMMOORS
UniversityofNewSouthWales
The pace of research on peer-to-peer (P2P) networking in the last five years warrants a
criticalsurvey.P2Phasthemakingsofadisruptivetechnology-itcanaggregateenormous
storage and processing resources while minimizing entry and scaling costs. The key to
realizingthispotentialinapplicationsotherthanfilesharingisrobustness.
TheentirebodyofP2Presearchcanbedivided intofourgroups- search,storage,security
andapplications.Althoughwebrieflyelaborateonthisoveralltaxonomy,themainfocusof
thissurveyisP2Psearchmethods.WesummarizeandcompareP2Pindexingmethods,from
distributed hash tables to systems for keyword lookup, information retrieval and data
management. We canvass the early work to optimize various types of queries over P2P
indexes. Throughout, we emphasize robustness considerations and identify open research
issues.Our ambition here is to baseline researchonP2P search methods and assist efforts
towardmoredependable,adaptableP2Psystems.
RISSON,J.,MOORS,T.Surveyofresearchtowardsrobustpeer-to-peernetworks:searchmethods,TechnicalReportUNSW-
EE-P2P-1-1,UniversityofNewSouthWales,Sydney,Australia,(September2004),awaitingpublication.
Authorsaddresses:J.RissonandT.Moors,Dept.ofElectricalEngineering,UniversityofNewSouthWales,Sydney,NewSouth
Wales,2052,Australia,e-mail:jr@tuffit.com,t.moors@unsw.edu.au
2�� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � Risson�and�Moors�
UNSW-EE-P2P-1-1.�
Table�of�Contents�
1.� Introduction.................................................................. 2�
1.1.� Related�Disciplines ............................................ 2�
1.2.� Structured�and�Unstructured�Routing ................ 4�
1.3.� Indexing�and�Searching ..................................... 5�
2.� Index�Types.................................................................. 5�
2.1.� Local�Index........................................................ 6�
2.2.� Central�Index ..................................................... 7�
2.3.� Distributed�Index ............................................... 7�
3.� Semantic-Free�Index .................................................... 8�
3.1.� Plaxton�Trees ................................................... 10�
3.2.� Rings................................................................ 11�
3.3.� Tori .................................................................. 11�
3.4.� Butterflies ........................................................ 12�
3.5.� de�Bruijn�Graphs.............................................. 12�
3.6.� Skip�Graphs ..................................................... 13�
4.� Semantic�Index........................................................... 14�
4.1.� Keyword�Lookup............................................. 14�
4.2.� Peer�Information�Retrieval .............................. 16�
4.3.� Peer�Data�Management.................................... 18�
5.� Search......................................................................... 21�
5.1.� Range�Queries ................................................. 21�
5.2.� Multi-Attribute�Queries ................................... 23�
5.3.� Join�Queries ..................................................... 24�
5.4.� Aggregation�Queries........................................ 24�
6.� Conclusions................................................................ 25�
7.� Bibliography .............................................................. 26�
�
1.� Introduction�
Peer-to-peer�(P2P)�networks�are�those�that�exhibit�three�
characteristics:� self-organization,� symmetric�
communication� and� distributed� control� (Roussopoulos,�
Baker� et� al.� 2004).� A� self-organizing� P2P� network�
“automatically� adapts� to� the� arrival,� departure� and�
failure� of� nodes”� (Rowstron� and� Druschel� 2001a).�
Communication� is� symmetric� in� that� peers� act� as� both�
clients� and� servers.� It� has� no� centralized� directory� or�
control�point.�USENET�servers�or�BGP�peers�have�these�
traits�(Yeager�and�Bhattacharjee�2003)�but�the�emphasis�
here� is� on� the� flurry� of� research� since� 2000.� Leading�
examples� include� Gnutella� (Klingberg� and� Manfredi�
2002),� Freenet� (Clarke� 1999),� Pastry� (Rowstron� and�
Druschel� 2001a),� Tapestry� (Zhao,� Kubiatowicz� et� al.�
2001),� Chord� (Stoica,� Morris� et� al.� 2001),� the� Content�
Addressable�Network�(CAN)�(Ratnasamy,�Francis�et�al.�
2001),� pSearch� (Tang,� Xu� et� al.� 2002b)� and� Edutella�
(Nejdl,� Decker� et� al.� 2003).�Some� have� suggested� that�
peers� are� inherently� unreliable� (Aberer� and� Hauswirth�
2001).� Others� have� assumed� well-connected,� stable�
peers�(Zhou�and�van�Renesse�2004).�
�
This� critical� survey� of� P2P� academic� literature� is�
warranted,�given�the�intensity�of�recent�research.�At�the�
time� of� writing,� one� research� database� lists� over� 5,800�
P2P�publications�("Citeseer�Scientific�Literature�Digital�
Library"�2004).�One�vendor�surveyed�P2P�products�and�
deployments� (Milojicic,�Kalogeraki� et� al.� 2002).�There�
is�also�a�tutorial�survey�of�leading�P2P�systems�(Aberer�
and� Hauswirth� 2002).� DePaoli� and� Mariani� recently�
reviewed� the�dependability� of� some�early�P2P� systems�
at� a� high� level� (DePaoli� and� Mariani� 2004).� The� need�
for� a� critical� survey� was� flagged� in� the� peer-to-peer�
research� group� of� the� Internet� Research� Task� Force�
(IRTF)�(Yeager�2003).
�
The� entire� body� of� P2P� research� literature� can� be�
divided� along� four� lines:� search,� security,� storage� and�
applications.� The� search� and� security� classifications�
have� been� used� by� Daswani� et� al� (Daswani,� Garcia-
Molina� et� al.� 2003).� In� Figure� 1,� we� elaborate� on� this�
taxonomy�and� give� a� representative� list� of� papers.�The�
list� is� by� no� means� comprehensive.� In� this� survey,� we�
concentrate� on� search� methods,� considering� semantic�
and� semantic-free� ways� of� indexing� information� in� a�
P2P� network.� We� also� canvass� early� work� to� optimize�
various�query�types�over�P2P�indexes.�Storage,�security�
and�application�aspects�are�deferred.�
�
Our� initial� objective� for� this� paper� was� to� answer� the�
question,� “How� robust� are� P2P� search� networks?”� A�
good� proportion� of� the� paper� first� addresses� the�
supporting� question,� “How� do� P2P� search� networks�
work?”�This�foundation�is�important�given�the�pace�and�
breadth�of�research.�Where�it�is�available,�we�emphasize�
work� on� robustness� and� flush� out� promising� lines� of�
investigation.�
�
P2P� is� potentially� a� disruptive� technology� with�
numerous� applications,� but� this� potential� will� not� be�
realized� unless� it� is� demonstrated� to� be� robust.� A�
massively� distributed� search� technique� may� yield�
numerous� practical� benefits� for� applications�
(Balakrishnan,�Kaashoek�et�al.�2003).�A�P2P�system�has�
potential� to� be� more� dependable� than� architectures�
relying�on�a�small�number�of�centralized�servers.�It�has�
potential�to�evolve�better�from�small�configurations�-�the�
capital� outlays� for� high� performance� servers� can� be�
reduced� and� spread� over� time� if� a� P2P� assembly� of�
general� purpose� nodes� is� used.� A� similar� argument�
motivated�the�deployment�of�distributed�databases�–�one�
thousand,� off-the-shelf� PC� processors� are� more�
powerful� and� much� less� expensive� than� a� large�
mainframe� computer� (Kossmann� 2000).� Storage� and�
processing�can�be�aggregated�to�achieve�massive�scale.�
Wasteful�partitioning�between�servers�or�clusters�can�be�
avoided.� As� Gedik� and� Liu� put� it,� if� P2P� is� to� find� its�
way� into� applications� other� than� simple� file� sharing,�
then� reliability� needs� to� be� addressed� (Gedik� and� Liu�
2003b).�
�
1.1.� Related�Disciplines�
Peer-to-peer� research�draws�upon�numerous�distributed�
systems� disciplines.� Networking� researchers� will�
recognize� familiar� issues� of� naming,� routing� and�
congestion�control.�P2P�designs�need�to�address�routing�
and� security� issues� across� network� region� boundaries�
(Sollins� 2003).� Networking� research� has� traditionally�
been� host-centric.� The� web’s� Universal� Resource�
Identifiers� are� naturally� tied� to� specific� hosts,� making�
object�mobility�a�challenge�(Walfish,�Balakrishnan�et�al.�
2004).�
A�Survey�of�Research�towards�Robust�Peer-to-Peer�Networks:�Search�Methods�� � � � � � � � � � � � �3�
UNSW-EE-P2P-1-1�
�
Taxonomy SelectedReferences
Search (Yang� and� Garcia-Molina� 2002b;� Yang� and� Garcia-Molina� 2002a;� Yang� and� Garcia-Molina� 2002c;� Balakrishnan,�
Kaashoek�et�al.�2003;�Bawa,�Sun�et�al.�2003;�Cooper�and�Garcia-Molina�2003b;�Daswani,�Garcia-Molina�et�al.�2003;�
Gummadi,�Gummadi�et�al.�2003;�Hellerstein�2003;�Huebsch,�Hellerstein�et�al.�2003;�Shi,�Guangwen�et�al.�2004)�
� Semantic-Free�Indexes�
� ���Plaxton�Trees�
� ���Rings�
� ���Tori�
� ���Butterflies�
� ���de�Bruijn�Graphs�
� ���Skip�Graphs�
(Devine�1993;�Litwin,�Niemat�et�al.�1993;�Litwin,�Neimat�et�al.�1996;�Karger,�Lehman�et�al.�1997;�Plaxton,�Rajaraman�
et�al.�1997;�Rowstron�and�Druschel�2001a;�Stoica,�Morris�et�al.�2001;�Zhao,�Kubiatowicz�et�al.�2001;�Harvey,�Dunagan�
et�al.�2002;�Li�and�Plaxton�2002;�Malkhi,�Naor�et�al.�2002;�Maymounkov�and�Mazieres�2002;�Ratnasamy,�Shenker�et�
al.� 2002;� Zhao,� Duan� et� al.� 2002;� Aberer,� Cudre-Mauroux� et� al.� 2003;� Aspnes� and� Shah� 2003;� Cates� 2003;� Gupta,�
Birman� et� al.� 2003;� Harvey,� Jones� et� al.� 2003a;� Kaashoek� and� Karger� 2003;� Loguinov,� Kumar� et� al.� 2003;� Rhea,�
Roscoe� et� al.� 2003;� Stoica,� Morris� et� al.� 2003;� Ganesan,� Krishna� et� al.� 2004;� van� Renesse� and� Bozdog� 2004;� Zhao,�
Huang�et�al.�2004)�
� Semantic�Indexes�
� ���Keyword�Lookup�
� ���Peer�Information�Retrieval�
� ���Peer�Data�Management�
(Clarke,� Sandberg� et� al.� 2001;� Jovanovic� 2001;� Babaoglu,� Meling� et� al.� 2002;� Kalogaraki,� Gunopulos� et� al.� 2002;�
Klingberg� and� Manfredi� 2002;� Lv,� Cao� et� al.� 2002;� Lv,� Ratnasamy� et� al.� 2002;� Ripeanu,� Iamnitchi� et� al.� 2002;�
Schlosser,�Sintek�et� al.�2002;�Sunaga,� Takemoto�et� al.�2002;� Bawa,�Manku�et� al.�2003;�Chawathe,�Ratnasamy�et� al.�
2003;� Joseph� and� Hoshiai� 2003;� Nejdl,� Siberski� et� al.� 2003;� Tatarinov,� Mork� et� al.� 2003;� Yang� and� Garcia-Molina�
2003;�Zhang,�Shi�et�al.�2003;�Cai�and�Frank�2004;�Loo,�Huebsch�et�al.�2004b;�Tempich,�Staab�et�al.�2004)��
� Search�
� ���Range�Queries�
� ���Multi-Attribute�Queries�
� ���Join�Queries�
� ���Aggregation�Queries�
� ���Continuous�Queries�
� ���Recursive�Queries�
� ���Adaptive�Queries�
(Litwin,�Neimat�et�al.�1994;�Litwin�and�Neimat�1996;�Avnur�and�Hellerstein�2000;�Aberer�2002b;�Andrzejak�and�Xu�
2002;�Harren,�Hellerstein�et�al.�2002;�Hodes,�Czerwinski�et�al.�2002;�Aberer,�Datta�et�al.�2003;�Albrecht,�Arnold�et�al.�
2003;�Aspnes�and�Shah�2003;�Bhagwan,�Varghese�et�al.�2003;�Cai,�Frank�et�al.�2003;�Daswani,�Garcia-Molina�et�al.�
2003;�Gedik�and�Liu�2003b;�Gedik�and�Liu�2003a;�Gupta,�Agrawal�et�al.�2003;�Harvey,�Jones�et�al.�2003a;�Hellerstein�
2003;� Huebsch,�Hellerstein�et� al.�2003;�Montresor,� Jelasity�et� al.�2003;�Ratnasamy,�Francis�et� al.�2003;�Triantafillou�
and� Pitoura� 2003;� Tsangou,� Ndiaye� et� al.� 2003;� van� Renesse,� Birman� et� al.� 2003;� Zhang,� Shi� et� al.� 2003;� Albrecht,�
Arnold�et� al.�2004;� Aspnes,�Kirsch�et� al.� 2004;� Bawa,�Gionis�et� al.�2004;� Bharambe,�Agrawal�et� al.�2004;�Ganesan,�
Bawa�et�al.�2004;�Jelasity,�Kowalczyk�et�al.�2004;�Loo,�Huebsch�et�al.�2004a;�Ramabhadran,�Ratnasamy�et�al.�2004;�
Schmidt� and� Parashar� 2004;� Tanin,� Harwood� et� al.� 2004;� van� Renesse� and� Bozdog� 2004;� Yalagandula� and� Dahlin�
2004)�
Storage �
� Consistency�&�Replication�
� ���Eventual�consistency�
� ���Trade-offs…�
(Lomet�1996;�Cohen�and�Shenker�2002b;�Cohen�and�Shenker�2002a;�Weatherspoon�and�Kubiatowicz�2002b;�Geels�and�
Kubiatowicz� 2003;�On,�Schmitt� et� al.�2003;�Gopalakrishnan,�Silaghi�et� al.�2004b)� (Kubiatowicz,� Bindel�et� al.�2000;�
Rhea,�Wells�et�al.�2001;�Rowstron�and�Druschel�2001b;�Adya,�Wattenhofer�et�al.�2002;�Lin,�Lian�et�al.�2004)�
� Distribution�
� ��Epidemics,�Bloom�Filters�
(Bloom� 1970;� Bailey�1975;�Demers,�Greene�et� al.�1987;�Gupta,� Birman�et� al.�2001;� Hodes,�Czerwinski�et� al.�2002;�
Mohan� and� Kalogaraki� 2002;� Weatherspoon� and� Kubiatowicz� 2002a;� Aberer,� Cudre-Mauroux� et� al.� 2003;� Birman�
2003;�Costa,�Migliavacca�et�al.�2003;�Eugster,�Guerraoiu�et�al.�2003;�Ganesh,�Kermarrec�et�al.�2003;�Gupta,�Birman�et�
al.�2003;�Koloniari,�Petrakis�et�al.�2003;�Koloniari�and�Pitoura�2003;�van�Renesse,�Birman�et�al.�2003;�Vogels,�Renesse�
et�al.�2003;�Voulgaris�and�van�Steen�2003;�Birman�and�Gupta�2004;�Costa,�Migliavacca�et�al.�2004;�Eugster,�Guerraoiu�
et�al.�2004;�Gupta�2004;�Koloniari�and�Pitoura�2004)�
� Fault�Tolerance�
� ���Erasure�Coding�
� ���Byzantine�Agreement�…�
(Byers,�Considine�et�al.�2002;�Rodrigues,�Liskov�et�al.�2002;�Weatherspoon�and�Kubiatowicz�2002b;�Weatherspoon,�
Moscovitz�et�al.�2002;�Castro,�Rodrigues�et�al.�2003;�Cates�2003;�Maymounkov�and�Mazieres�2003;�Naor�and�Wieder�
2003b;�Plank,�Atchley�et�al.�2003;�Krohn,�Freedman�et�al.�2004)�
� Locality� (Gummadi,�Saroui�et�al.�2002;�Hildrum,�Kubiatowicz�et�al.�2002;�Keleher,�Bhattacharjee�et�al.�2002;�Li�and�Plaxton�
2002;�Ng�and�Zhang�2002;�Zhao,�Duan�et�al.�2002;�Freedman�and�Mazieres�2003;�Gummadi,�Gummadi�et�al.�2003;�
Harvey,�Jones�et�al.�2003b;�Massoulie,�Kermarrec�et�al.�2003;�Pias,�Crowcroft�et�al.�2003;�Ruhl�2003;�Sollins�2003;�
Awerbuch� and� Scheideler� 2004a;� Cox,� Dabek� et� al.� 2004;� Dabek,� Cox� et� al.� 2004;� Dabek,� Li� et� al.� 2004;� Fessant,�
Handurukande� et� al.� 2004;� Hildrum,� Krauthgamer� et� al.� 2004;� Karger� and� Ruhl� 2004a;� Liu,� Liu� et� al.� 2004;� Lua,�
Crowcroft�et�al.�2004;�Mislove�and�Druschel�2004;�Zhang,�Zhang�et�al.�2004)�
� Load�Balancing� (Aberer,� Datta� et� al.� 2003;� Adler,� Halperin� et� al.� 2003;� Baquero� and� Lopes� 2003;� Byers,� Considine� et� al.� 2003;�
Kaashoek�and�Karger�2003;�Rao,�Lakshminarayanan�et�al.�2003;�Ruhl�2003;�Aspnes,�Kirsch�et�al.�2004;�Castro,�Lee�et�
al.� 2004;� Gao� and� Steenkiste� 2004;� Gopalakrishnan,� Silaghi� et� al.� 2004a;� Karger� and� Ruhl� 2004b;� Karger� and� Ruhl�
2004c;�Manku�2004;�Stavrou,�Rubenstein�et�al.�2004;�Wang,�Zhang�et�al.�2004)�
Security �
� Character�
� ���Identity�
� ���Reputation�and�Trust�
� ���Incentives�
(Damiani,� di� Vimercati� et� al.� 2002;� Blaze,� Feigenbaum� et� al.� 2003;� Buragohain,� Agrawal� et� al.� 2003;� Caronni� and�
Waldvogel�2003;�Schneidman�and�Parkes�2003;�Anagnostakis�and�Greenwald�2004;�Feldman,�Lai�et�al.�2004;�Marti,�
Ganesan�et�al.�2004;�Papaioannou�and�Stamoulis�2004;�Selcuk,�Uzun�et�al.�2004;�Sieka,�Kshemkalyani�et�al.�2004)�
� Goals�
� ���Availability�
� ���Authenticity�
� ���Anonymity�
� ���Access�Control�
� ���Fair�Trading�
(Clarke,� Sandberg� et� al.� 2001;� Daswani� and� Garcia-Molina� 2002;� Fiat� and� Saia� 2002;� Freedman� and� Morris� 2002;�
Hazel�and�Wiley�2002;�Serjantov�2002;�Sit�and�Morris�2002;�Bawa,�Sun�et�al.�2003;�Cox�and�Noble�2003;�Daswani,�
Garcia-Molina�et�al.�2003;�Ngan,�Wallach�et�al.�2003;�Ramaswamy�and�Liu�2003;�Singh�and�Liu�2003;�Surridge�and�
Upstill�2003;�Berket,�Essiari�et�al.�2004;�Feldman,�Papadimitriou�et�al.�2004;�Josephson,�Sirer�et�al.�2004;�O'Donnel�and�
Vaikuntanathan�2004)�
Applications (Li�2002;�Considine,�Walfish�et�al.�2003;�Karp,�Ratnasamy�et�al.�2004;�Roussopoulos,�Baker�et�al.�2004)�
� Memory�
� ���File�Systems�
� ���Web�
� ���Content�Delivery�Networks�
� ���Directories�
�� ���Service�Discovery�
� ���Publish�/�Subscribe�..�
(Dabek,�Kaashoek�et� al.�2001;�Gold�and� Tidhar�2001;� Kan�and� Faybishenko�2001;�Annexstein,� Berman�et� al.�2002;�
Kangasharju,� Ross� et� al.� 2002;� Muthitacharoen,� Morris� et� al.� 2002b;� Muthitacharoen,� Morris� et� al.� 2002a;� Saroiu,�
Gummadi� et� al.� 2002b;� Mislove,� Post� et� al.� 2003;� Fessant,� Handurukande� et� al.� 2004)� (Iyer,� Rowstron� et� al.� 2002;�
Bawa,�Bayardo�et�al.�2003;�Li,�Loo�et�al.�2003;�Freedman,�Freudenthal�et�al.�2004;�Loo,�Krishnamurthy�et�al.�2004)�
(Cuenca-Acuna,�Peery�et�al.�2002;�Junginger�and�Lee�2004;�van�Renesse�and�Bozdog�2004)�(Balazinska,�Balakrishnan�
et�al.�2002;�Chander,�Dawson�et�al.�2002;�Cox,�Muthitacharoen�et�al.�2002;�Hodes,�Czerwinski�et�al.�2002;�Iamnitchi�
2003;�Awerbuch�and�Scheideler�2004b;�Walfish,�Balakrishnan�et�al.�2004)�
� Intelligence�
� ���GRID�
� ���Security…�
(Hoschek�2002;�Iamnitchi,�Foster�et�al.�2002;�Foster�and�Iamnitchi�2003;�Lo,�Zappala�et�al.�2004)�(Ajmani,�Clarke�et�al.�
2002;�Aberer,�Datta�et�al.�2004)�
� Communication�
� ���Multicasting�
� ���Streaming�Media�
� ���Mobility�
� ���Sensors�…�
�
(Zhuang,�Zhao�et�al.�2001;�Castro,�Druschel�et�al.�2002;�Halepovic�and�Deters�2002;�Lienhart,�Holliman�et�al.�2002;�
Ratnasamy,�Karp�et�al.�2002;�Stoica,�Adkins�et�al.�2002;�Castro,�Druschel�et�al.�2003;�Demirbas�and�Ferhatosmanoglu�
2003;�Hefeeda,�Habib�et�al.�2003;�Ratnasamy,�Karp�et�al.�2003;�Sasabe,�Wakamiya�et�al.�2003;�van�Renesse,�Birman�et�
al.�2003;�Voulgaris�and�van�Steen�2003;�Zhang�and�Hu�2003;�Hellerstein�and�Wang�2004;�Hsieh�and�Sivakumar�2004;�
Nicolosi� and� Mazieres� 2004;� Padmanabhan,� Wang� et� al.� 2004;� Sit,� Dabek� et� al.� 2004;� Tran,� Hua� et� al.� 2004;�
Wawrzoniak,�Peterson�et�al.�2004;�Zhou�and�van�Renesse�2004)�
Figure1ClassificationofP2PResearchLiterature
4�� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � Risson�and�Moors�
UNSW-EE-P2P-1-1.�
�
P2P� work� is� data-centric� (Shenker� 2003).� P2P� systems�
for�dynamic�object� location�and�routing�have�borrowed�
heavily�from�the�distributed�systems�corpus.�Some�have�
used� replication,� erasure� codes� and� Byzantine�
agreement� (Rhea,�Wells�et� al.�2001).�Others�have�used�
epidemics� for� durable� peer� group� communication�
(Gupta,�Birman�et�al.�2003).�
�
Similarly,� P2P� research� is� set� to� benefit� from� database�
research� (Gribble,� Halevy� et� al.� 2001).� Database�
researchers� will� recognize� the� need� to� reapply� Codd’s�
principle� of� physical� data� independence,� that� is,� to�
decouple�data�indexes�from�the�applications�that�use�the�
data� (Hellerstein� 2003).� It� was� the� invention� of�
appropriate� indexing� mechanisms� and� query�
optimizations�that�enabled�data�independence.�Database�
indexes� like� B+� trees� have� an� analog� in� P2P’s�
distributed� hash� tables� (DHTs).� Wide-area,� P2P� query�
optimization� is� a� ripe,� but� challenging,� area� for�
innovation.�
�
More� flexible� distribution� of� objects� comes� with�
increased� security� risks.� There� are� opportunities� for�
security� researchers� to� deliver� new� methods� for�
availability,� file� authenticity,� anonymity� and� access�
control�(Daswani,�Garcia-Molina�et�al.�2003).�Proactive�
and� reactive�mechanisms�are�needed� to�deal�with� large�
numbers� of� autonomous,� distributed� peers.� To� build�
robust� systems� from� cooperating� but� self-interested�
peers,�issues�of�identity,�reputation,�trust�and�incentives�
need�to�be�tackled.�
�
Possibly�the�largest�portion�of�P2P�research�has�majored�
on� basic� routing� structures� (Balakrishnan,� Kaashoek� et�
al.� 2003),� where� research� on� algorithms� comes� to� the�
fore.� Should� the� overlay� be� “ structured” � or�
“ unstructured” ?� Are� the� two� approaches� competing� or�
complementary?� Comparisons� of� the� “ structured” �
approaches� –� hypercubes,� rings,� toroids,� butterflies,� de�
Bruijn� and� skip� graphs� –� have� weighed� the� amount� of�
routing�state�per�peer�and� the�number�of� links�per�peer�
against� overlay� hop-counts.� While� “ unstructured” �
overlays�initially�used�blind�flooding�and�random�walks,�
overheads� usually�