A Hybrid Dynamic Load Balancing Algorithm for Distributed Systems Using Genetic Algorithms

A Hybrid Dynamic Load Balancing Algorithm for Distributed Systems Using Genetic Algorithms

Mayuri A. Mehta (Department of Computer Engineering, Sarvajanik College of Engineering and Technology, Surat, India) and Devesh C. Jinwala (Department of Computer Engineering, S. V. National Institute of Technology, Surat, India)
Copyright: © 2014 |Pages: 23
DOI: 10.4018/ijdst.2014070101
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Dynamic Load Balancing (DLB) is sine qua non in modern distributed systems to ensure the efficient utilization of computing resources therein. This paper proposes a novel framework for hybrid dynamic load balancing. Its framework uses a Genetic Algorithms (GA) based supernode selection approach within. The GA-based approach is useful in choosing optimally loaded nodes as the supernodes directly from data set, thereby essentially improving the speed of load balancing process. Applying the proposed GA-based approach, this work analyzes the performance of hybrid DLB algorithm under different system states such as lightly loaded, moderately loaded, and highly loaded. The performance is measured with respect to three parameters: average response time, average round trip time, and average completion time of the users. Further, it also evaluates the performance of hybrid algorithm utilizing OnLine Transaction Processing (OLTP) benchmark and Sparse Matrix Vector Multiplication (SPMV) benchmark applications to analyze its adaptability to I/O-intensive, memory-intensive, or/and CPU-intensive applications. The experimental results show that the hybrid algorithm significantly improves the performance under different system states and under a wide range of workloads compared to traditional decentralized algorithm.
Article Preview

Introduction

In heterogeneous distributed environments, it is desirable to have the system workload balanced as evenly as possible among the computing resources, so that the average job response time is minimized. In classic distributed system, the minimization of response time is achieved through load balancing technique. Load balancing redistributes the system workload among the processing elements to maximize the overall system performance (Shiraji, Hurson & Kavi, 1995). Dynamic load balancing is a significant mechanism that adapts itself to the fluctuating workload to improve the performance in distributed system (Shah, Veeravalli & Misra, 2007). Any dynamic load balancing strategy can be classified as either centralized or decentralized (Baikerikar, Surve & Prabhu, 2010; Gupta & Bepari, 1995; Riedl & Richter, 1996; Siddesh & Srinisas, 2012). Though the centralized approach is simple in terms of implementation and overhead, with the evolution of large and more highly loaded distributed systems, it becomes less feasible due to a single point of failure (Chandra & Sahoo, 2010; Paksoy & Prado, 2013; Psoroulas, Anagnostopoulos, Loumos & Kayafas, 2007; Sotiriadis, Bessis & Antonopoulos, 2012). Further, it does not scale up well as the central load balancer can become a performance bottleneck (Mukhopadhyay, Ghosh & Mukherjee, 2010). On the other hand, the decentralized approach performs better for large size and heterogeneous system (Al-Azzoni & Down, 2009; Dhakal, Hayat, Pezoa, Yang & Bader, 2007; Fatta & Berthold, 2007; Paksoy & Prado, 2013; Shah, Veeravalli & Misra, 2007; Werstein, Situ & Huang, 2006). However, it increases load balancing communication overhead. Consequently, the design of an effective hybrid dynamic load balancing algorithm is crucial to overcome the limitations of centralized and decentralized approaches.

The popularity of distributed system has motivated several recent efforts to study dynamic load balancing for heterogeneous system. Hence, several DLB schemes have been proposed and reviewed in the literature (Al-Azzoni & Down, 2009; Anitha & Balakrishna, 2011; Chandra & Sahoo, 2010; Dhakal, Hayat, Pezoa, Yang & Bader, 2007; Fatta & Berthold, 2007; Mukhopadhyay, Ghosh & Mukherjee, 2010; Paksoy & Prado, 2013; Psoroulas, Anagnostopoulos, Loumos & Kayafas, 2007; Shah, Veeravalli & Misra, 2007; Sotiriadis, Bessis & Antonopoulos, 2012; Werstein, Situ & Huang, 2006). However, only a few strategies have been designed to reduce the communication overhead (Al-Azzoni & Down, 2009; Shah, Veeravalli & Misra, 2007), or are scalable or both. In addition, the suitability of existing DLB algorithms turns out to be limited concerning the nature of system workload (Chandra & Sahoo, 2010; Gopalachari, Sammulal & Babu, 2009; Kabbany, Wanas, Hegazi & Shaheen, 2011; Qin, Jiang & Manzanares, 2009; Werstein, Situ & Huang, 2006). Hence, we are interested in hybrid dynamic load balancing algorithm that resolves the below mentioned drawbacks of centralized and decentralized approaches.

  • Scalability issue of centralized approach

  • Single point of failure in centralized approach

  • Higher communication overhead in decentralized approach

  • Higher load balancing time in these approaches

Complete Article List

Search this Journal:
Reset
Open Access Articles
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing