Dynamic Load Balancing for High Dimensional Systems

Abstract

Load balancing is very relevant in networking, where incoming requests (jobs) have to be divided over various servers by dispatchers. The goal is mostly to minimize response times. Research in this field becomes ever more relevant by the current trend where users generate an increasing amount of internet traffic and data centers become larger and larger. A commonly used load balancing algorithm that uses randomization and performs well, is SQ(d). It sends an arriving job to the shortest of d queues, chosen uniformly at random. In most research this d is kept fixed and its performance is analyzed asymptotically in the number of servers. In this thesis we keep the number of servers finite and apply the theory of Markov decision processes (MDPs) to the load balancing problem. We model the SQ(d) algorithm as a Markov reward process and make it an MDP by introducing communication costs and allowing d to vary. Since MDPs are not scalable, we came up with a heuristic coined Dynamic SQ(d), that outperforms algorithms widely used in practice, such as SQ(2) and Join the Shortest Queue, for a fairly broad range of parameter values.