Adyson M Maia
email: adysonmaia@great.ufc.br

Yacine Ghamri-Doudane

Dario Vieira
email: dario.vieira@efrei.fr

Miguel Franklin De Castro
email: miguel@great.ufc.br

Miguel F De Castro

An improved multi-objective genetic algorithm with heuristic initialization for service placement and load distribution in edge computing

Keywords: internet of things, edge computing, 5G network, service placement, load distribution, genetic algorithm, multi-objective optimization

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Internet of Things (IoT) is a paradigm driving a digital transformation in our daily lives with the progressing development of computing and wireless technologies [START_REF] Al-Fuqaha | Internet of things: A survey on enabling technologies, protocols, and applications[END_REF]. In the IoT paradigm, smart objects, or things, are essential building blocks, which include mobile phones, vehicles, home appliances, sensors, actuators, and any other embedded devices. These devices will be interconnected in order to exchange data related to real and virtual worlds among themselves through modern communication network infrastructures. The continued growth of IoT brings more connected devices to collect and consume data across the network. Due to the resource constraints of those devices, a common approach is to use Cloud Computing (CC) to execute data analysis remotely. Some of the benefits of using CC are (i) the flexible pricing model (pay-as-you-go), (ii) the on-demand and elastic delivery of virtualized resources (e.g., computing, storage, and network resources), and (iii) the scalable computing model [START_REF] Pan | Future edge cloud and edge computing for internet of things applications[END_REF].

The backbone of CC is based on building a few large data centers in various parts of the world to serve a huge number of users. However, this means that all the data and requests need to be transmitted to a remote centralized data center, which results in long (network) latencies. For some time-sensitive IoT applications (e.g., factory automation, intelligent transport systems, emergency response, interactive mobile gaming, augmented reality, and mission-critical applications) requiring real-time responses at 10ms or even 1ms [START_REF] Schulz | Latency critical iot applications in 5g: Perspective on the design of radio interface and network architecture[END_REF], the delay caused by transferring data to the cloud is unacceptable. Moreover, some data processing can be made locally without having to be transmitted to the cloud.

Even when some decisions are made in the cloud, it may be unnecessary and inefficient to send the large volume of data to the cloud for processing and storing because not all data is useful for decision making and analysis [START_REF] Hu | Survey on fog computing: architecture, key technologies, applications and open issues[END_REF]. Another drawback of CC is the lack of fast and direct access to local contextual information (e.g., precise user location, local network conditions, and users mobility behavior) while provisioning resources to an application [START_REF] Liu | Mobile edge cloud system: Architectures, challenges, and approaches[END_REF]. Therefore, these challenges caused by the explosive growth of IoT cannot be addressed only by the Cloud Computing model.

Edge Computing (EC) aims to overcome some limitations of CC by bringing cloud services and resources (e.g., computing, storage, and networking resources) closer to end-users on geo-distributed nodes at the network edges [START_REF] Roman | A survey and analysis of security threats and challenges[END_REF][START_REF] Bilal | Potentials, trends, and prospects in edge technologies: Fog, cloudlet, mobile edge, and micro data centers[END_REF]. Some examples of such edge nodes are cellular base stations, routers, switches, and wireless access points. Thus, applications (or services 1 ) running on edge nodes in the vicinity of their users (customers or IoT devices) can filter, aggregate, or analyze data close to its source. Consequently, Edge Computing can (i) minimize latency and response time; (ii) reduce core and cloud networks traffic; (iii) reduce load on end-user devices; and minimize power consumption of those devices; (iv) make better location-and context-aware decisions; as well as (v) improve security and privacy [START_REF] Liu | Mobile edge cloud system: Architectures, challenges, and approaches[END_REF]. The characteristics of EC ensure a wide range of applications and use cases that can benefit from being deployed at the edge, such as healthcare, augmented and virtual reality, multi-player gaming, interactive multimedia, video analytics, smart environments, industrial control systems, vehicular communications, road traffic monitoring [START_REF] Bilal | Potentials, trends, and prospects in edge technologies: Fog, cloudlet, mobile edge, and micro data centers[END_REF].

Compared to a traditional cloud infrastructure, Edge Computing has distinguishing characteristics [START_REF] Hu | Survey on fog computing: architecture, key technologies, applications and open issues[END_REF][START_REF] Khan | Edge computing: A survey[END_REF]. First, Cloud Computing usually locates its resources in a few centralized data centers, but there will be a dense geodistribution of edge nodes in EC. Furthermore, the availability of the cloud services depends on the distance of multi-hop between the end-user and the cloud data centers, while edge nodes are one or few hops away from end-users.

Edge nodes are more heterogeneous than cloud servers, i.e., edge nodes come with different form factors and resources capabilities. However, edge nodes are generally more resource-limited than cloud data centers. 1 we use the notion of application and service interchangeably in this paper 3 Despite the benefits of Edge Computing, it is still a recent research topic and faces several challenges. We are particularly interested in the service placement problem in the context of EC, which is a resource management issue related to the selection of computer-based nodes (or servers) to host multiple applications according to some demands and constraints to optimize a set of performancerelated objectives [START_REF] Tärneberg | Dynamic application placement in the mobile cloud network[END_REF][START_REF] Filho | Approaches for optimizing virtual machine placement and migration in cloud environments: A survey[END_REF]. Therefore, a service placement scheme maps each application onto some hosting node.

Another challenge is provisioning adequate resources to handle the workloads generated by applications users, which relates to the amount of resources that should be allocated to each application that processes an incoming workload.

A simple solution to this problem is using resource over-provisioning to handle high peak loads. However, over-provisioning is unsuitable for EC due to high costs and limited resource capacity at edge nodes [START_REF] Skarlat | Towards qos-aware fog service placement[END_REF][START_REF] Bilal | Potentials, trends, and prospects in edge technologies: Fog, cloudlet, mobile edge, and micro data centers[END_REF]. Meanwhile, a service placement solution mappings can be many-to-many, i.e., an application can be placed onto one or more nodes, and a node can host more than one application.

In this way, service placement may consider the load balancing to distribute workloads of an application across multiple nodes. Load distribution can be applied to improve resource usage, increase availability, reduce response time, avoid bottlenecks and over-provisioning [START_REF] Xu | A survey on load balancing algorithms for virtual machines placement in cloud computing[END_REF].

Although the service placement and load distribution can be separately optimized in independent procedures, the placement decision may affect the load distribution, and vice versa [START_REF] Urgaonkar | Dynamic service migration and workload scheduling in edge-clouds[END_REF]. Hence, an optimal decision-making process may require a complex joint optimization of those two procedures.

We can find several research works in the literature concerning service placement in Cloud Computing (e.g., [START_REF] Pires | A virtual machine placement taxonomy[END_REF][START_REF] Pietri | Mapping virtual machines onto physical machines in cloud computing: A survey[END_REF][START_REF] Filho | Approaches for optimizing virtual machine placement and migration in cloud environments: A survey[END_REF]). However, these works cannot be directly applied to EC because they do not consider the distinct characteristics of EC. On the other hand, there are some research works on service placement in the context of Edge Computing, such as Tärneberg et al. [START_REF] Tärneberg | Dynamic application placement in the mobile cloud network[END_REF], Gu et al. [START_REF] Gu | Cost efficient resource management in fog computing supported medical cyber-physical system[END_REF], Skarlat et al. [START_REF] Skarlat | Towards qos-aware fog service placement[END_REF], Zhao and Liu [START_REF] Zhao | Optimal placement of virtual machines for supporting multiple applications in mobile edge networks[END_REF]. However, these existing works have shortcomings, such as not considering the limited resource capabilities of edge nodes, requirements of time-sensitive applications, or multiple conflicted opti-mization objectives. Motivated by the above facts, we jointly address the service placement and load distribution problem in Edge Computing. The formulated problem considers infrastructure constraints and different application characteristics (response deadline, resource demand, scalability, and availability) to minimize not only Service Level Agreement (SLA) violations but also other possibly conflicting objectives (e.g., operational cost and unavailability). Furthermore, we extend our previous Genetic Algorithm (GA) [START_REF] Maia | Optimized placement of scalable iot services in edge computing[END_REF][START_REF] Maia | A multiobjective service placement and load distribution in edge computing[END_REF] to improve the solutions obtained for the formulated problem. More specifically, the main contributions of this paper are as follows:

• We present a system model where multiple replicas of an application can be placed in different parts of the network to distribute requests (load) among these replicas. Moreover, we assume a static EC scenario where all information required in the service placement and load distribution decision-making process is provided in advance and does not change over time.

• We jointly formulate the service placement and load distribution as an Mixed-Integer Nonlinear Programming (MINLP) optimization problem to minimize the potential occurrence of SLA violations. Thus, a solution for this problem specifies the service placement mapping and the distribution of requests among different nodes. We also transform this MINLP into a Mixed-Integer Linear Programming (MILP) problem to be solved using a linear solver.

• The single-objective problem is extended to include multiple conflicted objectives but still prioritizing time-sensitive applications.

• We propose a meta-heuristic based on GA to solve the multi-objective problem. The proposal is an improvement of our previous works [START_REF] Maia | Optimized placement of scalable iot services in edge computing[END_REF][START_REF] Maia | A multiobjective service placement and load distribution in edge computing[END_REF] by including heuristic solutions in the initialization of the GA and the MGBM stopping criteria [START_REF] Martí | A stopping criterion for multi-objective optimization evolutionary algorithms[END_REF]. This improvement aims to speed up the algorithm and obtain better solutions.

The remainder of the paper is organized as follows. Section 2 reviews the related work. Next, Section 3 presents our system model. We formally formulate the service placement and load distribution problem in Section 4. In Section 5, we describe our proposed GA to solve the formulated optimization problem.

Then, Section 6 analyses the performance of our proposal. Finally, Section 7 concludes this paper.

Related Work

Virtual Machine (VM) placement is a well-studied topic in Cloud Computing (CC). Pires and Barán [START_REF] Pires | A virtual machine placement taxonomy[END_REF], Pietri and Sakellariou [START_REF] Pietri | Mapping virtual machines onto physical machines in cloud computing: A survey[END_REF], de Carvalho et al. [START_REF] De Carvalho | Evolutionary solutions for resources management in multiple clouds: State-of-the-art and future directions[END_REF],

and Filho et al. [START_REF] Filho | Approaches for optimizing virtual machine placement and migration in cloud environments: A survey[END_REF] published surveys on this topic over the past few years. However, service placement approaches to conventional CC cannot be directly applied to Edge Computing (EC) because they do not consider the distinct characteristics of EC (e.g., a large, distributed, and heterogeneous environment) nor the time-sensitive application requirements.

Computation offloading refers to the transfer of tasks from a device to an external platform, such as the edge and cloud computing. Hence, it enables running intensive computational applications at a device with constrained resources while reducing its energy consumption. Moreover, a crucial part of offloading is deciding whether to offload or not. In [START_REF] Mach | Mobile edge computing: A survey on architecture and computation offloading[END_REF], the authors present a survey concerning computation offloading in the context of Multi-access Edge Computing (MEC). In this paper, we are not interested in this offloading decision process, but service placement and computation offloading can be seen as complementary problems. Furthermore, we only focus on the static aspect of the service placement problem, where the mapping of applications onto hosting nodes does not change for a long time, and the decision parameters are known in advance.

We can find some approaches in the literature to solve the service placement problem in the context of Edge Computing. Skarlat et al. [START_REF] Skarlat | Towards qos-aware fog service placement[END_REF] examine the service placement in a hierarchical and distributed edge architecture to maximize the number of applications placed on edge nodes rather than the cloud.

The work also prioritizes time-sensitive applications to satisfy their response time deadline requirements. Moreover, a control node uses a Genetic Algorithm (GA) to obtain the application placement decision among its child nodes in the hierarchical network infrastructure. However, it does not address the load distribution, and the proposed GA can generate infeasible solutions, which may degrade the algorithm performance.

In [START_REF] Tärneberg | Dynamic application placement in the mobile cloud network[END_REF], the authors discuss the placement of applications in edge nodes to minimize the overall running cost. That is, the work aims to reduce the edge resource consumption due to the assumption that the running cost is proportional to resource usage. The authors present an iterative local search heuristic among neighboring solutions to find a near-optimal solution. A limitation of this work is the assumption of having sufficient resources for all applications at the network edge. Moreover, the work does not consider the requirements of time-sensitive applications.

Zhao and Liu [START_REF] Zhao | Optimal placement of virtual machines for supporting multiple applications in mobile edge networks[END_REF] address service placement and load distribution problems in MEC while targeting to minimize the average response time. The authors propose a heuristic strategy that tries to select, for each application, hosting nodes with low average response time among all requests to host the application and receive its requests. Nevertheless, the proposed solution does not take into consideration the response time deadline requirement that is particularly important for latency-sensitive applications.

In [START_REF] Gu | Cost efficient resource management in fog computing supported medical cyber-physical system[END_REF], the authors also investigate both service placement and load distribution problems in MEC. Gu et al. [START_REF] Gu | Cost efficient resource management in fog computing supported medical cyber-physical system[END_REF] formulate the optimization problem to minimize an overall cost while satisfying the maximum tolerable delay of time-sensitive medical applications. However, the authors only examine the application deployment in base stations of a mobile network, ignoring other possible locations such as the core network and cloud data centers. In addition, the work assumes that there are sufficient resources in the base stations to deploy all applications while satisfying the delay requirement.

Yang et al. [START_REF] Yang | Cost aware service placement and load dispatching in mobile cloud systems[END_REF] present a study for joint optimization of service placement and load distribution problems in a static scenario. The authors design a twostep heuristic to minimize the average latency of all application requests while satisfying the nodes capacity constraints. First, the heuristic relaxes the problem by disregarding the node capacity constraint, and it solves the problem using a linear programming solver. Then, a greedy strategy tries to obtain a feasible solution for the original problem from the optimal solution of the relaxed problem. A drawback of this work is the assumption that applications are homogeneous, as all requests consume the same amount of resources.

In [START_REF] Katsalis | Sla-driven vm scheduling in mobile edge computing[END_REF], the authors investigate VM scheduling and placement decision in MEC to (i) maximize infrastructure provider revenue, (ii) minimize SLA violations, and (iii) ensure fairness in resource allocation among service providers.

Even though the work investigates SLA violation in terms of response time, it considers the processing time responsible only for the response delay, neglecting the network delay. Furthermore, the work applies a weighted sum scalarization to transform the multi-objective problem into a single-objective one. Unfortunately, setting weights for each objective is not an easy task in a practical scenario for a decision-maker.

According to Spinnewyn et al. [START_REF] Spinnewyn | Resilient application placement for geo-distributed cloud networks[END_REF], an EC environment is more susceptible to unpredictable failures than the cloud. As a result, this characteristic significantly affects the reliability of applications deployed in an EC environment. Therefore, the authors investigate the placement of multi-component applications to optimize multi-objectives and satisfy the application minimum availability requirement. This work also applies a scalarization to transform a multi-objective optimization into a single-objective problem. More specifically, it sequentially optimizes the problem in multiple steps. In each step, an objective function is optimized, and the results of previous steps are added as equality constraints. A shortcoming of this work is that it does not consider the requirements of time-sensitive applications. Furthermore, the applied scalarization transformation also requires the decision-maker to have a global preference order among all objectives.

Table 1 presents a comparison of the discussed related work. We can observe that some works address both the service placement and load distribution problems, but not all works adequately address the Quality of Service (QoS) requirements, especially the response deadline requirement for time-sensitive applications. Regarding the optimization object, most research papers have a 210 single objective. Moreover, many multi-objective works transform the problem into a single-objective problem by some scalarization method that requires a global preference order among all optimization objectives. However, this preference order can be hard to adjust or, in many cases, does not even exist in a practical scenario. In order to overcome some limitations of the above-discussed works, we jointly investigate the static service placement and load distribution problems in a distributed, heterogeneous, and resources limited EC environment. In this paper, we present a single and multi-objective optimization formulations that consider applications, especially for IoT, with different QoS requirements. Moreover, we improve the performance of our previous solutions [START_REF] Maia | Optimized placement of scalable iot services in edge computing[END_REF][START_REF] Maia | A multiobjective service placement and load distribution in edge computing[END_REF] by including heuristics in the initialization of the proposed meta-heuristic based on GA.

System Model

In our system model, an Infrastructure Provider (InP) owns and maintains the network infrastructure comprised of hosting nodes and links connecting these nodes. A hosting node is a general-purpose machine having diverse resource capabilities (e.g., processing, memory, storage, and networking resources) and supporting execution of applications through virtualization technologies, such as VM or container. Moreover, hosting nodes can be located anywhere on the network between end-users and cloud data centers. Some nodes also act as access points for end-user devices.

Application Service Providers (ASPs) create applications used by end-users and rent on-demand resources from an InP to deploy their applications. Enduser devices are connected directly with some node over a wired or wireless link.

Over time, devices send requests, or tasks, to be processed by an application.

A device request is routed among the nodes up to a node hosting the required application. Lastly, the request is processed, and its response is sent back to the device.

ASPs do not directly determine where to place their applications. Usually, an ASP signs an SLA defining the QoS requirements to be fulfilled by the InP. In this way, a service placement scheme is an autonomous decision-making process maintained by the InP that decides where to deploy different applications over the network infrastructure according to some constraints, requirements, and performance goals defined by ASPs and InP.

In order to illustrate the system model, we describe the use case of a cellular network with Edge Computing capabilities (e.g., 5G network), as shown in Figure 1. In this case, applications can be hosted on nodes located on the Radio Access Network (RAN), Core Network, and Cloud Computing regions.

If an application is running on a Base Station (BS) in the RAN region, then a request can only be routed among neighboring Base Stations (BSs) to reduce traffic at the core and to decrease transmission delays. However, not all applications can be deployed to BSs because of the limited computing resources in this region. Hence, some applications are hosted in the core or the cloud while carrying about not violating some placement criteria defined by the providers.

Network Model

We model the network as an undirected and connected graph G = (V, E),

where the vertices V are hosting nodes and the edges E are network links between the nodes. We assume all vertices are accessible by any other vertex in the graph through multiple hops. In addition, end-user devices and their connections are not represented in G.

Each network link e = (u, v) ∈ E has the following property:

• Transmission Delay D a,e net is the average amount of time it takes for a request for an application a to be transmitted in the network link e.

Resource Type Model

The proposed system model allows specifying different types of resources, where R is the set of these considered resources. For instance, the set R = {CP U, RAM, DISK} is made up of processing (CPU), Random-Access Memory (RAM) and disk storage resources (DISK). RAM and disk storage are measured in bytes, while CPU can be measured in Instructions Per Second (IPS).

Node Model

A node, or vertex, in the graph G, represents a server with specific resource capabilities to run applications. Although multiple servers may be located on a single network node, we view these multiple servers as a single unit. Therefore, there is precisely one server for each network node, and we use the terms node and server interchangeably throughout this paper. In this way, we can include cloud data centers as a single cloud node in the graph.

Each node v ∈ V has the following features:

• Resource Capacity C r
v is a number describing the total capacity of resource r ∈ R on node v.

• Usage Cost g v (λ) is a function specifying the (monetary) cost of allocating resources for an application with a workload λ ≥ 0 on the node.

We define the workload λ v a as the (average) arrival rate of requests for application a in node v.

• Availability P v is the probability that the node v will not fail.

We assume that the cloud node has an unlimited capacity for all resources (i.e., C r cloud = ∞, ∀r ∈ R) due to the capacity difference between cloud and edge nodes.

Application Model

Let A be the set of all different applications to be placed over the network.

We consider that one or more instances, or replicas, of these applications can be deployed within the system, but these instances are independent of each other. Furthermore, a node can only host one instance of each application.

An application a ∈ A has the following parameters:

• Response Deadline D a is a number specifying the maximum time (i.e., deadline) allowed for responding a request for application a. The response time comprises the network delay plus the processing delay.

• Maximum Number of Instances N a describes how application a scales horizontally. For instance, it can be set to N a = 1, if the service does not allow replicas or N a = ∞ if the maximum number of instances is undefined.

• Resource Demand h r a (λ) denotes how an application scales vertically. In other words, it is a non-decreasing function specifying the (average) amount of resources r ∈ R required by a replica of a with a workload λ.

For instance, we can define a constant function if the vertical scaling is not supported or an increasing linear function if the amount of resources required is proportional to the workload.

• CPU Work Size W a is a value indicating the average amount of processing required to get a response to a request for a. It is measured by the number of instructions or clock cycles required to process a request.

• Availability P a denotes the probability that an application replica is working without internal failure.

User Model

End-user devices, or users, are not aware of where applications are deployed and which application instance will handle their requests. Therefore, we can distribute these requests among multiple replicas placed on the system. Let U bet the set of all users in the system, then a user u ∈ U has the following properties:

• Requested Application u a . It specifies the application a ∈ A requested by the user. For the sake of simplicity, we assume each user sends requests for only one application.

• Request Rate λ a is the average request generation rate for an end-user device of application a ∈ A. We assume that all users of a send requests to this application at the same average rate, which is determined by a Poisson distribution.

• Attached Node u v . A user is always connected to some node v ∈ V, which acts as an access point.

Then, we define U v a as the set of users connected to node v requesting application a, and U a is the set of all users requesting application a in the system. Table 2 summarizes the notations used in the system model.

Problem Statement and Formulation

In a practical scenario, it is not possible to place all applications on the edge of the network given the resource limitations of hosting nodes in this region.

Consequently, some applications are deployed further (i.e., in the core network or the cloud) from their end-users. This considerable distance between node and user may result in the response time of a request to exceed the deadline specified by some applications. Moreover, an overloaded server also increases response time, thus distributing the load among application replicas may mitigate this issue. Hence, both service placement and load distribution decisions may result in violations of the response deadline requirement, which is an important metric to be minimized for time-sensitive applications in an Edge Computings environment.

Infrastructure Provider (InP) and Application Service Providers (ASPs) often have many other performance metrics to optimize instead of just a single one.

Ua

Set of all users requesting application a in the system However, those multiple metrics are, in general, contradicting each other. For instance, an ASP wants to decrease response time while reducing the monetary cost of allocating resources to its applications. On the other hand, decreasing costs implies using cheaper cloud resources and, thus, increasing response time.

An InP may also seek to reduce the infrastructure running costs by decreasing the number of active nodes hosting applications. However, minimizing the number of servers in use may result in nodes being overloaded and, consequently, SLA violations.

Given the above context, we formulate the joint problem of service placement and load distribution to minimize deadline violation as a single objective, and multiple objectives in this section. In this paper, we are only interested in the static, or offline, approach of the problem where applications and users do not move for a long time. Moreover, all information required in the decision-making process is provided in advance. send requests to a from users in u to node v and d a,u,v proc is the average processing time of requests on v. We estimate both network and processing delays in the remainder of this subsection.

d u,v a = d a,u,v net + d a,u,v proc (1)

Network Delay

The network delay of a request includes: (i) the communication delay between the requesting end-user device and the node to which it is attached, and

(ii) the transmission delay from this latter node to a server hosting the application following a multi-hop routing path. It is important to note that a user attachment node can host the application and process its requests, and therefore the transmission delay of the second part is zero. Since we are examining the static problem case, the communication delay between a device and its attachment node does not affect the placement decision [START_REF] Zhao | Optimal placement of virtual machines for supporting multiple applications in mobile edge networks[END_REF]. Therefore, we do not consider this communication delay in the network delay estimation.

We estimate the average network delay of a request flow F u,v a as:

d a,u,v net =      0 if u = v e∈Pu→v D a,e net otherwise ( 2
)
where P u→v is the set of links in a routing path from u to v. This set can be determined by some shortest routing path algorithm, such as the Floyd-Warshall algorithm [START_REF] Floyd | Algorithm 97: Shortest path[END_REF][START_REF] Warshall | A theorem on boolean matrices[END_REF]. Therefore, we assume that d a,u,v net is a constant in the static problem.

Processing Delay

For an application replica placed on a node, we model its processing time as an M/M/1 queueing model. This queueing model helps us to estimate the average processing time in different workload conditions. Moreover, we utilize the M/M/1 queue because the aggregated traffic generated by users of an IoT application can be approximated as a Poisson process [START_REF] Metzger | Modeling of aggregated iot traffic and its application to an iot cloud[END_REF].

We determine the request arrival rate or workload λ v a for the application a running on node v as the sum of all requests arriving at this node. Equation 3expresses this request arrival rate, where δ u,v a ∈ [0, Q u a ] is an integer variable indicating the size of request flow F u,v a (i.e., number of requests in the flow).

Moreover, Q u a = |U u a |λ a is the number of requests for application a generated by users attached to node u, λ a is the request rate of a user of a, and

|U u a | is the cardinality of set U u a . λ v a = u∈V δ u,v a (3)
Service times have an exponential distribution with rate parameter µ, where 1/µ is the mean service time in an M/M/1 queue. Thus, we express 1/µ v a as the average time to perform the request CPU work W a with the resources allocated for a replica of application a in node v as:

1 µ v a = W a h CP U a (λ v a ) (4)
Finally, Equation 5gives the average processing time of requests for application a running on node v according to Little's law.

d a,u,v proc = 1 µ v a -λ v a (5)

Problem Variables and Constraints

In order to jointly formulate the service placement and load distribution problems, we define x = (ρ, γ, δ) as a triple of problem variables. We describe these variables as follows:

1. Application Placement ρ = {ρ v a | a ∈ A and v ∈ V} is a set of binary variables, where ρ v a ∈ {0, 1} indicates whether a replica of an application a is placed on a node v or not. A solution to the studied problem sets values for the above variables. Furthermore, a solution is feasible only if all the following constraints are met:

1. Number of Instances. A node can only host a single replica of a given application. Moreover, the number of instances deployed in the system must respect the limits defined by the applications (i.e., N a ), and all of them need to be placed.

1

≤ v∈V ρ v a ≤ N a ∀a ∈ A (6)
2. Request Flow Existence. A request flow F u,v a only exists if a replica of application a is placed on node v and there are users connected in u requesting a.

γ u,v a ≤ ρ v a Q u a ∀a ∈ A, ∀u, v ∈ V (7)
3. Request Flow Size. If a flow F u,v a exists, its size must be at least one and at most equal to the number of requests generated by users connected to node u.

γ u,v a ≤ δ u,v a ≤ γ u,v a Q u a ∀a ∈ A, ∀u, v ∈ V (8)
4. Load Conservation. The aggregate size of all request flows for application a from the same source node u is equal to the total number of requests for a generated by users connected to this node. In other words, all requests are distributed to some node.

v∈V δ u,v a = Q u a ∀a ∈ A, ∀u ∈ V (9)
5. Node Capacity. The total amount of resources demanded by applications placed on a server should not exceed its capacity.

a∈A ρ v a h r a (λ v a ) ≤ C r v ∀r ∈ R, ∀v ∈ V (10)
6. Queue Stability. An M/M/1 queue is stable only if the average service rate is larger than its average arrival rate. This stability needs to be guaranteed for each application placed on a node.

λ v a < µ v a ∀a, v (ρ v a = 1) , a ∈ A, v ∈ V (11)

Single Objective Formulation

Our goal is to minimize the deadline violation of the system, which we define as the highest violation among all request flows in the system. Then, we specify

f dv (x) = max x {[d u,v a -D a ] + } x = (ρ, γ, δ) (12)
Then, the static single objective optimization problem is formulated as:

min f dv (x) x = (ρ, γ, δ) subject to eqs. (6) to (11) (13)
The optimization problem ( 13) is a Mixed-Integer Nonlinear Programming

430

(MINLP) problem because constraints [START_REF] Filho | Approaches for optimizing virtual machine placement and migration in cloud environments: A survey[END_REF] and [START_REF] Skarlat | Towards qos-aware fog service placement[END_REF] and the objective function [START_REF] Xu | A survey on load balancing algorithms for virtual machines placement in cloud computing[END_REF] are nonlinear. MINLP is usually difficult to solve due to its high computational complexity [START_REF] Burer | Non-convex mixed-integer nonlinear programming: A survey[END_REF]. One way to reduce this complexity is to apply linearization and relaxation techniques. In Appendix A, we describe how to transform problem (13) into a Mixed-Integer Linear Programming (MILP) 435 problem.

Multiple Objective Formulation

Based on the single objective optimization problem [START_REF] Urgaonkar | Dynamic service migration and workload scheduling in edge-clouds[END_REF] and given F = (f 1 , f 2 , . . . , f m ) as a list of m performance-related functions, the multi-objective optimization problem for the static approach is formulated as:

min F (x) = (f 1 (x), f 2 (x), . . . , f m (x))
x = (ρ, γ, δ) subject to eqs. ( 6) to [START_REF] Skarlat | Towards qos-aware fog service placement[END_REF]

According to the InP or ASPs wishes, different objectives can be optimized.

Some non-exhaustive performance-related functions are listed below:

• Deadline Violation f dv . The violation level of the system defined in the single objective case by Equation 13 is a relevant metric to minimize for latency-sensitive applications.

• Operational Cost f cost . Deploying applications on the system is not a free operation, for there is a cost charged, possibly monetary, to ASPs for the resources used by their applications according to the pay-as-yougo pricing model. For this reason, a provider aims to reduce the cost of running a product. Given g v (•) as the allocation cost function on a node v described in Section 3, then the total operational cost for an application is simply the sum of costs on each node hosting an application replica, i.e., v∈V ρ v a g v (λ v a ). Considering all applications, a performance metric to minimize is the overall operational cost, which is defined as:

f cost (x) = a∈A v∈V ρ v a g v (λ v a ) x = (ρ, γ, δ) (15)
• Unavailability f f ail . ASPs also want high availability for their applica-

tions. An application becomes unavailable when all of its replicas become unavailable. A replica is unavailable when there is a failure in the node hosting it, or an internal failure occurs in its software. In other words, a replica is available if there is no hardware and software failure. We formulate this unavailability of an application as v∈V (1 -ρ v a P v P a ), where P v and P a are the availability probability of node v and application a respectively. In this way, maximizing the average availability or minimizing the average unavailability across all applications is a metric to be optimized, which we formally specify as follows:

f f ail (x) = 1 |A| a∈A v∈V (1 -ρ v a P v P a ) x = (ρ, γ, δ) (16)
Unlike single objective optimization problems that may have a unique optimal solution, in multi-objective optimization problems, conflicts among objectives usually prevent from having a single optimal solution that can optimize all 445 objectives simultaneously. In this way, improvement of one objective may lead to deterioration of another. For instance, reducing unavailability or increasing availability of applications means raising costs by placing more replicas. On the other hand, decreasing costs implies using more cloud resources as they are generally cheaper than edge resources, and thus increasing the deadline viola-450 tion. Therefore, it is necessary to search for a set of best optimal compromise solutions by considering trade-offs among the conflicting objectives.

The concept of Pareto dominance [START_REF] Stadler | A survey of multicriteria optimization or the vector maximum problem, part i: 1776-1960[END_REF] plays a vital role to find a set of best trade-off solutions that cannot be improved in any of the objectives without degrading at least one of the other objectives. Formally, a feasible solution x 1

Pareto dominates another solution x 2 , expressed as x 1 ≺ x 2 , only if

f i (x 1 ) ≤ f i (x 2 ) ∀i ∈ {1, 2, . . . , m} and f j (x 1 ) < f j (x 2 ) ∃j ∈ {1, 2, . . . , m} (17)
The set of all solutions that are not dominated by any other solution is called Pareto optimal set or Pareto front. These non-dominated solutions are considered equally good if there is no additional preference information. However, for the optimization problem [START_REF] Pires | A virtual machine placement taxonomy[END_REF], it is important to improve the performance of time-sensitive applications, which can be considered a preference information.

Moreover, we assume that a decision maker either does not have a preference order for other objectives or has difficulties in obtaining it. Motivated by this fact, we propose the following modification of Pareto dominance.

Preferred Dominance. Let f 1 be the highest priority function to be optimized among the list of objective functions F = (f 1 , f 2 , . . . , f m ). A feasible solution x 1 dominates another solution x 2 , expressed as x 1 ≺ 1 x 2 , only if

|f 1 (x 1 ) -f 1 (x 2 )| ≤ ξ and x 1 ≺ x 2 for (f 2 , . . . f m ) or if f 1 (x 1 ) < f 1 (x 2 ) -ξ (18)
where ξ is a constant approximation error. In other words, the dominance operator ≺ 1 prioritizes a selected function f 1 , and then it is sufficient that a solution x 1 has a smaller value than another solution x 2 in f 1 in order for x 1 dominates x 2 . Otherwise, if f 1 (x 1 ) and f 1 (x 2 ) have close values, then the Pareto dominance operator, defined in Equation 17, with the remaining objective functions is used instead. Therefore, we can select a performance-related function to time-sensitive applications as a priority goal. For instance, we can set the deadline violation in Equation 12as the primary objective to be optimized, i.e.,

f 1 = f dv .

Genetic Algorithm Proposal

Although well-known linear solvers, such as IBM ILOG CPLEX2 , can solve MILP problems, these problems are generally NP-Hard [START_REF] Zhao | Optimal placement of virtual machines for supporting multiple applications in mobile edge networks[END_REF]. Moreover, the linear version of Problem (13) in Appendix A is highly time-consuming due to a large number of variables. Another limitation of these solvers is that they only address single-objective optimization problems. A way to overcome this limitation is transforming a multi-objective optimization into a single-objective problem through scalarizing methods, such as weighted sum. However, these methods assume that there is a global preference order among all objectives to be optimized, which may be hard to define in practical cases. Furthermore, in many multi-objective optimizations, it is difficult to obtain the exact Pareto optimal set. Therefore, we propose a meta-heuristic based on Genetic Algorithm (GA) to obtain near-optimal solutions. We utilize a genetic approach because this meta-heuristic is not limited to linear, unconstrained, or single-objective problems. In other words, a GA can solve a nonlinear, constrained, and multiobjective problem, such as Problem [START_REF] Urgaonkar | Dynamic service migration and workload scheduling in edge-clouds[END_REF]. Moreover, a GA can be implemented in a parallel environment [START_REF] Cui | Review: Multi-objective optimization methods and application in energy saving[END_REF].

GA is a method for solving optimization problems inspired by the process of natural selection. In a GA, a population of candidate solutions, called individuals, to an optimization problem is evolved toward an optimal solution [START_REF] Goldberg | Genetic algorithms and machine learning[END_REF][START_REF] Holland | Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence[END_REF].

Each individual has a corresponding chromosome that encodes the solution. For instance, a traditional chromosome is represented by a string, or vector, of binary values, but other encodings are also possible. Moreover, a chromosome is associated with a fitness level, which is correlated to the objective function value of the solution it encodes. GA is an iterative process where at each step, called generation, it creates a new population by recombining or randomly mutating chromosome elements of selected individuals of the current population to produce offspring that make up the next generation. Individuals are selected stochastically, but those with better fitness are preferred over those that are less fit. Usually, GA terminates when either produces a maximum number of generations or reaches a satisfactory fitness level.

GA is typically applied for unconstrained optimization problems. A common way of incorporating constraints into a GA is through penalty functions that add a certain value to the objective function based on the amount of constraint violation present in a specific solution. Nonetheless, it may be extremely difficult to estimate good penalty factors or even generate a single feasible solution for some complex optimization problems [START_REF] Coello | Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art[END_REF].

An alternative method to handle constrained-optimization problems in GAs is to develop (i) special solution representations to simplify the shape of the search space, and (ii) special operators to preserve the feasibility of solutions at all times. Gonçalves and Resende [START_REF] Gonçalves | Biased random-key genetic algorithms for combinatorial optimization[END_REF] propose a Biased Random-Key Genetic Algorithm (BRKGA) where chromosomes are represented as a vector of randomly generated real numbers in the interval [0, 1]. A deterministic algorithm, named decoder, takes any chromosome as input and associates it with a feasible solution of an optimization problem, for which an objective value or fitness can be computed. In other words, a chromosome gives instructions on how to build a feasible solution for a particular problem.

Although BRKGA can handle constrained problems, it is generally applied for single-objective optimizations. On the other hand, GAs are suited for multiobjective problems due to the simultaneous evaluation of many candidate solutions, but it is necessary to incorporate the idea of Pareto optimality during the better fit selection process. Hence, we extend BRKGA by including the population classification strategy of the Non-dominated Sorting Genetic Algorithm II (NSGA-II) [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: Nsga-ii[END_REF]. NSGA-II is a well-known multi-objective genetic algorithm that uses dominance and diversity preservation mechanisms to rank individuals of a population.

Figure 2 shows the flowchart of our genetic algorithm that combines BRKGA and NSGA-II. In the next subsections, we detail the main evolutionary operations of the proposed genetic algorithm.

Chromosome representation

The chromosome representation proposed and the description of its parts are given below: 1. I a defines the number of replicas for an application a.

C = I 1 , I 2 , . . . , I |A| , S 1
2. S v a specifies the priority to place a replica of application a in node v. 3. E q is related to the order of a request q assigned to a replica, where q ∈ {1, 2, . . . , Q} and Q = Q u a is the total number of requests.

Decoder Algorithm. The proposed Algorithm 1 decodes the above chromosome representation into a feasible solution. Its basic idea is to first select the potential placement locations of each application (lines 4 to 7). For this, it takes the first part of the chromosome (I a ) to delimit the maximum number of possible nodes hosting an application replica on line 5. Then, nodes with high values in the second part of the chromosome (S v a ) are chosen as potential deployment sites for an application. The cloud is also added as a possible location to ensure that there are resources to deploy at least one replica of each application on the network.

The second step of Algorithm 1 is the load/request distribution (lines 8 to 20). It creates a sequence of all requests conforming to the third part of the chromosome (E q ). Following this sequence, requests are assigned one at a time among the nodes selected in the first step of the algorithm. For a request, the decoder looks for a node with short response time and sufficient resources to receive it. When the first envisioned target node is found, it sets to place a replica of the requested application on this node and assigns the request to this replica. It also updates the number of available resources and the response time of the target node after increasing the workload. Note that only the processing delay may be increased with a growing workload, thus using the estimated response time to select the target node is a way to distribute load among nodes without ignoring the network delay.

Finally, the decoder algorithm verifies that the maximum number of replicas of an application is respected and replaces surplus replicas with the cloud node (lines 21 to 24).

In order to exemplify how the Algorithm 1 works, let us define a simple system model with three nodes (one base station, the core, and the cloud), and one application, as shown in Figure 3a. This application allows a maximum of four replicas to be placed in the system (i.e., N 1 = 4), and it has three requests.

Moreover, the base station has resources available to receive a maximum of one request, while the core node can receive two requests, and the cloud has no restriction. Figure 3b shows the chromosome of an individual in this defined system. This chromosome leads the decoder algorithm to select only two nodes as candidates to host the application because I 1 N 1 = 0.5 * 4 = 2. More specifically, the base station and core nodes are selected because they have higher values in the second part of the chromosome (i.e., S BS 1 = 0.7, S core 1 = 0.4). The third part of the chromosome indicates that request E 2 is assigned first and followed by requests E 1 and E 3 . According to the shortest response time order in the second step of Algorithm 1, a replica of the application with request E 2 is placed in the base station and then another replica with the remaining requests E 1 and E 3 is placed in the core node. Figure 3c

Data: individual

Result: Decoded solution (ρ, γ, δ) Given that the number of resources types is much less than the number of nodes (i.e., R V ), then we have O (QV log V + QV R) = O (QV log V ). The loop between lines 21 and 24 has complexity O (AV ). Therefore, Algorithm 1 has

1 initialize ρ v a , γ u,v a , δ u,v a ← 0; 2 initialize d u,v a ← d a,
complexity O ((A + Q)V log V + Q log Q).

Initial Population

BRKGA initializes the first population with individuals as vectors of random

values. An alternative is to populate the starting population with a few solutions obtained with another heuristic for the specific problem being solved while the remaining individuals are randomly generated. This strategy may help speed up the convergence of the algorithm and improve the quality of the final solutions.

Hence, we apply the following heuristics that encode some feasible solutions on the proposed chromosome representation:

• Cloud. A simple solution is to place all applications in the cloud. According to Algorithm 1 (lines 4-7), it is sufficient that I a = 0 to only select the cloud node. Thus, the solution is encoded as

I a = 0, S v a = 0, E q = 0 ∀a ∈ A, ∀v ∈ V, ∀q ∈ [1, Q]
• Deadline. Another heuristic is to prioritize requests for applications with shorter deadline requirements. In addition, the heuristic selects as many nodes as possible, i.e., I a = 1, for an application to reduce response time and deadline violations. Given D app q as the application deadline requirement of request q, then the heuristic solution is encoded as

I a = 1, ∀a ∈ A S v a = 0, ∀a ∈ A, ∀v ∈ V E q = 1 - D app q max a∈A D a ∀q ∈ [1, Q]
• Net Delay. Zhao and Liu [START_REF] Zhao | Optimal placement of virtual machines for supporting multiple applications in mobile edge networks[END_REF] propose a heuristic that selects nodes with the lowest network latency for all other nodes as candidates to host an application. We encode this heuristic as follows:

I a = 1, ∀a ∈ A S v a = 1 - i∈V d a,i,v net max j∈V i∈V d a,i,j net , ∀a ∈ A, ∀v ∈ V E q = 0 ∀q ∈ [1, Q]
• Cluster. For each application, a heuristic is to place replicas of it in regions where its end-users are located. We can define a region as a set of close nodes where there are users attached to them (i.e., |U v a | > 0). Moreover, we apply the K-medoids clustering technique [START_REF] Park | A simple and fast algorithm for k-medoids clustering[END_REF] to detect those regions. The K-medoids algorithm is a variation of the classical K-means algorithm. Despite the similarity between these two algorithms, K-medoids chooses points in the dataset as centers, or medoids, of the clusters and can be used with an arbitrary distance function, while in Kmeans, a cluster center is not necessary a point in the dataset. Moreover, Park and Jun [START_REF] Park | A simple and fast algorithm for k-medoids clustering[END_REF] propose a simple and fast K-metoid algorithm with time complexity of O (nk), where n is the dataset size, and k is the number of clusters. These characteristics allow us to partition the subset of nodes where |U v a | > 0 in any connected graph using the network delay d a,u,v net as the distance function. Let M a be the set of medoids obtained after the execution of the clustering algorithm for an application a with a maximum of N a clusters. Then, the heuristic to place replicas close to end-users prioritizes nodes near to a center of |M a | regions, which is formally encoded as

I a = 1, ∀a ∈ A S v a = 1 - min i∈Ma d a,i,v net max j∈V min i∈Ma d a,i,j net , ∀a ∈ A, ∀v ∈ V E q = 0 ∀q ∈ [1, Q]
• Combined Solution. Given S as a set of random-key chromosome vectors and s i the i-th element of a vector s ∈ S with length n, then we can combine two or more heuristic solutions by summing their encoded vectors as specified below:

s + i = 1 |S| s∈S s i ∀i ∈ {1, . . . , n}
• Inverted Solution. In order to add more diversity to the initial population, we can add complementary, or inverted, solutions to those obtained by the above heuristics. Since s i ∈ [0, 1] is valid for each element of a chromosome vector s, we can obtain the inverted solution by doing the following operation: si = 1 -s i ∀i ∈ {1, . . . , n}

Next Population and Stopping Criteria

At the beginning of an iteration or generation t, our genetic algorithm decodes all individuals in the current population into feasible solutions. Next, it applies the sorting procedure of NSGA-II to rank individuals based on a dominance operator and a mechanism to preserve diversity. In this sorting procedure, we can either use our proposed dominance operator ≺ 1 or the Pareto dominance operator ≺ to check if a solution is better than another in a multi-objective context.

After the population sorting, the proposed GA partitions the population into two groups: (i) the best-ranked individuals as an elite group, and (ii) the remaining individuals as non-elite ones. Then, it adds the elite individuals without modification in the next generation. This elitist strategy keeps track of good solutions found during the algorithm iterations, which results in a monotonically improving heuristic. It is important to note that elite group size is a parameter of the algorithm, but a relatively small value is generally used.

In addition to the elite individuals, the next population is also composed of (i) mutant and (ii) offspring individuals. We utilize the BRKGA procedure to generate mutant individuals as simple random-generated vectors. Our GA completes the remainder of the next population with offspring. Each new offspring individual is produced by combining one solution selected at random from the group of elite individuals and one from the set of non-elite individuals. Similar to BRKGA, we use parameterized uniform crossover mechanism [START_REF] Spears | On the virtues of parameterized uniform crossover[END_REF] to combine two parent solutions and obtaining a new offspring. In this crossover mechanism, an offspring inherits a gene (i.e., the value of a vector element) of its elite parent with a probability P elite ≥ 0.5.

The above-discussed procedure for generating the next population is repeated until a stopping criterion is met. We use the stopping criterion for multi-objective problems proposed by Martí et al. [START_REF] Martí | A stopping criterion for multi-objective optimization evolutionary algorithms[END_REF], which is called MGBM after the authors surnames. MGBM tries to detect situations where no further progress will be made in the GA by designing a progress estimator Îmdr (t).

Thus, our GA terminates either when it reaches a maximum number of generations (i.e., t ≥ t max ) or when the progress estimation falls below a defined threshold (i.e., Îmdr (t) < Îmin mdr ). Here, t max and Îmin mdr are parameters to be set, and t ≥ 1 is the generation/iteration index.

Performance Analysis

In this section, we present the performance (i.e., the optimality) results of our proposed Genetic Algorithm (GA) by comparing it with benchmarking algorithms over a cellular network (5G) with Edge Computing (EC) capabilities. This section is structured as follows. First, Subsection 6.3 presents the performance metrics. Next, Subsection 6.2 describes the evaluated algorithms.

Then, Subsection 6.3 details the experiment setup. In Subsection 6.4, we define the values of key parameters of the proposed GA. Finally, we analyze the obtained experimental results in Subsection 6.5.

Performance Metrics

We select the deadline violation f dv , operational cost f cost , and service unavailability f f ail as performance-related functions to be optimized. We chose these functions because they are relevant in the context of EC, and there are conflicts between them, as discussed in Section 4.4. It is important to note that we can use other objectives since the proposed algorithm has no restrictions on this aspect.

Evaluated Algorithms

An overview of the compared algorithms is given below:

• MILP returns the optimal solution for the linear and relaxed version of (13) (see Appendix A). The optimal solution is found by the branch and cut technique in the CPLEX linear solver. We also use a timeout parameter to stop the solver tool.

• Cloud simply places everything in the cloud node.

• NetDelay+DL combines the Net Delay and Deadline heuristics presented in Section 5.2.

• Cluster+DL combines the Cluster and Deadline heuristics presented in Section 5.2.

• MOHGA(≺ 1 ) is the proposed GA for multi-objective using the heuristic initialization and the dominance operator ≺ 1 . The result of this algorithm is the best-ranked individual because we are only interested in obtaining a single solution.

• MOHGA(≺) is similar to MOHGA(≺ 1 ) but using the Pareto dominance operator ≺ instead.

• MOGA(≺ 1 ) is the same as MOHGA(≺ 1 ) but without using the heuristic initialization. That is, the first population is only randomly generated.

• SOHGA(f ) uses the proposed GA with heuristic initialization to optimize a single objective function f ∈ {f dv , f cost , f f ail }.

Analysis Setup

We conduct the experiment in Python with the CPLEX solver [START_REF]CPLEX, V12. 1: User's manual for cplex[END_REF] to evaluate the performance of the above-mentioned algorithms in a 5G network scenario. In this scenario, Base Stations (BSs) are equally distributed in a grid area, and there is a network link between neighboring BSs. There are also hosting nodes in different network parts (i.e., BS, core, and cloud), and their capacities are reduced as they descend from cloud to BSs.

We use the three types of applications specified for 5G networks, with the following characteristics [START_REF] Alliance | 5g white paper, Next generation mobile networks[END_REF]:

• massive Machine Type Communications (mMTC) has low resource usage, high deadline, and a large number of users;

Core-Cloud mMTC, URLLC: [START_REF] Filho | Approaches for optimizing virtual machine placement and migration in cloud environments: A survey[END_REF][START_REF] Xu | A survey on load balancing algorithms for virtual machines placement in cloud computing[END_REF], eMBB: [START_REF] Filho | Approaches for optimizing virtual machine placement and migration in cloud environments: A survey[END_REF][START_REF] Pietri | Mapping virtual machines onto physical machines in cloud computing: A survey[END_REF] An interval [a, b] means that a value is chosen randomly within this range.

• Ultra Reliable Low Latency Communications (URLLC) has low resource usage, a strict deadline, and a small volume of users;

• enhanced Mobile Broadband (eMBB) has high resource usage, a medium deadline, and an intermediate number of users.

Then, we randomly assign the value of the application parameters based on the above characteristics and some predictions for 5G discussed by Schulz et al. [START_REF] Schulz | Latency critical iot applications in 5g: Perspective on the design of radio interface and network architecture[END_REF] (response deadline and request rate). For evaluation purposes, we assume that it is sufficient to use relative values for the parameters among different application types instead of applying more realistically accurate values.

In addition, we also assume that the application resource demand h r a (•) and node usage cost g v (•) functions are linear according to Equations ( 19) and [START_REF] Martí | A stopping criterion for multi-objective optimization evolutionary algorithms[END_REF], respectively, where H a 1 , H a 2 , G v , and G r v are constants.

h r a (λ) = H a,r 1 λ + H a,r 2 (19)
g v (λ v a ) = G v ρ v a + r∈R G r v h r a (λ v a ) = G v ρ v a + r∈R G r v (H a,r 1 λ v a + H a,r 2 ) (20)
In order to have different user densities, users are distributed either uniformly or through isotropic Gaussian blobs [41] in the grid area. Then, a user is attached to the nearest BS. Finally, each test case is executed 30 times to obtain results with a 95% confidence interval [START_REF] Jain | The art of computer systems performance analysis[END_REF]. Table 4 summarizes the major experiment parameters.

Different Parameters Settings

Regarding the parameters of the proposed MOHGA(≺ 1 ), we analyze its performance in terms of the optimization objectives against different values of these parameters.

Elite and Mutant Group Size. In a GA with elitist strategy and random mutants, some parameters to be defined are the number of individuals in the elite and mutant sets. Figure 4 presents the influence of these parameters in the objective functions for MOHGA(≺ 1 ) with a population size of 100. We observe that values in the range between 10% and 20% for these parameters result in better results for all three objectives. These values allow the algorithm to have a diversity of solutions within the search space and still benefit from the elitist strategy. Therefore, we select the number of elite and mutant individuals to be both 10% of all population. Elite Probability. In the crossover operation described in Section 5.3, a parameter to be defined is the probability P elite to an offspring inheriting a gene of its elite parent. Figure 5 presents the impact of different values of P elite on the 745 objectives functions. We can see that this parameter does not have much influence on the objectives, but P elite = 0.6 has a slightly better results, specially for service availability in Figure 5c.

Stopping Criteria Threshold. We examine the performance of different stopping threshold Îmin mdr values for MOHGA(≺ 1 ) with a maximum of 100 generations 750 and a population size of 100 for each generation. Regarding the optimization objectives, the algorithm performs better when the threshold is below 0.2. However, a small threshold implies that the algorithm iterates over more generations, consequently, resulting in longer execution time, as shown in Figure 6d. Hence, we select Îmin mdr = 0.1 as a trade-off between optimality and execution time.

Results and Discussion

We evaluated performance of the examined algorithms for each optimization objective in scenarios with different amounts of applications, users, and hosting nodes.

Max. Deadline Violation. Figure 7a presents the impact on the system deadline violation level by increasing the number of deployed applications in a scenario with 5x5 BSs and 10k users. In all algorithms, the violation level grows as more applications compete for the fixed amount of node resources.

More specifically, Cloud heuristic has the worst results due to the distance between the users and the cloud node. Meanwhile, the optimum solutions of MILP number of nodes but with a fixed number of users and applications. This behavior is explained by how we estimate the number of requests generated. More specifically, we assume that there is at least one request coming from a node with users attached when the number of requests is defined as Q u a = |U u a |λ a in Section 4.1.2. Moreover, users will be more distributed in the test scenario by increasing the number of BSs. Consequently, there are more nodes with attached users and, thus, more requests are generated even if the number of users and applications does not change. Then, increasing the number of requests implies more resource consumption and higher operational costs.

Avg. Service Availability. Figures 9a,9b, and 9c relate the impact of service availability, or unavailability, with the variation of the number of applications, users, and nodes, respectively. Cloud heuristic has the worst results due to the placement of a single replica for each application, and all compared genetic algorithms outperform NetDelay+DL and Cluster+DL. Moreover, MOHGA(≺ 1 ) has slightly lower availability than other GAs in Figures 9a and9b. Meanwhile, the performance difference between MOHGA(≺ 1 ) and the other GAs is most notable in Figure 9c. This performance degradation may be explained by the trade-off of solution MOHGA(≺ 1 ) having less deadline violation. That is, MO-HGA(≺ 1 ) may try to place more replicas of time-sensitive applications to reduce deadline violations. Then, fewer resources are available to place many replicas of time-tolerant applications. Consequently, the average availability across all applications is impacted in MOHGA(≺ 1 ) as there are more time-tolerant than time-sensitive applications in our tests.

In Figures 9a and9b, we observe a considerable loss of availability for Net-Delay+DL and Cluster+DL heuristic by increasing the number of applications or users on a 5x5 BSs grid. As these heuristics may prioritize the same edge nodes for applications with some similar characteristics (e.g., network latency and user distribution), so there is more competition for those nodes by increasing the number of applications or users. As a result, NetDelay+DL and Clus-ter+DL deploy fewer application replicas resulting in decreased service avail-

835

Figure 9c shows that the majority of compared algorithms improve their performance by adding more hosting nodes in the system. As the number of nodes grows, it is possible to place more application replicas on the system, and thus, increasing service availability. Cloud is the only algorithm without improvement as the number of replicas deployed per application is fixed. We analyzed the efficiency of the proposed algorithm through simulations.

Our experimental results show that the proposed multi-objective GA achieves values close to the optimum of the MILP formulation in terms of deadline violation, and still generally outperforms the benchmark heuristics for the other analyzed objectives (operational cost and service availability). Moreover, we observed that the results of the proposed GA are related to the deadline prioritization and the heuristic initialization.

As future work, we plan to investigate the dynamic (or online) service placement and load distribution problems, which includes application migration, user mobility, and other dynamic changes in the network.

Node Capacity Constraint. For an application a, its monotonic resource demand function h r a (λ) may be nonlinear for a specific resource type r ∈ R. In this case, the function h r a (λ) can be replaced by an over linear estimator ĥr a (λ) in the domain interval [0, Q a ], as shown in Equation A.1, where H a,r 1 , H a,r 2 are constants, and Q a is equal to v∈V Q v a . That is, h r a (λ) is substituted by a linear function ĥr a (λ) such that h r a (λ) ≤ ĥr a (λ) for all λ ∈ [0, Q a ]. The idea here is that ĥr a (λ) results in a resource demand equal to or greater than that originally required by h r a (λ). For instance, a naive replacement can be the constant function ĥr a (λ) = H a,r 2 , where H a,r Given that requests only arrive at servers running the requested application according to Equations ( 3), ( 7) and ( 8), we have:

2 = max{h r a (x) | 0 ≤ x ≤ Q a }.
ρ v a λ v a = λ v a (A.2)
By applying Equations (A.1) and (A.2) to Equation 10, the node capacity constraint can be rewritten as: Queue Stability Constraint. In order to have a linear queue stability constraint, we apply Equations ( 4) and (A.1) to Constraint [START_REF] Skarlat | Towards qos-aware fog service placement[END_REF] and obtain:

λ v a H a,CP U 1 -W a + H a,CP U 2 > 0 ∀a, v (ρ v a = 1) , a ∈ A, v ∈ V (A.4)
However, it must remove the strictness of the above inequality to obtain a standard form of a MILP problem. For this, it is added a small constant Θ ∈ (0, 1]. Furthermore, both sides of the inequality are multiplied by ρ v a to ensure the queue existence constraint. Then, we further have:

ρ v a λ v a H a,CP U 1 -W a + ρ v a H a,CP U 2 ≥ ρ v a Θ ∀a ∈ A, ∀v ∈ V (A.5)
Finally, applying Equation A.2 to the above result, we obtain the following linear queue stability constraint:

λ v a H a,
γ u,v a d u,v a -D a ≤ ε ∀a ∈ A, ∀u, v ∈ V (A.7)
where ε ≥ 0 is a new variable indicating the system deadline violation that we want to minimize. Moreover, given Equations ( 1), ( 2), ( 4), ( 5) and (A.1), we rewrite Constraint (A.7) as:

γ u,v a λ v a d a,u,v net -ελ v a -λ v a D a H a,CP U 1 -W a + γ u,v a H a,CP U 2 d a,u,v net + W a -H a,CP U 2 D a + ε ≤ 0 ∀a ∈ A, ∀u, v ∈ V (A.8)
However, in Constraint (A.8), both γ u,v a λ v a and ελ v a are bilinear terms (i.e., multiplication of two variables). We can relax these terms to obtain linear ones using McCormick envelopes [START_REF] Mccormick | Computability of global solutions to factorable nonconvex programs: Part i -convex underestimating problems[END_REF]. That is, we replace these bilinear terms with new variables (ϕ u,v a = γ u,v a λ v a and ψ v a = ελ v a ) and add the following new linear constraints in the problem:

0 ≤ γ u,v a ≤ 1 and 0 ≤ λ v a ≤ Q a and 0 ≤ ε ≤ E ∀a ∈ A, ∀u, v ∈ V (A.9a) 0 ≤ ϕ u,v a ≤ λ v a and Q a (γ u,v a -1) + λ v a ≤ ϕ u,v a ≤ γ u,v a ∀a ∈ A, ∀u, v ∈ V (A.9b) 0 ≤ ψ v a ≤ λ v a E and εQ a + λ v a E -EQ a ≤ ψ v a ≤ εQ a ∀a ∈ A, ∀u, v ∈ V (A.9c)
where E is a constant specifying the maximum deadline violation allowed.

Then, we can rewrite Constraint (A.8) with the two new variables to have a linear constraint: It is important to note that a solution to problem (A.11) is also feasible for problem [START_REF] Urgaonkar | Dynamic service migration and workload scheduling in edge-clouds[END_REF], but it may present a higher objective value ε when applied to the original problem due to the bilinear relaxation.

ϕ u,v a d a,u,v net -ψ v a -λ v a D a H a,CP U 1 -W a + γ u,

Figure 1 :

 1 Figure 1: Proposed Edge Computing system for 5G networks.

F u,vaaaF

  Set of requests from users attached to node u to an instance of app a hosted on node v Q u Number of requests for app a generated from users attached to node u Qa Total number of requests for app a in the system d u,v a Average response time of a request flow F u,v a d a,u,v net Average network delay of a request flow F u,v a d a,u,v proc Average processing delay of a request flow F u,v a λ v Request arrival rate of app a on node v µ v a Service rate of app a on node v Problem Variables x = (ρ, γ, δ) Decision variables ρ v a Whether node v deploys an instance of app a or not γ u,v a Whether request flow F u,v a exists or not δ u,v a Number of requests in the flow F u,v a Optimization Objectives List of objective functions, F = (f1, . . . , fm) f dv (x) Deadline violation of the system given variable x fcost(x) Overall operational cost given variable x f f ail (x) Average unavailability of applications given variable x 4.1. Response Time Estimation Since requests can be distributed among multiple replicas of an application, we define a request flow F u,v a as the set of requests for application a ∈ A generated by users attached to node u ∈ V (source node) and handled by a replica of a placed on node v ∈ V (target node). In addition, let δ u,v a = |F u,v a | be the number of requests in a flow. Thus, Equation 1 specifies the average response time d u,v a of a request flow F u,v a , where d a,u,v net is the average time to

2 . 3 .

 23 Request Flow Existence γ = {γ u,v a | a ∈ A and u, v ∈ V} is the second set of binary variables, where γ u,v a ∈ {0, 1} specifies whether or not a request flow F u,v a exists between nodes u and v for an application a. Load Distribution δ = {δ u,v a | a ∈ A and u, v ∈ V} is a set of variables related to how requests are distributed, where δ u,v a ∈ Z + is the size of request flow F u,v a .

425

  the deadline violation of a request flow F u,v a as the positive part of the difference between its average response time and the application response deadline, i.e., max (0, d u,v a -D a ). Equation12expresses this objective function, where [z] + = max(0, z) is the positive part of a real number z.

Figure 2 :

 2 Figure 2: Proposed genetic algorithm flowchart.

  shows the feasible solution decoded from the exemplified chromosome. Complexity Analysis. Let A = |A|, V = |V| and R = |R|. The first outermost loop of Algorithm 1 (lines 4 to 7) has complexity O (AV log V ) due to the sorting procedure on line 6. Line 8 has complexity O (Q log Q). Assuming Algorithm 1: Proposed Chromosome Decoder.

1 E 1 E 2 E 3 (

 1123 b) Chromosome as an input parameter.

Figure 3 :

 3 Figure 3: Decoding example for Algorithm 1.

Figure 4 :

 4 Figure 4: Performance of different elite and mutant group sizes.

Figure 5 :

 5 Figure 5: Performance of different elite probability P elite values.

Figure 6 :

 6 Figure 6: Performance of different stopping criteria threshold Îmin mdr values.

Figure 7 :

 7 Figure 7: Maximum Deadline Violation

Figure 8 :

 8 Figure 8: Overall Operational Cost

  (a) 10000 users and 5x5 BSs (b) 50 apps and 5x5 BSs (c) 10000 users and 50 apps Legend

Figure 9 :

 9 Figure 9: Average Service Availability

840 7 .

 7 ConclusionIn this paper, we jointly formulated the static service placement and load distribution in an IoT and Edge Computing environment as an optimization problem by considering diverse application characteristics (e.g., response deadline, resource demand, scalability, and availability). The formulated problem aims to minimize SLA infringements, caused by violations of the deadline requirement, and other possibly conflicting objectives (e.g., operational cost and unavailability). Then, we proposed a multi-objective genetic algorithm based on BRKGA and NSGA-II to obtain feasible solutions close to the Pareto optimal front. We also modified the Pareto dominance operator to prioritize applications with strict deadline requirements. Furthermore, we included heuristic solutions during the initialization of the proposed genetic algorithm to improve its solution results.

2 (

 2 ĥr a (λ) = H a,r 1 λ + H a,r

2 d 2 D

 22 a,u,v net + W a -H a,CP U a + ε ≤ 0 ∀a ∈ A, ∀u, v ∈ V (A.10) Linear Formulation. Let ϕ = {ϕ u,v | a ∈ A and u, v ∈ V}, ψ = {ψ va | a ∈ A and v ∈ V}, and x = (ρ, γ, δ, ε, ϕ, ψ). Then, we use the above linearizations and relaxations to formulate the MILP problem of the static single objective case as follows:min x ε x = (ρ, γ, δ, ε, ϕ, ψ) s.t. eqs. (6) to (9), (A.3), (A.6), (A.9) and (A.10)(A.11)

Table 1 :

 1 Related work comparison

	Work	Problem Objective Requirement	Solution
	Skarlat et al. [11]	SP	SO	Resource-Based,	MH
				QoS-Based
	Tärneberg et al. [9]	SP	SO	Resource-Based	H
	Zhao and Liu [17]	SP, LD	SO	Resource-Based	H
	Gu et al. [16]	SP, LD	SO	Resource-Based,	H
				QoS-Based
	Yang et al. [23]	SP, LD	SO	Resource-Based	H
	Katsalis et al. [24]	SP, LD	MO2SO	Resource-Based,	D
				QoS-Based
	Spinnewyn et al. [25] SP	MO2SO	Resource-Based,	MH, H
				QoS-Based
	Our proposal	SP, LD	SO, MO	Resource-Based,	MH
				QoS-Based
	SP: Service Placement, LD: Load Distribution,
	SO: Single Objective, MO: Multi-Objective, MO2SO: MO transformed into SO,
	MH: Meta-Heuristic, H: Heuristic, D: Deterministic

Table 2 :

 2 Notations used in the proposed system model

	Symbol	Description
	System Model
		Set of network nodes, network links, resource types, applica-
	V, E, R, A, U
		tions, and users, respectively
	D a,e net	Network delay for application (app) a in a link e
	C r

v Total capacity of resource r on node v gv(λ) Resource allocation cost on node v for an app with workload λ Pv Availability probability of node v Da Maximum tolerable response time of app a Na Maximum number of replicas for app a h r a (λ) Demand of resource r for a replica of app a with workload λ Wa CPU work size of a request for app a λa Request generation rate for users of app a Pa Availability probability of app a U v a Set of users connected to node v requesting application a

Table 3

 3

		summarizes the notations used in this section, and the remaining of
		this section is organized as follows. First, Subsection 4.1 presents an estimation
	360	of the response time of a request. Then, Subsection 4.2 specifies the variables
		and constraints of the problem. Subsection 4.3 presents a nonlinear and linear
		formulation of the single-objective case. Finally, Subsection 4.4 formulates the
		multi-objective case.

Table 3 :

 3 Notations used in the problem formulation

	Symbol	Description
	Problem Formulation

Table 4 :

 4 Performance Evaluation Parameters

	Parameter		Value
	System
	CPU (MIPS)		Cloud: ∞, Core: 200000, BS: 40000
	Storage Disk (MB)	Cloud: ∞, Core: 32000, BS: 16000
	RAM (MB)		Cloud: ∞, Core: 8000, BS: 4000
	Node Availability Pv (%)	Cloud: 99.9, Core: 99.0, BS: 90.0
	Cost Gv, G r v		Cloud: 0.025, Core: 0.05, BS: 0.1
	User Proportion (%)	70 mMTC, 20 eMBB, 10 URLLC
	App. Proportion (%)	34 mMTC, 33 eMBB, 33 URLLC
	Applications
	Max. Replicas Na		[1, |V|]
	Deadline Da (ms)		mMTC: [100, 1000], URLLC: [1, 10], eMBB: [10, 50]
	λa (requests/ms)		mMTC: [0.0002, 0.001],
			eMBB: [0.001, 0.01], URLLC: [0.02, 0.2]
	App. Availability Pa (%)	mMTC, eMBB: [80.0, 90.0], URLLC: [90.0, 99.0]
	CPU Work Wa (MI)	mMTC, URLLC: [1, 5], eMBB: [1, 10]
	RAM, Disk H a,r 1 , H a,r 2	mMTC, URLLC: [1, 10], eMBB: [1, 50]
	CPU H a,r 1 , H a,r 2		Wa, Wa/Da + 1
	Net. Delay D a,u,v net	(ms)	mMTC, URLLC: [1, 2], eMBB: [1, 5]
	neighbor BS-BS, BS-Core
	Net. Delay D a,u,v net

  Objective Function. Problem[START_REF] Urgaonkar | Dynamic service migration and workload scheduling in edge-clouds[END_REF] has a min max f (x) objective, which is nonlinear because max function is nonlinear. This type of problem can be transformed into one without max function by replacing min max f (x) for min z, where z is a new variable, and adding a new constraint relating this variable to f (x) (i.e., f (x) ≤ z). In this way, the objective is linear, but it is necessary to check the linearity of the new constraint. Based on this transformation, we can add the following constraint in the problem:

CP U 1 -W a + ρ v a H a,CP U

https://www.ibm.com/products/ilog-cplex-optimization-studio

≥ ρ v a Θ ∀a ∈ A, ∀v ∈ V (A.6)

Acknowledgements

This work was partially financed by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior -Brasil (CAPES) -Finance Code 001, and by the FUI23 Project, SCORPION, in France.

Thus, Cloud heuristic is the optimum solution in this case. As solution SO-HGA(f cost ) includes the Cloud heuristic and only optimizes the cost function f cost , it also achieves an optimal solution. In addition, the multi-objective algorithms MOHGA(≺ 1 ), MOHGA(≺), and MOGA(≺ 1 ) have slightly better results than NetDelay+DL and Cluster+DL by varying the number of applications and 800 users, as shown in Figures 8a and8b, respectively.

In Figure 8c, all algorithms present a linear cost increase by varying the

Appendix A. Linearization and Relaxation

We transform the nonlinear problem (13) into a Mixed-Integer Linear Programming (MILP) problem by linearizing and relaxing its objective function, and constraints [START_REF] Filho | Approaches for optimizing virtual machine placement and migration in cloud environments: A survey[END_REF] and [START_REF] Skarlat | Towards qos-aware fog service placement[END_REF]. These transformations are described as follows.