# GASP: Genetic Algorithms for Service Placement in Fog Computing Systems
## 1 Introduction  
In the last few years, we have witnessed an ever increasing popularity of sensing applications, characterized by the fact that geographically distributed sensors produce huge amounts of data that are then pushed towards the Internet core where cloud computing data centers are located to be processed. However, this traditional approach may cause excessive delays for those applications and services that require data to be processed with very low and predictable latency, such as those related to systems for smart traffic monitoring, support for autonomous driving, smart grid, or fast mobility applications (i.e., smart connected vehicle or connected rails). Another important observation is that not all the data needs to go to the cloud data centers, but in many cases data could be preprocessed, aggregated, and filtered to store in the network core only a reduced meaningful set of data, thus avoiding unnecessarily stressing the network infrastructure. The emerging paradigm of fog computing represents a solution that can improve scalability and reduce application latency by extending cloud computing towards the edge of network [1; 2]. Although in the traditional cloud architecture (Figure 1a) the data flows are sent directly from the \"sensor layer\"to the data center(s) in the \"cloud layer\"; in the fog infrastructure (Figure 1b), tasks and services may be moved close to the sources of data to be processed thanks to the presence of an intermediate layer of fog nodes, located at the network edge interposed between the cloud data center(s) and the sources of data. The innovative paradigm of fog computing is promising in addressing the still unsolved issues of cloud computing related to unreliable latency, lack of mobility support, and location-awareness. However, realizing the full potential of fog computing introduces several new challenges [3; 4]. Many existing papers focus on balancing the load distribution between fog and cloud resources: among them, we should mentions the studies in the works by the authors of [5; 6] that tackle the issue of optimizing the allocation of the processing tasks coming from the fog nodes over the cloud infrastructure. To this aim, different solutions are proposed, such as the possibility to rely on horizontal communication among fog nodes to reduce the service delay through load sharing mechanism. On the other hand, less attention was received by the lower level connecting the data sources to the fog nodes. In the literature, indeed, many studies rely on the assumption that fog nodes communicate directly with sensors or mobile users through single-hop wireless connections [5] or that a domain of sensor nodes communicate with a specific and application-defined domain of fog nodes [6]. However, the choice of the fog node that receives and processes the data flow originated by a specific sensor may significantly affect the perceived latency and the overall performance of the application. Therefore, we claim that mapping the data flows from the sensors over the available fog nodes for processing and filtering tasks represents a critical issue to guarantee a high QoS in terms of latency and/or response time. The contribution of this paper is two-fold:  
* We present an optimization model for mapping the incoming data flows (sensor workload) over the nodes of the fog layer: the proposed model considers not only the processing time on the fog nodes depending on the local load, but also the latency between sensors and fog nodes due to the communication delay of the geographically distributed infrastructure. * We propose an heuristic to provide a scalable solution to the problem of mapping sensors over fog nodes that could be applied to large-scale instances.