chapter  9
24 Pages

Scalable Constant-Degree Peer-to-Peer Overlay Networks

In the past few years, the immense popularity of peer-to-peer (P2P) resource sharing services has resulted in a significant stimulus to content-delivery overlay network research. An important class of the overlay networks is distributed hash tables (DHTs) that map keys to the nodes of a network based on a consistent hashing function. Most of the DHTs require O(logn) hops per lookup request with O(logn) neighbors per node, where n is the network size. In this chapter, we present a constant-degree DHT, namely, Cycloid. It achieves a lookup path length of O(d) with O(1) neighbors, where d is the network dimension and n = d · 2d. The DHT degree determines the number of neighbors with which a node must maintain continuous contact. A constant degree puts a cap on the cost for maintenance,

The ubiquity of the Internet has made possible a universal storage space that is distributed among the participating end computers (peers) across the Internet. All peers assume equal role and there is no centralized server in the space. Such architecture is collectively referred to as the P2P system that is leading to new content distribution models for applications such as software distribution, distributed file systems, searching network, and static Web content delivery. The most prominent initial designs of P2P systems include Napster [66, 140], Gnutella [133], and Freenet [65]. Unfortunately, all of them have significant scaling problems. For example, in Napster a central server stores the index of all the files available within the Napster user community. To retrieve a file, a user queries this central server using the desired files well-known name and obtains the IP address of a user machine storing the requested file. The file is then downloaded directly from this user machine. Thus, although Napster uses a P2P communication model for the actual file transfer, the process of locating a file is still very much centralized. This makes it both expensive (to scale the central directory) and vulnerable (since there is a single point of failure). Gnutella decentralizes the file location process as well. Users in a Gnutella network self-organize into an application-level network on which requests for a file are not

Freenet goes a step further by addressing the security issues and privacy issues, but it still employs a flooding-based depth-first search mechanism that incurs a heavy traffic for large systems. Both Gnutella and Freenet are not guaranteed to find an existing object because the flooding has to be curtailed at some point.