Meihui Gao
email: meihui.gao@loria.fr

Bernardetta Addis
email: bernardetta.addis@loria.fr

Mathieu Bouet
email: mathieu.bouet@thalesgroup.com

Stefano Secci
email: stefano.secci@upmc.fr

Optimal Orchestration of Virtual Network Functions

Keywords: Network Functions Virtualization, VNF orchestration, VNF chaining, VNF placement

The emergence of Network Functions Virtualization (NFV) is bringing a set of novel algorithmic challenges in the operation of communication networks. NFV introduces volatility in the management of network functions, which can be dynamically orchestrated, i.e., placed, resized, etc. Virtual Network Functions (VNFs) can belong to VNF chains, where nodes in a chain can serve multiple demands coming from the network edges. In this paper, we formally define the VNF placement and routing (VNF-PR) problem, proposing a versatile linear programming formulation that is able to accommodate specific features and constraints of NFV infrastructures, and that is substantially different from existing virtual network embedding formulations in the state of the art. We also design a math-heuristic able to scale with multiple objectives and large instances. By extensive simulations, we draw conclusions on the trade-off achievable between classical traffic engineering (TE) and NFV infrastructure efficiency goals, evaluating both Internet access and Virtual Private Network (VPN) demands. We do also quantitatively compare the performance of our VNF-PR heuristic with the classical Virtual Network Embedding (VNE) approach proposed for NFV orchestration, showing the computational differences, and how our approach can provide a more stable and closer-tooptimum solution.

I. INTRODUCTION

After about ten years of fundamental research on network virtualization and virtual network embedding, the virtualization of network functions is becoming a reality thanks to huge investments being made by telecommunication providers, cloud providers and vendors.

The breaking point sits in 2012, when calls for experimentation and deployment of what was coined as "Network Functions Virtualization (NFV)" [START_REF] Chiosi | Network functions virtualisation: An introduction, benefits, enablers, challenges and call for action[END_REF] lead to the creation of an NFV industry research group at the European Telecommunications Standards Institute (ETSI) [START_REF] Etsi | Network Functions Virtualization -Introductory White Paper[END_REF]. Since then, applied researches and developments have accelerated investments, hence preliminary prototypes were demonstrated and deployed (leading to commercialization in some cases) since late 2014 [START_REF] Han | Network function virtualization: Challenges and opportunities for innovations[END_REF].

With NFV, the attention of network virtualization research is now focusing on key aspects of NFV systems that were either not considered relevant or not conceived before industry effort at Standards Developing Organizations (SDOs). A central role is played by the NFV service chaining [START_REF] Boucadair | Requirements for service function chaining (SFC)[END_REF] provisioning, i.e., the problem of allowing a traffic flow passing through a pre-computed or dynamically computed list of VNF nodes, possibly accounting for the fact that VNF nodes can be placed A preliminary version of this paper appeared in [START_REF] Addis | Virtual network functions placement and routing optimization[END_REF]. at, and migrated across, virtualization clusters as a function of demand assignment to existing VNF chains or sub-chains. Key aspects that are worth being mentioned (and often neglected in the proposed solution strategies) are the:

• ingress/egress bit-rate variations at VNFs, due to specific VNF operations (such as compression as with a firewall function or an egress tunneling function, or such as decompression as in an ingress tunneling function); • VNF processing and forwarding latency as an orchestration parameter. It can indeed be exponential with the traffic load on the VNF, or constant up to a maximum board if computation offloading solutions, such as direct memory access bypassing the hypervisor (as done with Intel/6WIND Data-Plane Development Kit [START_REF] Intel | Impact of the Intel Data Plane Development Kit (Intel DPDK) on packet throughput in virtualized network elements[END_REF]), or similar other 'fastpath' solutions are present.

We could not identify a work in the state of the art jointly taking these aspects all together into account. Furthermore, as summarized in Section II, most of the approaches rely on heuristic algorithms. Therefore, we propose a mathematical programming model integrating all of them and devise a method to find solutions for large size instances. A recent study [START_REF] Fischer | Generating virtual network embedding problems with guaranteed solutions[END_REF] evaluates some of them highlighting that they may come at a "Revenue/Cost" ratio of 50%, i.e., twice as many resources were consumed than demands realized by heuristic approaches, which suggests that there is significant optimization potential to achieve in the area, despite the high number of research papers on VNF orchestration. In this paper, we focus on the problem modeling and optimization, proposing a mathematical formulation to solve the NFV MANagement and Orchestration (MANO) decision making to optimality under reasonable execution time targets.

ETSI is de-facto the reference SDO for the NFV highlevel functional architecture specification. High-level means that its identified role is the specification of the main functional blocks, their architecture and inter-relationship, whose implementation elements could then be precisely addressed by other SDOs. ETSI specifies three components [START_REF]Network Functions Virtualization -Architectural Framework[END_REF] for the NFV architecture: Virtual Network Functions (VNFs); NFV Infrastructure (NFVI), including the elements needed to run VNFs such as the hypervisor node and the virtualization clusters; MANO, handling the operations needed to run, migrate, optimize VNF nodes and chains, possibly in coordination with transport network orchestrators.

MANO procedures come therefore to support the economies of scale of NFV, so that physical NFVI virtualization resources (NFVI nodes) dedicated to NFV operations are used efficiently with respect to both NFVI operators and edge users. A promising NFV use-case [START_REF]Network Functions Virtualization -Use Cases[END_REF] for carrier networks is the virtual Customer Premises Equipment (vCPE) that simplifies the CPE equipment by means of virtualized individual network functions placed at access and aggregation network locations, as depicted in Fig. I. There are also other promising use-cases like the virtualization of the Evolved Packet Core (EPC) cluster in cellular core networks [START_REF] Basta | Applying nfv and sdn to lte mobile core gateways, the functions placement problem[END_REF], [START_REF] Hawilo | Nfv: state of the art, challenges, and implementation in next generation mobile networks (vepc)[END_REF], and the virtualization of cellular base stations [START_REF] Wu | Cloud radio access network (c-ran): a primer[END_REF]. MANO operations are many and range from the placement and instantiation of VNFs to better meet user's demands to the chaining and routing of VNF chains over a transport network disposing of multiple NFVI locations. Part of the orchestration decision can also be the configuration of the VNFs to share them among active demands, while meeting common Traffic Engineering (TE) objectives in IP transport networks as well as novel NFV efficiency goals such as the minimization of the number of VNF instances to install. In this context, the paper contribution is as follows:

• we define and formulate via mathematical programming the VNF Placement and Routing (VNF-PR) optimization problem, including compression/decompression constraints and two forwarding latency regimes (with and without fastpath), under both TE and NFV objectives; our mathematical programming model is the first one in the literature taking into account explicitly all these key aspects together; • we compare the VNF-PR approach to the legacy Virtual Network Embedding (VNE) approach, qualitatively and quantitatively; to the best of our knowledge no other paper proposes such a comparison; • we design a model tailored math-heuristic approach allowing us to run experiments also for large instances of the problem within an acceptable execution time; • we evaluate our solution by extensive simulations. We draw considerations on NFV deployment strategies. The paper is organized as follows. Section II presents the state of the art on NFV orchestration. Section III describes the network model and the Mixed Integer Linear Programming (MILP) formulation. Analysis and discussion of optimization results are given in Section IV. Section V concludes the paper.

II. BACKGROUND

Network virtualization research was first driven by the convergence of computation, storage and network in cloud computing. A large number of works in the literature address the optimization of Virtual Machines (VM) placement with respect to, for example, server load balancing or energy saving [START_REF] Bobroff | Dynamic placement of virtual machines for managing sla violations[END_REF], [START_REF] Chaisiri | Optimal virtual machine placement across multiple cloud providers[END_REF]. Virtualizing the network between VMs is also a problem addressed in the area, defined as the Virtual Network Embedding (VNE) problem of mapping a set of logical graphs of interconnected VMs on a substrate graph [START_REF] Fischer | Virtual network embedding: A survey[END_REF].

In NFV, network functions that were once run by hardwarebased middleboxes [START_REF] Sherry | A survey of enterprise middlebox deployments[END_REF] are now meant to be virtualized as VNFs. VNFs can be chained together to provide a specific service, also known as service/VNF chaining. Service providers can deploy specific service chains to provide network service demands that requested by clients.

Preliminary works on NFV orchestration tend to solve the NFV orchestration problem as a VNE problem, which treats virtual network requests as logical graphs to be embedded into a substrate network. This is for example the case of [START_REF] Guerzoni | A novel approach to virtual networks embedding for sdn management and orchestration[END_REF]. VNFs are treated as normal VMs, mapped on a network of VM containers, which are interconnected via physical links that host logical links of virtual network demands. Similarly, authors in [START_REF] Mehraghdam | Specifying and placing chains of virtual network functions[END_REF] propose a VNF chain placement that combines location-routing problems and VNE problems, solving first the placement and then the chaining. In [START_REF] Moens | Vnf-p: A model for efficient placement of virtualized network functions[END_REF] the authors decouple the legacy VNE problem into two embedding problems: VM embedding and service chain embedding, where a service chain is embedded on VMs, and each VM on physical servers. Each service chain has specific requirements as notably an end-to-end latency requirement. In [START_REF] Vizarreta | Qos-driven function placement reducing expenditures in nfv deployments[END_REF] the authors consider specific constraints to guarantee the quality of service requirements in terms of forwarding latency and service chain availability. An Integer Linear Programming (ILP) model is proposed to solve the resource cost optimization problem. In addition, to cope with large instances, a greedy algorithm based on sequential chain embedding is introduced for providing near optimal solution in shorter execution time.

In its more general form, covering all the aspects of practical VNF operations, the placement and routing of VNFs does not directly match the classical VNE problem.In VNE, virtual network nodes need to be placed in an underlying physical infrastructure. However, differently from VNE, in VNF placement and routing: (i) the demand is not a multipointto-multipoint network connection request, but a point-to-point source-destination flow routing demand, i.e., VNE introduces a superstructure unnecessary to represent the problem; (ii) the VNF chain can in general have a free or partial order, feature that cannot be easily represented with the VNE model perspective; and (iii) specific aspects of NFV such as forwarding latency behavior, ingress/egress bit-rate changes, and VNF/chain composition (i.e., sharing of nodes in the VNE terminology and selection among different node sizes) are not addressed in VNE. Their inclusion would further increase the VNE time complexity (for instance, in [START_REF] Botero | Optimal mapping of virtual networks with hidden hops[END_REF] forwarding latency is considered by adding 'hidden nodes' hence largely increasing the spatial and time complexities). In this sense, the VNF placement and routing problem is closer to a facility location problem, whereas VNE is closer to a mapping problem.

We argue in this paper that the appropriate way to deal with NFV MANO decision problems [START_REF] Han | Network function virtualization: Challenges and opportunities for innovations[END_REF], [START_REF] Mijumbi | Network function virtualization: State-of-the-art and research challenges[END_REF] is to define the VNF Placement and Routing (VNF-PR) problem directly tailored to the NFV environment, for the sake of time complexity, modeling precision and practical usability. This is also the approach adopted by a few papers in the literature [START_REF] Mijumbi | Design and evaluation of algorithms for mapping and scheduling of virtual network functions[END_REF], [START_REF] Cohen | Near optimal placement of virtual network functions[END_REF], [START_REF] Luizelli | Piecing together the nfv provisioning puzzle: Efficient placement and chaining of virtual network functions[END_REF]. In [START_REF] Mijumbi | Design and evaluation of algorithms for mapping and scheduling of virtual network functions[END_REF] the authors consider the online orchestration of VNFs, modeling it as a scheduling problem of VNFs and proposing heuristics to scale with the online nature of the framework. In [START_REF] Cohen | Near optimal placement of virtual network functions[END_REF] the authors study a bi-criteria approximation algorithm for the cost minimization objective function as well as for the nodes size constraints. In [START_REF] Luizelli | Piecing together the nfv provisioning puzzle: Efficient placement and chaining of virtual network functions[END_REF] the authors propose a formulation of the VNF placement and chaining problem and an ILP model to solve it. Additionally, to cope with large infrastructures, they introduce a binary search procedure for efficiently guiding the ILP solver towards feasible, near-optimal solutions. Different to [START_REF] Mijumbi | Design and evaluation of algorithms for mapping and scheduling of virtual network functions[END_REF], [START_REF] Cohen | Near optimal placement of virtual network functions[END_REF], [START_REF] Luizelli | Piecing together the nfv provisioning puzzle: Efficient placement and chaining of virtual network functions[END_REF], in this paper, we focus on providing a more generic formulation to the VNF placement and routing problem. Apart from chaining with VNF ordering guarantees, we also capture and investigate the practical feature of traffic flow compression and decompression that could be imposed by the VNFs along the traffic route.

A common approach is to rely on graph properties to find a better utilization of the limited resources while serving a larger set of demands. In [START_REF] Bouet | Cost-based placement of vdpi functions in nfv infrastructures[END_REF] the specific Deep Packet Inspection (DPI) VNF node placement problem (without chaining) is targeted, with a formal definition of the problem and a greedy heuristic algorithm to solve it. In [START_REF] Kuo | Deploying chains of virtual network functions: On the relation between link and server usage[END_REF] the authors propose a heuristic to place and chain a maximum number of VNFs under capacity limitation; a linear programming approach is formulated to iterate the k-shortest paths computation for each VNF chain and choose the one that satisfies the maximal length and number of reused VNFs. In comparison, our proposal considers not only the efficiency of resources utilization, but also the quality of service provisioning (for instance, the traffic forwarding latency). Moreover, we discuss the tradeoff between resources efficiency goals and network traffic engineering goals.

Recently, game theoretic approaches are also considered: in [START_REF] Obadia | Revisiting nfv orchestration with routing games[END_REF] authors propose a heuristic based on routing games; in [START_REF] Elias | Efficient orchestration mechanisms for congestion mitigation in nfv: Models and algorithms[END_REF] authors propose a distributed dynamic pricing approach to allocate demands to already placed VNF instances, with convex congestion functions for both links and VNFs to control congestion.

Finally, the VNF placement and routing problem has also been addressed in specific contexts: wireless local area networks [START_REF] Riggio | Virtual network functions orchestration in wireless networks[END_REF] and optical networks [START_REF] Xia | Network function placement for nfv chaining in packet/optical datacenters[END_REF]. A comprehensive survey on NFV resource allocation and chaining was recently published in [START_REF] Herrera | Resource allocation in nfv: A comprehensive survey[END_REF].

Our paper takes inspiration from these early works, yet goes beyond being more generic and integrating in a mathematical programming model the specific features of NFV environments mentioned in the introduction and formalized in the following.

III. NETWORK MODEL

We provide in the following a problem statement, its mathematical programming formulation, and a description of its possible customization alternatives.

A. Problem statement Definition Virtual Network Function Placement and Routing (VNF-PR) Problem

The network is represented by a graph G(N, A), where N is the set of switching nodes, and A represents the possible directional connections between nodes. The router i ∈ N and its associated NFVI cluster are represented by the same node; this choice allows to keep the size of the graph limited and reduces the computational effort. We represent with N v ⊂ N the set of nodes N disposing of NFVI server clusters. We consider a set of demands D, each demand k ∈ D is characterized by a source o k , a destination t k , a nominal bandwidth b k (statistically representative for demand k), and a sequence of VNFs of different types, that must serve the demand (and therefore must be traversed by the demand). For each VNF a single VM is reserved, therefore we can equivalently speak of allocating a VM or a VNF on an NFVI node, meaning that we are reserving the necessary resources (e.g., CPU, RAM) to host a VM running a VNF. The VNF-PR optimization problem is to find:

• the optimal placement of VNF instances over NFVI nodes; • the optimal routing for demands and their assignment to VNF node chains. • subject to:

link capacity constraints; -NFVI node capacity constraints; -VNF flow compression/decompression constraints;

-VNF forwarding latency constraints; -VNF node sharing constraints; -VNF chain (total or partial) order for each demand.

The optimization objective should contain both networklevel and NFVI-level performance metrics. In our network model, we propose as network-level metric a classical TE metric, i.e., the maximum link utilization and as NFVI-level metric a measure of the overall allocated computing resources. Both objectives are -in a sequential way -minimized in the optimization model. Furthermore, we assume that:

• Multiple VNF instances of the same type (i.e., same functionality) can be allocated on the same node. Each VNF instance can serve multiple demands 1 , but each demand cannot split its flow on multiple VNF instances of the same type. • The VNF computing resource consumption can be expressed in terms of live memory (e.g., RAM) and Computing Processing Units (CPUs), yet the model shall be versatile enough to integrate other computing resources. • Latency introduced by a VNF instance can follow one among the two following regimes (as represented in Fig. 2):

-Standard: VNFs buffer traffic at input and output virtual and physical network interfaces such that the forwarding latency can be considered as a convex piece-wise linear function of the aggregate bit-rate at the VNF, due to increased buffer utilization and packet loss as the bit-rate grows as shown in [START_REF] Intel | Impact of the Intel Data Plane Development Kit (Intel DPDK) on packet throughput in virtualized network elements[END_REF], [START_REF] Intel | Network Function Virtualization Packet Processing Performance of Virtualized Platforms with Linux* and Intel Architecture[END_REF]. This is the case of default VNFs functioning with standard kernel and hypervisor buffers and sockets. -Fastpath: VNFs use optimally dimensioned and relatively small buffers, and decrease the number of times packets are copied in memory, so that the forwarding latency is constant up to a maximum aggregate bit-rate after which packets are dropped (e.g., this happens for Intel/6WIND DPDK fastpath solutions [START_REF] Intel | Impact of the Intel Data Plane Development Kit (Intel DPDK) on packet throughput in virtualized network elements[END_REF]).

Fig. 2 gives examples of forwarding latency profiles for the two cases. • For each demand and NFVI node, only one compression/decompression VNF can be installed. This allows us to keep the execution time at acceptable levels, without reducing excessively the VNF placement alternatives. This assumption can be relaxed at the cost of working on an extended graph, and therefore increasing the computational time of the algorithm. 1 this level of granularity allows to model the forwarding latency introduced by VNF instances

Binary variables

x k ij 1 if arc (i, j) is used by demand k ∈ D z f n ik 1 if demand k ∈ D uses the n-th instance of VNF of type f ∈ F placed on node i ∈ Nv y f n i 1 if the n-th instance of VNF of type f is assigned to node i ∈ Nv w f ik 1 if demand k uses a VNF of type f on node i ∈ Nv

B. Mathematical formulation

We first introduce a basic model that does not take into account latency limitations and compression/decompression features. The reason of this choice is twofold. First, it allows a clearer explanation of the model and a step by step introduction of the technicalities that allow us to keep the model 2 the maximum number of instances of VNF type f on a node i is limited by node capacity, therefore without loss of generality, we can set c f i = min r∈R Γ ir rr r linear; we recall that already without these two features, the model is a combination of a network design and a facility location. Second, as the model proved to be difficult to solve at optimality using a state of the art solver, we design a sequential procedure to reduce the solution computational time. In particular, instead of solving the overall model from the beginning, we solve a sequence of problems where the model details (latency, compression/decompression) are added step by step 3 . Therefore, this presentation allows to put in evidence the peculiarities of each model component.

1) Basic VNF-PR model: Table I and II report the mathematical notation used in the following Mixed Integer Linear Programming (MILP) that represents the basic formulation of the VNF-PR problem. We use four families of binary variables.The first family is used to represent the path used by each demand:

• x k ij represents the per-demand link utilization for demand k;

The other three families of binary variables are used to represent the VNF instantiation and the assignment of demands to VNF instances. Each VNF instance is represented by a triple (i, f, n) the n-th instance of a VNF of type f on node i;

• y f n i represents the allocation of the instance n of a VNF of type f on a node i; • z f n ik represents the assignment of a demand k to instance n of a VNF of type f , multiple demands can be assigned to the same VNF instance; • w f ik represents the assignment of demand k to a VNF of type f on node i, the specific instance is not indicated. This variable is introduced to simplify constraints [START_REF] Basta | Applying nfv and sdn to lte mobile core gateways, the functions placement problem[END_REF]. It can be removed using the equivalence with the sum of corresponding variables z (see constraints [START_REF]Network Functions Virtualization -Use Cases[END_REF]). The continuous variable U is used to represent the maximum link utilization in the network, that is the maximum fraction of link capacity that is used by the current solution. Continuous variable π ik is used to represent the position of node i in the path used to route demand k. This family of variables is necessary to impose (total or partial) order in the VNF chain. As mentioned before, we consider two objective functions:

• TE goal: minimize the maximum network link utilization:

min U (1)
• NFV goal: minimize number of cores (CPU) used by the instantiated VNFs:

min i∈Nv f ∈F n∈1..c f i rr CP U y f n i (2)
The former objective allows taking into consideration the inherent fluctuations related to Internet traffic and therefore minimizing the risk of sudden bottleneck on network links in the case bandwidth demands deviate from the expected values. Therefore, minimizing the fraction of link capacity that can be used, indirectly allows controlling the network congestion. The latter assumes the fact that today the first 3 see Subsection III-C for a detailed description of the procedure modular cost in virtualization servers, especially in terms of energy consumption and monetary cost, is the CPU. Since in common VM templates, the RAM resource is positively correlated to the CPU resource, considering CPU as reference cost indicator can indirectly imply also the consideration of the RAM consumption. We now present the constraints.

Single path flow balance constraints:

j:(i,j)∈A x k ij - j:(j,i)∈A x k ji =    1 if i = o k -1 if i = t k 0 otherwise ∀k ∈ D, ∀i ∈ N (3) Utilization rate constraints: k∈D b k x k ij ≤ U γ ij ∀(i, j) ∈ A (4)
Node resource capacity (VNF utilization) constraints:

f ∈F n∈1..c f i rr r y f n i ≤ Γ ir ∀i ∈ N v (5)
Each demand uses exactly one VNF of each required type:

i∈Nv n∈1..c f i z f n ik = 1 ∀k ∈ D, f ∈ F : m f k = 1 (6)
Constraints ( 7)-( 9) are consistency constraints among binary variables. A VNF can be used only if present, for a given node:

z f n ik ≤ y f n i ∀k ∈ D, i ∈ N v , f ∈ F, n ∈ 1..c f i (7)
If a demand does not pass by a VNF, it cannot use it:

z f n ik ≤ j:(j,i)∈A x k ji ∀k ∈ D, i ∈ N v , f ∈ F : m f k = 1 (8)
Auxiliary variables for ensuring consistency:

n∈1..c f i z f n ik = w f ik , ∀k ∈ D, i ∈ N v , f ∈ F (9)
Finally, we introduce constraints to avoid unfeasible routing and to impose the VNF chain order:

Preventing the formation of isolated cycles:

π jk ≥ π ik + x k ij -|N v |(1 -x k ij ) ∀k ∈ D, (i, j) ∈ A (10)
Imposing an order for virtual functions:

π jk ≥ π ik -(|N v | + 1)(2 -w f1 ik -w f2 ik ) ∀k ∈ D, ∀i, j ∈ N v , f 1 , f 2 ∈ F : s f2 k ≥ s f1 k ( 11
)
If we consider flow balance constraints (3) and link capacity constraints (4), for each demand, a selection of arcs forming a path plus an isolated cycle can be a feasible solution. In pure routing problems, these solutions are equivalent to the solution where routing variables along the cycle are removed and only the one along the path are kept. In fact, both constraints (3) and constraints (4) will be valid for this new solution. Our problem integrates routing features within a facility location problem, therefore such solutions cannot always be transformed in a simple path simply removing the cycle. In fact, if a facility (VNF) used by the demand is located on the cycle, removing the cycle will produce an unfeasible solution. Therefore, it is necessary to remove such solutions directly in the model, to this aim we introduced constraints (10), inspired by traveling salesman problems tour elimination constraints [START_REF] Papadimitriou | Combinatorial optimization: algorithms and complexity[END_REF]. Variable π ik represents the order of node i along the path serving demand k, therefore if arc (i, j) exists, then π jk will be at least π ik plus 1. On the other side, if arc (i, j) does not exist (x k ij = 0) then the constraint is not active: π ik is always smaller than |N v |, as a path can contain at most all the nodes in the graph. In this way, only solutions containing simple paths are allowed. These variables are also used in Equation [START_REF] Hawilo | Nfv: state of the art, challenges, and implementation in next generation mobile networks (vepc)[END_REF] to allow imposing an order on VNFs along the route of a demand k. They impose that if demand k uses VNF f 1 located on node i and its VNF successor f 2 (s f2 k ≥ s f1 k ) that is located on node j, then in the routing path of demand k node i must be precede node j.

2) VNF forwarding latency: We impose that for each demand k ∈ D a maximum latency L is allowed, to guarantee some level of Quality of Service (QoS). Latency depends on two components: link latency, represented by a parameter λ ij for each arc (i, j), and VNF latency. VNF latency depends on the used model of latency (standard or fastpath). To keep the notation as uniform as possible, we introduce an additional variable l f ik to represent the latency experienced by demand k traversing VNF f located on node i. Therefore we get a set of constraints common to both models limiting the overall latency:

(i,j)∈A λ ij x k ij + i∈Nv f ∈F l f ik ≤ L ∀k ∈ D (12)
A set of constraints depending on the chosen latency model allows to calculate the value of variable l f ik . • Standard: the latency introduced on demand k for using VNF f depends on the overall traffic traversing the VNF (its own and the one of others demands). Let us call g f j (•) the j-th component of the piece-wise linearization of the latency function for VNF of type f , then we get:

l f ik ≥ g f j ( d∈D b k z f n id ) -L(1 -z f n ik ) ∀k ∈ D, i ∈ N v , f ∈ F, n ∈ 1..c f i , j ∈ 1..n g (13)
We can observe that constraint ( 13) is active only when the demand uses instance n of VNF f on node i

f ∈ F b min k minimal bandwidth of demand k ∈ D b max k maximal bandwidth of demand k ∈ D M i maximum traffic volume that can be switched by node i Variables φ k ij ≥ 0 flow for demand k ∈ D on arc (i, j) ψ f n ik ≥ 0 flow for demand k ∈ D entering node i and using instance n of VNF f ∈ F (z f n ik = 1)
. Otherwise, as overall latency is limited by L (constraint ( 12)), any term g f j (•) must be smaller than L, and therefore, the constraint is a redundant constraint (l ik ≥ 0). We can observe that, even if in the standard latency model there is no theoretical limit on the allowed bandwidth, constraint (12) -limiting the overall latency for a single demand (VNFs forwarding latency plus propagation delay) -imposes an implicit limit on the maximum attainable bandwidth for a single VNF.

• Fastpath: the latency is fixed, but a limit in the total traffic that a VNF can support is imposed. Therefore we get the following two sets of constraints:

l f ik = lf ∀k ∈ D, i ∈ N v , f ∈ F (14) k∈D b k z f n ik ≤ B f max ∀i ∈ N v , f ∈ F, n ∈ 1..c f i ( 15
)
We can observe that constraints ( 14) can be substituted directly in constraints [START_REF] Wu | Cloud radio access network (c-ran): a primer[END_REF]. Constraints [START_REF] Fischer | Virtual network embedding: A survey[END_REF] impose that the total bandwidth traversing the n-th VNF instance of type f on node i is limited by the maximum amount of bandwidth that the VNF instance can support before rejecting a demand. Therefore, in our solutions no demand is discarded due to the fastpath mechanism. 3) Bit-rate compression/decompression: To introduce the possibility of compressing/decompressing flows for some VNFs, we need some modifications to our model description. We introduce a compression/decompression parameter µ f for each type of VNFs, µ f > 1 means that a decompression is performed by VNF f . When a demand pass through a VNF with µ f = 1, its bandwidth changes, therefore knowing just the routing (x variables) is not enough to determine the overall flow along an arc. For this reason we introduce variable φ k ij that represents explicitly the flow on arc (i, j) for demand k. Another consequence is that the classical flow balance equations are not anymore valid. To extend the model without introducing an excess of complexity, we work under the assumption that given a node i, and a demand k, such demand uses at most a VNF f with a factor of compression/decompression (µ f = 1).

We work on an extended graph to distinguish between access nodes (origin/destination nodes) and NFVI nodes (remind that with the basic model we collapsed NFVI nodes original graph extended graph i j i' i j Fig. 3. Duplication of an access node i.

on router nodes). Each access node i is duplicated in a node i as shown in Fig. 3. Arc (i, i ) will be added and all arcs (i, j) originating from access node i will be transformed in arcs (i , j). Therefore, the routing functionality is on node i and the NFVI functionality can be allocated on node i . Furthermore, we add variable φ f n ik , that represents the flow of demand k entering node i and using the instance n of the VNF of type f . If a demand passes through a VNF with a factor of compression/decompression µ f , then the out-flow of the node is proportional to the in-flow:

j∈N :(i,j)∈A φ k ij = µ f j∈N :(j,i)∈A φ k ji
or equivalently:

j∈N :(i,j)∈A φ k ij - j∈N :(j,i)∈A φ k ji = j∈N :(j,i)∈A (µ f -1)φ k ji
This equation is valid only if demand k uses an instance n of VNF f on given node i (remind that latency depends on the bandwidth passing throw a single instance). Therefore, to obtain a valid equation, we have to write:

j∈N :(i,j)∈A φ k ij - j∈N :(j,i)∈A φ k ji = j∈N :(j,i)∈A φ k ji n∈1..c f i (µ f -1)z f n ik when n∈1..c f i (µ f -1)z f n ik = 0
the constraint states that the in-flow and out-flow are the same, that is, if no VNF is traversed, the flow remains unchanged. The same result is obtained for all VNF f such that µ f = 1 (no compression/decompression). To the aim of linearizing this constraint, we introduced variable ψ f n ik (still non-linear representation):

ψ f n ik = ( j∈N :(j,i)∈A φ k ji )z f n ik
The constraints can be linearized using Equations ( 20)-( 22), with the parameter M i equal to (j,i)∈A γ ji , which represents the maximum quantity of flow that can enter node i. If (µ f -1)z f n ik = 1 then ψ f n ik representing the flow of demand k entering node i and passing through the instance n of the VNF f (constraint ( 20)-( 21)), otherwise it is zero (constraint ( 22)).

It is now possible to present the new constraints that must be added to the basic VNF-PR model: Flow balance for access nodes:

j∈N :(i,j)∈A φ k ij - j∈N :(j,i)∈A φ k ji = =        b k if i = o k 0 otherwise -b k f ∈F :m f k =1 µ f if i = t k ∀k ∈ D, i ∈ N a (16)
Flow and compression/decompression balance for NFVI nodes and for each demand:

j∈N :(i,j)∈A φ k ij - j∈N :(j,i)∈A φ k ji = f ∈F,n∈1..c f i (µ f -1)ψ f n ik ∀k ∈ D, i ∈ N v (17)
Coherence between path and flow variables:

φ k ij ≤ b max k x k ij ∀k ∈ D, (i, j) ∈ A (18) φ k ij ≥ b min k x k ij ∀k ∈ D, (i, j) ∈ A (19)
VNF compression/decompression linearization constraints:

ψ f n ik ≤ j∈N :(j,i)∈A φ k ji + M i (1 -z f n ik ) ∀k ∈ D, i ∈ N v , f ∈ F, n ∈ 1..c f i ( 20
)
ψ f n ik ≥ j∈N :(j,i)∈A φ k ji + M i (1 -z f n ik ) ∀k ∈ D, i ∈ N v , f ∈ F, n ∈ 1..c f i ( 21
)
ψ f n ik ≤ M i z f n ik ∀k ∈ D, i ∈ N v , f ∈ F, n ∈ 1..c f i ( 22
)
One compression/decompression VNF per node and demand:

f ∈F n∈1..c f i :µ f =1 z f n ik ≤ 1 ∀k ∈ D, ∀i ∈ N v (23)
Eq. ( 16) represents the flow balance for the access nodes. At destination node the quantity of flows is set equal to the demand multiplied for all factors of compression of all the demanded VNFs. Eq. ( 17) represents the flow balance for a given node that has the possibility of hosting VNFs (NFVI). Eq. ( 18)-( 19) allow to connect variables x and φ, in such a way that only and only if arc (i, j) is used by demand k, that is x k ij = 1, then variable φ can be different from zero. As the demand passes through VNF that can compress or decompress the flow, then we can determine upper and lower bound for the demand that are:

b max k = b k f ∈F :µ f ≥1 and b min k = b k f ∈F :µ f ≤1
4 . Variables x are still necessary to impose the isolated cycles elimination and the order in the VNF chain. The utilization rate constraints must be modified as follows: 4 To avoid these parameters being zero when does not exist any VNF with µ f ≥ 1 (only decompression), and µ f ≤ 1, respectively, the calculation of the parameter can be modified in b 4), ( 5)-( 11) basic-lat (3), ( 4), ( 5)-( 11) [START_REF] Wu | Cloud radio access network (c-ran): a primer[END_REF], [( 13) vs ( 14)-( 15)] basic-lat-cd

k∈D φ k ij ≤ U γ ij ∀(i, j) ∈ A (24)
max k = b k max{1, f ∈F :µ f ≥1 } and b min k = b k min{1, max{0, f ∈F :µ f ≥1 }}, respectively.
(3), ( 24), ( 5)-( 11) [START_REF] Wu | Cloud radio access network (c-ran): a primer[END_REF], [( 13) vs ( 14)-( 15)] ( 16)- [START_REF] Mijumbi | Network function virtualization: State-of-the-art and research challenges[END_REF] To take into account the combined effect of compression/decompression and VNF latency some modification are needed.

For the standard model, constraints [START_REF] Bobroff | Dynamic placement of virtual machines for managing sla violations[END_REF] are modified as follows:

l f ik ≥ g f j ( d∈D ψ f n id ) -L(1 -z f n ik ) ∀k ∈ D, i ∈ N v , f ∈ F, n ∈ 1..c f i , j ∈ 1..n g (25)
For the fastpath model, constraints [START_REF] Fischer | Virtual network embedding: A survey[END_REF] are modified as follows:

d∈D ψ f n id ≤ B f max ∀i ∈ N v , f ∈ F, n ∈ 1..c f i (26)
In Table V we summarize the different models. In the first column a short name is used to refer to each model, in the second column constraints necessary to model routing, location and resource capacity are reported. In the third and forth columns we report latency and compression/decompression constraints.

C. Multi-objective math-heuristic resolution

We face a multi-objective problem: minimizing the maximum link utilization, which reflects the ISP-oriented vision to improve the user quality of experience (strictly related to link congestion, especially for real-time services) and minimizing the virtualization infrastructure cost evaluated as the number of required CPUs at the NFVI level, which reflects the aims of the NFVI provider. Such a multi-objective approach makes especially sense when the NFVI provider is a different entity than the ISP. These two objectives are in competition; in fact, to obtain a low utilization, a large number of VNFs must be allocated.

We decided to prioritize the objectives: first we minimize the maximal link utilization (U ), and then the NFV cost (total number of used CPU). We refer to this as the TE-NFV objective. In practice, we perform a first optimization step to find the best solution accordingly to maximal link utilization (U ), and then, keeping the best value found in the first step as a parameter (i.e. adding the constraint U ≤ U ), we minimize the second objective (NFV cost). In fact, for a given optimal value of the first step, different possible configurations are available to the second step, and a large primary cost reduction can be achieved by this second step without losing with respect to the primary objective (maximum link utilization).

In order to understand the impact of imposing a maximal link utilization constraint on the NFV cost, we decided to study the sensitivity of the second step of optimization on the optimal value U . Therefore, we re-optimize the second objective relaxing the constraint on the maximum link utilization by a parameter α, i.e. we used constraint U ≤ α + U instead of U ≤ U . We increase α step by step, until the value of the NFV cost does not reduce anymore. This value corresponds to first minimize the NFV cost and then the maximum link utilization cost (NFV-TE).

From preliminary tests, we observed that optimizing the complete model is very expensive, and that computational time can be significantly reduced performing a sequence of optimization starting from a basic model to the complete one. The result of each step is used as a starting point for the following one, a so-called warm-start, that allows to reduce computational time and/or produce better solutions or gaps (when optimization is stopped before reaching the optimal solution). To be more precise, the sequence of models we optimize is first the basic one (only demand routing, VNF location and capacities are considered), then basiclat (latency is added) and finally basic-lat-cd (latency and compression/decompression are added), see Section III and Table V for the complete description of the models and equations involved.

The most challenging model from an optimization point of view is the last one, basic-lat-cd. For this reason, we need to provide a feasible starting solution (warm start) for this step. To this aim, the previous step, optimizing basic-lat model, must be done with some slightly modification. The compression/decompression feature changes the quantity of flow that traverses the graph, therefore to guarantee that the solution of the second step is feasible for the last one, it is necessary to route a worst case quantity of flow, given by the case that all the VNFs with decompression are already applied to the demand flow 5 .

The NFV objective function results to be computationally more challenging than the TE one. Therefore, for obtaining the optimal solution of the NFV goal, a bisection procedure is used on the number of allocated VNFs/VMs to guarantee solution optimality, even when in a single step the solver is not able to guarantee it: that is, at each bisection step, if a feasible solution is found, the number of VNF/VM is divided by two, and if no feasible solution exists then it is doubled. From numerical experiments, we observed that, for our problem, determining that an instance is unfeasible (fixing a maximum number of VNF instances) using the TE objective is computationally less challenging than solving to optimality the model using the NFV objective function. For this reason, the speed up obtained using the bisection procedure allows us to solve to optimality, or obtain a solution with a small gap on a larger number of instances than solving directly the NFV objective problem.

D. Further model refinements

The model we provided above can be possibly refined and customized to meet specific requirements. We list in the following the possible variants as well as the corresponding modeling variations.

• VNF affinity and anti-affinity rules: due to the privacy, reliability or other reasons, a provider may want impose rules on the placement of certain types of VNF: be placed or not placed on certain servers, be grouped or not grouped together, etc. Such specific VNF placement rules are called affinity and/or anti-affinity rules [START_REF] Bouten | Semantic validation of affinity constrained service function chain requests[END_REF]. To extend our model to take them into account, the simplest way is to introduce a new variable representing the presence of a certain type of VNF f on a given node i (we remind the reader that our model allows to have multiple copies of the same type of VNF on the same node). Let us call this variable v f i , it will be equal to one if a VNF of type f is located on node i. To make these variables consistent with already defined variables y f n i , we need to add:

n∈1..c f i y nf i ≤ c f i v f i ∀i ∈ N v , f ∈ F
More precisely, common affinity/anti-affinity rules are:

-VNF-VNF affinity rules: if two VNFs communicate frequently and should share a host node, we may want to keep the VNFs together in order to reduce traffic across the networks and improve the traffic efficiency. Let AffVV f1f2 be a parameter equal to one if f 1 and f 2 should share the same node. Then:

v f1 i = v f2 i ∀(f 1 , f 2 ) : AffVV f1f2 = 1
-VNF-Server affinity rules: certain intrusion prevention VNFs should reside in the network edges to guard against worms, viruses, denial-of-service (DoS) traffic and directed attacks. Let AffVS i be a parameter equal to one if f should be installed on i. Then:

v f i = 1 ∀(i, f ) : AffVS f i = 1 or restricted to a subset of nodes S ∈ N v : i∈S v f i = 1 ∀(i, f ) : AffVS f i = 1
-VNF-VNF anti-affinity rules: it may be required to install multiple instances of the same VNF onto multiple servers in order to improve VNF reliability against failures. Let AAff f be the anti-affinity parameter; we then impose that at least nbM in nodes host the VNF:

n∈Ns v f i ≥ nbM in ∀f : AAff f = 1
if different VNFs cannot be co-located, let AAffVV f1f2 be the anti-affinity parameter and impose:

v f1 i + v f2 i ≤ 1 ∀(f 1 , f 2 ) : AAffVV f1f2 = 1 -VNF-
Server anti-affinity rules: it may be required to avoid resource-hungry VNFs residing in certain cost-critical servers. Let AAffVS f i be the anti-affinity parameter and impose:

v f i = 0 ∀(i, f ) : AAffVS f i = 1
We can observe that all the constraints that set some variables to one or zero, just reduce the number of variables; therefore we can expect that such constraints do not increase the computing time. A slightly different condition can be imposed for sharing a VNF among different demands; we refer to that as VNF isolation. • VNF isolation: if the same VNF cannot be shared between two specific demands, we can add constraints to impose this condition. It is sufficient to introduce an incompatibility parameter inc k1k2 , equal to one if demand k 1 must be isolated from demand k 2 ; then we need to add:

z f n ik1 + z f n ik2 ≤ 1 ∀i ∈ N v , f ∈ F, n ∈ 1..c f i , k 1 , k 2 ∈ D
• Multiple comp./dec. VNFs per NFVI node: to make the presentation simpler, we assumed that in each NFVI node there is at most one VNF that can compress/decompress a flow, i.e. with a factor of compression µ f = 1. This assumption can be relaxed using an extended graph in which each node that can host a VNF (N v ) is expanded in multiple copies, one for each type of VNF that can be allocated in the node. Otherwise, we can represent all possible combinations of different VNFs allocated to the same node, and adding additional binary variables to represent which combination is chosen. • VNF partial chain ordering: we can observe that partial order can be imposed with a the same form of constraints used for total ordering [START_REF] Hawilo | Nfv: state of the art, challenges, and implementation in next generation mobile networks (vepc)[END_REF], just limiting their number to existing precedence conditions. It is sufficient to introduce a constraint for each couple of VNFs that has a precedence relation. More formally, for each demand k, we can introduce a directed acyclic graph O k (V k , P k ), where nodes V represent the set of VNFs that must serve the demand (V = {i ∈ F : m f k = 1}), and arcs P represent the order relation between such VNFs, that is an arc (i, j) ∈ P if VNF j must be used after VNF i. Then, constraints [START_REF] Hawilo | Nfv: state of the art, challenges, and implementation in next generation mobile networks (vepc)[END_REF] can be rewritten as:

π jk ≥ π ik -(|N v | + 1)(2 -w f1 ik -w f2 ik ) ∀k ∈ D, ∀i, j ∈ N v , f 1 , f 2 ∈ V k : (f 1 , f 2 ) ∈ P k
• Additional computing constraints: it can be easily included by tuning existing parameters, as far as computing resource requests can be expressed in an additive way (e.g., for storage). • Load balancing: in the current model, each demand can use a single VNF for each type. The model can be extended to allow per-VNF load balancing. If the load balancing is local to an NFVI node , the change in the model is small, in fact it is simply necessary to have some continuous variables taking into account the quantity of demand associated to each VNF. If the load balancing can be between different clusters, then it is necessary to extend the model allowing multiple paths for each demand. However such an extension is expected to largely increase the execution time. • Different VM templates: for the sake of simplicity, differently from [START_REF] Addis | Virtual network functions placement and routing optimization[END_REF], we presented the model considering a one-to-one correspondence between VNF and VM templates (single template). Nevertheless, multiple VM templates can be considered in the model at the price of increasing of one dimension/index all variables indexed on the VNF identifiers.

• Core router as a VNF: if the core routing function is also virtualized, i.e., if the NFVI node and the network router can be considered as a single physical node that runs the core routing function, processing the aggregate traffic independently of the demand, as a VNF, then we need to add a term proportional to InFlow plus OutFlow to (5):

k∈D f ∈F n∈1..c f i rr r y f n i + k∈D j:(i,j)∈A b k x k ij + k∈D j:(j,i)∈A b k x k ji ≤ Γ ir ∀i ∈ N v , r ∈ R
If bit-rate compression/decompression is considered, constraint ( 5) must be modified as follows:

k∈D f ∈F n∈1..c f i rr r y f n i + k∈D j:(i,j)∈A φ k ij + k∈D j:(j,i)∈A φ k ji ≤ Γ ir ∀i ∈ N v , r ∈ R

IV. RESULTS

Computational results are divided in two main parts: first, in Section IV-A, we show results using our VNF-PR algorithm under different case-study choices of demand distribution and different VNF forwarding latency models and values. Then, in Section IV-B, we present comparison results between our VNF-PR algorithm and a VNE algorithm.

A. Results of VNF-PR algorithm under different case-studies and different VNF forwarding latency profiles

In this section, we report experiments on our VNF-PR model and algorithm under different scenarios. We first present the parameter setting and then the analysis of the results.

1) Test settings: We adopt the three-tier topology represented in Fig. 4 for computational evaluation. Each edge node is connected to two aggregation nodes, each aggregation node is connected to two core nodes, and core nodes are fully meshed. We believe that this topology gives a good abstraction to represent the current vision on NFV deployment strategies: mobile edge facilities are represented by edge nodes, pointof-presence by aggregation nodes and data-centers by core nodes. Furthermore, the highly symmetric graph topology produces two main effects: it allows to better analyze the VNF distribution and the effects of latency limits and, on the other hand, produce a very challenging instance for the optimization phase, allowing to test the model in a stressful condition. As for the VNFs, we consider three VNF template types per traffic demand: one with a compression behavior, one with a decompression behavior and a third with no compression/decompression. For the sake of illustration, we name each of these templates with a realistic VNF type name: a 'Firewall' VNF for the compression (as it blocks part of the incoming traffic/packets), a 'Deep Packet Inspection (DPI)' VNF for the case with no compression, i.e., decompression, and a 'Tunneling ingress VNF' for the decompression (as headers are added to packet in the entry end-point). For the latter VNF, the assumption we do is that the egress tunneling is done elsewhere in the Internet or in the access border side. We considered a strict order for the VNFs chain: Firewall VNF first, then DPI VNF, and finally Tunneling ingress VNF. Each VNF instance has to reserve its own VM, and we consider one single VM template requiring 1 CPU and 16 GB of RAM. Table VI presents the evaluation settings of the network resources. NFVI nodes are dimensioned with an increasing capacity from edge to core: 3 CPUs and 40 GB RAM at each edge node, 5 CPUs and 80 GB RAM at each aggregation node and 10 CPUs and 160 GB RAM at core nodes. The physical links are also dimensioned with different capacity to represent realistic settings: the aggregation links are dimensioned so that there is a risk of link saturation (i.e. link utilization higher than 100%) if the traffic distribution is not optimized, while the core links are dimensioned such that there is a very low bottleneck risk. Link latencies are set as follows to cope for the different geographical scopes: 1ms for edge links, 3ms for aggregation links, and 5ms for core links. We run our tests using two different case-studies for the demand distribution: Internet and Virtual Private Network (VPN). In the Internet case-study (e.g., the flow in red on Fig. 4), the traffic demands are sent by each edge node (e.g., end user) to each core node (e.g., data center), and from each core node to reach each edge node, which means that in this case both edge nodes and core nodes are access nodes (i.e., where demands are generated); while under VPN case-study (e.g., the flow in blue on Fig. 4), the edge nodes send traffic requests to each other, which means that the set of edge nodes corresponds to the set of access nodes. The total number of traffic demands is different for the two case-studies (36 for Internet and 30 for VPN), but we kept constant the average total traffic volume (sum of demands) in the network for the sake of comparison. As shown in We run tests for both Internet and VPN case-studies under standard as well as fastpath latency profiles, VNF processing latencies being set as in Fig. 2. The two profiles differ for their behaviors with respect to the bandwidth: fastpath has a fixed latency and it rejects demands beyond a given threshold, while the standard profile can accept a larger amount of demands at the cost of a larger latency. For both profiles, the same end-toend latency is assigned to the bandwidth corresponding to the fastpath threshold. This allows to better compare the behavior of the two profiles. With fastpath we expect to aggregate demands up to the threshold (in the limits of the granularity of the demands and the routing possibilities), whereas with the standard profile we expect that a larger latency can be accepted (as long as we stay in the overall latency demand threshold) to reduce the number of VNF instances. In addition, we consider two levels of end-to-end latency bound (L): the strict and loose values (15ms and 20ms, resp.). To be precise, we run tests with both strict and loose latency bounds for the following combinations of scenarios:

• TE goal and TE-NFV goal both with:

-Internet demand profile: * standard forwarding regime * fastpath forwarding regime -VPN demand profile * standard forwarding regime * fastpath forwarding regime

For a total of 16 different cases (each of them repeated for 10 random generated demand instances). The model is implemented and solved using AMPL and CPLEX 12.6.3.0. The execution time is limited to 600s for each basic TE optimization phase (i.e., model basic and basiclat) and 800s for the complete TE phase (namely model basiclat-cd), as well as for each step of the dichotomy of the NFV optimization phase.

2) General observations: In this section, we introduce general considerations from a computational point of view, discussing the quality of the results in terms of optimality and gap of the solutions. In Section IV-A3 to IV-A6, we provide detailed analysis of the structure and properties of the solution in terms of network and system indicators.

Table VIII presents the averaged, minimum and maximum results of the complete TE objective stage (using a time limit of 800s) for Internet and VPN case-studies considering the 10 random instances. We observe that for both Internet and VPN cases, the results of the complete TE objective stage of all the 10 test instances are stable: around 0.45 in Internet case and 0.60 in VPN case. The obtained results have an average optimality gap of 15%. In some instances the optimality of the solution is certified (i.e., optimality gap is 0%) and in the worst case the optimality gap is 25%. These optimality gaps may appear large, but we need to observe that the optimality gap is only an upper bound to the distance from the optimal value, and in some cases, even if the current solution shows large gap, it can be the optimal one 6 . Therefore, to further investigate this aspect, we have performed some additional tests with a longer time limit (2 hours), and we could certify that the solutions found with a smaller (800s) time limit were optimal. As for the NFV objective stage, it is hard to reach the optimum within the time limit of 800s. Moreover, we observe that the results depend on the case-study: with the VPN case, under both standard and fastpath latency profiles, we obtain a lower optimality gap and a smaller variation of it than with the Internet case. A possible explanation is the increased number of traffic demands with the Internet case-study, which seems to significantly impact on the computational effort.

Fig. 5 illustrates the problem size with regard to the number of VNF types of both VPN and Internet case-studies. As shown In the following, we present the analysis of the solutions behavior. We compare the two different demand case-studies (i.e. Internet and VPN) with two points of view: i) what happens when we consider the NFV cost in the objective function instead of TE (Section IV-A3 and Section IV-A4), and ii) what happens when we make stronger the bound on the end-to-end latency (Section IV-A5). Then we also compare the behavior with respect to the latency profiles (Section IV-A6).

3) TE vs. TE-NFV objective: We analyze the difference between the results with the TE objective and the results with the composite TE-NFV objective.

• NFVI cost (Fig. 6 and Table IX): Table IX shows the averaged total NFVI cost (i.e., the number of used CPU) obtained using the TE objective and the TE-NFV objective for both Internet and VPN cases following the standard forwarding latency profile. In the fourth (respectively seventh) column the percentage reduction in the total NFVI cost is reported. As expected, the value is reduced, but it is worth to notice that the reduction is quite significant for both Internet and VPN traffic models. Moreover, the cost reduction with VPN is more significant than with Internet, especially with a loose bound on the end-to-end latency (L = 20ms), the total cost was reduced by 58.66% in average. As we discussed in Section IV-A2, a possible explanation is the increased number of traffic demands with Internet case, which leads to possibly lower quality solutions. The variation of solutions for Internet case can also be observed in Fig. 6, where the VNF node distribution (i.e., the number of used CPU by each VNF type across NFVI edge, aggregation and core levels) is illustrated for both Internet and VPN cases with a confidence interval of 95%. In plot (b) of Fig. 6 (with TE-NFV objective), the number of VNF instances varies greatly. While in plot (a) (with TE objective), the number of VNF instances varies gently.

Although there is big variation in the solutions with the TE-NFV objective, and even if the solutions are not optimal, the averaged total NFVI cost is reduced greatly with a better deployment of VNF distribution. This result shows that considering the NFV cost in the TE objective can reduce significantly the resource consumption even without reaching the optimality. • Link utilization (Fig. 7): in addition, the link utilization is not significantly affected by including the NFV cost minimization in the optimization goal. As illustrated in Fig. 7, in both cases with the TE goal, the aggregation links get most used. Furthermore, Internet case uses less the edge links, while VPN case uses less the core links. When taking into account the NFV cost in the objective, this behavior remains the same in both cases. This result shows that the TE-NFV goal can reduce the resource consumption without affecting the link utilization. • VNF forwarding latency (Fig. 8): with both Internet and VPN demands, it increases passing from the TE goal to the TE-NFV one. This suggests that adopting the TE-NFV goal allows a higher level of VNF sharing for both latency bound situations. 4) Relaxing the TE constraint -sensitivity to maximum link utilization: We perform a sensitivity analysis to put in evidence the effect of relaxing the TE objective with respect to the NFV optimal cost, with the goal to further put in evidence the trade-off between the two objectives. With the TE-NFV objective, even if the VNF allocation cost is minimized, a minimum maximum link utilization is guaranteed. What we want to analyze is the impact of the TE bound on the NFV cost objective optimization. To this aim, starting from the TE optimal value, we perform a series of optimization steps of the NFV cost objective function, allowing this bound to be relaxed, increasingly.

Table X shows the NFV cost (average of 10 executions) under different limit of maximal link utilization (U ). We calculate the NFV cost under U = U + α, with α varying from 0 to 0.4. For both Internet and VPN cases, when α = 0, the TE bound (U ) used for the TE-NFV phase is the U found in TE phase; when α = 0.4, the U used for the TE-NFV phase is around 1 (i.e., link saturation reached). The results show that a loose TE bound (link utilization) allows a better TE-NFV solution. For most cases, there is almost no reduction (or no reduction at all) from α = 0.2 to α = 0.4, which suggests that there exists a ceiling between the TE objective and TE-NFV objective: we can get better utilization of NFV resources (i.e., TE-NFV objective) by allowing relaxed link utilization limit (i.e., TE objective), however this is not always true when we reach the ceiling (e.g., other limits like VM capacity also impact NFV cost). While for case FastPath Internet L = 20ms, there is a reduction of NFVI cost with α increasing from 0.2 to 0.4. We can observe that for the same case-study with L = 15 the best objective found is 31 (both for α = 0.2 and 0.4), therefore we can attribute this change in behaviour to the not optimality of the solution in the case L = 20, rather than to a different behaviour of the system (we remind the reader that the problem is computationally very challenging, and we imposed a short time limit).

5) Sensitivity to the latency bound:

We analyze the impact of the VNF chain latency bound (L) on the results.

• NFVI cost (Fig. 6 and Table IX): as shown in Table IX, the averaged total cost is reduced with VPN demands under both optimization goals with a loose latency bound, especially with the TE-NFV goal. This happens because, with a loose latency bound, the traffic can pass by the links with high latency (e.g., core links) to share more VNFs. On the contrary, there is a small cost increase with Internet demands under TE-NFV goal. Analyzing in a more detailed way the results, we observe that for the Internet case-study, the solver (CPLEX) has more difficulties to reduce the gap. We can deduce that making the latency bound weaker makes the location problem component (locating VNF and the NFV goal) predominant with respect to the routing one, in fact, if the latency bound is large enough the routing problem is not constrained anymore, and more routing solutions are available; this allows more freedom in the location part, and probably increases its combinatorial structure, and therefore it makes the solution of the problem computationally more challenging. This is also confirmed by a noticeable variability in the results, with a smaller averaged cost reduction as shown in Table IX passing from strict latency (with a cost reduction of 26.86%) to loose latency bounds (with a cost reduction of 13.05%). Moreover, we can see that with VPN demands, there is a higher dependency to the latency bound than with Internet demands; this happens because in general it is farther to send traffic demands from edge node to edge node than from edge (core) node to core (edge) node, i.e., the endto-end forwarding path of VPN demands is in general longer than that of Internet demands, which leads to a higher dependency to the latency bound. • Link utilization (Fig. 7): in support of the abovementioned analysis, we can remark that under the loose latency bound, the core links get more utilized with VPN demands. While with Internet demands, the link utilization remains almost the same. This indicates that VPN case is more sensible to the latency bound. • VNF forwarding latency (Fig. 8 and Table XII): the same observation can be obtained by looking at end-to-end latency components, as shown in Table XII, the averaged total latency of VPN is always greater than Internet. Moreover, as shown in Fig. 8, the latency of each VNF and the total latency become longer with VPN demands with loose latency bound.

These observations confirm the importance of the bound for VNF chaining and placement decisions.

6) Standard vs. fastpath VNF switching: We now compare the results with the standard VNF forwarding latency profile to those with the fastpath profile.

• NFVI cost (Fig. 6 vs. Fig. 9, and Table IX vs. Table XI):

under the TE-NFV goal, the fastpath VNF forwarding is more expensive than the standard forwarding with VPN demands, especially with a loose bound on the end-toend latency (L = 20ms), the averaged total NFVI cost is 35.9 under the fastpath profile and 20.9 under the standard profile. While it is the opposite with Internet demands, for example, with the loose latency bound of 20ms, the averaged total NFVI cost of the TE-NFV goal is 52 under the standard profile, while it reduces to 38.7 under the fastpath profile. This happens because of the maximum traffic bound that is set under the fastpath case and that is not set for the standard case (which however brings to a higher end-to-end latency as confirmed in the last item hereafter), therefore, more VNF instances need to be deployed, which in turn increase the total cost. • Link utilization (Fig. 7 vs. Fig. 10) : the only difference between the link utilization under the standard and the fastpath profiles is remarkable for the case of VPN: the core links get less used with the strict latency bound of 15ms under the standard profile, while they are not used at all under the fastpath profile with the strict latency bound. However, there is no clear difference for both forwarding profiles when taking into account the NFV cost in the objective. Moreover, the behavior of the models is similar under the two forwarding profiles, when passing from strict latency limit to the loose one: under both the standard and the fastpath profiles, the core links get more utilized with VPN demands, while with Internet demands, the link utilization remains stable. • VNF forwarding latency (Fig. 8 vs. Fig. 11): as discussed previously, the VNF forwarding latency and the total latency under the standard profile increase passing from the TE goal to the TE-NFV goal. While this is not the case under the fastpath profile: the total end-toend latency under the fastpath profile remains almost the same passing from the TE goal to the TE-NFV goal. For example, as shown in Table XII, the averaged total latency is the same for the TE and the TE-NFV goal in the case of VPN demands with both strict and loose latency bounds and also in the case of Internet demands with loose latency bound. This is because of the maximum traffic bound set under the fastpath case but not under the standard case. Therefore the standard model can allow a higher demand aggregation on a single VNF. More precisely, it can support a larger bandwidth than the fastpath model while introducing a higher VNF forwarding latency. As a result, VNFs are better shared under the standard case, and especially with the loose latency bound. This also can be observed by detailed results on latency components as shown in Table XII.

For instance, under the standard profile with the TE-NFV goal, the averaged forwarding latency on each VNF instance of VPN is more than 1ms under both strict and loose latency bound. Furthermore, under the loose latency bound (L = 20ms), the averaged forwarding latency on each VNF instance is more than 1.5ms. This result also confirms the results reported in Table IX: the total cost of TE-NFV goal has been reduced by 58.66% in average, which shows that VNFs are better shared with the TE-NFV goal and under the standard case. To conclude, we discuss in this section the experimental results of our VNF-PR algorithm based on a large number of tests of different scenarios. The results show that the TE-NFV goal allows a significant higher level of VNF sharing with both the strict and the loose latency bounds. As a result, considering the NFV cost in the objective function reduces greatly the resource consumption (in terms of number of CPUs) without affecting the link utilization. Furthermore, by extensive tests of relaxing the TE objective with respect to the NFV cost, we find that there exists a ceiling between the TE objective and the TE-NFV objective: we can get better utilization of NFV resources by allowing relaxed link utilization limit, however this is not always true when we reach the ceiling. As for the TE-NFV goal with both the standard and the fastpath forwarding profiles, the total cost depends on the traffic model: the standard forwarding is more expensive than the fastpath with Internet demands, while it is the opposite with VPN demands. However, VNFs are better shared under the standard case for both Internet and VPN demands with the loose latency bound.

B. VNF-PR vs. VNE based approaches

In this section, we compare our VNF-PR approach with the VNE Based ('VNE-B') approach, already discussed in the beginning, using the algorithm from [START_REF] Bari | On orchestrating virtual network functions[END_REF], which is open sourced by the authors 7 .

In [START_REF] Bari | On orchestrating virtual network functions[END_REF], a VNE-B modeling approach is proposed for a generic VNF orchestration problem: each traffic demand is considered as a virtual graph (i.e., G(N, L) in [START_REF] Bari | On orchestrating virtual network functions[END_REF], where N is the set of traffic nodes, i.e., switches or VNFs, and L denotes the links between them) to be embedded in the substrate graph represented by switches/routers and NFVI nodes. The mapping of virtualized traffic demands' path onto a physical network is realized by embedding VNFs on physical servers and establishing path for virtual links. The objective considered is the minimization of the overall OPEX (OPerational EXpenditure) cost: VNF deployment cost, energy cost, traffic forwarding cost and an additional penalty to take into account Service Level Objective (SLO) violations. A weighted sum of the four aforementioned costs is considered as optimization objective. Authors proposed an ILP model, and they presents two different problems, a static one -where demands are know in advance -and a dynamic one -where demands arrive in an online fashion. In our comparison, we focus on the static version of the problem and its proposed solution approach; it is based on a procedure that solves a sequence of ILPs, where, for each iteration, the number of VNFs is limited and the execution time is limited as well. ILP executions are solved with CPLEX (using the callable library).

For the sake of comparison, we adapt our original VNF-PR model to the hypothesis used in [START_REF] Bari | On orchestrating virtual network functions[END_REF]; we list in the following the simplifications and adaptations to our model in order to use the same parameters used in the VNE-B approach:

• We reduced our objective to a single objective: minimizing the overall network operational cost, using the same parameters of the VNE-B approach. • We considered only the fastpath latency regime, i.e., we fixed the VNF forwarding latency. • We discarded compression/decompression aspects, i.e., we adopt our 'basic-lat' model. • As the VNE-B approach uses VNF templates, we associated a VNE template to each VNF type according to VNF requested number of vCPUs; for example, a template with capacity of 4 CPUs is associated to the VNF requesting 4 CPUs. • We added the penalty parameter for each traffic request to take into account SLO violations. Furthermore, similarly to the NFV cost optimization phase of our VNF-PR approach described in Section III-C, authors in [START_REF] Bari | On orchestrating virtual network functions[END_REF] use a dichotomy method on the number of VNFs. In order to understand the impact of adding the dichotomy method and to have a fair comparison, we tested two solving strategies for our model:

• VNF-PR algorithm: the adapted VNF-PR model solved directly without the dichotomy procedure. • VNF-PR-D algorithm: the adapted VNF-PR model solved with the dichotomy procedure. For the sake of comparison, we integrate our adapted VNF-PR model into the same procedure used in [START_REF] Bari | On orchestrating virtual network functions[END_REF] (i.e., replacing their model by ours in the dichotomy procedure) As for the evaluation test, the network settings are taken directly from the simulation setup of [START_REF] Bari | On orchestrating virtual network functions[END_REF]: adopting the Internet2 topology (12 switches and 15 links), setting the same physical link and NFVI server capacities, using the same VNF specification, VNF requests sequence, etc, and adopting the same cost data. As for the traffic data, we created 5 groups of tests with different sets of traffic requests (6, 12, 18, 24 and 30); for each group, we randomly selected from the traffic matrix set of [START_REF] Bari | On orchestrating virtual network functions[END_REF] 10 matrices. Then we tested these groups of data with the three methods (i.e., VNE-B, VNF-PR and VNF-PR-D). Our algorithms are implemented in AMPL, and the VNE-B algorithm is implemented in C++ using CPLEX for ILP resolution. CPLEX 12.5.1 was used for these tests. Fig. 12 reports a comparison between our VNF-PR solution and the VNE-B solution in terms of global cost, each group of bars represents results for different number of traffic requests. Note that VNF-PR is an exact method that finds always the optimal solution, while VNF-PR-D and VNE-B use the dichotomy process, so that they may provide suboptimal solutions. Moreover, the dichotomy process provides a set of feasible solutions and not a single one. Therefore, Fig. 12 illustrates 5 bars representing the solutions of different algorithms. More precisely, we report the optimal solution for VNF-PR, and we report the best solution as well as the average value of the feasible solutions for the VNE-B algorithm and the VNF-PR-D algorithm. As a result, the absolute optimality gap for sub-optimal solutions is shown by the difference between the red bar (optimal solution) and each other bar. We observe that VNF-PR-D is able to find better solutions compared to the VNE-B algorithm, especially when the amount of traffic demands is small where it can always find optimal solutions. While the VNE-B algorithm is always able to find a feasible solution very fast (i.e., within 10 seconds vs. up to one hour for our method), the result can be of very low quality, in fact it does not provide optimal solution even for the test with 6 demands.

V. CONCLUSION

In this paper we proposed a VNF chaining and placement model, including an algorithm formulated a mixed integer linear program, which goes beyond recent work in the state of the art. Our model took into consideration specific VNF forwarding modes (standard and fastpath modes), VNF chain ordering constraints, as well as flow bit-rate variations; these constraints make the allocation of edge demands over VNF chains unique yet complex. We also mentioned how additional properties being discussed for NFV systems can be integrated in the proposed formulation. In order to master the time complexity of the resolution algorithm, while considering two different optimization goals -traffic engineering (TE) goal alone and TE goal combined with NFV infrastructure cost minimization goal (TE-NFV) -we designed and evaluated a math-heuristic resolution method. Additionally, we compared our VNF-PR approach to the classical VNE approach often proposed in the literature for NFV orchestration.

We ran extensive tests to evaluate our algorithm on a three-tier topology representing an ISP topology. The results showed that the combined TE-NFV objective significantly reduced the number of VNFs in the network compared to the TE objective with almost no impact on the link utilization and on the latency. Moreover we observed that, in addition of different optimization objectives (TE and TE-NFV), the different distributions of traffic demand (Internet and VPN case-studies) and the different VNF types (in terms of function on the bit-rate) could lead to different placements of VNF nodes and different VNF chaining paths.

We also quantitatively compared our VNF-PR model to legacy VNE model. The experimental results showed that our VNF-PR algorithm was more stable and close-to-optimum than the VNE solution. The study also showed that the penalty for SLO violation was zero in almost all the tests performed with the VNF-PR approach, even if it is not directly taken into account in the constraints to match the VNE model hypotheses, while the SLO violation penalty always existed for all the tests with the VNE approach; this proved that our VNF-PR algorithm better defines the end-to-end service provisioning (point-to-point source-destination flow routing) problem. Furthermore, the averaged forwarding cost of all the tests solved with the VNE algorithm was at least 2 or 3 times more expensive than that of the VNF-PR algorithm, which indicated that, compared to the VNE solution, there were significantly less redundant traffic forwarding paths when chaining VNFs with the VNF-PR approach.

Our future work is to propose new solution algorithms to solve the NFV orchestration problem even more efficiently, taking into account the facility location structure of the problem, which seems to be the most challenging part in the model. Moreover, we envision to adapt our VNF-PR model to be able to meet more specific requirements such as VNF isolation, dynamic VNF orchestration, and the required extension to be run in a batch mode (on a per-demand basis or per groups of demands). As a further work we also plan to study the integration of availability targets in the placement and routing problem, i.e., to integrate an estimation of the robustness against network and system failure in the decision-making related to VNF chaining and placement.

Fig. 1 .

 1 Fig. 1. Traditional Customer Premises Equipment (CPE) compared to virtualized CPE (vCPE) with VNF chaining.

Fig. 2 .

 2 Fig. 2. Example of VNF forwarding latency profiles.

Fig. 4 .

 4 Fig. 4. Adopted network topology and VNF-PR solution example.

Fig. 5 .

 5 Fig. 5. Dependency between the number of VNF types and the problem size.

Fig. 6 .Fig. 7 .

 67 Fig.6. VNF node distribution across NFVI levels (standard case).

Fig. 8 .

 8 Fig.8. Empirical CDFs of latency components (standard case).

Fig. 9 .Fig. 10 .

 910 Fig. 9. VNF node distribution across NFVI levels (fastpath case).

Fig. 11 .

 11 Fig. 11. Empirical CDFs of latency components (fastpath case).

Fig. 12 .

 12 Fig. 12. Comparison between VNF-PR and VNE based algorithms in terms of objective function.

TABLE II VARIABLE

 II NOTATIONS FOR BASE MODEL.

TABLE III NOTATIONS

 III TO MODEL FORWARDING LATENCY.

		Parameters
	L	maximum allowed latency for a demand
	λ ij	latency introduced by link (i, j) ∈ A
		standard latency model
	g f j (b)	j-th component of the linearized latency function
		for VNF f and aggregated bandwidth b
	ng	number of piece-wise components of lin. latency function
		fastpath latency model
	lf	latency introduced by VNF f
	B f max	maximum allowed bandwidth to traverse VNF f
		Variables
	l f ik ≥ 0

latency that demand k ∈ D incurs using VNF f on node i of type f ∈ F hosted by node i ∈ Nv

TABLE IV NOTATIONS

 IV TO MODEL BIT-RATE VARIATIONS.

		Sets
	Na	access nodes
	N a	duplication of access nodes, where demands are located
		Parameters
	µ f	compression/decompression factor for VNF

TABLE V APPLICABLE

 V CONSTRAINTS TO VNF-PR PROBLEM VARIATIONS.

			Constraints
	Features	routing/location	latency profile	bit-rate
	basic	(3), (

  TableVII, the demands are randomly generated with uniform distribution of the required bandwidth volume in a given interval [a, b], in such a way that edge demands cannot create any bottleneck at the edge links, i.e., a = 0.1 and b = 0.14 in the Internet case-study, a = 0.13 and b = 0.17 in the VPN case-study. These values allow us to keep the total traffic volume at the same level for the two case-studies. In order to have more significant results than one single demand instance, we generate 10 random demand instances for each case-study.

TABLE VIII AVERAGED

 VIII , MINIMUM AND MAXIMUM VALUES OF THE TE OBJECTIVE FOR INTERNET AND VPN CASE-STUDIES.

	Standard	Internet L = 15ms L = 20ms	VPN L = 15ms L = 20ms
	Average	0.45	0.45	0.61	0.59
	Maximum	0.49	0.49	0.63	0.61
	Minimum	0.41	0.41	0.59	0.58
	Fastpath	Internet L = 15ms L = 20ms	VPN L = 15ms L = 20ms
	Average	0.44	0.45	0.60	0.59
	Maximum	0.49	0.49	0.62	0.62
	Minimum	0.41	0.41	0.58	0.57

TABLE IX AVERAGED

 IX RESULTS OF NFVI COST OF THE TE OBJECTIVE AND THE TE-NFV OBJECTIVE UNDER INTERNET AND VPN CASE-STUDIES, WITH THE REDUCTION RATIO OF COST FROM TE TO TE-NFV (STANDARD CASE).

	Standard	TE	Internet TE-NFV Reduction (%)	TE	VPN TE-NFV	Reduction (%)
	L = 15ms	66.4	48.2	26.86	46.1	31	31.08
	L = 20ms	59.9	52	13.05	43.2	20.9	58.66

in Table

V

, different model stages require different sets of variables and constraints

TABLE X NFV

 X COST FOR DIFFERENT TE GOAL RELAXATION LEVELS, WITH TE-NFV OPTIMIZATION.

	Instance	α = 0	α = 0.2	α = 0.4
			L=15ms
	Standard Internet	48.2	25.8	24.9
	Fastpath Internet	37.125	31	31
	Standard VPN	31	28.8	28.6
	Fastpath VPN	39.1	37.7	37.7
			L=20ms
	Standard Internet	52	23.7	23.1
	Fastpath Internet	38.7	34.8	31.2
	Standard VPN	20.9	20.4	20
	Fastpath VPN	34.9	34.8	33.8

TABLE XI AVERAGED

 XI RESULTS OF NFVI COST OF THE TE OBJECTIVE AND THE TE-NFV OBJECTIVE UNDER INTERNET AND VPN CASE-STUDIES, WITH THE REDUCTION RATIO OF COST FROM TE TO TE-NFV (FASTPATH CASE).

	Fastpath	TE	Internet TE-NFV Reduction (%)	TE	VPN TE-NFV	Reduction (%)
	L = 15ms	60.0	39.8	33.56	50.5	40	18.97
	L = 20ms	59.9	38.7	37.83	47.5	35.9	21.50

TABLE XII AVERAGED

 XII , MAXIMUM AND MINIMUM LATENCY COMPONENTS OF BOTH THE STANDARD AND THE FASTPATH CASES (F REPRESENTS 'FIREWALL', D IS 'DPI' AND T IS 'TUNNELING INGRESS').

					Internet study-case under TE objective with L=15ms
				Standard					FastPath
		VNF F	VNF D	VNF T	ALL VNFs	Path	Total	VNF F	VNF D	VNF T	All VNFs	Path	Total
	avg	0.82	0.38	0.57	1.76	6.27	8.03	1.00	1.00	1.00	3.00	6.25	9.25
	min	0.65	0.24	0.36	1.27	4.00	5.27	1.00	1.00	1.00	3.00	4.00	7.00
	max	1.15	0.50	0.70	2.15	9.60	11.40	1.00	1.00	1.00	3.00	9.67	12.67
					Internet study-case under TE objective with L=20ms
				Standard					FastPath
		VNF F	VNF D	VNF T	ALL VNFs	Path	Total	VNF F	VNF D	VNF T	All VNFs	Path	Total
	avg	1.21	0.44	0.92	2.56	6.68	9.24	1.00	1.00	1.00	3.00	6.37	9.37
	min	0.66	0.29	0.59	2.17	4.00	6.34	1.00	1.00	1.00	3.00	4.00	7.00
	max	1.79	0.59	1.29	2.98	10.80	13.16	1.00	1.00	1.00	3.00	10.50	13.50
					Internet study-case under TE-NFV objective with L=15ms
				Standard					FastPath
		VNF F	VNF D	VNF T	ALL VNFs	Path	Total	VNF F	VNF D	VNF T	All VNFs	Path	Total
	avg	1.07	1.09	0.84	3.01	6.27	9.28	1.00	1.00	1.00	3.00	6.34	9.34
	min	0.70	0.79	0.64	2.53	4.00	6.62	1.00	1.00	1.00	3.00	4.00	7.00
	max	1.55	1.38	1.11	3.46	9.60	12.62	1.00	1.00	1.00	3.00	9.67	12.67
					Internet study-case under TE-NFV objective with L=20ms
				Standard					FastPath
		VNF F	VNF D	VNF T	ALL VNFs	Path	Total	VNF F	VNF D	VNF T	All VNFs	Path	Total
	avg	1.26	1.11	1.01	3.38	6.68	10.06	1.00	1.00	1.00	3.00	6.37	9.37
	min	0.60	0.86	0.57	2.99	4.00	7.04	1.00	1.00	1.00	3.00	4.00	7.00
	max	1.87	1.39	1.50	3.75	10.80	14.05	1.00	1.00	1.00	3.00	10.50	13.50
					VPN study-case under TE objective with L=15ms
				Standard					FastPath
		VNF F	VNF D	VNF T	ALL VNFs	Path	Total	VNF F	VNF D	VNF T	All VNFs	Path	Total
	avg	0.86	0.64	0.61	2.12	8.07	10.18	1.00	1.00	1.00	3.00	7.48	10.48
	min	0.56	0.32	0.22	1.45	2.00	4.12	1.00	1.00	1.00	3.00	2.00	5.00
	max	1.18	0.93	1.00	2.71	11.67	13.39	1.00	1.00	1.00	3.00	9.40	12.40
					VPN study-case under TE objective with L=20ms
				Standard					FastPath
		VNF F	VNF D	VNF T	ALL VNFs	Path	Total	VNF F	VNF D	VNF T	All VNFs	Path	Total
	avg	0.90	0.68	0.61	2.19	9.58	11.77	1.00	1.00	1.00	3.00	9.95	12.95
	min	0.57	0.43	0.33	1.67	2.00	4.10	1.00	1.00	1.00	3.00	2.00	5.00
	max	1.15	0.99	0.85	2.86	14.17	16.53	1.00	1.00	1.00	3.00	13.50	16.50
					VPN study-case under TE-NFV objective with L=15ms
				Standard					FastPath
		VNF F	VNF D	VNF T	ALL VNFs	Path	Total	VNF F	VNF D	VNF T	All VNFs	Path	Total
	avg	1.16	1.21	1.11	3.48	8.07	11.55	1.00	1.00	1.00	3.00	7.48	10.48
	min	0.74	0.80	0.80	2.55	2.00	5.09	1.00	1.00	1.00	3.00	2.00	5.00
	max	1.58	1.74	1.63	4.59	11.67	14.26	1.00	1.00	1.00	3.00	9.40	12.40
					VPN study-case under TE-NFV objective with L=20ms
				Standard					FastPath
		VNF F	VNF D	VNF T	ALL VNFs	Path	Total	VNF F	VNF D	VNF T	All VNFs	Path	Total
	avg	1.59	1.84	1.62	5.06	9.58	14.63	1.00	1.00	1.00	3.00	9.95	12.95
	min	1.30	1.01	1.06	4.29	2.00	6.76	1.00	1.00	1.00	3.00	2.00	5.00
	max	2.24	2.41	2.17	5.68	14.17	18.76	1.00	1.00	1.00	3.00	13.50	16.50

Of course, this worst case can be improved considering the order of VNFs, when it is known in advance.

This can be due to a poor continuous relaxation, problem quite common when binary variables are present.

The source code is at https://github.com/srcvirus/middlebox-placement.

ACKNOWLEDGMENT

This work was partially supported by the ANR Reflexion project (http://anr-reflexion.telecom-paristech.fr, contract nb: ANR-14-CE28-0019), and the French Investissement dAvenir PSPC (Projet Structurant pour la Competitivit) FED4PMR project. Meihui Gao Ph.D. is supported by a grant of the French Ministry of Advanced Education and Research.