Tài liệu Tối ưu hóa triển khai các ứng dụng iot trong hệ thống cloud fog

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 1 Introduction 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Research questions . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.5 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 Literature review 9 2.1 Fog computing and the Internet of Things . . . . . . . . . . . . . 9 2.1.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1.2 Reference Architecture . . . . . . . . . . . . . . . . . . 10 2.2 IoT services . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3 Optimal services deployment problem . . . . . . . . . . . . . . . 16 vi 3 5 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 4 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 . . . . . . . . . . . . . 2 1.2 IoT services in Cloud-Fog system . . . . . . . . . . . . . . . . . 3 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 List of Tables 2.1 Differences between cloud and fog computing . . . . . . . . . . 11 2.2 Comparison of characteristics of related work . . . . . . . . . . . 21 3.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.1 Cloud-Fog system resources . . . . . . . . . . . . . . . . . . . . 37 xi Chapter 1 Introduction 1.1 Motivation Along with the development of connected devices and smart environments, the Internet of Things (IoT) has been receiving attention for years that the most obvious evidence is the growth in the number of devices over time. It enables a new breed of services and applications expected to analyze and augment captured data from IoT devices to create meaningful information for the end-users. Due to the limitations of computing and storage on devices, cloud computing is considered as a promising computing paradigm, which can provide elastic resources to the IoT services and applications. However, for those applications with low latency, location-awareness, mobility support requirements, the current centralized cloud paradigm, which tends to concentrate computing and storage resources in a few large data centers, will be no longer suitable. Recently, Cisco has introduced Fog computing as a new paradigm which takes advantage of the extensive resources in the cloud while being able to expand computing power to the edge of the network, close to end-users [2, 3]. Fig. 1.1 illustrates the architecture of a Cloud-Fog system with three hierarchical layers where VNFs are deployed to implement service functions. At the edgemost of the network is the device layer which contains numerous sensory nodes. They can be widely distributed at various public infrastructures to monitor their condition changes over time. Each node either collects data (i.e., video, temperature, noise) or performs a certain function (i.e., sprinkle, smart light). Data gener1 Figure 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 network devices or even user devices, which located in a wide-spread geographical area, together they form the fog layer that lies between the device layer and the cloud layer. Each fog node is connected to and responsible for a group of IoT devices, performing data analysis in a timely manner. Thanks to the virtualization technology, the fog nodes with heterogeneous resources can provide the ability to implement IoT service functions, providing the ability to reduce network load as well as ensure service QoS constraints including latency and location-awareness. On top of the architecture is cloud layer consists of a number of powerful servers allocated in a few data centers. The cloud layer is considered as an unlimited resource pool providing an ability to host VNFs that process computational-intensive tasks, store a massive amount of data. The IoT services take an important part in the Cloud-Fog system paradigm. It takes the form of the service layer above the shared physical infrastructure layer as illustrated in Fig. 1.2. A key aspect of increasing service performance and energy efficiency is the actual deployment of services functions. Deployment 2 decisions need to address the resource requirements of the services, make sure that the services meet its QoS constraints, and reduce the overall running cost of the system. The allocation of resources in a non-optimal way will result in both low-performance of services and an increase in the number of physical servers to use while some of these servers have a very low usage rate. 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 is still facing many challenges. While IoT service functions prefer to be hosted at the nearby fog nodes instead of cloud to obtain the low latency and location tracking, a fog node can only host a limited number of the service functions due to its resource capabilities. Unlike fog nodes, the cloud is considered as a powerful and unlimited resources pool to deploy IoT service functions. However, the cloud is far from IoT device networks, deploying IoT service functions to cloud may cause the increasing of network load and service latency. The network operator has, therefore, to optimize resource utilization while satisfying strict latency constraints when deploying IoT applications. While the prior works focus on application placement problem which tries to map application functions into 3 physical resources, we go a further step in this work by taking into account a multi-layer mapping where service functions are deployed into virtual resources before being mapping to physical resources. The Cloud-Fog system is composed of services, virtual resources, and physical resources. The virtual layer contains a network of virtual machines that host IoT service functions and be deployed to the physical layer. The virtual machine has a limited number of flavors that define a number of parameters in which the virtual machine belongs to. We formulate an optimization problem that performs multi-layer mapping that reduces energy costs and increases resource utilization in both fog and cloud. Unfortunately, our optimization model belongs to the NP-hard form that challenges any solver to find an optimal solution in polynomial time. We propose a greedy-based algorithm to obtain a near-optimal solution for the problem within an acceptable period of time. In this thesis, we propose a solution for finding optimal IoT services deployment in the Cloud-Fog system, where the goal is to find the appropriate virtual machines for each service function and then place the network of the virtual machines onto Cloud-Fog system infrastructure that minimizes the overall energy consumption. Our contributions can be summarized as follows: • We formulate the problem of the combination of IoT services deployment and virtual machine consolidation in the Cloud-Fog system as a mixed-integer linear program with three layers in the Cloud-Fog system including the service layer, virtual layer, and physical infrastructure layer. • We propose a greedy-based solution for solving the problem of optimized deployment of IoT services in the Cloud-Fog system in which tries to solve each phase of the deployment process sequentially. 1.2 Problem statement The Cloud-fog system is considered to be an efficient solution for providing resources to handle newly emerging IoT services with tightly QoS constraints. However, while the basic ideas and theoretical foundations of fog computing have been established [1, 2], deploying IoT services onto a Cloud-Fog system is still facing many challenges. Offloading IoT services to the cloud may result in an 4 additional network traffic load, increasing unnecessary costs while failing to meet the latency constraints of delay-sensitive services. On the contrary, the computingintensive functions of IoT services can not be deployed to the devices due to its limitations on computing power and battery life. Furthermore, manual deployment of complex IoT services onto the Cloud-Fog system can be complex, timeconsuming and error-prone. Therefore, the resource provider has to offer a service that ensures optimal automatic deployment of IoT services. One of the major issues in implementing the service is solving the problem of optimal deployment of services functions into physical resources. The problem contains selecting of appropriate virtual machines for service functions and then assigning existing resources to the network of these virtual machines according to specific constraints. Typically, an IoT service has its own resource requirements and QoS constraints. The resource requirements of a service often include computing and transmission capacity which referred to a collection of processor, memory, storage and bandwidth capacity that guarantees the properly running of the service. Latency is often referred to when considering the quality requirements of a service. The optimal deployment of IoT services is known as a highly complex process that requires to minimize the mapping costs, ensures the deployed services can meet its requirements as well as maximize the resource utilization. Overall, the following challenges are what we have to face when building the service that optimizes the deployment of IoT services in Cloud-Fog system: • Cost - energy consumption Allocating more resources than required when virtualizing services will incur unnecessary costs, whereas allocating insufficient resources will lead to the poor performance operation of the services. Besides, Cloud-Fog system is a heterogeneity multi-layered system in which each resource has its own processing, storage, and transmission capabilities as well as energy efficiency, the deployment strategy will determine the operating cost of the services. Our proposed solution has to take into account the capabilities and energy efficiency of computing and transmission resources to minimize the energy consumption of the system. 5 • QoS constraints Cost minimization may result in the low-performance of the services. The challenge here is to provide the IoT services with required QoS constraints with the optimal energy consumption. For example, the cloud may have powerful resources with high energy efficiency, however, it is far away from enduser devices while the fog nodes close to end-user have a limitation on computing power. A good deployment strategy is to deploy computing-intensive functions onto the cloud and the delay-intensive functions onto nearby fog nodes. Therefore, our solution has to come with a strategy that ensures QoS for IoT services by taking the location and link delay into consideration. • Resource utilization The allocation of resources in a non-optimal way will result in an increase in the number of physical servers to use while some of these servers have a very low usage rate. These servers contribute significantly to rising operating costs, low energy efficiency. Virtual machines consolidation promises to be a significant emerging solution to alleviate these problems. Basically, the Cloud-Fog system is built up of numerous physical servers and each of these servers can run multiple virtual machines. Theoretically, virtual machine consolidation concentrates target VMs into as small a number of running physical servers as possible according to their resource demands. Underutilized servers should be switched to the sleep mode or switched off so that they consume no power [4]. A consolidation strategy has to be taken into account to maximize resource utilization. 1.3 Research questions To address the aforementioned challenges, the following key research questions have been raised: • RQ1: How should we model IoT services to optimally virtualize each service function in Cloud-Fog system? The proposed system model must demonstrate characteristics of IoT services 6 including resource requirements, latency, and location constraints as well as taking into account the heterogeneous, distributed manner of the Cloud-Fog system. • RQ2: How the problem of optimal deployment of IoT services in Cloud-Fog system should be formulated? The proposed formulation for the problem will use the proposed system model and define a set of mathematical expressions to represent the system’s constraints. • RQ3: How can we optimally deploy IoT services onto the Cloud-Fog system with given resource constraints in order to meet service requirements and minimize the total energy consumption of the system? The purpose is to design an algorithm that efficiently allocates compute and networking resources to IoT services at minimal cost and maximal resource utilization while meeting service requirements. 1.4 Objectives Our main objective, in this thesis, is to propose a solution that solves the optimal deployment of IoT services in the Cloud-Fog system. It is divided into sub-objectives as follows: • O1: Building a mathematical model that represents the IoT services and Cloud-Fog system. • O2: Building an optimization model for minimizing the total energy consumption of the system while maintaining the resource requirements and QoS constraints of IoT services. • O3: Design an algorithm that optimizes the IoT services deployment onto Cloud-Fog system running in near real-time. The algorithm will collect information about services requirements and substrate resources at a centralized network controller, find the optimal deployment and disseminating the solution to all network nodes. 7 • O4: Carrying our simulations to validate the outperformance of our solution compared to existing solutions. 1.5 Outline This thesis is divided into five chapters organized as follows: • The first chapter is a general introduction. We first present the general context and motivation of this research. Then, the problem statement, the research questions and the objectives to be achieved are presented. • The second chapter discusses the technical background and the related work. In this chapter, we provide background knowledge needed to understand subsequent materials in the next chapters. Then, we present a review of the prior works that have dealt with the services deployment problem and, based on their findings, a synthesis was made to compare the different existing approaches, their limitations and highlight the contributions of this thesis. • The third chapter presents the methodology. According to the objectives of this thesis, we first present the system modeling and then propose a formulation for optimization of IoT services deployment in the Cloud-Fog system problem. Finally, we design an algorithm to efficiently deploy IoT services onto Cloud-Fog system. • The fourth shows the experiment results of our proposed solution. • I conclude my work in chapter fifth and discuss some possible future works on this problem. 8 Chapter 2 Literature review 2.1 Fog computing and the Internet of Things This section provides background knowledge of this thesis, including fog computing, IoT and the services deployment problem. 2.1.1 Definition Fog computing, a concept introduced by CISCO in 2012, is considered as an extension of the traditional cloud computing paradigm from the core to the edge of the network. It supports virtualization that enables computing at the edge of the network to provide computation, storage, and network services closer to IoT and/or end-user devices where data is being generated [2]. The implementations of fog computing can reside in multiple layers of a network’s topology and the cloud takes an important part in the architecture. Characteristics of fog computing: • Low latency and location-awareness: The fog contains of multiple computing nodes located at the edge of the network close to IoT and/or end-user devices which means that Fog Computing supports endpoints with the finest services at the edge of the network. • Widespread geographical distribution: The fog nodes typically are distributed in a large geographic area. In contrast to traditional centralized cloud, the services and applications targeted by Fog Computing demand widely distributed 9