Algorithm learns best way to balance jobs between different servers
Learning Adaptive SED for heterogeneous load balancing
Machine Learning
Summary
Sometimes computers need to decide how to send jobs to different servers that work at different speeds but the speeds are unknown at first. Simply guessing the speeds and choosing the fastest server can lead to bad decisions because the guesses are often wrong. The authors introduce a smart method that learns the true speeds over time by sometimes trying both servers on purpose to get better information. This strategy helps the system quickly figure out the best way to send jobs with less delay. Tests show this method outperforms simple guess-based policies, especially when careful exploration is crucial.
What this means in practice
- •For cloud infrastructure teams: Optimize job routing across servers with unknown performance to reduce wait times and improve responsiveness in cloud data centers.
- •For edge computing operators: Improve workload distribution in edge networks by learning device speeds on the fly, enhancing latency-sensitive services.
Authors
Sanne van Kempen, Jaron Sanders, Fiona Sloothaak, Maarten G. Wolf
Abstract
We study a two-server load balancing system with heterogeneous service rates that are a priori unknown to the dispatcher. The goal is to route customers according to the Shortest--Expected--Delay (SED) policy, but this requires knowledge of the service rates. Empirical policies that route based on estimates perform poorly: due to estimation error, the empirical policy disagrees with the oracle on an infinite region of the state space. We propose an online learning algorithm that converges to SED while learning the service rates. The algorithm carefully balances empirical SED routing with forced exploration phases that guarantee sufficient sampling of both servers. We prove that our algorithm achieves finite regret; this differs from classical Multi-Armed Bandit settings where regret typically grows logarithmically in time. Finally, numerical experiments demonstrate the performance of our algorithm and highlight the regimes in which forced exploration is especially beneficial.