Online Cost Minimization and Resource Allocation in Edge and Cloud Systems

Abstract

Recent advances in cloud and edge computing support increasingly complex applications, yet present challenges in dynamically allocating resources and controlling costs. Demand unpredictability, diverse pricing models, and limited foresight complicate decision-making for both customers and service providers (SP).

This thesis introduces a set of online algorithms that address cost minimization and resource allocation without prior knowledge of future demands. From the customer’s perspective, we propose the Multi-Object Break-Even (MOBE) algorithm, which balances on-demand and pre-paid options for multiple service components. MOBE achieves a tight competitive ratio of e/e−1≈1.58, surpassing the classical ski-rental ratio of 2, and proving cost-effective through simulations on real-world traces.

From the SP’s perspective, we focus on allocating limited resources to maximize social welfare. We first present the Known Volume Algorithm (KVA), which uses exact total demand information to outperform previous best-known results. We then extend to the Predicted Volume Algorithm (PVA), incorporating error-prone forecasts. PVA guarantees good performance even with imperfect predictions, ensuring both consistency and robustness. Additionally, the Limited Volume Algorithm (LVA) improves competitive ratios in a special case when the total demand volume is less than twice of the total resources.

Finally, we address the service placement problem in multi-tiered edge-cloud networks. Modeling data centers as nodes in a tree, we jointly optimize placement and relay costs. We develop the Anchor-Barrier Algorithm (ABA) and its variant for non-increasing placement costs (MNC). Both achieve a tight and optimal competitive ratio equal to Tiers+1, validated through theoretical proofs and trace-driven evaluations.