Title :
Measuring the cost of online load-balancing in distributed range-queriable systems
Author :
Konstantinou, Ioannis ; Tsoumakos, Dimitrios ; Koziris, Nectarios
Author_Institution :
Comput. Syst. Lab., Nat. Tech. Univ. of Athens, Athens, Greece
Abstract :
Distributed systems such as peer-to-peer overlays have been shown to efficiently support the processing of range queries over large numbers of participating hosts. In such systems, uneven load allocation has to be effectively tackled in order to minimize overloaded peers and optimize their performance. In this work, we detect and analyze the two basic methodologies used to achieve load-balancing: Iterative key re-distribution between neighbors and node migration. Based on this analysis, we propose a hybrid method that adaptively utilizes these two extremes to achieve both fast and cost-effective load-balancing in distributed systems that support range queries. As a case study, we offer an implementation on top of a Skip Graph, where we validate our findings in a variety of workloads. Our experimental analysis shows that the hybrid method converges 10% faster than simple neighbor item exchanges and is more than 70% bandwidth efficient compared to simple node migrations.
Keywords :
Internet; data structures; resource allocation; Internet; distributed range-partitioned data structures; distributed range-queriable system; iterative key re-distribution; load allocation; node migration; online load-balancing; skip graph; Bandwidth; Costs; Distributed computing; Internet; Iterative methods; Laboratories; Load management; Particle measurements; Peer to peer computing; Web server;
Conference_Titel :
Peer-to-Peer Computing, 2009. P2P '09. IEEE Ninth International Conference on
Conference_Location :
Seattle, WA
Print_ISBN :
978-1-4244-5066-4
Electronic_ISBN :
978-1-4244-5067-1
DOI :
10.1109/P2P.2009.5284544