Dynamic Distributed Edge Resource Provisioning via Online Learning across Timescales
Wencong You, Lei Jiao, Sourav Bhattacharya, Yuan Zhang · 2020
The strategic management of distributed resources of mobile edge computing networks often requires managing different system components over different timescales. In this paper, we formulate a nonlinear mixed-integer program to capture the online optimization of the edge network’s long-term cost, where we distribute workload more frequently on the fast timescale and provision resources less frequently on the slow timescale. We design a novel online learning framework consisting of three algorithms to make fast-timescale and slow-timescale fractional decisions, respectively, and round such decisions into integers. Our algorithms run in polynomial time in an online manner, jointly solving the original NP-hard problem that can contain arbitrary and unpredictable inputs. Via rigorous formal analysis, we prove a parameterized-constant competitive ratio as the performance guarantee for our approach. We conduct extensive evaluations with real-world data and confirm our approach’s superiority over existing practices and state-of-the-arts.