3rd International ICST Conference on Collaborative Computing: Networking, Applications and Worksharin

Research Article

Load Balancing in a Hierarchical DHT-based P2P System

  • @INPROCEEDINGS{10.1109/COLCOM.2007.4553855,
        author={Stefan Zoels and Zoran Despotovic and Wolfgang Kellerer},
        title={Load Balancing in a Hierarchical DHT-based P2P System},
        proceedings={3rd International ICST Conference on Collaborative Computing: Networking, Applications and Worksharin},
        publisher={IEEE},
        proceedings_a={COLLABORATECOM},
        year={2008},
        month={6},
        keywords={Algorithm design and analysis  Analytical models  Communication networks  Electronic mail  Europe  Laboratories  Load management  Peer to peer computing  Performance analysis  Scalability},
        doi={10.1109/COLCOM.2007.4553855}
    }
    
  • Stefan Zoels
    Zoran Despotovic
    Wolfgang Kellerer
    Year: 2008
    Load Balancing in a Hierarchical DHT-based P2P System
    COLLABORATECOM
    IEEE
    DOI: 10.1109/COLCOM.2007.4553855
Stefan Zoels1,*, Zoran Despotovic2,*, Wolfgang Kellerer2,*
  • 1: Institute of Communication Networks, Technische Universitat Munchen, Munich, Germany
  • 2: DoCoMo Communication Laboratories Europe, Munich, Germany
*Contact email: stefan.zoels@tum.de, despotovic@docomolab-euro.com, kellerer@docomolab-euro.com

Abstract

Hierarchical DHT (HDHT) systems, outperforming flat DHTs with respect to scalability and network locality, became an important P2P research area in recent years. Appropriate load balancing algorithms, which are available only for flat DHTs so far, are also required for the reliability and scalability of HDHTs. However, their impact is different. In HDHTs, failures caused by overloaded nodes in higher hierarchical layers affect larger portions of the network than overloaded nodes in lower layers. In comparison to flat DHTs, HDHTs offer an additional dimension of balancing load, i.e., through varying relevant parameters of the hierarchical organization. This makes load balancing in HDHTs significantly different from load balancing in flat DHTs. In this paper, we exploit this possibility and present a novel load balancing algorithm for a two-tier HDHT system. Analytically and by simulations we show that our algorithm provides good load balancing performance, while at the same time generating less overhead than, e.g., the renowned “power of two choices” algorithm.