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
| Type: | Proceedings paper |
|---|---|
| Title: | Service Placement with Provable Guarantees in Heterogeneous Edge Computing Systems |
| Event: | 2019 IEEE International Conference on Computer Communications (IEEE INFOCOM 2019) |
| Location: | Paris, France |
| Dates: | 29 April 2019 - 02 May 2019 |
| Open access status: | An open access version is available from UCL Discovery |
| Publisher version: | https://infocom2019.ieee-infocom.org/ |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10075008 |
Loading...
Loading...Loading...Loading...Archive Staff Only
 |
View Item |
