Online Scheduling and Splittable Routing for Serverless Functions at Network Edge
Yuchen Yang, Shaowei Wang · 2024
Introducing the serverless computing paradigm to network edge offers a promising solution to the emerging latency-critical cloud services. Unique features such as highly-variable execution times and unpredictable arrival patterns of the serverless functions pose fundamental challenges to achieve such goals. In this paper, we propose an online algorithm for joint function scheduling and routing, aiming to maximize the rewards of deadline-constrained serverless functions. The algorithm dynamically swaps the scheduling orders by exploiting the actual realizations of the stochastic execution times, and enables splittable routing taking into account the interval estimates of the latest function starting times. We prove that the proposed algorithm is $\frac{1}{{1 - \delta }}\mathcal{O}(\log (\Lambda \mathcal{P}))$-competitive against δ-risk non-anticipatory offline optimum, where parameters Λ and $\mathcal{P}$ capture the instance pattern. Numerical results demonstrate that our proposed scheme outperforms the state-of-the-art ones.