在現代雲端運算與分散式系統中，任務執行時間的高度動態性與重尾分佈（Heavy-Tailed Distribution）常導致系統面臨負載傾斜與局部過載問題。傳統負載平衡策略多僅針對單一目標（如預期平均負載或變異數）進行最佳化，使系統難以同時兼顧空間負載平衡與時間波動風險。近年提出之雙目標排程方法雖試圖緩解此問題，卻普遍依賴靜態權重參數進行決策，且在負載失衡後仍需透過反應式遷移（Reactive Migration）維持系統穩定，進而增加資料中心內部頻寬消耗、服務延遲與系統震盪風險。
針對上述挑戰，本研究提出一項無參數化（Parameter-free）的線上「動態約束雙目標派發演算法（Dynamically Constrained Dual-Objective Dispatch, DCDD）」。DCDD 採用零遷移（Zero-Migration）的主動派發架構，其核心理論奠基於全變異數定理（Law of Total Variance），將系統工作負載的時間波動風險轉化為對空間負載不平衡的動態約束閾值，藉此取代傳統方法對固定超參數的依賴。在每次任務抵達時，DCDD 透過低負載節點補償、自適應可行解空間過濾，以及可行解空間內之貪婪風險最小化等三階段決策流程，動態調整負載平衡與風險隔離之間的決策邊界。此外，本研究進一步推導基於全局平方和差分更新之數學公式，使單一候選節點的空間變異數預測可於 O(1) 時間內完成，並將單次任務派發之整體決策複雜度維持於 O(M)，以滿足大型雲端系統對線上即時排程的效能需求。
為驗證所提方法之穩健性與實務可行性，本研究以 Google、Microsoft Azure 與 Alibaba 等大型資料中心之真實工作負載日誌作為實驗資料，並透過 10,000 次蒙地卡羅模擬進行評估。實驗結果顯示，相較於傳統貪婪式負載平衡策略、靜態雙目標模型以及基於隨機預測之方法，DCDD 不僅能在常規工作負載下維持較低的空間負載不平衡度，更能在高變異數壓力測試中有效降低風險集中現象，並在負載平衡與風險隔離之間展現較佳的帕雷托效能權衡（Pareto-efficient Trade-off）。此外，DCDD 在維持微秒級派發延遲的同時，可降低後續事後遷移需求，顯示其具備應用於大型雲端資料中心之工程可行性與擴展潛力。

In modern cloud computing, the highly dynamic nature and heavy-tailed distribution of task execution times lead to severe load skew and local overloads. Traditional single-objective load balancing strategies fail to simultaneously manage spatial load distribution and temporal volatility risk, while recent dual-objective methods over-rely on static weights and reactive migration. To address these limitations, this study proposes the Dynamically Constrained Dual-Objective Dispatch (DCDD), a parameter-free, zero-migration online scheduling algorithm. DCDD leverages the Law of Total Variance to dynamically translate temporal volatility risk into a strict constraint for spatial load imbalance. The algorithm employs a three-stage decision process: low-load node compensation to prevent starvation (grounded in Chebyshev’s Inequality), dynamic feasible region filtering to prevent objective divergence (justified by the AM-GM Inequality), and greedy risk minimization to optimize local queueing delays (supported by the Pollaczek-Khinchine Formula). Additionally, DCDD utilizes a global differential update mechanism, achieving O(1) spatial variance prediction and maintaining O(M) overall dispatch complexity. Evaluated via 10,000 Monte Carlo simulations using real-world traces from Google, Microsoft Azure, and Alibaba Cloud, DCDD successfully maintains balanced spatial loads while significantly suppressing risk concentration. Operating with an average dispatch latency of approximately 95 microseconds, DCDD eliminates the need for post-facto reactive migrations, demonstrating superior Pareto-efficient trade-offs and robust scalability for next-generation cloud data centers.

[1] Alibaba Cloud. https://github.com/alibaba/clusterdata.
[2] Ganesh Ananthanarayanan, Srikanth Kandula, Albert Greenberg, Ion Stoica, Yi Lu, Bikas Saha, and Edward Harris. Reining in the outliers in map-reduce clusters using mantri. In Proceedings of the 9th USENIX conference on Operating systems design and implementation (OSDI ’10), pages 265–278. USENIX Association, 2010.
[3] Yossi Azar, Andrei Z. Broder, Anna R. Karlin, and Eli Upfal. Balanced allocations. SIAM Journal on Computing, 29(1):180–200, 1999.
[4] Microsoft Azure. https://azure.microsoft.com/.
[5] AzurePublicDataset. https://github.com/Azure/AzurePublicDataset.
[6] Nikhil Bansal and Ohad N. Feldheim. The power of two choices in graphical allocation. STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 52–63, 2022.
[7] Luiz André Barroso and Urs Hölzle. The Datacenter as a Computer: Designing Warehouse-Scale Machines. Springer Nature, 3rd edition, 2018.
[8] David Bernstein. Containers and cloud: From LXC to Docker to Kubernetes. IEEE Cloud Computing, 1(3):81–84, 2014.
[9] Brendan Burns, Brian Grant, David Oppenheimer, Eric Brewer, and John Wilkes. Borg, omega, and kubernetes. In Communications of the ACM, volume 59, pages 50–57. ACM, 2016.
[10] Zheyi Chen, Jia Hu, Geyong Min, Chunbo Luo, and Tarek El-Ghazawi. Adaptive and efficient resource allocation in cloud datacenters using actor-critic deep reinforcement learning. IEEE Transactions on Parallel and Distributed Systems, 33(8):1911–1923, 2022.
[11] Christopher Clark, Keir Fraser, Steven Hand, Jacob Gorm Hansen, Eric Jul, Christian Limpach, Ian Pratt, and Andrew Warfield. Live migration of virtual machines. NSDI’05: Proceedings of the 2nd conference on Symposium on Networked Systems Design and Implementation, 2:273–286, 2005.
[12] M.E. Crovella and A. Bestavros. Self-similarity in world wide web traffic: Evidence and possible causes. IEEE/ACM Transactions on Networking, 5(6):835–846, 1997.
[13] Jeffrey Dean and Luiz André Barroso. The tail at scale. Communications of the ACM, 56(2):74–80, 2013.
[14] Christina Delimitrou and Christos Kozyrakis. Quasar: Resource-efficient and QoS-aware cluster management. In Proceedings of the 19th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 127–144, 2014.
[15] Google Cloud Platform. https://cloud.google.com.
[16] Geoffrey Grimmett and David Stirzaker. Probability and Random Processes. Oxford University Press, 3rd edition, 2001.
[17] Wenxia Guo, Wenhong Tian, Yufei Ye, Lingxiao Xu, and Kui Wu. Cloud resource scheduling with deep reinforcement learning and imitation learning. IEEE Internet of Things Journal, 8(5):3576–3586, 2021.
[18] Mor Harchol-Balter, Mark E. Crovella, and Cristina D. Murta. On choosing a task assignment policy for a distributed server system. Journal of Parallel and Distributed Computing, 59(2):204–228, 1999.
[19] Hung-Chang Hsiao, Lian-Xing Wei, and Ching-Hsien Hsu. Robust load balancing taking advantage of aggregated performance metrics. IEEE Transactions on Services Computing, 19:628–641, 2026.
[20] Chengzhi Lu, Kejiang Ye, Guoyao Xu, Cheng-Zhong Xu, and Tongxin Bai. Imbalance in the cloud: An analysis on alibaba cluster trace. IEEE International Conference on Big Data, 2017.
[21] Michael Mitzenmacher. The power of two choices in randomized load balancing. IEEE Transactions on Parallel and Distributed Systems, 12(10):1094–1104, 2001.
[22] Michael Mitzenmacher and Matteo Dell’Amico. The supermarket model with known and predicted service times. IEEE Transactions on Parallel and Distributed Systems, 33(11):2740–2751, 2022.
[23] Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge University Press, 2nd edition, 2017.
[24] Sam Newman. Building Microservices: Designing Fine-Grained Systems. O’Reilly Media, 2015.
[25] Athanasios Papoulis and S. Unnikrishna Pillai. Probability, Random Variables, and Stochastic Processes. McGraw-Hill, 4th edition, 2002.
[26] Sheldon M. Ross. Introduction to Probability Models. Academic Press, 11th edition, 2014.
[27] Amazon Web Services. https://aws.amazon.com.
[28] Abhishek Verma, Luis Pedrosa, Madhukar Korupolu, David Oppenheimer, Eric Tune, and John Wilkes. Large-scale cluster management at google with borg. EuroSys ’15: Proceedings of the Tenth European Conference on Computer Systems, pages 1–17, 2015.
[29] Berthold Vöcking. How asymmetry helps load balancing. Journal of the ACM, 50(4):568–589, 2003.
[30] Liang Wang, Mengyuan Li, Yinqian Zhang, Thomas Ristenpart, and Michael Swift. Peeking behind the curtains of serverless platforms. In USENIX ATC ’18: Proceedings of the 2018 USENIX Conference on Usenix Annual Technical Conference, pages 133–145. USENIX Association, 2018.
[31] Lei Yu, Liuhua Chen, Zhipeng Cai, Haiying Shen, Yi Liang, and Yi Pan. Stochastic load balancing for virtual resource management in datacenters. IEEE Transactions on Cloud Computing, 8(2):459–472, 2020.