A symmetric load balancing algorithm with performance guarantees for distributed hash tables

Hung Chang Hsiao, Che Wei Chang

研究成果: Article

25 引文 斯高帕斯(Scopus)

摘要

Peers participating in a distributed hash table (DHT) may host different numbers of virtual servers and are enabled to balance their loads in the reallocation of virtual servers. Most decentralized load balance algorithms designed for DHTs based on virtual servers require the participating peers to be asymmetric, where some serve as the rendezvous nodes to pair virtual servers and participating peers, thereby introducing another load imbalance problem. While state-of-the-art studies intend to present symmetric load balancing algorithms, they introduce significant algorithmic overheads and guarantee no rigorous performance metrics. In this paper, a novel symmetric load balancing algorithm for DHTs is presented by having the participating peers approximate the system state with histograms and cooperatively implement a global index. Each peer independently reallocates in our proposal its locally hosted virtual servers by publishing and inquiring the global index based on their histograms. Unlike competitive algorithms, our proposal exhibits analytical performance guarantees in terms of the load balance factor and the algorithmic convergence rate, and introduces no load imbalance problem due to the algorithmic workload. Through computer simulations, we show that our proposal clearly outperforms existing distributed algorithms in terms of load balance factor with a comparable movement cost.

原文English
文章編號6127858
頁(從 - 到)662-675
頁數14
期刊IEEE Transactions on Computers
62
發行號4
DOIs
出版狀態Published - 2013 三月 18

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

指紋 深入研究「A symmetric load balancing algorithm with performance guarantees for distributed hash tables」主題。共同形成了獨特的指紋。

  • 引用此