Farah A Ït-Salaht

Frédéric Desprez

Adrien Lebre

An overview of service placement problem in Fog and Edge Computing

Keywords: Fog Computing, Edge Computing, Services placement, Placement taxonomy

To support the large and various applications generated by the Internet of Things (IoT), Fog Computing was introduced to complement the Cloud Computing and offer Cloud-like services at the edge of the network with low latency and real-time responses. Large-scale, geographical distribution and heterogeneity of edge computational nodes make service placement in such infrastructure a challenging issue. Diversity of user expectations and IoT devices characteristics also complexify the deployment problem. This paper presents a survey of current research conducted on Service Placement Problem (SPP) in the Fog/Edge Computing. Based on a new classification scheme, a categorization of current proposals is given and identified issues and challenges are discussed.

Introduction

In recent years, the Internet of Things (IoT) becomes ingrained in our society by transforming objects of everyday life like wearable, transportation, augmented reality, etc., in communicating devices, and thus introduces new challenges and opportunities. With more than 50 billion devices connected to the network by 2020 according to Cisco [START_REF]Fog Computing and the Internet of Things: Extend the Cloud to Where the Things Are[END_REF], it is clear that the current infrastructures will not be able to support all the data that will be generated. Indeed, the current Cloud infrastructure alone can not support a large number of the current IoT applications and those essentially for three main reasons: First, the huge amount of generated data makes their transfer from where they are created (end-devices), to where they are processed (Cloud servers), impractical due to bandwidth limitations, processing overhead, and transmission costs. Second, the significant end-to-end delay from end-devices to the Cloud servers that are often too far from end-users can deter the performance of applications that require real-time analysis, such as online gaming, video applications, etc. Finally, some data may have implications in terms of privacy and security and it is advisable or even forbidden for this data to cross the entire Internet [START_REF] Yi | Security and Privacy Issues of Fog Computing: A Survey[END_REF].

To cope with these issues, a promising paradigm able to avoids network bottlenecks, overcome communication overheads and reduce the delay of data transfer has been identified [START_REF] Bonomi | Fog Computing: A Platform for Internet of Things and Analytics[END_REF]. This new conceptual approach that combines the benefits of Cloud and the decentralized processing of services on edge devices is known as Fog or Edge Computing [START_REF] Bonomi | Fog Computing: A Platform for Internet of Things and Analytics[END_REF]. The community has not yet converged against crisp definitions of these terms [START_REF] Bilal | Potentials, trends, and prospects in edge technologies: Fog, cloudlet, mobile edge, and micro data centers[END_REF][START_REF] Chiang | Fog and IoT: An Overview of Research Opportunities[END_REF][START_REF] Elmroth | Connecting Fog and Cloud Computing[END_REF][START_REF] Hu | Survey on Fog Computing: Architecture, Key Technologies, Applications and Open Issues[END_REF]. In the following, we use the term Fog Computing for simplicity.

Fog Computing [START_REF] Vahid Dastjerdi | Fog Computing: Principles, Architectures, and Applications[END_REF] extends Cloud Computing and services to the edge of the network, bringing processing, analysis, and storage closer to where requests are created and used. The objective is to reduce the amount of data sent to the Cloud, reduce latency and computation costs. As a new paradigm, Fog Computing poses old and new challenges, and one of the main open issues is service management and 1 more precisely the service placement problem. Indeed, one of the major barriers to the adoption of Fog is "how to efficiently deploy services on available Fog nodes". Unlike Cloud data centers, Fog devices are geographically distributed, resource-constrained, and highly dynamic, which makes the problem quite challenging. Therefore, the definition of an efficient, effective, and fair provisioning for the IoT applications will be important to provide and hence ensure end-to-end guaranteed services to end-users. Moreover, depending on the context and the interest, different aspects may come into focus: resource utilization [START_REF] Taneja | Resource Aware Placement of IoT Application Modules in Fog-Cloud Computing Paradigm[END_REF], Quality of Service (QoS) [START_REF] Brogi | QoS-Aware Deployment of IoT Applications Through the Fog[END_REF][START_REF] Skarlat | Towards QoS-Aware Service Placement[END_REF][START_REF] Souza | Handling Service Allocation in Combined Fog-Cloud Scenarios[END_REF], Quality of Experience (QoE) [START_REF] Mahmud | Quality of Experience (QoE)-Aware Placement of Applications in Fog Computing Environments[END_REF], etc. These last few years, several works have been carried out and attempt to address this issue. Different assumptions, characteristics, and strategies have been considered to propose an efficient service placement. In this paper, we review a wide range of works that studied this issue in Fog environments and explore the methodologies and the strategies proposed in the literature. We underline that the survey goes beyond just describing the main approaches developed in the literature. It first identifies five main scenarios, based on user expectations, problem descriptions, and deployment objectives. Second, it provides a new classification scheme where the different variants of SPP, and the various solutions coming from the research community are classified. The following aspects are considered: problem statement, placement characteristics, technical formulation, problem objectives, optimization strategies, and experimental tools.

The paper is organized as follows. Section 2 summarizes existing surveys and tutorials on Fog Computing and resource management in the related area and highlights the contributions of our paper. Section 3 gives an overview of Fog systems: definition, architecture, main characteristics and advantages. Section 4 introduces the service placement problem and summarizes the most common formulations, optimization strategies, major design objectives, and evaluation tools proposed in the literature to address this issue. The provided classification for the SPP approaches is presented in Section 5. Section 6 outlines the open challenges and highlights emerging research directions. Finally, Section 7 concludes this survey.

Existing surveys

There are several surveys that address different aspects of Fog Computing and the related challenges [START_REF] Bonomi | Fog Computing and Its Role in the Internet of Things[END_REF][START_REF] Brogi | How to Place Your Apps in the Fog -State of the Art and Open Challenges[END_REF][START_REF] Chiang | Fog and IoT: An Overview of Research Opportunities[END_REF][START_REF] Vahid Dastjerdi | Fog Computing: Principles, Architectures, and Applications[END_REF][START_REF] Hu | Survey on Fog Computing: Architecture, Key Technologies, Applications and Open Issues[END_REF][START_REF] Kumar | Fog in Comparison to Cloud: A Survey[END_REF][START_REF] Li | Edge-Oriented Computing Paradigms: A Survey on Architecture Design and System Management[END_REF][START_REF] Mahmud | Fog Computing: A Taxonomy, Survey and Future Directions[END_REF][START_REF] Mukherjee | Survey of Fog Computing: Fundamental, Network Applications, and Research Challenges[END_REF][START_REF] Perera | Fog Computing for Sustainable Smart Cities: A Survey[END_REF][START_REF] Puliafito | Fog Computing for the Internet of Mobile Things: Issues and Challenges[END_REF][START_REF] Sarkar | Assessment of the Suitability of Fog Computing in the Context of Internet of Things[END_REF][START_REF] Toczé | A Taxonomy for Management and Optimization of Multiple Resources in Edge Computing[END_REF][START_REF] Yi | A Survey of Fog Computing: Concepts, Applications and Issues[END_REF][START_REF] Yousefpour | All One Needs to Know about Fog Computing and Related Edge Computing Paradigms: A Complete Survey[END_REF]. Indeed different works have been proposed to discuss the concept and the role of Fog computing [START_REF] Bonomi | Fog Computing and Its Role in the Internet of Things[END_REF][START_REF] Chiang | Fog and IoT: An Overview of Research Opportunities[END_REF][START_REF] Dastjerdi | Fog Computing: Helping the Internet of Things Realize Its Potential[END_REF][START_REF] Perera | Fog Computing for Sustainable Smart Cities: A Survey[END_REF][START_REF] Stojmenovic | Fog Computing: A Cloud to the Ground Support for Smart Things and Machine-to-Machine Networks[END_REF][START_REF] Vaquero | Finding Your Way in the Fog: Towards a Comprehensive Definition of Fog Computing[END_REF][START_REF] Yannuzzi | Key Ingredients in an IoT Recipe: Fog Computing, Cloud computing, and More Fog Computing[END_REF][START_REF] Yi | A Survey of Fog Computing: Concepts, Applications and Issues[END_REF]. For instance, Bonomi et al. [START_REF] Bonomi | Fog Computing and Its Role in the Internet of Things[END_REF] investigate the role of Fog Computing in the IoTs domain, its characteristics, and its applications. Saharan and Vaquero et al. [START_REF] Vaquero | Finding Your Way in the Fog: Towards a Comprehensive Definition of Fog Computing[END_REF] give an overview of the concept in terms of enabling technologies and emerging trends. Chiang and Zhang [START_REF] Chiang | Fog and IoT: An Overview of Research Opportunities[END_REF] discuss, in the context of IoT, the need for a new architecture for computing, and storage. In [START_REF] Yi | A Survey of Fog Computing: Concepts, Applications and Issues[END_REF], the authors give the definition of Fog Computing and closely related concepts and present three motivating applications: augmented reality, Content delivery, and Mobile Data Analytics. Many other papers discuss the Fog Computing characteristics, application domains, and related research challenges as [START_REF] Dastjerdi | Fog Computing: Helping the Internet of Things Realize Its Potential[END_REF][START_REF] Stojmenovic | Fog Computing: A Cloud to the Ground Support for Smart Things and Machine-to-Machine Networks[END_REF][START_REF] Yannuzzi | Key Ingredients in an IoT Recipe: Fog Computing, Cloud computing, and More Fog Computing[END_REF], however they do not investigate and discuss the problem of service placement is such geo-distributed and large scale environments. Indeed, these studies do not provide insights into how IoT applications are deployed over the network (what are the applications requirements, infrastructures characteristics, domain constraints; mapping strategies; metrics to optimize, etc.).

Recent surveys attempt to fill the resource management and service placement problems, among them we quote the work of Yousefpour et al. [START_REF] Yousefpour | All One Needs to Know about Fog Computing and Related Edge Computing Paradigms: A Complete Survey[END_REF], that provides a tutorial on Fog Computing, compares the Fog to the related computing paradigms, and discusses the resource management and service deployment (orchestration and migration) in Fog environment. In [START_REF] Mahmud | Fog Computing: A Taxonomy, Survey and Future Directions[END_REF], the authors present a taxonomy of Fog Computing, its related challenges, and features, and discuss briefly the problem of service management. Nath et al. [START_REF] Shubha | A Survey of Fog Computing and Communication: Current Researches and Future Directions[END_REF] focus on the architectures and features of Fog Computing systems, applications of Fog, security and privacy of Fog, and discuss the future scopes and open research. In their survey, the authors briefly discuss challenges related to resource management, orchestration between fog nodes and the cloud, and give some comparison of different QoS aspects of Fog computing. In [START_REF] Mouradian | A Comprehensive Survey on Fog Computing: State-of-the-Art and Research Challenges[END_REF], Mouradian et al. present a detailed review on Fog architectures and algorithms and illustrate two application domains namely IoT and Content Delivery Networks (CDN). Li et al. [START_REF] Li | Edge-Oriented Computing Paradigms: A Survey on Architecture Design and System Management[END_REF][START_REF] Toczé | A Taxonomy for Management and Optimization of Multiple Resources in Edge Computing[END_REF] provide a survey on Edge Computing architecture and system management. They propose to characterize Edge Computing by considering the following aspects: architecture characteristics, management approaches, and design objectives. Brogi et al. [START_REF] Brogi | How to Place Your Apps in the Fog -State of the Art and Open Challenges[END_REF] propose also to review the existing SPP proposals. They pursue three main objectives: elaborate an overview of the current algorithms, available prototypes, and experiments; classify the works based on the application and Fog infrastructure characteristics; And, identify and discuss some open challenges.

Although these surveys explore the resource management and service placement problem in Fog/Edge Computing, we note that these works are limited in at least one of the following: 1) limited review, and discussion on SPP in Fog/Edge Computing; 2) lack of comprehensive descriptions of the problem; stateof-the-art efforts regarding problem taxonomy, resolution approaches, evaluation environments; concrete research directions; 3) do not provide an in-depth comparison, classification or some useful insights regarding the existing works (e.g., how we can evaluate/compare the different proposals).

Our paper is different in the content and research issues. Mainly dedicated to achieving an exhaustive and very clear overview of SPP in the Fog environment, our survey aims at simplifying the user's access to references and identify a flavor of challenges. It is characterized by the following contributions.

Our contributions

The main contributions of our paper can be summarized as follows:

1. Provide an exhaustive and very clear description and overview of the SPP in the Fog environment.

2. Provide a taxonomy of the problem in the area of large-scale, geo-distributed and heterogeneous systems.

3. Propose a classification of surveyed works based on the identified scenarios, provided taxonomy and optimization strategies.

Finally

, highlight the open challenges and discusses future research directions.

Overview of Fog Computing

In this section, we provide a brief overview of Fog Computing: definition, architecture, main characteristics and advantages.

Definition

Fog Computing (FC) is a highly virtualized platform, that offers computational resources, storage and control between end-users and Cloud servers. Introduced by Cisco in 2012 [START_REF] Bonomi | Fog Computing and Its Role in the Internet of Things[END_REF], FC is a new paradigm in which centralized Cloud coexists with distributed edge nodes and where the local and global analysis are performed at the edge devices or forwarded to the Cloud.

Architecture

Several architectures have been provided for FC. Mostly derived from the fundamental three-layers structure (as depicted in Fig. 1), a Fog infrastructure consists of IoT devices (End layer), one or more layers of Fog Nodes, and at least one Cloud Data Center (Cloud layer).

• End layer: Bottom-most layer and closest to the end-users. It comprises various IoT devices (e.g., cameras, mobile phones, smart cars, smoke detectors, . . . ). Widely geographically distributed, these devices enable sensing events and forwarding them to their immediate upper layer in the hierarchy for analysis and storage.

• Fog layer: Middle layer, consists of a set of devices that are able to process, and store the received requests. Denoted by Fog Nodes (FNs), these devices that include access points, routers, gateways, switches, base stations, laptops, specific Fog servers, etc., are connected to the Cloud servers and are able to send requests to data centers. Distributed between the end-users and DCs, these resources can be fixed devices (static) at some location or mobile (like smartphones, vehicles, intelligent transportation systems, Drones . . . ).

Architectural characteristics and advantages

Considered as the future of Cloud systems and the Internet of Things, the Fog Computing involves a number of characteristics and advantages where the main ones are mentioned below:

1. Location awareness and low latency. Most latency-sensitive applications such as augmented reality, gaming, or video streaming, require sub-second processing time and do not necessarily need to be sent across long routes to data centers or Cloud services to be processed. With the Fog Computing, the support of these aspects is provided through the geo-distribution of the various Fog nodes in different locations and their proximity to end-users. Sarkar and Misra [START_REF] Sarkar | Theoretical Modelling of Fog Computing: A Green Computing Paradigm to Support IoT Applications[END_REF] proved by theoretical modeling that the service latency in FC is significantly lower than that with Cloud Computing.

2. Save bandwidth. FC helps to unclog the network and speed up the processing of certain tasks by performing locally some computation tasks and sending only part of useful data or those that require significant analysis to the Cloud.

3.

Scalability. The number of connected devices grows rapidly, and the IoT data and application generated by these trillions of things [START_REF] Li | Efficient and Scalable IoT Service Delivery on Cloud[END_REF] increases also exponentially. Given this large amount of data, processing the whole IoT applications in the Cloud is neither efficient nor feasible, so Fog intervenes as a complementary paradigm able to support all these requests and help the scalability of such systems.

4. Support for mobility. Having a widely distributed fog devices that providing computational and storage capabilities over the network, the Fog Computing is more suited to support the mobility of end-users than the traditional centralized Cloud servers and thus will allow to provide service guarantees for the mobile end-users without interruptions. The service placement problem has been highly discussed in the literature and several proposals have emerged. Based on different application descriptions, network assumptions, and expected outcomes, these solutions are generally difficult to compare with each other. In this section, we propose to describe the methodology usually employed to address the SPP and give an overview of the following aspects: problem statement, placement taxonomy, optimization strategies, and evaluation tools (as depicted in Figure 2). These elements will allow us to clearly describe the problem, and define the different aspects on which we will base our comparison and classification of the surveyed works.

Service Placement in Fog Computing

Problem statement

The statement of the SPP problem goes through the description of the following three parts: the infrastructure model, the application model, and the deployment pattern with its related constraints.

Infrastructure model

The physical Fog infrastructure (see Fig. 1) consists respectively of a set of devices with no computational capabilities (sensors, and actuators), and a set of resources that possess computational power and/or storage capacity (Fog nodes, and Cloud data centers). Due to their physical structure [START_REF] Mahmud | Latency-aware Application Module Management for Fog Computing Environments[END_REF], the fog nodes are resource-constrained and heterogeneous to each other. And, any devices equipped with computational resources (in terms of CPU, memory, storage, bandwidth, . . . .) can be considered as potential FNs, such as routers, small servers, access points, laptops, or gateway, etc. The infrastructure network is generally abstracted as a connected graph where the vertices denote the set of IoT devices, Fog nodes, and Cloud servers, and the edges denote the links between the nodes. We mention hereafter the most common resources type and characteristics depicted in the literature to describe the Fog infrastructure.

• Resources type. Computing: servers, PCs, cloudlets [START_REF] Ai | Edge Computing Technologies for Internet of Things: A Primer[END_REF][START_REF] Satyanarayanan | The Case for VM-Based Cloudlets in Mobile Computing[END_REF], etc. Networking: gateways, routers, switches, base stations, etc. Storage: every node that can provide storage. Mobile: vehicles, smartphones, etc. Endpoint abstraction: sensors, actuators (e.g., GPS devices, wireless sensors, cameras, voice collector, radar, . . . ).

• Characteristics. Computing: CPU power, number of cores, RAM, battery life, etc. Networking: Type: wireless, wired; Capabilities: latency, bandwidth, error rate, etc. Storage: Disk, etc. Virtualization: VMs, containers, unikernel, etc. Hardware: GPU, NUMA, FPGA, etc.

Application(s) model

Several abstractions and model definitions are used in the literature to characterize the applications generated by the IoT devices and treated at Fog resources and Cloud servers. According to the surveyed papers, we identify the following main descriptions: a) a monolithic service, b) a set of inter-dependent components, and c) a connected graph.

a) Monolithic service The application sent by end-users or IoT devices is represented in the form of a single component (monolithic service). As an example, we can mention the case of an image processing application or data instance that needs to be proceeded or stored in a single physical node. The application can be defined in this case as a monolithic service.

b) Set of inter-dependent services This case assumes that the application is pre-partitioned into a set of components (services), each performs some specific operation (functionality) in the application.

In that case, dependencies between the application components are not considered.

c) A connected graph The application, in this case, is composed of a set of inter-dependent components represented as a connected graph. The vertices represent the processing/computational components of the application, and edges represent the inter-dependencies and communication demand between nodes [START_REF] Gupta | iFogSim: A Toolkit for Modeling and Simulation of Resource Management Techniques in Internet of Things, Edge and Fog Computing Environments[END_REF].

Different topologies of a graph can be identified and among them, we have respectively: line graph, tree application graph, and Directed Acyclic Graph (DAG). The DAG application topology is the most often used because it models a large range of realistic IoT applications like Video processing [START_REF] Reza Arkian | MIST: Fog-Based Data Analytics Scheme with Cost-Efficient Resource Provisioning for IoT Crowdsensing Applications[END_REF][START_REF] Bittencourt | Mobility-Aware Application Scheduling in Fog Computing[END_REF][START_REF] Scoca | Scheduling Latency-Sensitive Applications in Edge Computing[END_REF], gaming [START_REF] Zao | Augmented Brain Computer Interaction Based on Fog Computing and Linked Data[END_REF], or healthcare [START_REF] Gia | Fog Computing in Healthcare Internet of Things: A Case Study on ECG Feature Extraction[END_REF] applications. Figure 3.a) illustrates an example of DAG application (cognitive assistance application).

Regarding the application requirements, we can summarize some of them in the following: Computing: CPU power, number of cores, RAM, etc. Network-oriented: Bandwidth, Latency, Error-rate, Jitter (per link, end-to-end). Task-oriented: Deadline. Location-oriented: the application must run in a specific geographical location (for instance in Paris); the application can run only at some Fog node, etc.

Deployment pattern

The application placement problem defines a mapping pattern by which applications components and links are mapped onto an infrastructure graph (i.e., computing devices, and physical edges). Figure 3 shows a mapping example of an application modeled as a DAG (Fig. 3.a) to available Fog nodes (Fig.

3.b).

Typically, application placement involves finding the available resources in the network (nodes and links) that satisfy the application(s) requirements, satisfy the constraints, and optimize the objective (if any). For instance, respect the applications (services) requirements, not exceed the resource capacities, satisfy the locality constraints, minimize the energy consumed, etc. Service providers have to take into account these constraints to first, limit the research space and second, provide an optimum or near optimum placement. We propose hereafter to depict some of the constraints mostly considered in the literature.

Resource constraints (CR). An infrastructure node is limited by finite capabilities in term of CPU, RAM, storage, bandwidth, etc. Therefore, when placing application(s) (service components), we need to respect the resource requirements, i.e., ensures that the resources of the components deployed on the infrastructure nodes do not exceed their capabilities.

Network constraints (CN ). A network link can also be bounded by constraints like latency, bandwidth, etc., and these constraints need to be satisfied when deploying applications.

Application constraints: We highlight here two kind of application constraints:

-Locality requirement (CL). Locality requirement typically restricts certain services' executions to specific locations. Due to specific hardware, privacy requirements or given policy, some components can be restricted to be deployed on specific areas (zone) or devices. Locality constraints can be based on: a set of Fog nodes [START_REF] Xia | Combining Hardware Nodes and Software Components Ordering-based Heuristics for Optimizing the Placement of Distributed IoT Applications in the Fog[END_REF][START_REF] Yu | Application Provisioning in Fog Computing-enabled Internetof-Things: A Network Perspective[END_REF]; a specific geo-spatial location using GPS for instance [START_REF] Sarkar | Theoretical Modelling of Fog Computing: A Green Computing Paradigm to Support IoT Applications[END_REF], impose a co-localization of components [START_REF] Abderrahim | Efficient Resource Allocation for Multi-Tenant Monitoring of Edge Infrastructures[END_REF], etc.

-Delay sensitivity (CD). Some applications can specify a deadline for processing operation, or deploying the whole application in the network. This constraint is generally specified by defining a threshold to not exceed.

Service placement taxonomy

Addressing the SPP involves considering some specificities and criteria when designing the deployment strategies. Denoted as a service placement taxonomy, we propose in this paper to pay attention to the following four main aspects as depicted in Figure 4. As such, the first specificity considers whether the mapping coordination is done in a centralized or distributed manner. The second is based on whether the problem is tackled as an offline or online deployment. The third proposes to observe whether the dynamicity of the system is handled or not (i.e., handle the changes in the system, or not). Finally, the fourth characteristic describes whether the mobility of end-users and/or Fog devices is supported by the provided solution or not.

These eight characteristics described hereafter are used in Section 5.1 to classify the SPP proposals coming from the literature.

Control plan design: Centralized vs. Distributed

The development of a placement strategy and service management starts first by selecting the coordination strategy to adopt. Two common control plane models are presented in this paper: centralized and Distributed coordination. Relevant for multi-layered and geo-distributed systems, these approaches are relatively different and each has its own advantages and inconveniences as presented in the following. a) Centralized. A centralized control plane requires global information about application demands and infrastructure resources to take and disseminate global deployment decisions. The advantage of centralized placement algorithms is to potentially find a globally optimal solution, however, they are vulnerable regarding the scalability and the computational complexity issue.

When surveying papers, we observed that a large number of works considers a centralized control plane when addressing the SPP. Among these works, we mention the work of Hong et al. [START_REF] Hong | Supporting Internet-of-Things Analytics in a Fog Computing Platform[END_REF] that considers a central coordinator to make deployment decisions of IoT applications over Fog infrastructure.

b) Distributed

Unlike centralized solution, a distributed approach considers multiple authority and orchestrator nodes to control the services mapping. Generally distributed in the network (as illustrated in Fig. 5), the management elements compute placement decisions based on local resources and information. This control plane is more flexible and can be more efficient to handle the dynamic changes of infrastructure like a Fog Computing without resorting to network-wide computations. The distributed approach helps to address the scalability and the locality awareness issues and allows providing services that best fit with the local context, however, no guarantees are provided regarding the global optimality of the computed solutions.

Among the works that considered a distributed control plane, we quote the work of Wang et al. [START_REF] Wang | A Fog-Based Architecture and Programming Model for IoT Applications in the Smart Grid[END_REF] that considers a fog-based architecture composed of fog nodes and fog nodes coordination. The FNs sub-layer deals with the tasks that need real-time processing. The complex tasks that require more computational capabilities are transmitted to the FNs coordination sub-layer or forwarded to the Cloud.

Offline vs. Online placement

The service placement problem can be tackled in an offline or online manner. More precisely, we say that the placement is offline if it takes a deployment decision at the compile-time, where all required information are available. It needs complete information about the system activities and provides solutions that satisfy the given requirements. For online placement, the deployment decisions are made during the run-time of the system. The decisions are based on both process characteristics and the current state of the system. In most real use-cases, the SPP has to be addressed as an online problem. That is, the related algorithms have to consider the services as they arrive, rather than computing the placement in advance before their execution. We notice that an online placement can accommodate dynamic behavior (changes) of the system but it cannot make the best use of system resources (provide optimal placement decision).

As an example of offline placement algorithms provided in the literature, we mention [START_REF] Nishio | Service-Oriented Heterogeneous Resource Sharing for Optimizing Service Latency in Mobile Cloud[END_REF][START_REF] Souza | Handling Service Allocation in Combined Fog-Cloud Scenarios[END_REF] that assumes full information knowledge for the Fog network. For the online placement, we have for instance the work of Lee et al. [START_REF] Lee | An Online Secretary Framework for Fog Network Formation with Minimal Latency[END_REF] that proposes an online placement strategy that minimizes the computational latency for Fog system under uncertainty of available FNs. The provided online optimization framework proposes to sequentially observe the information on the network.

Static vs. Dynamic placement

This criterion tackles the fact that proposals handle or not the dynamicity of the system. We can identify respectively two aspects: the dynamicity of Fog infrastructure and the dynamicity of applications. The Fog network is highly dynamic where entities join and leave network due to instability of network links or failures. Resources capabilities can also vary over time. From an application point of view, the application graph structure can evolve over time in response to changes in real-life conditions. New sources or devices may appear or existing ones may disappear (adding new cameras, breakdown of certain components, user's can decide at any time to start or stop sending their data for a service, etc.). In addition, changes in the application information can also be observed (e.g., on the amount of data, component requirements, etc.).

To deal with the dynamic nature of Fog infrastructure and/or applications, it is required to define reactive strategies able to determine when adaptation is required, provide a transparent mechanism, and deliver the satisfying QoS. Thus, an approach is said to be dynamic if the provided placement strategy is able to deploy new services, replace or release services already deployed, in order to meet the QoS constraints and optimize a given objective (if any).

By surveying the literature, we identified a number of works that propose to manage the dynamic nature of Fog environment, among them we mention the work of Yousefpour et al. [START_REF] Yousefpour | QoS-aware Dynamic Fog Service Provisioning[END_REF] that proposes a dynamic provisioning of services in Fog infrastructure that satisfies the QoS requirements and the Service Level Agreements (SLA), and minimizes the resources cost. To handle the dynamicity of IoT applications, Mahmud et al. [START_REF] Mahmud | Latency-aware Application Module Management for Fog Computing Environments[END_REF] propose a policy that dynamically determines host nodes for the deployed components and handle sudden changes in frequencies of the received services.

Mobility support

Manage mobility is a major challenge in Fog Computing. Provide a solution that supports the mobility of end-users and/or fog devices and ensures that the users always receive the associated services and desired performance without interruptions is a complex issue in Fog Computing. Frequent changes in locations for end nodes (or fog nodes, e.g., smartphone, smart car) can lead to excessive delays or to packet loss. In such a situation, the system manager (coordinator) should be able to move the service transparently from the previous devices to the new ones so as to ensure its continuity.

In [START_REF] Bahreini | Efficient Placement of Multi-component Applications in Edge Computing Systems[END_REF][START_REF] Hong | Mobile Fog: A Programming Model for Large-scale Applications on the Internet of Things[END_REF][START_REF] Ottenwälder | MigCEP: Operator Migration for Mobility Driven Distributed Complex Event Processing[END_REF][START_REF] Santos | Resource Provisioning for IoT Application Services in Smart Cities[END_REF][START_REF] Saurez | Incremental Deployment and Migration of Geo-distributed Situation Awareness Applications in the Fog[END_REF][START_REF] Urgaonkar | Dynamic Service Migration and Workload Scheduling in Edge-Clouds[END_REF][START_REF] Velasquez | Service Placement for Latency Reduction in the Internet of Things[END_REF][START_REF] Wang | Elastic Urban Video Surveillance System Using Edge Computing[END_REF][START_REF] Wang | A Fog-Based Architecture and Programming Model for IoT Applications in the Smart Grid[END_REF], for instance, the authors attempt to address the problem of end-user mobility by providing dynamic placement approaches. In [START_REF] Saurez | Incremental Deployment and Migration of Geo-distributed Situation Awareness Applications in the Fog[END_REF], Saurez et al. propose to handle the mobility of end-users by providing strategy based on the following decisions: "When-to-Migrate" based on the latency parameter; and "Where-to-Migrate" based on the proximity of a FN to the mobile devices and the current processing node.

Optimization strategies

Optimizing the service placement problem in a Fog infrastructure has been tackled from several different objectives, with different formulations and diverse algorithm proposals. This section discusses the possible objectives that may pursue in such systems, the metrics considered to evaluate the provided deployment, the problem formulation used by existing proposals, the resolution strategies, and algorithms used to solve the SPP.

Optimization objective and metrics

We propose to present first a global classification of optimization strategies proposed in the literature. On one hand, we distinguish the following two categories: mono-objective and multi-objective optimization. On the other hand, we present the metrics most often considered during optimization. a) Mono vs. Multi-objective optimization Mono-objective optimization proposes to optimize only one objective function. While multi-objective proposes to optimize simultaneously a collection of objective functions [START_REF] Marler | Survey of Multi-Objective Optimization Methods for Engineering[END_REF]. A first classification of SPP solutions regarding these two optimizations is given in Table 1. Works that have studied both aspects (mono-objective and multi-objective) are marked with an asterisk (*).

Optimization objective References

Mono-objective [START_REF] Abdullah Alsaffar | An Architecture of IoT Service Delegation and Resource Allocation Based on Collaboration between Fog and Cloud Computing[END_REF][START_REF] Amarasinghe | A Data Stream Processing Optimisation Framework for Edge Computing Applications[END_REF][START_REF] Reza Arkian | MIST: Fog-Based Data Analytics Scheme with Cost-Efficient Resource Provisioning for IoT Crowdsensing Applications[END_REF][START_REF] Ascigil | On Uncoordinated Service Placement in Edge-Clouds[END_REF][START_REF] Bahreini | Efficient Placement of Multi-component Applications in Edge Computing Systems[END_REF][START_REF] Barcelo | IoT-Cloud Service Optimization in Next Generation Smart Environments[END_REF][START_REF] Benamer | Latency-Aware Placement Heuristic in Fog Computing Environment[END_REF][START_REF] Deng | Towards Power Consumption-Delay Tradeoff by Workload Allocation in Cloud-Fog Computing[END_REF][START_REF] Deng | Optimal Workload Allocation in Fog-Cloud Computing Toward Balanced Delay and Power Consumption[END_REF] • Latency Low latency for delay-sensitive applications. Achieving lower latency has attracted attention in several surveyed papers. Indeed, several works aim at minimizing services latency deployed on available resources while satisfying the set of requirements and constraints. For instance, in [START_REF] Yousefpour | On Reducing IoT Service Delay via Fog Offloading[END_REF][START_REF] Yousefpour | Fog Computing: Towards Minimizing Delay in the Internet of Things[END_REF], the authors propose to minimize the service delay of deploying IoT applications on the IoT-Fog-Cloud framework.

• Resource utilization An important issue in Fog Computing is how to optimize resource utilization while deploying the maximum number of service over appropriate fog nodes. Among the works found in the literature that investigate this goal, we can cite the work of Hong et al. [START_REF] Hong | Supporting Internet-of-Things Analytics in a Fog Computing Platform[END_REF] that provides deployment decisions while maximizing the number of satisfied IoT analytics requests. Skarlat et al. in [START_REF] Skarlat | Optimized IoT Service Placement in the Fog[END_REF] propose also to maximize the number of satisfied application requests by prioritizing the applications with the closest deadline.

• Cost Cost-related factors become very influential in Fog service management, from the service provider's point of view or from the users' point of view. We can identify two main types of costs: the networking cost for the data transmission charges and associated expenses; execution cost related to the computational expenses of Fog nodes. Other expenses can also be identified: costs related to storage, deployment, security safeguards, migration, and so on.

In [START_REF] Yousefpour | QoS-aware Dynamic Fog Service Provisioning[END_REF], the authors propose to minimize a total cost that includes the cost of processing and storage in Cloud and Fog, the cost of communication between Fog and Cloud and between Fog nodes, and the communication cost of service deployment from the Fog service controller to FNs.

• Energy consumption Energy efficiency is one of the main concerns in IoT systems and a significant performance metric that several works attempt to investigate within the Fog context. The energy consumption encompasses mostly two things. The type of service to process, and the energy consumption at the service level that includes three main aspects: when the service is sent by the end-user to the fog device; when the service is processed by the FN; and when the Fog needs the Cloud. For instance, Sarkar et al. [START_REF] Sarkar | Assessment of the Suitability of Fog Computing in the Context of Internet of Things[END_REF][START_REF] Sarkar | Theoretical Modelling of Fog Computing: A Green Computing Paradigm to Support IoT Applications[END_REF], and Nishio et al. [START_REF] Nishio | Service-Oriented Heterogeneous Resource Sharing for Optimizing Service Latency in Mobile Cloud[END_REF] investigate the energy consumption issue in the Fog environment by considering energy consumption in both the network and the device side.

• Other metrics Other metrics can be considered when addressing the service placement problem. Some of these metrics are quality of experience, congestion ratio, blocking probability, failed requests, etc. Accepted as the user-centric measurement, QoE encapsulates the user's requirements, perceptions, and intentions when deploying services [START_REF] Laghari | QoE Aware Service Delivery in Distributed Environment[END_REF]. As an example study, we mention the work done by Mahmud et al. [START_REF] Mahmud | Quality of Experience (QoE)-Aware Placement of Applications in Fog Computing Environments[END_REF] that provides a QoE-aware application placement strategy by which the deployment prioritizes the user expectations. Regarding the congestion ratio, Yu et al. [START_REF] Yu | Application Provisioning in Fog Computing-enabled Internetof-Things: A Network Perspective[END_REF] propose to consider the minimum ratio between the flow and the capacity of link to address the service placement and data routing of real-time processing applications in IoT.

Technical formulation

The SPP is generally formalized using one of these two main categories: Integer programming or Constrained optimization. Table 3 groups the surveyed works according to the identified problem formulation briefly described below. that some decision variables are not discrete. In [START_REF] Ascigil | On Uncoordinated Service Placement in Edge-Clouds[END_REF], to study the latency-critical services management in an Edge-Cloud, the authors formulate the problem as a MILP that minimizes the number of failed requests. Mixed Integer NonLinear Programming (MINLP) considers continuous and discrete variables and nonlinear objective function and/or constraints. Due to the high computational complexity for solving this class of problems, most of the work proposes to linearize it into a MILP. As an example, to investigate the cost-efficient service deployment problem in the Fog architecture, Arkian et al. [START_REF] Reza Arkian | MIST: Fog-Based Data Analytics Scheme with Cost-Efficient Resource Provisioning for IoT Crowdsensing Applications[END_REF] first formulate the cost minimization problem as an MINLP, and then linearize it into MILP to solve it more easily.

• Mixed Integer Quadratic Programming (MIQP) This problem refers to optimization problems with quadratic objective function in the integer and in the continuous variables, and linear constraints in the variables of both types. As an example, in [START_REF] Yu | Application Provisioning in Fog Computing-enabled Internetof-Things: A Network Perspective[END_REF], the authors formulate the problem of real-time processing applications provisioning in IoT as a MIQP. To overcome the high complexity of solving such a problem, the authors propose to relax some of the constraints and present an approximation scheme.

b) Constrained optimization Constrained optimization is a set of methods designed to find out the best possible values of certain variables (i.e., optimizing process) in the presence of some restrictions (constraints). It uses a set of constraints that can easily be extended further to involve more aspects. For instance, in [START_REF] Aït-Salaht | Service Placement in Fog Computing Using Constraint Programming[END_REF], Ait-Salaht et al. propose to handle the SPP problem by provided a generic and easy-to-upgrade constraint programming model. Brogi et al. [START_REF] Brogi | QoS-Aware Deployment of IoT Applications Through the Fog[END_REF][START_REF] Brogi | How to Best Deploy Your Fog Applications, Probably[END_REF] propose a constrained model to determine the feasible deployments (if any) of an application in the Fog infrastructure.

c) Other technical formulations

As other formulations found in the literature we quote: Matching Game [START_REF] Gu | Matching Theory for Future Wireless Networks: Fundamentals and Applications[END_REF], Markov Decision Process (MDP) [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF], stochastic optimization [START_REF] Neely | Stochastic Network Optimization with Application to Communication and Queueing Systems[END_REF], petri nets [START_REF] Abdulla | Priced Timed Petri Nets[END_REF], potential games [START_REF] Monderer | Potential Games[END_REF], quadratic assignment problem [START_REF] Burkard | The Quadratic Assignment Problem[END_REF], general convex optimization [START_REF] Boyd | Convex Optimization[END_REF].

For instance, in [START_REF] Saad Elbamby | Proactive Edge Computing in Latency-Constrained Fog Networks[END_REF], a matching game is employed to formulate the task placement problem in Mobile Edge Computing systems while minimizing the computation latency. In [START_REF] Urgaonkar | Dynamic Service Migration and Workload Scheduling in Edge-Clouds[END_REF], Urgaonkar et al. model the migration problem as an MDP (also known as reinforcement learning). In [START_REF] Ni | Resource Allocation Strategy in Fog Computing Based on Priced Timed Petri Nets[END_REF], the authors use priced timed Petri nets (PTPNs) to study the service placement in Fog Computing while optimizing price and time costs for completing a task.

Resolution strategies

Compute optimal application scheduling in Fog infrastructure is an NP-hard problem [START_REF] Bokhari | On the Mapping Problem[END_REF][START_REF] Eidenbenz | Task Allocation for Distributed Stream Processing[END_REF][START_REF] Kwok | Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors[END_REF]. Indeed, several issues complicate the compute of effective services placement in such a context. First, the heterogeneous nature and the limited capacities of most Fog nodes (resource-constrained). Second, the dynamicity of the environment, resources may appear and disappear, others are moving, infrastructure and application information may change over time (e.g., the variation of the workload). Third, the geographical distribution of fog devices over a large-scale infrastructure. Several specificities and constraints that make the SPP problem in Fog environment a challenging task. In the literature, we identify four main approaches used to solve such a problem: exact resolution, approximation strategies, heuristic or meta-heuristic policies. We briefly describe these procedures in the following.

a) Exact solution

The definition of an exact solution is often computed by using an ILP solver, or by performing exhaustive research (by enumerating all solutions). Among the works that attempted to solve the SPP in an exact way, we mention the works [START_REF] Sq | Toward Service Placement on Fog Computing Landscape[END_REF][START_REF] Santos | Resource Provisioning for IoT Application Services in Smart Cities[END_REF][START_REF] Skarlat | Optimized IoT Service Placement in the Fog[END_REF][START_REF] Tinini | Optimal Placement of Virtualized BBU Processing in Hybrid Cloud-Fog RAN over TWDM-PON[END_REF][START_REF] Velasquez | Service Placement for Latency Reduction in the Internet of Things[END_REF], that use ILP formulation and exact optimization solver to define an optimal solution, and [START_REF] Zhao | Optimal Placement of Virtual Machines in Mobile Edge Computing[END_REF] that uses exhaustive placement research.

However, it is important to notice that performing an exact resolution requires long processing time before reaching the optimal solutions and can only be used for small problem instances. Indeed, finding an exact solution can be extremely time-consuming and not appropriate for large problems such as Fog environments. Thus, the main focus of works within the research community is based on providing an effective approximation, heuristic or meta-heuristic approaches where suboptimal solutions can be computed in a short time.

b) Approximations Approximation techniques are used to compute solutions with provable guarantees regarding their distance to the optimal one. Approximations are efficient algorithms that allow to compute suboptimal solutions of NP-hard optimization problems. For example, in [START_REF] Yu | Application Provisioning in Fog Computing-enabled Internetof-Things: A Network Perspective[END_REF], the authors propose to use a fully polynomial-time approximation algorithm to address the problem of IoT application provisioning. This approach allows computing a suboptimal solution and bounds for SPP in a relatively small time.

c) Heuristics Because of the scale, the dynamic and mobile aspects of Fog infrastructures, that make exact analysis almost inapplicable, heuristics are often investigated. Designed to obtain a solution in a reasonable time frame, a heuristic is a set of rules and methods that aim at finding a feasible solution for a given problem. However, with heuristic-based solutions, no performance guarantees are provided. As heuristic approaches we can find for instance fail-first/fail-last heuristics used by Brogi et al. in [START_REF] Brogi | QoS-Aware Deployment of IoT Applications Through the Fog[END_REF][START_REF] Brogi | How to Best Deploy Your Fog Applications, Probably[END_REF]. The authors in this work propose to adopt these two strategies to determine in a relatively short time, a feasible deployment for an application in the FC. The fail-first heuristic is used in that case to selects the undeployed component that has fewer compatible nodes. The fail-last policy sorts the candidate nodes by decreasing the number of end-devices required by a software component, and their hardware capabilities. To guarantee that all requests are satisfied, these heuristics compute the best resource in terms of spatial proximity and the most powerful devices that can support them. d) Meta-heuristics Typically inspired by nature, the meta-heuristic solutions aim at providing the best solution by iteratively improving the quality of the result and helping the search process to escape from local optima within a reasonable time (unlike heuristics that can be stuck in a local optimum). Several meta-heuristic algorithms are provided in the literature, like Genetic Algorithms [START_REF] Holland | Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence[END_REF], Ant Colony Optimization [START_REF] Dorigo | Optimization, Learning and Natural Algorithms[END_REF], Particle Swarm Optimization [START_REF] Kennedy | Particle Swarm Optimization[END_REF], or Tabu Search [START_REF] Glover | Future Paths for Integer Programming and Links to Artificial Intelligence[END_REF]. These algorithms are based on population evolution where, at each evolution, the best-founded population (solution) is kept into the next evolution, in order to define at the end the best solution regarding a given objective (metric).

As an example, we mention the work of Skarlat et al. [START_REF] Skarlat | Optimized IoT Service Placement in the Fog[END_REF] that uses a Genetic Algorithm (GA) to solve the SPP in FC. A GA [START_REF] Whitley | A Genetic Algorithm Tutorial[END_REF] is an evolutionary algorithm that mimics the process of a natural evolution of chromosome. In their work, the authors assume that each gene in a chromosome denotes a service placement decision. The placement is iteratively improved according to a fitness function based on the principle of encouragement.

Evaluation environments

To evaluate the performance of their proposals, the research community uses different programming tools to perform extensive experiments and test their solutions in relevant environments and preferably in realistic setups. We depict thereafter, the most common tools used in the surveyed papers. Table 4 summarizes the programming environment adopted in the literature. Table 4: A Summary of evaluation environments.

Analytical tool

Analytical tool is one of the common approaches used to compute and evaluate the performance of the formulated strategies. The most frequently mentioned tools are: Java [START_REF] Brogi | QoS-Aware Deployment of IoT Applications Through the Fog[END_REF][START_REF] Yousefpour | QoS-aware Dynamic Fog Service Provisioning[END_REF], C++ [START_REF] Saurez | Incremental Deployment and Migration of Geo-distributed Situation Awareness Applications in the Fog[END_REF][START_REF] Yu | Application Provisioning in Fog Computing-enabled Internetof-Things: A Network Perspective[END_REF], Matlab [START_REF] Jijin | Service Load Balancing in Fog-Based 5G Radio Access Networks[END_REF]. For instance, Brogi et al. [START_REF] Brogi | QoS-Aware Deployment of IoT Applications Through the Fog[END_REF] prototype a proof-of-concept Java tool named FogTorch1 that implements and solve the SPP. These tools are sometimes associated with other tools or APIs such as ILP solvers. As solvers frequently mentioned in the literature we have IBM CPLEX2 ([133], [START_REF] Naas | iFogStor: An IoT Data Placement Strategy for Fog Infrastructure[END_REF]), the commercial solver Gorubi3 ([62]), or Choco-Solver4 ([9]).

Simulator

Another commonly used approach is performing simulation. Among the simulators cited in the literature, we find a simulator CloudSim [START_REF] Calheiros | CloudSim: A Toolkit for Modeling and Simulation of Cloud Computing Environments and Evaluation of Resource Provisioning Algorithms[END_REF] designed for regular cloud environments, most often used with some extensions. A SimGrid5 framework designed for large-scale distributed systems. A simulator iFogSim [START_REF] Gupta | iFogSim: A Toolkit for Modeling and Simulation of Resource Management Techniques in Internet of Things, Edge and Fog Computing Environments[END_REF] designed for Fog Computing, which extends CloudSim. iFogSim is a simulation toolkit proposed by Gupta et al. [START_REF] Gupta | iFogSim: A Toolkit for Modeling and Simulation of Resource Management Techniques in Internet of Things, Edge and Fog Computing Environments[END_REF] for evaluating application design and resource management techniques in Fog systems. The simulator performs discrete event simulation and allows users to run applications over Fog infrastructure and measure metrics like latency, energy consumption, and network usage. Other simulators are also cited like network generic simulator OMNeT++6 (used of instance in [START_REF] Amarasinghe | A Data Stream Processing Optimisation Framework for Edge Computing Applications[END_REF]); FogTorchΠ provided by [START_REF] Brogi | How to Best Deploy Your Fog Applications, Probably[END_REF] that employs the Monte Carlo method [START_REF] Dunn | Exploring Monte Carlo Methods[END_REF] to estimate the QoS-assurance of output deployments; Event-driven simulator based on SimPy 7 performed by Borylo et al. [START_REF] Borylo | Energy-Aware Fog and Cloud Interplay Supported by Wide Area Software Defined Networking[END_REF], etc.

Experimental testbeds

Finally, we have physical testbeds. As realistic environments, we can cite FIT/IoT-LAB [START_REF] Adjih | FIT IoT-LAB: A large scale open experimental IoT testbed[END_REF] and Grid5000 [START_REF] Balouek | Adding Virtualization Capabilities to the Grid'5000 Testbed[END_REF] large-scale experimentation environments. Designed for testing the Future Internet of Things, FIT IoT-LAB testbed is a France large scale open-platform that provides access to a variety of fixed and mobile technologies and services (with more than 2700 heterogeneous sensors spread in six different sites). More focused on parallel and distributed computing, Grid'5000 is a scientific instrument for experimental research on large future infrastructures: Clouds, datacenters, HPC Exascale, Big Data infrastructures, networks, etc. It contains a large variety of powerful resources, network connectivity, and storage access, grouped in homogeneous clusters spread in 10 sites in France. We have Software stacks "OpenStack" [START_REF] Shrivastwa | OpenStack: Building a Cloud Environment[END_REF] which is a set of open source software tools for deploying Cloud Computing infrastructures (Resource reservation, disk image deployment, monitoring tools, data collection and storage). We can identify also Cumulus [START_REF] Gedawy | Cumulus: A distributed and flexible computing testbed for edge cloud computational offloading[END_REF] platform for computational offloading at the Edge, or platforms like FED4Fire [START_REF]Fed4fire project[END_REF]: largest federation of Next Generation Internet testbeds in Europe, PlanetLab [START_REF]PlanetLab[END_REF]: a testbed for computer networking and distributed systems research, etc.

Summary

This section describes the SPP and summarizes the most common formulations, resolution strategies, and evaluation tools used in the literature to address this issue. Next, we propose to categorize the surveyed works based on a new classification scheme that allows to simplifying access to references in the category of interest and identifying more easily the challenges and emerging research directions.

A classification of service placement approaches

In this section, we use the taxonomy developed in Section 4.2 to provide a new classification scheme and categorize the works provided on the SPP by the research community. First, we propose to categorize the problem on two main scenarios according to the problem description. Then, we provide the classification we perform. The idea is to group the works addressing the same issues to better understand the needs of each problem, and facilitate the user's access to references.

Identified scenarios

When surveying the literature, we found that depending on the problem's features, we can identify two main scenarios. Scenario 1 that aims at deploying services in Fog while satisfying the QoS requirements and Scenario 2, slightly different from the first one, that in order to ensure minimum latency and satisfactory quality of service must disseminate and deploy services (replicate some services and place them) over Fog infrastructure. The description of these scenarios is given hereafter. In this scenario, we remark that according to how we characterize the services, we can identify the following sub-scenarios: assignment of set of monolithic applications, assignment of continuous request sent from IoT node to the Fog/Cloud layer, assignment of set of applications each composed by a set of inter-dependant components, assignment of set of applications each having a DAG topology.

• Scenario 1.1: Deploy a set of monolithic applications. This scenario addresses the problem of defining the best storage/process location for set of services that are assumed to be monolithic.

• Scenario 1.2: Deploy applications that receives continuous request from a data source. This scenario deals with the assignment of service flows between service producer (i.e., sensors) and service consumers (i.e., Fog resources). Application placement here involves both determining the host devices and routing path that satisfies requirements and optimize objective (if any).

• Scenario 1.3: Deploy applications each abstracted as a set of interdependent services. This scenario assumes that each application is composed of a set of independent components, i.e., without networking dependencies (requirements in terms of latency, bandwidth, etc., between services are not considered).

• Scenario 1.4: Deploy applications each abstracted as a Directed Acyclic Graph (DAG). The application here is defined through a DAG topology, where each node represents an operational service of the application and the links describe the networking requirements between components (refer to Section 4.1.2.b for more details).

ii) Scenario 2: Ensure minimum latency and a satisfactory QoS when deploying services Fog Computing allows bringing computational power to the edge of the network, reduce latency and overheads. However, when applications need access to data that are centrally stored (which is the case of many services like video streaming, video on demand, gaming, etc.), the benefits of the Fog can be quickly affected (deterioration of latency, presence of bottlenecks). To avoid these situations, one solution consists to disseminate data in a Fog environment. Offloading data to the Edge involves the use of data replication and place the replicas on critical network nodes to provide a more cost-effective solution.

This scenario tackles the service placement problem in a slightly different context compared to scenario 1. Indeed, where to place the service replicas involves satisfying additional and specific requirements and constraints such as: do not place an identical service in the same place or region, which service replica to select, and so on. Moreover, addressing the SPP here is connect to others issues such as: "Which application components to replicate?", "How many replicas for each service should we create?", "When to create and destroy a copy?", etc. So many factors that make this problem and scenario a very challenging task.

A classification of SPP according to service placement taxonomy

Based on the identified scenarios and service placement taxonomy presented in Section 4.2, we propose to categorize some approaches elaborated in the literature. The provided classification are depicted in Table 6. A more detailed classification is depicted in Tables 7, 8, 9, 10, and 11. In these tables, we propose to outline the placement requirements considered (based on those mentioned in Section 4.1.3), and describe the individual contributions of each work. [START_REF]Fed4fire project[END_REF]. The following syntax is introduced to associate each work to the related taxonomy:

Scenario

[C|Di] / [Off|On] / [S|Dy] / [nM|M]
The first parameter denotes whether the considered control plan is Centralized or Distributed. The second parameter denotes whether the scheduling is performed in Off line or Online manner. The third one denotes whether the placement is Static (i.e., considers unchanging infrastructure and applications topologies and information), or Dynamic (i.e., handles the dynamicity of the system). Finally, the fourth parameter denotes whether the provided strategy supports the mobility (M) of end-users and/or Fog devices or not (nM). So, an approach denoted as C/On/Dy/nM will be a centralized, online, dynamic, and do not support mobility. This description allows categorizing quickly any given proposals and proper compare with similar approaches. We note that each of these categories is mutually independent. Proposes a latency-aware application management policy to achieve improvements in network conditions and service QoS. [START_REF] Scoca | Scheduling Latency-Sensitive Applications in Edge Computing[END_REF] C R , C N Designs a score-based scheduling framework for latency-sensitive applications that maximize the end-users service quality experienced.

[139]

C R , C N Introduces an online optimization scheme for the task distribution under uncertainties in Fog network.

C/On/Dy/nM [35] C R , C N , C D
Provides an online placement approach that attempts to fairly satisfy all web applications.

C/On/Dy/M [115] C R , C N , C L
Designs a dynamic and mobility-aware service placement framework to provide a desirable performance-cost trade-off in Mobile Edge Computing. [135] C R , C N Presents a conceptual framework for Fog resource provisioning.

[132] C R , C D Proposes a security and deadline aware tasks scheduling algorithm.

Table 7: Taxonomy dedicated to Scenarios 1.1.

Category Reference RequirementsContributions

C/On/S/nM

[14] C R , C N , C D
Proposes a cost efficient resource provisioning strategy in Fog environment. [START_REF] Borylo | Energy-Aware Fog and Cloud Interplay Supported by Wide Area Software Defined Networking[END_REF] C R , C N , C D Provides latency-Aware deployment policy combined with anycast strategies for Fog and Cloud service provisioning. [START_REF] Deng | Towards Power Consumption-Delay Tradeoff by Workload Allocation in Cloud-Fog Computing[END_REF] C R , C N C D Minimizes power costs when distributing workload in Cloud/Fog systems. [START_REF] Deng | Optimal Workload Allocation in Fog-Cloud Computing Toward Balanced Delay and Power Consumption[END_REF] C R , C N C D Defines a workload allocation policy for the Fog-Cloud Computing services and investigates the tradeoff between power consumption and delay. [START_REF] Do | Approximal Algorithm for Joint Resource Allocation and Minimizing Carbon Footprint in Geo-Distributed Fog Computing[END_REF] C R Investigates the problem of service deployment while minimizing carbon footprint for video streaming service in Fog architecture.

[50] C R , C N , C L , C D Provides a proactive tasks placement in Fog networks under latency and reliability constraints. [START_REF] Gargees | Incident-Supporting Visual Cloud Computing Utilizing Software-Defined Networking[END_REF] C R , C N , C D Provides data placement policy in context of incidental disasters. [START_REF] Gu | Cost Efficient Resource Management in Fog Computing Supported Medical Cyber-Physical System[END_REF] C R ,

C N , C D
Proposes a heuristic algorithm to address the task distribution, and virtual machine placement problem toward cost-efficient Fog computation and medical cyber-physical systems. [START_REF] Intharawijitr | Analysis of Fog Model Considering Computing and Communication Latency in 5G Cellular Networks[END_REF] C R , C D Provides a mathematical service placement model in Fog architecture.

[88] C R Elaborates a data placement policy in Fog architectures that aims to reduce network usage.

[101] C R , C N , C D Proposes a balanced energy-delay solution for IoT applications placement and energy consumption problem in Fog Computing. [START_REF] Naas | A Graph Partitioning-based Heuristic for Runtime IoT Data Placement Strategies in a Fog Infrastructure[END_REF][START_REF] Naas | iFogStor: An IoT Data Placement Strategy for Fog Infrastructure[END_REF] C R , C N Provides a framework called iFogStor for IoT data placement in a Fog infrastructure.

[129] C R Provides a placement mechanism that models the competition between IoT users and the efficient service deployment over a hierarchical Fog-Cloud computing system.

[164] C R , C N , C D
Proposes provisioning schemes for real-time processing applications in Fog Computing.

C/On/Dy/nM [16] C R , C N , C D
Proposes a set of strategies for service placement in Edge-Cloud environment. [START_REF] Yousefpour | QoS-aware Dynamic Fog Service Provisioning[END_REF] C R , C D Introduces a dynamic Fog service provisioning policy that meets QoS constraints.

C/On/Dy/M [145]

C R , C N Designs an online control algorithm that provides where and when services should be migrated according to demand variation and user mobility in Edge-Clouds networks.

[149] C R , C L Proposes a strategy that dynamically route data to proper fog nodes in the context of real-time surveillance applications.

Di/On/S/nM

[7] C R , C N , C L
Proposes an algorithm to distribute workload in Fog Computing environment that minimize the response time and costs. [START_REF] Abdullah Alsaffar | An Architecture of IoT Service Delegation and Resource Allocation Based on Collaboration between Fog and Cloud Computing[END_REF] C R , C N , C D Elaborate an approach for service mapping and service delegation between Fog and Cloud Computing. [START_REF] Jana | Enhancement of QoS for Fog Computing Model Aspect of Robust Resource Management[END_REF] C R , C D Proposes a QoS-aware service deployment technique in Fog Computing to reduce latency and network congestion.

[86] C R , C N Proposes an online optimization framework to perform efficient task distribution over hybrid Fog-Cloud architecture.

[87] C R , C N Provides an online dispatching and scheduling mechanism of tasks to distributed Edge-Clouds system.

[143] C R Develops workload placement algorithms to efficiently execute mobile programs in the Edge-Cloud network.

[162] C R , C D Proposes a delay-minimizing policy for IoT applications placement over IoT-Fog-Cloud network.

[161] C R Proposes a delay-minimizing tasks offloading scheme for IoT applications in Fog Computing.

Di/On/Dy/M [150] C R , C N , C D
Proposes a new model to coordinate service deployment and migration that includes latency, location awareness, and mobility support in the smart grid. C R , C N Designs an algorithm for traffic-aware VM placement and determine the maximum number of accepted VMs in the cloudlet mesh.

[112] C R Proposes a dynamic service mapping strategy that optimize resource utilization and satisfy the users' QoS requirements in Fog Computing.

C/On/Dy/M [122] C R , C N , C D
Evaluates resource provisioning in Smart City scenarios by providing an IoT application service placement mechanism. [START_REF] Saurez | Incremental Deployment and Migration of Geo-distributed Situation Awareness Applications in the Fog[END_REF] C R , C N , C L , C D Proposes an application deployment and migration mechanism for geodistributed systems. [START_REF] Velasquez | Service Placement for Latency Reduction in the Internet of Things[END_REF] C R Proposes a service placement architecture for the IoT that continuously adapt (migrate) services according to the network changing conditions and users status.

Di/On/S/nM

[102] C R , C N , C D
Provides a service placement policy that leveraging context-aware information (location, time, and QoS) in Fog landscapes. [START_REF] Skarlat | Optimized IoT Service Placement in the Fog[END_REF][START_REF] Skarlat | Towards QoS-Aware Service Placement[END_REF] C R , C N , C D Proposes provisioning and service placement approach to enable the exploitation of Fog-based computational resources. [START_REF] Venticinque | A Methodology for Deployment of IoT Application in Fog[END_REF] C R , C D Provides a mapping strategy of IoT applications that optimizes resource utilization and satisfies QoS services requirements.

Table 9: Taxonomy dedicated to Scenario 1.3.

Category Reference RequirementsContributions C/Off/S/nM [20] C R , C N Provides a latency-aware service placement heuristic in Cloud-Fog en- vironment. [29, 31] C R , C N , C L
Proposes a QoS-aware deployment strategy for multi-components IoT applications in Fog infrastructure. [START_REF] Maio | First Hop Mobile Offloading of DAG Computations[END_REF] C R , C N , C L Designs a tasks deployment framework for Mobile Edge Cloud Offloading that achieves a trade-off between applications' runtime, mobile device battery lifetime and cost for the user. [START_REF] Gedeon | On Scalable In-Network Operator Placement for Edge Computing[END_REF] C R , C N Provides a set of heuristics to address the service placement problem in Cloud-Fog network.

[71]

C R , C N , C L Designs, implements, and evaluates a Fog Computing platform that runs analytics on multiple devices. [START_REF] Huang | Evaluating Algorithms for Composable Service Placement in Computer Networks[END_REF] C R , C N Evaluates a set of heuristic algorithms for solving the service placement problem in the context of next-generation network architectures.

[79] C R , C N Addresses the task assignment problem for the virtual Fog access point.

[103] C R , C N Proposes a tasks deployment policy that assigns the processing tasks to nodes which provide the optimal processing time and near optimal networking costs in Edge-Fog Cloud system.

[118] C R , C N Provides a scheduling algorithm that guarantees application performance and reduces the cost of using Cloud resources.

[140] C R Proposes a service mapping solution for efficient resources utilization in the Fog infrastructure.

[

154] C R , C N , C L
Proposes a mechanism for placing distributed IoT applications in Fog infrastructure while minimizing the services response time.

C/On/S/nM [12] C R , C N , C L
Provides an optimization placement framework of data stream processing applications that minimise end-to-end latency in Edge-Cloud Computing. [START_REF] Barcelo | IoT-Cloud Service Optimization in Next Generation Smart Environments[END_REF] C R , C N , C D Designs an IoT service placement strategy for IoT-Cloud infrastructure that satisfies end user demands and minimizes overall operational cost. [START_REF] Cardellini | Optimal Operator Placement for Distributed Stream Processing Applications[END_REF] C R , C N Proposes a solution for the distributed data stream application placement in a geographically distributed environment.

[46] C R , C N Proposes an orchestration mechanisms for service provisioning in Fog network that minimizes the provisioning cost of IoT applications.

[64] C R , C N Proposes a transfer-time aware service scheduling policy for IoT-Fog-Cloud Computing environments.

[89] C R , C N , C D
Proposes a policy for service placement in Fog devices based on communities and transitive closures notions. [START_REF] Mahmoud | Towards Energy-Aware Fog-Enabled Cloud of Things for Healthcare[END_REF] C R Proposes an energy-aware algorithm for mapping application components on Fog devices.

[

151] C R , C N , C L
Addresses the multi-Component application placement problem in Edge environments and develop algorithms with provable performance bounds. [START_REF] Yi | LAVEA: Latency-aware Video Analytics on Edge Computing Platform[END_REF] C R , C N Builts the Latency-Aware Video Edge Analytics system to investigate task placement schemes.

C/On/Dy/nM [START_REF] Aryal | Dynamic Application Deployment in Federations of Clouds and Edge Resources Using a Multiobjective Optimization AI Algorithm[END_REF] C R , C L Proposes a decision-making strategy for virtual machine placement considering multiple optimization objectives.

[58] C R Proposes adaptive scheduling strategies for dynamic event analytic dataflows placement in Edge-Cloud devices that support Smart City applications emerging needs.

[97] C R , C D Refines the service provisioning algorithm to guarantee the application deadlines and optimize Edge resource exploitation.

C/On/Dy/M [17] C R , C N
Proposes an online mobile application placement algorithm that minimizes the services computational cost.

[114] C R , C N , C D Proposes a service placement and migration policy for mobile event processing applications in Cloud and Fog resources.

Di/On/S/nM [START_REF] Shurman | Collaborative Execution of Distributed Mobile and IoT Applications Running at the Edge[END_REF] C R , C N Introduces a collaborative approach of executing applications components in a distributed manner between fog devices.

Table 10: Taxonomy dedicated to Scenarios 1.4.

Category Reference RequirementsContributions

C/Off/S/nM [START_REF] Althamary | Popularity-Based Cache Placement for Fog Networks[END_REF] C R , C N Proposes an efficient cache placement strategy based on content popularity to reduce energy consumption in Fog networks.

[167] C R ,C N Proposes a placement algorithm for virtual machine replica in Mobile Edge Computing that minimizes the average data traffic in the network.

C/On/S/nM

[52] C R , C N , C L
Provides two request-routing strategies to tackle the problem of energy-efficient and latency-aware data placement in geo-distributed Cloud data centers. [START_REF] Mayer | FogStore: Toward a Distributed Data Store for Fog Computing[END_REF] C R Provides a Fog-aware replica placement algorithm based on the definition of failure groups.

[166] C R , C N Designs a task scheduling strategy that minimizes tasks completion time for promoting the user experience.

Di/On/Dy/nM

[13] C R , C N , C L
Elaborates a dynamic placement (creation/replacement/removal) of data replicas across IaaS providers. [START_REF] Selimi | Towards Network-Aware Service Placement in Community Network Micro-Clouds[END_REF] C R , C N , C L Provides a bandwidth and availability-aware policy for service deployment on Micro-Cloud infrastructures that maximizes user QoS and QoE.

Table 11: Taxonomy dedicated to Scenarios 2.

A classification of SPP according to resolution approaches

We propose now to group works based on the used resolution approach. Some solutions along with their objectives are detailed in Tables 12, 13, 14, 15, and 16. Each table refers to the aforementioned scenarios (see Section 5.1).

Category Solutions References

Objective and a brief description of the resolution technique.

C/Off/S/nM Exact [START_REF] Tinini | Optimal Placement of Virtualized BBU Processing in Hybrid Cloud-Fog RAN over TWDM-PON[END_REF] Minimizes the number of Fog nodes. Exact resolution of the ILP using CPLEX solver.

[69] Minimizes the overall communication cost. Uses linear programming solver.

C/On/S/nM Approximation [START_REF] Tan | Online Job Dispatching and Scheduling in Edge-Clouds[END_REF] Minimizes the total response time over all the deployed tasks. Uses a Dual-fitting algorithm to find a feasible solution.

Heuristic [START_REF] Kochar | Real Time Resource Allocation on a Dynamic Two Level Symbiotic Fog Architecture[END_REF] Maximizes the utilization of residual computing capabilities of terminals. Provides two heuristics: 1) Prioritize the task with the earliest deadline. 2) Choose the device with the minimum remaining computation capacity.

[127] Maximizes the QoE. Computes a quality score that combines connectivity, bandwidth, and resource scores to deploy a service on the most suitable VM.

Metaheuristic [96]

Maximizes QoE-gain of the user. Uses a Fuzzy logic based reasoning.

C/On/Dy/nM Heuristic [START_REF] Carrera | Utility-Based Placement of Dynamic Web Applications with Fairness Goals[END_REF] Equally satisfies the applications. Uses utility-driven application placement policy.

C/On/Dy/M Heuristic [START_REF] Ouyang | Follow Me at the Edge: Mobility-Aware Dynamic Service Placement for Mobile Edge Computing[END_REF] Minimizes the average service latency under cost budget constraints. Uses Lyapunov optimization to decompose the problem into a set of problems that do not require a priory knowledge of user mobility.

Machine Learning [START_REF] Chen | A Dynamic Service-Migration Mechanism in Edge Cognitive Computing[END_REF] Minimizes the service costs, meantime and improve the QoE. Uses Q-learning method [START_REF] Hwang | Big-Data Analytics for Cloud, IoT and Cognitive Computing[END_REF] to determine for each service request, the host (node) that provides the optimal migration.

Di/Off/S/nM Exact [START_REF] Souza | Handling Service Allocation in Combined Fog-Cloud Scenarios[END_REF] Minimizes the service latencies in a Fog, while satisfying the QoS requirements. Uses Gurobi optimizer [START_REF]Gurobi Optimizer Reference Manual[END_REF] to solve the ILP provided model.

Di/On/S/nM Heuristic [START_REF] Singh | RT-SANE: Real Time Security Aware Scheduling on the Network Edge[END_REF] Minimizes the cost of the user job. Sorts the jobs in increasing order of deadlines.

[135] Maximizes the utilization of Fog resources. Uses a fog colonies notion and simulation approach to perform provisioning plan of requested services.

[54] Maximizes the application deployment revenue. Operates an iterative application deployment by region. Finds the minimum congestion ratio. Uses fully polynomial-time approximation that in order to reduce the resolution complexity of IoT application provisioning proposes to decompose the initial problem into two sub-problems to be solved separately.

[129] Each user maximize its own QoE. Uses -Nash equilibrium and offloading game to model the competition between end-users and provides near-optimal service mapping.

Heuristic [START_REF] Deng | Towards Power Consumption-Delay Tradeoff by Workload Allocation in Cloud-Fog Computing[END_REF][START_REF] Deng | Optimal Workload Allocation in Fog-Cloud Computing Toward Balanced Delay and Power Consumption[END_REF] Minimizes the power consumption in the Cloud-Fog Computing.

Decomposes the initial problem into three sub-problems that can be independently solved, and uses convex optimization techniques, Generalized Benders' Decomposition, and Hungarian method to find feasible solution.

[55]

Minimizes service delay and expensive resource over provisioning. Computes the shortest path that satisfies application QoS constraints.

[77]

Minimizes the blocking probability (ratio between a number of rejected workloads and the total number of workloads). Proposes three resolution approaches: Random, Lowest latency, and Maximum available capacity policies.

[88]

Optimizes the network usage. Determines the Fog device with the closest and most evenly distance to the data sources. The placement decision considers the FN with the highest centrality value. [START_REF] Naas | A Graph Partitioning-based Heuristic for Runtime IoT Data Placement Strategies in a Fog Infrastructure[END_REF][START_REF] Naas | iFogStor: An IoT Data Placement Strategy for Fog Infrastructure[END_REF] Minimizes the overall latency of storing and retrieving data in a Fog. Provides a geographical partition to decreases the problemsolving time. [START_REF] Reza Arkian | MIST: Fog-Based Data Analytics Scheme with Cost-Efficient Resource Provisioning for IoT Crowdsensing Applications[END_REF][START_REF] Borylo | Energy-Aware Fog and Cloud Interplay Supported by Wide Area Software Defined Networking[END_REF][START_REF] Do | Approximal Algorithm for Joint Resource Allocation and Minimizing Carbon Footprint in Geo-Distributed Fog Computing[END_REF][START_REF] Saad Elbamby | Proactive Edge Computing in Latency-Constrained Fog Networks[END_REF][START_REF] Gu | Cost Efficient Resource Management in Fog Computing Supported Medical Cyber-Physical System[END_REF] Metaheuristic [START_REF] Mebrek | Efficient Green Solution for a Balanced Energy Consumption and Delay in the IoT-Fog-Cloud Computing[END_REF] Minimizes the total energy consumption of mobile applications.

Uses a modified genetic algorithm.

C/On/Dy/nM Heuristic [START_REF] Ascigil | On Uncoordinated Service Placement in Edge-Clouds[END_REF] Minimizes failed requests. Proposes two heuristics: strictest deadline first, and first in first out policies.

[163] Minimizes overall cost (processing, storage, and communication).

Proposes Two heuristics: 1) Min-Viol: aims at minimizing the deadline violations. 2) Min-Cost: aims at minimizing the total cost.

C/On/Dy/M Heuristic [START_REF] Urgaonkar | Dynamic Service Migration and Workload Scheduling in Edge-Clouds[END_REF] Minimizes the cost of execution, delays, and location constraints.

Decouples the initial Markov Decision Process (MDP) into two independent MDPs and solves the problems using a Lyapunov optimization.

[149] Minimizes the average cost over time. When emergency event happens, computes reconfiguration and reallocation only on the impacted zone.

Di/On/S/nM Heuristic [START_REF] Agarwal | An Efficient Architecture and Algorithm for Resource Provisioning in Fog Computing[END_REF] Minimizes the response time and maximize the throughput. Schedules jobs on VMs based on service level agreement.

[10] Meets SLA and QoS. Prioritizes the mapping based on a linearized decision composed by services size, completion time, and VMs capacity. Component with higher priority are mapped first and the one with lower priority are deployed last.

[143] Minimizes the cumulative delay of executing mobile services. Solves the MNIP problem as follows: first transforms the mixed nonlinear integer program to a convex optimization problem, and then solves the problem that only contains the integer variables.

[162] Reduces the service delay for IoT applications. Compares the estimated waiting time of task at a given FN with their deadline. If it is smaller, accept the task, if not, the FN offloads the service to one of its neighbors, or to the Cloud. [START_REF] Jana | Enhancement of QoS for Fog Computing Model Aspect of Robust Resource Management[END_REF][START_REF] Lee | An Online Optimization Framework for Distributed Fog Network Formation with Minimal Latency[END_REF][START_REF] Lee | An Online Secretary Framework for Fog Network Formation with Minimal Latency[END_REF][START_REF] Yousefpour | On Reducing IoT Service Delay via Fog Offloading[END_REF] Di/On/Dy/M Heuristic [START_REF] Wang | A Fog-Based Architecture and Programming Model for IoT Applications in the Smart Grid[END_REF] Reduces the application delay of IoT applications in the Smart Grid. Chooses the best nodes from the set of nodes that satisfy QoS of end-nodes and having the nearest deadline. Optimizes multiple objectives: maximize number of accepted IoT application requests, maximize service bandwidth, minimize service migrations between iterations, minimize number of active computational nodes, minimize the number of active gateways, minimize hop count between computational nodes and end devices, and minimize of path loss. Computes iteratively the solution so that in every iteration refines the previous obtained solution by improving the model with an additional optimization objective.

[126]

Optimizes tasks mapping by saving bandwidth and reducing latency.

Determines incrementally the fog nodes that match the capacity constraints and handle the application dynamism.

[147] Minimizes: the hop count between end-nodes and hosting nodes, the hop count between communication nodes, and the number of service migrations. Deploys the services in random locations, and later adapts to the network and applications constraints and requirements.

Di/On/S/nM Exact [START_REF] Sq | Toward Service Placement on Fog Computing Landscape[END_REF] Maximizes the number of deployed applications. Uses ILP solver.

[134] Maximizes the number of services deployed on Fog landscape. Uses ILP solver.

Heuristic [START_REF] Skarlat | Towards QoS-Aware Service Placement[END_REF] Maximizes the number of deployed services to Fog infrastructure.

Prioritizes the applications having the minimum value between their deadline and their deployment time.

Metaheuristic [START_REF] Skarlat | Optimized IoT Service Placement in the Fog[END_REF] Maximizes the number of deployed services to Fog devices rather than to Cloud ones. Uses a genetic Algorithm.

Table 14: Classification according to resolution approaches dedicated to Scenarios 1.3.

Category Solutions References

Objective and a brief description of the resolution techniques.

C/Off/S/nM Exact [START_REF] Aït-Salaht | Service Placement in Fog Computing Using Constraint Programming[END_REF] Provides feasible (resp. optimal) service placement solutions in Fog environment. Uses the constraint programming Choco-solver.

[20] Minimizes the overall latency and ensures the QoS requirements.

Uses ILP-solver CPLEX.

Heuristic [START_REF] Brogi | QoS-Aware Deployment of IoT Applications Through the Fog[END_REF] Determines eligible deployments of composite applications. Performs pre-processing plus backtracking to determine an eligible deployment.

[31] Determines eligible deployments of composite applications. Exploits Monte Carlo simulations [START_REF] Dunn | Exploring Monte Carlo Methods[END_REF] to handle the communication links variations, and performs pre-processing plus backtracking to determine the final eligible deployment.

[98]

Optimizes the following objectives: minimize runtime and user cost, and maximize battery lifetime. Computes the local optimum solution for each objective, and then, selects the one with the lowest score (calculated according to a given equation).

[57] Minimizes the overall cost (placement and link costs). Provides six heuristics: 1) Limits the deployment of an application component to a subset of nodes; 2) Restricts the placement of a component to one particular node; 3) Applies the co-location of some components to one node; Accelerate the previous heuristics by 4) Combines heuristics 2 and 1; 5) Combine heuristics 2 and 3; and 6) Combines heuristics 1 and 3.

[71] Maximizes the number of satisfied IoT analytics. Prioritizes the scarcest resource first and the closer to source device next.

[75]

Minimizes end-to-end delay. Elaborates a layered graph placement algorithm that proposes to find a lowest cost path that includes communication cost and processing cost.

[79] Minimizes maximum cost service node. Selects the mapping with the minimum total cost by iterating on the set of all possible mappings.

[103] Minimizes network cost. Minimizes processing cost first and then optimizes the network cost.

[140] Optimizes utilization of network resources. Prioritizes the components placement based on the resource expectation.

[154] Minimises the average response time. Proposes three heuristics based on backtracking solution and the notion of anchor.

C/On/S/nM Exact [START_REF] Barcelo | IoT-Cloud Service Optimization in Next Generation Smart Environments[END_REF] Minimizes overall operational cost. Uses the linear programming solver Xpress-MP.

[34]

Minimizes the application end-to-end latency. Uses the ILP solver.

Appro. [START_REF] Wang | Online Placement of Multi-Component Applications in Edge Computing Environments[END_REF] Minimizes the maximum weighted cost on network nodes and links.

Provides polynomial-logarithmic worst-case optimality bound. Splits the application graph into simple branches, and solve the problem recursively.

Heuristic [START_REF] Amarasinghe | A Data Stream Processing Optimisation Framework for Edge Computing Applications[END_REF] Minimizes end-to-end latency. Breakdowns the latency calculation into computational latency and network transfer latency, and minimizes the sum.

[46] Minimizes the provisioning cost. Adopts a divide and conquer approach and incrementally computes the best solution.

[65] Determines an eligible application placement. Prioritizes interdependent components based on the computation cost and communication time.

[89] Minimizes the network delays between interrelated services while optimizing the QoS and the service availability for the users. Uses a first fit decreasing approach to place applications in device communities, and then prioritizes the applications with the shortest deadlines.

[94] Minimizes energy consumption. Deploys the incoming application components to Fog resources based on the remaining CPU, energy consumption, and related deadline.

[157] Minimizes the response time. Performs sequential quadratic programming and divides the problem into two sub-problems to minimize computational complexity.

C/On/Dy/nM Heuristic [START_REF] Mahmud | Latency-aware Application Module Management for Fog Computing Environments[END_REF] Minimizes the network cost during the task assignment. Proposes to minimize first the processing cost and then optimizes the network cost.

Metaheuristic [15]

Optimizes a multi-objectives function: Minimize cost, maximize user support, minimize latency, and maximize user footprint. Converts the multi-objective optimization problem to a single objective problem by using a scalarization method. And provides Pareto optimal solution.

[58] Minimizes the total makespan while meeting energy and QoS constraints. Proposes two prior GA meta-heuristics (GA-Incremental and GA-Global) to support dynamically the multiple dataflows arriving and departing.

C/On/Dy/M Heuristic [START_REF] Bahreini | Efficient Placement of Multi-component Applications in Edge Computing Systems[END_REF] Minimizes the cost to run the application. Performs an iterative matching process and local search phase to compute the best solution.

[114] Minimizes the costs of migration and placement of a single component. Creates time-graph model and considers the shortest path from data source to identify possible migration nodes.

Di/On/S/nM Heuristic [START_REF] Shurman | Collaborative Execution of Distributed Mobile and IoT Applications Running at the Edge[END_REF] Minimizes the cost to run the application. Prioritizes the placement according to dependencies between the components and computational power of edge devices. Minimizes the average data traffic in the Edge environment. Exhaustive research is performed, i.e., enumerates all placements of service replica and selects the solution that minimizes the objective among all computed placement solutions.

Heuristic [START_REF] Zhao | Optimal Placement of Virtual Machines in Mobile Edge Computing[END_REF] Minimizes the overall latency of storing and retrieving data in a Fog. Splits the original service placement problem into set of subproblems each performing an optimal placement solution for one components.

[11] Maximizes the energy efficiency while maintaining the successful delivery. The provided algorithm proposes to categorize the services into three popularity levels and strategically cache them in Fog resources.

C/On/S/nM Heuristic [START_REF] Zeng | Joint Optimization of Task Scheduling and Image Placement in Fog Computing Supported Software-Defined Embedded System[END_REF] Minimizes the maximum average task completion time. First, partition the problem on two sub-problems and optimize each of them. Then, re-couple the two solutions in order to optimize the main objective.

[100] Achieves minimal latency in between the replicas and between the replicas and the data sources and sink. Exploits end-users and service locality in Fog network when deploying.

Di/On/Dy/nM Heuristic [START_REF] Aral | A Decentralized Replica Placement Algorithm for Edge Computing[END_REF] Defines a trade-off between cost and latency. Evaluates cost of storing replicas and expected latency improvement, to make a migration or duplication decision.

[128]

Maximizes the end-to-end performance. Provides bandwidth and availability-aware service placement policy. Based on the provided tables, we propose in the next section to discuss the open research directions and the challenges related to SPP in Fog Computing.

Emerging research directions

This section discusses the current limitations and highlights the challenges related to service placement problem in the Fog Computing. Three main directions that need attention in the near future are identified: challenges related to the problem statement, optimization strategies, and evaluation environment.

Challenges related to problem statement

Despite the recent research efforts outlined on SPP, many challenges still remain open, and one of them concerns the "problem statement" i.e., which problematic we try to address (fits which scenario), which important information needs to be considered (infrastructure information, application description, mapping requirements), and under which aspects to address it (taxonomy). Here we present some of the identified open problems.

Scenario that considers dependencies at the data level.

Based on the surveyed papers, we identified two main scenarios considered by the research community (see section 5.1), however, we noticed that for the most works that fit into the aforementioned scenarios, an important use-case was not really (and marginally) considered in SPP. It corresponds to "computation placement with data dependencies" that represents one of the problems that motivate the Fog since the goal of the Fog Computing is to keep the services close to the devices that produce and act on the data. Thus, when deploying services, the mapping must consider the dependencies at the data level, either in terms of locality (e.g., if a service is deployed in a particular zone, the related components must also be deployed in the same area for security reasons for instance) or in term of minimizing the flow of data exchanged, etc. Marginally addressed in the literature (to the best of our knowledge), the application placement with data dependencies represents real challenges that need to be more considered and studied.

Distributed service deployment

As mentioned earlier in the paper, distributing the making decisions to multiple substrate nodes instead of relying the mapping on a single central node helps to spread the load and possibly increasing scalability. With infrastructure such as Fog Computing, there is a tendency to believe that most works are based on this process. However, according to Tables 6, 7, 8, 9, 10, and 11 we observe that there is a lack of solutions proposed in the literature that address the SPP in distributed way. This is mainly due to that distributed algorithms are difficult to construct and their implementations are often non-trivial to achieve in a real environment due to the complexity of the inter-process communication and synchronization. Moreover, the lack of knowledge of the global state makes difficult to compute optimal solutions and even to reach near-optimal placement. We remark also that only a few approaches perform SPP in a distributed and dynamic way [START_REF] Aral | A Decentralized Replica Placement Algorithm for Edge Computing[END_REF][START_REF] Hong | Mobile Fog: A Programming Model for Large-scale Applications on the Internet of Things[END_REF][START_REF] Selimi | Towards Network-Aware Service Placement in Community Network Micro-Clouds[END_REF][START_REF] Wang | A Fog-Based Architecture and Programming Model for IoT Applications in the Smart Grid[END_REF]. And still less that considers distributed solutions that handle dynamicity of the system and support mobility of end-users/FNs ( [START_REF] Hong | Mobile Fog: A Programming Model for Large-scale Applications on the Internet of Things[END_REF][START_REF] Wang | A Fog-Based Architecture and Programming Model for IoT Applications in the Smart Grid[END_REF] for scenario 1.2). Thus, research in these directions is still open.

Challenges related to optimization strategies

We detail hereafter some of the challenges and opportunities worth further research in terms of optimization strategies point of view.

Optimized objective.

Depending on the studied problem and considered use-case, different metrics can be observed: Latency/bandwidth between end-user, robustness in case of failures, energy consumption/battery life cycle of the sensors, cost, application-specific metric (frame/packet loss, end-to-end delay in processing some data), etc. According to Table 1, we can easily observe that the performance metrics are usually taken as individual objectives (minimize latency, maximize the number of satisfied applications, minimize energy consumption, etc.). However, to improve QoS and QoE, these metrics should be simultaneously considered in the objective function, instead of integrating them into the model as constraints functions. Considering multiple objectives at the same time has not received significant attention so far. Due to the complexity of such problems, only a few works have attempted to address such issues [START_REF] Aryal | Dynamic Application Deployment in Federations of Clouds and Edge Resources Using a Multiobjective Optimization AI Algorithm[END_REF][START_REF] Chen | A Dynamic Service-Migration Mechanism in Edge Cognitive Computing[END_REF][START_REF] Do | Approximal Algorithm for Joint Resource Allocation and Minimizing Carbon Footprint in Geo-Distributed Fog Computing[END_REF][START_REF] Maio | First Hop Mobile Offloading of DAG Computations[END_REF][START_REF] Pham | Towards Task Scheduling in a Cloud-Fog Computing System[END_REF][START_REF] Santos | Resource Provisioning for IoT Application Services in Smart Cities[END_REF][START_REF] Zeng | Joint Optimization of Task Scheduling and Image Placement in Fog Computing Supported Software-Defined Embedded System[END_REF]. Indeed, conduct multi-objective optimization and derive effective solutions requires a huge computational effort [START_REF] Chiandussi | Comparison of Multi-Objective Optimization Methodologies for Engineering Applications[END_REF]. Multiobjective metaheuristics can be explored to solve such a problem, like MOPSO [START_REF] Hao | Multi-Objective Particle Swarm Optimization Algorithm Based on Enhanced -Dominance[END_REF] and NSGA-II [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF], or scheduling approaches like [START_REF] Fard | Multi-objective list scheduling of workflow applications in distributed computing infrastructures[END_REF].

Solution that support mobility

Due to the high mobility of some end-users and Fog devices, the elaborated solutions must ensure the continuity of the services and that the users always receive the desired requests. For this, the services must follow this mobility and perform some migrations across different Fog instances. When reviewing the literature, we observed that only a few works propose to provide a solution that supports the mobility of end-users/FNs (see Table 6). Moreover, most of the dynamic application migration approaches elaborated consider a restricted application topology (monolithic, line or tree graph), support only the mobility of end-users (not those of FNs), and developed dynamic solutions based on complex techniques and algorithms. In view of that, it is clear that the definition of standard algorithmic techniques appropriate for implementation in real Fog systems is a real need for the community. Moreover, we have observed that currently, most of the placement techniques that support mobility are reactive. Thus, addressing the problem from a proactive point of view by predicting the mobility pattern of users' and devices' could be more suitable in the Fog context. Indeed, understanding the movement behavior of end devices (or FN) may be helpful for an efficient service placement and service management in Fog Computing.

Energy-efficiency.

Regarding the energy consumption in Fog service management, we found that research is less prevalent in some aspects of energy consumption in the Fog environment. We identify the following factors: a model that considers the carbon footprint, uses renewable energy sources like wind turbines or solar panels, etc., take into account the energy-constrained of end devices (sensors) in terms of residual battery lifetime, the energy of communication links; etc. The use of Follow the Sun and Follow the Moon strategies in these cases could be helpful to manage efficiently the energy consumption, for instance by controlling the devices in terms of intelligent lighting, ventilation, and air conditioning, etc.

Generic and effective mapping

It is clearly seen in Section 4.3 that many formulation and solutions are developed to address the SPP for a specific application. These placement policies, given in the literature (mainly heuristics), consider different assumptions (infrastructure information, application topology, QoS attributes and metrics, . . . ), different objectives, that make them not easily comparable. Indeed, given the diversity of criteria, handling all these parameters is practically impossible. So, the questions arising today are: which criteria are most significant and should be considered in order to develop an effective solution? according to these criteria can we compare the existing proposals and identify the relevant approaches? or should we make a clean sweep and propose a new generic and easy to upgrade methodology?. Many open issues that deserve to be deepened.

Challenges related to evaluation environments

We propose to describe here one of the challenges that in our opinion is the most important regarding the evaluation environments' point of view.

Uniform environment

Through Table 4, we can easily observe that different tools are used by the research community to test and perform their experiments. Each tool has its own specificities and is adapted to a given problem (use-case) as described in Section 4.4. While there are a number of works that have addressed the SPP challenge, we notice that there does not yet a generic development environment that handles a large range of standardized IoT applications and allows considering various network topologies. So, there is a requirement of making a uniform platform involving most of the concepts, easy to take in hand and that favors the realization of extensive experiences. Based on the classification scheme and the scenarios provided in Section 5.1, our contribution through this paper consists to bring some basics on which we can rely to design a generic and extensible model that will take over the different Fog Computing use cases.

Conclusion

This paper focuses on the Service Placement Problem (SPP) in a Fog environment, which is currently an open issue that calls for extensive discussions and solutions. This paper gives a survey of current works. A description of the SPP was provided. Five scenarios related to this issue were identified. A categorization of solutions along four distinct dimensions (centralized vs. distributed control plan, offline vs. online scheduling, static vs. dynamic system, not support vs. support mobility of endusers/fog nodes) was elaborated. A number of algorithmic proposals to the SPP were discussed. Finally, these aspects were used to create a classification of SPP solutions elaborated in the literature based on placement taxonomy. More precisely and compared to existing surveys, our work highlights a new classification scheme which aims to simplify the user's access to references in a specific context and identify more easily the placement-related challenges.

Figure 1 :

 1 Figure 1: Generic Fog computing architecture [152].

Figure 2 :

 2 Figure 2: The structure of the section.

Figure 3 :

 3 Figure 3: Cognitive assistance application [67], shown in (a), and deployed onto Fog network, shown in (b).

Figure 4 :

 4 Figure 4: Service placement taxonomy.

Figure 5 :

 5 Figure 5: Example of a distributed control plane.

[ 36 ]

 36 C R , C N Defines a mobility-aware dynamic service-migration mechanism based on the behavioral cognition of a mobile user in Edge Cognitive Computing. Di/Off/S/nM [137] C R , C N , C D Provide a new formulation for the QoS-aware service allocation problem for Combined Fog-Cloud architectures. Di/On/S/nM [54] C R , C N Describes an efficient placement of Fog applications modules either on the Edge or in the Cloud.

Table 1 :

 1 Classification regarding the optimization objectives. b) Optimization metrics We provide hereafter a list of optimization metrics usually considered in the literature in the context of the works provided so far. The optimization can be addressed to maximize or minimize the value of the following metrics.

	Others	Quality-of-experience	[36, 55, 96, 127, 129]
		Congestion ratio	[93, 164, 167]
		Blocking probability / Failed re-	[77] / [16] / [97]
		quests / Number of computation-
		ally active FNs

,

[START_REF] Do | Approximal Algorithm for Joint Resource Allocation and Minimizing Carbon Footprint in Geo-Distributed Fog Computing[END_REF]

* ,

[46, 50, 57, 58, 62, 69, 71, 72, 75, 77, 79, 81, 86-89, 93, 94, 96, 97, 101-103, 107, 108, 115, 117, 127, 129, 132-135, 137, 139- 141, 143, 145, 147-151, 154, 157, 161-164]

,

[START_REF] Zeng | Joint Optimization of Task Scheduling and Image Placement in Fog Computing Supported Software-Defined Embedded System[END_REF]

* ,

[START_REF] Zhao | Optimal Placement of Virtual Machines in Mobile Edge Computing[END_REF]

Multi-Objectives

[START_REF] Aryal | Dynamic Application Deployment in Federations of Clouds and Edge Resources Using a Multiobjective Optimization AI Algorithm[END_REF][START_REF] Chen | A Dynamic Service-Migration Mechanism in Edge Cognitive Computing[END_REF]

, [45] * , [98, 118, 122], [166] * Metrics References Latency [7, 12, 13, 15, 20, 26, 43, 50, 55, 58, 75, 85-87, 89, 98, 107, 108, 113, 115, 118, 119, 124, 137, 139, 140, 143, 147, 150, 154, 157, 161, 162, 166]

Resource utilization

[START_REF] Abdullah Alsaffar | An Architecture of IoT Service Delegation and Resource Allocation Based on Collaboration between Fog and Cloud Computing[END_REF][START_REF] Aryal | Dynamic Application Deployment in Federations of Clouds and Edge Resources Using a Multiobjective Optimization AI Algorithm[END_REF][START_REF] Ascigil | On Uncoordinated Service Placement in Edge-Clouds[END_REF][START_REF] Hong | Supporting Internet-of-Things Analytics in a Fog Computing Platform[END_REF][START_REF] Hong | Dynamic Module Deployment in a Fog Computing Platform[END_REF][START_REF] Kochar | Real Time Resource Allocation on a Dynamic Two Level Symbiotic Fog Architecture[END_REF][START_REF] Lera | Comparing Centrality Indices for Network Usage Optimization of Data Placement Policies in Fog Devices[END_REF][START_REF] Lera | Comparing Centrality Indices for Network Usage Optimization of Data Placement Policies in Fog Devices[END_REF][START_REF] Sq | Toward Service Placement on Fog Computing Landscape[END_REF][START_REF] Perera | Fog Computing for Sustainable Smart Cities: A Survey[END_REF][START_REF] Santos | Resource Provisioning for IoT Application Services in Smart Cities[END_REF][START_REF] Skarlat | Optimized IoT Service Placement in the Fog[END_REF][START_REF] Skarlat | Towards QoS-Aware Service Placement[END_REF][START_REF] Skarlat | Resource Provisioning for IoT Services in the Fog[END_REF][START_REF] Venticinque | A Methodology for Deployment of IoT Application in Fog[END_REF]

Cost

[13-15, 17, 19, 28, 34, 36, 46, 57, 62, 69, 71, 79, 98, 103, 112, 114, 118, 132, 145, 149, 151, 156, 163, 168]

Energy consumption

[11, 15, 26, 43-45, 94, 94, 98, 101, 113, 122-124, 141]

Table 2 :

 2 Optimization metrics.

Table 3 :

 3 Classification according to technical formulation. a) Integer programming Class of problems that encompasses mathematical optimization problems in which some or all of the variables are integers. We have different variants of integer programming approaches. We list the main ones hereafter.• Integer Linear Programming (ILP) This category of problems expresses the optimization of a linear function subject to a set of linear constraints over integer variables. Several works, such as[START_REF] Cardellini | Optimal Operator Placement for Distributed Stream Processing Applications[END_REF][START_REF] Hong | Dynamic Module Deployment in a Fog Computing Platform[END_REF][START_REF] Naas | iFogStor: An IoT Data Placement Strategy for Fog Infrastructure[END_REF][START_REF] Skarlat | Optimized IoT Service Placement in the Fog[END_REF][START_REF] Skarlat | Towards QoS-Aware Service Placement[END_REF], formulate the placement problem with ILP.

	Technical	Model	References
	formula-
	tion
		Integer Linear Programming (ILP)	[19, 20, 34, 57, 71, 72, 77, 87, 88, 96, 101, 102, 107,
			108, 122, 127, 133-135, 137, 141, 147, 154, 154, 164]
	Integer programming	Integer Nonlinear Programming (INLP)	[87, 163]
		Mixed Integer Linear Programming	[14, 16, 17, 52, 110, 166] / [14, 62, 157, 166]
		(MILP) / Mixed-integer non-linear
		programming (MINLP)
		Mixed Integer Quadratic Programming	[164]
		(MIQP)
			[7, 9, 12, 12, 13, 26, 26, 29, 31, 35, 43, 44, 55, 58, 64,
	Constrained optimization	69, 75, 79, 87, 91, 98, 114, 116, 118, 124, 128, 131,
			132, 139, 140, 148, 149, 167]
	Others	Matching game	[50]
		Machine learning	[36, 145]

• Integer NonLinear Programming (INLP) An integer nonlinear program is an ILP which present nonlinear constraints. For instance, in [163], Yousefpour et al. formulate the dynamic Fog service provisioning problem as an INLP. • Mixed Integer Linear Programming (MILP) / Mixed Integer NonLinear Programming (MINLP) The class of a problem known as a Mixed Integer Programming Problem assumes

Table 5 :

 5 Classification of surveyed works according to identified scenarios. Most of the surveyed works are part of this first scenario, and try to provide answers and address the following question: "where should the service be deployed and executed to best fit with the objectives".

	Service model	Papers
		Scenario 1.1	[35, 36, 54, 69, 81, 96, 115, 127, 132, 135-137, 139, 141]
	Scenario 1	Scenario 1.2	[7, 10, 14, 16, 26, 43-45, 50, 55, 63, 77, 78, 86-88, 101, 107, 108, 129, 143, 145,
			149, 150, 161-164]
		Scenario 1.3	[72, 93, 102, 112, 122, 126, 133, 134, 147, 148]
		Scenario 1.4	[9, 12, 15, 17, 19, 20, 29, 31, 34, 46, 57, 58, 65, 71, 75, 79, 89, 94, 97, 98, 103, 114,
			131, 140, 149, 154, 157]
	Scenario 2	[11, 13, 52, 100, 128, 166, 167]
	7 https://simpy.readthedocs.io/en/latest/

Table 6 :

 6

	Reference	Service placement taxonomy
		Control plane	Online	Dynamic	Mobility
	[69, 141]	C
	[81, 96, 127, 139]	C
	[35, 136]	C
	Scenario 1.1

A classification of SPP according to service placement taxonomy. The mark means that the criterion is met; otherwise the criterion is not met or not considered.

Table 7 (

 7 resp. Table 8, Table 9, and Table 10, 11) is dedicated to approaches dealing with Scenario 1.1 (resp. Scenario 1.2, Scenario 1.3, and Scenario 1.4, and Scenario

Table 8 :

 8 Taxonomy dedicated to Scenarios 1.2.

	Category	Reference RequirementsContributions
	C/Off/S/nM	[72]	C R	Proposes an heuristic algorithm to solve service deployment problem
				in Fog computing.
	C/On/S/nM	[93]

Table 12 :

 12 Classification according to resolution approaches dedicated to Scenarios 1.1.

	Category	Solutions	References	Objective and a brief description of the resolution technique.
	C/Off/S/nM	Approximation [164]

Table 13 :

 13 Resolution approaches dedicated to Scenarios 1.2. Maximizes the number of satisfied services. Considers the applications with fewer components first (if the same, takes those who have the least feasible resources).

	Category	Solutions	References	Objective and a brief description of the resolution technique.
	C/Off/S/nM	Heuristic	[72]
	C/On/S/nM	Heuristic	[93]	Minimizes the total inter-cloudlet communication traffic in cloudlet
				mesh. Iterates on jobs and provides placement that minimize inter-
				cloudlet communication and satisfies the communication demands
				and resource constraints.
	C/On/Dy/M	Heuristic	[122]

Table 15 :

 15 Resolution approaches dedicated to Scenario 1.4.

	Category	Solutions	References	Objective and a brief description of the resolution technique.
	C/Off/S/nM	Exact	[167]

Table 16 :

 16 Classification according to resolution approaches dedicated to Scenarios 2.

https://github.com/di-unipi-socc/FogTorch

https://www-01.ibm.com/software/commerce/optimization/ cplex-optimizer/.

http://www.gurobi.com

http://www.choco-solver.org

https://github.com/simgrid/simgrid

https://omnetpp.org/