Heterogeneity and load balance in distributed hash tables

Philip B Godfrey, Ion Stoica

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Existing solutions to balance load in DHTs incur a high overhead either in terms of routing state or in terms of load movement generated by nodes arriving or departing the system. In this paper, we propose a set of general techniques and use them to develop a protocol based on Chord, called Y 0, that achieves load balancing with minimal overhead under the typical assumption that the load is uniformly distributed in the identifier space. In particular, we prove that Y 0 can achieve near-optimal load balancing, while moving little load to maintain the balance and increasing the size of the routing tables by at most a constant factor. Using extensive simulations based on real-world and synthetic capacity distributions, we show that Y 0 reduces the load imbalance of Chord from O(log n) to a less than 3.6 without increasing the number of links that a node needs to maintain. In addition, we study the effect of heterogeneity on both DHTs, demonstrating significantly reduced average route length as node capacities become increasingly heterogeneous. For a real-word distribution of node capacities, the route length in Y 0 is asymptotically less than half the route length in the case of a homogeneous system.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE INFOCOM 2005. The Conference on Computer Communications - 24th Annual Joint Conference of the IEEE Computer and Communications Societies
EditorsK. Makki, E. Knightly
Pages596-606
Number of pages11
DOIs
StatePublished - Oct 10 2005
Externally publishedYes
EventIEEE INFOCOM 2005 - Miami, FL, United States
Duration: Mar 13 2005Mar 17 2005

Publication series

NameProceedings - IEEE INFOCOM
Volume1
ISSN (Print)0743-166X

Other

OtherIEEE INFOCOM 2005
CountryUnited States
CityMiami, FL
Period3/13/053/17/05

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Heterogeneity and load balance in distributed hash tables'. Together they form a unique fingerprint.

  • Cite this

    Godfrey, P. B., & Stoica, I. (2005). Heterogeneity and load balance in distributed hash tables. In K. Makki, & E. Knightly (Eds.), Proceedings - IEEE INFOCOM 2005. The Conference on Computer Communications - 24th Annual Joint Conference of the IEEE Computer and Communications Societies (pp. 596-606). (Proceedings - IEEE INFOCOM; Vol. 1). https://doi.org/10.1109/INFCOM.2005.1497926