Replication-Based Load Balancing

Load balancing of large distributed server systems is a complex optimization problem of critical importance in cloud systems and data centers. Existing schedulers often incur a high communication overhead when collecting the data required to make scheduling decisions, hence delaying job requests on their way to the executing servers. We propose a novel scheme that incurs no communication overhead between the users and the servers upon job arrival, thus removing any scheduling overhead from the job's critical path. Our approach is based on creating several replicas of each job and sending each replica to a different server. Upon the arrival of a replica to the head of the queue at its server, the latter signals the servers holding replicas of that job, so as to remove them from their queues. We show, through analysis and simulations, that this scheme significantly improves the expected queuing overhead over traditional schemes under various load conditions and different job length distributions. In addition, we show that our scheme remains efficient even when the inter-server signal propagation delay is significant (relative to the job's execution time). We provide a heuristic solution to the performance degradation that occurs in such cases and show, by simulations, that it efficiently mitigates the detrimental effect of propagation delays.