Peer-to-Peer Systems – Design of Peer-to-Peer Search Overlay Networks

Since the huge success of Napster, many new peer-to-peer overlay networks have been proposed. Although most of them are built for file-sharing, there are many more application areas for the use of peer- to-peer overlays are used. From centralized indexing (like that in Napster) to full decentralization, the structure of the overlays varies. Additionally, there are many types of queries that users or applications can perform on these overlays.

With the classification of key design aspects defined by Aberer et al. in [1], we can better compare overlays’ design decisions and assess the influence they have on quality aspects. Six key design aspects in peer-to-peer overlay networks identified in [1] are:

  1. Choice of an Identifier Space: describes the space of identifiers for each peer and resource in the network. Furthermore, it defines a closeness metric between the identifiers which can be used for routing through structured overlays.
  2. Mapping to the Identifier Space: defines how identifiers are assigned to peers and resources.
  3. Management of the Identifier Space: explains which peers are responsible for a resource with a given key. It describes replication capabilities and how these are handled.
  4. Graph Embedding: shows how an overlay selects its neighbors and builds its routing table.
  5. The Routing Strategy: describes how neighbors’ contacts are used to resolve the user query and perform overlay operations (e.g. publish, store, update).
  6. The Maintenance Strategy: describes how the failed contacts are detected and replaced and resources kept available.

We have observed and simulative compared four search overlays of different types which are well established in research and deployed in practical peer-to-peer applications: Chord, Kademlia, Gnutella 0.6, and Gia. Our findings regarding the influence design decisions we used as a basis for an engineering approach to building peer-to-peer search overlays.


In [2] we propose a peer-to-peer overlay for location-based search that provide area search, finding a closest service or a service on a specific geographical location. The results of all three types of queries must be valid – complete and correct. The resulting overlay Globase.KOM, is a superpeer-based overlay forming a tree enhanced with interconnections. Superpeers are chosen from publicly reachable, static peers with more capacity, spare bandwidth, and good network connectivity. The world projection is divided in rectangular, not over- lapping zones, as presented in Figure 1. Each zone is assigned to a superpeer that is located inside of the zone and keeps overlay/underlay contact addresses to all peers in that zone. Superpeers form the tree where superpeer A is called the parent of superpeer B when B’s zone is inside A’s zone.

Beside parent and children connections, each superpeer maintains interconnections to the superpeers in the higher levels of the same branch or to the superpeers from the different branches. The inner zones are formed once a number of peers inside exceed a load threshold. A newly formed zone is then assigned to one peer in that area, that fulfills the requirements for becoming a superpeer. PeerID has information about the zone of responsibility and the geolocation of a peer. When a peer in the zone of superpeer B initiates an area search, it sends a query message to superpeer B. In the overlay and zone structure from Figure 1, if the zone does not intersect the zone superpeer B is responsible for, the query message will be forwarded to the superpeer A. This process continues on each superpeer in the path. Eventually, superpeers A, C, and D will reply with the list of the matching results.


In [3], we suggested mechanisms to address scalability, efficiency, fault-tolerance, fairness, load-balancing and support for heterogeneity within a unified solution. They have been realized within a novel Overlay Network, called Omicron. Omicron follows a hybrid approach with a two-tier architecture, employing clusters to achieve the required fault-tolerance and uses de Bruijn graphs for the inter-cluster topology. A rich role identification model effectively exploits the heterogeneity of the peers by providing a balanced distribution of common tasks which have to be performed in order for the system to operate (e.g. routing, indexing, maintenance, etc.). A high level description of Omicron is provided in Figure 2.

[1] Karl Aberer, Luc Onana Alima, Ali Ghodsi, Sarunas Girdzijauskas, Seif Haridi, and Manfred Hauswirth. The essence of P2P: A reference architecture for overlay networks. In Proceedings of the 5th IEEE International Conference on Peer-to-Peer Computing (P2P), pages 11–20, 2005.

[2] Aleksandra Kovacevic, Nicolas Liebau, and Ralf Steinmetz. Globase.KOM - A P2P Overlay for Fully Retrievable Location- based Search. In Proceedings of the 7th IEEE International Conference on Peer-to-Peer Computing (P2P), September 2007.

[3] Vasilios Darlagiannis, Andreas Mauthe, and Ralf Steinmetz. Overlay Design Mechanisms for Heterogeneous, Large Scale, Dynamic P2P Systems. Journal of Network and Systems Management, Special Issue on Distributed Management, 12(3):371-395, September 2004.


Dr. Boris Koldehofe

Technische Universität Darmstadt
Fachgebiet Multimedia Kommunikation
Rundeturmstr. 10
64283 Darmstadt