# Placement of IoT Microservices in Fog Computing Systems: A Comparison of Heuristics
###### Abstract  
In the last few years, fog computing has been recognized as a promising approach to support modern IoT applications based on microservices. The main characteristic of this application involve the presence of geographically distributed sensors or mobile end users acting as sources of data. Relying on a cloud computing approach may not represent the most suitable solution in these scenario due to the non-negligible latency between data sources and distant cloud data centers, which may represent an issue in cases involving real-time and latency-sensitive IoT applications. Placing certain tasks, such as preprocessing or data aggregation, in a layer of fog nodes close to sensors or end users may help to decrease the response time of IoT applications as well as the traffic towards the cloud data centers. However, the fog scenario is characterized by a much more complex and heterogeneous infrastructure compared to a cloud data center, where the computing nodes and the inter-node connecting are more homogeneous. As a consequence, the the problem of efficiently placing microservices over distributed fog nodes requires novel and efficient solutions. In this paper, we address this issue by proposing and comparing different heuristics for placing the application microservices over the nodes of a fog infrastructure. We test the performance of the proposed heuristics and their ability to minimize application response times and satisfy the Service Level Agreement across a wide set of operating conditions in order to understand which approach is performs the best depending on the IoT application scenario. fog computing; microservices chain; IoT applications; service placement; heuristics +
Footnote †: journal:  
00 000-0001-40  
network-related delays between fog nodes that are usually not negligible, exacerbating the need for accurate and efficient deployment of microservices over the system resources. Because the problem of optimally placing chained microservices of an IoT application over the distributed fog nodes is NP-hard, in this paper we focus on developing solutions based on heuristics that are able to solve the placement problem within short execution times. Specifically, we present three different heuristics for microservice placement in a distributed fog scenario and compare their performance in order to evaluate their efficiency in minimizing IoT applications response times and satisfying SLAs. In particular, we consider a greedy heuristic developed starting from a solution applied to the problem of allocating virtual machines over the physical nodes of a cloud data center [11; 12; 13] along with two further meta-heuristics. To summarize, in this paper we present:  
* A greedy heuristic based on a modified version of the Modified Best Fit Decreasing (MBFD) [11] algorithm;
* A metaheuristic based on a Genetic Algorithm (GA) [14; 15];
* A metaheuristic based on the Variable Neighborhood Search (VNS) [16] algorithm. The contributions of this paper are twofold. First, starting from the analytical framework used to model the microservice chain placement problem over distributed fog nodes defined in [5], we adapt the above heuristics, already used for optimization problems in other contexts such as virtual machine allocation over cloud physical servers [11; 14], to the problem of microservice placement over the nodes of a fog system. It is worth noting that this adaptation is not straightforward due to the complexity introduced by the presence of microservice chains and network latency; the details of the adaptation are highlighted in Section 3. Second, we carry out a thorough experimental evaluation focusing on the parameter sensitivity and stability of the proposed solutions. The heuristics performance comparison is carried out over a wide range of parameter settings, with the aim of determining whether one heuristic dominates the others in all the considered scenarios or whether the best performing alternative depends on specific conditions.