Tangram: A New Constant-degree P2P System

Abstract: Peer-to-Peer (P2P) is a research hotspot of distributed computing and computer network. A structured P2P system is based on distributed hash table and its overlay network is a graph. Because of the relationship between the stored data and the network topology, efficient routing algorithm can be gained on the structured P2P system. Some classic P2P system, like Chord, CAN, Pastry and Tapestry, can achieve a path length of O(logN) by using O(logN) neighbors per node. The number of neighbors of a node shows the overhead of the network topology maintenance, so a constant-degree P2P system is valuable to research. Constant-degree P2P system can reduce the overhead of topology maintenance when the network is churning. Some constant-degree P2P systems, such as Koorde, Viceroy and Cycloid, are proposed.This paper presents the design and evaluation of a P2P Tangram system, which is a scalable, distributed object location and routing system. We firstly propose a new constant-degree graph, DBR, which combines De Bruijn and Ring and keeps 2 in-degrees and 2 out-degrees. Then, we design the new structured, constant-degree P2P system, Tangram, by adapting DBR to the dynamic network. Tangram is completely decentralized and self-organizing, and achieves a time complexity of O(logN) per lookup request by using 0(1) neighbors per node, where N is the network size. Experimental result shows that Tangram is efficient.