UnoHop: Efficient Distributed Hash Table with O(1) Lookup Performance

Herry Sitepu, Carmadi Machbub, Armein Z. R. Langi, Suhono H. Supangkat

Abstract


Distributed Hash Tables (DHTs) with O(1) lookup performance strive to minimize the maintenance traffic required for disseminating membership changes information (events). These events dissemination allows each node in the peertopeer network maintains accurate routing tables with complete membership information. We present UnoHop, a novel DHT protocol with O(1) lookup performance. The protocol uses an efficient mechanism to distribute events through a dissemination tree that is constructed dynamically rooted at the node that detects the events. Our protocol produces symmetric bandwidth usage at all nodes while decreasing the events propagation delay.

Full Text:

PDF

References


FIPS1801. Secure hash standard, U.S. Departement of Commerce, April 1995.

Gummadi, K., Gummadi, R., Gribble, S., Ratnasamy, S., Shenker, S. & Stoica, I., The impact of DHT routing geometry on resilience and proximity, In SIGCOMM ’03: Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, pp. 381–394, New York, NY, USA, ACM Press, 2003.

Gummadi, K.P., Saroiu, S. & Gribble, S.D. King: Estimating latency between arbitrary internet end hosts, In Proceedings of the SIGCOMM Internet Measurement Workshop (IMW 2002), Marseille, France, November 2002.

Gupta, A., Liskov, B. & Rodrigues, R., Ef􀂿cient routing for peertopeer overlays, In Proceedings of the First Symposium on Networked Systems Design and Implementation (NSDI ’04), March 2004.

Li, J., Stribling, J., Morris, R., Kaashoek, M.F. & Gil, T.M., A performance vs. cost framework for evaluating dht design tradeoffs under churn, In Proceedings of the 24th INFOCOM, Miami, FL, March 2005.

Maymounkov, P. & Maziã¨res, D., Kademlia: A peertopeer information system based on the XOR metric, In Proceedings of the First International Workshop, IPTPS 2002, Cambridge, MA, USA, March 78, 2002. Revised Papers, pp. 53–65, 2002.

Saroiu, S., Goummadi, P. & Gribble, S., A measurement study of peertopeer 􀂿le sharing systems. In Proceedings of Multimedia Computing and Networking (MMCN), San Jose, CA, USA, January 2002.

Stoica, I., Morris, R., Karger, D., Kaashoek, F.M. & Balakrishnan, H., Chord: A scalable peertopeer lookup service for internet applications, In SIGCOMM ’01: Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, 31, pp. 149–160, New York, NY, USA, ACM Press, October 2001.

Zhao, B.Y., Huang, L., Stribling, J., Rhea, S.C., Joseph, A.D. & Kubiatowicz, J.D., Tapestry: A resilient globalscale overlay for service deployment, IEEE Journal on Selected Areas in Communications, 22(1):41–53, 2004.

Li, J., Stribling, J., Morris, R. & Kaashoek, M.F., Bandwidthefficient management of DHT routing tables, In Proceedings of the 2nd Symposium on Networked System Design and Implementation (NSDI'05). May 2005.

Gupta, I., Birman, K., Linga, P., Demers, A. & van Renesse, R., Kelips: Building an ef􀂿cient and stable p2p DHT through increased memory and background overhead. In IPTPS ’03: 2nd International Workshop on PeertoPeer Systems, 2003

Leong, B. & Li, J., Achieving onehop DHT lookup and strong stabilization by passing tokens. In Proceedings of the 12th International Conference on Networks 2004 (ICON 2004), Singapore, November 2004.

Rowstron, A. & Druschel, P., Pastry: Scalable, Decentralized Object Location and Routing for Large Scale PeertoPeer Systems, In International Conference on Distributed Systems Platforms (Middleware), pp. 329350, Heidelberg, Germany, November 2001.

Rodrigues, R. & Blake, C., When MultiHop PeertoPeer Lookup Matters, In Proceedings of IPTS, San Diego, CA, USA, February, 2004

Wang, W., Wang, G., Liu, X., Liu, J., OneHop DHT Lookup based on Grouped Random Broadcast Messages, In Proceedings of the 2007 IEEE International Conference on Integration Technology, Shenzen, China, March 2007.




DOI: http://dx.doi.org/10.5614%2Fitbj.ict.2008.2.1.4

Refbacks

  • There are currently no refbacks.


Contact Information:

ITB Journal Publisher, LPPM – ITB, 

Center for Research and Community Services (CRCS) Building Floor 7th, 
Jl. Ganesha No. 10 Bandung 40132, Indonesia,

Tel. +62-22-86010080,

Fax.: +62-22-86010051;

e-mail: jictra@lppm.itb.ac.id.