A Scalable and Robust DHT Protocol for Structured P2P Network

Xiao Shu, Xining Li

Computing and Information Science, University of Guelph, Guelph, Canada.

DOI: 10.4236/ijcns.2012.512084                

Abstract

Distributed Hash Tables (DHTs) were originated from the design of structured peer-to-peer (P2P) systems. A DHT provides a key-based lookup service similar to a hash table. In this paper, we present the detailed design of a new DHT protocol, Tambour. The novelty of the protocol is that it uses parallel lookup to reduce retrive latency and bounds communication overhead to a dynamically adjusted routing table. Tambour estimates the probabilities of routing entries' liveness based on statistics of node lifetime history and evicts dead entries after lookup failures. When the network is unstable, more routing entries will be evicted in a given period of time, and the routing tables will be getting smaller which minimize the number of timeouts for later lookup requests. An experimental prototype of Tambour has been simulated and compared against two popular DHT protocols. Results show that Tambour outperforms the compared systems in terms of bandwith cost, lookup latency and the overall efficiency.

Keywords

P2P Network; Distributed Hash Table; Small-World Distribution; Parallel Lookups

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	K. Gummadi, R. Gummadi, S. Gribble, S. Ratnasamy, S. Shenker and I. Stoica, “The Impact of DHT Routing Geometry on Resilience and Proximity,” Proceedings of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, ACM, New York, 2003, pp. 381-394.
[2]	Z. Yang, J. Tian and Y. Dai, “Towards a More Accurate Availability Evaluation in Peer-To-Peer Storage Systems,” Proceedings of the 2006 International Workshop on Networking, Architecture, and Storages, Shenyang, 2006, pp. 73-80. doi:10.1109/IWNAS.2006.45
[3]	M. Zhou, Y. Dai and X. Li, “A Measurement Study of the Structured Overlay Network in P2P File-Sharing Systems,” Advanced Multimedia, Vol. 2007, No. 1, 2007, pp. 10-18.
[4]	S. Saroiu, P. K. Gummadi and S. D. Gribble, “A Measurement Study of Peer-To-Peer File Sharing Systems,” Multimedia Computing and Networking Conference (MMCN), San Jose, January 2002, pp. 156-170.
[5]	I. Stoica, R. Morris, D. Karger, F. F. Kaashoek and H. Balakrishnan, “Chord: A Scalable Peer-To-Peer Look up Service for Internet Applications,” Computer Communication Review, Vol. 31, No. 4, 2001, pp. 149-160. doi:10.1145/964723.383071
[6]	A. Rowstron and P. Druschel, “Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-To-Peer Systems,” Lecture Notes in Computer Science, Vol. 2218, 2001, pp. 329-350. doi:10.1007/3-540-45518-3_18
[7]	B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph and J. D. Kubiatowicz, “Tapestry: A Resilient Global-Scale Overlay for Service Deployment,” IEEE Journal on Selected Areas in Communications, Vol. 22, No. 1, 2004, pp. 41-53. doi:10.1109/JSAC.2003.818784
[8]	P. Maymounkov and D. Mazières, “Kademlia: A Peer-To-Peer Information System Based on the XOR Metric,” IPTPS, 2002, pp. 53-65.
[9]	R. Bhagwan, S. Savage and G. M. Voelker, “Understanding Availability,” IPTPS, 2003, pp. 256-267.
[10]	J. Kleinberg, “The Small-World Phenomenon: An Algorithmic Perspective,” Proceedings of the 32nd ACM Symposium on Theory of Computing, ACM, New York, 2000, pp. 163-170.
[11]	G. S. Manku, M. Bawa, P. Raghavan and V. Inc, “Symphony: Distributed Hashing in a Small World,” Proceedings of the 4th USENIX Symposium on Internet Technologies and Systems, 2003, pp. 127-140.
[12]	J. Li, J. Stribling, R. Morris and M. F. Kaashoek, “Bandwidth-Efficient Management of DHT Routing Tables,” Proceedings of the 2nd Conference on Symposium on Net- worked Systems Design & Implementation, USENIX Association, Berkeley, 2005, pp. 99-114.
[13]	I. Gupta, K. Birman, P. Linga, A. Demers and R. V. Renesse, “Kelips: Building an Efficient and Stable P2P DHT through Increased Memory and Background Overhead,” Proceedings of the 2nd International Workshop on Peer-to-Peer Systems, Berkeley, 2003, pp. 160-169.
[14]	R. Rodrigues and C. Blake, “When Multi-Hop Peer-To-Peer Routing Matters,” The 3rd International Workshop on Peer-to-Peer Systems, La Jolla, 26-27 February, 2004, pp. 112-122.
[15]	A. Gupta, B. Liskov and R. Rodrigues, “Efficient Routing for Peer-To-Peer Overlays,” Proceedings of the 1st Conference on Symposium on Networked Systems Design and Implementation, USENIX Association, Berkeley, 2004, pp. 113-126.
[16]	B. Leong and J. Li, “Achieving One-Hop DHT Look up and Strong Stabilization by Passing Tokens,” Proceedings of the 12th International Conference on Networks (ICON), Singapore, November 2004, pp. 344-350.
[17]	J. Li, J. Stribling, R. Morris, M. F. Kaashoek and T. M. Gil, “A Performance vs. Cost Framework for Evaluating DHT Design Trade offs under Churn,” Proceedings of the 24th Infocom, Miami, 13-17 March 2005, pp. 225-236.
[18]	S. Saroiu, K. P. Gummadi and S. D. Gribble, “Measuring and Analyzing the Characteristics of Napster and Gnutella Hosts,” Multimedia Systems, Vol. 9, No. 2, 2003, pp. 170-184. doi:10.1007/s00530-003-0088-1
[19]	F. Dabek, R. Cox, F. Kaashoek and R. Morris, “Vivaldi: A Decentralized Network Coordinate System,” SIGCOMM, 2004, pp. 15-26.
[20]	H. Zhang, A. Goel and R. Govindan, “Incrementally Improving Lookup Latency in Distributed Hash Table Systems,” ACM Sigmetrics, 2003, pp. 114-125.
[21]	“A Simulator for Peer-To-Peer (P2P) Protocols,” 2012. http://pdos.csail.mit.edu/p2psim
[22]	B. Leong, B. Liskov and E. D. Demaine, “EpiChord: Parallelizing the Chord Lookup Algorithm with Reactive Routing State Management,” The 12th International Conference on Networks (ICON), Singapore, November 2004, pp. 1243-1259.