VIETNAM NATIONAL UNIVERSITY, HANOI UNIVERSITY OF ENGINEERING AND TECHNOLOGY DANG VAN DO OPTIMIZATION OF IOT SERVICES DEPLOYMENT IN CLOUD-FOG SYSTEM MASTER THESIS Major: Data Communication and Computer Networks HA NOI - 2019 VIETNAM NATIONAL UNIVERSITY, HANOI UNIVERSITY OF ENGINEERING AND TECHNOLOGY Dang Van Do OPTIMIZATION OF IOT SERVICES DEPLOYMENT IN CLOUD-FOG SYSTEM MASTER THESIS Major: Data Communication and Computer Networks Supervisor: Dr Tran Truc Mai Assoc.Prof Nguyen Kim Khoa HA NOI - 2019 Abstract With the predicted explosion in the number of connected devices, sensors and extremely large amount of data generated need to be analyzed, the current cloud paradigms, which tend to me concentrate computing and storage resources in a few large data centers, will inevitably lead to excessive network load, end-to-end service latency, and overall power consumption This leads to the creation of new network architectures that extend computing and storage capabilities to the edge of the network, close to end-users Along with the new network architectures, it enables a new breed of services and applications with tightly Quality of services The emerging problem is how to efficiently deploy the services to the system that satisfies service resource requirements and QoS constraints while maximizing resource utilization In this thesis, we investigate the problem of IoT services deployment in CloudFog system to provide IoT services with minimal resource usage cost We formulate the problem using a Mixed-Integer Linear Programming model taking into account the characteristics of computing and transmission resources in Cloud-Fog system as well as the IoT services specific requirements Our solution provides a multi-layer mapping mechanism that efficiently deploys IoT services to the appropriate virtual network in physical infrastructure Unfortunately, our proposed model is unable to solve in polynomial time due to it is NP-hard We propose greedy-based algorithms for solving the problem which tries to solve each phase of the deployment process sequentially We illustrate the utility of our solutions over a motivating example where we compare the efficiency of our solutions with the existing solutions for a traffic monitoring service The experimental results show that our proposed solution outperforms compared to existing solutions in terms of energy efficiency iii Acknowledgements I would like to express my sincere gratitude to Dr Tran Truc Mai and Assoc Prof Nguyen Kim Khoa, my supervisors, for providing continuous support to my studies and research, for their patience, motivation, enthusiasm and immense knowledge Their guidance helped me all the time doing this research and writing this thesis My sincere thanks also go to the Faculty of Information and Technology, University of Engineering and Technology, Vietnam National University for providing me all the necessary facilities to make this research project easier Finally, I would like to say thanks to my family, my friends who have always believed, motivated and supported me throughout the past process to achieve today’s results iv Declaration I hereby declare that this thesis was entirely my own work and that any additional sources of information have been duly cited I certify that, to the best of my knowledge, my thesis does not infringe upon anyone’s copyright nor violate any proprietary rights and that any ideas, techniques, quotations, or any other material from the work of other people included in my thesis, published or otherwise, are fully acknowledged in accordance with the standard referencing practices Furthermore, to the extent that I have included copyrighted material, I certify that I have obtained written permission from the copyright owner(s) to include such material(s) in my thesis and have included copies of such copyright clearances to my appendix I declare that this thesis has not been submitted for a higher degree to any other University or Institution v Table of Contents Abstract iii Acknowledgements iv Declaration v Table of Contents vii Acronyms viii List of Figures x List of Tables xi Introduction 1.1 Motivation 1.2 Problem statement 1.3 Research questions 1.4 Objectives 1.5 Outline Literature review 2.1 Fog computing and the Internet of Things 2.1.1 Definition 2.1.2 Reference Architecture 10 2.2 IoT services 14 2.3 Optimal services deployment problem 16 vi Algorithms 16 2.3.2 Comparison and discussion 20 Methodology 22 3.1 System model 22 3.1.1 Network model 22 3.1.2 Service model 23 3.1.3 Virtual layer model 24 The optimization of IoT services deployment in Cloud-Fog system 24 3.2.1 MILP formulation 24 3.2.2 Deployment model 32 3.2 2.3.1 Experiment results and discussion 36 4.1 Experiment results 36 4.1.1 Simulation details 36 4.1.2 Simulation scenarios 38 Conclusion 42 vii Acronyms 4G Fourth Generation CPU Central Processing Unit DC Data Center Gbps Gigabit per second IoT Internet of Things J/bit Joule per bit Mbps Megabit per second MCF Multi-commodity Flow MILP Mixed Integer Linear Programming MIPS Millions of Instructions Per Second NP Non-deterministic Polynomial-time QoS Quality of Service TCP Transmission Control Protocol UDP User Datagram Protocol viii VM Virtual Machine VNE Virtual Network Embedding VNF Virtual Network Function WSN Wireless Sensor Network ix List of Figures 1.1 Three-layer Cloud-Fog system paradigm 1.2 IoT services in Cloud-Fog system 2.1 Fog computing reference architecture [1] 12 3.1 Traffic monitoring service model 23 3.2 Services deployment problem 26 4.1 Smart city infrastructure used in our simulations 37 4.2 Average power consumption of the traffic monitoring service for different amounts of energy consumed by server nodes in idle state 39 4.3 Average power consumption of the traffic monitoring service for different edge node efficiencies x 40 consumed by a physical node is defined in (3.5) which contained the consumed energy when it doing nothing but power on and the consumed energy when processing computing tasks btj u ct αu pu = du σu + ∀u ∈ V p (3.5) t,j The equation (3.6) defines the energy consumed by a link to transmit data between nodes xiuv cei αuv puv = ∀u, v ∈ V p (3.6) ei ∈A • Flow-related constraints: Constraint set (3.7)-(3.9) refers to the flow conservation conditions, which denote that the net flow to a node must be zero except for source node si and sink node ti xiuv − v∈V s xivu = ∀ei ∈ A, ∀u ∈ V s \{si , ti } (3.7) v∈V s xisi w − w∈V s xiwsi = ∀ei ∈ A (3.8) xiwti = −1 ∀ei ∈ A (3.9) w∈V s xiti w − w∈V s w∈V s • Capacity constraints: The summation of flows on the link (u, v ) has to remain within its available bandwidth xiuv cei ≤ ruv ∀u, v ∈ V s (3.10) ei ∈A Constraint set (3.11) and (3.12) enforces the capacity bounds of nodes and virtual machines on node The constraint (3.12) shows that virtual functions deployed in the virtual machine are provided with its required computing power The constraint (3.11) ensures that the total computing resource required by all of the virtual machines on a physical node remains within its computing capacity btj u ct ≤ ru ∀u ∈ V p (3.11) ∀u, t, j (3.12) t,j btjw u λw ≤ ct w∈F 30 • QoS constraints: Latency: Constraint (3.13) refers to the latency requirement of each virtual link The total delay of substrate links that the virtual link mapped to must less than or equal to the virtual link latency constraint huv xiuv ≤ hei ∀ei ∈ A (3.13) u,v∈V s • Deployment restrictions: The set guarantees that only one substrate node is selected for each VNF and all of the VNFs will be deployed to the appropriate substrate node btjw u = ∀w ∈ F (3.14) u,t,j i btjw u ≥ xwu ∀ei ∈ A, ∀u ∈ V p , ∀w ∈ F (3.15) i btjw u ≥ xuw ∀ei ∈ A, ∀u ∈ V p , ∀w ∈ F (3.16) t,j t,j tjw btj u ≥ bu ∀i, t, j, ∀u ∈ V p , ∀w ∈ F (3.17) The node u is known as power on if there is any virtual machine is running in it du ≥ btj u ∀t, j, ∀u ∈ V p (3.18) • Domain constraints: xiuv : A variable indicates the fraction of the ith virtual link is embedded in the substrate link (u, v) xiuv ∈ [0, 1] ∀i, ∀u, v ∈ V s (3.19) btjw u : A binary variable takes the value “1” if the virtual function w is deployed to the j th virtual machine type t on physical node u; Otherwise, it’s set to “0” p btjw u ∈ {0, 1} ∀t, j, ∀u ∈ V , w ∈ F (3.20) btj u : A binary variable, which has the value “1” if the j th virtual machine of type t is running on physical node u; Otherwise, it’s set to “0” p btj u ∈ {0, 1} ∀t, j, ∀u ∈ V 31 (3.21) du : A binary variable, which has the value “1” when physical node u is power on; Otherwise, it’s set to “0” du ∈ {0, 1} ∀u ∈ V p (3.22) • We remark that the solution for IoT services deployment in Cloud-Fog system is centralized It requires collecting information about services requirements and network resources at a centralized network controller and disseminating the solution to all network nodes 3.2.2 Deployment model The Cloud-Fog system is designed following the suggested in [16] with the Resource management service responsible for most tasks related to resource discovery, resource allocation, the dynamic joining and leaving of fog node, and provisioning and maintaining the resource pool in a distributed manner When a service deployment request arrives, the Resource management service has to determine whether to accept the request or not based on its requirements and constraints and residual capacity of the system If the request is accepted, the Resource management service will find a suitable deployment for the service and allocate resources to the deployment Since solving a MILP is known to be computationally intractable, simultaneous function and link mapping using MILP is practically infeasible Hence, we propose two greedy-based strategies for solving each phase of the deployment process sequentially The first one is presented in Algorithm which tries to deploy each of the service functions into appropriate virtual machines first and then embed the network of the virtual machines onto physical infrastructure network The second strategy tries to map services function to the satisfying physical nodes first and then apply the consolidation mechanism to pack the service functions in each node into virtual machines presented in Algorithm The Algorithm takes service deployment request as input and creates a virtual network that host the service one at a time For each VNF of the input service, the procedure creates a virtual function base on a flavor in the list of virtual machine flavors that has minimum processing capacity while satisfying the CPU capacity required by the VNF Next, for each virtual node, the procedure first checks 32 Algorithm Service deployment with function-to-vm mapping first 1: procedure S ERVICE D EPLOYMENT(F , A) 2: Vv ← Ø 3: Ev ← Ø 4: for all f ∈ F 5: Let tmin = arg mint∈T {ct |ct ≥ λf } 6: Create virtual machine w belong to type tmin 7: ϕf ← w 8: V v += w 9: for all ei ∈ A 10: Create Virtual link (ϕsi , ϕti ) 11: E v += (ϕsi , ϕti ) 12: 13: for all w ∈ V v if Ωw \{u ∈ Ωw |ru < cw } == Ø then 14: Reject the request 15: return 16: for all u ∈ Ωw 17: u ← ru cu αu 18: Let umin = arg minu∈Ωw { u |ru ≥ cw } 19: MN (w) ← umin 20: Update residual capacities of node umin 21: Solve MCF to map virtual links in E v 22: if MCF succeeded then 23: 24: 25: Update residual capacities of system resources else Reject the request 33 Algorithm Service deployment with function-to-node mapping first 1: procedure V IRTUAL N ETWORK D EPLOYMENT(F , A) 2: 3: for all f ∈ F if Ωf \{u ∈ Ω|ru < λf } == Ø then 4: Reject the request 5: return 6: for all u ∈ Ωf 7: u ← ru cu αu 8: Let umin = arg minu∈Ωw { u |ru ≥ λf } 9: MF (f ) += umin 10: for all u ∈ V p 11: Iterative best-fit decreasing mapping 12: Update residual capacities of node u 13: Solve MCF to map virtual links 14: if MCF succeeded then 15: 16: 17: Update residual capacities of system resources else Reject the request 34 [17] whether there are any possible substrate nodes within its Ω set that remaining with enough available CPU capacity If any of the Ω sets is empty, the procedure rejects the request and stops immediately Otherwise, for each virtual node w, the procedure calculates a value u for each substrate node u ∈ Ωw u is cal- culated as a fraction of the available CPU capacity ru of node u and the product of total capacity cu and the processing cost αu of node u The value u helps use to sort the substrate nodes by its processing cost and remaining available resource compare to its own capacity The procedure maps the virtual node w to the node with minimum u value while satisfied with the resource requirement of w to archive the minimum cost when running the virtual node Once all the virtual nodes have been mapped to suitable substrate nodes, the procedure applies the multi-commodity flow (MCF) algorithm to map the virtual links in E v onto substrate paths Finally, it updates the residual capacities on system resources The Algorithm tries to map the VNFs to the substrate nodes first and then to pack the VNFs in each node into virtual machines It takes the service deployment request as input For each VNF of the service, the procedure checks whether there any substrate nodes within its Ω set that remaining with enough available CPU capacity for the VNF If any of the Ω sets is empty, the procedure rejects the request and stops immediately Otherwise, for each substrate node u within the set Ωf , it calculates value u as defined in procedure Next, the VNF f will be mapped to the node with the minimum value of while satisfied with the resource requirement of f Once all of VNF has been mapped to suitable nodes, the procedure iterates over the substrate nodes and tries to pack the mapped VNFs in the node to appropriate virtual machines The procedure uses the Iterative best-fit decreasing mapping algorithm proposed in [17] to deploy the unmapped VNFs to appropriate virtual machines After that, the procedure applies the multicommodity flow (MCF) algorithm to map the virtual links in E v onto substrate paths Finally, it updates the residual capacities on system resources 35 Chapter Experiment results and discussion 4.1 Experiment results In this section, we present the experiment results from our solution to the services deployment problem in Cloud-Fog systems We investigate and compare the efficiency of our solution with: i) the IoT-Cloud solution from [11] which finds the optimal location of IoT service functions exploiting the full flexibility of the IoT-Cloud infrastructure, and ii) the ViNEYard model in which minimizing the cost of embedding VN request as well as balance the load across the substrate network resources [12] 4.1.1 Simulation details We consider a hierarchical Cloud-Fog system architecture composed of three main layers: i) a cloud layer with cloud nodes located in some large data centers (DC), ii) an access layer, composed of base stations (BS) hosting fog nodes, and iii) a device layer, containing sensors, cameras, smart devices We consider a traffic monitoring service in which users request information about the real-time traffic status in the city The service scheme illustrated in Fig 3.1 contains of VNFs: Video capturing, Video compressor, Vehicle recog36 Table 4.1: Cloud-Fog system resources Capacity Efficiency Cloud node 53.5 Million MIPS 500 MIPS/W Fog node 6.5 Million MIPS 100-500 MIPS/W Smart Device 5000 MIPS MIPS/W Sensor 1000 MIPS MIPS/W Optical link 4480 Gbps 12.6 nJ/bit Wifi link 150 Mbps 300 nJ/bit 4G link (Down/Up) 72/12 Mbps 76.2/19 µJ/bit Figure 4.1: Smart city infrastructure used in our simulations 37 nition, Road condition detection, Congestion detection and Visualization The information about traffic status is generated from the videos captured in surveillance cameras In particular, we assume that there is a video of Mbps generated in each surveillance camera The Video compressor module requires a complexity of 4000 instructions per bit to compress the input video with a compression ratio of 3:1 Both Vehicle recognition and Road condition detection modules require a complexity of 8000 instructions per bit to process the data from the Video compressor module We assume that the Congestion detection module is the highest processing complexity which requires 15000 instructions per bit to generate the real-time traffic status, which requested by users The Visualization receives data from the Congestion detection module and creates a visual map to users with a complexity of 1000 instruction per bit In terms of network access technologies, we assume that half of the users use WiFi and the other half use 4G to access the network In the following, we compute our solution to the deployment problem for the traffic monitoring service in the smart city infrastructure illustrated in Fig 4.1, to evaluate the impact of different system parameters in the Cloud-Fog solution, such as edge node’s efficiency and energy consumed by server node in idle state 4.1.2 Simulation scenarios The change of energy consumed by edge nodes in idle state In Fig 4.2, we show the average energy consumption of Cloud-Fog system for a different amount of energy consumed by server nodes in idle state In this scenario, the fog nodes’ efficiency is set up at 400 MIPS/W We change the amount of energy consumed by server nodes in the idle state from 10% to 50% of the node capacity For the cost sufficiently high, our solution allocates the functions of the service at the edge nodes instead of cloud nodes to reduce the overall energy consumption Otherwise, our solution tends to consolidate the functions to cloud nodes to reduce the number of nodes being used There is a slightly different between the results of Cloud-Fog and Cloud-Fog due to the consolidation mechanism The Cloud-Fog finds the appropriate virtual machine for each VNF first, then deploys them to the physical network It creates an unused space in 38 Figure 4.2: Average power consumption of the traffic monitoring service for different amounts of energy consumed by server nodes in idle state 39 each virtual machine and increases the energy consumption while the Cloud-Fog algorithm has a consolidation mechanism that consolidates VNFs into virtual machines reducing the unused space in virtual machines We also observe that the ViNEYard solution yields the highest overall energy consumption over the solutions This is because of the ViNEYard solution tries to balance the load over the infrastructure resulting in most servers being used The IoT-Cloud solution tends to deploy the service functions at the lost-cost, nearby nodes to reduce the transmission cost However, the cost to run a server is significantly high comparing to the transmission cost over the network Different edge node efficiencies In Fig 4.3, we show the average energy consumption for different edge node efficiencies In this scenario, the simulation results show that our solution chooses Figure 4.3: Average power consumption of the traffic monitoring service for different edge node efficiencies 40 to consolidate the service functions in the data center to take advantage of the high processing efficiency of the cloud server and reduce the number of running nodes The reason for the difference between the results of Cloud-Fog and Cloud-Fog is the same as in the scenario above The ViNEYard solution produces the highest overall energy consumption one more time due to its deployment strategy The IoT-Cloud solution adapts the offloading decisions according to the processing efficiency of edge nodes With the sufficiently high edge nodes efficiency, the IoT-Cloud offloads some functions from cloud nodes to the edge nodes resulting in the increase in the number of nodes being used 41 Chapter Conclusion In this work, we study the problem of optimal IoT services deployment in Cloud-Fog system, which is known as NP-hard problem We propose a mathematical formulation for the problem that captures the characteristics of IoT services, Cloud-Fog system and takes into account the limitation on virtual machine flavors We formulate the problem with three layers including the physical layer, virtual layer, and services layer Our formulation takes into account the multilayer mapping which efficiently deploys IoT services to the appropriate virtual network in physical infrastructure We also propose two greedy-based strategies for solving each phase of the deployment process sequentially Compared to the current approach that only considers finding the placement of IoT service functions and routing of network flows across the infrastructure, we illustrate that our solution outperforms in terms of energy efficiency In the future, we plan to continue our research to provide a more flexible solution model for dynamically deploying services, helping them adapt to the change in the number of users over time 42 References [1] A V Dastjerdi, H Gupta, R N Calheiros, S K Ghosh, and R Buyya, “Fog computing: Principles, architectures, and applications,” in Internet of Things, pp 61–75, Elsevier, 2016 [2] F Bonomi, R Milito, J Zhu, and S Addepalli, “Fog computing and its role in the internet of things,” in Proceedings of the first edition of the MCC workshop on Mobile cloud computing, pp 13–16, ACM, 2012 [3] M Hajibaba and S Gorgin, “A review on modern distributed computing paradigms: Cloud computing, jungle computing and fog computing,” Journal of computing and information technology, vol 22, no 2, pp 69–84, 2014 [4] T Janpan, V Visoottiviseth, and R Takano, “A virtual machine consolidation framework for cloudstack platforms,” in The International Conference on Information Networking 2014 (ICOIN2014), pp 28–33, IEEE, 2014 [5] S Madakam and P Bhagat, “Fog computing in the iot environment: Principles, features, and models,” in Fog Computing, pp 23–43, Springer, 2018 [6] L Atzori, A Iera, and G Morabito, “The internet of things: A survey,” Computer networks, vol 54, no 15, pp 2787–2805, 2010 [7] M Thoma, S Meyer, K Sperner, S Meissner, and T Braun, “On iotservices: Survey, classification and enterprise integration,” in 2012 IEEE International Conference on Green Computing and Communications, pp 257– 260, IEEE, 2012 [8] D G Andersen, “Theoretical approaches to node assignment,” 2014 43 [9] B Meindl and M Templ, “Analysis of commercial and free and open source solvers for linear optimization problems,” Eurostat and Statistics Netherlands within the project ESSnet on common tools and harmonised methodology for SDC in the ESS, vol 20, 2012 [10] I Houidi, W Louati, W B Ameur, and D Zeghlache, “Virtual network provisioning across multiple substrate networks,” Computer Networks, vol 55, no 4, pp 1011–1023, 2011 [11] M Barcelo, A Correa, J Llorca, A M Tulino, J L Vicario, and A Morell, “Iot-cloud service optimization in next generation smart environments,” IEEE Journal on Selected Areas in Communications, vol 34, no 12, pp 4077–4090, 2016 [12] M Chowdhury, M R Rahman, and R Boutaba, “Vineyard: Virtual network embedding algorithms with coordinated node and link mapping,” IEEE/ACM Transactions on Networking (TON), vol 20, no 1, pp 206–219, 2012 [13] M Yu, Y Yi, J Rexford, and M Chiang, “Rethinking virtual network embedding: substrate support for path splitting and migration,” ACM SIGCOMM Computer Communication Review, vol 38, no 2, pp 17–29, 2008 [14] C Pham, K K Nguyen, and M Cheriet, “An approximation mechanism for elastic iot application deployment,” in 2018 9th IEEE Annual Ubiquitous Computing, Electronics & Mobile Communication Conference (UEMCON), pp 159–165, IEEE, 2018 [15] D T Nguyen, C Pham, K K Nguyen, and M Cheriet, “Placement and chaining for run-time iot service deployment in edge-cloud,” IEEE Transactions on Network and Service Management, 2019 [16] S Yi, Z Hao, Z Qin, and Q Li, “Fog computing: Platform and applications,” in 2015 Third IEEE Workshop on Hot Topics in Web Systems and Technologies (HotWeb), pp 73–78, IEEE, 2015 [17] J Kang and S Park, “Algorithms for the variable sized bin packing problem,” European Journal of Operational Research, vol 147, no 2, pp 365–372, 2003 44 ... Figure 1.2: IoT services in Cloud- Fog system While the basic ideas and theoretical foundations of fog computing have been established, the optimal deployment of IoT services onto the Cloud- Fog environment... 1.1: Three-layer Cloud- Fog system paradigm ated by IoT devices can be sent to and processed by the VNFs deployed at the fog nodes nearby the data sources The fog nodes can be micro clouds, access... Sensor Network ix List of Figures 1.1 Three-layer Cloud- Fog system paradigm 1.2 IoT services in Cloud- Fog system 2.1 Fog computing reference architecture [1]