Mobile edge computing pushes computationally-intensive services closer to the user to provide reduced delay due to physical proximity. This has led many to consider deploying deep learning models on the edge-commonly known as edge intelligence (EI). EI services can have many model implementations that provide different QoS. For instance, one model can perform inference faster than another (thus reducing latency) while achieving less accuracy when evaluated. In this paper, we study joint service placement and model scheduling of EI services with the goal to maximize Quality-of-Servcice (QoS) for end users where EI services have multiple implementations to serve user requests, each with varying costs and QoS benefits. We cast the problem as an integer linear program and prove that it is NP-hard. We then prove the objective is equivalent to maximizing a monotone increasing, submodular set function and thus can be solved greedily while maintaining a (1-1/e)-Approximation guarantee. We then propose two greedy algorithms: one that theoretically guarantees this approximation and another that empirically matches its performance with greater efficiency. Finally, we thoroughly evaluate the proposed algorithm for making placement and scheduling decisions in both synthetic and real-world scenarios against the optimal solution and some baselines. In the real-world case, we consider real machine learning models using the ImageNet 2012 data-set for requests. Our numerical experiments empirically show that our more efficient greedy algorithm is able to approximate the optimal solution with a 0.904 approximation on average, while the next closest baseline achieves a 0.607 approximation on average.
|Title of host publication||30th International Conference on Computer Communications and Networks, ICCCN 2021|
|State||Published - Jul 2021|
|Event||30th International Conference on Computer Communications and Networks, ICCCN 2021 - Virtual, Athens, Greece|
Duration: Jul 19 2021 → Jul 22 2021
|Name||Proceedings - International Conference on Computer Communications and Networks, ICCCN|
|Conference||30th International Conference on Computer Communications and Networks, ICCCN 2021|
|Period||7/19/21 → 7/22/21|
Bibliographical noteFunding Information:
ACKNOWLEDGEMENTS This material is based upon work supported by the National Science Foundation under grant no. CSR-1948387. This work was also partially funded by Cisco Systems Inc. under the research grant number 1215519250. We thank both our sponsors for their generous support.
© 2021 IEEE.
- Deep Learning
- Edge Computing
- Edge Intelligence
- Service Placement
ASJC Scopus subject areas
- Computer Networks and Communications
- Hardware and Architecture