| Abstract |
Edge computing is an emerging technology to offer resource-intensive yet delay-sensitive applications from the edge of mobile networks, where a major challenge is to allocate limited edge resources to competing demands. While prior works make a simplifying assumption that resource demands of different users are additive, this assumption does not hold for social applications (e.g., social virtual reality), where users collaborating on a task are interested in services (e.g., scene updates) based on the same set of data/code. Meanwhile, serving each user request also consumes non-negligible additive resources (e.g., CPU, bandwidth). We study the optimal provisioning of such applications by jointly placing services and scheduling requests under both additive (communication, computation) and sub-additive (storage) resource constraints. In the homogeneous case, we show that while the problem is polynomial-time solvable without storage constraints, it is NP-hard even if each edge cloud has unlimited communication or computation resources. We further show that the hardness is caused by the service placement subproblem, while the request scheduling subproblem is polynomial-time solvable via maximum-flow algorithms. In the general case, both subproblems are NP-hard. We develop a constant-factor approximation algorithm for the homogeneous case and efficient heuristics for the general case, all achieving near-optimal performance in our trace-driven evaluations. |