TY - GEN
T1 - It's hard to share
T2 - 38th IEEE International Conference on Distributed Computing Systems, ICDCS 2018
AU - He, Ting
AU - Khamfroush, Hana
AU - Wang, Shiqiang
AU - La Porta, Tom
AU - Stein, Sebastian
N1 - Publisher Copyright:
© 2018 IEEE.
PY - 2018/7/19
Y1 - 2018/7/19
N2 - Mobile 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 often make a simplifying assumption that resources assigned to different users are non-sharable, this assumption does not hold for storage resources, where users interested in services (e.g., data analytics) based on the same set of data/code can share storage resource. Meanwhile, serving each user request also consumes non-sharable resources (e.g., CPU cycles, bandwidth). We study the optimal provisioning of edge services with non-trivial demands of both sharable (storage) and non-sharable (communication, computation) resources via joint service placement and request scheduling. 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. Our trace-driven simulations show that the proposed algorithms, especially the approximation algorithm, can achieve near-optimal performance, serving 2-3 times more requests than a baseline solution that optimizes service placement and request scheduling separately.
AB - Mobile 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 often make a simplifying assumption that resources assigned to different users are non-sharable, this assumption does not hold for storage resources, where users interested in services (e.g., data analytics) based on the same set of data/code can share storage resource. Meanwhile, serving each user request also consumes non-sharable resources (e.g., CPU cycles, bandwidth). We study the optimal provisioning of edge services with non-trivial demands of both sharable (storage) and non-sharable (communication, computation) resources via joint service placement and request scheduling. 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. Our trace-driven simulations show that the proposed algorithms, especially the approximation algorithm, can achieve near-optimal performance, serving 2-3 times more requests than a baseline solution that optimizes service placement and request scheduling separately.
UR - http://www.scopus.com/inward/record.url?scp=85050991638&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85050991638&partnerID=8YFLogxK
U2 - 10.1109/ICDCS.2018.00044
DO - 10.1109/ICDCS.2018.00044
M3 - Conference contribution
AN - SCOPUS:85050991638
T3 - Proceedings - International Conference on Distributed Computing Systems
SP - 365
EP - 375
BT - Proceedings - 2018 IEEE 38th International Conference on Distributed Computing Systems, ICDCS 2018
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 2 July 2018 through 5 July 2018
ER -