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.