Online placement of multi-component applications in edge computing environments
File(s)Shiqiang_Wang_MappingAlgorithm_2017_01.pdf (1.38 MB)
Accepted version
Author(s)
Wang, S
Zafer, M
Leung, KK
Type
Journal Article
Abstract
Mobile edge computing is a new cloud computing paradigm which makes use of small-sized edge-clouds to provide real-time services to users. These mobile edge-clouds (MECs) are located in close proximity to users, thus enabling users to seamlessly access applications running on MECs. Due to the coexistence of the core (centralized) cloud, users, and one or multiple layers of MECs, an important problem is to decide where (on which computational entity) to place different components of an application. This problem, known as the application or workload placement problem, is notoriously hard, and therefore, heuristic algorithms without performance guarantees are generally employed in common practice, which may unknowingly suffer from poor performance as compared to the optimal solution. In this paper, we address the application placement problem and focus on developing algorithms with provable performance bounds. We model the user application as an application graph and the physical computing system as a physical graph, with resource demands/availabilities annotated on these graphs. We first consider the placement of a linear application graph and propose an algorithm for finding its optimal solution. Using this result, we then generalize the formulation and obtain online approximation algorithms with polynomial-logarithmic (poly-log) competitive ratio for tree application graph placement.We jointly consider node and link assignment, and incorporate multiple types of computational resources at nodes.
Date Issued
2017-02-08
Date Acceptance
2017-02-03
ISSN
2169-3536
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Start Page
2514
End Page
2533
Journal / Book Title
IEEE Access
Volume
5
Copyright Statement
6
2017 IEEE. Translations and content mining are permitted for academic research only.
Personal use is also permitted, but republication/redistribution requires IEEE permission.
See http://www.ieee.org/publications_standards/publications/rights/index.html for more information
2017 IEEE. Translations and content mining are permitted for academic research only.
Personal use is also permitted, but republication/redistribution requires IEEE permission.
See http://www.ieee.org/publications_standards/publications/rights/index.html for more information
Sponsor
IBM United Kingdom Ltd
Grant Number
PO4603106973
Subjects
Science & Technology
Technology
Computer Science, Information Systems
Engineering, Electrical & Electronic
Telecommunications
Computer Science
Engineering
Cloud computing
graph mapping
mobile edge-cloud (MEC)
online approximation algorithm
optimization theory
mobile edge-cloud
Publication Status
Published