APPLICATION FUNCTIONS PLACEMENT OPTIMIZATION IN A MOBILE DISTRIBUTED CLOUD ENVIRONMENT
DOI:
https://doi.org/10.24193/subbi.2018.2.03Keywords:
5G, Distributed Cloud, Distributed Computing, Application Partitioning, Edge Computing, Augmented Reality.Abstract
Distributed Computing in 5G Mobile Networks is a potential requirement for certain applications that depends on low latency and information sharing through or with data information sources. Such applications may be observed as a distributed application. We present a tool and method to optimize the deployment of distributed applications, dividing it into Modules, in a 5G Mobile Network environment. To do so we apply an approximation algorithm for the Path Computation and Function Placement Problem described in [1]. We show that under certain circumstances it is beneficial to deploy parts of such applications in a Cloud Computing environment with Distributed Cloud resources at the Mobile Network Edge. We verify our findings with an example, an Augmented Reality application.
References
G. Even, M. Rost, and S. Schmid, “An approximation algorithm for path computation and function placement in sdns,” in International Colloquium on Structural Information and Communication Complexity, pp. 374–390, Springer, 2016.
E. AB, “5g systems, enabling the transformation of industry and society,” white paper, ERICSSON, 2017.
J. Liu, E. Ahmed, M. Shiraz, A. Gani, R. Buyya, and A. Qureshi, “Application partitioning algorithms in mobile cloud computing: Taxonomy, review and future directions,” Journal of Network and Computer Applications, vol. 48, pp. 99–117, 2015.
I. Giurgiu, O. Riva, D. Juric, I. Krivulev, and G. Alonso, “Calling the cloud: enabling mobile phones as interfaces to cloud applications,” in Proceedings of the 10th ACM/IFIP/USENIX International Conference on Middleware, p. 5, Springer-Verlag New York, Inc., 2009.
L. Yang, J. Cao, Y. Yuan, T. Li, A. Han, and A. Chan, “A framework for partitioning and execution of data stream applications in mobile cloud computing,” ACM SIGMET-RICS Performance Evaluation Review, vol. 40, no. 4, pp. 23–32, 2013.
R. Newton, S. Toledo, L. Girod, H. Balakrishnan, and S. Madden, “Wishbone: Profile-based partitioning for sensornet applications.,” in NSDI, vol. 9, pp. 395–408, 2009.
X. Gu, K. Nahrstedt, A. Messer, I. Greenberg, and D. Milojicic, “Adaptive offloading inference for delivering applications in pervasive computing environments,” in Pervasive Computing and Communications, 2003. (PerCom 2003). Proceedings of the First IEEE International Conference on, pp. 107–114, IEEE, 2003.
A. Messer, I. Greenberg, P. Bernadat, D. Milojicic, D. Chen, T. J. Giuli, and X. Gu, “Towards a distributed platform for resource-constrained devices,” in Distributed Computing Systems, 2002. Proceedings. 22nd International Conference on, pp. 43–51, IEEE, 2002.
L. Wang and M. Franz, “Automatic partitioning of object-oriented programs for resource-constrained mobile devices with multiple distribution objectives,” in Parallel and Distributed Systems, 2008. ICPADS’08. 14th IEEE International Conference on, pp. 369–376, IEEE, 2008.
L. Yang, J. Cao, and H. Cheng, “Resource constrained multi-user computation partitioning for interactive mobile cloud applications,” Technical reort. Department of Computing, Hong Kong Polytechnical University, 2012.
D. Kovachev, “Framework for computation offloading in mobile cloud computing,” IJI-MAI, vol. 1, no. 7, pp. 6–15, 2012.
M.-R. Ra, B. Priyantha, A. Kansal, and J. Liu, “Improving energy efficiency of personal sensing applications with heterogeneous multi-processors,” in Proceedings of the 2012 ACM Conference on Ubiquitous Computing, pp. 1–10, ACM, 2012.
E. Cuervo, A. Balasubramanian, D.-k. Cho, A. Wolman, S. Saroiu, R. Chandra, and P. Bahl, “Maui: making smartphones last longer with code offload,” in Proceedings of the 8th international conference on Mobile systems, applications, and services, pp. 49–62, ACM, 2010.
B.-G. Chun, S. Ihm, P. Maniatis, M. Naik, and A. Patti, “Clonecloud: elastic execution between mobile device and cloud,” in Proceedings of the sixth conference on Computer systems, pp. 301–314, ACM, 2011.
M. Goraczko, J. Liu, D. Lymberopoulos, S. Matic, B. Priyantha, and F. Zhao, “Energyoptimal software partitioning in heterogeneous multiprocessor embedded systems,” in Proceedings of the 45th annual design automation conference, pp. 191–196, ACM, 2008.
T. Verbelen, T. Stevens, F. De Turck, and B. Dhoedt, “Graph partitioning algorithms for optimizing software deployment in mobile cloud computing,” Future Generation Computer Systems, vol. 29, no. 2, pp. 451–459, 2013.
B. Hendrickson and T. G. Kolda, “Graph partitioning models for parallel computing,” Parallel computing, vol. 26, no. 12, pp. 1519–1534, 2000.
H. Meyerhenke, B. Monien, and S. Schamberger, “Graph partitioning and disturbed diffusion,” Parallel Computing, vol. 35, no. 10-11, pp. 544–569, 2009.
S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” science, vol. 220, no. 4598, pp. 671–680, 1983.
F. Berman, “High-performance schedulers,” The grid: blueprint for a new computing infrastructure, vol. 67, pp. 279–309, 1999.
D. L. Long and L. A. Clarke, “Task interaction graphs for concurrency analysis,” in Proceedings of the 11th international conference on Software engineering, pp. 44–52, ACM, 1989.
M. Naghibzadeh, “Modeling workflow of tasks and task interaction graphs to schedule on the cloud,” CLOUD COMPUTING 2016, p. 81, 2016.
D. Grove and C. Chambers, “Ibm research report an assessment of call graph construction algorithms,” 06 2000.
M. Masdari, S. S. Nabavi, and V. Ahmadi, “An overview of virtual machine placement schemes in cloud computing,” Journal of Network and Computer Applications, vol. 66, pp. 106–127, 2016.
X. Meng, V. Pappas, and L. Zhang, “Improving the scalability of data center networks with traffic-aware virtual machine placement,” in INFOCOM, 2010 Proceedings IEEE, pp. 1–9, IEEE, 2010.
R. A. da Silva and N. L. da Fonseca, “Algorithm for the placement of groups of virtual machines in data centers,” in Communications (ICC), 2015 IEEE International Conference on, pp. 6080–6085, IEEE, 2015.
J. Chase, R. Kaewpuang, W. Yonggang, and D. Niyato, “Joint virtual machine and bandwidth allocation in software defined network (sdn) and cloud computing environments,” in Communications (ICC), 2014 IEEE International Conference on, pp. 2969– 2974, IEEE, 2014.
J. Halpern and C. Pignataro, “Service function chaining (sfc) architecture,” tech. rep., 2015.
B. Addis, D. Belabed, M. Bouet, and S. Secci, “Virtual network functions placement and routing optimization,” in Cloud Networking (CloudNet), 2015 IEEE 4th International Conference on, pp. 171–177, IEEE, 2015.
Y. Xie, Z. Liu, S. Wang, and Y. Wang, “Service function chaining resource allocation: A survey,” arXiv preprint arXiv:1608.00095, 2016.
T. Taleb, M. Bagaa, and A. Ksentini, “User mobility-aware virtual network function placement for virtual 5g network infrastructure,” in Communications (ICC), 2015 IEEE International Conference on, pp. 3879–3884, IEEE, 2015.
R. Cohen, L. Lewin-Eytan, J. S. Naor, and D. Raz, “Near optimal placement of virtual network functions,” in Computer Communications (INFOCOM), 2015 IEEE Conference on, pp. 1346–1354, IEEE, 2015.
M. F. Bari, S. R. Chowdhury, R. Ahmed, and R. Boutaba, “On orchestrating virtual network functions,” in Network and Service Management (CNSM), 2015 11th International Conference on, pp. 50–56, IEEE, 2015.
A. Mohammadkhan, S. Ghapani, G. Liu, W. Zhang, K. Ramakrishnan, and T. Wood, “Virtual function placement and traffic steering in flexible and dynamic software defined networks,” in Local and Metropolitan Area Networks (LANMAN), 2015 IEEE International Workshop on, pp. 1–6, IEEE, 2015.
M. Bouet, J. Leguay, and V. Conan, “Cost-based placement of virtualized deep packet inspection functions in sdn,” in Military Communications Conference, MILCOM 2013-2013 IEEE, pp. 992–997, IEEE, 2013.
R. Mijumbi, J. Serrat, J.-L. Gorricho, N. Bouten, F. De Turck, and S. Davy, “Design and evaluation of algorithms for mapping and scheduling of virtual network functions,” in Network Softwarization (NetSoft), 2015 1st IEEE Conference on, pp. 1–9, IEEE, 2015.
B. Hendrickson and R. W. Leland, “A multi-level algorithm for partitioning graphs.,” SC, vol. 95, no. 28, pp. 1–14, 1995.
S. Lin and B. W. Kernighan, “An effective heuristic algorithm for the traveling-salesman problem,” Operations research, vol. 21, no. 2, pp. 498–516, 1973.
G. Karypis and V. Kumar, “Metis – unstructured graph partitioning and sparse matrix ordering system, version 2.0,” tech. rep., 1995.
K. Ha, P. Pillai, W. Richter, Y. Abe, and M. Satyanarayanan, “Just-in-time provisioning for cyber foraging,” in Proceeding of the 11th annual international conference on Mobile systems, applications, and services, pp. 153–166, ACM, 2013.
P. Raghavan, Randomized rounding and discrete ham-sandwich theorems: provably good algorithms for routing and packing problems. University of California. Computer Science Division, 1986.
N. Nethercote and J. Seward, “Valgrind: a framework for heavyweight dynamic binary instrumentation,” in ACM Sigplan notices, vol. 42, pp. 89–100, ACM, 2007.
W. Scott, “Content delivery networks (cdn): Caching principles, architecture, and resource optimization.” https://www.slideshare.net/hacktivism/cisco-live-content-delivery-networks-cdn, 2017. Online; accessed 29-March-2018.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2018 Studia Universitatis Babeș-Bolyai Informatica
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
