Provably Efficient Resource Allocation of Cloud Native Functions for Network Services
Nikolaos Lazaropoulos, Ioannis Vaxevanakis, Ioannis Sigalas, Ioannis Lamprou, Vassilis Zissimopoulos · 2025
Modern Network Function Virtualization (NFV) revolutionizes network service provisioning by orchestrating Cloud Native Functions (CNFs), deployed as containerized workloads across distributed cluster workers. These deployments consist of modular microservices that enable elastic scalability and collaborative service delivery. This study presents a framework for addressing the Resource Allocation problem of CNFs, focusing on approximation algorithms with provable performance guarantees. The proposed framework, designed for Capacity Constrained Resource Allocation of CNFs, encompasses three variations of the Group Generalized Assignment Problem (Group GAP). Key contributions include: (1) a 1/2-approximation algorithm for instances where each CNF's size is at most half of the cluster capacity, enhancing known results for Group GAP; (2) a 1/2(1 − e −1/d)-approximation algorithm for shared microservices among multiple CNFs, where d is the degree of sharing, supported by experimental evaluation of the algorithm's relative error; and (3) an algorithm for cases involving diverse microservice sizes and profits, achieving a (1/2 − ϵ) approximation ratio. By employing linear programming relaxation and rounding techniques, our framework ensures computational efficiency and scalable solution quality, effectively addressing CNF resource management in modern network infrastructures.