Efficient placement of multi-component applications in edge computing systems

ABSTRACT

Mobile Edge Computing (MEC) is a new paradigm which has been introduced to solve the inefficiencies of mobile cloud computing technologies. The key idea behind MEC is to enhance the capabilities of mobile devices by forwarding the computation of applications to the edge of the network instead of to a cloud data-center. One of the main challenges in MEC is determining an efficient placement of the components of a mobile application on the edge servers that minimizes the cost incurred when running the application. In this paper, we address the problem of multi-component application placement in edge computing by designing an efficient heuristic on-line algorithm that solves it. We also present a Mixed Integer Linear Programming formulation of the multi-component application placement problem that takes into account the dynamic nature of users' location and the network capabilities. We perform extensive experiments to evaluate the performance of the proposed algorithm. Experimental results indicate that the proposed algorithm has very small execution time and obtains near optimal solutions.

References

1. 2009. IBM ILOG CPLEX V12.1 User's Manual. (2009). ftp://ftp.software.ibm.com/software/websphere/ilog/docs/
2. Nikhil Bansal, Kang-Won Lee, Viswanath Nagarajan, and Murtaza Zafer. 2011. Minimum congestion mapping in a cloud. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. ACM, 267--276.
3. Michael Till Beck, Martin Werner, Sebastian Feld, and S Schimper. 2014. Mobile edge computing: A taxonomy. In Proceedings of the Sixth International Conference on Advances in Future Internet. 48 -- 54.
4. Flavio Bonomi, Rodolfo Milito, Jiang Zhu, and Sateesh Addepalli. 2012. Fog computing and its role in the internet of things. In Proceedings of the First Edition of the MCC Workshop on Mobile Cloud Computing. ACM, 13--16.
5. Tracy Camp, Jeff Boleng, and Vanessa Davies. 2002. A survey of mobility models for ad hoc network research. Wireless communications and mobile computing 2, 5 (2002), 483--502.
6. Mosharaf Chowdhury, Muntasir Raihan Rahman, and Raouf Boutaba. 2012. Vineyard: Virtual network embedding algorithms with coordinated node and link mapping. IEEE/ACM Transactions on Networking (TON) 20, 1 (2012), 206--219.
7. Debojyoti Dutta, Michael Kapralov, Ian Post, and Rajendra Shinde. 2012. Embedding paths into trees: VM placement to minimize congestion. In European Symposium on Algorithms. Springer, 431--442.
8. Xiaopeng Fan, Jiannong Cao, and Haixia Mao. 2011. A survey of mobile cloud computing. zTE Communications 9, 1 (2011), 4--8.
9. Jason Flinn and M. Satyanarayanan. 1999. Energy-aware Adaptation for Mobile Applications. In Proceedings of the Seventeenth ACM Symposium on Operating Systems Principles (SOSP '99). 48--63.
10. Adlen Ksentini, Tarik Taleb, and Min Chen. 2014. A Markov decision process-based service migration procedure for follow me cloud. In 2014 IEEE International Conference on Communications (ICC). IEEE, 1350--1354.
11. H. W. Kuhn. 1955. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly 2, 1--2 (1955), 83--97.
12. Milan Patel, B Naughton, C Chan, N Sprecher, S Abeta, A Neal, and others. 2014. Mobile-edge computing introductory technical white paper. White Paper, Mobile-edge Computing (MEC) industry initiative (2014).
13. Alexey Rudenko, Peter Reiher, Gerald J Popek, and Geoffrey H Kuenning. 1998. Saving portable computer battery power through remote process execution. ACM SIGMOBILE Mobile Computing and Communications Review 2, 1 (1998), 19--26.
14. Mahadev Satyanarayanan. 2015. A brief history of cloud offload: A personal journey from odyssey through cyber foraging to cloudlets. GetMobile: Mobile Computing and Communications 18, 4 (2015), 19--23.
15. Mahadev Satyanarayanan, Paramvir Bahl, Ramón Caceres, and Nigel Davies. 2009. The case for vm-based cloudlets in mobile computing. IEEE Pervasive Computing 8, 4 (2009), 14--23.
16. Tarik Taleb and Adlen Ksentini. 2013. Follow me cloud: interworking federated clouds and distributed mobile networks. IEEE Network 27, 5 (2013), 12--19.
17. Rahul Urgaonkar, Shiqiang Wang, Ting He, Murtaza Zafer, Kevin Chan, and Kin K. Leung. 2015. Dynamic service migration and workload scheduling in edge-clouds. Performance Evaluation 91 (2015), 205 -- 228.
18. Shiqiang Wang, Rahul Urgaonkar, Murtaza Zafer, Ting He, Kevin Chan, and Kin K Leung. 2015. Dynamic service migration in mobile edge-clouds. In IFIP Networking Conference (IFIP Networking), 2015. IEEE, 1--9.
19. Shiqiang Wang, Murtaza Zafer, and Kin K Leung. 2017. Online Placement of Multi-Component Applications in Edge Computing Environments. IEEE Access 5 (2017), 2514--2533.

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

      • Cloud computing

• Networks

  • Network services

    • Cloud computing