Herbster, M; Pasteris, S; Shiqiang, W; He, T; (2019) Service Placement with Provable Guarantees in Heterogeneous Edge Computing Systems. In: Proceedings of the 2019 IEEE International Conference on Computer Communications (IEEE INFOCOM 2019). IEEE: Paris, France. (In press).

Preview

Text SP_INFOCOM2019.pdf - Published Version Download (612kB) | Preview

Abstract

Mobile edge computing (MEC) is a promising technique for providing low-latency access to services at the network edge. The services are hosted at various types of edge nodes with both computation and communication capabilities. Due to the heterogeneity of edge node characteristics and user locations, the performance of MEC varies depending on where the service is hosted. In this paper, we consider such a heterogeneous MEC system, and focus on the problem of placing multiple services in the system to maximize the total reward. We show that the problem is NP-hard via reduction from the set cover problem, and propose a deterministic approximation algorithm to solve the problem, which has an approximation ratio that is not worse than (1 − e−1)/4. The proposed algorithm is based on two subroutines that are suitable for small and arbitrarily sized services, respectively. The algorithm is designed using a novel way of partitioning each edge node into multiple slots, where each slot contains one service. The approximation guarantee is obtained via a specialization of the method of conditional expectations, which uses a randomized procedure as an intermediate step. In addition to theoretical guarantees, simulation results also show that the proposed algorithm outperforms other state-of-the-art approaches

Download activity - last month

Export as JSONXMLCSV

Download activity - last 12 months

Export as CSVXMLJSON

Downloads by country - last 12 months

Export as JSONXMLCSV

Archive Staff Only

View Item