ABSTRACT
We present two methods for weighted consistent hashing also known as weighted distributed hash tables. The first method, called Linear Method, combines the standard consistent hasing introduced by Karger et al. [9] with a linear weighted distance measure. By using node copies and different partitions of the hash space, the balance of this scheme approximates the fair weight relationship with high probability. The second method, called the Logarithmic Method, uses a logarithmic weighted distance between the peers and the data to find the corresponding node. For distributing one data element it provides perfect weighted balance. To provide this distribution for many data elements we use partitions to achieve a fair balance with high probability. These methods provide small fragmentation, which means that the hash space is divided into at most O (n log n) intervals. Furthermore, there is an efficient data structure that assigns data elements to the nodes in expected time O (log n). If small fragmentation is not an issue one can replace the use of partitions by a method we call double hash functions. This method needs O (n) for assigning elements to a node, yet it can be directly used for Storage Area Networks, where the number of nodes is small compared to participating nodes in Peer-to-Peer networks.
- P. K. Agarwal and M. Sharir. Simple bounds. In Davenport-Schinzel Sequences and Their Geometric Applications, chapter 1, pages 1--47. Cambridge University Press, in handbook of computational geometry edition, 1995. ISBN 0-521-47025-0.Google Scholar
- P. Bleckmann, S. Böttcher, E. Cesnavicius, A. Francisco, T. D. Hollerung, B. Kühnel, M. J. Liu, S. Obermeier, S. Oberthür, F. Peter, F. Rammig, C. Schindelhauer, G. Schomaker, T. Steenweg, Q. A. Tarar, M. Tiemeyer, A. Türling, and A. Vater. The design of pamanet the paderborn mobile ad-hoc network. In MobiWac '04: Proceedings of the second international workshop on Mobility management & wireless access protocols, pages 119--121, New York, NY, USA, 2004. ACM Press. Google ScholarDigital Library
- A. Brinkmann, F. Meyer auf der Heide, K. Salzwedel, C. Scheideler, M. Vodisek, and U. Rückert. Storage management as means to cope with exponential information growth. In Proceedings of SSGRR 2003, L'Aquila, Italy, 28 July - 3 Aug. 2003.Google Scholar
- A. Brinkmann, K. Salzwedel, and C. Scheideler. Efficient, distributed data placement strategies for storage area networks (extended abstract). In Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, pages 119--128. ACM Press, 2000. Google ScholarDigital Library
- A. Brinkmann, K. Salzwedel, and C. Scheideler. Compact, adaptive placement schemes for non-uniform distribution requirements. In Proc. of the 14th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 53--62, Winnipeg, Manitoba, Canada, 11-13 Aug. 2002. Google ScholarDigital Library
- J. Byers, J. Considine, and M. Mitzenmacher. Simple load balancing for distributed hash tables. Technical report, BU Computer Science, 2002.Google Scholar
- P. Druschel and A. Rowstron. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In R. Guerraoui, editor, Middleware 2001, IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, Germany, November 12-16, 2001, Proceedings, volume 2218 of Lecture Notes in Computer Science, pages 329--350. Springer, 2001. Google ScholarDigital Library
- K. Hildrum, J. D. Kubiatowicz, S. Rao, and B. Y. Zhao. Distributed object location in a dynamic network. In Proceedings of the 14th Annual ACM Symposium on Parallel ALgorithms and Architectures (SPAA-02), pages 41--52, New York, Aug. 10--13 2002. ACM Press. Google ScholarDigital Library
- D. Karger, E. Lehman, T. Leighton, M. Levine, D. Lewin, and R. Panigrahy. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 654--663, El Paso, Texas, 4--6 May 1997. Google ScholarDigital Library
- D. R. Karger and M. F. Kaashoek. Koorde: A simple degree-optimal distributed hash table. In Proc. 2nd IPTPS, Berkeley, CA, Feb. 2003, Feb. 10 2003.Google Scholar
- M. Mitzenmacher. The power of two choices in randomized load balancing. IEEE Transactions on Parallel and Distributed Systems, 12(10):1094--1104, 2001. Google ScholarDigital Library
- M. Naor and U. Wieder. Novel architectures for p2p applications: the continuous-discrete approach. In Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, pages 50--59. ACM Press, 2003. Google ScholarDigital Library
- C. G. Plaxton, R. Rajaraman, and A. Richa. Accessing nearby copies of replicated objects in a distributed environment. In 9th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '97), pages 311--320, New York, June 1997. Association for Computing Machinery. Google ScholarDigital Library
- A. Rao, K. Lakshminarayanan, S. Surana, R. Karp, and I. Stoica. Load balancing in structured p2p systems. In 2nd International Workshop on Peer-to-Peer Systems (IPTPS '03), 2003.Google ScholarCross Ref
- S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker. A scalable content-addressable network. In Computer Communication Review, volume 31, pages 161--172. Dept. of Elec. Eng. and Comp. Sci., University of California, Berkeley, 2001. Google ScholarDigital Library
- I. Stoica, R. Morris, D. Karger, F. Kaashoek, and H. Balakrishnan. Chord: A scalable Peer-To-Peer lookup service for internet applications. In R. Guerin, editor, Proceedings of the ACM SIGCOMM 2001Conference (SIGCOMM-01), volume 31, 4 of Computer Communication Review, pages 149--160, New York, Aug. 27--31 2001. ACM Press. Google ScholarDigital Library
- B. Zhao, J. Kubiatowicz, and A. Joseph. Tapestry: An infrastructure for fault-tolerant wide-area location and routing. Technical Report UCB/CSD-01-1141, Computer Science Division, U. C. Berkeley, Apr. 2001. Google ScholarDigital Library
Index Terms
Weighted distributed hash tables
Recommendations
Replica Placement for Route Diversity in Tree-Based Routing Distributed Hash Tables
Distributed hash tables (DHTs) share storage and routing responsibility among all nodes in a peer-to-peer network. These networks have bounded path length unlike unstructured networks. Unfortunately, nodes can deny access to keys or misroute lookups. We ...
Scalable blind search and broadcasting over Distributed Hash Tables
Typical blind search algorithms in P2P networks generate a significant amount of duplicate query messages in order to increase the success rate. We present a novel framework, named Recursive Partitioning Search (RPS), for blind search over structured ...
Enabling Dynamic Querying over Distributed Hash Tables
Dynamic querying (DQ) is a search technique used in unstructured peer-to-peer (P2P) networks to minimize the number of nodes that is necessary to visit to reach the desired number of results. In this paper, we introduce the use of the DQ technique in ...
Comments