nach oben

Peer-to-Peer Networking and Applications

Erschienen in:

01.12.2009

Structured P2P technologies for distributed command and control

verfasst von: Daniel R. Karrels, Gilbert L. Peterson, Barry E. Mullins

Erschienen in: Peer-to-Peer Networking and Applications | Ausgabe 4/2009

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The utility of Peer-to-Peer (P2P) systems extends far beyond traditional file sharing. This paper provides an overview of how P2P systems are capable of providing robust command and control for Distributed Multi-Agent Systems (DMASs). Specifically, this article presents the evolution of P2P architectures to date by discussing supporting technologies and applicability of each generation of P2P systems. It provides a detailed survey of fundamental design approaches found in modern large-scale P2P systems highlighting design considerations for building and deploying scalable P2P applications. The survey includes unstructured P2P systems, content retrieval systems, communications structured P2P systems, flat structured P2P systems and finally Hierarchical Peer-to-Peer (HP2P) overlays. It concludes with a presentation of design tradeoffs and opportunities for future research into P2P overlay systems.

Vorheriger Artikel Gossiping protocols for hybrid grid resource scheduling

Nächster Artikel Dealing with network partitions in structured overlay networks

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Livelock in a dynamic routing management system can occur when one agent modifies a route to redirect traffic to another section of the network. If the agent responsible for the targeted portion of the network is unaware of the change, it may reverse the effect by redirecting traffic back through the previous route. This process can occur very quickly with software agents, thus leading to a deadlock of live nodes.

Arguments persist about the true nature of BitTorrent’s topology. For the purposes of this document, we consider BitTorrent to be a combination of structured and unstructured ideas.

Note: It may not be the case that the dataset itself is semantically random. Instead, the probability of existence of a data item in a network, the probability of a search query from a source reaching the node that stores the desired data item, and the differing semantics used to store and query items may cause searches to appear as probabilistic to an outside observer.

Adar E, Huberman BA (2000) Free riding on gnutella. First Monday 5

Clarke I, Sandberg O, Wiley B, Hong TW (2001) Freenet: a distributed anonymous information storage and retrieval system. Lect Notes Comput Sci 2009:46–63CrossRef

Gerkey BP, Mataric MJ (2004) A formal analysis and taxonomy of task allocation in multi-robot systems. Int J Rob Res 23:939–954CrossRef

Chalupsky H, Gil Y, Knoblock CA, Lerman K, Oh J, Pynadath DV, Russ TA, Tambe M (2001) Electric elves: applying agent technology to support human organizations. In: Proceedings of the thirteenth conference on innovative applications of artificial intelligence conference. AAAI, Menlo Park, pp 51–58

Stanney KM, Mourant RR, Kennedy RS (1998) Human factors issues in virtual environments: a review of the literature. Presence Teleoper Virtual Environ 7(4):327–351CrossRef

Barella A, Carrascosa C, Botti V, Martí M (2007) Multi-agent systems applied to virtual environments: a case study. In: VRST ’07: proceedings of the 2007 ACM symposium on virtual reality software and technology. ACM, New York, pp 237–238CrossRef

Tao N, Baxter J, Weaver L (2001) A multi-agent policy-gradient approach to network routing. In: ICML ’01: proceedings of the eighteenth international conference on machine learning. Morgan Kaufmann, San Francisco, pp 553–560

Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms, 2nd edn. MIT, CambridgeMATH

Yang B, Garcia-Molina H (2003) Designing a super-peer network. icde. 00:49

10.

Milgram S (1967) The small world problem. Psychol Today (2):60–67

11.

Kleinberg J (2000) The small-world phenomenon: an algorithmic perspective. In: Proceedings of the 32nd ACM symposium on theory of computing. ACM, New York, pp 163–170

12.

Cao YU, Fukunaga AS, Kahng AB (1997) Cooperative mobile robotics: antecedents and directions. Auton Robots 4(1):7–23CrossRef

13.

Dudek G, Jenkin M, Milios E, Wilkes D (1996) A taxonomy for multi-agent robotics. Auton Robots 3:375–397

14.

Lua K, Crowcroft J, Pias M, Sharma R, Lim, S (2005) A survey and comparison of peer-to-peer overlay network schemes. Commun Surv Tutor IEEE 7:72–93CrossRef

15.

Rowstron AIT, Druschel P (2001) Pastry: scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In: Middleware ’01: proceedings of the IFIP/ACM international conference on distributed systems platforms heidelberg. Springer, London, pp 329–350

16.

Zhao B, Huang L, Stribling J, Rhea S, Joseph A, Kubiatowicz J (2004) Tapestry: a resilient global-scale overlay for service deployment. IEEE J Sel Areas Commun 22:41–53CrossRef

17.

Gummadi K, Gummadi R, Gribble S, Ratnasamy S, Shenker S, Stoica I (2003) The impact of dht routing geometry on resilience and proximity. In: SIGCOMM ’03: proceedings of the 2003 conference on applications, technologies, architectures, and protocols for computer communications. ACM, New York, pp 381–394CrossRef

18.

Gnutella (2009) Internet. http://gnutella.wego.com

19.

Cohen B. Bittorrent protocol specification v1.0. WWW

20.

Bustamante FE, Qiao Y (2008) Designing less-structured p2p systems for the expected high churn. IEEE/ACM Trans Netw 16(3):617–627CrossRef

21.

Loguinov D, Kumar A, Rai V, Ganesh S (2003) Graph-theoretic analysis of structured peer-to-peer systems: routing distances and fault resilience. In: SIGCOMM ’03: proceedings of the 2003 conference on applications, technologies, architectures, and protocols for computer communications. ACM, New York, pp 395–406CrossRef

22.

Li J, Stribling J, Morris R, Kaashoek MF (2005) Bandwidth-efficient management of dht routing tables. In: NSDI’05: proceedings of the 2nd conference on symposium on networked systems design & implementation. USENIX Association, Berkeley, pp 99–114

23.

Rhea S, Geels D, Roscoe T, Kubiatowicz J (2004) Handling churn in a dht. In: ATEC ’04: proceedings of the annual conference on USENIX annual technical conference. USENIX Association, Berkeley, pp 10–10

24.

Fiat A, Saia J (2002) Censorship resistant peer-to-peer content addressable networks. In: SODA ’02: proceedings of the thirteenth annual ACM-SIAM symposium on discrete algorithms. Society for Industrial and Applied Mathematics, Philadelphia, pp 94–103

25.

Ratnasamy S, Francis P, Handley M, Karp R, Schenker S (2001) A scalable content-addressable network. In: SIGCOMM ’01: proceedings of the 2001 conference on applications, technologies, architectures, and protocols for computer communications. ACM, New York, pp 161–172CrossRef

26.

Stoica I, Morris R, Karger D, Kaashoek F, Balakrishnan H (2001) Chord: a scalable peer-to-peer lookup service for internet applications. In: Proceedings of the 2001 ACM SIGCOMM conference. ACM, New York, pp 149–160

27.

Alima LO, Ghodsi A, Haridi S (2004) A framework for structured peer-to-peer overlay networks. Lect Notes Comput Sci 3267:223–250CrossRef

28.

Maymounkov P, Mazières D (2002) Kademlia: a peer-to-peer information system based on the xor metric. In: IPTPS ’01: revised papers from the first international workshop on peer-to-peer systems. Springer, London, pp 53–65

29.

Gupta I, Birman K, Linga P, Demers A, van Renesse R (2003) Kelips: building an efficient and stable P2P DHT through increased memory and background overhead. In: Proceedings of the 2nd international workshop on peer-to-peer systems (IPTPS ’03)

30.

Kaashoek MF, Karger DR (2003) Koorde: a simple degree-optimal distributed hash table. In: Proceedings of the 2nd international workshop on peer-to-peer systems (IPTPS ’03)

31.

Bharambe AR, Agrawal M, Seshan S (2004) Mercury: supporting scalable multi-attribute range queries. SIGCOMM Comput Commun Rev 34(4):353–366CrossRef

32.

Gupta A, Liskov B, Rodrigues R (2004) Efficient routing for peer-to-peer overlays. In: NSDI’04: proceedings of the 1st conference on symposium on networked systems design and implementation. USENIX Association, Berkeley, pp 9–9

33.

Aberer K (2001) P-grid: a self-organizing access structure for p2p information systems. In: CoopIS, pp 179–194

34.

Harvey NJA, Jones MB, Saroiu S, Theimer M, Wolman A (2003) Skipnet: a scalable overlay network with practical locality properties. In: USITS’03: proceedings of the 4th conference on USENIX symposium on internet technologies and systems. USENIX Association, Berkeley, pp 9–9

35.

Manku GS, Bawa M, Raghavan P (2003) Symphony: distributed hashing in a small world. In: USITS’03: proceedings of the 4th conference on USENIX symposium on internet technologies and systems. USENIX Association, Berkeley, pp 10–10

36.

Malkhi D, Naor M, Ratajczak D (2002) Viceroy: a scalable and dynamic emulation of the butterfly. In: PODC ’02: proceedings of the twenty-first annual symposium on principles of distributed computing. ACM, New York, pp 183–192CrossRef

37.

Wolpert DH, Macready WG (1995) No free lunch theorems for search. Santa Fe Institute, Working Papers 95-02-010

38.

Karger D, Lehman E, Leighton T, Panigrahy R, Levine M, Lewin D (1997) Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the world wide web. In: STOC ’97: proceedings of the twenty-ninth annual ACM symposium on theory of computing. ACM, New York, pp 654–663CrossRef

39.

Horowitz E, Sahni S, Rajasckaran S (1996) Computer algorithms: C++. W H Freeman, New York

40.

Kumar V, Grama A, Gupta A, Karypis G (1994) Introduction to parallel computing: design and analysis of algorithms. Benjamin-Cummings, Redwood CityMATH

41.

Ateconi S, Hales D, Babaoglu O (2007) Broadcasting at the critical threshold in peer-to-peer networks. Tech. Rep., University of Bologna, Department of Computer Science University of Bologna Mura Anteo Zamboni 7 40127 Bologna (Italy)

42.

Vishnevsky V, Safonov A, Yakimov M, Shim E, Gelman AD (2006) Scalable blind search and broadcasting in peer-to-peer networks. In: P2P ’06: proceedings of the sixth IEEE international conference on peer-to-peer computing. IEEE Computer Society, Washington, DC, pp 259–266CrossRef

43.

Ripeanu M, Iamnitchi A, Foster I (2002) Mapping the gnutella network. IEEE Internet Computing 6(1):50–57CrossRef

44.

Zeinalipour-Yatzi D, Folias T (2002) A quantitative analysis of the gnutella network traffic. Technical report, University of California, Riverside

45.

Kalogeraki V, Gunopulos D, Zeinalipour-Yazti D (2002) A local search mechanism for peer-to-peer networks. In: CIKM ’02: proceedings of the eleventh international conference on information and knowledge management. ACM, New York, pp 300–307CrossRef

46.

Coulouris GF, Dollimore J (1988) Distributed systems: concepts and design. Addison-Wesley Longman, BostonMATH

47.

Lv Q, Cao P, Cohen E, Li K, Shenker S (2002) Search and replication in unstructured peer-to-peer networks. In: ICS ’02: proceedings of the 16th international conference on supercomputing. ACM, New York, pp 84–95CrossRef

48.

Vuong S, Li J (2003) Efa: an efficient content routing algorithm in large peer-to-peer overlay networks. In: P2P ’03: proceedings of the 3rd international conference on peer-to-peer computing. IEEE Computer Society, Washington, DC, p 216

49.

Krishnamurthy B, Wang J, Xie Y (2001) Early measurements of a cluster-based architecture for p2p systems. In: IMW ’01: proceedings of the 1st ACM SIGCOMM workshop on internet measurement. ACM, New York, pp 105–109CrossRef

50.

Saroiu S, Gummadi KP, Gribble SD (2003) Measuring and analyzing the characteristics of napster and gnutella hosts. Multimedia Syst 9(2):170–184CrossRef

51.

Leibowitz N, Ripeanu M, Wierzbicki A (2003) Deconstructing the kazaa network. In: WIAPP ’03: proceedings of the the third IEEE workshop on internet applications. IEEE Computer Society, Washington, DC, p 112CrossRef

52.

Ganesh AJ, Kermarrec A-M, Massoulié L (2001) Scamp: peer-to-peer lightweight membership service for large-scale group communication. In: NGC ’01: proceedings of the third international COST264 workshop on networked group communication. Springer, London, pp 44–55

53.

Li HC, Clement A, Wong EL, Napper J, Roy I, Alvisi L, Dahlin M (2006) Bar gossip. In: USENIX’06: proceedings of the 7th conference on USENIX symposium on operating systems design and implementation. USENIX Association, Berkeley, pp 14–14

54.

Abdallah M, Temal L (2003) Gridb: a scalable distributed database sharing system for grid environments. Tech. Rep., Paris University, 8, rue du Capitaine Scott 75015 Paris, France

55.

Androutsellis-Theotokis S, Spinellis D (2004) A survey of peer-to-peer content distribution technologies. ACM Comput Surv 36(4):335–371CrossRef

56.

Lu J, Callan J (2004) Federated search of text-based digital libraries in hierarchical peer-to-peer networks. In: Proceedings of the 27th European conference on information retrieval

57.

Lu J, Callan J (2006) Content-based peer-to-peer network overlay for full-text federated search. In: Proceedings of the eighth recherche d’information assistee par ordinateur (RIAO) conference

58.

Zhang H, Croft WB, Levine B, Lesser V (2004) A multi-agent approach for peer-to-peer based information retrieval system. aamas 01:456–463

59.

Zhang H, Lesser V (2004) A dynamically formed hierarchical agent organization for a distributed content sharing system. In: IAT ’04: proceedings of the intelligent agent technology, IEEE/WIC/ACM international conference on (IAT’04). IEEE Computer Society, Washington, DC, pp 169–175CrossRef

60.

Zhang H, Lesser V (2006) Multi-agent based peer-to-peer information retrieval systems with concurrent search sessions. In: AAMAS ’06: proceedings of the fifth international joint conference on autonomous agents and multiagent systems. ACM, New York, pp 305–312CrossRef

61.

Aberer K, Cudré-Mauroux P, Datta A, Despotovic Z, Hauswirth M. Punceva M, Schmidt R (2003) P-grid: a self-organizing structured p2p system. SIGMOD Rec 32(3):29–33CrossRef

62.

Bao X, Fang B, Hu M, Xu B (2005) Heterogeneous search in unstructured peer-to-peer networks. IEEE Distrib Syst Online 6(2):1CrossRef

63.

Brunskill E (2001) Building peer-to-peer systems with chord, a distributed lookup service. In: HOTOS ’01: proceedings of the eighth workshop on hot topics in operating systems. IEEE Computer Society, Washington, DC, p 81

64.

Kaufman C, Perlman R, Speciner M (2002) Network security: PRIVATE communication in a PUBLIC world. Prentice Hall PTR, Upper Saddle River

65.

Li J, Stribling J, Morris R, Kaashoek MF, Gil TM (2005) A performance vs. cost framework for evaluating dht design tradeoffs under churn. In: INFOCOM. IEEE, Piscataway, pp 225–236

66.

Wikipedia, De bruijn graph. Internet. http://en.wikipedia.org/wiki/DeBruijngraph

67.

Castro M, Druschel P, Charlie Y, Rowstron HA (2002) Exploiting network proximity in peer-to-peer overlay networks. Tech. Rep

68.

Dabek F, Li J, Sit E, Robertson J, Kaashoek MF, Morris R (2004) Designing a dht for low latency and high throughput. In: NSDI’04: proceedings of the 1st conference on symposium on networked systems design and implementation. USENIX Association, Berkeley, pp 7–7

69.

WikiPedia (2008) Kademlia. WWW. http://en.wikipedia.org/wiki/Kademlia

70.

Ghodsi A, Alima L, El-Ansary S, Brand P, Haridi S (2003) Self-correcting broadcast in distributed hash tables. ACTA, Anaheim

71.

Ghodsi A, Alima LO, Haridi S (2005) Low-bandwidth topology maintenance for robustness in structured overlay networks. In: HICSS ’05: proceedings of the proceedings of the 38th annual Hawaii international conference on system sciences (HICSS’05) - track 9. IEEE Computer Society, Washington, DC, p 302.1

72.

Garces-Erice L, Biersack EW, Ross KW, Felber PA, Urvoy-Keller G (2003) Hierarchical p2p systems. In: Proceedings of ACM/IFIP international conference on parallel and distributed computing (Euro-Par), Klagenfurt

73.

Xue G, Jiang Y, You Y, Li M (2007) A topology-aware hierarchical structured overlay network based on locality sensitive hashing scheme. In: UPGRADE ’07: proceedings of the second workshop on use of P2P, GRID and agents for the development of content networks. ACM, New York, pp 3–8CrossRef

74.

Zhao BY, Duan Y, Huang L, Joseph AD, Kubiatowicz J (2002) Brocade: landmark routing on overlay networks. In: IPTPS ’01: revised papers from the first international workshop on peer-to-peer systems. Springer, London, pp 34–44

75.

Ganesan P, Gummadi K, Garcia-Molina H (2004) Canon in g major: designing dhts with hierarchical structure. In: ICDCS ’04: proceedings of the 24th international conference on distributed computing systems (ICDCS’04). IEEE Computer Society, Washington, DC, pp 263–272

76.

Zoels S, Despotovic Z, Kellerer W (2008) On hierarchical dht systems—an analytical approach for optimal designs. Comput Commun 31(3):576–590CrossRef

77.

Hofstätter Q, Zöls S, Michel M, Despotovic Z, Kellerer W (2008) Chordella—a hierarchical peer-to-peer overlay implementation for heterogeneous, mobile environments. In: P2P ’08: proceedings of the 2008 eighth international conference on peer-to-peer computing. IEEE Computer Society, Washington, DC, pp 75–76CrossRef

78.

Datar M (2002) Butterflies and peer-to-peer networks. In: ESA ’02: proceedings of the 10th annual European symposium on algorithms. Springer, London, pp 310–322

79.

Zöls S, Schollmeier R, Kellerer W, Tarlano A (2005) The hybrid chord protocol: a peer-to-peer lookup service for context-aware mobile applications. In: Lorenz P, Dini P (eds) Networking—ICN 2005. 4th international conference on networking, proceedings, part II. Ser. lecture notes computer science, vol 3421. Springer, Berlin Heidelberg New York, pp 781–792

80.

Zoels S, Schubert S, Kellerer W, Despotovic Z (2006) Hybrid dht design for mobile environments. In: Proc. AP2P workshop at AAMAS 2006, Hakodate, 9–12 May 2006

81.

Wallach DS (2002) A survey of peer-to-peer security issues. In: International symposium on software security, pp 42–57

82.

Shehory O, Kraus S (1995) Coalition formation among autonomous agents: strategies and complexity (preliminary report). In: Castelfranchi C, Müller J-P (eds) From reaction to cognition—fifth European workshop on modelling autonomous agents in a multi-agent world, MAAMAW-93, LNAI, vol 957. Springer, Heidelberg, pp 56–72

83.

Ketchpel SP (1994) Forming coalitions in the face of uncertain rewards. In: National conference on artificial intelligence, pp 414–419

84.

Winter E (2002) The handbook of game theory. The Shapley value. North-Holldand, Amsterdam, pp 2026–2052

85.

Shehory O, Kraus S (1995) Task allocation via coalition formation among autonomous agents. In: Proceedings of the fourteenth international joint conference on artificial intelligence (IJCAI-95), Montréal, pp 655–661

86.

Gerkey BP (2003) On multi-robot task allocation. PhD dissertation, University of Southern California

Titel: Structured P2P technologies for distributed command and control
verfasst von: Daniel R. Karrels
Gilbert L. Peterson
Barry E. Mullins
Publikationsdatum: 01.12.2009
Verlag: Springer US
Erschienen in: Peer-to-Peer Networking and Applications / Ausgabe 4/2009
Print ISSN: 1936-6442
Elektronische ISSN: 1936-6450
DOI: https://doi.org/10.1007/s12083-009-0033-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 4/2009

An open digital environment to support business ecosystems

NodeWiz: Fault-tolerant grid information service

Gossiping protocols for hybrid grid resource scheduling

Editorial: Peer-to-peer networking and applications, volume 2, issue 4

Facilitating resource discovery in grid environments with peer-to-peer structured tuple spaces

Dealing with network partitions in structured overlay networks