Over the Internet today, computing and communications environments are significantly more complex and chaotic than classical distributed systems, lacking any centralized organization or hierarchical control. There has been much interest in emerging Peer-to-Peer (P2P) network overlays because they provide a good substrate for creating large-scale data sharing, content distribution, and application-level multicast applications. These P2P overlay networks attempt to provide a long list of features, such as: selection of nearby peers, redundant storage, efficient search/location of data items, data permanence or guarantees, hierarchical naming, trust and authentication, and anonymity. P2P networks potentially offer an efficient routing architecture that is self-organizing, massively scalable, and robust in the wide-area, combining fault tolerance, load balancing, and explicit notion of locality. In this article we present a survey and comparison of various Structured and Unstructured P2P overlay networks. We categorize the various schemes into these two groups in the design spectrum, and discuss the application-level network performance of each group. A SURVEY AND COMPARISON OF PEER-TO-PEER OVERLAY NETWORK SCHEMES SECOND QUARTER 2005, VOLUME 7, NO. 2 www.comsoc.org/pubs/surveys eer-to-peer (P2P) overlay networks are distributed systems in nature, without any hierarchical organization or centralized control. Peers form self-organizing overlay networks that are overlayed on the Internet Protocol (IP) networks, offering a mix of various features such as robust wide-area routing architecture, efficient search of data items, selection of nearby peers, redundant storage, permanence, hierarchical naming, trust and authentication, anonymity, massive scalability, and fault tolerance. Peer-to-peer overlay systems go beyond services offered by client-server systems by having symmetry in roles where a client may also be a server. It allows access to its resources by other systems and supports resource sharing, which requires fault-tolerance, self-organization, and massive scalability properties. Unlike Grid systems, P2P overlay networks do not arise from the collaboration between established and connected groups of systems and without a more reliable set of resources to share. We can view P2P overlay network models spanning a wide spectrum of the communication framework, which specifies a fully-distributed, cooperative network design with peers building a self-organizing system. Figure 1 shows an abstract P2P overlay architecture, illustrating the components in the overlay The Network Communications layer describes the network characteristics of desktop machines connected over the Internet or small wireless or sensor-based devices that are connected in an ad-hoc manner. The dynamic nature of peers poses challenges in the communication paradigm. The Overlay Nodes Management layer covers the management of peers, which include discovery of peers and routing algorithms for optimization. The Features Management layer deals with the security, reliability, fault resiliency, and aggregated resource availability aspects of maintaining the robustness of P2P systems. The Services Specific layer supports the underlying P2P infrastructure and the application-specific components through scheduling of parallel and computation-intensive tasks, content and file management. Meta-data describes the content stored across the P2P peers and the location information. The Application-level layer is concerned with tools, applications, and services that are implemented with specific functionalities on top of the underlying P2P overlay infrastructure. Thus, there are two classes of P2P overlay networks: Structured and Unstructured. The technical meaning of structured is that the P2P overlay network topology is tightly controlled and content is placed not at random peers but at specified locations that will make Table ( DHT) as a substrate, in which data object (or value) location information is placed deterministically, at the peers with identifiers corresponding to the data object's unique key. DHT-based systems have a property that consistently assigned uniform random NodeIDs to the set of peers into a large space of identifiers. Data objects are assigned unique identifiers called keys, chosen from the same identifier space. Keys are mapped by the overlay network protocol to a unique live peer in the overlay network. The P2P overlay networks support the scalable storage and retrieval of {key,value} pairs on the overlay network, as illustrated in Fig. 2 . Given a key, a store operation (put(key,value)) lookup retrieval operation (value=get(key)) can be invoked to store and retrieve the data object corresponding to the key, which involves routing requests to the peer corresponding to the key. Each peer maintains a small routing table consisting of its neighboring peers' NodeIDs and IP addresses. Lookup queries or message routing are forwarded across overlay paths to peers in a progressive manner, with the NodeIDs that are closer to the key in the identifier space. Different DHT-based systems will have different organization schemes for the data objects and its key space and routing strategies. In theory, DHT-based systems can guarantee that any data object can be located in small O(logN) overlay hops on average, where N is the number of peers in the system. The underlying network path between two peers can be significantly different from the path on the DHT-based overlay network. Therefore, the lookup latency in DHT-based P2P overlay networks can be quite high and could adversely affect the performance of the applications running over it. Plaxton et al. [1] provide an elegant algorithm that achieves nearly optimal latency on graphs that exhibit power-law expansion [2], at the same time preserving the scalable routing properties of the DHT-based system. However, this algorithm requires pair-wise probing between peers to determine latencies, and it is unlikely to scale to a large number of peers in the overlay. DHT-based systems [3] [4] [5] [6] [7] are an important class of P2P routing infrastructures. They support the rapid development of a wide variety of Internetscale applications ranging from distributed file and naming systems to application-layer multicast. They also enable scalable, wide-area retrieval of shared information. In 1999 Napster [8] pioneered the idea of a peer-to-peer file sharing system supporting a centralized file search facility. It was the first system to recognize that requests for popular content need not be sent to a central server but instead could be handled by many peers that have the requested content. Such P2P file-sharing systems are self-scaling in that as more peers join the system, they add to the aggregate download capability. Napster achieved this self-scaling behavior by using a centralized search facility based on file lists provided by each peer; thus, it does not require much bandwidth for the centralized search. Such a system has the issue of a single point of failure due to the centralized search mechanism. However, a lawsuit filed by the Recording Industry Association of America (RIAA) attempted to force Napster to shut down the free-for-all file-sharing service for copyrighted digital music -literally, its killer application. However, this paradigm caught the imagination of platform providers and users alike. Gnutella [9-11] is a decentralized system that distributes both the search and download capabilities, establishing an overlay network of peers. It is the first system that makes use of an unstructured P2P overlay network. An unstructured P2P system is composed of peers joining the network with some loose rules, without any prior knowledge of the topology. The network uses flooding as the mechanism to send queries across the overlay with a limited scope. When a peer receives the flood query, it sends a list of all content matching the query to the originating peer. While floodingbased techniques are effective for locating highly replicated items and are resilient to peers joining and leaving the system, they are poorly suited for locating rare items. Clearly this approach is not scalable as the load on each peer grows linearly with the total number of queries and the system size. Thus, unstructured P2P networks face one basic problem: peers readily become overloaded, and thus the system does not scale when handling a high rate of aggregate queries and sudden increases in system size. Although structured P2P networks can efficiently locate rare items since the key-based routing is scalable, they incur significantly higher overheads than unstructured P2P networks for popular content. Consequently, over the Internet today the decentralized unstructured P2P overlay networks are more commonly used. However, there are recent efforts on keybased routing (KBR) API abstractions [12] that allow more application-specific functionalities to be built over these common basic KBR API abstractions, and OpenDHT 1 (Open publicly accessible DHT service) [13] that allow the unification platform to provide developers with a basic DHT service model that runs on a set of infrastructure hosts, to deploy DHT-based overlay applications without the burden of maintaining a DHT, and with ease of use to spur the deployment of DHT-based applications. In contrast, unstructured P2P overlay systems are ad-hoc in nature, and do not present the possibilities of being unified under a common platform for application development. In later sections of this article we will describe the key features of structured P2P and unstructured P2P overlay networks and their operation functionalities. After providing a basic understanding of the various network overlay schemes in these two classes, we proceed to evaluate these various overlays schemes in both classes and discuss its developments. Then we attempt to use the following taxonomies to make comparisons between the various discussed structured and unstructured P2P overlay schemes: • Decentralization -examine whether the overlay system is distributed. • Architecture -describe the overlay system architecture with respect to its operation. • Lookup protocol -the lookup query protocol adopted by the overlay system. • System parameters -the required system parameters for the overlay system operation. • Routing performance -the lookup routing protocol performance in overlay routing. • Routing state -the routing state and scalability of the overlay system. • Peers join and leave -describe the behavior of the overlay system when churn and self-organization occurred. • Security -look into the security vulnerabilities of overlay systems. • Reliability and fault resiliency -examine how robust the overlay system is when subjected to faults. Finally, we conclude with some thoughts on the relative applicability of each class to some of the research problems that arise in ad-hoc, location-based, and content delivery networks, as examples.
Approaches for peer-to-peer overlay networks are surveyed in REF , which discusses both structured and unstructured models.
A survey and comparison of peer-to-peer overlay network schemes
IEEE Communications Surveys & Tutorials
IEEE Communications Surveys & Tutorials
Computer Science