Provably Efficient Resource Allocation for Edge Service Entities Using Hermes

Virtualization techniques help edge environments separate the role of the traditional edge providers into two: edge infrastructure providers (EIPs), who manage the physical edge infrastructure, and edge service providers (ESPs), who aggregate resources (especially, compute resources) from multiple EIPs to place service entities and offer value-added services to end users (EUs). In such an environment, end users submit their data analysis jobs to ESPs; ESPs process the data analysis jobs using their service entities. One fundamental and critical problem for an ESP is to decide how much compute resources to rent from each edge server under the constraint that the total amount of rental resources is no more than a specified budget threshold, so that the average makespan of the data analysis jobs submitted to it is minimized. This Edge Resource Allocation (ERA) problem is proven to be NP-complete by reducing the set cover problem to a special case of it. To design an approximation algorithm for ERA, we perform two transformations on ERA: first, we transform ERA into mERA by replacing minimization with maximization; second, we transform mERA into dmERA by limiting the possible amounts of rental resources to a finite set of values. We find that dmERA has several tractable properties that allow us to design Hermes, a provably efficient algorithm that approximates the optimal allocation. We demonstrate that the gap between Hermes and the optimum in simulations and Android-based testbed experiments are no larger than 4.78% and 12.43%, respectively. Hermes can also output a curve showing the trade-off between the average makespan and the budget threshold, so that an ESP can choose the right balance.