Keywords: Optimization, Network Design, Network Slicing, Device-to-Device

Every second, a large amount of digital data is transported through huge number of types of devices via cellular networks worldwide, and expectations are at a greatly accelerated growth with increasingly large requests. In few years, these networks could thereby reach their maximum capacities in terms of data transmission. To face these challenges, Network Slicing has been presented as a novel virtualized infrastructure for the new generation cellular network system. This technology now not only covers application-level abstraction but also physical and switching layers virtualization, with di↵erent radio access and link communication technologies. Hence, each service provider is to be able to deploy its communication services on top of logical networks, named Network Slices, specifically tailored to its technical requirements. The Device-to-Device communication mode is another approach presented as a promising alternative to traditional communication in cellular networks. This technology allows to reuse radio resources and to decrease the end-to-end latency of local communications. Consequently, the optimization of physical resources in cellular networks becomes crucial to better deploy virtual networks. The overall objective of this work is therefore to define and study the concept of device-todevice communication and network slice design in 5G systems, and propose mathematical models and innovative algorithms to solve the underlying optimization problems.

A davit I, undersigned, Wesley da Silva Coelho, hereby declare that the work presented in this manuscript is my own work, carried out under the scientific direction of Stefano Secci (thesis director), in accordance with the principles of honesty, integrity and responsibility inherent to the research mission. The research work and the writing of this manuscript have been carried out in compliance with the French charter for Research Integrity. This work has not been submitted previously either in France or abroad in the same or in a similar version to any other examination body.

Paris, November 8th 2021

Signature

Résumé

Chaque seconde, une grande quantité de données numériques est transportée à travers une infinité de types d'appareils via les réseaux cellulaires du monde entier, et les attentes sont à une croissance considérablement accélérée avec des demandes de plus en plus importantes. En quelques années, ces réseaux pourraient ainsi atteindre leurs capacités maximales en termes de transmission de données.

Introduction

The expectations around the data flow on mobile networks are at a greatly accelerated growth with increasingly large requests. In few years, these networks could consequently reach their maximum capacities in terms of data transmission. To face all these challenges, 5G technology is posed by enabling the digitization of society and economic information. The idea behind the concept of 5G is that it does not correspond to a simple increase in data rate, as was the case for previous generations, but also the aim is thereby to widen the diversity of user equipment (UE).

This technological evolution will touch the whole network environment, going from cellular and radio access to the application service architectures. This transition challenges network design since multiple resources and segments, historically managed independently, are to be operated with both continuity in networking and computing resource allocation and provisioning an as-a-whole and unique service. In this context, di↵erent providers can be associated with di↵erent communication services (CS) running on the same physical network at the access, core, and application segments.

Such communication services can be of three classes: enhanced Mobile Broadband (eMBB; e.g., broadband everywhere and large-scale events), Ultra-Reliable Low Latency Communications (URLLC; e.g., online gaming and autonomous driving), and massive Machine Type Communications (mMTC; e.g., device-to-device communication and internet of things) -di↵ering in the requirements, such as maximum latency, minimum availability, and bandwidth. To provide the necessary flexible provisioning, Network Function Virtualization [2], Software Defined Networking [3], and Network Slicing [4] technologies can be adopted to let the CS provider deploy its services on top of logical networks.

Because of di↵erent bitrate and latency requirements, policies on radio access function splitting are also going to have an impact on the backhauling network dimensioning, and therefore on the placement of core network functions and on the configuration of edge computing application servers.

Moreover, di↵erent policies for control versus data-plane function sharing and scaling are expected to be applied.

To overcome these challenges, 'Network Slice' has been presented as a novel virtualized infrastructure model. This technology not only covers the application-level abstraction but also the physical and switching layers virtualization, with di↵erent radio access and link communication technologies.

Hence, each service provider is to be able to deploy its communication services on top of logical networks, named Network Slices, specifically tailored to its technical requirements.

The Device-to-Device (D2D) communication mode is another new approach presented as a promising alternative to traditional communication in cellular networks. This technology allows to reuse radio resources and to decrease the end-to-end latency of local communications. Then, D2D would allow a set of UEs geographically close to each other to establish direct D2D communications, or span multiple links (multi-hop D2D communications), to access a given service (e.g. video streaming or gaming) while ensuring the required service quality.

In this context, optimizing resources in cellular networks becomes crucial on backhauling network dimensioning, and hence on the placement of core network functions and the configuration of edge computing application servers. Moreover, di↵erent policies for control versus data-plane function sharing and scaling are expected to be applied. All these challenges must be overcome wisely and e↵ectively, as the state of the system can change every second. In legacy technologies, such as 3G and 4G, the entire network system was designed for approximately ten years of use, with small variations and slow evolution over the period. Contrarily, the 5G system is meant to be extremely flexible and still be able to o↵er a customized and complete virtual network in a few minutes for each Communication Service request. The overall objective of this work is therefore to define and study the concept of deviceto-device and network slice design in 5G systems and propose mathematical models and innovative algorithms to solve the underlying optimization problems. This manuscript is organized as follows. We first briefly present the basic notions on graph theory and combinatorial optimization in Chapter 2. Then, in Chapter 3, we overview the evolution of the mobile system, from 3G to 5G, and present the entities appearing in new generation networks as well the main modeling aspects and technical constraints related to 5G systems and beyond. The content presented in Chapters 3 was partially published in the IEEE Communications Standards Magazine [1].

In Chapter 4, we formally define the Domain Creation Problem (DCP) and we propose a node-arc (compact) integer linear programming (ILP) formulation to model it. We then present some strategies to enhance the linear relaxation of the formulation along with two classes of valid inequalities within a branch-and-cut algorithm to solve the problem. We also propose another solving method to address the DCP, which is based on a decomposition of the problem into two sub-problems: the routing sub-problem and the resource allocation sub-problem, that are to be solved separately. We further propose a two-phase heuristic, obtained by such decomposing. To solve the routing sub-problem, we propose two methods: an LP-based heuristic from the linear relaxation of a compact formulation, and a non-compact formulation obtained by generating a subset of relevant paths. Then, the allocation sub-problem is transformed into a vertex coloring problem that is solved heuristically by an improved greedy algorithm. The content of Chapter 4 was presented at the International Network Optimization Conference and published in its proceedings [START_REF] Benhamiche | Routing and resource assignment problems in future 5G radio access networks[END_REF].

In Chapter 5, we introduce and study the Network Slice Design Problem (NSDP) in 5G systems.

We first propose a mixed-integer linear programming (MILP) formulation for the problem including novel splitting, mapping and provisioning constraints described in the published 5G standards documents [START_REF]Architecture enhancements for control and user plane separation of EPC nodes (Release 14)[END_REF][START_REF] Ford | maximal flow through a network[END_REF][START_REF] Jump | Julia for Mathematical Programming: Callbacks[END_REF]. Then, we model new variants and extensions of the problem: NDSP with intra-slice flexible splitting (NSDP-ISFS) and NDSP with inter-slice split continuity. We then provide several sensitivity analyses regarding the impact of each proposed variant on the network. In Chapter 6, we propose several classes of valid inequalities in order to strengthen the linear relaxation of the proposed MILP and integrate them in a Branch-and-Cut framework to solve the problem. We further present several strategies to reduce the symmetries and the size of the model. We go beyond in Chapter 7 by proposing an open-access framework based on a math-heuristic for the Network Slice Design that relies on decomposing the NSDP into a few sub-problems and sequentially solve them. The content presented in both Chapters 5 and 7 was respectively presented at the International Conference on Network and Service Management and at the International Teletra c Congress, and published in their related proceedings [9,[START_REF]A Math-Heuristic for network slice design[END_REF].

We dedicate Chapter 8 to present another variant of the NSDP, where dedicated network functions are deployed to each network slice. Di↵erent strategies are then proposed in order to e ciently solve the optimization problems related to the problem. First, we propose a compact formulation and an extended one. To solve the former, we proposed a Relax-and-Fix heuristic that relies on repetitively solving the proposed related ILP with only a few integer variables and fixing or relaxing most of the remaining integer and binary ones. On the other hand, to address the exponential number of variables in the extended formulation, a column generation-based framework is then proposed. In this chapter, we describe some theoretical aspects that are fundamental to a better understanding of our work. We begin by describing some concepts of the graph theory and some classical problems that are used within our proposed approaches. Then we describe some exact and non-exact approaches commonly used to address optimization problems.

Theory of graphs

Graphs are widely used in computer science and applied mathematics. They are vastly used to describe di↵erent types of networks and scheduling processes for example. This section formalizes some concepts of graph theory to better represent cellular networks.

Definitions

As described in [START_REF] Gibbons | Algorithmic graph theory[END_REF], a graph is composed of vertices and arcs (or edges). A graph G is defined formally by a pair (V, E) where V is a finite set of elements called a vertex, and a subset (possibly empty) E is of pairs of elements of V . Each element of the subset E is called arc if the graph is oriented -or edge if the graph is a non-oriented graph.

The set E of an oriented graph, for example, is therefore composed of pairs (u, v), where u and v are called origin and destination respectively. We call size of the graph the cardinality of the set E, that is, the number of arcs of the graph. Similarly, we call order the cardinality of the set V , that is, the number of vertices of the graph.

Non-oriented graphs are graphs that have no orientation on their arcs (we, therefore, use the term edge), which means that if there is an edge between the vertex u and v, the information flow can be sent in both directions: from u to v and also from v to u. Both u and v can be the origin or destination of the edge at a time, depending on the case. Figure 2.1 shows a representation of a non-oriented graph of size 6 and order 5.

In this context, a path of length k between a vertex u and a vertex v of a graph G = (V, E) is a vertices sequence v 0 , v 1 , ..., v k such that u = v 0 , v = v k , and (v i≠1 , v i ) belongs to E for i = 1, ..., k. We say that a vertex v is reachable by a vertex u if there is a path between u and v such that its length k is greater than zero. Two vertices are called adjacent if k = 1. In this context, a complete graph is a graph where all vertices are adjacent to each other, that means that every pair of disjoint vertices is connected by an edge. A cycle in the graph is defined as a path v 0 , v 1 , ..., v k such that k > 0 and

v 0 = v k .
Finally, a path is called elementary if all its vertices are visited only once.

Some classical problems

We dedicate this sub-section to make a brief introduction to some important problems involving graphs that were used in this work.

Path finding problem

Pathfinding is a problem that consists in finding how to move in an environment between a starting point and a point of arrival taking into account di↵erent constraints. This problem is intensively studied and used in various fields such as transportation [START_REF] Gutenschwager | The shortest path: Comparison of di↵erent approaches and implementations for the automatic routing of vehicles[END_REF][START_REF] Dror | Note on the complexity of the shortest path models for column generation in vrptw[END_REF][START_REF] Zhang | Route selection for emergency logistics management: A bio-inspired algorithm[END_REF][START_REF] Zhang | Optimization of logistics route based on dijkstra[END_REF] and telecommunications [START_REF] Pham | Performance analysis of reactive shortest path and multipath routing mechanism with load balance[END_REF][START_REF] Zhang | Neural network implementation of the shortest path algorithm for tra c routing in communication networks[END_REF].

However, pathfinding becomes a complex problem when attempting to take into account various additional constraints (E.g., real-time execution, presence of uncertainties, resource constraints, and scalable environment). Initially, a path-finding problem can be reduced to a problem of finding the shortest path between two nodes in a graph. There are several ways to solve the shortest path problems, each one is adapted to a set of di↵erent problems [START_REF] Demetrescu | The Shortest Path Problem: Ninth DIMACS Implementation Challenge[END_REF]:

-Problem with a single destination: consists of determining the shortest path between each vertex of the graph and a given destination vertex;

-Problem with a single origin: determines the shortest path between a given vertex and all the other vertex of the graph;

-Origin-destination problem: determines the shortest path between two vertices given;

-All shortest paths problem: determines the shortest path between each pair of vertices present in the graph.

According to the same authors, specific algorithms to solve the shortest path problem are sometimes called path search algorithms. Among the algorithms of this class, the most known are:

-Dijkstra's algorithm [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF]: it solves the problem with an origin vertex in a graph whose edges have weights greater than or equal to zero. This algorithm can determine the shortest path to all the other vertices of the graph starting from a given vertex;

-Bellman-Ford's algorithm [START_REF] Bellman | On a routing problem[END_REF]: it solves the problem with an original vertex in a graph whose edges can have negative weights; -Johnson's algorithm [START_REF] Johnson | E cient algorithms for shortest paths in sparse networks[END_REF]: it determines the distance between all vertices pairs in a graph.

-Breadth-First Search (BFS) [START_REF] Beamer | Direction-optimizing breadth-first search[END_REF]: it calculates the distances of all nodes from a source node in 2.1. THEORY OF GRAPHS an unweighted graph (oriented or non-oriented); -Yen's algorithm [START_REF] Yen | An algorithm for finding shortest routes from all source nodes to a given destination in general networks[END_REF]: computes single-source K-shortest loopless paths for a graph with nonnegative edge weight.

In telecommunications and signal processing, the modeling might be slightly di↵erent (probabilistic), and the problem can be solved by the Viterbi's algorithm [START_REF] Andrew | Viterbi. 1967. error bounds for convolutional codes and an asymptotically optimal decoding algorithm[END_REF].

Max-clique problem

A clique in a graph G = (V, E) is a sub-set of vertices C ™ V , such that for every two vertices in C, there is an edge connecting them. This is equivalent to saying that the induced sub-graph of C is complete.

It is important to di↵erentiate a maximal clique from a maximum clique. A maximal clique is a clique that can not be extended by adding one or more adjacent vertices. On the other hand, a maximum clique is the largest possible clique on a given graph. The clique number Ê(G) of a graph G is the number of vertices of its maximum clique.

The optimization problem associated with the "clique problem" is the problem of the maximum clique: it consists in finding the largest clique (in the sense of its number of vertices) in a graph.

The search for a clique of maximal size in a graph is a classical problem of the complexity theory.

The maximum clique problem is one of the 21 NP-complete problems of Karp published in 1972 in Reducibility Among Combinatorial Problems [START_REF] Karp | Reducibility among combinatorial problems[END_REF].

Coloring problem

In graph theory, graph coloring is a special case of graph labeling. It is an assignment of labels traditionally called "colors". In its simple form, it is a process where a di↵erent color tone is assigned to each vertex of a graph, such that there is no adjacent vertex sharing the same color. This is called vertex coloring. Likewise, the edges coloring assigns a color to each edge so that there are no two adjacent edges of the same color.

The graph coloring problem can be formulated in two ways. First, as a decision problem, in which the objective is to identify if a graph is colorable with exactly k colors. In the second formulation, which is related to optimization problems, the objective is to find the minimum value of k. The fact that this problem is classified as NP-hard constitutes a shred of strong evidence that there are no 2.2. LINEAR PROGRAMMING polynomial algorithms that can be used in its resolution, justifying therefore the use of enumeration methods or development and use of heuristics [START_REF] Rego | Algoritmos para o problema de coloração de grafos[END_REF]. The size of the maximum clique of a graph is the best-known lower bound for the vertex coloring problem.

Linear programming

The development of linear programming has been classified as one of the greatest scientific advances since the 1950s. According to [START_REF] Hillier | Introdução à pesquisa operacional[END_REF], the problem of optimizing a linear function subject to linear constraints originated with the Fourier studies of linear inequalities systems in 1826. However, only in 1939, Kantorovich [START_REF] Kantorovich | The mathematical method of production planning and organization[END_REF] notes the practical importance of these questions, creating an algorithm for its solution.

This type of problem peaked with George Dantzig in the 1940s, with the formulation of the diet problem [START_REF] Dantzig | The diet problem[END_REF] as a problem of mixing components. Danzig not only formulates the problem of linear programming but also creates the Simplex algorithm for its solution in 1947. Its impact on the midtwentieth century has allowed companies to save millions of euros and continues to help the various industrial and service sectors nowadays.

According to [START_REF] Boussard | La programmation linéaire dans les modèles de production[END_REF], a general problem to be solved by linear programming can be defined as the objective of allocating in the best possible way -optimal -limited resources for activities that compete with one another. Thus, the choice of the level of activity determines the quantity of each resource consumed at each activity.

Linear programming, therefore, uses a mathematical model to describe the problem studied. According to [START_REF] Hillier | Introdução à pesquisa operacional[END_REF], the adjective linear means that all the mathematical functions of this model are necessarily linear functions 1 . On the other hand, the noun programming, in this context, does not refer directly to computer programming. It is, in essence, a synonym for planning.

Hence, linear programming winds up the planning of activities to obtain an optimal result, that is a result that makes it possible to obtain the best allocation of resources between all the possible scenarios. We can therefore define a generic model for any linear programming problem as follows:

max c t x (2.1)

LINEAR PROGRAMMING

Ax AE b (2.2)

x Ø 0 (2.3)
where c and b are vectors with constant values and have the size of the decision variables and the number of constraints, respectively. A is a matrix [|b|, |c|] also having constant values to represent the coe cients of each variable in each constraint. Here, x is the representation, also by a vector, of the decision variables. The Simplex algorithm is a powerful tool for solving this type of problem and we discuss it in the following sections.

Integer linear programming

A integer linear programming problem is a linear programming problem in which all of the variables are discrete -they must be integer values [START_REF] Hillier | Introdução à pesquisa operacional[END_REF]. Similarly, if there are continuous and discrete variables, then the mathematical model is a problem of a mixed integer linear programming (MILP).

We can therefore write the program as follows:

min{cx : Ax AE b, x Ø 0, x oe Z}

The author in [START_REF] Rao | Engineering optimization: theory and practice[END_REF] considers the problems of linear programming involving yes or no decisions as one of its most important applications. In these decisions, the only possible choices are yes or no.

With only two options, these decisions can be represented by decision variables that are limited to only two values, typically 0 or 1.

Consequently, the i-th decision of this nature is represented by x i , such that:

x i = I 1
, if the decision is yes 0 , if the decision is no These variables are called binary variables. Therefore, linear programming problems that contain binary variables can be classified as binary integer programming.

Geometric aspects of linear programming

In this subsection, we focus on the geometric aspects of Linear Programming, introducing the concepts of Convexity, Polyhedron and Facets. First, a point x is a convex combination of m points 2.2. LINEAR PROGRAMMING in x j R n , 'j = 1, .., m, if and only if

x = m ÿ j=1 ⁄ j x j m ÿ j=1 ⁄ j = 1 ⁄ j Ø 0 , 'j = 1..m bibitem R AO
In particular, a point x(⁄) is a convex combination of two points z and w, if

x(⁄) = (1 ≠ ⁄)z + ⁄w, ⁄ oe [0, 1]
Geometrically, they are the points on the straight line that goes from z to w. A set C oe R n is said to be convex when, for all x and y of C, the interval [x, y] is contained in C. That is to say:

⁄x + (1 ≠ ⁄)y oe C , 'x, y oe C, '⁄ oe [0, 1]
We call extreme point of a convex set C any point x which can not be represented as a convex combination of two distinct points of C. The C profile is the set of all extreme points of C. We call convex envelope of a set C, the intersection of all (closed) convex sets containing C. A convex and compact -closed and bounded -set C is equal to the closed convex envelope of its profile.

A constraint in R n is an inequality of the form g(x) AE 0, g : R n ae R and a feasible region defined by m constraints of the type g(x) is the set of feasible x points. A polyhedron in R n is a feasibility region defined by linear constraints:

Ax AE d
We say that in a feasible point x, the constraint g i (x) oe A is active if and only if it is of the form

g i (x) = d.
It is worthwhile mentioning that polyhedrons are convex, but not necessarily limited.

Duality in linear programming

According to [START_REF] Hillier | Introdução à pesquisa operacional[END_REF], any linear programming problem is associated with another linear programming problem called dual. And this original problem is called the primal problem. The relationship between the dual problem and the original problem (primal) is extremely useful.

LINEAR PROGRAMMING

Let a primal linear programming problem be described in the following way on the left, and for its corresponding dual problem we have the model on the right:

P RIM AL max c t x Ax AE b x Ø 0 DU AL min b t y A t y Ø c y Ø 0
If the primal problem is maximization, the dual problem is minimization. The dual problem uses the same parameters as its associated primal problem, but in the following way:

-The coe cients of the objective function of the primal problem are the right sides of the constraints in the dual problem.

-The right sides of the constraints in the primal problem are the coe cients of the objective function of the dual problem.

-The coe cients of a variable in the constraints of the primal problem are the coe cients of a constraint of the dual problem.

Knowing that the dual is also a problem of linear programming, one can say that there exists another associated problem of linear programming called dual. If one goes back to the problem, one sees that the latter is none other than the dual problem of departure. Thus we have that the dual of a dual problem is equal to the primal problem.

The main results of applying the primal-dual relation can be summarized in the following theorems, whose proofs can be found in [START_REF] Borwein | Characterization of optimality for the abstract convex program with finite dimensional range[END_REF][START_REF] Boyd | Convex optimization[END_REF]:

The weak duality theorem: If x is a feasible solution of the primal, and y a feasible dual solution, then necessarily c t x AE b t y. In particular, if c t x = b t y then x is an optimal solution of the primal and y is an optimal solution of the dual.

The strong duality theorem: If the primal problem has an optimal solution x then the dual problem has an optimal solution y. In this case, we necessarily have c t x = b t y.

SOLVING APPROACHES FOR LINEAR PROGRAMMING

Complementary gaps theorem: If x is a feasible solution of the primal problem, and y a feasible solution of the dual problem, then x and y are optimal feasible solutions if and only if the following conditions are satisfied:

-If a constraint is satisfied as a strict inequality in the primal (dual) then the corresponding variable of the dual (primal) is zero.

-If the value of a variable in the primal (dual) is strictly positive then the corresponding constraint of the dual (primal) is an equality.

The dual problem also has a much-used economic interpretation, called reduced cost. The value of the dual variable corresponding to a constraint of the primal gives the value of the reduced cost of this constraint. We consider the reduced cost as the potential gain we can have in the objective function of the primal: its value gives us the e↵ect on the objective function if we increase by one the right side of the constraint. We can compute the reduced cost cr associated with a variable x of the primal by:

cr = c ≠ A t y.
If we look at the constraint A t y Ø c of the dual model described above, we can easily see that the reduced cost is associated with the fact that the constraint is satisfied or not.

Solving approaches for linear programming

In this section, we describe the most e cient methods for solving linear programs. We first introduce the Simplex method. Then, we cover the methods of linear relaxation and cutting planes.

We also introduce the basis of e cient branch-and-bound and column generation methods. Finally, we present some non-exact methods such as heuristics and meta-heuristics.

Graphical method and Simplex

The Graphical method -or Geometric method -allows solving simple linear programming problems in an intuitive and visual way. This method is limited to problems with two or three decision variables since it is not possible to graphically illustrate more than 3 dimensions. According to [START_REF] Moskowitz | Investigación de operaciones[END_REF], this method is a visual aid to interpret and understand the algorithm of the Simplex method (much more sophisticated and abstract) and the concepts that surround it. The phases of the problem-solving process using the Graphic method are as follows:

-Draw a Cartesian coordinate system in which each decision variable is represented by an axis.

-Establish a scale of measurement for each of these axes appropriate to the associated variable.

SOLVING APPROACHES FOR LINEAR PROGRAMMING

-Draw the constraint coordinates of the problem, including non-negative (which will be the axes themselves). Note that an inequality defines a region that will be the half-plane bounded by the straight line obtained by considering the constraint as an equality, while an equation defines a region that is the straight line itself.

-The intersection of all regions determines the feasible region or solution space (which is a convex set). If this region is not empty, one must continue to the next step. Otherwise, there is no point that simultaneously satisfies all constraints, so the problem will have no solution and it will be called unfeasible.

-Determine the endpoints or vertices of the polygon or polyhedron that form the feasible region.

These points will be the candidates for the optimal solution.

-Evaluating the objective function at each vertex. That (or those) that maximize (or minimize)

the resulting value will determine the optimal solution to the problem.

The Simplex method is an iterative process that allows improving the solution of the objective function in each step. The process ends when it is not possible to continue improving this value, that is when the optimal solution is obtained. Based on the value of the objective function at any point, the procedure consists in looking for another point that improves the previous value. As can be seen in the graph method, such points are the vertices of the polygon (or polyhedron, if the number of variables is greater than 2). The search is carried out employing displacements by the edges of the polygon, from the current vertex to an adjacent one that improves the value of the objective function.

Whenever there is a viable region, and since its number of vertices and edges is finite, it will be possible to find the solution. For problems of maximization, for example, the Simplex method is based on the following property: if the objective function Z does not take its maximum value at vertex A, it means that there is an edge that starts from A and along which the value of Z increases.

Linear relaxation

In integer linear programming, we use the term relaxation to indicate that some of the restrictions of the original problem have been relaxed. The most known example is the linear relaxation. In this particular case, we remove the integrality constraint on all variables of the original model. Formally, if we have a formulation F represented by z = min{c(x) : x oe P } where P is the set of points that satisfy the constraints of the formulation, c(x) is the objective function and z is the value of the optimal solution.

A formulation

F R z R = min{f (x) : x oe R}
is a relaxation if all the points of P are in R (P ™ R) and if f (x) AE c(x) for x oe P . Note that because of these properties, the optimal relaxation solution is a dual limiting for the original formulation, z r AE z. The dual limiting can be used, for example, to improve the performance of the Branch and Bound algorithm [START_REF] Schrijver | Theory of linear and integer programming[END_REF] .

The advantage of using relaxations in some cases is that they are easier to solve. For example, linear relaxations can be solved in polynomial time, while the integer version, in general, is much harder to be solved [START_REF] Schrijver | Theory of linear and integer programming[END_REF]. We can relax a formulation by removing some of its constraints. Note, however, that the more we relax the formulation, the further we will be from the optimal solution.

Ideally, one should find a relaxation that is easy to solve and that gives us a good dual limit, that is, very close to the optimal value of the original formulation.

Linear relaxation of an integer linear programming can be solved using a standard linear programming technique, such as Simplex algorithm. If the optimal solution for the relaxed linear program has all the variables equal to an integer value, then it is also the optimal solution for the original integer model [START_REF] Alves | Programação linear inteira[END_REF].

The branch-and-bound framework

To exactly solve an NP-hard optimization problem is often a challenging task requiring very e cient algorithms, and the Branch and Bound paradigm is one of the main tools on this. A Branch and Bound algorithm searches the complete solution space for a given problem for the best solution. However, explicit enumeration is normally impossible because of the exponentially increasing number of potential solutions. The use of limits for the function to optimize, combined with the value of the best current solution allows the algorithm to search for parts of the solution space implicitly.

At any time during the process of finding the solution, the state of the solution over the search for the solution space is described by an unexplored subset of this and the best solution found so far.

According to [START_REF] Hillier | Introdução à pesquisa operacional[END_REF], at first, a single subset exists, namely the complete solution space, and the best 2.3. SOLVING APPROACHES FOR LINEAR PROGRAMMING solution found so far is OE. Unexplored subspaces are represented as nodes in a dynamically generated search tree, which initially contains only the root, and each iteration of the classical algorithm treats such a node. The iteration has three main components: the selection of the node to be processed, calculation of the limit, and the branching step. The sequence of these may vary depending on the strategy chosen to select the next node to be processed.

If the following sub-problem selection is based on the value of the sub-problem boundary, the first operation of an iteration after choosing the node is branching, that is, the subdivision of the space of the solution of the node into two or more subspaces to be studied in a subsequent iteration. For each of them, we check whether the subspace consists of a unique solution, in which case it is compared to the best current solution while keeping the best of them. Otherwise, the subspace selection function is computed and compared to the best current solution. If it can be established that the subspace can not contain the optimal solution, the whole subspace is rejected, otherwise, it is stored in the set of live nodes with its limit. In [START_REF] Clausen | Branch and bound algorithms-principles and examples[END_REF], this is called impatient strategy for node evaluation, since the limits are computed as soon as nodes are available.

An alternative is to start with the calculation of the boundary of the selected node, then branch on this node if necessary. The created nodes are then stored with the boundary of the processed node.

This strategy is often used when the next node to be processed is chosen to be a living node of the maximum depth in the search tree. The search ends when there are no more unexplored parts of the solution space, and the optimal solution is then the one recorded as the best current.

Cutting planes and branch-and-cut algorithm

Now, we introduce the concept of Cutting Planes. Let P be the following linear programming problem:

max{cx|x oe X} with X = {x oe R n |Ax AE b , x oe Z}
where A and b have rational coe cients. An inequality fix AE fi 0 is a valid inequality for X if fix AE fi 0 is valid for all x oe X. As a valid inequality for X, we have, in particular, those which define the convex

SOLVING APPROACHES FOR LINEAR PROGRAMMING

envelope of X, conv(X), which is always a polyhedron. According to [START_REF] Alves | Apoio à decisão em problemas de programação inteira e inteira-mista multiobjectivo: contribuições metodológicas[END_REF] the problem P could be solved through max{cx|x oe conv(X)} because all the basic solutions that optimize this problem are also optimal solutions for P . However, there is usually no a simple way to characterize the inequalities needed to describe P .

Let S be the linear relaxation of P . We define a cutting plane as a valid inequality for X that cut the non-integer solutions of S. In general, an algorithm of cutting planes has the following form:

-beginning -t = 0 et S 0 = S -Iteration t -Determine the optimal solution x t for the relaxed problem: max{cx|x oe S t }. If x t is integer, then x t is an optimal solution for P . Otherwise, if we find a valid inequality for X, fi t x AE fi t 0 , which cuts x t , such as fi t x > fi t 0 , we add it to S, S t+1 = S t fl {x : fi t x AE fi t 0 }, and we increase t, t = t + 1. If we do not find any valid inequality, we finish the procedure.

The Iterations are also known as the separation problem and give us the following theorem [START_REF] Grötschel | The ellipsoid method and its consequences in combinatorial optimization[END_REF]: A cutting plan procedure may intend to end when an entire solution is found, or serve only to improve the formulation of the original problem. We call branch-and-cut algorithm when the separation routine is within a branch-and-bound framework.

Theorem 2.

Column generation and the branch-and-price algorithm

In this section we discuss the column generation method. It is a technique used to solve a linear program when the number of variables of the model to solve is very large.

The basic principles of column generation have been published for more than four decades [START_REF] Barnhart | Branch-and-price: Column generation for solving huge integer programs[END_REF].

Hence, the methods of separation and the generation of columns (branch-and-price) were born. One of the first successful practical applications was made in 1961 and 1963 by Gilmore and Gomory on the cutting problem [START_REF] Gilmore | A linear programming approach to the cutting stock problem-part ii[END_REF]. In this application, the solution was found by rounding.

In the generation method of columns, the original problem is divided into two problems:

-Restricted master problem: the problem to solve, with fewer columns;

-Subproblem: generator of new columns for the master problem.

These columns are embedded in the set of columns used by the restricted master problem to improve As pointed-out by [START_REF] Sarah | A column generation approach to bus driver scheduling[END_REF], the purpose of the sub-problem is therefore to generate new columns (variables). These new columns are added to the restricted master problem that improves the value of the solution, or updates the dual variables, to produce other new columns by the subproblem. The interaction between these two problems is represented in the figure 2.2 below:

Since the main problem only works with a subset of columns, a linear programming packet can quickly find the solution. When new columns are added little by little, a solution can be obtained from the previous solution. To this point, the method focuses on approaches to solve the sub-problem more e↵ectively. Let the problem P 3

min c t x (2.4) subject to Ax Ø b (2.5) 2.3. SOLVING APPROACHES FOR LINEAR PROGRAMMING x Ø 0 (2.6)
This problem has a large number of variables. For this reason, it may not be possible to solve it directly. We first solve a problem P 4 which is smaller, with a subset x Õ ™ x of variables:

min c Õt x Õ (2.7) subject to A Õ x Õ Ø b (2.8) x Õ Ø 0 (2.9)
For many constraints, each solution found must be tested if it satisfies all constraints, even those that are not yet in the model. We call this test as viability test. In the case where the problem has a large number of variables we must do the test of optimality, that is to say that each solution found must be tested to know if the solution is an optimal solution of the problem, even without variables that are not yet included in the model.

y Ø 0 (2.12)
When we solve the model P 4 we find a solution x Õú . Let y ú be the solution of the dual problem P D 1 . This solution is tested to find the constraints violated by y ú in the dual set in (2.11). All or some of the variables corresponding to the violated constraints are added to the problem P 4 , modifying x Õ , c Õ , and A Õ . This process must be iteratively redone until there are no more violated constraints in the dual problem P D 1 .

SOLVING APPROACHES FOR LINEAR PROGRAMMING

The test in (2.11) for a solution y ú , rewritten as c ≠ A t y Ø 0, shows more clearly the significance of the separation problem in the dual model. For each variable x j , the first term of the inequality (2.13) is the reduced cost in the primal problem P 4 , computed by the dual prices y ú i of the constraints.

c ≠ ÿ i a ij y i Ø 0 (2.13)
It should be noted that an unsatisfied constraint in the dual problem is equivalent to a negative cost variable negative in the primal problem. This variable, when added to the model, can produce a solution having a better value in the objective function, and it is therefore interesting to add it to the problem. This method is called column generation and we call branch-and-price algorithm when the column generation routine is within a branch-and-bound framework.

The original problem with fewer variables is called master problem. The separation problem in the dual (or pricing) model, which is the problem of finding or generating a new column, is commonly called sub-problem. As mentioned earlier, this process can be used in problems where the number of variables is very large, which would make it impossible to develop a model with each of them exactly. According to [START_REF] Pileggi | Heurísticas para os problemas de geração e sequenciamento de padrões de corte bidimensionais[END_REF], it is not necessary to introduce all the variables in the model, just create an algorithm that, starting from the dual prices of the current solution, finds variables of reduced cost, then simply add these variables to the master problem. We can go even further: it can be applied to problems where we do not yet know all the variables. It is enough to generate iteratively the variables of reduced negative cost which are interesting in the problem of optimization.

Heuristic methods

A heuristic is an algorithmic procedure developed by a cognitive model, usually by rules based on the experience of developers. Unlike exact methods that seek to find an algorithmic way to find an optimal solution by combining or looking for all possible solutions, heuristics usually tend to have some degree of knowledge about problem behavior, generating a much smaller number of solutions [START_REF] Arroyo | Heurísticas e metaheurísticas para otimização combinatória multiobjetivo[END_REF].

Many factors make using heuristic algorithms interesting to solve a particular problem. According to [START_REF] Clancey | Heuristic classification[END_REF], some factors are:

-When there is no exact method to solve this problem or it requires a very high processing time.

In this case, o↵ering a good solution is better than having no solution;

SOLVING APPROACHES FOR LINEAR PROGRAMMING

-When the solution is not necessary because the solutions obtained are already reasonable; -When data is unreliable. In this case, the search for the optimal solution has no meaning, because it is already an approximation of reality;

-When time and/or money constraints require the use of rapid response methods;

-As intermediate steps of other algorithms, potentially accurate or others heuristics.

Heuristic methods include strategies and approximation procedures to find a good solution, even if not optimal, within a reasonable calculation time.

A constructive heuristic is a type of heuristic that begins with an empty solution and extends the current solution until a complete solution is obtained. It di↵ers from the local search heuristic which begins with a complete solution and then tries to improve the current solution with local movements [START_REF] Clancey | Heuristic classification[END_REF].

A meta-heuristic is a generic heuristic method for solving optimization problems (usually in the domain of combinatorial optimization). Meta-heuristics are generally applied to problems that do not have a known e↵ective algorithm. According to [START_REF] Simon | Heuristic problem solving: The next advance in operations research[END_REF], they use the combination of random choices and historical knowledge of the previous results obtained by the method to orient itself and carry out its search through the space of possible solutions, which prevents premature stoppages in optimal premises.Local search is a meta-heuristic method for solving optimization problems. The main objective is to find the "best" solution among several possible candidates by maximizing or minimizing the criteria. From a starting point, this type of method applies local changes until a solution considered ideal is found, or a time limit of execution is exceeded [START_REF] Simon | Heuristic problem solving: The next advance in operations research[END_REF]. Therefore, each solution found, better than the last, gets the new starting point for the next iteration. The search space contains all possible solutions to a problem.

According to [START_REF] Katz | Proceedings of the SIGCHI conference on human factors in computing systems[END_REF], the criteria for the use of a heuristic to solve a particular problem are the following:

-Optimality: When there are several solutions to a given problem, does the heuristic ensure that the best solution will be found? Is it really necessary to find the best solution?

-Completeness: When there are several solutions to a given problem, can the heuristic find all of them? Do we really need all the solutions? -Precision: Can this heuristic provide a good interval of confidence for the desired solution? Is the gap between the optimal solution and the one found by the heuristic good enough?

Chapter 3

A view on the telecommunications network evolution Contenu Every second, a large amount of digital data is transported through huge number of types of devices via cellular networks worldwide, and expectations are at a greatly accelerated growth with increasingly large requests. In this context, in few years these networks could reach their maximum capacities in terms of data transmission. Consumer mobile communications, video downloads, and the use of mobile applications represent the bulk of the current use of radio resources in 4G networks.

Hence, the need to optimize resources in classical cellular networks becomes extremely important. To face all these challenges, 5G technology is posed by enabling the digitization of society and economic information. The idea behind the concept of 5G is that it does not correspond to a simple increase in data rate, as was the case for previous generations. With 5G, the aim is thereby to widen the diversity of users.

In this context, Device-to-Device communication (D2D) has been highlighted, as it provides a better allocation of resources compared to conventional cellular communication underway. D2D is a set of communication technologies that allow two digital devices (i.g., mobile phones and robots) in close proximity zone to communicate directly with each other without passing through the traditional cellular network's access points (i.e., antennas and base stations). With discovery and communication functions, the user equipment can find others around to exchange information.

Network Slicing [4] is another novel virtualized infrastructure model in new generation mobile networks. This technology now not only covers application-level slice abstraction as done with preliminary works on 'slicing', but also physical and switching layers virtualization, with di↵erent radio access and link communication technologies. This transition challenges slice network design since multiple resources and segments, historically managed independently from each other, are to be operated with continuity in networking and computing resource allocation and provisioning as a whole and unique service. In this context, di↵erent providers can be associated with di↵erent communication services running on the same physical network at the access, core, and application segments.

Because of di↵erent bitrate and latency requirements, policies on radio access function splitting have an impact on the backhauling network dimensioning, and therefore on the placement of core network functions and on the configuration of edge computing application servers. Moreover, di↵erent policies for control versus data-plane function sharing and scaling are to be applied. For instance, in 5G a first service classification in three classes is given [START_REF]Architecture enhancements for control and user plane separation of EPC nodes (Release 14)[END_REF]: enhanced Mobile Broadband (eMBB), Ultra-Reliable Low Latency Communications (URLLC), and massive Machine Type Communications (mMTC). Each of these application categories has its specific requirements, such as maximum latency, minimum availability, and bandwidth capacity and, to provide a flexible environment to support those customized networks, novel infrastructures are supported by Network Function Virtualization [2], Software Defined Networking [3], and Network Slicing [4] technologies. Hence, each communication service (CS) provider can deploy its services on top of logical networks, named Network Slices, specifically tailored to its technical requirements.

CORE NETWORK EVOLUTION

Addressing end-to-end network slicing, however, requires considering heterogeneous resources from di↵erent physical and virtual network topologies, each with specific technical constraints and particular orchestration rules. Furthermore, an important novelty of 5G specification is the introduction of three novel mapping dimensions influencing the placement and interconnection of slices and network functions: (i) a CS can be delivered by multiple network slices; (ii) Slices can be decomposed into Network Slice Subnets; and (iii) Network Functions can be decomposed into Network Function Services.

While the first mapping requirement can simply impact network design hyperparameters only, the second and third ones come with new technical constraints to guarantee a coherent provisioning of each CS. Namely, continuity constraints among slice subnets and the capacity to support specific behaviors for all the components of the same slice, such as function splitting, sharing, and scaling policies. In addition to these peculiar constraints, classical network function embedding, routing, and requirements on latency, availability, and network and computing capacities hold as well.

In this chapter, we present the entities appearing in new generation networks and the main modeling aspects and technical constraints related to 5G systems and beyond 1 .

Core network evolution

Third Generation Partnership Project (3GPP) emerged from the need of technically specifying the third generation (3G) mobile network. Such specifications were structured in documents called Releases: the first one was issued in 1999, called Release 99 [START_REF]3rd Generation Partnership Project[END_REF]. At that time, 3GPP's work was based on Global System for Mobile communication networks, also called 2G systems. The Core Network is responsible for all control and central processing for the 3G system, being an evolution of the legacy Network Switching Subsystem. For the conventional Circuit Switched domain, the 3G core network was conceived with Mobile Switching Center (MSC) and MSC Gateway (GMSC) entities, responsible for carrying calls from network users and interfacing with external circuit-based networks, respectively. 3G mobile technology supports a wide variety of services, ranging from multimedia applications available on the Internet. For this purpose, 3G core is also conceived with a Packet Switched domain

CORE NETWORK EVOLUTION

to carry users' data. As described by [START_REF] Neruda | Evolution of 3gpp core network[END_REF], this domain includes General Packet Radio Services Support Node (SGSN) and Gateway General Packet Radio Services Support Node (GGSN). While SGSN is the entity responsible for mobility, session management, and billing, GGSN can be seen as the main entity of the 3G core. In this architecture, GGSN is responsible for ensuring and managing the connection with external packet-switched networks, (e.g., Internet). Furthermore, Equipment Identity Register (EIR), Home Location Register (HLR), and Authentication Center (AuC) are the entities shared by both Circuit and Packet domains and contain all administrative information of each subscribed User Equipment (UE). These entities are also responsible for connection rules and information and data protection.

From 3G to 4G

To better deal with the immense popularization of the Internet on mobile phones and to support a greater number of customers and volume of data, Release 8 [START_REF]Technical Specifications and Technical Reports for a UTRAN-based 3GPP system (Release 8)[END_REF] was delivered by 3GPP in 2009.

Release 8 was the first document presenting standards for Long-Term Evolution (LTE) mobile system, so-called 4G. It is important to note that 3GPP did not change its name when moving to 4G (and beyond) technology specification. . Release 8 presents standards for the Packet Switch system, called Evolved Packet Core (EPC).

Within this new architecture, all services (e.g. voice, SMS, and data) are driven by the Internet Protocol (IP), which implies the disappearance of Circuit Switched domain from legacy Core Network.

As depicted in Fig. 3.1, MSC and EIR's functionalities were combined into Mobility Management Entity (MME), the main controlling entity in EPC. MME is responsible for authentication, roaming, and session management on the broadband network. It interfaces with two other entities, named Home Subscriber Server (HSS) and Serving Gateway (S-GW). The former is the database where all network user information is found and can be considered as an aggregation and evolution of HLR and AuC from the 3G system. S-GW, in turn, has some functionalities from the legacy SGSN 3G core entity.

It acts as mobility anchor during handovers and is responsible for routing users' data packets. In that way, each user that accesses the EPC is associated with a single SGW, which interfaces with Packet Data Network Gateway (PDN-GW). This last entity is the essential interconnection point between EPC and external IP-based networks. It is also responsible for packet filtering, legal interception, and IP address allocation. Hence, PDN-GW has functionalities from GMSC and GGSN, combined.

CORE NETWORK EVOLUTION

Finally, we find the Policy and Charging Rules Function (PCRF) within the EPC system. It is part of a functional framework called Policy and Charging Control (PCC), which is used to control the bearer services o↵ered by the LTE network as well as to control the charging mechanisms. PCRF is a software component and is responsible for providing access rules and policies for core network gateways.

Separating 4G core with CUPS

In order to o↵er a higher degree of modularity and scalability for core entities, 3GPP proposes a new architecture called CUPS: it stands for Control and User Plane Separation and o↵ers a complete split between Control Plane (CP) and User Plane (UP). In this new EPC system, introduced in Release 14 [START_REF]Architecture enhancements for control and user plane separation of EPC nodes (Release 14)[END_REF], a more e↵ective approach to support increasing and dynamic tra c is provided. With CUPS, UP and CP scaling can be made independently. For this purpose, S-GW becomes Serving Gateway

From 4G to 5G

The 5G architecture enhanced by Network Function Virtualization (NFV), Software-Defined Networking (SDN), and Network Slicing provides an even more flexible environment supporting end-to-end customizable virtual networks. With dedicated resources to ensure specific QoS for a wide variety of services, all entities in 5G might be entirely or partially virtualized. 3GPP proposes 5G Core (5GC), another change in the mobile core network. Hence, 5GC presents the evolution of the legacy entities found in 4G and additionally introduces optional Network Functions that might be necessary to control and operate each slice. In the resulting new virtualized architecture, what were called entities in 3G and 4G are now called Network Functions in 5G Management Function (AMF), Session Management Function (SMF) and Unified Data Management (UDM). AMF is responsible for registration, connection and reachability management, access authentication, and access authorization. UDM further shares responsibilities found in legacy HSS with the new Authentication Server Function (AUSF). SMF, in turn, is responsible for session management and takes all functionalities from PGW-C and SGW-C. Additionally, SMF will directly interface with 5G User Plane, which is represented by User Plane Function (UPF). In this context, UPF might apply all functionalities found in PGW-U, SGW-U and TDF-U, combined. Moreover, policies and charging rules, which were in 4G PCRF entity, are provided by the Policy Control Function (PCF), which interfaces with Application Function (AF); AF is meant to act like the logical 4G AF integrated into PCC framework [51], o↵ering dynamic tra c information and applications based on user behaviors.

In this evolving context, we can identify a primary set of functions that need to be present to deploy a core slice. In that way, this slice must contain at least the basic functions connected to control and user planes: AMF, SMF, PCF, AUSF, UDM and UPF. Additionally, to better control and operate each slice in future 5G networks with specific requirements and technical constraints, several new functions are proposed by 3GPP [START_REF] Jump | Julia for Mathematical Programming: Callbacks[END_REF][START_REF]Telecommunication management, Charging management, 5G system and charging service (Release 15)[END_REF][START_REF]Binding Support Management Service (Release 15)[END_REF]. Following, we present the main functionalities of these

5G CORE SPECIFICITIES new functions:

-Network Exposure Function (NEF) -event and capability safe exposure to functions and third party networks.

-Non-3GPP Inter Working Function (N3IWF) -IP Security tunnel support in cases of untrusted non-3GPP accesses.

-Network Slice Selection Function (NSSF) -slice selection for serving users.

-Unstructured Data Storage Function (UDSF) -information retrieval and storage as unstructured data.

-5G-EIR -Permanent Equipment Identifier status checking.

-Network Data Analytics Function (NWDAF) -slice load level information.

-Charging Function (CHF) -online and o✏ine charging -Network Repository Function (NRF) -provides NF instances information such as function type, function ID, and Network Slice related Identifier(s).

-Unified Data Repository (UDR) -subscription and policy structured data retrieval and storage.

-SMS Function (SMSF) -SMS management and delivery over Non-Access-Stratum.

-Location Management Function (LMF) -measures user, downlink and uplink location.

-Security Edge Protection Proxy (SEPP) -non-transparent proxy responsible for filtering and policing between Public Land Mobile Networks' control planes.

-Binding Support Function (BSF) -supports binding information updates by NF service consumers.

Figure 3.1 summarizes the aforementioned core network evolution, from 3G to 5G. For an in-depth functionality description of each 5G function, one may refer to [START_REF] Jump | Julia for Mathematical Programming: Callbacks[END_REF][START_REF]Telecommunication management, Charging management, 5G system and charging service (Release 15)[END_REF][START_REF]Binding Support Management Service (Release 15)[END_REF].

5G core specificities

To better support network slicing, 3GPP has proposed more flexible, customized service-based network functions for 5G systems. With this new architecture, functions make use of a complete integrated interface that allows them to expose their capability to other authorized NFs without precluding the use of intermediate functions. This implies that all Control Plane functions have potential to directly communicate with each other by request/response and subscribe/notify application-level signaling. For this propose, each CP function is conceived with a set of NF services to be consumed by other functions. The interactions between CP functions are depicted in Fig. 3.2. In this example, A is a NF service consumer from B's point of view, which is, in turn, a NF service producer from A's perspective. Note that the same function may be service consumer and service producer at the same time, as illustrated by B. One function might consume services from di↵erent NF service producers and a function might also o↵er services for di↵erent NF service consumers. It is also important to notice that a NF service can provide and consume services to and from other NF services within the same function.

3GPP has also been providing some technical reports with a non exhaustive list of possible interactions between di↵erent functions and NF services [START_REF] Jump | Julia for Mathematical Programming: Callbacks[END_REF]54,[START_REF]G System; Unified Data Management Services (Release 16)[END_REF]. Some of those iterations are exemplified on Table 3.1, where UDM is taken as example with its non-exhaustive list of NF services [START_REF]G System; Unified Data Management Services (Release 16)[END_REF]. Note that UDM is able to o↵er a same service to di↵erent NF service consumers. In this example, UDM can subscribe data from AMF, SMF and SMSF. It is also important to notice that a same service might make di↵erent operations (e.g. get, subscribe, update, result confirmation) and they are made by request/response and subscribe/notify queries. To assure all these features, each NF service must be reusable, self-contained, and use individual schemes independently from all NF services present in the system. E↵ectively, being reusable eliminates redundancy by o↵ering total integration between all others NF services, within the same NF or not. In that way, each service is specific to a NF service producer and must be available to all potential NF service consumers. Additionally, all NF services are supposed to be self-contained and their operations must be done in their own contexts. Hence, NF services are allowed to operate only on their own internal storage, using their own software resources.

Auto-scaling and distribution

To better deal with tra c load fluctuation, auto-scaling becomes a powerful tool to alleviate network congestion due to the high data tra c load in certain periods. Additionally, distributing the flow intelligently is essential to ensure that each user has access to the demanded Communication Service with assured QoS. Such a distribution must be done by frameworks capable of detecting data tra c load fluctuation in a given slice in order to multiply instances of some critical functions. By knowing the high signaling sent and received by a sub-set of NFs within a slice, the orchestrator entity is responsible to provide and implement a tra c-aware algorithm capable of creating NF instances in critical moments (scale in) and distributing the tra c among them. Equally, in periods of low data tra c load, NFs copies in the same slice are removed (scale out) and a data tra c redistribution must be done. Following the 3GPP standards, physical resources can be saved and QoS is assured to users when NF instances are scaled out and in, respectively, once data tra c is properly distributed.

5G CORE SPECIFICITIES

In 5G, scalability is facilitated by using as much stateless functions as possible. Today's applications found in mobile networks are often stateful, which greatly increases the risk of failure and related management overhead. For the 5G core, most of its functions are meant to be stateless, facilitating scalability and decreasing the failure risk. To do this, these functions use other specific NFs that store states (e.g., network and users' data and information). For such management, 3GPP proposes UDM, UDSF, and UDR functions.

The user-plane case

Even though there is no precise reference to the User Plane domain, some assumptions based on 3GPP releases can be taken into account when designing a slice that o↵ers UPFs. Firstly, one possibility is to install a single instance of UPF with all the necessary NF services to a specific slice. This approach becomes necessary in slices dedicated to civil security; in this example, security and isolation constraints might imply that there must be only one node between access and data networks. However, for those scenarios where there are no such constraints, proposed 5G systems support interconnections between di↵erent UPFs by reference point named N9 [START_REF] Jump | Julia for Mathematical Programming: Callbacks[END_REF]. In this way, each UPF would be conceived with a sub-set of NF services and, unlike control plan data flow, user data is carried through an ordered chain of functions, each one responsible for a specific data processing. In the case of downlink data bu↵ering, for example, one UPF may act as the PDU Session Anchor while another UPF may be responsible for data encapsulation. Furthermore, N9 reference points can be established between di↵erent UPFs within the same Public Land Mobile Network (PLMN) or di↵erent PLMNs [START_REF] Jump | Julia for Mathematical Programming: Callbacks[END_REF] and, consequently, between di↵erent slices.

Functional splitting in the radio access network

Flexible Radio Access Network splitting [START_REF] Chabbouh | Cloud RAN architecture model based upon flexible RAN functionalities split for 5G networks[END_REF] is a technique meant to increase network e ciency leveraging NFV flexibility. In 1G and 2G RANs, all entities responsible for radio and baseband processing were distributed and integrated into each base station. To minimize costs and facilitate network deployment, it was proposed to split the base station into Remote Radio Unit (RRU, also called Remote Radio Head and Radio Unit) and Baseband Unit (BBU) (also called Data Unit). In this context, the RRU is responsible for Physical Layer functionalities, while the BBU is responsible for Data Link Layer functionalities [START_REF]Study on new radio access technology[END_REF]; the distance between these two entities could be up to 40 The bitrates are calculated as in [START_REF] Larsen | A survey of the functional splits proposed for 5G mobile crosshaul networks[END_REF] for a scenario using 100 MHz bandwidth and 32 antenna ports, while the maximum accepted one-way latency through FH is proposed by 3GPP [START_REF]Study on new radio access technology[END_REF]. Note first that the highest bitrates and lowest latency are imposed by option 8. However, one of the advantages of choosing this split would be in reducing the number of NFs throughout the access network, as they would be installed centrally and shared by di↵erent DUs. Contrarily, option 1 requests low bitrates and admits higher latency; the disadvantage of this option is that almost all NFs would be installed locally -this scenario demands higher computational power on each DU, which could be impractical given the number of expected DUs in mobile systems. It is also important to point out the di↵erence between downlink (DL) and uplink (UP) bitrates, due to physical layer operations (e.g., transformations between transport blocks and in-phase and quadrature symbols in each direction of the data flow). SDN and NFV technologies can be used together with C-RAN to o↵er flexibility to split RAN slice subnets [START_REF]Architecture enhancements for control and user plane separation of EPC nodes (Release 14)[END_REF][START_REF]Study on new radio access technology[END_REF]. To this propose, two classes of RAN functions are proposed by [START_REF]Mobile and wireless communications Enablers for the Twenty-twenty Information Society[END_REF]: asynchronous to either be implemented as dedicated machines or installed on a path that assures low latency and high bandwidth. According to [START_REF] Marsch | 5g radio access network architecture: Design guidelines and key considerations[END_REF], strict timing dependency between protocol layers must be avoided, using instead asynchronous NFs as much as possible to grant more flexibility to RAN slicing.

Being consistent with [START_REF]Architecture enhancements for control and user plane separation of EPC nodes (Release 14)[END_REF][START_REF]Study on new radio access technology[END_REF][START_REF] Marsch | 5g radio access network architecture: Design guidelines and key considerations[END_REF], we incorporate flexible RAN splitting in order to design end-to-end network slices. This approach can better deal with the heterogeneous requirements of each NS request while decreasing the redundancy in the network, that is, minimizing the number of virtual AN-based functions installed throughout the physical network. [START_REF] Maeder | Towards a flexible functional split for cloud-ran networks[END_REF][START_REF] Wang | Centralize or distribute? a techno-economic study to design a low-cost cloud radio access network[END_REF][START_REF] Chabbouh | Cloud RAN architecture model based upon flexible RAN functionalities split for 5G networks[END_REF] address the challenges of flexible functional split schemes to optimize the allocation of physical and virtual resources. [START_REF] Chabbouh | Cloud RAN architecture model based upon flexible RAN functionalities split for 5G networks[END_REF], for example,

proposes a new architecture that introduces a flexible split of RAN functionalities between the Cloud-RRH, an edge cloud, and the central cloud. [START_REF] Wang | Centralize or distribute? a techno-economic study to design a low-cost cloud radio access network[END_REF], in turn, analyze the technical features of the network in order to find the optimal split for di↵erent scenarios; the authors considered the configuration of the base stations, the fiber ownership, and the data transmission direction. They demonstrated that a lower total cost of ownership can be achieved with optimal functional split compared to classical radio access networks. The required backhaul capacities for uplink tra c in terms of minimum bandwidth and maximum latency for di↵erent split options are analyzed in [START_REF] Maeder | Towards a flexible functional split for cloud-ran networks[END_REF].

Even though there are several works in the literature addressing functional split mode selection and network slicing problems with NF sharing and NF scaling, no attention has been given to jointly address the complete problem in order to design end-to-end network slices including functional splitting for the radio access functions and di↵erent schemes for dimensioning and sharing NFs. Source: [START_REF] Asadi | A survey on device-to-device communication in cellular networks[END_REF] 3

.3 Device-to-device communication

In new generation access networks, mobile User Equipment will be able to host functions that give them new abilities such as sharing connectivity, capacity, and CPU resources with other UEs, regardless of the ongoing traditional communications. The 5G wireless technology, along with the evolution of mobile users' behavior and needs, will make the current scheme of communication (UE to Base Station) no longer optimal in terms of radio resource utilization for some cases. The Device-to-Device (D2D) communication mode is one of the new approaches presented as a promising alternative to traditional communication in cellular networks. D2D communication is defined as direct communication between two mobile or fixed user devices, without traversing the Base Station (BS) [START_REF] Asadi | A survey on device-to-device communication in cellular networks[END_REF]. This technology allows to reuse radio resources and to decrease the end-to-end latency of local communications. Then, D2D

would allow a set of UEs geographically close to each other to establish direct D2D communications, or span multiple links (multi-hop D2D communications), to access a given service (e.g. video streaming or gaming) while ensuring the required service quality. Outband D2D, where coordination between radio interfaces is controlled by the users.

One of the first works proposing the use of D2D communication was published in 2000 [START_REF] Lin | Multihop cellular: A new architecture for wireless communications[END_REF]. Soon afterward, several researchers turned their attention to this promising technology and looked for effective methods to improve its use. Both Inband D2D and Outband D2D are studied since then, with more attention to the former. However, several authors suggest that the main advantages of Outband D2D are related to the absence of interference between cellular and D2D users. In addition, there is no need to dedicate cellular resources to the D2D spectrum as in the Overlay Inband D2D approach. Hence, resource allocation becomes easier because the scheduler does not require to take the frequency-time matrix and location of the users into account. In addition, simultaneous D2D and cellular communication are feasible. However, according to [START_REF] Asadi | A survey on device-to-device communication in cellular networks[END_REF][START_REF] Fodor | Design aspects of network assisted device-to-device communications[END_REF] main disadvantages related to Outband D2D commutation are:

-Interference in unlicensed spectrum is not in the control of the BS;

-Only cellular devices with two radio interfaces (e.g., LTE and WiFi) can use Outband D2D communications;

-The e cient power management between two wireless interfaces is crucial, otherwise, the power consumption of the device can increase; and

-Packets (at least the headers) need to be decoded and encoded because the protocols employed by di↵erent radio interfaces are not the same.

On the other hand, according to the authors in [START_REF] Asadi | A survey on device-to-device communication in cellular networks[END_REF][START_REF] Fodor | Design aspects of network assisted device-to-device communications[END_REF], the main advantages and problems related to Underlay Inband D2D are:

-Spectrum e ciency: With the use of D2D we can improve the use of the cellular spectrum very e↵ectively. This can be done by using interference reduction techniques between D2D and classical cellular communication, or by developing high interference recognition applications to avoid the use of problematic frequencies in a certain region and time.

-Power e ciency: In several studies, it was observed that power e ciency can be improved with D2D technology. One of the most used techniques is the dynamic choice between cellular or

DEVICE-TO-DEVICE COMMUNICATION

D2D as a communication mode.

-Performance with QoS/Power Constraints: Improving the performance of D2D-enabled cellular systems with QoS/power constraints usually require advanced techniques such as stochastic optimization, nonlinear programming, and integer optimization.

However, Overlayng Inband D2D eliminates the concern about the interference between the two types of communication, since they do not share the same spectral range. This approach considerably reduces the number of resources to promote each part, and may promote an important waste of them.

BS-assisted scheduling [START_REF] Zhou | Intracluster device-to-device relay algorithm with optimal resource utilization[END_REF] and D2D power control [START_REF] Li | Device-to-device (d2d) communication in mu-mimo cellular networks[END_REF], techniques were proposed to reduce D2D interference. Another technique is proposed by the authors in [START_REF] Fodor | Design aspects of network assisted device-to-device communications[END_REF]. They propose to use the Base Station as a relay (backup re-transmitter) for the D2D transmission or to use multiple D2D users as the relays (re-transmitters) for multi-casting. According to the authors, both methods have low complexity which makes them practical for real-world scenarios.

Even with important works using Controled Outbound D2D [START_REF] Golrezaei | Base-station assisted deviceto-device communications for high-throughput wireless video networks[END_REF][START_REF] Golrezaei | Device-to-device collaboration through distributed storage[END_REF][START_REF] Asadi | Wifi direct and lte d2d in action[END_REF][START_REF] Ji | Wireless device-to-device caching networks: Basic principles and system performance[END_REF][START_REF] Cai | Exploiting double opportunities for deadline based content propagation in wireless networks[END_REF], Autonomous

Outband D2D [START_REF] Wang | Increasing opportunistic gain in small cells through base station-driven tra c spreading[END_REF][START_REF] Wang | Recouping opportunistic gain in dense base station layouts through energy-aware user cooperation[END_REF], and Overlayng Inband D2D [START_REF] Zhou | Intracluster device-to-device relay algorithm with optimal resource utilization[END_REF][START_REF] Li | Device-to-device (d2d) communication in mu-mimo cellular networks[END_REF][START_REF] Fodor | Design aspects of network assisted device-to-device communications[END_REF], most of works were developed using Underlay Inband D2D.

In [START_REF] Yu | Resource sharing optimization for device-to-device communication underlaying cellular networks[END_REF], Underlay Inband D2D was applied in both non-orthogonal and orthogonal resource sharing modes. In this work, the authors showed how to find a sub-set of viable solutions to ensure the optimal solution for the non-orthogonal resource sharing technique. They have shown that their approach provides gain over pathloss-based selection mode. Due to the non-convex di culty found in optimization problems in this context, authors in [START_REF] Wang | Resource sharing of underlaying device-to-device and uplink cellular communications[END_REF] proposed two sub-optimal strategies that have a smaller complexity, facilitating their resolution. In such a work, authors used uplinks in Underlaying Inband D2D technique to optimize only the transmission power of the D2D communications, fixing in advance the transmission powers of the classic colleges that use base stations.

Authors in [START_REF] Chae | Radio resource allocation scheme for deviceto-device communication in cellular networks using fractional frequency reuse[END_REF] propose dividing each cell into inner and outer regions and allocating di↵erent frequency bands for the communications regarding the position of the users. The authors present a fractional frequency reuse (FFR) approach to minimize interference between cellular communications and D2D. Following the approach depicted in Figure 3.6, authors in [START_REF] Chae | Radio resource allocation scheme for deviceto-device communication in cellular networks using fractional frequency reuse[END_REF] showed that D2D can significantly improve the total throughput of the cellular network compared to random allocation schemes.

Authors in [START_REF] Chae | Radio resource allocation scheme for deviceto-device communication in cellular networks using fractional frequency reuse[END_REF] were able to improve the spatial-spectral e ciency in the network using the inter-cell interference coordination (ICIC) technique, which is managed by the base stations. Finally, authors in [START_REF] Wang | Distance-constrained resource-sharing criteria for device-to-device communications underlaying cellular networks[END_REF] propose distance-constrained resource-sharing criteria as select mode technique, controlling the interference by keeping a minimum distance between communications that use the same frequency. Numerical results have shown the e↵ectiveness of this approach to significantly reduce the interference caused by D2D active links.

5G system mapping requirements

The 3GPP specifications [START_REF] Jump | Julia for Mathematical Programming: Callbacks[END_REF][START_REF] Ford | maximal flow through a network[END_REF][START_REF]Architecture enhancements for control and user plane separation of EPC nodes (Release 14)[END_REF] present the di↵erent entities appearing in 5G systems; as we describe in [1], they are: User Equipment (UE), Communication Service (CS), Network Slice (NS), Network Slice Subnet (NSS), Network Function (NF), NF Service (NFS).

Fig. 3.7 depicts the relationships between these entities. A UE can be a smartphone, a robot, or even an autonomous car, that might be connected to several CSs; e.g., a car connected to an Autonomous Car Service while broadcasting movies and music from Streaming Services to its passengers.

To better deal with heterogeneous technical constraints of each service, each CS might run on one or more customized NSs. Additionally, each NS might be composed of one or more NSSs, which might also be composed of lower-layer NSSs. A simple example of this scenario is given by considering an NS We can distinguish five mapping levels for creating a complete virtual 5G environment, each one with its characteristics and technical complexities to be implemented.

Mapping NF services into network functions

The first mapping is the most technical one. At this level, the di culty lies in how to program each function so that it behaves exactly as expected. As already discussed, each function is conceived with a customized sub-set of NF services that keeps a slice operational and e cient. The di culty related to this mapping is imposed by the need of minimizing the resource allocation for each function.

5G SYSTEM MAPPING REQUIREMENTS

Intuitively, the greater is a sub-set of NF services within a function, the greater is the number of physical resources that must be provided to install it. Clearly, an important work must be done on this level to find the right sub-set of NF services for each function and each use case, assuring the operability and e ciency of each CS.

Mapping network functions into slices and slice subnets

Mapping functions into slices is another technical problem. In this mapping, each NF has its own minimal physical capacity request (e.g. CPU, RAM, storage) as well as its capability (e.g. package treatment rate). The mapping at this level must also take into account the connection between each possible pair of functions that must be linked, as well as the required capacity and processing rate on each of those virtual links. At this level, the orchestrator entity is already aware of the sub-set of NF services within each function. As a result, mapping functions into slices o↵ers to the orchestrator entity a catalog of well-defined slice templates to specific and recurrent CSs. The problem for this mapping level is how to decide which function must be present in each slice and how to predict the quantity of each NF instance within a slice to better deal with the expected data rate throughout the system. It is important to mention that this level also refers to the mapping of functions into slice subnets, so creating NSSIs.

Mapping slices subnet into slices

After creating a slice subnet catalog as mentioned in the previous mapping level, the orchestrator entity might decide to create NSIs from well-defined slice subnet templates. This may be the case where a core NSI is created from UP and CP slices, combined. Hence, from 3GPP's point of view, those two last NSs are seen as slice subnet and the whole core as a slice. Notably, to do this type of mapping, well-defined sets of slice subnet templates must be available to guarantee the deployment of a whole NSI.

Mapping slices into communication services

This fourth level mapping is less technical than the previous ones. It takes advantage that all slice templates are already cataloged and ready to be deployed. According to its heterogeneous needs and expected data rate throughout the slice, each CS has a subset of possible slice templates to be mapped

5G SYSTEM MAPPING REQUIREMENTS

to. In this context, one may use matching techniques to better identify which templates are the most appropriated to a given set of CSs. It is worth noting that this mapping level can also be applied when slices are already deployed. In this context, each CS request might be mapped to an active virtual network.

Mapping communication services into user equipment

The mapping levels formerly described are related to the first phase of the life cycle of a slice [START_REF] Ford | maximal flow through a network[END_REF].

This phase, called Preparation, deals with the design of each previous mapping level, as well as the pre-provisioning and network environment preparation. The second phase consists of installing all slices on top of a physical network and activating them. Then, a mapping of Communication Services into UEs must be done as soon as a new request arrives. Next, in the Run-time phase, all slices are already activated and each UE must be connected to the right CS. More technically, this mapping is essentially a mapping of UE into the right NSI. This is done after a registration procedure by the first AMF receiving the connection request. This function then interacts with NSSF. Based on the orchestrator's policy rules, NSSF is responsible to direct each UE to the right Communication Service.

Hence, this last mapping level is essentially concentrated on NSSF, which must be connected to all AMF of other slices o↵ered by CS Providers.

Clearly, a higher level of mapping can only be done if all lower ones are already concluded, creating a strong dependency between them. Additionally, each level in this nested arrangement has its own complexity, and choosing the right mapping to o↵er a CS request is crucial. Hence, a trade-o↵ between flexibility and readiness is imposed. Deploying Communication Services from the first level gives more flexibility to adapt a virtual environment to a new 5G CS with specific and unexpected technical constraints. However, this might be a very arduous work to be done for every single request. Along these lines, for those highly expected classes of CSs with well-known technical constraints, creating templates to be available to a higher mapping level speeds up the procedure to build a virtualized 5G CS using network slicing techniques.

We have to stress that the decomposition of NSs into NSSs and of NFs into NFSs is, on the one hand, motivated by scalability and e ciency reasons and, on the other hand, requires the network slice design process to take into consideration continuity constraints. Indeed, one NS can be geographically deployed in a scalable manner thanks to the segmentation of a slice into multiple NSSs; and the 3.5. SHARING POLICIES overall computing demand can be decreased by allocating resources to NF micro-services rather than to macro NF units. Moreover, depending on techno-economic and network management policies, continuity constraints on the decomposition may be needed; more precisely, the slice provider might decide whether all NSSs belonging to the same higher level NS should undergo the same functional split setting in the Radio Access Network (RAN).

Sharing policies

The mapping problem rising in 5G described above appears as a novel multi-level embedding of network nodes. Jointly, addressing each mapping strategy involves a crucial point: how will each entity of the same level interact with the higher level instances? Isolation is a key aspect for network slicing and dedicated functions, for example, might be necessary to ensure that each slice operates independently, preventing the incorrect balance of resources between the serving slices. Additionally, security is another extremely important point in virtual environments. To ensure security and data routing control, partially or completely isolated slices with dedicated functions might be implemented.

On the other hand, sharing a function is an interesting strategy to simplify virtual environment implementation and to reduce redundancies throughout the network. Due to the high programmability of NFs, some of them can be installed on top of physical resources to be shared by a set of slices.

In addition, following 3GPP standards for 5GC, some NF instances must be common and shared between di↵erent slices. This imposition can be interestingly exemplified with NSSF. This function is It is important to keep in mind that, as functions, an NSSI can also be shared by two or more NSIs, or it might still be entirely dedicated to a slice. Isolation is a key aspect for network slicing and dedicated NFs might be necessary to ensure that each NS operates independently. This approach is important for preventing the incorrect balance of resources between the served NSs. Additionally, security is another crucial point in virtual environments. To ensure security and data routing control, partially or completely isolated network slices with dedicated NFs might be implemented. Hence, isolation constraints might be applied on the virtual layer; NFs installed in the same physical node must be dedicated to a virtual network serving a specific client, thus cannot be shared by two or more NSs. On the other hand, sharing NFs among di↵erent NSs can be an interesting strategy to simplify the virtual environment implementation and to reduce redundancies throughout the network [START_REF] Ford | maximal flow through a network[END_REF]. We assume that an NF can treat data from two or more NSs if and only if they have an a nity for each other. By a nity, we mean allowing a network slice to share one or more NFs with another NS. It is important to mention that an NS request might impose isolation constraints only on a specific subset of network functions that cannot be shared with a specific subset of NSs; this might be the case for critical NFs or network slices belonging to the di↵erent tenants, for example.

We depict in Fig. 3.9 six possible NF sharing policies that, based on our analysis, are possible as of 3GPP specifications; in this illustration, a DP block can refer to data-plane functions for both access and core segments. They are as follows:

3.5. SHARING POLICIES 1. Flat Sharing: all CSs share the same virtual network; it can be an interesting strategy when di↵erent slices have no isolation constraints and show similar technical constraints in terms of latency and availability.

2. Hard Isolation: the isolation is complete, each CS has its own virtual network.

3. Shared Control-Plane: slices share the same Control-Plane (CP) while having their own and dedicated user Data-Planes (D-DPs); it may be a solution for NSs requiring low end-to-end latency, and in this scenario, DP equipment should be deployed as close as possible to UEs, which has, therefore, an impact on the level of functional splitting. According to 3GPP specifications, these settings are in practice adaptable to multiple CSs. In addition, regarding the orchestration complexity inherent to each sharing policy (e.g., security and route control), other configurations might be proposed to guarantee Service Level Agreements.

Figure 3.9 -NF sharing policies.

3.6. CHALLENGES

Challenges

3GPP has been proposing a series of evolution in both Access and Core Networks to better serve the upcoming 5G network. We summarized this work in this chapter with a particular view on function decomposition and related mappings, which seems to call for even more integration of SDN, NFV, and Network Slicing subsystems than what was commonly anticipated. Indeed, new challenges are imposed to operators to ensure that future virtualized networks are successfully operational.

One of the main challenges is related to the first level of mapping. Managing the granularity of a function is a crucial point to minimize the use of physical resources. As a consequence, an intelligent entity is needed to provide the exact sub-set of NF services.What level this granularity is managed and which entity is responsible for it remain both open questions. In other words, will the dynamic creation of customized NFs be in charge of the NFs themselves, the orchestration entity or there will be a new NF dedicated to this end? A similar problem was addressed by [START_REF] Chowdhury | Re-architecting nfv ecosystem with microservices: State of the art and research challenges[END_REF]. In this work, the authors propose a flexible service composition in order to minimize the redundant functionality found in instances of di↵erent service functions (e.g. application and edge firewalls, load balancer, and proxy) throughout the virtual architecture. For this purpose, they apply the microservice concept on service function chains for re-architecting the NFV ecosystem. This interesting approach is directly related to the concept of NF services introduced by 3GPP, however, there is no study proposing such a technique in functions related to 5G Core Network. Hence, this remains an open problem to be addressed.

Furthermore, for each new and uncontemplated use case, new mappings at each level must be performed, causing higher levels to depend intrinsically on the lower levels. In other words, to map slice templates to CSs, for example, a complete function mapping work into slice must already be completed. Clearly, mapping strategies have a strong impact on slice deployment and how to model it. First, an intelligent framework to correctly distribute the flow of data throughout slices must be provided. This is due to the proposed scalability for critical functions to handle highly dynamic data rates. In this context, defining the number of instances for each function within a slice is not a trivial work. Such a framework must be aware of the current state of the network to decide the exact time of scaling up and down some critical NF instances and to redistribute the flow among them in an intelligent manner. [START_REF] Alawe | On the scalability of 5g core network: the amf case[END_REF] presents an approach to address this problem, however, the authors apply such framework only on one critical network function and do not give any instruction on how it could 3.6. CHALLENGES be implemented on two or more core functions at the same time. In fact, proposing such a global framework is not a trivial task and remains an open problem to be addressed.

All these challenges must be overcome wisely and e↵ectively, as the state of the system can change every second. In legacy technologies, such as 3G and 4G, the entire network system was designed for approximately ten years of use, with small variations and slow evolutions over the period. Contrarily, the 5G system is meant to be extremely flexible and still be able to o↵er a customized and complete virtual network in minutes for each Communication Service request. In this way, network designers and engineers have a laborious road to develop and apply techniques, algorithms, models, and approaches that guarantee the high e ciency in translating Communication Service demands into slices, doing all the necessary mappings, allocating physical and virtual resources, and activating, monitoring, and evolving each slice on 5G system.

Chapter 4

Device-to-device communication in radio access networks In future 5G networks, mobile User Equipment (UEs) will be able to host functions that give them new abilities such as sharing connectivity, capacity, and CPU resources with other UEs, regardless of the ongoing traditional communications. The 5G wireless technology, along with the evolution of mobile users' behavior and needs, will make the current scheme of communication (UE to Base Station) no longer optimal in terms of radio resource utilization. The Device-to-Device (D2D) communication mode is one of the new approaches presented as a promising alternative to traditional communication in cellular networks. D2D communication is defined as a direct communication between two mobile or fixed user devices, without traversing the Base Station (BS) [START_REF] Asadi | A survey on device-to-device communication in cellular networks[END_REF]. This technology allows to reuse 4.1. PROBLEM STATEMENT radio resources and to decrease the end-to-end latency of local communications. Then, D2D would allow a set of UEs geographically close to each other to establish direct D2D communications, or span multiple links (multi-hop D2D communications), to access a given service (e.g. video streaming or gaming) while ensuring the required service quality.

A domain is defined as the set of UEs and BSs that are used to establish mobile communications (D2D or cellular) related to a specific service. The communication is either direct or uses multiple links (D2D or via the BS). Two UEs can then communicate through cellular links, using the BS or D2D links, and both technologies can coexist within the same mobile network. In any case, radio resources should be allocated to every active link involved in a communication, and the SINR (Signalto-Interference-plus-Noise Ratio) level required by the service should be ensured.

In this chapter, we formally define the Domain Creation Problem and we propose a node-arc (compact) ILP formulation to model it. We present some strategies to enhance the linear relaxation of the formulation along with two classes of valid inequalities. Our results are embedded within a branch-and-cut algorithm to solve the problem. Numerical experiments are made on instances generated thanks to realistic parameters of Orange mobile networks 1 .

Problem statement

We consider a mobile network composed of a set of devices (UEs), a set of antennas (BS), and a set of services eligible to D2D communications, with their associated tra c matrices. These tra c matrices are in the form of data volume to be exchanged between pairs of devices. The involved devices can communicate through one or several links, either using D2D or cellular communication (via the BS). A non-negative weight, corresponding to the SINR, is associated with each link. It is a measure of the quality of the communication that could be established using this link. Every service requires a minimal quality threshold in terms of SINR and available resources (hardware capacity for the devices, radio resources for the links) to be successfully established. Once these conditions are met, the services are delivered through the di↵erent types of resources allocated to both the devices and the links. The figure on the right side is the Video streaming domain, where just one demand uses the BS. Note that, using the legacy approach, all demands must pass through the BS, using one uplink (from UE origin to BS) and one downlink (from the BS to UE destination) for each demand. Since all active links share at least one arc extremity (BS), the solution would require all the available resources (a di↵erent one for each active link) to avoid interference. Thus, using D2D communications allow here to save 50% of radio resources compared to a "fully cellular" solution.

Related works

The problem of assigning radio resources to transmission links is studied in [START_REF] Aardal | A branch-and-cut algorithm for the frequency assignment problem[END_REF] and [START_REF]Models and solution techniques for frequency assignment problems[END_REF] under the denomination of Frequency Assignment Problem (FAP). In [START_REF] Aardal | A branch-and-cut algorithm for the frequency assignment problem[END_REF], the authors give an ILP formulation for the problem and propose a branch-and-cut algorithm to solve it. The work in [START_REF]Models and solution techniques for frequency assignment problems[END_REF] presents sev-

A MATHEMATICAL FORMULATION FOR THE DCP eral variants of FAP and discusses existing and original optimization (including exact and heuristic)

approaches to solve them. The routing and resource allocation aspects are combined in the so-called Routing and Wavelength Assignment (RWA) problem (see [START_REF] Jaumard | ILP Formulations for the Routing and Wavelength Assignment Problem: Symmetric Systems[END_REF] and [START_REF] Ozdaglar | Routing and wavelength assignment in optical networks[END_REF] for instance) which arises in Optical Networks. The DCP di↵ers from the above-cited problems in that tra c demands are unsplittable (each demand has to be sent along a unique path using D2D or cellular links), several types of capacities on the devices are considered, and radio resources re-use is submitted to distance constraints to avoid radio interference. [START_REF] Zulhasnine | E cient resource allocation for device-to-device communication underlaying lte network[END_REF] propose a greedy heuristic as an alternative to allocate resources to active links using D2D communication. The proposed heuristic is divided into two phases, each one responsible for the allocation of uplinks and downlinks. After several tests in realistic scenarios, the authors showed that the greedy heuristic improves the total throughput significantly reducing the interference between classic and D2D communications. To maximize the number of active links respecting minimum quality requirements in wireless networks, authors in [START_REF] Capone | A new computational approach for maximum link activation in wireless networks under the sinr model[END_REF] proposed a new integer programming algorithm based on an e↵ective representation of the SINR constraints which is inspired by knapsack problems using lifting procedure.

A mathematical formulation for the DCP

In this section, we propose a compact ILP formulation for the DCP followed by some valid inequalities to be used in a branch-and-cut algorithm.

Notations and formulation

The three types of binary variables are:

• x k
er , e oe A, k oe K, r oe R that takes the value 1 if the arc e is used by the demand k and assigned with the resource r, 0 otherwise.

• y k i , i oe V fi U , k oe K, that
takes the value 1 if the node i is used by the demand k, 0 otherwise.

• z r , r oe R that takes the value 1 if the resource r oe R is assigned with at least one arc, 0 otherwise.

Then, the DCP can be formulated as:

min ÿ koeK ÿ eoeA ÿ roeR µ s k e x k er + ÿ roeR Âz r (4.1) 4.3. A MATHEMATICAL FORMULATION FOR THE DCP s.t. ÿ eoe" ≠ (u) ÿ roeR x k er ≠ ÿ eoe" + (u) ÿ roeR x k er = Y _ ] _ [ 1, if u = d k , ≠1, if u = o k , 0, otherwise, 'k oe K, 'u oe U fi V (4.2) x k er -k AE SIN R e ' k oe K, ' e oe A, ' r oe R (4.3) ÿ koeK\T (i)
y k i a s k m AE c i m ' i oe V, ' m oe C d (4.4) 2x k er ≠ y k i ≠ y k j AE 0 'k oe K, 'r oe R'(i, j) = e oe A (4.5) x k er + x k Õ fr AE z r 'r oe R, 'k, k Õ oe K, 'e oe A, 'f oe D(e) (4.6)
x k er oe {0, 1} 'k oe K, 'e oe A, 'r oe R (4.7)

y k i oe {0, 1} 'k oe K, 'i oe V (4.8) z r oe {0, 1} 'r oe R (4.9)
This formulation has a polynomial number of variables and constraints. The objective (4.1) is to minimize the total costs composed of non-negative routing and radio resource utilization costs. The first set of inequalities (4.2) are the flow conservation constraints. They ensure that each demand is routed along a unique path between its origin node and its destination node. Note that such a routing path can either span arcs corresponding to D2D links or use a node of U corresponding to some BS. Inequalities (4.3) guarantee that a demand for a given service is routed along edges whose SINR satisfies the quality threshold required by this service. (4.4) express the capacity constraints in every node for the di↵erent types of hardware resources, with T (i) being the set of demands k oe K that have i oe V as origin or destination. These capacity constraints are needed only on intermediate nodes, that is, the nodes that are not the origin nor the destination of a given demand k oe K. Inequalities (4.5)

are linking constraints and inequalities (4.6) guarantee that the same radio resource is not assigned to di↵erent edges unless they are distant enough, where D(e) is a set of arcs that are close to a given arc e oe A. Note that, as the objective is to minimize the resources, in any optimal solution one radio resource at most will be allocated to the same arc for a given demand. Finally, (4.7)-(4.9) are the integrality constraints.

The ILP formulation (4.1)-(4.9) can be strengthened by replacing inequalities (4.3) by:

x k er 6 Â SIN R e -k Ê, 'k oe K, e oe A,

Valid inequalities

We introduce now two classes of inequalities valid for the DCP.

Clique-based inequalities

Given an instance of DCP, we define the conflict graph associated with a node u oe V as follows.

For each capacity type m oe C d , let H m u = (V m u , E m u ) be the undirected graph obtained from the set of demands K as follows. A node v k in V m u is associated with every demand k oe K and there exists an edge are allocated the same resource r oe R in a solution, then it cannot be feasible for the DCP.

v k v l oe E m u between two nodes v k , v l of V m u if a s k m + a s l m > c u m . In
Note that similar inequalities are used in [START_REF] Aardal | A branch-and-cut algorithm for the frequency assignment problem[END_REF] and [START_REF]Models and solution techniques for frequency assignment problems[END_REF] for the Frequency Assignment Problem.

In what follows, we describe our branch-and-cut framework and show some computational results

to assess the e ciency of our cuts.

A branch-and-cut algorithm for the DCP

We developed a branch-and-cut algorithm for the DCP based on two heuristic procedures to generate dynamically inequalities (4.12) and (4.13). Both separation routines rely on a greedy algorithm introduced in [START_REF] Nemhauser | A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing[END_REF] for the Independent Set problem, that finds a clique in the conflict graph (respectively the interference graph) with appropriate weights on the nodes. We then add the corresponding violated clique-based (respectively strengthened neighborhood) inequalities, if any, to the current LP.

Both classes of valid inequalities are separated throughout the branch-and-cut tree and several inequalities may be added at each iteration of the algorithm. We further propose a two-phase heuristic, obtained by decomposing the problem into routing and radio resource allocation sub-problems. To solve the routing sub-problem, we propose two methods: an LP-based heuristic from the linear relaxation of a compact formulation, and a non-compact formulation obtained by generating a subset of relevant paths. Then, the allocation sub-problem is transformed into a vertex coloring problem that is solved heuristically by an improved greedy algorithm. This greedy algorithm is compared to a dual bound given by the exact solution of the associated Max-Clique Problem. In what follows, we present in detail each of the proposed approaches.

Routing sub-problem

We propose two formulations for the routing sub-problem: a compact formulation obtained by relaxing the resource assignment constraints (4.6) from (4.1)-(4.9), and a path reformulation.

Compact formulation

This formulation is the compact formulation obtained by relaxing the resource allocation constraints (4.6) from the formulation (4.1)-(4.9). The returned solution is a set of elementary paths for each request, respecting the capacities of the nodes along the paths. Two kinds of binary variables remains in the formulation : x k e that takes value 1 if the link e oe A is used by the request k oe K and the variables y i k . The objective is to minimize the total cost of active links:

min ÿ koeK ÿ eoeE µ s k e x k e (4.14)

A 2-PHASE HEURISTIC FOR THE DCP

Solving approach: The linear relaxation of this formulation is strengthened replacing (4.5) by:

x k e ≠ y k i AE 0 ' k oe K, ' (i, j) = e oe E, (4.15)
x k e ≠ y k j AE 0 ' k oe K, ' (i, j) = e oe E. (4.16) and adding the following inequalities :

y k i (a s k m ≠ c i m ) AE 0 ' i oe V, ' m oe C d , ' k oe K\T (i). (4.17)
The linear relaxation of this strengthened sub-problem is then solved and a heuristic procedure is used to get a feasible integer solution. This approach is summarized in Algorithm 1.

First, the linear relaxation is solved to optimality. Then, variables having an integer optimal value are fixed by updating the right-hand side of the constraints (4.5) in step 5. Finally, this residual ILP formulation is solved to optimality, giving rise to an integer solution for the whole problem. Step 11 is the rounding procedure on the solution found by step 1. This heuristic is particularly e cient for this problem since most of the optimal variable values of the linear relaxation are integers.

Path formulation

The second formulation is a path formulation. We assume that all feasible paths P k have been previously generated for each demand k. Thus, we define new binary variables x k p that take value 1 if the path p oe P k is used by the demand k oe K, 0 otherwise. The objective now is to minimize the sum of the active path weights:

min ÿ koeK ÿ poeP k µ s k p x k p (4.18)
where µ s k p is the cost of path p oe P k , defined as the sum of the weights on the arcs of p. Lete p , respectively " i p , be an indicator parameter with value 1 if the arc e, respectively the node i, is in the path p. The constraints of the path formulation are: Solving approach: This formulation, restricted to a subset of paths, is solved to optimality. The subsets of paths are generated by applying the algorithm proposed by Yen [START_REF] Yen | An algorithm for finding shortest routes from all source nodes to a given destination in general networks[END_REF]. This algorithm returns the K-shortest loopless paths for a graph with non-negative edge costs. It uses a shortest path algorithm as an intermediary to construct the whole solution. In this work, we use Dijkstra's algorithm [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF], which has a good performance and a polynomial complexity. Using Yen's algorithm gives a guarantee to generate all the feasible paths due to the characteristics of our use case: for each demand, once a path uses the base station we are sure that all the feasible D2D paths have already been generated, then the path generation is stopped. This feature is due to greater weights on BS arcs. The di↵erence between the weights of the BS links and the D2D ones plays an important role in the construction of the paths subsets: the greater this di↵erence is, the longer it could be to obtain all the paths that use only D2D communication. Finally, to reduce the size of the formulation, a pre-processing on the SINR constraints is operated before solving both routing formulations: only the valid SINR link constraints are kept in the formulation.

ÿ poeP k x k p = 1 ' k oe K, ( 4
ÿ koeK\T (i) ÿ poeP k " i p x k p a s k m AE c i m ' i oe V, ' m oe C d , ( 4

Resource allocation sub-problem

The resource allocation sub-problem consists in allocating the radio resources to each active link provided by the solution of the first sub-problem. For this purpose, let G a (V a , E a ) be a graph where each vertex in the set V a represents an active link, that is, a link used by at least one path of the routing problem solution (steps 2-5 in Algorithm 2). An edge e oe E a is associated with a pair of The proposed heuristic has as input the initial graph of the problem, the values of the routing solutions, and a criteria value that represents the minimum distance for a pair of links to have the same resource. This value was fixed to D = 100 meters to be representative of realistic use cases.

Hence, for dist() method, we calculate the distance between the opposite ends of the pair of links, that is, the origin of one with the destination of the other. The method returns zero for adjacent links.

Finally, to find the coloring of the graph G a (that is, allocate the resources to each active link) we use the Coloring() method which is the implementation of a classical greedy algorithm [START_REF] Matula | Graph coloring algorithms[END_REF] for the Vertex Coloring Problem.

It is well known that the performance of this greedy algorithm is sensitive to the order of choice of the next vertex to be colored. For this reason, we randomly generate a large number of orders and choose the one that returns the minimum amount of colors. A lower bound value for the optimal solution is given by solving the associated Max-clique problem. For this purpose, we use the method proposed by [START_REF] Depolli | Exact parallel maximum clique algorithm for general and protein graphs[END_REF], which is an exact approach using parallel programming.

COMPUTATIONAL RESULTS

Computational results

We now present the numerical experiments applying each of the proposed approaches to solve the DCP. We first discuss the e ciency of the branch-and-cut algorithm and the symmetry-breaking constraints. Then, we analyze the numerical simulations applying our 2-phase algorithm on di↵erent realistic instances.

Branch-and-cut and symmetry-breaking constraints

We present below some experiments obtained for a set of small instances containing 5 to 15 nodes and up to 7 demands. For these tests, each scenario contains only 1 antenna and 2 service domains.

For each instance, realistic data was provided by Orange, including the network topologies and SINR values. We implemented our approach in a C++ environment using ILO CPLEX 12.6 as the linear solver. Our tests were run on a Linux server with an Intel Xeon E5-2650 CPU. using strenghthened neighborhood inequalities (4.13) in addition to formulation (4.1)-(4.9), (iii) using clique-based inequalities (4.12) in addition to strengthened model and (iv) both cuts are used in the branch-and-cut. We can observe that the gap at root node is substantially reduced when adding cuts (the gap value decreases from 59.65% to 23.58% for instance U 5 D8 when using strenghthened neighborhood cuts) and so for the size of the branch-and-cut tree (for instance U 10 D5, we range from 1327 nodes without cuts to 84 nodes when both cuts are used). Overall, the strenghthened neighborhood cuts are more e cient in reinforcing the strengthened model.

2-phase heuristic

We present below some experiments obtained from applying the proposed 2-phase heuristic on a set of di↵erent instance sizes. We implemented our approaches in a C++ environment using ILO CPLEX 12.6 as the linear solver. Our tests were run on a Linux server with an Intel Xeon E5-2650 CPU. The solver's time limit was set to 7200 seconds (2 hours) and only one thread was provided to the branch-and-bound process.

Test setup

All instances were generated and o↵ered by the Mobile Access Design team from Orange Labs, in which each cell has a 500 meters radius and is based on the networks of the figure 4.3 and follow the following premises:

-The total number of UEs is evenly divided between the 7 core cells. -We set the link weight to:

-1.0 between each UEs pair in the central cell if the distance between them is less than 100 meters; -1.49 between a UE and the nearest base station; -0.9 between each pair of base stations;

-The origins of all requests are in the central cell;

-The requests are unique, that is, there is only one with the specific configuration (origin, destination, required service), and random values are generated for only three UE physical capacities (e.g., CPU, battery, and RAM).

-6 di↵erent service domains are available to be required.

As previously presented, the name of each instance refers to the number of users (U#), links (L#), and demands (D#).

Numerical results

We use this section to present and analyze the results obtained from the numerous tests performed with the instances presented in the previous section. Such tests have as main objective to analyze the performance of each approach of our 2-phase formulations in terms of execution time and quality of the solution obtained in each phase.

COMPUTATIONAL RESULTS

Routing sub-problem:

The numerical tests of the routing subproblem are summarized in table 4.3. The first column of the Compact Formulation part is the percentage of active variables that are not integers in the optimal LP solution. We note that it is always less than 6%. The second column is the gap between the solution found by the relaxation and the final solution found by the LP-based heuristic. The average gap is 2.30% with a standard deviation equals to 3.85%. Finally, the third column is the total run time in seconds (pre-processing, relaxed solution, and LP-based heuristic). In the second part of table 4.3, the pre-processing and solver run times of the path formulation are presented. The average number of paths generated in pre-processing is equal to 5.26 for each demand (with a standard deviation equals to 2.39). Most of the runtime of the compact formulation-based approach was spent in solving the linear relaxation of the problem. Given the very low number of fractional variables in the relaxed solution, the last IP on the residual formulation is quickly solved. It is also worth noticing that the pre-processing in path formulation is the most important step since it is responsible for most of the solving time for all instances. However, its performance is relatively better than for the compact formulation, being on average 1.30 times faster. It is important to mention that the gap between the two formulations was always less than 0.50%.

Resource allocation sub-problem: Table 4.4 shows the results for the resource allocation subproblem, where the Pre-processing column represents the time needed to transform the solution from the previous subproblem into a classic graph and find its max-clique. We can observe that even though they are extremely large graphs, the time needed to find the final solution is relatively short. This is due to the characteristics of the topology constructed from the assumptions and hypotheses previously presented. Generated graphs have an average density equals to 64.05% -standard deviation equals to 1.98%. Another important result emphasizes is that in all cases, we found the optimal solution, proven by the lower bound value previously calculated by the exact max-clique algorithm (last column).

Final solution: In order to analyze the quality of the global solution, we performed additional tests to compare the solutions found by our approach and those found by the original model (4.1)-(4.9). Due to the high complexity of the original model, we run tests with only small instances. Table 4.5 shows the time spent on each approach, as well as the solutions found. Regarding the results applying the proposed 2-phase heuristic, Runtime columns represent the total time spent by both pre-processing and solving steps one each approach. As seen in Table 4.5, our approach has a short time calculation and reached the global optimum in all instances in these simulations.

Summary

In this chapter, we studied the Domain Creation problem, that is a routing and resource assignment problem arising in future 5G networks. We proposed two algorithms: exact and heuristic, to solve it. The exact approach is based on a node-arc ILP formulation enhanced by two families of valid inequalities that are used within a branch-and-cut framework. The preliminary results show a significant impact of the cuts in strenghthening the LP relaxation and reducing the computation time.

We expect that adding further classes of cuts and performing an analysis to find out the specificities of di cult instances (regardless of their size) will allow to solve even larger instances. A natural question would be to consider a non-compact formulation, based on path variables and propose a column generation based algorithm to solve it. On an other hand, our experiments show that the heuristic approach performs well, even on large instances with up to 2100 devices and 1500 service requests on 7-cell networks. It would be interesting and most probably very powerful to use it as a primal heuristic to boost e ciency of an exact algorithm.

Chapter 5

The Network Slice Design problem Telecommunications network infrastructures evolved with 5G [START_REF]3rd Generation Partnership Project[END_REF] and the development of the 'network slice' as a novel virtualized infrastructure model. This technology now not only covers application-level slice abstraction as done with preliminary works on 'slicing', but also physical and switching layers virtualization, with di↵erent radio access and link communication technologies. This transition challenges slice network design since multiple resources and segments, historically managed independently from each other, are to be operated with continuity in networking and computing resource allocation and provisioning as a whole and unique service. In this context, di↵erent providers can be associated with di↵erent communication services running on the same physical network at the 5.1. PROBLEM STATEMENT AND NOTATIONS access, core, and application segments.

In this chapter, we formally define the Network Slice Design problem (NSDP) as a comprehensive network function dimensioning, placement, routing, and mapping framework that (i) takes into consideration the above mentioned new mapping dimensions and (ii) models the relationship between flexible radio access functional splitting, control-plane and data-plane function isolation, and core network function placement. We use the 3rd Generation Partnership Project (3GPP) [START_REF] Jump | Julia for Mathematical Programming: Callbacks[END_REF][START_REF] Ford | maximal flow through a network[END_REF][START_REF]Architecture enhancements for control and user plane separation of EPC nodes (Release 14)[END_REF] 5G as a reference system, knowing that the next generations shall support the same functional requirements in terms of function mapping, sharing, and placement.

Even though several works partially cover the network slice design problem [START_REF] Baumgartner | Optimisation models for robust and survivable network slice design: A comparative analysis[END_REF][START_REF] Tan | Analog coded softcast: A network slice design for multimedia broadcast/multicast[END_REF] and related sub-problems, such as functional split mode selection [START_REF] Maeder | Towards a flexible functional split for cloud-ran networks[END_REF][START_REF] Wang | Centralize or distribute? a techno-economic study to design a low-cost cloud radio access network[END_REF][START_REF] Chabbouh | Cloud RAN architecture model based upon flexible RAN functionalities split for 5G networks[END_REF], network slicing with VNF sharing [START_REF] Malandrino | Getting the most out of your vnfs: Flexible assignment of service priorities in 5G[END_REF][START_REF] Truong-Huu | Service chain embedding for diversified 5G slices with virtual network function sharing[END_REF][START_REF] Crippa | Resource sharing for a 5G multi-tenant and multi-service architecture[END_REF], and network slicing with VNF scaling [START_REF] Alawe | On the scalability of 5g core network: the amf case[END_REF][START_REF] Alawe | Smart scaling of the 5G core network: an rnn-based approach[END_REF][START_REF] Wang | Online learning-assisted vnf service chain scaling with network uncertainties[END_REF][START_REF] Fei | Adaptive VNF scaling and flow routing with proactive demand prediction[END_REF][START_REF] Zhang | Proactive VNF provisioning with multi-timescale cloud resources: Fusing online learning and online optimization[END_REF], no attention has been given to address jointly all aforementioned aspects in order to design network slices and understand the impact of mapping, sharing and split policies.

The overall objective of this chapter is thereby to introduce and study the Network Slice Design Problem in 5G systems. We first propose a Mixed-Integer Linear Programming (MILP) formulation for the problem including novel splitting, mapping and provisioning constraints described in the published 5G standards documents [START_REF]Architecture enhancements for control and user plane separation of EPC nodes (Release 14)[END_REF][START_REF] Ford | maximal flow through a network[END_REF][START_REF] Jump | Julia for Mathematical Programming: Callbacks[END_REF] and analyze its complexity1 .

Problem statement and notations

In this section, we introduce a set of necessary notations and we give a formal definition of the Network Slice Design Problem. Table 5.1 summarizes the notations.

Physical network

The physical layer is modeled by a directed graph denoted G = (V , A), where V is the set of nodes and A the set of arcs. The set V consists of three disjoint subsets denoted V du , V ac , and V ap and corresponding to di↵erent types of nodes, namely the distributed unities, aggregation/core servers, and application nodes, respectively. Each node u oe V is characterized by a set of available capacities

PROBLEM STATEMENT AND NOTATIONS Table 5.1 -Main notation: sets and parameters

Set Description

V Set of all nodes.

V du Set of all distributed units.

V ac

Set of all aggregation/core nodes.

V ap

Set of all applications server nodes.

A

Set of all arcs.

F

Set of all NFS types.

F d

Set of all data-plane NFS types.

F c

Set of all control-plane NFS types.

S

Set of all network slice requests.

F (s)

Set of all CP NFS pairs that must be connected in slice s.

G(s)

Set of all pairs of NFSs from di↵erent type sets that must be connected to each other in slice s.

K(s)

Set of all demands of slice request s.

O(s)

Set of origin nodes of all tra c demand from slice s.

N

Network function services

Let N denote the set of Network Functions (NF). Each NF n oe N is composed of one or several Network Function Services (NFS). The set of all NFS is noted F . We suppose that F is composed of a sub-set F c of control-plane NFSs, an ordered sub-set F d of data-plane NFSs and an auxiliary dummy function f 0 , so that F = F c fi F d fi {f 0 }. Every NFS f oe F requires a set of resources {c 1 f , . . . , c c f }, has a tra c processing capacity denoted cap(f ) and delivers an expected data rate b f . Moreover, we let b fg > 0 denote the total amount of tra c generated by two communicating NFSs f and g

PROBLEM STATEMENT AND NOTATIONS

and by d fg the maximum delay threshold between NFSs f and g. For each f oe F d , ⁄ f denotes a compression coe cient applied on the data-plane tra c of NFS f . We suppose that ⁄ f 0 = 1 and all the aforementioned parameters are supposed to be equal to 0 for the dummy NFS f 0 .

Network slice requests

We denote by S the set of network slice requests. Every request s oe S is associated with a binary parameters f that takes 1 (resp. 0) if at least one NFS of type f oe F is (resp. is not) required in the associated slice. Let F (s) = {(f, g) : (f oe F c ) • (g oe F c )} be the set of NFS types that must be connected. Additionally, we denote by G(s) = {(f, g) : (f oe F c ) ü (g oe F c )} the set of NFS pairs from di↵erent sub-sets of NFS types that must be connected. Hence, the control-plane required by a slice s is given by F (s) fi G(s). We denote by q st fg the binary parameter that takes value 1 if two NFS f, g oe F respectively required by slice s, t oe S can be packed together in the same NF, and 0 otherwise, representing then the so-called virtual layer isolation. Similarly, the physical layer isolation requirement is expressed by the binary parameter q st that takes value 1 if slice requests s, t oe S can share a common physical node, 0 otherwise. Each slice request s oe S is associated with a set K(s) of tra c demands to be routed on the physical layer. Each demand k oe K(s) is defined by a pair of origin-destination nodes (o k , t k ), an initial data rate b k sent by o k to t k and a maximum end-toend latency value d s , similar for all tra c demands in K(s). Finally, the expected number of users connected to slice s is denoted by ÷ s .

Problem statement

We define the Network Slice Design Problem as follows.

Definition 5.1.1. Given a directed graph G representing the physical network, a set of slice requests S, a set of tra c demands K(s) associated with each request s oe S, and a set F of NFS types, the NSDP consists in determining the number of NFSs to install for each s oe S, the size of NF hosting them as well as in deciding whether they are to be installed centrally or distributed (e.i., selecting the functional splitting), so that (i) K(s) demands can be controlled and routed in G using these NFs; (ii) the NFSs installed on G can be packed into the NFs while satisfying both isolation and capacity constraints; and

(iii) a path in G is associated with each pair of installed NFs that must be connected. The objective is to design each network slice and embed them into the physical network G while minimizing the Note that, for each slice, several copies of the same NFS type could be required (e.g. NFS 2). In the illustrated solution, copies of NFS 1 from NS 1 are installed distributed, at each of its origin nodes, while all other NFSs are centralized. Furthermore, copies of NFS 5 are packed into NF6 and shared by both network slices. Finally, the tra c flow from each slice request is routed through the physical network: regarding the tra c demand (distributed unit 3 ae application node 7) of slice 1, its virtual DP flow encompassing the virtual link (NF1, NF4) is routed through the physical path (3,[START_REF]Architecture enhancements for control and user plane separation of EPC nodes (Release 14)[END_REF][START_REF] Ford | maximal flow through a network[END_REF]. In our previous work [9], we reported numerical results showing that flexible splitting appears as a key factor to deal with heterogeneous requirements to deploy distinct CSs, leading to considerable network slice cost decrease.

Related works

Scalability is a crucial point in dynamic environments, such as mobile networks. Authors in [START_REF] Alawe | On the scalability of 5g core network: the amf case[END_REF] propose an algorithm based on Control Theory in order to balance the load on instances of a specific core-based NF, called Access Management Function (AMF). Their algorithm scales out or in the AMF 5.2. RELATED WORKS and path constraints, as well as a heuristic to reduce the computational complexity and apply it to production-level networks.

Optimization approaches related to network slicing problems mostly consider them either as Virtual Network Embedding (VNE) [START_REF] Fischer | Virtual network embedding: A survey[END_REF] or Function Placement and Routing (FPR) [START_REF] Addis | Virtual network functions placement and routing optimization[END_REF] problems. The former problem can be defined as follows: given a set of r requested virtual network represented by graphs G v = (V v , A v ), v oe {1, . . . , r} and a physical network represented by graph G p = (V p , A p ), the aforementioned approaches seek to embed the graphs G v into G p . Hence, each requested node u oe V v , v oe {1, . . . , r} is mapped to a physical node in V , each requested arc a oe A v is mapped to a physical path on G p , and all technical constraints are respected. In the case of the FPR problem, each virtual network request is given by a directed acyclic graph to represent ordering constraints on mapping virtual nodes through physical paths connecting di↵erent pairs of source-destination nodes on the physical network. For instance, Esteves et al [START_REF] Esteves | Location-based data model for optimized network slice placement[END_REF] propose an FPR-based ILP formulation to design network function placement under slice-mimicking demands while considering the users' geographic location to guarantee the acceptable end-to-end latency on the data-plane flow; the same authors propose in [START_REF]Heuristic for edge-enabled network slicing optimization using the "power of two choices[END_REF] an online heuristic to address the computational complexity of the studied problem.

In the same context, Fendt et al [START_REF] Fendt | A formal optimization model for 5g mobile network slice resource allocation[END_REF] present a MILP taking into consideration the network function chaining and path splitting, which is based on an FPR formation. The proposed model also considers an embedding with minimum latency for the virtual links of the NF chains related to the slices. Liu et al [START_REF] Liu | Provisioning optimization for determining and embedding 5g end-to-end information centric network slice[END_REF], in turn, consider that the quantity, the types, and the locations of the NFs related to the slice are determined by the requirements and distribution of users. Due to the complexity of the proposed model, they also present a VNE-based heuristic to address the related problem in large-scale networks.

Even though several works partially cover the network slice design problem [START_REF] Baumgartner | Optimisation models for robust and survivable network slice design: A comparative analysis[END_REF][START_REF] Tan | Analog coded softcast: A network slice design for multimedia broadcast/multicast[END_REF] and related sub-problems, such as functional split mode selection [START_REF] Maeder | Towards a flexible functional split for cloud-ran networks[END_REF][START_REF] Wang | Centralize or distribute? a techno-economic study to design a low-cost cloud radio access network[END_REF][START_REF] Chabbouh | Cloud RAN architecture model based upon flexible RAN functionalities split for 5G networks[END_REF], network slicing with VNF sharing [START_REF] Malandrino | Getting the most out of your vnfs: Flexible assignment of service priorities in 5G[END_REF][START_REF] Truong-Huu | Service chain embedding for diversified 5G slices with virtual network function sharing[END_REF][START_REF] Crippa | Resource sharing for a 5G multi-tenant and multi-service architecture[END_REF], and network slicing with VNF scaling [START_REF] Alawe | On the scalability of 5g core network: the amf case[END_REF][START_REF] Alawe | Smart scaling of the 5G core network: an rnn-based approach[END_REF][START_REF] Wang | Online learning-assisted vnf service chain scaling with network uncertainties[END_REF][START_REF] Fei | Adaptive VNF scaling and flow routing with proactive demand prediction[END_REF][START_REF] Zhang | Proactive VNF provisioning with multi-timescale cloud resources: Fusing online learning and online optimization[END_REF], no attention has been given to address jointly all the aforementioned aspects in order to design network slices and understand the impact of mapping, sharing and split policies.

MATHEMATICAL PROGRAMMING FORMULATION

Mathematical programming formulation

We now present the network slice provisioning as an optimization problem including novel mapping and provisioning requirements rising with new radio and core function placement policies. In this section, we propose a mixed-integer linear programming formulation for the NSDP. The problem variables are defined as follows:

• z s f oe {0, 1} that takes value 1 if NFS f is centralized, 0 otherwise,
• x sf nu oe {0, 1} that takes value 1 if NFS f serving slice s is packed into NF n, installed on node u, 0 otherwise,

• w sf nu oe R + the ratio between the quantity of tra c processed by NFS f , packed into NF n and installed on node u to serve slice s, over its capacity cap(f ),

• y f nu oe Z the total number of NFSs f packed into NF n, installed on node u,

• " ka fg oe {0, 1} that takes value 1 if arc a is used to route the tra c between NFS f and NFS g for demand k, 0 otherwise.

The constraints are categorized into several blocks and defined as follows :

Split Selection: The split selection constraints are to impose that if NFS f oe F d is centralized, then the remaining NFSs of the ordered set F d should also be centralized, thus defining a splitting policy attached to a slice :

z s f AE z s f +1 , 's oe S, 'f oe F d \{f |F d | }. ( 5
cap(f )w sf nu = Y _ _ _ ] _ _ _ [ q koeK(s)|u=o k ⁄ f ≠1 b k x sf nu if f oe F d , u oe V du ÷ s b f x sf nu if f oe F c ; q koeK(s) ⁄ f ≠1 b k x sf nu if f oe F d , u oe V ac . 's oe S, 'f oe F, 'n oe N, 'u oe V (5.2) ÿ soeS w sf nu AE y f nu 'n oe N, 'v oe V, 'f oe F (5.3)
x sf nu + x tg nu AE 1 + q st fg q ts gf 's, t oe S, u oe V, n oe N, f, g oe F (5.4)

ÿ noeN x sf nu + ÿ moeN
x tg mu AE 1 + q st q ts 's, t oe S, u oe V na , f, g oe F (5.5)

x sf nu + x tg nv AE 1 's, t oe S, f, g oe F, n oe N, u, v oe V : v " = u (5.6)
Let us explain in detail the inequalities (5.3) with some examples. Suppose that NFSs of type f from s and t cannot be packed together ('n oe N, x sf nu ü x tf nu ). Hence, all copies of f installed on node u and serving s are not shared with t. In this way, if (5.2) set w sf mu to 4.60 and w tf nu to 1.25, for example, we must install at least seven (Á4.60Ë + Á1.25Ë) NFSs of type f on the node u using two di↵erent NFs. Now, let s and t be two slices with no isolation constraints and using the same NF for a given NFS f (x sf nu • x tf nu ). Suppose that (5.2) have set w sf bu and w tf nu equal to 4.60 and 1.25, respectively. Since both s and t accept NFS sharing with each other (q st ff •q ts ff ), we need to install only six (Á4.60 + 1.25Ë) NFSs of type f on node u instead of seven of them. Using this approach on residual capacities, this saving can be even greater if we have a bigger sub-set of slices having q st fg = 1 for a given tuple (s, t, f, g).

Network Function Services Placement: For each slice request s, equalities (5.7) ensure that a distributed NFS f should be installed on every origin node of K(s); whereas equalities (5.8) ensure that each centralized NFS f serving s should be installed in a node of V ac .

ÿ noeN x sf nu = I 1 ≠ z s f , if f oe F d , u = o k ; 0 , otherwise . 'k oe k(s)|s oe S, 'f oe F, u oe V du (5.7) ÿ noeN ÿ uoeV ac x sf nu = I z s f , if f oe F d ; -s f , if f oe F c . 's oe S, 'f oe F (5.
w s uf Ø 0 oe R 's oe S, 'f oe F, 'n oe, 'u oe V (5.19)
While the first term in (7.9) is related to the number of installed functions, the second term in (7.9) multiplied by is inserted to mechanically avoid loops, with a negligible qualitative impact on the network solution. An alternative way to the second term would be to add loop avoidance constraints, however increasing the complexity. Network designers may want to tune the factor to drive toward the desired outcome (e.g., to emphasize the number of NFSs over the number of links).

Complexity

In order to prove the complexity of the NSDP, we first define the Virtual Network Embedding problem, which is used in our reduction framework.

Virtual Network Embedding problem: Let G p = (V p , A p ) be a directed graph representing the physical network (also known as substrate network), where V p is the set of physical nodes and A p is the set of physical links. While c c p (u) represents the available resource c oe C on the physical node u oe V p , b p (a) is the available bandwidth on arc a oe A p . Also, each arc in A p has the latency d p (a) expressing the time needed by a fow to traverse a. Finally, the request graph is similarly defined as a directed graph G r (V r , A r ) with minimum capacities c c r (u) and b r (a) required respectively by virtual nodes and arcs from G r ; each arc in A r also has the maximum latency d r (a) that must be respect in the embedding process.

In the VNEP, the requested graph must be mapped to the physical graph: each requested node u oe V r is mapped to a physical node in V p , and a requested arc is mapped to a physical path on G p . A valid mapping must respect both required and available resources and latency constraints. As proven by [START_REF] Rost | On the hardness and inapproximability of virtual network embeddings[END_REF], the VNEP is N P-complete even with no latency and resource constraint related to 5.4. COMPLEXITY the physical network (i.e., physical nodes and links have infinite capacities and no latency) and cannot be approximated under any objective unless P = N P holds.

Theorem 5.4.1. The Network Slice Design problem is N P-complete even with only one slice request.

Proof. We first prove the N P-hardness of the NSDP. For this purpose, our framework reduction relies on the VNEP. Given a VNEP instance with a request graph G r , we construct a slice request s for each sub-graph in G r as following. For each requested node u oe V r , a control-plane NFS is created in F c with the same required capacity c c u and, for each f oe F c , the relateds f is set to 1. Similarly, for each arc in G r , there is a tuple in F (s) imposing the connection between the related NFSs f and g from F c with the same acceptable minimum bandwidth and maximum latency values.

In addition, a set F d is constructed with dummy functions with no capacity required to be installed (i.e., c c f 0 = 0, 'f oe F d , 'c oe C). Additionally, any function in F has infinite processing capacity (i.e., cap(f ) = +OE ). For any tuple (s, t, f, g) : {s, t oe S, f, g oe F |s " = t}, the related isolation parameter q st fg is set to 0. In other words, no NFS sharing is allowed between any pair of slice requests. Moreover, for each s oe S, dummy tra c demands with no data flow are created (i.e., b k = 0, 'k oe K(s)|s oe S); origin and destination nodes o k and t k are randomly chosen among the physical nodes in V du and V app , respectively, for any tra c demand k. Note that F d and K(s) sets can be of any size, even empty. Finally, the graph G representing the physical network remains the same. This reduction is done in polynomial time with complexity O(|A r |).

Clearly, if there exists a feasible solution to the NSDP that respects the capacity and latency constraints (if there exists any), then this solution is also feasible for the VNEP. Hence, any algorithm applied to solve the NSDP can also be used to decide the VNEP, showing the N P-hardness of the NSDP.

To conclude the N P-completeness proof, we now show that NSDP is also in N P. For this end, our verifier-based algorithm relies on the proposed compact formulation (5.1)-(5.19) without the objective function (7.9). Giving an NSDP instance I, a certificate X (i.e., a solution to I) can therefore be constructed in polynomial size in |S|, |F |, |N | (i.e., number of variables). In other words, X is a vector with a fixed value to each variable of the linear system. Our verifier V is also constructed in polynomial size in |S|, |F |, |N | and |V | (i.e., number of constraints). To decide whether X is a feasible solution to I, we apply V in order to verify if there exists at least one violated constraint. It is easy to 5.5. VARIANTS AND EXTENSIONS FOR THE NSDP see that V returns true if and only if X is a feasible solution to I (i.e., no constraint is violated). Since verifying a system of equations is done in a polynomial time, the NSDP is also in N P, and hence in N P-complete.

It is important to note that NF dimensioning and NFS sharing sub-problems are partially solved by setting all related isolation parameters q st fg to zero; this implies that, on the control-plane, there exists only one feasible solution for each sub-problem; on the data-plane, these sub-problems depend on the select split setting chosen for each slice request. Also, even being fully solved, the data-plane split selection sub-problem has no impact on the reduction framework since no physical capacity is required by the related dummy flows. Note that this sub-problem can be seen as a Service Function Chaining problem [START_REF] Bhamare | A survey on service function chaining[END_REF], which is also a di cult problem. Clearly, an NSDP instance that has di↵erent values for these aforementioned parameters increases the related sub-problems' feasible solution space and therefore makes the NSDP even harder to be solved in optimization scenarios.

Variants and extensions for the NSDP

In the following, we present a few relevant variants of the Network Slice Design Problem.

NDSP with intra-slice flexible splitting

With this variant of the problem, di↵erent split settings can be selected within the same slice. In other words, flexible splitting is applied independently to each DU related to a given slice. For this purpose, we apply a pre-processing to transform each tra c demand into a slice request2 . Hence, any NS request is now composed of only one tra c demand (i.e., representing a unique tra c demand of the initial NS request). In order to impose a shared control-plane to all DU related to the same initial NS (i.e., before the pre-processing), we introducest , a binary parameter generated during the pre-processing: it holds 1 if the new slices s and t come from the same initial NS request (i.e., before the decomposition); 0 otherwise. Finally, in order to reduce the management complexity, we add the new constraints (5.20): they impose that requests from the same NS must share the same control-plane NFSs. Note that the single requests from the same original slice can have their own data-plane. We

VARIANTS AND EXTENSIONS FOR THE NSDP refer to this variant by NSDP with intra-slice flexible splitting (NSDP-ISFS)

.

-st ≠ 1 AE x sf nu ≠ x tf nu AE 1 ≠ -st , 's, t oe S, f oe F c , n oe N, u oe V ac (5.20)
Note that, constraints (5.20) impose the binary variables x to have the same value (i.e., either 1 or 0) if and only if the related parameter -holds 1; otherwise, these inequalities are implicitly relaxed.

After applying the described pre-processing on the initial input, the original formulation of NSDP (5.1)-( 5. [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF]) can be directly applied along with the new constraints (5.20).

NDSP with inter-slice split continuity

We propose this variant in order to represent the scenarios with strict split setting constraints on each DU. In fact, imposing the same split selection for any tra c demand traversing a given DU might be necessary to reduce the management complexity. Complementary to Ineq. (5.20), we add the new constraints (5.21), where fl st is a binary parameter generated during the pre-processing; it holds 1 if the new slices s and t have the same origin DU node as their tra c demands; 0 otherwise.

fl st ≠ 1 AE z s f ≠ z t f AE 1 ≠ fl st , 's, t oe S, 'f oe F d (5.21)
Note that these inequalities can only be applied to instances whose slice requests have only one tra c demand (i.e., after pre-processing). We refer to this variant by NSDP with inter-slice split continuity (NSDP-ISSC).

NSDP with optimized link load

In order to minimize the tra c volume throughout the network, we introduce U , a continuous variable that represents the maximal load among physical links. We then replace constraints (5.12) by Ineq. (5.22) and (5.23) and add the new constraints (5.24) in order to impose upper bounds to y variables; these inequalities are important to this NSDP variant since we no longer have the related component within the new objective function (5.25). and v, there exists one arc (v, u) for each arc (u, v). Fig. 5.2a shows this topology where n is equal to 16. For sake of clarity, each pair of arcs between two nodes is represented by an edge.

ÿ soeS ÿ koeK(s) b k (⁄ f |F d | " ka f |F d | f 0 + ÿ f oe{f 0 }fiF d \{f |F d | } ⁄ f " ka ff+1 )]+
In our simulation, while application nodes have no capacity constraint (they are considered as sink nodes), each one of DU, aggregation, and core nodes provides 30 servers, each of which with 16 CPUs; this capacity corresponds to 12.5% of the global generated CPU computing demand (i.e., with no function sharing) and enables to test all split settings and sharing policies. In addition, fronthaul links (i.e., between DUs and aggregation nodes), backhaul links (i.e., between aggregation and core nodes), and core links (i.e., between core and application nodes) have link capacities b a set to respectively 100%, 200% and 300% of the maximum flow sent by a single DU at the split setting with the highest bitrate. Finally, to simulate a small region, the latency d a in each arc randomly takes a value between: 50µs and 100µs for fronthaul links, 200µs and 300µs for backhaul links, and 400µs and 600µs for core links 3 .

We also run our tests on two di↵erent physical topologies: one binary tree-based structure (hereinafter referred to as Tree; Fig. 5.2b) with 31 nodes and 60 arcs, and Sun from SNDlib [START_REF] Orlowski | SNDlib 1.0-Survivable Network Design Library[END_REF] composed of 27 nodes and 102 arcs (Fig. 5.2c). We mapped the 16 DUs to all 16 leaves and the nodes composing the external ring path in the former and latter structures, respectively; aggregation, core, and application nodes were randomly mapped in both topologies. While the capacities on physical nodes follow the same parameter values in Mandala, the bandwidth on links from the Tree structure was set to 500% of the maximum flow sent by a single DU at the split setting with the highest bitrate; the latency is between 50µs and 100µs. For the Sun topology, these values were randomly chosen between 3. Note that the end-to-end latency along the shortest path between any DU and application node is at most 1ms. This value is commonly used as a threshold to strict latency constrained 5G services [START_REF] Alliance | 5G White Paper[END_REF]. 50µs and 600µs for the latency whereas the bandwidth values were set between 100% and 300% of the maximum flow sent by a single DU.

SENSIBILITY ANALYSES

Virtual layer

To scale with the complexity of the formulation while stressing the impact of functional splitting on the placement of NFSs, we set F d with five data-plane NFS types: NFS1 represents functions of the MAC bloc; NFS2 represents functions of the RLC block; NFS3 represents functions from PDCP block;

NFS4 represents functions from RRC block; NFS5 represents DP functions from the core network4 .

In addition, there are four mandatory control-plane NFS types (labeled NFS6..NFS9) and other four optional CP NFS types (labeled NFS10..NFS13; examples of mandatory and optional 5G core NFs are presented in [1]). Each NFS has a processing capacity cap(f ) set to 100% of the average volume sent by all DUs. Furthermore, the resource c f required to install each copy of them is set to roughly 5% of the average capacity available on physical nodes. Also, the tra c generated from or to any CP NFS was set to 1 kbps per UE.

According to the 4G functional split levels reported in Table 3.2 and considering the uplink direction, we set similar compression coe cients ⁄ f related to initial volume sent by a tra c demand: 65% for NFS1 and 40% for the other DP NFSs. Additionally, the acceptable latency d fg between two DP NFSs from F d also follows those in Table 3.2, taking the upper bound when an interval is proposed.

Finally, the latency d fg involving any CP NFS is set not to exceed 500µs; this value corresponds to 5% of the total CP latency proposed by 3GPP [START_REF]Architecture enhancements for control and user plane separation of EPC nodes (Release 14)[END_REF].

Slice requests

We tested instances with four NS requests, each with four tra c demands with random origindestination pairs; for each k oe K(s), origin o k is a DU while destination t k is an application node as 5.6. SENSIBILITY ANALYSES previously discussed. Additionally, all network slices must contain all data-plane NFSs, four mandatory control-plane NFSs, and a di↵erent set of additional NFSs that can be required (see Table 5.2). We assume that all CP NFSs are connected to each other. Furthermore, to simulate the communication between data and control planes, there exists an expected tra c volume between CP NFSs and DP ones on each related network slice; we create such tra c from CP NFS6 only (e.g., corresponding to the Access and Mobility Management Function, AMF, in 5G core [1]) to all DP NFSs (NFS1..NFS5).

To also observe the impact of di↵erent sharing policies on the number of distributed NFSs, 25% of available DUs are set to be an origin node of all NS requests; application nodes are evenly distributed as target nodes. Finally, each slice request imposes di↵erent technical constraints related to end-to-end latency d s , demands for optional CP NFSs, and expected user experienced data rate. As depicted in Table 5.2, we applied the assumptions proposed by [START_REF] Alliance | 5G White Paper[END_REF] for each aforementioned requirements. In our simulations, slice request 1 represents an eMBB application with an important tra c volume, which impacts both virtual and physical capacities. Slice request 3, in turn, represents an URLLC application, imposing a strict end-to-end latency on the data-plane, which restrains the placement possibilities of the related NFSs. The other two slice requests are intermediate regarding both aforementioned parameters; request 2 can be seen as an mMTC application. Finally, being an origin of one of some slice's tra c demands, each DU is associated with a flow rate equal to the product between the expected number of UE per DU and their related data rate in such NS.

Scenarios

Following Fig. 3.3, each scenario represents one combination of functional split setting and sharing policy applied to all slices. While di↵erent sharing policies are those previously presented (see Fig. 3.9), the split settings impose di↵erent sets of distributed and centralized DP NFSs. Table 5.3 summarizes the tested scenarios. Te proposed scenarios represent realistic areas, such as small cities and dense zones to scale with the complexity of the formulation while stressing the impact of functional splitting on the placement of network functions services. Each simulated parameter follows those proposed in related technical documents [START_REF] Alliance | 5G White Paper[END_REF][START_REF]Architecture enhancements for control and user plane separation of EPC nodes (Release 14)[END_REF] in order to provide scenarios that are as realistic as possible.

SENSIBILITY ANALYSES

Numerical results

The analyses made in the following sub-sections are related to the formulation ( 1)-( 26) and present the numerical experiments of each variant of the problem on sub-section 3. We implemented our model in a Julia-JuMP environment using ILO CPLEX 12.8 as the linear solver. We set to an enough small value (i.e., 10 ≠3 ) on the objective function (7.9) only to prioritize elementary paths to carry tra c demands and to emphasize the number of NFSs over the number of links in the optimization process. Finally, our tests were run on a Linux server with an Intel Xeon E5-2650 CPU and 256GB

RAM. The data-set and the source code are available on [START_REF] Da | NSDP: source code and instances[END_REF].

Execution time

Before discussing the results related to the simulation setting as previously detailed, we present the performance of our model on di↵erent instance sizes: we varied the number of NFSs available (from 3 up to 24), the number of tra c demands per slice request (from 1 up to 16), and the physical topology size (13, 26, and 52 physical nodes with random connection and average degree equals to 10). Finally, all instances had 4 NS requests. We run 30 tests of each instance size, varying both origin and target nodes of each tra c demand. Finally, we set the maximal number of parallel threads that could be invoked by the solver to 1 and the time limit to 10 800 seconds (three hours).

As shown in Fig. 5.3, the time needed to achieve the best solution increases exponentially with the size of the instance. In particular, the number of NFSs available has the worst impact on the 5.6. SENSIBILITY ANALYSES model. Even with small topologies (13 nodes), the problem with 24 NFSs could not be solved within 3 hours. Due to the di↵erent levels of packing problems within the model, this time limit is also reached with the biggest topologies (52 nodes) and only 12 NFSs. The execution time also increases as the number of tra c demands increases. Due to the related routing sub-problems, the limit of three hours is also reached with any number of demands and 12 NFSs on large topologies. It is worthwhile to mention that, for those instances with 13 (resp. 52) nodes that reached the time limit and could not be solved to optimality by the solver, the average relative gap was roughly 7% (resp. 43%) with standard deviation equals to approximately 2% (resp. 8%).

Functional split and NF sharing

We now discuss the results depending on the presented network settings. We applied additional constraints to impose the desired split setting to all slice demands. Additionally, sharing policies were imposed by changing the q st fg parameters values used in Ineq. (5.4). All instances were generated using Mandala, Sun and Tree topologies with 16 DUs (see Fig. 5.2). Finally, we run 10 tests on each physical network varying both tra c demands' origin and destination nodes. The goal of the following numerical analysis is to assess the impact of novel mapping, splitting, and sharing policies on network design. -Since all NFSs are installed on all DUs related to each slice request, split setting 1 requires the largest number of NFS copies in all proposed sharing policies; -Since each (resp. no) NFS copy is dedicated to a single NS, Hard (resp. Flat) Isolation has the greatest (resp. smallest) number of NFSs copies on all split settings, including the flexible one.

In our simulations, having isolation constraints on di↵erent sets of NFS types led to di↵erent impacts on the network slice design. Regarding the five first split settings, Shared DP and Partial DP policies provided a mean decrease (resp. increase) of 28% (resp. 42%) on the number of distributed (resp. centralized) NFSs compared to Shared CP and Partial CP; the total number of NFSs when using shared policies (i.e., CP Shared and DP Shared) was always smaller than when using partial policies (i.e., Partial CP and Partial DP). Also, flexible splitting proves to be an interesting strategy even for scenarios that have strong isolation restrictions. With roughly 56% as an overall reduction, this approach has the smallest number of NFSs in all mapping scenarios; regarding each sharing policy, the average reduction was roughly 38% (standard deviation equals to approximately 10%) compared to split setting 1. It is important to note that, since we minimize the total number of NFSs, flexible split always had the same number of NFS copies as split setting 6, which provided the greatest number 5.6. SENSIBILITY ANALYSES of centralized NFSs. This behavior might di↵er if the NS provider is interested in optimizing other parameters, such as the load on physical arcs.

In Fig. 5.5 we show that applying di↵erent sharing policies and split settings has also an important impact on the physical network. It is worth mentioning that we excluded from the computation of the average load the unused links and nodes, and for sake of readability, the standard deviations are not depicted; the observed ratios of the standard deviation to the mean were always less than 14%. First, we observe that split settings 6 and Flexible have the worst impact on link load in all sharing policies, requiring up to 100% of the capacity on the most loaded link (see Fig. 5.5e); the average load on backhaul and core (resp. fronthaul) links was equal to 52% (resp. 40%) applying Flat (resp. Shared DP) sharing policy and split setting 6 (see Figures 5.5c and 5.5d). This behavior is expected since all NFSs are installed centrally and the data volume sent by each tra c demand is completely decompressed before traversing the fronthaul links. Conversely, split setting 1 benefits from the impact of the compressed data and demands the least amount of capacity on the links in all mapping approaches, requiring at most 60% of the capacity on the link on average (see Fig. 5.5e).

However, as shown in Fig. 5.5a, this split is one of the settings that require the largest number of links (between 77% and 82%) since the NFSs from CPs and DPs are further from each other. Besides, CP NFS6 must be connected to all distributed DP NFSs of the related NS.

We also note a strong impact of di↵erent scenarios on physical nodes. Since there exist at least one NFS type installed locally, the first five functional splits had the largest number of physical nodes hosting at least one NF (see Fig. 5.5f). We also observe a decrease of the average load on physical nodes (see Fig. 5.5g), in particular on DU nodes (see Fig. 5.5h), on all sharing policies. However, due to the completely decompressed data arriving in the centralized DP chain, a shift of behavior is observed when split setting 6 is applied (see Fig. 5.5g). Unlike physical links and aggregation and core nodes (see Fig. 5.5b and Fig. 5.5i, respectively), DU nodes benefit from functional splits where a greater number of NFSs is installed centrally. The average load on DU (resp. aggregation and core) nodes decreased (resp. increased) from roughly 43% (resp. 21%) applying split setting 1 along with Partial CP (resp. Shared CP) sharing policy to approximately 8% (resp. 75%) applying split setting 5 jointly with Flat sharing policy; the most loaded physical node (see Fig. 5.5j) provided 98% (resp. 43%) on average of its available resource applying split setting 6 (resp. setting 1) and Partial DP (resp. Flat) sharing policy. Note that, applying Hard, Shared CP, and Partial CP isolation policies, 5.6. SENSIBILITY ANALYSES Figure 5.5 -Impact of di↵erent split settings and sharing policies on the physical network. all distributed NFSs can serve only one slice. Hence, they will always demand the same capacity from DU nodes when the same split setting is applied (see Fig. 5.5h).

Even with a negative impact on the number of installed NFSs, mapped links, and nodes (see Figures 5.4, 5.5a, 5.5f, respectively), Hard Isolation could partially unload the physical network. In fact, due to strong isolation constraints, this sharing policy demanded less physical capacity from links (see Fig. 5.5b) and from aggregation and core nodes (see Fig. 5.5i) in some split settings. Consequently, a short physical path for each tra c demand was prioritized, leading to the use of physical nodes and links not mapped to other tra c demands. Also, let us recall that the final solutions prioritized minimizing the number of NFSs, even if this approach harms the load of the physical network; to bring the final solution closer to its economic strategy, the NS provider can simply modify the objective function (7.9) to a more suitable one. It is also worth mentioning that, in order to test feasible instances of all functional split settings, we set a low enough latency for each physical link; otherwise, some split settings (e.g. settings 5) could be impossible. Finally, since we imposed the same scenario (see Table 5.3) to all slice requests, we did not observe a significant di↵erence in the results using distinct physical topologies. For instance, comparing the three proposed topologies, the di↵erence in the number of physical nodes hosting an NF, the ratio of active links, and the number of NFS copies were always less than 7%, 11%, and 1%, respectively. This behavior might be di↵erent in real scenarios since NS requests are likely to impose di↵erent isolation constraints and physical networks might not have enough capacity to allow all split settings (due to the relation between the fronthaul capacity and the NFSs' compression coe cient). This, therefore, reinforces the importance of applying flexible 5.6. SENSIBILITY ANALYSES functional splitting while considering di↵erent sharing policies in virtual environments.

NSDP and variants

We now present the impact of the proposed variants of the presented problem on the physical network. Henceforth, we refer by NSDP the original formulation (5.1)- (5.19); the other two variants refer to the proposed formulations as previously discussed. Since we set to 10 ≠3 in (7.9), we refer by minNFS this objective function while minLinkLoad refers to (5.25); as aforesaid, this objective function is implemented along with inequalities (5.22)-(5.24). Also, the sharing policy was randomly chosen for each pair of slices while we applied the Flexible Split setting along with the same parameters related to both physical and virtual layers as previously presented in this section. Finally, we run 10 tests on each combination of objective function, variant, and physical topology, varying both origin and target nodes of each tra c demand; for NSDP-ISFS and NSDP-ISSC variants, the pre-processing described in the previous section was applied on the NSDP instances. variants, the average increase in terms of both numbers of NFSs and hosting nodes was roughly 400%. This is due to the impact of the compression coe cient related to data-plane NFSs; when installed locally, they can compress the data before leaving the origin node of each tra c demand. However, as seen in Fig. 5.6j, this strategy is limited by the available resources on DU nodes, which impose to install some DP NFSs centrally whenever the related physical capacities are reached (see Fig. 5.6k and Fig. 5.6l). Moreover, since the data flow is spread over as many physical links as possible, minimizing the load on physical links also increased the end-to-end DP latency (i.e., the latency between tra c requests' origin and target physical nodes); this increase was approximately 100% on all NSDP variants (see Fig. 5.6c).

Applying di↵erent variants has also an important impact on the physical network. Since NSDP-ISFS and NSDP-ISSC variants allow sharing data-plane NFSs with other slices rather than the ones from the same initial slice request (which gives more flexibility to NFS placement decisions), di↵erent objective functions had opposite impacts on the physical network. Indeed, the NSDP approach demanded up to 40% more (resp. 50% less) bandwidth compared to the other variants when the number of NFSs (resp. load on the physical links) is minimized (see Figures 5.6d,5.6e, and 5.6f). Also, comparing the two objective functions, the load on physical links could be reduced by a factor of 3, and the most loaded physical link provided roughly 97% (resp. 34%) of its capacity when NSDP-ISSC (resp. NSDP) is applied along with minNFS (resp. minLinkLoad) objective function (see Fig. 5.6g). This behavior is explained by the concentration of NFSs on few physical nodes when the minNFS objective function is applied, hence stressing the related incoming links; applying the split setting 6 whenever is possible, this concentration is due to the greater number of centralized DP functions to be installed.

Moreover, the NSDP-ISSC variant had a relevant impact on the physical nodes (see Fig. 5.6i); comparing this variant to NSDP and regarding the minNFS formulation, the load on physical nodes could be decreased from 85% to 65% on average. NFSs' compression coe cients also play an important role in the final solution. Indeed, depending on the parameter to be optimized, di↵erent split settings are prioritized. For instance, when the load on the physical links is minimized, split setting 1 is always selected when it is admissible by DUs' capacity (see Fig. 5.6j); this functional split places all DP NFSs locally and therefore completely compresses the tra c demands' flow before sending it through fronthaul links (see Fig. 5.6e). It is worth mentioning that, regarding the three proposed physical topologies, we observed an important di↵erence only on the end-to-end DP latency and on the fronthaul links' load. In our simulations, while the average end-to-end DP latency was 2.50 ms on the Tree structure, these values increased to 4.20 ms and 6.60 ms on Sun and Mandala topologies, respectively. Let us recall that, since there is only one possible elementary path to connect any pair of physical nodes on the Tree topology and slice 5.7. SUMMARY request 3 imposes a strict DP latency (see Tab. 5.2), the latency on the related physical links is lower than those found on Sun and Mandala structures; otherwise, some instances would be infeasible. For the same reason and in order to carry the flow from slice request 1, the links' capacity on Tree topology is greater than on the other two structures. Hence, when the number of NFS copies was minimized, the average load on fronthaul links on Tree, Sun, and Mandala was respectively 12.50%, 30%, and 40%. However, running the same instance on each of these topologies, we observed no di↵erence in the selected split setting on the final solutions. However, this behavior might not be observed in real scenarios since physical networks are unlikely to have enough capacity to allow any split setting and hence be able to allocate resources to all slice requests. This, therefore, reinforces the importance of applying flexible functional splitting in future 5G systems and beyond.

Summary

In this chapter, we modeled the network slice provisioning as an optimization problem including novel mapping and provisioning requirements. In particular, we considered novel mapping dimensions appearing with 5G systems, modeling the relationship between flexible radio access functional splitting, control-plane and data-plane function separation, and sharing policies. Di↵erent variants of the problem were also proposed and the related models are compliant with running standards. We demonstrated by simulation the impact of taking into full and partial consideration of the peculiar constraints rising from the standards. For instance, we reported numerical results showing that flexible splitting appears as a key factor to deal with heterogeneous requirements to deploy distinct communication services, leading to considerable network slice cost decrease. In our simulations, the number of NFSs needed to deploy the virtual networks could be reduced by up to 56% depending on which of the six proposed sharing policies is applied to each network slice. We also observed that di↵erent variants related to the flexible splitting have an important impact on the physical network; depending on the selected approach, the average load on physical links could be reduced by a factor of 3.

Chapter 6

Exact approaches for the NSDP In this chapter, we propose several exact approaches based on the MILP formulation (5.1)- (5.19) for the problem, which includes novel splitting, mapping and provisioning constraints described in the published 5G standards documents [START_REF]Architecture enhancements for control and user plane separation of EPC nodes (Release 14)[END_REF][START_REF] Ford | maximal flow through a network[END_REF][START_REF] Jump | Julia for Mathematical Programming: Callbacks[END_REF]. We propose several classes of valid inequalities in order to strengthen the linear relaxation of the proposed MILP and integrate them in a Branch-and-Cut framework to solve the problem. We further present several strategies to reduce the symmetries and the size of the model1 . All notations follow those presented in Table 5.1.

SYMMETRY-BREAKING CONSTRAINTS

Symmetry-breaking constraints

This formulation could be strengthened by eliminating the inherent symmetries corresponding to the NF usage. The following inequalities are symmetry-breaking constraints for the NSDP.

x sf nu AE ÿ toeS ÿ goeF ÿ voeV x tg n≠1v 's oe S, 'f oe F, 'u oe V, 'n oe N \{n 1 } (6.1)
Inequalities (6.1) allow assigning the NFs in an ordered way, by forbidding the use of an NF n + 1 if NF n is available (i.e., hosting no NFS).

Proof. Given any NF n oe N , having the left-hand side of inequality (6.1) equals to zero (i.e., x sf nu = 0 for any s oe S, f oe F, u oe V p ) implies that n was not assigned to any f oe F and hence it is available to host any NFS from any slice request. Since we check this feature in a paired, ordered way (i.e., (n≠1, n)) and there is no utilization cost related to the uncapacitated functions from N , the right-hand side of the same inequality can hold any value equal or greater than zero; the related upper-bound will be imposed by constraints (5.4)-(5.13). Hence, (6.1) cut o↵ part of the feasible region, while guaranteeing that at least one optimal solution from the original problem remains feasible.

Example: Consider an instance with one slice request s 1 and three available network functions {n 1 , n 2 , n 3 } to host two di↵erent NFS types {f 1 , f 2 }. Given a physical node u 1 and regardless the related capacity constraints, all the following values for the x variables would imply the same cost in the complete solution for the problem:

x s 1 f 1 n 1 u 1 = x s 1 f 2 n 2 u 1 = 1 and x s 1 f 1 n 2 u 1 = x s 1 f 1 n 3 u 1 = x s 1 f 2 n 1 u 1 = x s 1 f 2 n 3 u 1 = 0 (6.2) x s 1 f 1 n 1 u 1 = x s 1 f 2 n 3 u 1 = 1 and x s 1 f 1 n 2 u 1 = x s 1 f 1 n 3 u 1 = x s 1 f 2 n 1 u 1 = x s 1 f 2 n 2 u 1 = 0 (6.3) x s 1 f 1 n 2 u 1 = x s 1 f 2 n 3 u 1 = 1 and x s 1 f 1 n 1 u 1 = x s 1 f 1 n 3 u 1 = x s 1 f 2 n 1 u 1 = x s 1 f 2 n 3 u 1 = 0 (6.4)
However, applying Proposition 6.1, only (6.2) would be feasible.

Valid inequalities

We now present several families of valid inequalities used to strengthen the linear relaxation of formulation (5.1)-(5.19).

VALID INEQUALITIES

Lower-bound inequality

The first inequality expresses a lower bound on the number of NFSs needed to satisfy all the slice requests of S and the associated tra c demands.

The following inequality

ÿ f oeF c Ï ÿ soeS n s b f cap(f ) Ì + ÿ f oeF d Ï ÿ koeK(s):soeS ⁄ f ≠1 b k cap(f ) Ì AE ÿ f oeF ÿ noeN ÿ voeV y f nu (6.5)
is valid for the NSDP.

Proof. The left-hand side of inequality (6.5) is the sum of constraints (5.2) when isolation (5.4)-(5.5) constraints and capacity inequalities (5.12)-(5.13) are relaxed. Hence, this is the minimum value for the right-hand side of inequality (6.5), which is the sum of constraints-(5.3) and the optimized parameter in the objective function (7.9) disregarding the required capacities and their related costs.

Shortest path-based inequalities

The following trivial valid inequalities are based on the fact that the physical path assigned to carry the flow associated to a tra c demand k cannot be shorter than the shortest path between o k and t k that is capable of carry the flow of k completely compressed. For each tra c demand k oe K(s) : s oe S, let sp(k) be the end-to-end latency on the shortest path between o k and t k with enough available capacity to carry the flow of k. Then, the following inequalities

ÿ aoeAp d a (" ka f |F d | f 0 + ÿ f oe{f 0 }fiF d \{f |F d | } " ka ff+1 ) Ø sp(k) , 'k oe K(s) : s oe S (6.6)
are valid for the NSDP problem.

Proof. Given a tra c demand k oe K, the left-hand side of inequalities (6.6) contains all possible gamma variables that will be present in any feasible solution for an NSDP instance; due to the flow conservation constraints (5.9), the variables holding 1 represent the path connecting the origin and target nodes of k and transversing all installed DP NFSs copies related to the same tra c demand.

Clearly, the sum of latency of all active arcs carrying the tra c sent by k cannot be smaller than the end-to-end latency on the shortest path with enough capacity to carry the expected volume between the related origin and target nodes. Also, consider a scenario with only one NFS f 1 installed on the origin node of the tra c demand k 1 , whose expected volume from its origin node o k to its target node t k is equals to 100Gbs after being compressed by NFS f 1 ; the dummy function f 0 is installed in the target node t k as previously discussed. As depicted by Fig. 6.1b,

" k 1 a1 f 1 f 0 = " k 1 a2 f 1 f 0 = 0.
50 is a feasible solution since it respects all technical constraints for the linear relaxation of the formulation (5.1)- (5.19). Since only arc a2 is capable of carry the complete flow of k 1 , sp(k 1 ) is equal to 100ms. By Proposition 6.2.2, this fractional solution is no longer feasible since we add the following valid inequality:

10" k 1 a2 f 1 f 0 + 100" k 1 a2 f 1 f 0 Ø 100 (6.7)
Hence, only setting " k 1 a1 f 1 f 0 to 0.00 and " k 1 a2 f 1 f 0 to 1.00 is a feasible solution as shown in Fig. 6.1b.

Minimum cut-based inequalities

The following valid inequalities are based on one min-cut max-flow theorem of Ford and Fulkerson [120], which states that for a single commodity, the maximum flow is equal to the minimum cut separating the related origin and target nodes. We, therefore, consider only the arcs with enough capacity to carry the expected flow individually. For each k oe K(s) : s oe S, let (k) be the set of all minimum cuts separating o k from t k , such that for any " oe (k

) ™ A p , " = {a|b a Ø ⁄ f |F d | b k }. Then, the following inequalities ÿ aoe" (" ka f |F d | f 0 + ÿ f oe{f 0 }fiF d \{f |F d | } " ka ff+1 ) Ø 1 'k oe K(s) : s oe S, '" oe (k) (6.8)
are valid for the NSDP problem. is no longer feasible since we add the following valid inequalities:

" k 1 a2 f 1 f 0 Ø 1 (6.9) " k 1 a4 f 1 f 0 Ø 1 (6.10) " k 1 a6 f 1 f 0 Ø 1 (6.11)
Hence, only setting " k1a2 f 1f 0 , " k 1 a4 f 1 f 0 , " k 1 a4 f 1 f 0 to 1.00 and all other variables to zero is a feasible solution.

Clique-based inequalities

In what follows, we introduce a set of inequalities based on the so-called conflict graphs related to the isolation constraints on one hand and the physical capacities on the other hand.

Virtual isolation

Let H n = (V n , E n ) be the associated graph obtained for each function n oe N as follows. A node v in V n is associated with every tuple (s, f, u) : s oe S, f oe F, u oe V and there exists an edge in (u, v) oe E n between any two nodes u = (s, f, u) and v = (t, g, u) from V n if q st fg ú q ts gf = 0 holds. Hence, an edge in H n exists if two NFSs are packed together in the same function n while violating the isolation constraints imposed by the NSs.

Let C(H n ) be the set of all cliques in H n . Then, the following inequalities

ÿ (s,f,u)oeC x sf nu 6 1 'n oe N, 'C oe C(H n ) (6.12)
are valid for the NSDP. Example: Consider a small instance with three slice requests {s 1 , s 2 , s 3 }, one CP NFS type f c , three NF {n 1 , n 2 , n 3 } and one non-access node u 1 in the physical network. For this instance, we also have q st fcfc ú q ts fcfc = 0 for any pair (s,t) of distinct slice requests from S. From (5.4), we have:

x s 1 fc n 1 u 1 + x s 2 fc n 1 u 1 + x s 3 fc n 1 u 1 + x s 1 fc n 2 u 1 + x s 2 fc n 2 u 1 + x s 3 fc n 2 u 1 + x s 1 fc n 3 u 1 + x s 2 fc n 3 u 1 + x s 3 fc n 3 u 1 AE 4.50 (6.13)
Now, consider the linear relaxation of the problem in which we no longer have the integrity constraints on the variables. Setting 0.5 all x variables gives a feasible fractional solution for (6.13) and

for the whole relaxed model. By Proposition 6.2.4.1, this fractional solution is no longer feasible since

VALID INEQUALITIES

we add the following aggregated cut:

x s 1 fc n 1 u 1 + x s 2 fc n 1 u 1 + x s 3 fc n 1 u 1 + x s 1 fc n 2 u 1 + x s 2 fc n 2 u 1 + x s 3 fc n 2 u 1 + x s 1 fc n 3 u 1 + x s 2 fc n 3 u 1 + x s 3 fc n 3 u 1 AE 3 (6.14)

Physical isolation

Let H u = (V u , E u ) be the associated undirected graph obtained from an instance of NSDP as follows. A node v in V u is associated with every tuple (s, f, n) : s oe S, f oe F, n oe N that x ¯sf nu > 0 holds in the current solution. In addition, there exists an edge in (u, v) oe E between any two nodes

u = (s, f, n) and v = (t, g, n) from V u if (q st
ú q ts = 0) holds. In other words, an edge in H u exists if two functions are packed together in any node u oe V p while violating the isolation constraints imposed by the related slices. Let C(H u ) be the set of all cliques on H u . Then, the following inequalities

ÿ (s,f,n)oeC x sf nu 6 1 'u oe V na p , 'C oe C(H u ) (6.15)
are valid for the NSDP.

Proof. Let C be a clique in C(H u ). If two tuples (s, f, n) and (t, g, n) from C are assigned to a same physical node u oe V p , the related isolation constraints (5.5) will be violated. I other words, each pair of tuples from clique C represents an infeasible packing of NFSs from di↵erent slices requests in a node u oe V p . Consequently, a clique in the graph H u corresponds to a set of NFS that cannot be simultaneously installed in any physical node u oe V p .

Example: Consider a small instance with three slice requests {s 1 , s 2 , s 3 }, one CP NFS type f c , three NF {n 1 , n 2 , n 3 } and one non-access node u 1 in the physical network. For this instance, we also have q st ú q ts = 0 for any pair (s,t) of distinct slice requests from S. From (5.5), we have:

x s 1 fc n 1 u 1 + x s 2 fc n 1 u 1 + x s 3 fc n 1 u 1 + x s 1 fc n 2 u 1 + x s 2 fc n 2 u 1 + x s 3 fc n 2 u 1 + x s 1 fc n 3 u 1 + x s 2 fc n 3 u 1 + x s 3 fc n 3 u 1 AE 4.50 (6.16) x s 1 fc n 1 u 2 + x s 2 fc n 1 u 2 + x s 3 fc n 1 u 2 + x s 1 fc n 2 u 2 + x s 2 fc n 2 u 2 + x s 3 fc n 2 u 2 + x s 1 fc n 3 u 2 + x s 2 fc n 3 u 2 + x s 3 fc n 3 u 2 AE 4.50 (
6.17)

x s 1 fc n 1 u 3 + x s 2 fc n 1 u 3 + x s 3 fc n 1 u 3 + x s 1 fc n 2 u 3 + x s 2 fc n 2 u 3 + x s 3 fc n 2 u 3 + x s 1 fc n 3 u 3 + x s 2 fc n 3 u 3 + x s 3 fc n 3 u 3 AE 4.50 (6.18)
Now, consider the linear relaxation of the problem in which we no longer have the integrity constraints on the variables. Setting 0.5 all x variables gives a feasible fractional solution for (6.16)-(6.18)

VALID INEQUALITIES

and for the whole relaxed model. However, by applying Proposition 6.2.4.2, this fractional solution is no longer feasible since we add the following aggregated cuts:

x s 1 fc n 1 u 1 + x s 2 fc n 1 u 1 + x s 3 fc n 1 u 1 + x s 1 fc n 2 u 1 + x s 2 fc n 2 u 1 + x s 3 fc n 2 u 1 + x s 1 fc n 3 u 1 + x s 2 fc n 3 u 1 + x s 3 fc n 3 u 1 AE 3 (6.19) x s 1 fc n 1 u 2 + x s 2 fc n 1 u 2 + x s 3 fc n 1 u 2 + x s 1 fc n 2 u 2 + x s 2 fc n 2 u 2 + x s 3 fc n 2 u 2 + x s 1 fc n 3 u 2 + x s 2 fc n 3 u 2 + x s 3 fc n 3 u 2 AE 3 (6.20) x s 1 fc n 1 u 3 + x s 2 fc n 1 u 3 + x s 3 fc n 1 u 3 + x s 1 fc n 2 u 3 + x s 2 fc n 2 u 3 + x s 3 fc n 2 u 3 + x s 1 fc n 3 u 3 + x s 2 fc n 3 u 3 + x s 3 fc n 3 u 3 AE 3 (6.21)

Link capacity

Let H a = (V a , E a ) be the associated graph obtained for each physical link a oe A as follows. A node v in V a is associated with every tuple (k, f, g) : s oe S, k oe K(s), f, g oe F . Let b(k, f, g) be the total data flow between NFSs f and g from commodity k. There exists an edge in (u, v) oe E a between . From (5.12), we have:

any two nodes u = (k, f, g) and v = (k Õ , f Õ , g Õ ) from V a if b(k, f, g) + b(k Õ , f Õ , g Õ ) > b a holds. Let
10" k 1 a f 0 f 1 + 10" k 2 a f 0 f 1 AE 15 , 'a oe A p (6.23)
This constraint imposes that the volume sent by each tra c demand to the DP NFS f 1 and carried by the arc a cannot be greater than its capacity. Now, consider the linear relaxation of the problem

VALID INEQUALITIES

in which we no longer have the integrity constraints on the variables. Setting 0.75 all " variables gives a feasible fractional solution for (6.23). However, by applying Proposition 6.2.4.3, this fractional solution is no longer feasible since we add the following cuts: andc 1 f 1 = 10. From (5.2),(5.3), and (5.13), we have:

" k 1 a f 0 f 1 + " k 2 a f 0 f 1 AE 1 , '
n 1 b f 1 cap(f 1 ) = n 2 b f 1 cap(f 1 ) = 1,
w sf 1 nu = x sf 1 nu
, 's oe S, 'n oe N, 'u oe V ac p (6.26)

w s 1 f 1 nu + w s 2 f 1 nu AE y f 1 nu AE 1.5
, 'n oe N, 'u oe V ac p (6.27)

A BRANCH-AND-CUT ALGORITHM FOR THE NSDP

Now, consider the linear relaxation of the problem in which we no longer have the integrity constraints on the variables. Setting x s 1 f 1 n 1 u 1 and x s2 f 1 n 2 u 1 to 0.75 gives a feasible fractional solution for (6.26) and (6.27). However, by applying Proposition 6.2.4.4, this fractional solution is no longer feasible since the following cut are added:

x s 1 f 1 n 1 u 1 + x s 2 f 1 n 2 u 1 AE 1 , 'n oe N, 'u oe V ac p (6.28)

A branch-and-cut algorithm for the NSDP

In this work, we first propose a parallelized Branch-and-Cut algorithm to solve the problem eciently. In this algorithm, referred to as Clique-based Branch-and-Cut (CBC), we build the conflict graphs in each node of the branch-and-bound tree as follows.

Physical node isolation: A node in the related conflict graph H u = (V u , E u ) is associated with every tuple (s, f, n) : s oe S, f oe F, n oe N that x ¯sf nu > 0 holds in the current solution. In addition, there exists an edge in E u between any two nodes (s, f, n) and (t, g, n) from V u if (q st ú q ts = 0) • (x ¯sf nu + x ¯tf nu > 1) holds 2 . In other words, given a fractional solution, an edge in H u exists if two functions are packed together in any node u oe V p while violating the isolation constraints imposed by the related slices.

Network function isolation: For each n oe N , a node in the related conflict graph

H n = (V n , E n )
is associated with every tuple (s, f, u) : s oe S, f oe F, u oe V p that x ¯sf nu > 0 holds in the current solution. Also, there exists an edge in E n between any two nodes (s, f, u) and (t, g, u) from V n if (q st fg ú q ts gf = 0) • (x ¯sf nu + x ¯tf nu > 1) holds.

Physical link capacity:

A node in the related conflict graph is associated with every tuple (k, f, g) :

s oe S, k oe K(s), f, g oe F that " ¯ka fg > 0 holds in the current solution. Considering di↵erent tra c generation dependencies3 and the compression coe cients of each NFS type, let b(k, f, g) be the total data flow between NFSs f and g from commodity k. There exists an edge in E a between any two

nodes u = (k, f, g) and v = (k Õ , f Õ , g Õ ) from V a if (b(k, f, g) + b(k Õ , f Õ , g Õ ) > b a ) • (" ¯k,a f ,g + " ¯kÕ ,a f Õ ,g Õ > 1)
holds.

A ROW-GENERATION FRAMEWORK FOR THE NSDP

Physical node capacity: Let w ¯sf nu and x ¯sf nu be the values of the related variables in the current solution. For each physical node u oe V , a node in the related conflict graph H u = (V u , E u ) is associated with every tuple (s, f, n) : s oe S, f oe F, n oe N that x ¯sf nu > 0 holds in the current solution. There exists an edge in E u between any two nodes u = (s, f, n

) and v = (t, g, m) from V u if w ¯sf nu x ¯sf nu c c f + w ¯tg mu x ¯tg mu c c g > c c
u holds for any physical resource c oe C.

Regarding the solution of the current LP, we run several separation routines in parallel as follow:

each available thread is responsible for creating a conflict graph from the capacity and isolation constraints, and identifying violated clique inequalities (6.12)-(6.25), as previously discussed. All cliques provided by the separation routines are found by using Bron-Kerbosch algorithm [START_REF] Bron | Algorithm 457: finding all cliques of an undirected graph[END_REF] and added as user cuts through the solver's callback procedure [START_REF] Jump | Julia for Mathematical Programming: Callbacks[END_REF].

A row-generation framework for the NSDP

We also propose the Reduced MILP-based Row-Generation (RMRG) framework, which is based on a relaxed model: the original formulation (5.1)-(5. [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF]) is reduced to a new one without the isolation, capacity, and latency constraints. Hence this new formulation has only the constraints related to the main decisions on the NSDP: the split selection inequalities (5.1), the dimensioning equations (5.2), the packing inequalities (5.3), the placement constraints (5.7) and (8.27), and the routing constraints (5.9); integrality constraints remain in the model. This reduced model can thereby be considerably smaller, having up to 98% fewer constraints compared to the original formulation; for the instances with only one element in each input set, the reduced model has 50% fewer constraints. We then denote by L the set of relaxed constraints, namely the isolation constraints (5.4)-(5.6), the capacity inequalities (5.13) and (5.19), and the latency constraints (5.10) and (5.11). During the branch-and-bound process, the Lazy Constraints routine (available in the MILP solver's callback procedure [START_REF] Jump | Julia for Mathematical Programming: Callbacks[END_REF]) is called each time the solver finds a new and better integer solution: if the current solution violates any constraint from L, it is added as cut to the reduced model. We developed a parallelized framework in which each parallel process is responsible for searching and adding the violated constraints related to a given physical node or link. The maximum latency d fg between two NFSs and the end-to-end latency ds imposed by each slice request s oe S is set respectively to between 50% and 150% and to between 250% and 500% of the average latency on the physical links.

High (H)

The maximum latency d fg between two NFSs and the end-to-end latency ds of each slice s oe S is set respectively to between 200% and 400% and to between 300% and 1000% of the average latency on the physical links.

Capacity Description Tight (T)

The available bandwidth ba on the physical links have between 50% and 100% of the average volume (without compression) generated by the slices. In addition, each physical node u oe V \V ap has enough capacity to host between 1 and 3 copies of each NFS type; application nodes has no available capacity.

Moderate (M)

The available bandwidth ba on the physical links have between 200% and 300% of the average volume (without compression) generated by the slices. In addition, each physical node u oe V \V ap has enough capacity to host between 5 and 8 copies of each NFS type; application nodes has no available capacity.

Isolation Description Weak (W)

10% of isolation parameters q st and q st fg are set to 0; they are randomly chosen. Strong (S) 75% of isolation parameters q st and q st fg are set to 0; they are randomly chosen.

Numerical experiments

We generated di↵erent instance sizes (see Table 6.1), in which the processing capacity cap(f ) of each NFS in F d was set to a value between 50% and 100% of the average volume generated by the tra c demands. For NFSs of F c , this value was set to between 50% and 100% of the volume related to the total number n s of expected UEs connected to the slice. Also, the total amount b f g of tra c

between two functions from F (s) fi G(s) was set to 1 Kbps per UE. As shown in Table 6.2, di↵erent instance classes are also proposed, which are related to the ratio between the resources required by the slices and those available on the physical network, and also between the latency on the physical links and the threshold imposed by slices and pairs of NFSs. The complete reference of each generated instance is given by joining the acronyms of each size and class name from Table 6.1 and Table 6.2.

For example, < S, L, M, S > refers to a small instance with low latency threshold, moderate capacity requirements, and strong isolation constraints. The data-set and the source code are available on [START_REF] Da | OptNSDP: source code and instances[END_REF].

6.5. NUMERICAL EXPERIMENTS stance, the average final gap on scenarios with weak and strong isolation constraints was respectively 15% (resp. 8%) and 9% (resp. 5%) on small (resp. tiny) instances. Since the possibilities of embedding NFs into physical nodes are decreased when strong isolation constraints are applied, these valid inequalities led to fewer fractional routing-related variables " in the linear relaxation: we observed up to 30% fewer variables holding values in ]0, 1[. This behavior might therefore have an important impact in selecting a branching strategy by the solver's black box in order to find integer solutions.

The proposed SB, LB, SP, and MC inequalities (6.1)-(6.8) outperformed the original model with no valid inequalities in almost all tests, specially on instances without strict latency constraints (e.g.,

< S, T, H, S >

). Together, the final gap could be reduced from 30% to 2% on < S, T, H, W > instances. It is worthwhile mentioning that the original model had its performance decreased when applied on instances with strict capacity instances: the average final gap was respectively equal to 22% and 30% on < T, T, L, W > and < S, T, H, W > instances.

Branch-and-cut algorithm

We now present the results from the numerical experiments applying the proposed CBC algorithm along with the isolation-based valid inequalities (6.12) and (6.15) (hereafter referred to as Isolation Cuts) and the capacity-based valid inequalities (6.22) and (6.25) (hereafter referred to as Capacity Cuts) to the original model (5.1)- (5.19). The separation routines were made as previously discussed and using 8 threads. Finally, SB, LB, SP, and MC inequalities (6.1)-(6.8) were not applied in these tests.

Fig. 6.3 depicts the results applying the proposed branch-and-cut frameworks. We ran 10 instances of each class and, for sake of clarity, only the average of each parameter is presented. First, both capacity and isolation cuts had smaller gaps in almost all tests, especially on instances with strict latency and capacity constraints. For instance, compared to the branch-and-bound framework without any cut, the average gap decreased from 22% to 13% (resp. from 21% to 14%) on < T, T, L, W > (resp.

< S, T, L, S >) when capacity (resp. isolation) cuts were applied (see Fig. 6.3a; resp. Fig. 6.3b). This impact is also reflected on the size of the branch-and-bound tree, in particular on tiny instances (see Fig. 6.3c): regarding all instance classes and applying either isolation or capacity cuts, the average reduction was roughly 85% on small instances (see Fig. 6.3d).

On the other hand, these cuts did not present a relevant outperformance when applied on instances without strict capacity, latency, and isolation constraints: see the results for < ≠, M, H, W > instances on both instance sizes in Fig. 6.3a and Fig. 6.3b for example. Also, due to the time required by the separation routine within the Branch-and-Cut framework, jointly applying all proposed cutting-planes increased the final gap. Regarding all instance classes and sizes, the average time spent within the separation routine was 10 times greater than when only one cut class was applied. This issue might be overcome by increasing the number of threads on the parallel searches for violated inequalities. (see Table 6.2). Instances with no feasible solution found within the time limit (i.e., 3600 seconds) are represented with a final gap equal to 100%.

Row-generation framework

We observe that RMRG outperformed BB in all graph densities. Indeed, while the RMRG model had a final gap smaller than 10% in more than 90% of all instances, RMRG+ has its performance decreased only on instances with complete mesh graphs (see Fig. 6.4d); these approaches had a similar e ciency on instances with graphs with density equals to 0.25 and 0.50 (see Fig. 6.4b and Fig. 6.4c, respectively). This behavior is expected since the separation routines within these approaches search for violated link-related constraints and, hence, the time to find them is directly proportional to the number of arcs in the graph. Moreover, the graph density has also an important impact on BB and CBC+ approaches. Since it is more di cult (resp. easier) to find a solution feasible for both mapping and routing sub-problems in sparse (resp. mesh) graphs that respect all capacity and latency constraints in the NSDP, BB had less (resp. more) than 35% (resp. 90%) of instances solved with a final gap smaller than 25% (see Fig. 6.4a; resp. Fig. 6.4d).

Summary

In this chapter, we presented and discussed the Network Slice Design Problem in 5G systems, and proposed a MILP formulation and exact algorithms to solve it. Numerical experiments showed the e ciency of each approach on di↵erent instance classes. For instance, the proposed symmetry-breaking and lower bound-based constraints led to an important decrease in the final gap: from 30% to 1% in some instances. Also, our Branch-and-Cut algorithm could reduce the size of the Branch-and-Bound tree by 85% and outperformed the solver's Branch-and-Bound algorithm in all tests. Finally, our Row-Generation framework outperformed the Branch-and-Bound approach in all tests, especially in those with sparse graphs.

Chapter 7

A math-heuristic for the NSDP The overall objective of this chapter is to go beyond the work presented in the previous chapter.

To this purpose, we propose an open-access framework based on a math-heuristic for the Network Slice Design Problem present numerical results to assess the e ciency of our approach1 . The overall idea of the proposed math-heuristic relies on decomposing the NSDP into a few sub-problems and sequentially solve them. These sub-problems are related to the following decisions: split selection, NFS-NF packing, NF-node embedding, and tra c routing. All notations follow those presented in Table 5.1.

Algorithm description

Algorithm 1 presents the global framework of our approach. As input, the heuristic receives an NSDP instance composed of a directed graph G representing the physical network with the set of capacities C, a set of slice requests S, each of which with a set of tra c demands K(s), a set F of NFS types, and a set N of potential host virtual functions. As output, Algorithm 1 returns a virtual network to each slice request s oe S ensuring all technical constraints imposed by both physical and virtual layers.

Split selection

After initializing the auxiliary variables at step 1, the first decision is made by the chooseCUs() procedure. It first calculates the minimal number of CUs to host all functions serving slices without isolation constraints: this lower-bound -is given by Equation (7.1), which considers the ratio of the most demanded physical resource by NFSs and the most critical resource on physical nodes as well as the di↵erent tra c from data and control planes.

-= ÿ f oeF c max{c c f /c c u : c oe C, u oe V ac } Ï ÿ soeS n s b f cap(f ) Ì 7.1. ALGORITHM DESCRIPTION + ÿ f oeF d max{c c f /c c u : c oe C, u oe V ac } Ï ÿ koeK(s):soeS ⁄ f ≠1 b k cap(f ) Ì (7.1)
Then, the procedure builds a set V h of -host CUs with the most centralized nodes. If it is not called for the first time, the procedure builds a new set with the nodes already chosen in previous iterations. The Closeness Centrality value cent(u) of each node u oe V ac is given by Equation (7.2), which verifies the distance dist(u, v), in terms of latency, between the node u to all other nodes in G.

cent(u) = 1 q voeV :v" =u dist(u, v) , 'u oe V (7.2)
Next, steps 3-7 are dedicated to find elementary paths to the related tra c demands of each slice request s oe S, and to select a split setting to the related data-plane flow. First, the Yen() procedure is called to find ◊ paths between the origin o k and target t k nodes of each tra c demand k oe K(s). These paths are generated by Yen's algorithm [START_REF] Yen | An algorithm for finding shortest routes from all source nodes to a given destination in general networks[END_REF] in order to find only paths that respect the end-to-end latency d s while traversing as many host CUs (those found in step 3) as possible. Since finding paths for each slice request is done independently, this procedure is run in parallel, with each thread being responsible for running Yen's algorithm on a single tra c demand. Subsequently, a path is chosen for each tra c demand by procedure choosePaths() in step 7, which seeks to maximize the number of host CUs visited by the selected paths. For this purpose, let x k p be a binary variable that takes the value 1 if path p from the set of paths P (k) is chosen to carry the flow of tra c demand k oe K(s); 0 otherwise. Also, let z uv be an integer variable corresponding to the number of active paths passing by node u oe V h before node v oe V h , with V h ™ V ac being the set of host CUs generated in step 3.

Finally, let fi uv be the associated cost of each pair of nodes u, v oe V h . In order to break the inherent symmetry of the proposed formulation, we set fi uv = 1 + 10 ≠4 and fi vu = 1 ≠ 10 ≠4 for any pair of nodes u, v oe V h . Then, the choosePaths() procedure solves the following Integer Linear Program:

max ÿ u,voeV h |u" =v fi uv z uv (7.3) ÿ poeP (k) x k p = 1 , 'k oe K(s) : s oe S (7.4) ÿ koeK(s) ÿ poeP (k) ⁄ p uv x k p = z uv , 'u, v oe V h |u " = v (7.5)
x k p oe {0, 1} , 'k oe K(s)|s oe S, 'p oe P (k) (7.6)

z uv oe N 0 , 'u, v oe V h |u " = v (7.7)

ALGORITHM DESCRIPTION

Since the aim is to share ordered data-plane NFS chains among as many tra c demands as possible, the objective function (7.3) consists in maximizing the number of chosen paths that have similar structures. For this end, Equation (7.5) calculates how many activated paths pass by node u oe V h before node v oe V h , where ⁄ p uv is an auxiliary binary parameter that holds 1 if node u oe V h comes before node v oe V h in path p, and 0 otherwise. While Equation (7.4) ensures that there is exactly one path selected to each tra c demand k, (7.6) and (7.7) are the variable domain constraints. The proposed formulation is then solved by a distributed parallel branch-and-bound algorithm [START_REF]Solving a MIP with distributed parallel optimization[END_REF] using multiple threads to solve each singular branch-and-bound tree's node.

After, a split setting is selected for each slice in step 8. For this purpose, the selectSplit() procedure verifies if there is at least one common host CU visited by the chosen path of each tra c demand k oe K(s) of a given slice s oe S. If that is the case, a split setting is randomly chosen for a random sub-set S Õ ™ S of slices requests as follows. For each slice request s oe S Õ , an NFS f oe F d is randomly chosen to be the first centralized NFS in the data-plane chain. Then, all NFSs before the chosen NFSs f in the ordered set F d are set to be distributed. The remain sub-set S\S Õ of slice requests are set to have all their data-plane NFSs centralized. On the other hand, if there is no common host CU visited by the chosen path of each tra c demand k oe K(s) of a given slice s oe S, all related data-plane NFSs are forced to be distributed, that is, they must be installed in each DU node u oe O(s). Let us recall that control-plane NFSs cannot be distributed and hence are always installed in aggregation/core nodes. Since selecting a split for each slice request is done independently, the selectSplit() is run in a parallel way, with each distributed thread being responsible for a single slice. As output, sets F dist (s) and F cent (s) are generated with the distributed and centralized network function service copies, respectively.

Network function service packing

The packNFSs() procedure (see Algorithm 2) generates copies of network functions with di↵erent NFS types in order to process the data from all slices. This decision is made by translating the related NSDP sub-problem into a Vertex Coloring Problem [START_REF] Malaguti | A survey on vertex coloring problems[END_REF]. To this end, let distGraph = (V d , E d ) be the conflict graph associated with the set of distributed NFSs as follows. A node u in V d is associated with every tuple (s, f, u) : s oe S, f oe F dist (s), u oe O(s) and there exists an edge in algorithm [START_REF] Grimmett | On colouring random graphs[END_REF]: in each iteration, a random vertex is chosen and added to the current clique if and only if it is a common neighbor.

(v, v Õ ) oe E d between any two nodes v = (s, f, u) and v Õ = (s Õ , f Õ , u Õ ) from V d if (q ss Õ ff Õ q s Õ s f Õ f = 0) ' (u " = u Õ ) holds.
In order to find a clique with maximum size, the greedy algorithm is run several times in a distributed parallel way (i.e., across multiple threads) within the getCliquesSize() procedure. The best value is then taken into consideration as lower-bounds to the related vertex coloring problem.

This translated sub-problem is then solved in step 3 by the colorGraph() procedure, which runs the randomized sequential coloring algorithm presented by Syslo [START_REF] Sys Lo | Sequential coloring versus welsh-powell bound[END_REF]. It is also run several times in a distributed parallel way and returns the best coloring (i.e., with the minimal chromatic number).

Regarding the related clique size calculated in step 2, the colorGraph() procedure stops any time an optimal coloring is found (i.e., the clique size equals to the chromatic number) or a maximal number of tries is reached. Hence, each NFSs represented by a vertex with the same color is packed in the same network function by the buildNFs() procedure in step 4.

Steps 7-15 in Algorithm 2 repeat the previous ones in order to pack the centralized NFS set, which also includes control-plane network function services. For this purpose, let centGraph = (V c , E c ) be 7.1. ALGORITHM DESCRIPTION the associated conflict graph as follows. For each centralized NFS f oe F cent (s)|s oe S, we associate a node v in V c with every tuple (s, f ). Also, let w s f oe R + be the ratio between the quantity of tra c from slice s and processed by NFS f , over its capacity cap(f ) as calculated by Equation (7.8).

w s f = Y _ _ _ _ ] _ _ _ _ [ n s b f cap(f ) if f oe F c ; q koeK(s) ⁄ f ≠1 b k cap(f ) if f oe F d . , 's oe S, 'f oe F cent (s) (7.8)
Moreover, there exists an edge in

(v, v Õ ) oe E c between any two nodes v = (s, f ) and v Õ = (s Õ , g Õ ) from V d if (max{ c c f w s f + c c f Õ w s Õ f Õ c c u : c oe C, u oe V h } > 1) ' (q ss Õ ff Õ q s Õ s f Õ f + q ss Õ q s Õ s < 2) holds. Hence,
an edge in centGraph exists in order to forbid two NFSs to be packed together in the same function n while violating capacity and isolation constraints. Since the conflict graph is built regarding only each pair of NFSs, the coloring solution calculated in step 8 must be checked: if the sum of physical capacity required by all NFSs hosted by a given NF n oe N Õ is greater than the maximal amount that any host CU can provide, another coloring for the related conflict graph must be provided if the maximal number of tries is not reached; otherwise, packNFSs() procedure will be stopped and no solution will be generated.

Network function embedding

In step 12 from Algorithm 1, each network function n oe N generated in the previous step is embedded into a physical node. A copy of each n hosting a distributed NFS f oe F dist (s) from any slice s oe S is generated and embedded into every associated DU node u oe O(s). For network functions hosting centralized data-plane NFSs, a host node is chosen as follows. Let S(n) be the set of slices from S and served by NF n oe N , and V (n) the set of host CUs among those visited by all paths p oe P (k) : s oe S(n), k oe K(s) as chosen in step 7 of Algorithm 1. Then, for each NF n hosting centralized network functions services, a host physical node is randomly chosen among those in V (n).

This procedure is repeated until an embedding that respects capacity constraints on physical nodes is found or the maximal number of tries is reached.

Tra c routing

The last sub-problem solved within Algorithm 1 is related to finding a path for each pair of physical nodes that host NF copies that must be connected. Algorithm ?? depicts our approach to 7.2. NUMERICAL EXPERIMENTS found, where rand() uniformly generates a random number between 0 and 1 and fl(t) = 1 ≠ "/t is a function depending on the time t (in seconds) that passed until such verification and a parameterizable value ". For instance, setting " to 60, the probability P (rand() Ø fl) that rand() is greater than fl is equal to 100% if t is equal to 60 seconds or less, and less than 50% (resp. 10%) if t is equal to 120 (resp. 600) seconds. If the test returns true, then another solution is generated. Otherwise, the best solution found theretofore is returned as output and the procedure stops.

Algorithm's time complexity

O(F + V ) getPaths() O(KV 4 ) choosePaths() Solver's black box's complexity selectSplit() O(SF d ) packNFSs() O(SF + V 3 + N ), V from conflict graph embedNFs() O(N ) colorGraph() O(V 2 ), V from conflict graph routing() O(V 4 ) Auxiliary Procedures Asymptotic Complexity getDistributedConflictGraph() O(SF d ) getCentralizedConflictGraph() O(SF ) getCliqueSize() O(V 4 ), V from conflict graph BuildNFs() O(N )
Table 7.1 summarizes the time complexity of each procedure within Algorithm 1, where K = q soeS |K(s)|. All other notations follow those presented in Table 5.1. Let us recall that, besides chooseCU() and embedNFs(), all procedures are able to be run in a distributed parallel way.

Numerical experiments

Let us first detail the simulation settings. We propose di↵erent instance sizes (see Table 7.2), in which we set the processing capacity cap(f ) of each NFS in F d to between 50% and 100% of the The maximum latency d fg between two NFSs and the end-to-end latency ds imposed by each slice request s oe S is set respectively to between 50% and 150% and to between 250% and 500% of the average latency on the physical links.

High (H)

The maximum latency d fg between two NFSs and the end-to-end latency ds of each slice s oe S is set respectively to between 200% and 400% and to between 300% and 1000% of the average latency on the physical links.

Capacity Description Tight (T)

The available bandwidth ba on the physical links have between 50% and 100% of the average volume (without compression) generated by the slices. In addition, each physical node u oe V \V ap has enough capacity to host between 1 and 3 copies of each NFS type; application nodes has no available capacity.

Moderate (M)

The available bandwidth ba on the physical links have between 200% and 300% of the average volume (without compression) generated by the slices. In addition, each physical node u oe V \V ap has enough capacity to host between 5 and 8 copies of each NFS type; application nodes has no available capacity.

Isolation

Description Weak (W) 10% of isolation parameters q st and q st fg are set to 0; they are randomly chosen. Strong (S) 75% of isolation parameters q st and q st fg are set to 0; they are randomly chosen.

average volume generated by the tra c demands. For NFSs of F c , this value was set to between 50% and 100% of the volume related to the total number n s of expected UEs connected to the slice. Also, the total amount b f g of tra c between two functions from F (s) fi G(s) was set to 1 Kbps per UE. As shown in Table 7.3, di↵erent instance classes are also proposed, which are related to the ratio between the resource required by the slices and those available on the physical network, and also between the latency on the physical links and the threshold imposed by slices and pairs of NFSs. The complete reference of each generated instance is given by joining the acronyms of each size/class name from tables 7.2 and 7.3. For example, < S, L, M, S > refers to a small instance with low latency threshold, moderate capacity requirements, and strong isolation constraints. We implemented our model in a Julia-JuMP environment using ILO CPLEX 12.10 as the linear solver. Our tests were run on a Linux server with an Intel Xeon E5-2650 CPU. Also, we provided 12 threads for each distributed parallel procedure. Finally, for each instance size/class, 30 di↵erent instances were randomly generated as previously discussed. The data-set and the source code are available on [START_REF] Da | A Math-Heuristic for the NSDP: source code and instances[END_REF].

Quantitative analyses

We first analyze the e ciency of the proposed Math-Heuristic. For this purpose, we compare it with the mixed-integer linear programming formulation (5. for all other sizes in our simulations. Fig. 7.1 shows di↵erent results on tiny and small instances. First, as seen in Fig. 7.1a and Fig. 7.1f, approximately 75% (resp. 70%) of all tiny (resp. small) instances were solved in less than 130 (resp. 220) seconds. We also observe that tiny (resp. small) instances with moderate (resp. tight) capacity constraints were solved faster in general. For instance, the average runtime was roughly 98 and 118

(resp. 85 and 120) seconds on < T, M, L, W > and < T, T, L, W > (resp. < S, T, L, W > and < S, M, L, W >) instance classes, respectively. While there is no strong impact on the number of feasible solutions found by the Math-heuristic on small-size instances (see Fig. 7.1g), this behavior led to an increase in the number of solutions for tiny-size instances (see Fig. 7.1b). In fact, 75% of < T, M, L, W > and < T, M, L, S > (resp. < T, T, H, W > and < T, T, L, W >) instance classes had more (resp. less) than 1700 (resp. 900) feasible solutions found within 180 seconds of execution time. Considering all instance classes, the average time needed to find a feasible solution for tiny and small instances was approximately 1 and 3 seconds, respectively. Moreover, as seen in Fig. 7.1c and Fig. 7.1h, the best solution (not necessarily the optimal one) was found in less than 300 rounds for more than 50% of all tiny and small instances. Due to greater feasible solution space, more iterations were needed for instances with moderate capacity constraints. In fact, the best solution could be found only after 800 (resp. 1000) rounds for some < T, M, L, S > (resp. < S, M, L, W >) instances. Math-heuristic and the optimal value obtained by MILP. First, we observe that more than 80% (resp 75%) of tiny-size (resp. small-size) instances had a gap smaller than 2% (resp. 4%). Also, we do not observe any strong impact on the final gap related to di↵erent instance classes. In fact, 100% of all instances solved by the Math-Heuristic had a final gap less or equal to 10%. However, the average gap of each feasible solution for tiny-size instances was better when strong isolation and strict latency constraints were applied. As seen in Fig. 7.1e and Fig. 7.1j, the average gap on < T, T, L, S > and < T, M, H, W > (resp. < S, M, L, S > and < S, T, H, W >) instances were respectively 2% and 5% (resp. 5% and 8%).

Table 7.4 shows the total execution time and final gap on medium-small, medium, medium big, big, and extra big instances. In each simulation, an instance class (i.e., a combination of capacity, latency, and isolation constraints; see Table 7.3) was randomly chosen. While the third and fourth columns of Table 7.4 are related to MILP, the two last columns depict the values when the proposed Math-Heuristic was applied. In both cases, the final gap is related to the best solution and the lower bound obtained from the linear relaxation of MILP. First, we observe that the Math-Heuristic was faster than MILP in all instance sizes. While MILP reached the time limit in almost all instance sizes, our Math-Heuristic needed less than 20 minutes to find a good solution. As seen in Table 7.4, the average gap could be reduced from 36.3% to 4.3% on medium-big instances. Moreover, while MILP could not find any feasible integer solution for big and extra big instances within 1 hour, the average runtime and final gap were respectively 997 seconds and 8.2% (resp. 1245 seconds and 11.5%) when

Math-Heuristic was applied on big (resp. extra big) instances.

Qualitative analyses

To better understand the impact of our math-heuristic on the physical network, we now analyze di↵erent parameters related to both physical nodes and physical links, as well as the end-to-end (e2e) latency on the data-plane flow. Fig. 7.2 shows the impact of each approach on the aforementioned when Math-heuristic (resp. MILP) was applied, (see Fig. 7.2a and Fig. 7.2f). However, the average load on active links remains the same on tiny instances (see Fig. 7.2b) and on small instances without strict capacity constraints (see Fig. 7.2g). Also, as seen in Fig. 7.2g, the Math-heuristic could reduce the average load on active links on small instances with strict capacity constraints, especially those with strong isolation restrictions: compared to MILP, we observe a reduction from 58% (resp. 55%) to 40% (resp. 38%) on < S, T, L, S > (res. < S, T, H, S > ) instances. Regarding all instance classes, the average reduction was approximately 16% on small instances. Finally, we observe an adverse e↵ect on the e2e latency only on small instances without strict capacity constraints applying the proposed Math-Heuristic, especially on instances without strict latency constraints. Even though all latency constraints are respected (i.e., e2e latency and between each pair of NFSs) by both approaches, the average e2e data-plane latency was respectively 0.5 ms and 2.55 ms (resp. 0.38 ms and 1.89 ms) on < T, M, H, S > and < S, M, H, W > when Math-Heuristic (resp. MILP) was applied; regarding all instance classes, the average increase on the e2e latency was equal to 14% and 25% on tiny and small instances, respectively (see Fig. 7.2c and Fig. 7.2h).

We also observe similar behavior on physical nodes. The proposed Math-Heuristic led to more nodes hosting at least one network function than the MILP formulation. As seen in Fig. 7.2i, the number of host nodes considerably increased when the Math-heuristic was applied on small instances, especially those with strong isolation constraints. For instance, the ratio of host nodes increased from 17% (resp. 17%) with MILP to 36% (resp. 27%) with Math-Heuristic on < S, T, L, S > (resp.

< S, M, L, S >) instances; regarding all instance classes, the average ratio increased by roughly 2% and 47% on tiny and small instances, respectively (see Fig. 7.2d and Fig. 7.2i). This behavior, however, led to an important decreasing in the average node load, especially on small-size instances with strict capacity and isolation constraints. As seen in Fig. 7.2j, the Math-heuristic could reduced the average load on host nodes from 41% (resp. 30%) to 18% on < S, T, L, S > (res. < S, T, H, S > ) instances.

Regarding all instance classes, the average reduction was approximately 35% on small instances (see Fig. 7.2j); we did not observe an important impact on the average load of physical nodes on tiny instances (see Fig. 7.2e).

SUMMARY

must therefore be carried out to assess the e↵ects of the proposed Math-heuristic on such scenarios and before conclusions can be drawn. Also, let us recall that, as the proposed approach is a Math-Heuristic, the optimality of the solutions found by our algorithm cannot be ensured. However, as seen in the presented numerical results, the e ciency of our approach o↵sets this aspect and led to finding solutions with a small average gap on relatively short execution time, even on big instances. Thus, it would be interesting and most probably very powerful to use it as a primal heuristic to boost the e ciency of an exact algorithm.

Chapter 8

Network slice design with dedicated network functions In this chapter, we present another variant of the NSDP, where the Hard Isolation policy is always applied, that is, all network functions are slice-dedicated (see Chapter 3 for more information). Thanks to this hypothesis, the complexity of the studied problem can be decreased, allowing us to propose di↵erent heuristic and mathematical approaches to solve the related optimization problem. However, the intra-slice anti-a nity constraints remain, which represent the possibility of packing two di↵erent NFSs into the same network function serving a given network slice. The motivation for keeping the NFS-NF mapping comes from decreasing the operational complexity related to the deployment of each NS. In other words, installing few network functions instead of several network function services allows operators to aggregate into the same entity all NFSs that share the same communication protocol or other types of a nity. Hence, the set-up step of deploying networks slices might potentially be easier and faster, reducing, therefore, operating expenses costs [START_REF] Malandrino | Reducing service deployment cost through vnf sharing[END_REF]. We refer this variant as to Network Slice Design with Dedicated Network Functions (NSDP-DNF).

A COMPACT FORMULATION FOR THE NSDP-DNF

In what follows, we present di↵erent strategies in order to e ciently solve the optimization problems related to the NSDP-DNF 1 . First, we propose a compact formulation and an extended one. To solve the former, we proposed a Relax-and-Fix heuristic that relies on repetitively solving the proposed related ILP with only a few integer variables and fixing or relaxing most of the remaining integer and binary ones. On the other hand, to address the exponential number of variables in the extended formulation, a column generation-based framework is then proposed.

A compact formulation for the NSDP-DNF

In this section, we present a integer linear programming formulation for the NSDP. The following formulation is based on those proposed on our previous Chapter 5, and presents some modifications to better address the variant of the NSDP-DNF presented in this chapter. The problem variables are therefore defined as :

• z s f oe {0, 1} that takes value 1 if NFS f is centralized, 0 otherwise,
• x sf nu oe {0, 1} that takes value 1 if NFS f serving slice s is packed into NF n, installed on node u, 0 otherwise,

• w sf nu oe Z the total number of NFSs f packed into NF n, installed on node u, and serving slice s

• y n oe {0, 1} that takes value 1 if NF n is built; 0 otherwise,

• " ka fg oe {0, 1} that takes value 1 if arc a is used to route the tra c between NFS f and NFS g for demand k, 0 otherwise.

• r a oe R + the total volume traversing arc a.

The constraints are categorized into several blocks and defined as follows :

Split Selection: The split selection constraints are to impose that if NFS f oe F d is centralized, then the remaining NFSs of the ordered set F d should also be centralized, thus defining a splitting policy Inequalities (8.3) are the anti-a nity constraints on NFs on the virtual layer. They also ensure that NF n is assigned to at most one physical node of V , while forcing the variable y to be equal to 1 if there is at least one NFSs hosted by the related network function n oe N . The objective function consists in minimizing the total cost of the NFS copies installed over the nodes of G and the number of network functions to be built. When the costs of physical resources are unitary, it allows identifying the smallest number of NFS needed to design and embed all network slice requests in a common physical infrastructure.

cap(f )w sf nu Ø Y _ _ _ ] _ _ _ [ q koeK(s)|u=o k ⁄ f ≠1 b k x sf nu if f oe F d , u oe V du n s b f x sf nu if f oe F c ; q koeK(s) ⁄ f ≠1 b k x sf nu if f oe F d ,

An extended formulation for the NSDP-DNF

In this formulation, the concept of virtual network templates is based on the definition of Network Slice Templates (NST) and Network Slice Blueprint (NSB) respectively proposed by 3GPP [START_REF] Ford | maximal flow through a network[END_REF] and NGMN [START_REF] Alliance | Description of Network Slicing Concept[END_REF]. Hence, a virtual network template contains the complete description of the structure, the configuration of contained components, and the plans/workflows for how to instantiate and control the NS instance. We extend the NST and NSB definitions to incorporate splitting, packing, and mapping decisions. For this purpose, we introduce the set G(s) of all possible virtual network templates for slice request s oe S. Moreover, let x ¯gf nu be a parameter that takes value 1 if NFS f is packed into NF n and installed on node u in virtual network template g oe G(s); 0 otherwise. Also, w ¯gf nu is the ratio between the quantity of tra c processed by NFS f , packed into NF n and installed on node u in virtual network template g, over its capacity cap(f ). Moreover, let y ¯g n be a binary parameter that takes 1 (resp. 0) if NF n is (resp. is not) built within within virtual network template g, and by r ¯g a the expect volume from virtual network template g on arc a. Finally, for each slice request, let µ s g be the cost of embedding virtual network template g oe G(s) into physical network G. This cost takes into 8.3. SOLVING APPROACHES FOR THE NSDP-DNF

Solving approaches for the NSDP-DNF

In what follows, we present di↵erent strategies in order to e ciently solve the proposed formulations related to the NSDP-DNF. First, we propose a compact formulation and an extended one. To solve the former, we proposed a Relax-and-Fix heuristic that relies on repetitively solving the proposed related ILP with only a few integer variables and fixing or relaxing most of the remaining integer and binary ones. On the other hand, to address the exponential number of variables in the extended formulation, a column generation-based framework is then proposed.

Relax-and-fix algorithm

Algorithm 6 presents the global framework of our approach. The overall idea of the proposed heuristic, hereinafter referred to as Relax-and-Fix, relies on repetitively solving the proposed ILP (8.1)-(8.17) with only a few integer variables and fixing or relaxing most of the remaining integer and binary variables. As input, the heuristic receives an NSDP-DNF instance composed of a directed graph G representing the physical network with the set of capacities C, a set of slice requests S, each of which with a set of tra c demands K(s), a set F of NFS types, a set N of potential host virtual functions, and the pacing strategy fl oe Z + . As output, it returns a virtual network to each slice request s oe S ensuring all technical constraints imposed by both physical and virtual layers.

Steps 1-6 are responsible for initiating all parameters within Relax-and-Fix. First, an auxiliary set N ú is created with only one NF in it and a model M is created following the presented ILP (8.1)- (8.17).

In order to accelerate the solving process, M is created with N ú instead of N , and Inequalities (8.3) are relaxed (i.e., they are not presented in M). Also, the integrality constraint of each variable in M is removed. In step 4, the set S of slice request is ordered following a given strategy. For instance, S might be ordered in an increasing (resp. decreasing) order in terms of end-to-end latency d s (resp. required capacity) or even in a random way. In this work, each ILP sub-problem within M is related to a slice request (and all related variables and constraints). Hence, a pace p represents how many slices should be embedded in each iteration. In other words, in each iteration, we restore integrality constraints on all variables related to p slices requests in S. Then, in step 5, p is set to the initial pacing strategy fl. Finally, an auxiliary set S ú is created in step 6 with no element. This set will represent the embedded slices after each pacing within Relax-and-Fix, that is, the slice request with Steps 7-21 are the core of our proposed algorithm. First, let IntSlices be a set of slices whose variables will be enforced to be integers in the current round. This set is built regarding the p first slice requests in S and disregarding those already embedded in previous rounds (i.e., those whose variables have fixed values). Then, in step 11, the model M is solved. In this step, the variables associated with slice requests in S, S ú , and IntSlice are respectively continuous, integer (or binary), and fixed (i.e., taking the values found in previous rounds where they were set to integer). Next, if M is feasible, steps 13-14 are responsible for fixing the values found in step 11 only on each slice request s oe IntSlices. Then, IntSlices is added to the embedded slices set S ú and p is restored to fl. If M is not feasible and S ú is not empty (i.e., there is at least one slice embedded theretofore), then the last slice request is removed from the set S ú of embedded slices, and the value of p is incremented by one unit. This last step is responsible for creating a big set IntSlices in step 8 during the next round.

SOLVING APPROACHES FOR THE NSDP-DNF

This loop stops when all slices are embedded or the instance I is proven to be unfeasible.

If a feasible solution is found, then packNFSs() procedure generates copies of network functions with di↵erent NFS types in order to process the data from all slices. This decision is made by translating the related NSDP-DNF sub-problem into a Vertex Coloring Problem [START_REF] Malaguti | A survey on vertex coloring problems[END_REF] which is summarized in Algorithm 7. First, let G c = (V c , E c ) be the conflict graph associated with the set of distributed NFSs as follows. A node v in V c is associated with every tuple (s, f, u) : s oe S, f oe F ), u oe V and there exists an edge in (v, v Õ ) oe E c between any two nodes v = (s, f, u) and

v Õ = (s Õ , f Õ , u Õ ) from V c if (q s ff Õ q s Õ f Õ f = 0) ' (u " = u Õ ) holds.
Hence, an edge in G c exists in order to forbid two NFSs to be packed together in the same network function n while violating anti-a nity packing constraints (see Inequalities (8.3)). Once the conflict graph is generated, its maximal clique size is calculated by applying the Grimmett-McDiarmid's greedy algorithm [START_REF] Grimmett | On colouring random graphs[END_REF]: in each of its iteration, a random vertex is chosen and added to the current clique if and only if it is a common neighbor to all vertices already in the clique. In order to find a clique with maximal size, the greedy algorithm is run several times in a distributed parallel way (i.e., across multiple threads). The best value is then taken into consideration as lower-bound to the related vertex coloring problem, which is then solved by running the randomized 8.3. SOLVING APPROACHES FOR THE NSDP-DNF [START_REF] Sys Lo | Sequential coloring versus welsh-powell bound[END_REF]. It is also run several times in a distributed parallel way and returns the best coloring (i.e., with the minimal chromatic number). Regarding the related clique size previously calculated, the procedure stops any time an optimal coloring is found (i.e., the clique size is equal to the chromatic number) or a maximal number of tries is reached. Hence, each NFSs f represented by a vertex with the same color is packed into the same network function n.

Algorithm analysis

While Algorithm 6 is mainly driven by the solver's black box's time complexity, Table 8.1 depicts the complexity related to each inner procedure in Algorithm 7. In what follows, we present en discuss some important features of the proposed Relax-and-Fix algorithm. Proof. If the pace p is equal to the number of slices requests in set S, then IntSlices will be equal to S in the next round. Hence, the integrality constraints will be enforced to all variables in M. As it can only happen if there is no slice with fixed variables (see steps 17-19 in Algorithm 6) and applying the well-known Duality Theorem [START_REF] Bachem | Linear programming duality[END_REF], it is clear that if M is not feasible, then no feasible solution exists to I.

As a direct implication of Theorem 8.3.1, we have the following corollary: Corollary 1. Relax-and-Fix always returns a feasible solution to M if there exists at least one.

Proof. The proof is trivial, since that Relax-and-Fix will solve M enforcing the integrality constraints on all variables of the model in the worst case (i.e., IntSlice set is equal to set S of slice requests). Theorem 8.3.2. If S ú is empty and I is feasible, then the solution found to M is a lower-bound to ILP (8.1)-(8.17).

NUMERICAL EXPERIMENTS

negative, then the generated virtual network template is added to G Õ (s) and the new RMP is solved with the new columns. These last steps are repeated until no column is generated from any PSP(s*).

Finally, the ILP related to the RMP, with all generated columns and the integrality constraints (8.23), is then solved.

Note that this framework gets as input a minimal sub-set G Õ (s) for each slice request. The construction of such sub-sets that ensure a feasible solution for the NSDP-DNF instance I is made in pre-processing.

Numerical experiments

Let us first detail the simulation settings. We propose di↵erent instance sizes (see Table 8.2), in which we set the processing capacity cap(f ) of each NFS in F d to between 50% and 100% of the average volume generated by the tra c demands. For NFSs of F c , this value was set to between 50% and 100% of the volume related to the total number n s of expected UEs connected to the slice. Also, the total amount b f g of tra c between two functions from F (s) fi G(s) was set to 1 Kbps per UE. As shown in Table 8.3, di↵erent instance classes are also proposed, which are related to the ratio between the resource required by the slices and available on the physical network, and also between the latency on the physical links and the threshold imposed by slices and pairs of NFSs. The complete reference of each generated instance is given by joining the acronyms of each size/class name from tables 8.2 The maximum latency d fg between two NFSs and the end-to-end latency ds imposed by each slice request s oe S is set respectively to between 50% and 150% and to between 250% and 500% of the average latency on the physical links.

High (H)

The maximum latency d fg between two NFSs and the end-to-end latency ds of each slice s oe S is set respectively to between 200% and 400% and to between 300% and 1000% of the average latency on the physical links.

Capacity Description Tight (T)

The available bandwidth ba on the physical links have between 50% and 100% of the average volume (without compression) generated by the slices. In addition, each physical node u oe V \V ap has enough capacity to host between 1 and 3 copies of each NFS type; application nodes has no available capacity.

Moderate (M)

The available bandwidth ba on the physical links have between 200% and 300% of the average volume (without compression) generated by the slices. In addition, each physical node u oe V \V ap has enough capacity to host between 5 and 8 copies of each NFS type; application nodes has no available capacity.

Isolation Description Weak (W)

10% of anti-a nity parameters q s fg are set to 0; they are randomly chosen. Strong (S) 75% of anti-a nity parameters q s fg are set to 0; they are randomly chosen. and 8.3. For example, < S, L, M, S > refers to a small instance with low latency threshold, moderate capacity requirements, and strong isolation related to a nity constraints. We implemented our model in a Julia-JuMP environment using ILO CPLEX 12.10 as the linear solver. Our tests were run on a Linux server with an Intel Xeon E5-2650 CPU. Also, we provided 12 threads for each distributed parallel procedure. Finally, for each instance size/class, 30 di↵erent instances were randomly generated as previously discussed.

Compact formulation and relax-and-fix algorithm

We first analyze the e ciency of the proposed Relax-and-Fix algorithm. For this purpose, we compare it with the compact formulation (8.1)-(8.17) formulation, hereafter referred to as to ILP, introduced in this chapter. In these tests, we set the time limit to 3600 seconds (one hour). For 8.4 are related to random slice ordering and the 1-slice pacing strategy. First, we observe that the Relax-and-Fix was faster than ILP in all instance sizes. For instance, ILP reached the time limit on medium small-size instances and bigger ones, while our proposed Relax-and-Fix needed less than 20 minutes to solve any instance size. Indeed, we observed that approximately 90% of medium-small (resp. small) instances were solved in less than 1 (resp. 120) seconds. As seen in Table 8.4, the average gap could also be reduced from 82.8% to 4.31% (resp. 48.4% to 5.77%) on medium-big (resp. medium) instances. It is worth mentioning that 50% of medium instances had a gap smaller than 25%, and any feasible solution was found within 1-hour runtime for roughly 20% of medium-small instances. Moreover, while ILP could not find any feasible integer solution within

1-hour runtime for any big-size instance, the average runtime and final gap were respectively 907 seconds and 5.2% when Relax-and-Fix was applied on the same instances.

Fig. 8.1 shows the influence of di↵erent instance classes on the e ciency of our approach (random slice ordering and 1-slice pacing strategy were applied in all tests). Regarding all 32 possible combinations, we observe a moderate impact only on tiny and small instances (see Fig. In what follows, we analyze the response of the Relax-and-Fix algorithm to di↵erent pacing and ordering strategies. To this purpose, we proposed three slice ordering strategies, which is responsible to chose the order of slices having the integrality constraints restored on the related variables (see steps 4 and 8-10 in Algorithm 6): by capacity (i.e., decreasing order of ratio between the capacity required by the slice and those available on the physical network), by latency (i.e., increasing order accepted latency on the data-plane function chain), and randomly. We also implemented di↵erent pacing strategies (from 1 to 4), which, in turn, is related to how many slices have their variables enforced to be integer on each iteration of our approach (see steps 5, 8, and 10 in Algorithm 6). For each combination ordering/pace, the average and the 95% confidence interval related to 100 instances are presented. These instances were randomly chosen among those generated with di↵erent sizes and classes (see Tables 8 (resp. 6.92% ) to 1.25% (resp. 0.40%) on medium-small (resp. medium) instances when latency (resp. random) ordering strategy was applied. Regarding all ordering strategies, the overall reduction on medium-big instances was approximately 22% from 1-slice pacing to 2-slice pace, 55% from 2-slice pacing to 3-slice pace, and 30% from 3-slice pacing to 4-slice pace.

In general, the runtime increases as the pacing strategy gets bigger. Indeed, the time needed to find the final solution by our approach increased from 270 seconds with 1-slice pacing to 490 seconds with 2-slice pacing on medium-big instances when capacity ordering strategy was applied (see Fig. 8.2g). We observe an even bigger increase from 3-slice pacing to 4-slice pacing in smaller instances (see Fig. 8.2e and Fig. 8.2f): in general, the runtime increased by 121% and 88% on medium small and medium instances, respectively. This behavior is expected since, even with fewer iterations (see the loop from steps 7-21 in Algorithm 6), the number of integer variables are considerably bigger on pacing strategies with more slices, which has a well-known strong influence on the branch-and-bound performed by the solver. This e↵ect is even more noticeable on big-size instances (see Fig. ) and no physical capacity required. As previously discussed, our pricing sub-problem is based on the compact formulation (8.1)-(8.17), hereafter referred to as to CF, where S = {sú} and whose objective function (8.11) is replaced by (8.30). We refer this approach as to AT-CG. For each pricing iteration, we set the time limit to 3600 ≠ seconds, where is the time elapsed theretofore. Finally, for each instance size, 30 random instances were generated as previously discussed (see Tables 8.2 and 8.3). Table 8.5 depicts the result of our numerical experiments applying the proposed column generation framework on di↵erent instance sizes. For each approach, we present the linear relaxation gap 2 , the final gap 3 , the total runtime (in seconds), and the number of pricing iterations done before finding the best solution (only for the column generation-based approaches).

First, the final gap was substantially improved by the RF-CG on bigger instances. On mediumsmall and big instances, for example, the average reduction related to the CF was roughly 96% and 88%. This approach was also 96% (resp. 58%) faster than CF on tiny (resp. medium) instances and 44% faster than the AT-CG on average. In addition, while AT-CG could not find any feasible solution in less than 3600-second runtime on medium-big and big instances, RF-CG could improve the initial solution (i.e., those found by the relax-and-fix algorithm) in almost all instance sizes. Indeed, due 2. Calculated as the absolute value of the ratio between the found solution of the relaxed model and the best-known lower-bound, calculated as previously discussed.

3. Calculated as the absolute value of the ratio between the found solution of the related model with all integrality constraints and the best-known lower-bound, calculated as previously discussed. 31%) fewer pricing iterations on tiny (resp. small) instances compared to AT-CG.

SUMMARY

Moreover, we observe that the linear relaxation solutions of both CG-based frameworks were considerably better than those found by the compact formation: the average gap related to the bestknown lower-bound could be reduced from roughly 22% (resp. 38%) to 0.4% (resp. 15%) on small (rep. medium-big) instances after less than 5 pricing iterations. It is important to mention that, the small number of pricing iterations on di↵erent instance sizes is due to di↵erent reasons. Indeed, while tiny and small instances could be solved in few iterations thanks to the quality of generated columns and the starting point (using the solution found by the relax-and-fix framework) on RF-CG, AT-CG instances could not be solved all potential pricing sub-problems to the optimality due to the time limit for bigger instances. For instance, the average gap of the last pricing iteration was approximately 13%

(resp. 22%) on medium-big (resp. big) instances when the RF-CG was applied; these gaps were respectively 16% and 21% applying AT-CG. It is also worthwhile mentioning that we did not observe any significant improvement by changing the gap tolerance in the pricing routine since the solver spent a considerable amount of time on improving the dual bound in general on each pricing sub-problem.

Summary

In this chapter, we presented another variant of the NSDP, called Network Slice Design with Dedicated Network Functions, where the Hard Isolation policy is always applied, that is, all network 8.5. SUMMARY functions are slice-dedicated, keeping, however, the intra-slice anti-a nity constraints, which represent the possibility of packing two di↵erent NFSs into the same network function serving a given network slice. The motivation for keeping the NFS-NF mapping comes from decreasing the operational complexity related to the deployment of each NS. We then presented di↵erent strategies in order to e ciently solve the optimization problems related to the NSDP-DNF. First, we proposed a compact formulation and an extended one. To solve the former, we proposed a Relax-and-Fix heuristic that relies on repetitively solving the proposed related ILP with only a few integer variables and fixing or relaxing most of the remaining integer and binary ones. On the other hand, to address the exponential number of variables in the extended formulation, a column generation-based framework was then proposed.

In our simulations applying the proposed RF algorithm, for example, the average gap could be reduced from 82.8% to 4.31% (resp. 48.4% to 5.77%) on medium-big (resp. medium) instances for instance. Moreover, while ILP could not find any feasible integer solution within 1-hour runtime for any big-size instance, the average runtime and final gap were respectively 907 seconds and 5.2% when Relax-and-Fix was applied on the same instances. Regarding the column generation-based framework, this approach could improve the gap in all instances sizes, especially when the solution found by the RF algorithm was given as starting point. For instance, the gap and the runtime could be reduced by 96%.

problem were also considered and the proposed models are compliant with running standards. We demonstrated by numerical analyses the impact of taking into full and partial consideration of the peculiar constraints rising from the standards. For instance, we reported numerical results showing that flexible splitting appears as a key factor to deal with heterogeneous requirements to deploy distinct communication services, leading to considerable network slice cost decrease. In our simulations, the number of NFSs needed to deploy the virtual networks could be reduced by up to 56% depending on which of the six proposed sharing policies is applied to each network slice. We also observed that di↵erent variants related to the flexible splitting have an important impact on the physical network; depending on the selected approach, the average load on physical links could be reduced by a factor of 3.

In order to strengthen the linear relaxation of the proposed MILP, we presented several classes of valid inequalities and integrate them into a Branch-and-Cut framework to solve the problem. We further present several strategies to reduce the symmetries and the size of the model. Numerical experiments showed the e ciency of each approach on di↵erent instance classes. For instance, the proposed symmetry-breaking and lower bound-based constraints led to an important decrease in the final gap: from 30% to 1% in some instances. Also, our Branch-and-Cut algorithm could reduce the size of the Branch-and-Bound tree by 85% and outperformed the solver's Branch-and-Bound algorithm in all tests. Finally, our Row-Generation framework outperformed the Branch-and-Bound approach in all tests, especially in those with sparse graphs.

Moreover, to address the time complexity related to the proposed exact approaches, we presented an open-access framework based on a Math-heuristic to address the underlying optimization problem.

The overall idea of the proposed approach relied on decomposing the NSDP into several sub-problems and sequentially solve them while encompassing control-plane and data-plane separation and novel mapping and decomposition dimensions influencing the placement and interconnection of slices. Numerical experiments showed the e ciency of our approach on di↵erent instance classes, which could attain near-optimal solutions in a competitive runtime. Comparing it to a mixed-integer linear programming formulation, the proposed Math-Heuristic could reduce the average runtime and the final gap by up to 78% and 90%, respectively. Moreover, our approach could reduce the congestion on the physical network, better balancing the data flow while considering all technical constraints. For instance, the average load on physical links and physical nodes could be reduced by 16% and 35%, respectively.

We also studied the variant NSDP-DNF, where the Hard Isolation policy is always applied, that is, all network functions are slice-dedicated, ensuring however the intra-slice anti-a nity constraints, which represent the possibility of packing two di↵erent NFSs into the same network function serving a given network slice. We then proposed di↵erent strategies in order to e ciently solve the optimization problem. First, we presented a compact formulation and an extended one. To solve the former, we proposed a Relax-and-Fix heuristic that relies on repetitively solving the proposed related ILP with only a few integer variables and fixing or relaxing most of the remaining integer and binary ones. On the other hand, to address the exponential number of variables in the extended formulation, a column generation-based framework is then proposed. In our simulations applying the proposed Relax-and-Fix approach, for instance, the average gap could be reduced from 82.8% to 4.31% (resp. 48.4% to 5.77%) on medium-big (resp. medium) instances. Moreover, while ILP could not find any feasible integer solution within 1-hour runtime for any big-size instance, the average runtime and final gap were respectively 907 seconds and 5.2% when Relax-and-Fix was applied on the same instances. Regarding the column generation-based framework, this approach could improve the gap in all instances sizes, especially when the solution found by the RF algorithm was given as starting point. For instance, the gap and the runtime could be reduced by 96%.

On a practical note, a tough but interesting extension of our work related to the DCP is to include users' mobility and temporal aspect in radio resource assignment. Indeed, managing handovers is highly expected in real scenarios, which might potentially imply an important reconfiguration of the created domains in every short time period (i.e., minutes or even seconds). Also, other variants of the NSDP can be studied (e.g., applying Multi-Access Edge Computing) and a service-aware function objective might be proposed. In other words, di↵erent parameters might alternatively be optimized regarding the service related to each network slice (e.g., latency over capacity). Finally, an extension of our work on network slicing might also include availability constraints in order to ensure all technical constraints that are expected in the Service Level Agreements.

We also expect to embed the proposed column generation-based algorithm into a branch-and-price framework to ensure the optimal solution for each instance. On the other hand, in order to address the time complexity related to the column generation-based algorithm proposed to the NSDP-DNF, heuristic-based pricing algorithms might be proposed in order to attain near-optimal solutions in a competitive runtime. Finally, applying clustering algorithms as pre-processing might also be a powerful approach to be applied in a distributed parallel programming, in which each thread might be responsible for solving smaller NSDP or DCP instances. For instance, such clustering algorithms can be based on geographical zone or even on service a nity.

Chapter 1

Résumé de Thèse

Le problème Network Slice Design

Le système 5G couvre désormais non seulement l'abstraction de slice au niveau de l'application comme cela a été fait avec les travaux préliminaires sur le 'slicing', mais aussi la virtualisation des Abstract : Every second, a large amount of digital data is transported through cellular networks worldwide, and expectations are at a greatly accelerated growth with increasingly large requests. In few years, these networks could thereby reach their maximum capacities in terms of data transmission. To face these challenges, Network Slicing has been presented as a novel virtualized infrastructure for the new generation cellular network system. This technology now not only covers application-level abstraction but also physical and switching layers virtualization, with di↵erent radio access and link communication technologies. Hence, each service provider is to be able to deploy its communication services on top of logical networks, named Network Slices, specifically tailored to its technical requirements. The Device-to-Device communication mode is another approach presented as a promising alternative to traditional communication in cellular networks. This technology allows to reuse radio resources and to decrease the end-to-end latency of local communications. Consequently, the optimization of physical resources in cellular networks becomes crucial to better deploy virtual networks. The overall objective of this work is therefore to define and study the concept of device-to-device communication and network slice design in 5G systems, and propose mathematical models and innovative algorithms to solve the underlying optimization problems.

Keywords: Optimization, Network Design, Network Slicing, Device-to-Device

1

 1 Pour faire face ces défis, Network Slicing a été présenté comme une nouvelle infrastructure virtualisée pour le système de réseau mobile de nouvelle génération. Cette technologie couvre désormais non seulement le niveau des applications, mais également la virtualisation des couches physiques et de commutation, avec di↵érentes technologies d'accès radio. Ainsi, chaque fournisseur de services doit pouvoir déployer ses services et applications sur des réseaux logiques, appelés Network Slices, spécifiquement adaptés à ses exigences techniques. Le mode de communication Device-to-Device est une autre approche présentée comme une alternative prometteuse à la communication traditionnelle dans les réseaux cellulaires. Cette technologie permet de réutiliser les ressources radio et de diminuer la latence de bout en bout des communications locales. Par conséquent, l'optimisation des ressources physiques dans les réseaux cellulaires devient cruciale pour mieux dimensionner et déployer les réseaux virtuels. L'objectif global de ce travail est donc de définir et d'étudier le concept de Device-to-Device Communication et Network Slice Design dans les systèmes 5G, en proposant des modèles mathématiques et des algorithmes innovants pour résoudre les problèmes d'optimisation sous-jacents. Mots-clés : Optimisation, Conception de réseau, Découpage réseau en tranches, Communication d'appareil à ap-Graphical method and Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.2 Linear relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.3 The branch-and-bound framework . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.4 Cutting planes and branch-and-cut algorithm . . . . . . . . . . . . . . . . . . . 2.3.5 Column generation and the branch-and-price algorithm . . . . . . . . . . . . . 2.3.6 Heuristic methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 A view on the telecommunications network evolution 3.1 Core network evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 From 3G to 4G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.2 Separating 4G core with CUPS . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.3 From 4G to 5G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 5G core specificities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Customized service-based network functions . . . . . . . . . . . . . . . . . . . . 3.2.2 Auto-scaling and distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.3 The user-plane case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.4 Functional splitting in the radio access network . . . . . . . . . . . . . . . . . . 3.3 Device-to-device communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 5G system mapping requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.1 Mapping NF services into network functions . . . . . . . . . . . . . . . . . . . . 3.4.2 Mapping network functions into slices and slice subnets . . . . . . . . . . . . . 3.4.3 Mapping slices subnet into slices . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.4 Mapping slices into communication services . . . . . . . . . . . . . . . . . . . . 3.4.5 Mapping communication services into user equipment . . . . . . . . . . . . . . 3.5 Sharing policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . LIST OF TABLES 7.4 Quantitative analyses: from medium small to extra big instances . . . . . . . . . . . . 8.1 Time Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 Instance Sizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3 Instance Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.4 Relax-end-Fix: gap and runtime on di↵erent instances sizes. . . . . . . . . . . . . . . . 8.5 Column Generation-based framework: gap and runtime on di↵erent instances sizes. . . List of Figures 1.1 Contributions and manuscript organization. . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Representation of a graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Interaction between the restricted master problem and the sub-problem . . . . . . . . 3.1 3GPP Network Core function evolution: from 3G to 5G. . . . . . . . . . . . . . . . . . 3.2 Service-based interactions between network functions. . . . . . . . . . . . . . . . . . . 3.3 Di↵erent functional split options. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Functional split example with four RAN NFs. . . . . . . . . . . . . . . . . . . . . . . . 3.5 Representative use-cases of D2D communications in cellular networks. . . . . . . . . . 3.6 Resource allocation prodedure for D2D UEs . . . . . . . . . . . . . . . . . . . . . . . . 3.7 Relationships between 5G entities. Source: [1]. . . . . . . . . . . . . . . . . . . . . . . 3.8 Interactions between Slice and Slice Subnet Instances. . . . . . . . . . . . . . . . . . . 3.9 NF sharing policies. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Example of a network with 6 nodes and 6 demands to be delivered for 2 di↵erent services 4.2 Feasible solution: active links and associated radio resource for Gaming domain (left) and Video streaming domain (right) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Simulated Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 Example of a solution for an NSDP instance. . . . . . . . . . . . . . . . . . . . . . . . Chapter 1

Figure 1 . 1 -

 11 Figure 1.1 -Contributions and manuscript organization.

Figure 1 .

 1 Figure 1.1 summarizes our contributions and the organization of this manuscript.

2. 1 .Figure 2 . 1 -

 121 Figure 2.1 -Representation of a graph

2. 3 .Figure 2 . 2 -

 322 Figure 2.2 -Interaction between the restricted master problem and the sub-problem

Control

  Plane function (SGW-C) and Serving Gateway User Plane function (SGW-U). Equally, PDN-GW is split into PDN Gateway Control plane function (PGW-C) and PDN Gateway User Plane function (PGW-U). While SGW-C and PGW-C are responsible for controlling the processing of data that transverse User Plane functions, SGW-U and PGW-U implement specific features for a certain group of users, such as low latency or high bandwidth, to ensure Quality of Service (QoS). 3GPP has also proposed to split Tra c Detection Function (TDF) into CP and UP entities. TDF is part of PCC block [51] and is responsible for improving the operator's charging functions. With CUPS, TDF becomes TDF User Plane (TDF-U) and TDF Control Plane (TDF-C) functions.

3. 1 .

 1 Figure 3.1 -3GPP Network Core function evolution: from 3G to 5G.

Figure 3 . 2 -

 32 Figure 3.2 -Service-based interactions between network functions.

Figure 3 . 3 -

 33 Figure 3.3 -Di↵erent functional split options.

Figure 3 .

 3 Figure 3.4 represents a scenario with di↵erent split options with two operators and a RAN function chain composed of four NFs. In this example, the split between NF 1 and NF 2 is applied to treat the flow from DU 3 and DU 4. These two DUs have only NF 1 installed locally and send their flow to CU 2, which has NF 2, NF 3, and NF 4. Note that these functions in CU 2 are shared by both DU 3 and DU 4.

Figure 3 . 4 -

 34 Figure 3.4 -Functional split example with four RAN NFs.

3. 3 .Figure 3 . 5 -

 335 Figure 3.5 -Representative use-cases of D2D communications in cellular networks.

Figure 3 .

 3 5 illustrates the advantages and uses of D2D communication. D2D communication can be divided into two groups: Inband D2D and Outband D2D. The former proposes the use of licensed spectrum [66]. It is further subdivided into Underlay D2D Inband, where both D2D communication and classical cellular communication can share all licensed spectrum range, 3.3. DEVICE-TO-DEVICE COMMUNICATIONand Overlay Inband D2D, in which the spectrum range is divided into two and each part is dedicated to only one type of communication. On other hand, Outband D2D proposes to use unlicensed spectrum[START_REF] Jeon | Lte in the unlicensed spectrum: Evaluating coexistence mechanisms[END_REF]. It is also further subdivided into two others sub-categories: Controlled Outband D2D, in which coordination between radio interfaces is controlled by the Base Station, and Autonomous

3. 4 .Figure 3 . 6 -

 436 Figure 3.6 -Resource allocation prodedure for D2D UEsSource:[START_REF] Chae | Radio resource allocation scheme for deviceto-device communication in cellular networks using fractional frequency reuse[END_REF]

Figure 3 . 7 -

 37 Figure 3.7 -Relationships between 5G entities. Source: [1].

Figure 3 . 8 -

 38 Figure 3.8 -Interactions between Slice and Slice Subnet Instances.

Fig. 3 .

 3 8 illustrates this concept and depicts a possible mapping for di↵erent Communication Services. Note that service -is serviced by NSI A, while service -is mapped to NSI B. In this example, NSSI 2 is a shared entity and is serving both NSI A and NSI B. From a holistic point of view, NSSI 2 can be interpreted as an access network serving two cores (NSSI 1 and NSSI 3), or the other way around, for example.Given the expected data volume from each UE connected to each antenna and the processing capacity of each NF, it is important to predict how many instances of each function type should be installed for each network slice. Moreover, dimensioning strategies have to model how NFs relate to di↵erent slices.

4 . 5 . 6 .

 456 Partial Control-Plane Isolation: only a part of the CP, called common CP (C-CP), is shared by two CSs; a CP portion and entire DPs of each CS are dedicated. Shared Data-Plane: CSs share the same Data-Plane while having their own and dedicated Control-Planes (D-CPs). Partial Data-Plane Isolation case: only a part of the DP is shared by two CSs, named common DP (C-DP); a DP portion and entire CPs of each CS are dedicated.

Contenu 4 . 1

 41 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Related works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 A mathematical formulation for the DCP . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 Notations and formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2 Symmetry-breaking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.3 Valid inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 A branch-and-cut algorithm for the DCP . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 A 2-phase heuristic for the DCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5.1 Routing sub-problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5.2 Resource allocation sub-problem . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6 Computational results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6.1 Branch-and-cut and symmetry-breaking constraints . . . . . . . . . . . . . . . 4.6.2 2-phase heuristic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 .

 1 The content of this chapter was published in the following paper: Benhamiche, Amal, Wesley da Silva Coelho, and Nancy Perrot. "Routing and Resource Assignment Problems in Future 5G Radio Access Networks." International Network Optimization Conference. 2019.

4. 1

 1 Figure 4.1 -Example of a network with 6 nodes and 6 demands to be delivered for 2 di↵erent services

Figure 4 . 2 -

 42 Figure 4.2 -Feasible solution: active links and associated radio resource for Gaming domain (left) and Video streaming domain (right)

4. 5 .

 5 A 2-PHASE HEURISTIC FOR THE DCP 4.5 A 2-phase heuristic for the DCP Since solving the initial formulation (4.1)-(4.9) presented in the previous chapter has impractical runtime even for small instances, we propose a solving method based on a decomposition of the DCP into two sub-problems: the routing sub-problem and the resource allocation sub-problem, that are to be solved separately. The objective of the first sub-problem is to find an elementary path for each demand while minimizing the total link utilization costs. Then, the second sub-problem provides a resource allocation to each active link obtained from the routing sub-problem solution.

4. 5 .

 5 A 2-PHASE HEURISTIC FOR THE DCP vertices if the corresponding active links cannot share the same radio resource due to interference (steps 6-12). The objective is to assign a minimum number of colors (resources) to the vertices of the graph G a , in such a way there are no adjacent vertices with the same color (step 14). This falls into a classical Vertex Coloring Problem [93].

4. 6

 6 Figure 4.3 -Simulated Network.

Contenu 5 . 1

 51 Problem statement and notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.1 Physical network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.2 Network function services . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.3 Network slice requests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.4 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Related works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Mathematical programming formulation . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Variants and extensions for the NSDP . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5.1 NDSP with intra-slice flexible splitting . . . . . . . . . . . . . . . . . . . . . . . 5.5.2 NDSP with inter-slice split continuity . . . . . . . . . . . . . . . . . . . . . . . 5.5.3 NSDP with optimized link load . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6 Sensibility analyses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6.1 Simulation setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6.2 Numerical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  Set of all NFs. C set of resource types available on physical nodes Parameter Description c c u amount of available resource c on node u. µ c u cost of one unit of resource c provided by node u. ba bandwidth value on arc a. da delay value on arc a. c c f amount of resource c required by NFS f . cap(f ) tra c processing capacity of NFS f . b fg total amount of tra c generated between NFSs f and g by an UE. b f expected data rate of NFS f given one UE. d fg the maximum accepted delay between NFSs f and g. ⁄ f compression coe cient of NFS f .

  a NFS type f must be present in slice s; 0 otherwise. q st fg holds 1 if slice s admits sharing a NFS of type f with a NFS of type g of slice t; 0 otherwise.q st equalsto 1 if slice s admits sharing physical node with slice t; 0 otherwise. ÷s expected number of UEs connected to slice s ds maximum accepted delay on data plane of slice s. o k origin node of demand k t k target node of demand k b k expected volume of data between sent by origin node of demand k.denoted by C = {c 1 u , . . . , c c u }, corresponding to the types of physical resources, on any node type, and a cost per unit of resource usage c oe C, noted µ u > 0. Each arc a = (u, v) oe A represents a physical link connecting nodes u and v oe V , and is characterized by a bandwidth capacity b a and a latency value d a .

Figure 5 . 1 -

 51 Figure 5.1 -Example of a solution for an NSDP instance.

Fig. 5 .

 5 Fig. 5.1 shows an example of how to design di↵erent slices and embedding them into a physical network. In this example, we consider 2 slices, 5 tra c demands (e.g., from NS 2: distributed unit 23 ae application node 16), 7 NFS types (3 for data-plane and 4 for control-plane), 8 NFs, and a physical network with 23 nodes (6 DUs, 12 aggregation/core nodes representing CUs, and 5 application nodes).

. 1 )

 1 Network Function Services Dimensioning and Packing: Equalities (5.2) are to define variables w directly as a function of x variables, while inequalities (5.3) force to install enough NFS to process all the tra c. Inequalities (5.4) and (5.5) are the isolation constraints, respectively on NFs and on physical nodes. Finally, constraints (5.6) ensure that NF n is assigned to at most one physical node 5.3. MATHEMATICAL PROGRAMMING FORMULATION of V .

8 )

 8 Tra c routing: The constraints (5.9) are the flow conservation constraints, for each slice request s oe S, each demand k oe K(s) and each pair of NFSs in F . They allow to associate a path in G for each tra c demand k between its origin node o k and the first NFS f = 1 from the ordered set F d and serving k, and between the last NFS f = |F d | from F d and the destination node t k of k.

Figure 5 . 2 -

 52 Figure 5.2 -Physical network structures: examples with 16 DUs.

Fig. 5 .Figure 5 . 3 -

 553 Fig. 5.4 reports the average number of distributed and centralized NFSs on di↵erent sharing policies and split strategies for the three aforementioned physical topologies merged together (i.e., in the same results set here). While distributed entities are only NFSs from DP, centralized ones also aggregate NFSs from CP; translucent bars show the total number of installed NFSs. Note first that the generated instances' characteristics are such that:

Figure 5 . 4 -

 54 Figure 5.4 -Number of NFSs on di↵erent scenarios.

Figure 5 .

 5 Figure 5.6 shows the mean and the standard deviation of each depicted parameter. Minimizing the load on physical links generally increased the number of NFSs installed throughout the network (see Figures 5.6a and 5.6b) and the number of physical nodes hosting an NF (see Fig. 5.6h); regarding all

Figure 5 . 6 -

 56 Figure 5.6 -Impact of di↵erent NSDP variants on the physical network.

Contenu 6 . 1

 61 Symmetry-breaking constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 6.2 Valid inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 6.2.1 Lower-bound inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 6.2.2 Shortest path-based inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 6.2.3 Minimum cut-based inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 6.2.4 Clique-based inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 6.3 A branch-and-cut algorithm for the NSDP . . . . . . . . . . . . . . . . . . . . . . . . 122 6.4 A row-generation framework for the NSDP . . . . . . . . . . . . . . . . . . . . . . . . 123 6.5 Numerical experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 6.5.1 Model strengthening . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 6.5.2 Branch-and-cut algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 6.5.3 Row-generation framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 6.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

6. 2 .

 2 VALID INEQUALITIES (a) Without SP valid inequality. (b) With SP valid inequality.

Figure 6 . 1 -

 61 Figure 6.1 -An example of applying the shortest path-based (SP) valid inequality.

Figure 6 . 2 -

 62 Figure 6.2 -An example of applying the minimum cut-based valid inequality.

Proof.

  Let C be a clique in C(H n ). If two tuples (s, f, u) and (t, g, v) from C are mapped to a same network function n oe N , the related isolation constraints (5.4) will be violated. I other words, each pair of tuples from clique C represents an infeasible packing of NFSs from di↵erent slices requests in an NF n oe N . Consequently, a clique in the graph H n corresponds to a set of NFS that cannot be simultaneously packed in any network function n oe N .

C

  (H a ) be the set of all cliques on H a . Then, the following inequalities ÿ (k,f,g)oeC " ka fg 6 1 'a oe A, 'C oe C(H a ) (6.22) are valid for the NSDP. Proof. Let C be a clique in C(H a ). If the flow of two pairs (k, f, g) and (k Õ , f Õ , g Õ ) from C are carried through a same physical link a oe A p , the related capacity constraint (5.12) will be violated. I other words, each pair of nodes from clique C represents an infeasible routing from di↵erent tra c demands in a physical link a oe A p . Consequently, a clique in the graph H a corresponds to a set of tra c demands that cannot be carried simultaneously through physical link a. Example: Consider a small instance with one slice requests s 1 with two tra c demands {k 1 , k 2 }, one DP NFS type f 1 , f 2 , and several physical arcs {a 1 , .., a |Ap| } in the physical network. For this instance, we also have b a = 15 for any a oe A p and b k 1 = b k 2 = 10

Figure 6 . 3 -

 63 Figure 6.3 -Impact of di↵erent cutting-planes.

Fig. 6 .Figure 6 . 4 -

 664 Fig. 6.4 depicts the cumulative distribution function (CDF) from the tests applying the proposed RMRG framework. The search of violated cuts from the set L of lazy constraints was done as previously discussed and added using 8 parallel threads. While BB refers to the formulation (5.1)-(7.9) solved by the solver's Branch-and-Bound, CBC+ and RMRG+ are respectively CBC and RMRG approaches along with SB, LB, SP, and MC inequalities (6.1)-(??) and both isolation and capacity-cut classes. Finally, we generate 40 medium-size instances varying the graph density from 0.10 to 1.00

Contenu 7 . 1 132 7. 1 . 1 132 7. 1 . 2

 711321113212 Algorithm description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Split selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Network function service packing . . . . . . . . . . . . . . . . . . . . . . . . . . 134 7.1.3 Network function embedding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 7.1.4 Tra c routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 7.1.5 Final solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 7.1.6 Algorithm's time complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 7.2 Numerical experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 7.2.1 Quantitative analyses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 7.2.2 Qualitative analyses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 7.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

7. 1 .

 1 ALGORITHM DESCRIPTION Hence, an edge in distGraph exists in order to forbid two NFSs to be packed together in the same function n while violating the isolation constraints imposed by the NSs, or slices s and t do not share any access node u oe V du . Once the conflict graph is generated in step 1 in Algorithm 2, its maximum clique size is calculated with getCliquesSize() on step 2 by applying the Grimmett-McDiarmid's greedy

Fig. 7 .

 7 Fig. 7.1d and Fig. 7.1i depict the final gap related to the best solution found by the proposed

Figure 7 . 1 -

 71 Figure 7.1 -Quantitative analyses: tiny and small instances.

Contenu 8 . 1 A

 81 compact formulation for the NSDP-DNF . . . . . . . . . . . . . . . . . . . . . . . . 8.2 An extended formulation for the NSDP-DNF . . . . . . . . . . . . . . . . . . . . . . . 8.3 Solving approaches for the NSDP-DNF . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3.1 Relax-and-fix algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3.2 Column generation-based algorithm . . . . . . . . . . . . . . . . . . . . . . . . 8.4 Numerical experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.4.1 Compact formulation and relax-and-fix algorithm . . . . . . . . . . . . . . . . . 8.4.2 Extended formulation and column generation-based framework . . . . . . . . . 8.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 .

 1 The content of this chapter was subbimited to Networks Journal in November 2021 as: W. d. S. Coelho, A. Benhamiche, N. Perrot and S. Secci, "Relax-and-Fix and Column Generations Algorithms for the Network Slice Design Problem".

8. 1 .. 1 )

 11 A COMPACT FORMULATION FOR THE NSDP-DNF attached to a slice :z s f AE z s f +1 , 's oe S, 'f oe F d \{f |F d | }. (8Network Function Services Dimensioning and Packing: Constraints (8.2) are to define variables w directly as a function of x variables while forcing to install enough NFS to process all the tra c: they express the number of copies of distributed and centralized NFSs needed for each NS request s oe S.

8. 3 .

 3 SOLVING APPROACHES FOR THE NSDP-DNF fix values on their variables.

Theorem 8 . 3 . 1 .

 831 If IntSlice set is equal to the set S of slice requests and the mathematical formulation M is unfeasible, then no feasible solution exists for I.

8. 4 .

 4 NUMERICAL EXPERIMENTS

  .2 and 8.3) used in the previous tests. Let us recall that the final gap is related to the best lower bound between those obtained by Relax-and-Fix and the solver on the ILP formulation.

Figure 8 . 1 -Figure 8 . 2 -

 8182 Figure 8.1 -Relax-end-Fix: qualitative analyses on di↵erent instance classes.

Fig. 8 .

 8 Fig. 8.2 presents the trade-o↵ between runtime and quality of the final solution when di↵erent ordering and pacing strategies are applied within the proposed Relax-and-Fix framework. As expected, we observed a better solution quality when a bigger pacing is applied instances with 4 slices requests (see Fig. 8.2a, Fig. 8.2b, and Fig. 8.2c). For instance, the final gap could be reduced from 8.00%

1. 1 . 2 Sommaire

 12 Nous avons étudié le problème de création de domaine en proposant deux algorithmes: exact et heuristique. L'approche exacte est basée sur une formulation ILP noeud-arc renforcée par deux familles d'inégalités valides qui sont utilisées dans un cadre de branch-and-cut. Les résultats montrent un impact significatif des coupures dans le renforcement de la relaxation LP et la réduction du temps de calcul. Nous nous attendons à ce que l'ajout de classes de coupes supplémentaires et la réalisation d'une analyse pour découvrir les spécificités des instances diciles (quelle que soit leur taille) permettront de résoudre des instances encore plus grandes. Une question naturelle serait d'envisager une formulation non compacte, basée sur des variables de chemin et de proposer un algorithme basé sur la génération de colonnes pour la résoudre. D'un autre côté, nos expériences montrent que l'approche heuristique fonctionne bien, même sur de grandes instances avec jusqu'à 2100 appareils et 1500 demandes de service sur des réseaux à 7 cellules. Il serait intéressant et très probablement très puissant de l'utiliser comme heuristique primale pour augmenter l'e cacité d'un algorithme exact.

CHAPTER 1 .

 1 R ÉSUM É DE TH ÈSE couches physiques et de commutation, avec di↵érentes technologies d'accès radio et de communication de liaison. Dans ce contexte, di↵érents fournisseurs peuvent être associés à di↵érents services de communication s'exécutant sur le même réseau physique au niveau des segments d'accès, de coeur et d'application.1.2.1 Définition du problèmeNous définissons le problème de Network Slice Design comme suit. Definition 1.2.1. Étant donné un graphe orienté G représentant le réseau physique, un ensemble de requêtes de slices S, un ensemble de requêtes de trafic K(s) associé à chaque requête s oe S, et un ensemble F de types de NFS, le NSDP consiste à déterminer le nombre de NFS à installer pour chaque s oe S, la taille des NF qui les hébergent ainsi qu'à décider s'ils doivent être installés de manière centralisée ou distribuée (c'est-à-dire en sélectionnant le découpage fonctionnel ), de sorte que (i) les demandes de K(s) puissent être contrôlées et acheminées dans G en utilisant ces NF ; (ii) les NFS installés sur G peuvent être compressés dans les NF tout en satisfaisant à la fois les contraintes d'isolement et de capacité ; et (iii) un chemin en G est associé à chaque paire de NF installées qui doivent être connectées. L'objectif est de concevoir chaque slice et de les intégrer dans le réseau physique G tout en minimisant le coût total de déploiement des requêtes de slice et en garantissant toutes les contraintes techniques imposées par les couches physiques et virtuelles.1.2.2 SommaireNous avons démontré par simulation l'impact de la prise en compte totale et partielle des contraintes particulières découlant des normes. Nous avons rapporté des résultats numériques montrant que le fractionnement flexible apparaît comme un facteur clé pour faire face à des exigences hétérogènes pour déployer des services de communication distincts, conduisant à une diminution considérable des coûts de slices. Dans nos simulations, le nombre de NFS nécessaires pour déployer les réseaux virtuels pourrait être réduit jusqu'à 56% selon laquelle des six politiques de partage proposées est appliquée à chaque slice. Nous avons également observé que di↵érentes variantes liées au fractionnement flexible ont un impact important sur le réseau physique: selon l'approche choisie, la charge sur les liens physiques pourrait être réduite d'un facteur 3.

1. 3 .

 3 APPROCHES EXACTES POUR LE NSDP CHAPTER 1. R ÉSUM É DE TH ÈSE court chemin entre son origine et sa destination.

  ka f |F d | f 0 + ÿ f oe{f 0 }fiF d \{f |F d | } " ka ff+1 ) Ø sp(k) , 'k oe K(s) : s oe S (1.3)are valid for the NSDP problem.1.3.2.3 Inégalités basées sur les coupes minimalesLes inégalités valides suivantes sont basées sur un théorème min-cut/max-flow de Ford et Fulkerson[START_REF] Ford | maximal flow through a network[END_REF], qui précise que pour un même produit, le débit maximal est égal à la coupe minimale séparant les noeuds d'origine et destination associés. Nous ne considérons donc que les arcs ayant une capacité su sante pour transporter individuellement le flux attendu.

  f |F d | f 0 + ÿ f oe{f 0 }fiF d \{f |F d | } " ka ff+1 ) Ø 1 'k oe K(s) : s oe S, '" oe (k)(1.4)are valid for the NSDP problem. 1.3.3 Un algorithme de génération de lignes pour le NSDP Nous proposons également l'algorithme Reduced MILP-based Row-Generation (RMRG), qui est basé sur un modèle relaxé : la formulation originale proposée est réduite à une nouvelle sans les contraintes d'isolement, de capacité et de latence. Ainsi, cette nouvelle formulation n'a que les contraintes liées aux principales décisions sur le NSDP : les inégalités de sélection fractionnée, les équations de dimensionnement, les inégalités d'emballage, les contraintes de placement, et les contraintes de routage; les contraintes d'intégralité restent dans le modèle. On note alors L l'ensemble des contraintes relâchées, à savoir les contraintes d'isolement, les inégalités de capacité et les contraintes de latence et. Pendant le processus de branchement, la routine Lazy Constraints (disponible dans la procédure de rappel du solveur MILP [8]) est appelée chaque fois que le solveur trouve une nouvelle et meilleure solution entière: si la solution actuelle viole toute contrainte de L, il est ajouté en tant que cut au modèle réduit. Nous avons développé un cadre parallélisé dans lequel chaque processus parallèle est chargé de rechercher et d'ajouter les contraintes violées liées à un noeud ou un lien physique donné.

1. 4 . 1 . 3 . 4 Sommaire

 4134 UNE MATH-HEURISTIQUE POUR LE NSDP 189 Dans cette section, nous avons présenté et discuté le problème de conception de slices dans les systèmes 5G et proposé une formulation MILP et des algorithmes exacts pour le résoudre. Des expériences numériques ont montré l'e cacité de chaque approche sur di↵érentes classes d'instances. Par exemple, la rupture de symétrie proposée et les contraintes basées sur les limites inférieures ont conduit à une diminution importante de l'écart final : de 30% à 1% dans certains cas. De plus, notre algorithme Branch-and-Cut a pu réduire la taille de l'arbre Branchand-Bound de 85% et a surpassé l'algorithme Branch-and-Bound du solveur dans tous les tests. Enfin, notre framework Row-Generation a surpassé l'approche Branch-and-Bound dans tous les tests, en particulier dans ceux avec des graphiques clairsemés. 1.4 Une math-heuristique pour le NSDP L'objectif global de cette section est d'aller au-delà des travaux présentés dans la section précédente. À cette fin, nous proposons un cadre d'accès ouvert basé sur une heuristique mathématique pour le problème de conception de tranches de réseau présentant des résultats numériques pour évaluer l'e cacité de notre approche. L'idée globale de l'heuristique mathématique proposée repose sur la décomposition du NSDP en quelques sous-problèmes et sur leur résolution séquentielle. Ces sous-problèmes sont liés aux décisions suivantes : sélection fractionnée, regroupement NFS-NF, intégration de noeud NF et routage du trafic. 1.4.1 Description de l'algorithme L'algorithme 1 présente le cadre global de notre approche. En entrée, l'heuristique reçoit une instance NSDP composée d'un graphe orienté G représentant le réseau physique avec l'ensemble de capacités C, un ensemble de requêtes de tranche S, dont chacune avec un ensemble de trafic demande K(s), un ensemble F de types NFS et un ensemble N de fonctions virtuelles hôtes potentielles. En sortie, l'algorithme 1 renvoie un réseau virtuel à chaque demande de tranche s oe S garantissant toutes les contraintes techniques imposées par les couches physiques et virtuelles.

1. 4 . 2 Sommaire

 42 Dans cette section, nous avons présenté et discuté le problème de conception de tranches de réseau dans les systèmes 5G, en proposant un cadre d'accès ouvert basé sur une math-heuristique pour résoudre le problème d'optimisation sous-jacent. Des expériences numériques ont montré l'e cacité de notre approche sur di↵érentes classes d'instances, qui pourraient atteindre des solutions quasi optimales dans un environnement d'exécution compétitif. En la comparant à une formulation de programmation linéaire à nombres entiers mixtes, la Math-Heuristique proposée pourrait réduire le temps d'exécution moyen et l'écart final jusqu'à 78% et 90%, respectivement. De plus, notre approche pourrait réduire la congestion sur le réseau physique, en équilibrant mieux le flux de données tout en tenant compte de toutes les contraintes techniques. Par exemple, la charge moyenne sur les liens physiques et les noeuds physiques pourrait être réduite de 16% et 35%, respectivement. Sur une note pratique, vu que notre Math-Heuristique pourrait réduire la charge moyenne sur les noeuds physiques et les liens physiques, une extension di cile mais intéressante consiste à l'utiliser dans un algorithme en ligne. Notre approche pourrait potentiellement augmenter le taux d'acceptation des tranches, c'est-à-dire le rapport entre le nombre de tranches intégrées et 1.5. CONCEPTION DE SLICES AVEC DES FONCTIONS DE R ÉSEAU D ÉDI ÉESS191 le nombre de requêtes, puisque la solution proposée par la Math-Heuristique distribue le flux de données entre plusieurs noeuds et liens, conduisant à une diminution de l'encombrement du réseau. Davantage de tests doivent donc être e↵ectués pour évaluer les e↵ets de l'heuristique mathématique proposée sur de tels scénarios et avant de pouvoir tirer des conclusions. Aussi, rappelons que, l'approche proposée étant une Math-Heuristique, l'optimalité des solutions trouvées par notre algorithme ne peut être assurée. Cependant, comme le montrent les résultats numériques présentés, l'e cacité de notre approche compense cet aspect et conduit à trouver des solutions avec un petit écart moyen sur des temps d'exécution relativement courts, même sur de grandes instances. Ainsi, il serait intéressant et très probablement très puissant de l'utiliser comme heuristique primale pour augmenter l'e cacité d'un algorithme exact. 1.5 Conception de slices avec des fonctions de réseau dédiéess Dans cette section, nous présentons une autre variante du NSDP, où la politique d'isolation matérielle est toujours appliquée, c'est-à-dire que toutes les fonctions réseau sont dédiées aux tranches. Grâce à cette hypothèse, la complexité du problème étudié peut être diminuée, ce qui nous permet de proposer di↵érentes approches heuristiques et mathématiques pour résoudre le problème d'optimisation associé. Cependant, les contraintes d'anti-a nité intra-tranche demeurent, ce qui représente la possibilité de regrouper deux NFS di↵érents dans la même fonction de réseau desservant une slice donnée. La motivation pour conserver la cartographie NFS-NF vient de la diminution de la complexité opérationnelle liée au déploiement de chaque NS. En d'autres termes, l'installation de quelques fonctions réseau au lieu de plusieurs services de fonctions réseau permet aux opérateurs d'agréger dans une même entité tous les NFS partageant le même protocole de communication ou d'autres types d'a nité. Par conséquent, l'étape de configuration du déploiement de slices pourrait être potentiellement plus facile et plus rapide, réduisant ainsi les coûts d'exploitation [9]. Nous appelons cette variante Network Slice Design with Dedicated Network Functions (NSDP-DNF). Dans ce qui suit, nous présentons di↵érentes stratégies afin de résoudre e cacement les problèmes d'optimisation liés au NSDP-DNF. Tout d'abord, nous proposons une formulation compacte et une formulation étendue. Pour résoudre le premier, nous avons proposé une heuristique Relax-and-Fix qui repose sur la résolution répétitive de l'ILP lié proposé avec seulement CHAPTER 1. R ÉSUM É DE TH ÈSE quelques variables entières et la correction ou la relaxation de la plupart des entiers et binaires restants. D'autre part, pour traiter le nombre exponentiel de variables dans la formulation étendue, un cadre basé sur la génération de colonnes est ensuite proposé. 1.5.0.1 L'algorithme Relax-and-fix L'algorithme 2 présente le cadre global de notre approche. L'idée globale de l'heuristique proposée, ci-après dénommée Relax-and-Fix, repose sur la résolution répétitive de l'ILP proposé avec seulement quelques variables entières et sur la fixation ou la relaxation de la plupart des variables entières et binaires restantes. En entrée, l'heuristique reçoit une instance NSDP-DNF composée d'un graphe orienté G représentant le réseau physique avec l'ensemble des capacités C, un ensemble de demandes de tranches S, chacune avec un ensemble de demandes de trafic K(s), un ensemble F de types NFS, un ensemble N de fonctions virtuelles hôtes potentielles et la stratégie de rythme fl oe Z + . En sortie, il renvoie un réseau virtuel à chaque demande de tranche s oe S garantissant toutes les contraintes techniques imposées par les couches physiques et virtuelles. 1.5.0.2 Algorithme basé sur la génération de colonnes Nous décrivons maintenant le cadre de génération de colonnes pour résoudre le NSDP, qui repose sur la formulation E-ILP proposée comme problème principal. Nous avons d'abord introduit la formulation duale associée : les contraintes d'intégralité sont alors relâchées et deviennent donc respectivement fi s g Ø 0. Ensuite, nous présentons une formulation ILP correspondant au sous-problème de tarification lié à chaque demande de tranche. Le problème du maître restreint Puisque G(s) a un nombre exponentiel de modèles potentiellement appropriés pour chaque demande de tranche, la formulation E-ILP a un nombre exponentiel de variables. Par conséquent, nous proposons d'initialiser le problème maître avec seulement un sous-ensemble de colonnes (c'est-à-dire des variables liées à chaque g oe G Õ (s) ™ G(s) pour chaque s oe S). Ce modèle est alors appelé Restricted Master Problem (RMP) et peut être généré en proposant des modèles sans exigence de capacité physique et de coût avec une valeur su samment grande (par exemple, µ s g = 10 5 ). Nous proposons également d'initialiser le RMP avec la solution finale trouvée par l'algorithme Relax-and-Fix proposé décrit dans les sous-sections précédentes.

1. 5 .

 5 CONCEPTION DE SLICES AVEC DES FONCTIONS DE R ÉSEAU D ÉDI ÉESS193 1.5.1 Sommaire Dans cette section, nous avons présenté une autre variante du NSDP, appelée Network Slice Design with Dedicated Network Functions, où la politique d'isolation matérielle est toujours appliquée, c'est-à-dire que toutes les fonctions réseau sont dédiées aux tranches, en gardant cependant l'anti-tranche intra-tranche. -les contraintes d'a nité, qui représentent la possibilité de regrouper deux NFS di↵érents dans la même fonction de réseau desservant une slice donnée. La motivation pour conserver la cartographie NFS-NF vient de la diminution de la complexité opérationnelle liée au déploiement de chaque NS. Nous avons ensuite présenté di↵érentes stratégies afin de résoudre e cacement les problèmes d'optimisation liés au NSDP-DNF. Dans un premier temps, nous avons proposé une formulation compacte et une autre étendue. Pour résoudre le premier, nous avons proposé une heuristique Relax-and-Fix qui repose sur la résolution répétitive de l'ILP connexe proposé avec seulement quelques variables entières et en fixant 194 CHAPTER 1. R ÉSUM É DE TH ÈSE ou en relaxant la plupart des entiers et binaires restants. D'autre part, pour traiter le nombre exponentiel de variables dans la formulation étendue, un cadre basé sur la génération de colonnes a ensuite été proposé. Dans nos simulations appliquant l'algorithme RF proposé, par exemple, l'écart moyen pourrait être réduit de 82,8% à 4,31% (resp. 48,4% à 5,77%) sur des instances moyennes-grandes (resp. moyennes) par exemple. De plus, bien qu'ILP n'ait pu trouver de solution entière réalisable en 1 heure d'exécution pour une instance de grande taille, la durée d'exécution moyenne et l'écart final étaient respectivement de 907 secondes et de 5,2% lorsque Relax-and-Fix était appliqué sur les mêmes instances. En ce qui concerne le cadre basé sur la génération de colonnes, cette approche pourrait améliorer l'écart dans toutes les tailles d'instances, en particulier lorsque la solution trouvée par l'algorithme RF a été donnée comme point de départ. Par exemple, l'écart et le temps d'exécution pourraient être réduits de 96%.

1. 6

 6 Conclusions finalesNous avons défini et étudié le concept de communications appareil à appareil et de découpage de réseau dans les systèmes 5G et proposons des modèles mathématiques et des algorithmes innovants pour résoudre les problèmes d'optimisation sous-jacents. En particulier, nous avons étudié le problème de création de domaine, qui est un problème de routage et d'a↵ectation de ressources survenant dans les futurs réseaux 5G. Nous avons proposé deux algorithmes, un exact et un heuristique, pour le résoudre. L'approche exacte est basée sur une formulation ILP noeud-arc renforcée par deux familles d'inégalités valides qui sont utilisées dans un cadre de branchement et de coupure. Nous avons également présenté une méthode de résolution basée sur une décomposition du DCP en deux sous-problèmes : le sous-problème de routage et le sous-problème d'allocation de ressources. Premièrement, un impact significatif des coupes dans le renforcement de la relaxation LP et la réduction du temps de calcul a été observé. Malgré un temps d'exécution plus long pour certaines instances utilisant les coupes proposées, nous avons pu observer que l'écart entre la solution racine et la solution finale est toujours plus petit lorsque des coupes de voisinage sont appliquées. En utilisant les réductions de capacité, cette amélioration est observée pour la moitié des instances considérées. Cependant, la taille finale de l'arbre après avoir trouvé la solution finale à l'aide de ces coupes peut être jusqu'à 76,40% plus 1.6. CONCLUSIONS FINALES 195 petite. Nos expériences ont également montré que l'approche heuristique proposée fonctionne bien, même sur de grandes instances avec jusqu'à 2 100 appareils et 1 500 demandes de service sur des réseaux à 7 cellules. Il serait intéressant et très probablement très puissant de l'utiliser comme heuristique primale pour augmenter l'e cacité d'un algorithme exact. Nous avons également défini et modélisé l'approvisionnement des slices en tant que problème d'optimisation comprenant de nouvelles exigences de mappage et d'approvisionnement. En particulier, nous avons pris en compte les nouvelles dimensions de mappage apparaissant avec les systèmes 5G, modélisant la relation entre la séparation fonctionnelle flexible de l'accès radio, la séparation des fonctions du plan de contrôle et du plan de données et les politiques de partage. Di↵érentes variantes du problème ont également été considérées et les modèles proposés sont conformes aux normes de fonctionnement. Nous avons démontré par des analyses numériques l'impact d'une prise en compte totale et partielle des contraintes particulières découlant des normes. Par exemple, nous avons rapporté des résultats numériques montrant que le fractionnement flexible apparaît comme un facteur clé pour faire face aux exigences hétérogènes de déploiement de services de communication distincts, entraînant une diminution considérable des coûts de slice. Dans nos simulations, le nombre de NFS nécessaires pour déployer les réseaux virtuels pourrait être réduit jusqu'à 56% selon laquelle des six politiques de partage proposées est appliquée à chaque slice. Nous avons également observé que di↵érentes variantes liées au fractionnement flexible ont un impact important sur le réseau physique ; selon l'approche choisie, la charge moyenne sur les liens physiques pourrait être réduite d'un facteur 3. Afin de renforcer la relaxation linéaire du MILP proposé, nous avons présenté plusieurs classes d'inéquations valides et les avons intégrées dans un cadre Branch-and-Cut pour résoudre le problème. Nous présentons en outre plusieurs stratégies pour réduire les symétries et la taille du modèle. Des expériences numériques ont montré l'e cacité de chaque approche sur di↵érentes classes d'instances. Par exemple, la rupture de symétrie proposée et les contraintes basées sur les limites inférieures ont conduit à une diminution importante de l'écart final : de 30% à 1% dans certains cas. De plus, notre algorithme Branch-and-Cut a pu réduire la taille de l'arbre Branch-and-Bound de 85% et a surpassé l'algorithme Branch-and-Bound du solveur dans tous les tests. Enfin, notre framework Row-Generation a surpassé l'approche Branch-and-Bound dans tous les tests, en particulier dans ceux avec des graphiques clairsemés.

CHAPTER 1 .

 1 R ÉSUM É DE TH ÈSE De plus, pour répondre à la complexité temporelle liée aux approches exactes proposées, nous avons présenté un cadre d'accès ouvert basé sur une heuristique mathématique pour résoudre le problème d'optimisation sous-jacent. L'idée générale de l'approche proposée reposait sur la décomposition du NSDP en plusieurs sous-problèmes et sur leur résolution séquentielle tout en englobant la séparation du plan de contrôle et du plan de données et de nouvelles dimensions de mappage et de décomposition influençant le placement et l'interconnexion des tranches. Des expériences numériques ont montré l'e cacité de notre approche sur di↵érentes classes d'instances, qui pourraient atteindre des solutions quasi optimales dans un environnement d'exécution compétitif. En la comparant à une formulation de programmation linéaire à nombres entiers mixtes, la Math-Heuristique proposée pourrait réduire le temps d'exécution moyen et l'écart final jusqu'à 78% et 90%, respectivement. De plus, notre approche pourrait réduire la congestion sur le réseau physique, en équilibrant mieux le flux de données tout en tenant compte de toutes les contraintes techniques. Par exemple, la charge moyenne sur les liens physiques et les noeuds physiques pourrait être réduite de 16% et 35%, respectivement. Nous avons également étudié la variante NSDP-DNF, où la politique d'isolement dur est toujours appliquée, c'est-à-dire que toutes les fonctions réseau sont dédiées aux tranches, en garantissant toutefois les contraintes d'anti-a nité intra-tranches, qui représentent la possibilité de regrouper deux NFS di↵érents dans la même fonction de réseau desservant une slice donnée. Nous avons ensuite proposé di↵érentes stratégies afin de résoudre e cacement le problème d'optimisation. Dans un premier temps, nous avons présenté une formulation compacte et une autre étendue. Pour résoudre le premier, nous avons proposé une heuristique Relax-and-Fix qui repose sur la résolution répétitive de l'ILP connexe proposé avec seulement quelques variables entières et en fixant ou en relaxant la plupart des entiers et binaires restants. D'autre part, pour traiter le nombre exponentiel de variables dans la formulation étendue, un cadre basé sur la génération de colonnes est ensuite proposé. Dans nos simulations appliquant l'approche Relax-and-Fix proposée, par exemple, l'écart moyen pourrait être réduit de 82,8% à 4,31% (resp. 48,4% à 5,77%) sur moyen-grand (resp. moyen) instances. De plus, bien qu'ILP n'ait pu trouver de solution entière réalisable en 1 heure d'exécution pour une instance de grande taille, la durée d'exécution moyenne et l'écart final étaient respectivement de 907 secondes et de 5,2% lorsque Relax-and-Fix était appliqué sur les mêmes instances. En ce qui concerne le cadre basé 1.6. CONCLUSIONS FINALES 197 sur la génération de colonnes, cette approche pourrait améliorer l'écart dans toutes les tailles d'instances, en particulier lorsque la solution trouvée par l'algorithme RF a été donnée comme point de départ. Par exemple, l'écart et le temps d'exécution pourraient être réduits de 96%. Wesley DA SILVA COELHO Modeling and Optimization of 5G Network Design Résumé : Chaque seconde, une grande quantité de données numériques est transportée à travers les réseaux cellulaires du monde entier, et les attentes sont à une croissance considérablement accélérée avec des demandes de plus en plus importantes. En quelques années, ces réseaux pourraient atteindre leurs capacités maximales en termes de transmission de données. Pour faire face ces défis, Network Slicing a été présenté comme une nouvelle infrastructure virtualisée pour le système de réseau mobile de nouvelle génération. Cette technologie couvre désormais non seulement le niveau des applications, mais également la virtualisation des couches physiques et de commutation, avec di↵érentes technologies d'accès radio. Ainsi, chaque fournisseur de services doit pouvoir déployer ses services sur des réseaux logiques, appelés Network Slices, spécifiquement adaptés à ses exigences techniques. Le mode de communication Device-to-Device est une autre approche présentée comme une alternative prometteuse à la communication traditionnelle dans les réseaux cellulaires. Cette technologie permet de réutiliser les ressources radio et de diminuer la latence de bout en bout des communications locales. Par conséquent, l'optimisation des ressources physiques dans les réseaux cellulaires devient cruciale pour mieux dimensionner et déployer les réseaux virtuels. L'objectif global de ce travail est donc de définir et d'étudier le concept de Device-to-Device Communication et Network Slice Design dans les systèmes 5G, en proposant des modèles mathématiques et des algorithmes innovants pour résoudre les problèmes d'optimisation sous-jacents. Mots clés: Optimisation, Conception de réseau, Découpage réseau en tranches, Communication d'appareil à appareil

  Theory of graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Linear programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solving approaches for linear programming . . . . . . . . . . . . . . . . . . . . . . . .

	Chapter 2
	Background
	Contenu
	2.1

2.1.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.2 Some classical problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 2.2.1 Integer linear programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Geometric aspects of linear programming . . . . . . . . . . . . . . . . . . . . . 2.2.3 Duality in linear programming . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 2.3.1 Graphical method and Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.2 Linear relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.3 The branch-and-bound framework . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.4 Cutting planes and branch-and-cut algorithm . . . . . . . . . . . . . . . . . . . 2.3.5 Column generation and the branch-and-price algorithm . . . . . . . . . . . . . 2.3.6 Heuristic methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  Device-to-device communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 5G system mapping requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sharing policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1 Core network evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 From 3G to 4G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.2 Separating 4G core with CUPS . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.3 From 4G to 5G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 5G core specificities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Customized service-based network functions . . . . . . . . . . . . . . . . . . . . 3.2.2 Auto-scaling and distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.3 The user-plane case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.4 Functional splitting in the radio access network . . . . . . . . . . . . . . . . . . 3.3 3.4.1 Mapping NF services into network functions . . . . . . . . . . . . . . . . . . . . 3.4.2 Mapping network functions into slices and slice subnets . . . . . . . . . . . . . 3.4.3 Mapping slices subnet into slices . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.4 Mapping slices into communication services . . . . . . . . . . . . . . . . . . . . 3.4.5 Mapping communication services into user equipment . . . . . . . . . . . . . . 3.5

Table 3 .

 3 1 -Example of a NF service decomposition: UDM as NF service producer

	NF Service	NF Service operations	Signaling semantic	NF Service consumers
	Subscriber Data Management	Get Subscribe Notification	Request/Response Subscribe/Notify	AMF, SMF, SMSF
	UE Context Management UE Authentication	Get Update Result Confirmation	Request/Response	NEF, SMSF AUSF
	Parameter Provision	Update	Request/Response	NEF

Table 3 .

 3 2 depicts di↵erent fronthaul (FH) bitrates and latency indicators for each functional split.

	3.2. 5G CORE SPECIFICITIES
	kilometers. However, there is still redundancy in the network: all RAN functionalities are replicated
	for each pair of BBU and RRU. To overcome this, centralized RAN (C-RAN) was first introduced in
	2011 [58]; pools of BBUs with large capacity, now called Centralized Units (CUs), are proposed to
	treat tra c from a sub-set of RRUs, now named Distributed Units (DUs). Hence, one of the first
	tasks is to define the functionalities enabled locally at the DU, and those installed centrally at the CU
	and thus shared among a subset of DUs.
	Figure 3.3 illustrates di↵erent functional split options on the 4G stack, as the 5G RAN split options
	have not yet been specified. Let's take option 3 as an example: all functions from Radio Frequency
	(RF) to Low Radio Link Control (RLC) blocks are locally installed, while high RLC, Packet Data
	Convergence Protocol (PDCP) and Radio Resource Control (RRC) functions are centrally installed.
	Equivalently, with option 7 on the uplink direction, all functionalities after the low Physical (PHY)
	block are installed at a CU, while with option 5 all entities before the low Media Access Control
	(MAC) block are installed at the DUs.
	Since the functional split was originally meant to be made a priori (i.e., before deploying the
	network) choosing the best split [59] for each scenario is not trivial. Defining the distributed and cen-
	tralized functionalities should take into account end-to-end delay and total bandwidth constraints on
	each physical path connecting DUs and CUs while optimizing the resource allocation. It is important
	to mention that all distributed functionalities should be installed in each DU to support any type of
	split. Complementary, centralized functionalities have few instances that are installed in CUs and are
	shared by a specific sub-set of DUs. The dependency factors such as varying network latency and
	capacity has recently motivated experimenting dynamic functional splitting, where the split decision
	can be reconfigured on a short time scale for one or a few split options [60].

Table 3 .

 3 2 -Fronthaul bitrate and latency in functional split.

	3.2. 5G CORE SPECIFICITIES
	Functional Split	DL Bitrate	UP Bitrate	FH Latency
	Option 1: RRC-PDCP	4 Gbps	3 Gbps	10 ms
	Option 2: PDCP-hRLC	4 Gbps	3 Gbps	1.5-10 ms
	Option 3: hRLC-lRLC	4 Gbps	3 Gbps	1.5-10 ms
	Option 4: lRLC-hMAC	5.2 Gbps	4.5 Gbps	0.1-1.0 ms
	Option 5: hMAC-lMAC	5.6 Gbps	7.1 Gbps	0.1-1.0 ms
	Option 6: lMAC-hPHY	5.6 Gbps	7.1 Gbps	0.25 ms
	Option 7: hPHY-lPHY	9.2 Gbps	60.4 Gbps	0.25 ms
	Option 8: lPHY-RF	157.3 Gbps	157.3 Gbps	0.25 ms

  Due to the inherent symmetry of this problem, there is possibly a large number of feasible solutions.

	4.3. A MATHEMATICAL FORMULATION FOR THE DCP
	4.3.2 Symmetry-breaking
	(x, y, z) oe {0, 1} (m◊|R|+n)◊|K|+|R|
	satisfying inequalities (4.2)-(4.6), where m = |A| and n = |V |. The breaking symmetry constraints
	(4.11) are inspired by classical inequalities in combinatorial optimization (see [91]), and can help in
	reducing the number of symmetric solutions in the formulation.
	(4.10)

r oe R. z r > z r+1 , '1 6 r 6 |R| ≠ 1, (4.11) (4.11) allow to assign the radio resources in an ordered way, forbidding to use a resource r + 1 if r is available. Note that a vector (x, y, z) oe {(x, y, z) oe {0, 1} (m◊|R|+n)◊|K|+|R| : (x, y, z) satisfies (4.2) ≠ (4.11)} is clearly a feasible solution to the DCP.

  other words, an edge in H m u exists if two demands cannot be packed together in the node u due to the lack of capacity for the resource type m. Consequently, a clique in the graph H m u corresponds to a set of demands that cannot use simultaneously the node u. Hence, we denote by C H the set of cliques in the graph H m u . Let u be a node of V and m oe C d be a physical resource type. Then the following inequalities Let  C be a clique in H m u . It is clear that if two demands k 1 , k 2 from clique  C use the resource m of node u, the capacity constraint (4.4) for the resource m will be violated. In other words, each edge v k i v k j of the clique  C represents an infeasible packing of the demands k i , k j in the node u.The second family of valid inequalities strengthen constraints (4.6). They are obtained by considering the interference graph N = (V N , E N ) defined as follows. Every node u oe V

	4.3.3.2 Strengthened neighborhood inequalities

ÿ koeC y k u 6 1, 'C oe C H (4.12) are valid for the DCP.

4.4. A BRANCH-AND-CUT ALGORITHM FOR THE DCP Proof. N corresponds to an arc in A and two nodes u e , u f of V N (associated respectively with the arcs e and f from A) are interconnected by an edge if e and f are close enough from each other (ie if d(e, f ) 6 D). Consequently, a clique in the graph N corresponds to a subset of arcs in A that are pairwise close, and cannot receive the same radio resource due to interference constraints. Likewise in the conflict graph defined before, we denote by C N the set of cliques in the graph N . The following inequalities ÿ koeK ÿ eoeC x k er 6 z r , 'r oe R, C ™ C N (4.13) are valid for the DCP. Proof. Let  C be a clique in N and u e , u f two nodes of V N that belong to clique  C. Clearly, if e and f

Table 4 .

 4 1 -Runtime comparison (in seconds) with strengthening constraints.

	Instance Original Model Symmetry-Breaking	SINR	Symmetry & SINR
	U5 D2	0.05	0.06	0.05	0.06
	U5 D6	187.18	11.55	77.18	10.71
	U5 D8	600.56	45.16	90.70	72.43
	U10 D5	1677.21	290.33	697.49	435.08
	U10 D7	8746.32	3569.18	4453.58	2967.45
	U15 D7	10800	10800	10800	10800

Table 4 .

 4

1

shows the impact of inequalities (4.10) and

(4.11)

on the initial model (formulation (4.1)-(4.9)). In the first column, the name of each instance refers to the number of users (U#) and demands (D#). The next four columns show the computational time (in seconds) for the initial formulation, then when adding symmetry breaking constraints (4.11), strenghthened SINR constraints (4.10) and both constraints, respectively. We can notice that using constraints (4.11) allows to obtain the best execution time for two out of five instances tested (U 5 D8 and U 10 D5) while the instances U 5 D6 and U 10 D7 have the lower runtime when applying constraints (4.10) and (4.11), combined. For instance U 15 D7, the optimal solution could not be found after 3 hours of execution.

We tested the impact of using our valid inequalities and compared the results to CPLEX branchand-bound for the strengthened model (formulation (4.1)-(4.2) + (4.4)-(4.11)). Table

4

.2 shows the results obtained on five instances (same as in Table

4

.1) when (i) no additional cuts are used, (ii) 4.6. COMPUTATIONAL RESULTS

Table 4 .

 4 2 -Solution quality comparison between models with and without additional cuts.

		Strengthened Formulation	Strengthened + Neighborhood cuts
	Instance	root gap (%) runtime (s) tree size	root gap (%)	runtime (s) tree size
	U5 D2	0.00	0.05	1	0.00	0.06	1
	U5 D6	10.00	11.49	7	10.00	11.67	8
	U5 D8	59.65	154.65	470	23.58	130.69	291
	U10 D5	57.89	677.21	1327	33.09	1370.90	190
	U10 D7	62.26	3236.61	1850	50.04	8654.21	2040
	U15 D7*	77.23	10800	58	72.37	10800	8
		Strengthened + Clique-based cuts	Strengthened + both cuts
	Instance	root gap (%) runtime (s) tree size	root gap (%)	runtime (s) tree size
	U5 D2	0.00	0.06	1	0.00	0.05	1
	U5 D6	10.00	12.33	2	10.00	13.31	2
	U5 D8	33.71	389.01	1225	32.00	150	599
	U10 D5	48.23	1262.83	91	33.09	2265.83	84
	U10 D7	62.26	3251.99	1850	50.04	9648.12	2040
	U15 D7*	77.23	10800	70	72.37	10800	22

Table 4 .

 4 3 -Routing subproblem: numerical simulations.

			Compact formulation		Path Formulation
	Instances	Act. Frac. Var. (%) Gap (%) Runtime (s) Pre-processing (s) Solver (s)
	U700 D175	0.05	0.03	9.16	4.81	0.02
	U700 D350	1.92	1.1	13.92	9.5	0.02
	U700 D525	1.84	13	21.28	14.26	0.08
	U700 D700	0.87	0.04	26.72	19.22	0.13
	U1400 D350	5.22	0.02	46.83	27.48	0.8
	U1400 D700	3.37	3.6	77.7	55.68	0.26
	U1400 D1050	3.13	3.05	152.31	82.82	0.42
	U1400 D1400	1.79	0.49	143.78	110.81	0.60
	U2100 D525	5.56	0.02	143.28	81.28	0.23
	U2100 D1050	3.54	0.09	257.18	163.39	0.65
	U2100 D1575	2.15	3.86	242.84	230	0.8

Table 4 .

 4 4 -Resource Allocation sub-problem: numerical simulations

	Instances	Pre-processing (s)	Greedy (s) Gap (%)
	U700 D175	0.13	0.89	0
	U700 D350	0.53	1.81	0
	U700 D525	1.15	2.75	0
	U700 D700	2.12	3.89	0
	U1400 D350	0.54	1.74	0
	U1400 D700	2.34	3.76	0
	U1400 D1050	4.97	5.95	0
	U1400 D1400	7.06	6.97	0
	U2100 D525	1.32	2.07	0
	U2100 D1050	4.45	5.25	0
	U2100 D1575	11.21	9.51	0

Table 4 .

 4 5 -Quality of the final solution.

			2-Phase Heuristic		Branch-and-Bound
	Instance	Compact Formulation	Path Formulation	Original Formulation
		Gap (%) Runtime (s) Gap (%) Runtime (s) Gap (%) Runtime (s)
	U140 L334 D35	0.0	0.19	0.0	0.15	0.0	7816
	U140 L342 D35	0.0	0.19	0.0	0.16	0.0	8523
	U140 L346 D35	0.0	0.18	0.0	0.14	0.0	7822
	U140 L333 D35	0.0	0.19	0.0	0.16	0.0	7560
	U140 L329 D35	0.0	0.17	0.0	0.13	0.0	7987
	U140 L336 D35	0.0	0.18	0.0	0.14	0.0	8622
	U210 L518 D52	0.0	0.46	0.0	0.43	0.0	32892
	U210 L501 D52	0.0	0.43	0.0	0.34	0.0	37808
	U210 L512 D52	0.0	0.45	0.0	0.35	0.0	38091
	U210 L522 D52	0.0	0.45	0.0	0.39	0.0	33790
	U210 L513 D52	0.0	0.43	0.0	0.40	0.0	36987
	U210 L508 D52	0.0	0.45	0.0	0.38	0.0	37090

Table 5 .

 5 2 -Simulated slice demand setting.

	Slice	Service required	Aditional CPNFSs	Max E2E latency ds	UE data rate UE per DU
	1	Broadbandaccessindenseareas	NFS10,NFS11	10ms

Table 5 .

 5 3 -Scenarions: split settings and sharing policies

	Split Setting	Description
	Setting 1	all DP NFS are installed locally for all NS requests.
	Setting 2	for each slice, only NFS5 is installed centrally.
	Setting 3	for each slice, only NFS4 and NFS5 are installed centrally. It corresponds to 3GPP's split 1 in
		Fig. 3.3.
	Setting 4	for each slice, only NFS1 and NFS2 are distributed; it corresponds to 3GPP's split 2 in Fig. 3.3.
	Setting 5	for each slice, only NFS1 is installed locally. It corresponds to 3GPP's split 4 in Fig. 3.3.
	Setting 6	all DP NFSs are installed centrally for all NS requests. It corresponds to 3GPP's split 6 in Fig. 3.3
	Flexible	free functional split selection for each NS request.
	Policy	Description
	Hard Isolation	NS requests do not accept sharing any NFS.
	Shared DP	only DP NFSs can be shared among slices.
	Shared CP	only CP NFSs can be shared among slices.
	Partial DP Isol.	only NFS1, NFS2, and NFS3 can be shared.
	Partial CP Isol.	only mandatory CP NFSs can be shared among NSs.
	Flat Sharing	NS requests do not impose any isolation constraint.

  This class of valid inequalities depends directly on the values of x and w variables and therefore can be generated only regarding a solution for the presented formulation (5.1)-(7.9). Let w ¯sf Consider a small instance with two slice requests {s 1 , s 2 }, one DP NFS type f 1 , two available NFs {n 1 , n 2 }, and two aggregation/core nodes {u 1 , u 2 } with only one resource type c 1 in the physical network. For this instance, we also have c 1 u = 15 for any u oe V ac p ,

		a oe A p	(6.24)
	6.2.4.4 Node capacity
	c c f +	w ¯tg
	nu

nu and x ¯sf nu be the values of the related variables in the current solution. For each u oe V p , let H u = (V u , E u ) be the associated undirected graph obtained from an instance of NSDP as follows. A node v in V u is associated with every tuple (s, f, n) : s oe S, f oe F, n oe N that x ¯sf nu > 0 holds in the current solution. There exists an edge in

(u, v) oe E u between any two nodes u = (s, f, n) and v = (t, g, m) from V u if w ¯sf nu x ¯sf mu x ¯tg

mu c c g > c c u holds for any physical resource c oe C. Let C(H u ) be the set of all cliques on H u . Then, the following inequalities ÿ (s,f,n)oeC x sf nu 6 1 , 'u oe V p , 'C oe C(H u ) (6.25) are valid for the NSDP. Proof. Let C be a clique in C(H u ). If the flow of two pairs (s, f, n) and (t, g, m) from C are carried through a same physical node u oe V p , the related capacity constraint (5.13) will be violated. I other words, each pair of nodes from clique C represents an infeasible packing from di↵erent NFSs in a physical node u oe V p . Consequently, a clique in the graph H u corresponds to a set of functions that cannot be packed simultaneously in the physical node u.

Example:

Table 6 .

 6 1 -Instance Sizes

		Instance size Tiny (T)	|V | 10	Graph density 0.15	|S| 2	Demands per slice |F d 1 2	|	|F c 2	|
		Small (S)	15	0.10	2	2	4		2
		Medium (M)	20	variable	4	3	4		3
				Table 6.2 -Instance Classes
	Latency	Description
	Low (L)

Table 7 .

 7 1 -Time Complexity

	Main Procedures	Asymptotic Complexity
	chooseCU()

Table 7 .

 7

			2 -Instance Sizes
	Instance size Tiny (T)	|V | 10	Graph Density* |S| 0.15 2	|K| 1	|F d 2	|	|F c 2	|
	Small (S)	15	0.10	2	2	4		2
	Medium-Small (SM)	20	0.15	4	3	4		3
	Medium (M)	25	0.15	4	8	6		4
	Medium-Big (MB)	30	0.20	4	8	6		6
	Big (B)	35	0.20	8	8	8		6
	Extra-Big (EB)	40	0.25	8	8	8		8
	* Ratio between exiting and theoretically possible number of arcs.

Table 7 .

 7 3 -Instance Classes

	Latency	Description
	Low (L)

  1)-(5.19) with the proposed objective function (6.29), hereafter referred to as to MILP, introduced in the previous chapters. Concerning 7.2. NUMERICAL EXPERIMENTS step 17 of Algorithm 1, we set fl to 1 ≠ 60/seconds for tiny and small instances and 1 ≠ 600/seconds

Table 7 .

 7 4 -Quantitative analyses: from medium small to extra big instances

	Instance Size	MILP	Math-Heuristic
		Runtime (s)	Gap (%)	Runtime (s)	Gap (%)
	Medium-Small Medium Medium-Big Big Extra-Big * Time limit reached. 2165 ± 364 3600 ú 3600 ú 3600 ú 3600 ú	0 5.7 ± 2.1 36.3 ± 4.8 ** ** ** No feasible solution was found. 732 ± 87 3.2 ± 0.5 803± 122 4.5±0.7 4.3±1.2 894 ± 109 8.2±3.6 997 ± 84 11.5±2.4 1245 ± 241

  u oe V ac . 's oe S, 'f oe F, 'n oe N, 'u oe V (8.2) serving s should be installed in a node of V ac . The constraints(8.6) are the flow conservation constraints, for each slice request s oe S, each demand k oe K(s) and each pair of NFSs in F . They allow to associate a path in G for each tra c demand k between its origin node o k and the first NFS f = 1 from the ordered set F d and serving k, and between the last NFS f = |F d | from F d and the destination node t k of k.

	x sf nu + x tg nv AE Network Function Services Placement: For each slice request s, equalities (8.4) ensure that a dis-I 1 + q s fg if s = t, u = v, y n otherwise . 's, t oe S, 'f, g oe F, 'n oe N, 'u, v oe V (8.3) tributed NFS f should be installed on every origin node of K(s); whereas equalities (8.5) ensure that each centralized NFS f ÿ noeN x sf nu = I 1 ≠ z s f , if f oe F d , u oe O(s); 0 , otherwise. , s oe S, 'f oe F, u oe V du (8.4) ÿ noeN ÿ uoeV\V du x sf nu = I z s f , if f oe F d ; -s f , otherwise. s oe S, 'f oe F (8.5) subject to (8.1) ≠ (8.10) 0 AE r a AE b a oe R , 'a oe A (8.12) y n oe {0, 1} 'n oe N (8.13) x sf nu oe {0, 1} 's oe S, 'f oe F, 'n oe, 'u oe V (8.14) z s f , oe {0, 1} 's oe S, 'f oe F (8.15) " ka fg oe {0, 1} 'k oe K(s) : s oe S, 'f, g oe F (8.16) Tra c routing: 8.2. AN EXTENDED FORMULATION FOR THE NSDP-DNF w sf nu Ø 0 oe Z 's oe S, 'f oe F, 'n oe N, 'u oe V (8.17)

Table 8 .

 8

	1 -Time Complexity
	Main Procedures Creating conflict graph 1-5 Steps Asymptotic Complexity O(SF V ), V from physical network Getting clique size 6-10 O(V 4 ), V from conflict graph Coloring conflict graph 11-17 O(V 2 ), V from conflict graph
	sequential coloring algorithm presented by Syslo

Table 8 .

 8 2 -Instance Sizes

	8.4. NUMERICAL EXPERIMENTS
	Instance size Tiny (T)	|V | Graph Density* |S| |K| |F d | |F c | 10 0.15 2 1 2 2
	Small (S)	15	0.10	2	2	2	2
	Medium-Small (SM)	20	0.15	4	3	5	2
	Medium (M)	25	0.15	4	8	5	5
	Medium-Big (MB)	30	0.20	4	8	10	5
	Big (B)	35	0.20	8	8	10	10
	* Ratio between exiting and theoretically possible number of arcs.

Table 8

 8

	.3 -Instance Classes

Table 8 .

 8 4 -Relax-end-Fix: gap and runtime on di↵erent instances sizes. instance size, 30 instances for each class (i.e., a combination of capacity, latency, and isolation constraints; see Table8.3) were randomly generated as previously discussed.

				ILP	Relax-and-Fix
	Instance Size	Gap (%)	Runtime (s) Gap (%)	Runtime (s)
	Tiny Small Medium Small	0.0 0.0 26.5±2.3	5±3 248±49 3600*	1.14 ± 1.1 1.65 ± 0.3 8.44±0.2	0.03±0.01 0.23±0.1 97±28
	Medium	48.4±28.8	3600*	5.77±0.1	178±37
	Medium Big	82.8±32.2	3600*	4.31±0.06	319±49
	Big		**	3600*	5.90±0.1	907±158
	* Time limit reached.	** No feasible solution was found.

each

Table 8 .

 8 4 shows the execution time and final gap (average and standard deviation) on all instance sizes. While the second and third columns are related to the ILP formulation within the solver branch-

and-bound, the two last columns depict the values when the proposed Relax-and-Fix algorithm was applied. In both cases, the final gap is related to the best lower bound between those obtained by Relax-and-Fix (see Theorem 8.3.2) and the solver on the ILP formulation (8.1)-(8.17). All results reported in Table

  8.1a and Fig. 8.1b). ) before the last iteration (i.e., with all variables with either fixed values or related integrality constraints restored). However, we did not observe any important influence on the performance of our approach applying di↵erent instance classes on bigger instances (see Fig.8.1c and Fig.8.1d). Also, di↵erent latency and anti-a nity constraints did not statistically impact the quality of the final solutions on any instance size.

	8.4. NUMERICAL EXPERIMENTS
	had the same solution quality. We also observed that the average final gap on tiny (resp. small) in-
	stances with tight capacity constraints was roughly 1.50% (resp. 2.47%) against 0.78% (resp. 0.50%)
	presented by those with moderate physical capacities. This behavior can be explained by the fact
	that almost all integrality constraints are relaxed during the first iterations of the proposed Relax-
	and-fix algorithm, which might potentially lead to the violation of several capacity constraints (see
	Inequalities (8.9)-(8.10)

Indeed, while 100% of < T, H, M, W > (resp. < S, H, M, W >) instances had a gap smaller than 1.50% (resp. 2.50%), only 37.50% (resp. 60.0%) of < T, L, T, S > (resp. < S, L, T, S >) instances

  We now present the results from solving the extended (8.19)-(8.23) along with the proposed column generation-based framework (seeAlgorithm 6). As a start point, we gave the solution found by our RF algorithm applying the 2-slice pace and capacity ordering strategies and set the time limit to 3600

	8.4. NUMERICAL EXPERIMENTS
	4-slice pacing on all ordering strategies. As seen in Figures 8.2e and 8.2g, however, this is not always
	the case. For instance, we observed a decrease from 1-slice pacing to 2-slice pacing (resp. 2-slice pacing
	to 3-slice pacing) on medium-small (resp. medium) instances with latency (resp. random) ordering
	strategy. More tests must therefore be carried out to assess this behavior in such scenarios before
	conclusions can be drawn.
	8.4.2 Extended formulation and column generation-based framework

8.2d and Fig. 8.2h

). While there is a smaller gain by increasing the pacing strategy, the runtime reached the 1-hour limit with the seconds (1 hour). We refer to this approach as to RF-CG. Also, an artificial template-based starting point was proposed, in which an artificial column (i.e., slice template) was created with a large enough artificial cost (i.e., µ s g = 10 2|S|

Table 8 .

 8 5 -Column Generation-based framework: gap and runtime on di↵erent instances sizes.

	Approach		Instance Size
	Tiny	Small	M. Small	Medium	M. Big	Big
	LR (%) Gap (%) Runtime (s) LR (%) Iterations Gap (%) Runtime (s) LR (%) Iterations Gap (%) Runtime (s) * Time limit reached. Compact Formulation Relax-and-Fix + Column Generation Artificial Temp. + Column Generation ** No feasible solution was found. 22.5±6.9 22.6±1.2 47.2±7.0 0.0 0.0 26.5±2.3 48.4±28.8 42±5.1 5±3 3600* 3600* 2 4 8 ±49 0.8±0.1 0.4±0.3 1.9±0.05 2.62±0.5 3.21±0.3 4.6±0.7 20.2±4.2 15.0±3.1 0.4±0.2 0.8+0.1 2.7±0.5 3.0±0.4 0.2±0.01 4±2 1484±342 4 9 2 ±200 0.8±0.1 0.4±0.3 1.9±0.5 0.2±0.07 5.46±0.5 6.7±0.9 21.9±3.7 18.5±2.8 3.5±0.5 10.2±5.6 16.5±6.1 47.2±10.3 0.36±0.5 7±4 3600* 7 3 3 ±247	38.5±16.2 82.8±32.2 3600* 1.8 ±1.1 3.5±1.2 2.54±0.6 3600* 15.6±9.2 2.2±1.3 ** 3600*	39.1±13.4 ** 3600* 5.9±0.1 0 5.90 ±0.1 3600* 27.3±16.4 0 ** 3600*

to time constraints, RF-CG could not complete any pricing iteration on big instances, generating no additional column (i.e., slice template) to the master problem. Compared to AT-CG, RF-CG could reach the best linear-relaxation solution with fewer iterations. For instance, RF-CG needed 41% (resp.

  Une fois ces conditions remplies, les services sont délivrés via les di↵érents types de ressources allouées à la fois aux appareils et aux liens.Dans ce contexte, nous définissons le problème de création de domaine (DCP) comme suit. Definition 1.1.1. Le problème de création de domaine consiste à trouver une allocation de coût minimum des ressources radio aux arcs actifs pour fournir un chemin de routage réalisable pour chaque demande. En particulier, un routage p k = {(o k , u), . . . , (v, d k )} pour une demande k est dit faisable si -tous les arcs de p k ont une valeur SINR supérieure au seuil de qualité requis par la demande k et, -tous les noeuds de p k ont une capacité su sante pour satisfaire les besoins en ressources.

	184 1.2. LE PROBL ÈME NETWORK SLICE DESIGN CHAPTER 1. R ÉSUM É DE TH ÈSE 185
	Device-to-Device (D2D) permet aussi de réutiliser les ressources radio et de diminuer la latence établi avec succès.
	de bout en bout des communications locales. D2D permettrait à un ensemble d'utilisateurs
	géographiquement proches les uns des autres d'établir des communications D2D directes pour
	accéder à un service donné.
	Dans ce contexte, l'optimisation des ressources dans les réseaux cellulaires devient cruciale
	sur le dimensionnement des réseaux de backhauling, et donc sur le placement des fonctions
	de coeur de réseau et la configuration des serveurs d'applications edge computing. De plus,
	di↵érentes politiques de partage et de mise à l'échelle des fonctions de contrôle par rapport au
	plan de données devraient être appliquées.
	férents fournisseurs peuvent être associés à di↵érents services de communication exécutés sur le
	même réseau physique au niveau des segments d'accès, de coeur et d'application. Pour fournir le 1.1.1 Définition du problème
	provisionnement flexible nécessaire, les technologies Network Function Virtualization [1], Soft-
	ware Defined Networking [2] et Network Slicing [3] peuvent être adoptées pour permettre au Nous considérons un réseau mobile composé d'un ensemble de dispositifs, d'un ensemble
	fournisseur CS de déployer ses services sur le dessus. de réseaux logiques. d'antennes et d'un ensemble de services éligibles aux communications D2D, avec leurs matrices
	Pour faire face à ces défis, 'Network Slice' couvre non seulement l'abstraction au niveau de de trafic associées. Un poids non négatif, correspondant au SINR, est associé à chaque lien.
	C'est une mesure de la qualité de la communication qui pourrait être établie à l'aide de ce

Les flux de données sur les réseaux mobiles a une croissance très accélérée avec des demandes de plus en plus importantes depuis les années 2000. En quelques années, ces réseaux pourraient ainsi atteindre leurs capacités maximales en termes de transmission de données. Pour faire face à tous ces défis, la technologie 5G se pose en permettant la numérisation de la société et de l'information économique. L'idée derrière le concept de la 5G est qu'elle ne correspond pas à une simple augmentation du débit, comme c'était le cas pour les générations précédentes, mais aussi qu'il s'agit par là d'élargir la diversité des équipements des utilisateurs. Cette évolution technologique touchera l'ensemble de l'environnement réseau, allant des accès cellulaires et radio aux architectures de services applicatifs. Cette transition remet en question la conception du réseau, car plusieurs ressources et segments, historiquement gérés de manière indépendante, doivent être exploités à la fois avec une continuité dans l'allocation des ressources réseau et informatique et la proposition d'un service global et unique. Dans ce contexte, difl'application mais également la virtualisation des couches physiques et de commutation, avec di↵érentes technologies d'accès radio et de communication de liaison. Ainsi, chaque fournisseur de services doit pouvoir déployer ses services de communication avec des réseaux logiques, appelés Network Slices, spécifiquement adaptés à ses exigences techniques. Le mode de communication L'objectif global de ce travail est donc de définir et d'étudier le concept de conception d'D2D et de Network Slicing dans les systèmes 5G et de proposer des modèles mathématiques et des algorithmes innovants pour résoudre les problèmes d'optimisation sous-jacents. 1.1 La communication appareil à appareil Un domaine est défini comme l'ensemble des utilisateurs et des stations de base qui sont utilisés pour établir des communications mobiles (D2D ou cellulaires) liées à un service spécifique. Deux utilisateurs peuvent alors se communiquer via des liaisons cellulaires, en utilisant les liaisons classiques ou D2D, et les deux technologies peuvent coexister au sein du même réseau mobile. Dans tous les cas, des ressources radio devraient être allouées à chaque liaison active impliquée dans une communication, et le niveau SINR (Signal-to-Interference-plus-Noise Ratio) requis par le service devrait être assuré. lien. Chaque service nécessite un seuil de qualité minimal en termes de SINR et de ressources disponibles (capacité matérielle pour les appareils, ressources radio pour les liens) pour être

2.3. SOLVING APPROACHES FOR LINEAR PROGRAMMING-Runtime: Is this the best-known and fastest heuristic to solve the problem? Some heuristics converge faster than others. Some heuristics are only slightly faster than conventional methods.In some cases, it may be di cult to decide whether the solution found by the heuristic is good enough because the underlying theory of this heuristic is not very elaborate.

The content of this chapter was accepted for publication on Transactions on Network and Service Management: W. d. S. Coelho, A. Benhamiche, N. Perrot and S. Secci, "Function splitting, isolation, and placement trade-o↵s in network slicing", November 2021, Preprint.

Following the taxonomy presented in this work, these new post-processed requests can be seen as network slice subnets.

Since RF and PHY blocs have synchronous network functionalities that pose extremely strict latency requirements, we assume they are PNFs integrated to each DU. Hence, they are not considered in our virtual DP chains.

The content of this chapter was submitted to Discrete Applied Mathematics Journal as: W. d. S. Coelho, A. Benhamiche, N. Perrot and S. Secci, "Exact Approaches for the Network Slice Design Problem", September 2021.

It is worth mentioning that, if s = t, q st + q ts = 2 always holds.

As previously discussed, data-plane tra c depends on the service is provided by the slice while control-plane tra c relies on the expected number of UE and their behaviors.

The content of this chapter was published in the following paper: W. d. S. Coelho, A. Benhamiche, N. Perrot and S. Secci. "A Math-Heuristic for Network Slice Design", the 33nd International Teletra c Congress (ITC 33), Avignon, France, 2021.

RESUME

List of Tables 5.2. RELATED WORKS instance depending on the network load in order to save both virtual and physical resources. In the same context, authors in [START_REF] Alawe | Smart scaling of the 5G core network: an rnn-based approach[END_REF] propose another solution to scale dynamically the 5G NFs; the proposed approach prevents the latency and avoids overloading the core network. Authors in [START_REF] Wang | Online learning-assisted vnf service chain scaling with network uncertainties[END_REF] propose an online algorithm to minimize the cost for provisioning NF instances while minimizing the congestion in a data-center network. Authors in [START_REF] Zhang | Proactive VNF provisioning with multi-timescale cloud resources: Fusing online learning and online optimization[END_REF][START_REF] Fei | Adaptive VNF scaling and flow routing with proactive demand prediction[END_REF] propose di↵erent proactive approaches in order to estimate the upcoming tra c and adjust NF deployment a priori. While [START_REF] Zhang | Proactive VNF provisioning with multi-timescale cloud resources: Fusing online learning and online optimization[END_REF] combine an online learning method with a multi-period online optimization algorithm, authors in [START_REF] Fei | Adaptive VNF scaling and flow routing with proactive demand prediction[END_REF] aim to minimize the error in predicting the service chain demands for new instance assignment and service chain rerouting. Moreover, authors in [START_REF] Malandrino | Getting the most out of your vnfs: Flexible assignment of service priorities in 5G[END_REF] address an NF scaling and sharing problem in order to minimize the redundancy throughout the virtual networks; they propose FlexShare, a near-optimal NF-sharing algorithm capable of ensuring priority and NF sharing decisions in polynomial time. Authors in [START_REF] Truong-Huu | Service chain embedding for diversified 5G slices with virtual network function sharing[END_REF] propose a mathematical formulation and a heuristic based on a goodness function in order to address large-sized network instances; they show that sharing NFs among network slices can use up to 30% less bandwidth and 45% fewer NF instances, compared to dedicated-NF approaches. It is important to mention that, di↵erently from these works, our model also encompasses the control-plane and data-plane separation and considers di↵erent functional split options for designing NSs.

On top of mapping NFSs into network functions, we should provide a physical path connecting each pair of NFs that must be connected. In this context, each virtual link between two or more NFs has specific rules that must be ensured on the physical layer, such as ordering constraints, minimum bandwidth, and maximum end-to-end delay values. The objective might be to optimize the length of physical paths carrying NSs' flow while respecting the imposed technical constraints. These restrictions are the combination of technical constraints imposed by each network slice served by the given virtual structure. This sub-problem can be seen as a variant of the well-known multi-commodity flow problem [START_REF] Hu | Multi-commodity network flows[END_REF] with additional latency and ordering constraints. Authors from [START_REF] Wang | E cient tra c engineering for 5G core and backhaul networks[END_REF][START_REF] Molner | Optimization of an integrated fronthaul/backhaul network under path and delay constraints[END_REF] address di↵erent aspects of this problem and propose mathematical models applied to 5G networks. In [START_REF] Wang | E cient tra c engineering for 5G core and backhaul networks[END_REF], the authors propose a framework that exploits the tra c information and topology of both backhaul and core networks for 5G systems; they propose a linear programming relaxation method and a heuristic method in order to better manage network load balancing, achieving close-optimal solutions with low computational complexity. Authors in [START_REF] Molner | Optimization of an integrated fronthaul/backhaul network under path and delay constraints[END_REF], in turn, aim at integrating backhaul and fronthaul tra c over the same transport layer; a routing optimization framework is proposed, taking into account delay

MATHEMATICAL PROGRAMMING FORMULATION

x sg mu otherwise. 'k oe K(s) : s oe S, 'f, g oe F, 'u oe V (5.9)

Latency: Inequalities (5.10) ensure that each demand k oe K(s) is routed along a path that respects the end-to-end latency value requested for slice s oe S while inequalities (5.11) ensure that the maximum latency value between any pair of NFSs is also respected.

Physical Capacity: Inequalities (5.12) are the capacity constraints over the arcs of A. Note that the flow using an arc a oe A is composed of two types of tra c for each s oe S, namely the part of tra c generated by inter-NFS communication and the part of tra c generated by the demands of K(s), which is submitted to the compression coe cients ⁄. Inequalities (5.13) express the capacity constraints in terms of NFs that can be installed on each physical node u oe V .

Being the scaling coe cient related to link utilization, the NSDP is then equivalent to the following

The new objective function is then formulated as following:

min U (5.25) This formulation can be applied to any NSDP variant and a similar model can be generated in order to minimize the maximal load on physical nodes.

Sensibility analyses

We now propose an open-access framework based on the proposed MILP formulations, which encompass flexible functional splitting, with possibly di↵erent splitting for di↵erent slices and slice subnets, while taking into account di↵erent network sharing policies from 5G specifications. We also consider novel mapping and continuity constraints specific to the 5G architectures and beyond. We show by numerical simulations the impact of taking into full and partial consideration these peculiar novel technical constraints. To this purpose, we first detail the simulation setting and then expose the results.

Simulation setup

Let us detail the simulation settings.

Physical topologies

We simulated di↵erent physical networks with di↵erent features. Inspired by common access networks structure, we first propose a specific topology called Mandala (Fig. 5.2a) with the following structure: given n DU nodes, we have n/4 aggregation nodes, n/4 core nodes, and n/8 application nodes. Note that n must be equal or multiple of 8. Each DU node is connected to two aggregation nodes, which, in turn, are connected to two inner-level core nodes. Each core node is additionally connected to two application nodes, where demands are served. Finally, given two di↵erent nodes u

NUMERICAL EXPERIMENTS

We implemented our model in a Julia-JuMP environment using ILO CPLEX 12.10 as the linear solver.

Our tests were run on a Linux server with an Intel Xeon E5-2650 CPU. Finally, all tests were made by replacing the objective function (7.9) by the following one:

Model strengthening

We now analyze the impact of Symmetry-Breaking (SB) constraints (6.1), the Lower-Bound (LB) inequality (6.5), Shortest-Path (SP) constraints (6.6), and Min-Cut (MC) inequalities (6.8) on the original model (5.1)- (5.19). While each shortest path sp(k) on (6.6) is calculated using Dijkstra's algorithm [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF], we provide di↵erent minimum cuts to the set (k) on (6.8) by using Edmonds-Karp algorithm [124], Dinic's algorithm [START_REF] Dinic | Algorithm for solution of a problem of maximum flow in networks with power estimation[END_REF], and Boykov-Kolmogorov algorithm [START_REF] Boykov | An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[END_REF], which are e cient algorithms to solve the related dual Max-Flow problem. We then eliminate all arcs that do not have enough capacity to individually carry the flow of the related tra c demand. Note that, by using these three di↵erent algorithms, we can provide at most three di↵erent minimum cuts. Table 6.3 and Table 6.4 show the impact of these di↵erent models with and without the proposed inequalities. The first and second columns refer to the instance and the additional inequalities (if any), respectively.

While the third column shows the gap between the linear relaxation and the best integer solution found in one-hour runtime, the fourth column depicts the number of nodes on the branch-and-bound tree. Finally, the two last columns refer to the final gap and the total runtime. In all columns, we show the average and standard deviation of the related parameter from 10 di↵erent instances of the same class.

We observe first that LB inequality had an important impact on all instance classes, especially on scenarios with weak isolation. For instance, the average gap from the linear relaxation and final gap were respectively equal to 3% and 0% (resp. 2% and 1%) on < T, T, H, W > (resp. < S, T, H, W >)

instances. As seen in Table 6.3, SB inequalities better performed on instances with strict capacity, latency, and isolation constraints: the average reduction on the tree size was equal to 57% and 83% on < T, T, L, S > and < S, T, L, S > instances, respectively.

Interestingly, SP and MC inequalities worked better on instances with strong isolation. For in-6.5. NUMERICAL EXPERIMENTS

Final solution

If a feasible solution is generated, its cost is then calculated in step 15 of Algorithm 1 as follows:

Where y f nu oe Z 0 and µ c u are the total number of NFSs f packed into NF n and installed on node u, and the related cost per unit of resource usage c oe C, respectively. It is worthwhile mentioning that the first cost of BestSolution is set to +OE in step 1. Then, step 17 tests if a better solution should be

Summary

In this chapter, we presented and discussed the Network Slice Design Problem in 5G systems, proposing an open-access framework based on a Math-heuristic to address the underlying optimization problem. The overall idea of the proposed approach relies on decomposing the NSDP into several subproblems and sequentially solve them while encompassing control-plane and data-plane separation and novel mapping and decomposition dimensions influencing the placement and interconnection of slices. Numerical experiments showed the e ciency of our approach on di↵erent instance classes, which could attain near-optimal solutions in a competitive runtime. Comparing it to a mixed-integer linear programming formulation, the proposed Math-Heuristic could reduce the average runtime and the final gap by up to 78% and 90%, respectively. Moreover, our approach could reduce the congestion on the physical network, better balancing the data flow while considering all technical constraints. For instance, the average load on physical links and physical nodes could be reduced by 16% and 35%, respectively.

On a practical note, as our Math-Heuristic could reduce the average load on physical nodes and physical links, a tough but interesting extension is to use it within an online algorithm. Our approach might potentially increase the slice acceptance ratio, that is the ratio between the number of embedded slices and the number of requests, since the solution proposed by the Math-Heuristic distributes the data flow among several nodes and links, leading to a decreasing in the network congestion. More tests

A COMPACT FORMULATION FOR THE NSDP-DNF

x sg mu , otherwise.

'k oe K(s) : s oe S, 'f, g oe F, 'u oe V (8.6)

Latency: Inequalities (8.7) ensure that each demand k oe K(s) is routed along a path that respects the end-to-end latency value requested for slice s oe S while inequalities (8.8) ensure that the maximum latency value between any pair of NFSs is also respected.

Physical Capacity: Inequalities (8.9) are the capacity constraints over the arcs of A. Note that the flow using an arc a oe A is composed of two types of tra c for each s oe S, namely the part of tra c generated by inter-NFS communication and the part of tra c generated by the demands of K(s), which is submitted to the compression coe cients ⁄. Inequalities (8.10) express the capacity constraints in terms of NFs that can be installed on each physical node u oe V .

The NSDP-DNF is then equivalent to the following formulation:

AN EXTENDED FORMULATION FOR THE NSDP-DNF

consideration the cost of resources from host nodes and the number of built NFs, and is calculated as following:

We now propose a extended integer linear programming formulation, hereafter referred as to E-ILP, for the NSDP. The variables related to this formulation are then defined as :

The objective function consists in minimizing the total cost of the NFS copies installed over the nodes of G and the number of network functions to be built. When the costs of physical resources are unitary, it allows identifying the smallest number of NFS needed to design and embed all network slice requests in a common physical infrastructure. Constraints (8.20) ensure that exactly one virtual network template is chosen for each slice request. Inequalities (8.21) express the capacity constraints in terms of NFs that can be installed on each physical arc a oe A, while inequalities (8.22) are the capacity constraints over the nodes of V .

SOLVING APPROACHES FOR THE NSDP-DNF

Proof. The proof is trivial, since the Inequalities (3)-( 4) and integrality constraints are partially relaxed and there is no variable with fixed value.

Column generation-based algorithm

We now describe the Column Generation framework to solve the NSDP, which relies on the proposed E-ILP formulation (8. [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF])-(8.23) as the Master Problem. We first introduced the related dual formulation: the integrality constraints (8.23) are then relaxed and therefore respectively become

Then, we present an ILP formulation corresponding to the pricing sub-problem related to each slice request.

The restricted master problem

Since G(s) has an exponential number of potentially suitable templates for each slice request, the E-ILP formulation (8. [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF])-(8.23) has an exponential number of variables. Hence, we propose to initialize the master problem with only a sub-set of columns (i.e., variables related to each g oe G Õ (s) ™ G(s) for each s oe S). This model is then called Restricted Master Problem (RMP) and can be generated by proposing templates with no physical capacity requirement and cost with a large enough value (e.g., µ s g = 10 5 ). We also propose to initialize the RMP with the final solution found by the proposed Relax-and-Fix algorithm described in the previous sections.

Pricing sub-problems

We first present the D-NCILP formulating related to the linear relaxation of E-ILP, whose dual variables are depicted on the right of each related constraint class in the previous section of this work.

Concluding remarks and perspectives

We defined and studied the concept of device-to-device communications and network slicing in 5G systems and propose mathematical models and innovative algorithms to solve the underlying optimization problems. In particular, we studied the Domain Creation problem, which is a routing and resource assignment problem arising in future 5G networks. We proposed two algorithms, one exact and one heuristic, to solve it. The exact approach is based on a node-arc ILP formulation enhanced by two families of valid inequalities that are used within a branch-and-cut framework. We also presented a solving method based on a decomposition of the DCP into two sub-problems: the routing sub-problem and the resource allocation sub-problem. First, a significant impact of the cuts in strengthening the LP relaxation and reducing the computation time was observed. Despite a longer runtime for some instances using the proposed cuts, we could observe that the gap between the root solution and the final solution is always smaller when neighborhood cuts are applied. Using capacity cuts, this improvement is observed for half of the considered instances. However, the final size of the tree after finding the final solution using these cuts can be up to 76.40% smaller. Our experiments also showed that the proposed heuristic approach performs well, even on large instances with up to 2100 devices and 1500 service requests on 7-cell networks. It would be interesting and most probably very powerful to use it as a primal heuristic to boost the e ciency of an exact algorithm.

We also defined and modeled the network slice provisioning as an optimization problem including novel mapping and provisioning requirements. In particular, we considered novel mapping dimensions appearing with 5G systems, modeling the relationship between flexible radio access functional splitting, control-plane and data-plane function separation, and sharing policies. Di↵erent variants of the

Publications

In what follows, we present the published and submitted papers issued from this doctoral research.

Published papers

Contraintes de rupture de symétrie

Les inégalités suivantes sont des contraintes de rupture de symétrie pour le NSDP.

x sf nu AE

Inégalités valides

Nous présentons aussi plusieurs familles d'inéquations valides utilisées pour renforcer la relaxation linéaire de la formulation proposée.

Inégalité de la borne inférieure

La première inégalité exprime une borne inférieure sur le nombre de NFS nécessaires pour satisfaire toutes les demandes de slices et les demandes de trafic associées.

The following inequality

is valid for the NSDP.

Inégalités basées sur le plus court chemin

Les inégalités valides triviales suivantes sont basées sur le fait que le chemin physique assigné pour transporter le flux associé à une demande de trafic ne peut pas être plus court que le plus