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 signiﬁcant 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 ﬁle systems, searching network, and static Web content delivery. The most prominent initial designs of P2P systems include Napster [66, 140], Gnutella , and Freenet . Unfortunately, all of them have signiﬁcant scaling problems. For example, in Napster a central server stores the index of all the ﬁles available within the Napster user community. To retrieve a ﬁle, a user queries this central server using the desired ﬁles well-known name and obtains the IP address of a user machine storing the requested ﬁle. The ﬁle is then downloaded directly from this user machine. Thus, although Napster uses a P2P communication model for the actual ﬁle transfer, the process of locating a ﬁle 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 ﬁle location process as well. Users in a Gnutella network self-organize into an application-level network on which requests for a ﬁle are not
Freenet goes a step further by addressing the security issues and privacy issues, but it still employs a ﬂooding-based depth-ﬁrst search mechanism that incurs a heavy trafﬁc for large systems. Both Gnutella and Freenet are not guaranteed to ﬁnd an existing object because the ﬂooding has to be curtailed at some point.