Paper Info
Title
The Home Model and Competitive Algorithms for Load Balancing in a Computing Cluster
Abstract
Abstract: Most implementations of a Computing Cluster (CC) use greedy-based heuristics to perform load balancing. In some cases, this is in contrast to theoretical results about the performance of on-line load balancing algorithms. In this paper we define the home model in order to better reflect the architecture of a CC. In this new theoretical model, we assume a realistic cluster structure in which every job has a "home" machine which it prefers to be executed on, e.g. due to I/O considerations or because it was created there. We develop several on-line algorithms for load balancing in this model. We first provide a theoretical worst-case analysis, showing that our algorithms achieve better competitive ratios and perform less reassignments than algorithms for the unrelated machines model, which is the best existing theoretical model to describe such clusters. We then present an empirical average-case performance analysis by means of simulations. We show that the performance of our algorithms is consistently better than that of several existing load balancing methods, e.g. the greedy and the opportunity cost methods, especially in a dynamic and changing CC environment.
Year
DOI
Venue
2001
10.1109/ICDSC.2001.918941
ICDCS
Keywords
Field
DocType
load balancing,new theoretical model,existing theoretical model,theoretical result,computing cluster,on-line load,home model,competitive algorithms,cc environment,unrelated machines model,theoretical worst-case analysis,existing load,computer science,distributed algorithms,load balance,resource allocation,computer networks,clustering algorithms,computer architecture,communication networks,computational modeling,simulation
Online algorithm,Computer science,Load balancing (computing),Algorithm,Implementation,Distributed algorithm,Heuristics,Resource allocation,Computer cluster,Opportunity cost,Distributed computing
Conference
ISSN
Citations 
PageRank 
1063-6927
9
0.77
References 
Authors
6
2
Name
Order
Citations
PageRank
Ron Lavi168573.46
Amnon Barak2590119.00