Weakly Coupled MDP for Load Balancing in Containerized Cloud: A Scalable Control Design

Load balancing is a core challenge in containerized cloud systems. We formulate the dispatcher’s decision problem as a weakly coupled Markov Decision Process (MDP) and derive a scalable policy via a Lagrangian linear-programming relaxation that decouples per-VM control. A toy-scale study is first used to expose structural behavior and guide design; we then run full-scale simulations to assess performance and robustness. We prove that the optimal value function is non-decreasing in total backlog and establish a stochastic-dominance corollary. Several appealing conjectures (e.g., per-VM monotonicity) hold at low demand but fail near saturation, clarifying when “balance everything” heuristics become suboptimal. Motivated by these insights, we propose a deployable load-aware dispatcher that blends JSQ-like behavior at low load with advantage-based routing at high load. Across scaled experiments, the dispatcher consistently reduces blocking and tail delay versus standard baselines, and competes favorably with a state-of-the-art heuristic, while incurring modest control overhead. The study bridges stochastic control and deployable cloud scheduling, offering both analytical insights and a practical policy design.