Alberto Ceselli

Marco Premoli

Stefano Secci
email: stefano.secci@upmc.fr.

Mobile Edge Cloud Network Design Optimization

Keywords:

Major interest is currently given to the integration of clusters of virtualization servers, also referred to as 'cloudlets' or 'edge clouds', into the access network to allow higher performance and reliability in the access to mobile edge computing services. We tackle the edge cloud network design problem for mobile access networks. The model is such that virtual machines are associated with mobile users and are allocated to cloudlets. Designing an edge cloud network implies first determining where to install cloudlet facilities among the available sites, then assigning sets of access points such as base-stations to cloudlets, while supporting virtual machine orchestration and taking into account partial user mobility information, as well as the satisfaction of service-level agreements. We present linkpath formulations supported by heuristics to compute solutions in reasonable time. We qualify the advantage in considering mobility for both users and virtual machines as up to 20% less users not satisfied in their SLA with little increase of opened facilities. We compare two VM mobility modes, bulk and live migration, as a function of mobile cloud service requirements, determining that a high preference should be given to live migration, while bulk migrations seems to be a feasible alternative on delay-stringent tiny-disk services such as augmented reality support, and only with further relaxation on network constraints.

I. INTRODUCTION

M OBILE devices are ubiquitous in people's everyday life, with a remarkable growth of mobile data traffic over recent years [START_REF]CVN Index: Global Mobile Data Traffic Forecast Update[END_REF]. As mobile applications become increasingly resource-hungry, the gap between required resources and those available in mobile devices widens. To bridge this gap, cloud computing can be used to expand mobile devices resources. To deal with high latency of distant cloud center, the concept of cloudlet was introduced in [START_REF] Satyanarayanan | The case for vm-based cloudlets in mobile computing[END_REF] where it is defined as a trusted, resource-rich computer or cluster of computers well-connected to the Internet and available for use by nearby mobile devices. A cloudlet represents a container for virtual machines (VMs): connected users are associated with VMs supporting low-latency application offloading use-cases.

Cloudlet concept is expected to be supported by 3-tier hierarchical network provisioning as presented in [START_REF] Jararweh | Resource efficient mobile computing using cloudlet infrastructure[END_REF] and [START_REF]Elijah[END_REF]. In this hierarchy the cloudlet is the primal resource for the augmentation of the mobile device capabilities, while a remote cloud is used as last available resource, or for delay-tolerant resource-intensive applications. Telecommunication vendors and providers show an increasing interest in such deployments, also referred to as 'mobile edge computing' (MEC) solutions in industrial fora and standardization bodies (e.g. [START_REF] Patel | Mobile-edge computing introductory technical white paper[END_REF], [START_REF]Mobile Edge Computing (MEC); Technical Requirements[END_REF]).

Within this framework, in this paper we focus on the potential medium-term planning of an edge cloud network in mobile access networks, which is, to the best of our knowledge, an untreated problem in the literature. This consists in the placement of all virtualization infrastructure resources, from the access points to the cloudlets, together with the assignment of users to cloudlets. We investigate two design cases: (i) with a network in a static state and (ii) with the network state variations in terms of load and service level, caused by user mobility. In this latter case we include orchestration of virtual resources, in particular VM orchestration across cloudlets, in order to re-balance the system. Our contribution is as follows:

• We provide a link-path mixed integer linear programming formulation including a polynomial number of variables to represent location and design decisions, and an exponential number of them to encode routing ones. • Since adaptations of heuristics from the literature are unable to produce accurate results, we exploit mathematical programming techniques, combining column generation [START_REF] Desaulniers | Column generation[END_REF], iterative rounding, local search, very large scale neighborhood and problem reduction to achieve high quality solutions in reasonable time. • We bring novel and original insights on the planning of cloudlets for mobile access networks. By performing extensive simulations on real 4G cellular network datasets from the Île-de-France Orange network, we show the trade-off that can be achieved by means of the two design cases and the impact of user mobility on the cloudlet network: as few as 13 to 26 cloudlets can be planned for 180 thousands of users while requiring tight delay guarantees. We show that there is a sensible gain in the number of users with respected SLA, up to 20%, by including user and VM mobility in the network planning. We do also qualify the eligibility of two different VM mobility strategies, namely VM bulk and live migrations, for two reference mobile cloud services differing in the level of required latency and memory characteristics: augmented-reality and remote desktop. • We report empirical distributions of the dataset features in order to allow the reproducibility of our results.

In [START_REF] Ceselli | Cloudlet network design optimization[END_REF] we provide a preliminary modeling of the mobile edge cloud network design problem. In this paper we refine the model and we provide a new heuristic including a dynamic decomposition logic. Furthermore, we present a more detailed set of results, carrying out a substantially deeper analysis of policies and practices. The paper is organized as follows. Sect. II presents the background. Sect. III presents cloudlet network models and related mathematical formulations. Sect. V presents the dataset. Sect. VI reports experimental results and Sect. VII contains brief conclusions.

II. BACKGROUND

Benefits of cloudlet usage on users' QoE are presented in [START_REF] Clinch | How close is close enough? understanding the role of cloudlets in supporting display appropriation by mobile users[END_REF]- [START_REF] Fesehaye | Impact of cloudlets on interactive mobile cloud applications[END_REF] where authors compare performances of different types of applications on different layers of the 3-tier hierarchy. In [START_REF] Clinch | How close is close enough? understanding the role of cloudlets in supporting display appropriation by mobile users[END_REF] authors show that application placement can significantly impact performance and user experience moving applications closer to the users. Authors of [START_REF] Ha | The impact of mobile multimedia applications on data center consolidation[END_REF] question, by quantitative experimental results, benefits from consolidating computing resources in large data centers when strict latency constraints are required. Considering multi-hop WiFi networks, in [START_REF] Fesehaye | Impact of cloudlets on interactive mobile cloud applications[END_REF] authors show that the cloudlet-based approach always outperforms the cloud-based one when no more than two wireless hops are used to transfer data, and that up to a maximum of four hops the cloudlet-based approach is the best one for most of the instances. There is no binding dependence on the nature of the wireless link: even if the seminal idea was to use cloudlet via WiFi, the virtualization architecture is independent of it. A further survey on researches on cloudlet based mobile computing is available in [START_REF] Pang | A survey of cloudlet based mobile computing[END_REF].

Hardware technologies for the implementation of cloudlets already exist, thanks to fabrics called 'micro data centers' or 'modular data center' [START_REF] Hamilton | Architecture for modular data centers[END_REF]- [START_REF]Myoonet[END_REF]. A standardization effort is sustained by the European Telecommunications Standardization Institute (ETSI) that in [START_REF] Patel | Mobile-edge computing introductory technical white paper[END_REF], [START_REF]Mobile Edge Computing (MEC); Technical Requirements[END_REF] provides technical requirements for a deployment of a mobile edge cloud network, together with use-cases examples such as augmented reality, Internet-of-Things (IoT) and data caching among others. In this work we primarily address application VMs rather than virtual network functions.

A. VM mobility technologies

In Section III.D we deal with the dynamic state of the network, whose variations generate imbalances and users' SLA violations. To re-balance the system, we include VM mobility from cloudlet to cloudlet in the model, considering three VM mobility technologies at the state of the art:

• VM bulk migration [START_REF] Bradford | Live wide-area migration of virtual machines including local persistent state[END_REF]: consists in migrating the whole VM stack including disk and memory, stopping the VM for a long period to transfer it. • VM live migration [START_REF] Raad | Achieving sub-second downtimes in large-scale virtual machine migrations with lisp[END_REF]- [START_REF] Herrmann | KVM live migration[END_REF]: stops the VM only for a small amount of time required to transfer the most re-cently used memory, not requiring an entire one-shot disk transfer, but a permanent disk storage synchronization among source and destination locations. • VM replication [START_REF] Cully | Remus: High availability via asynchronous virtual machine replication[END_REF]: consists in a permanent synchronization of both disk storage and memory among source and destination locations, not requiring the point transfer neither of the disk nor of the most recently used memory. We assume VM orchestrations to be performed in a Cloud Stack platform in a centralized way. Given that the main purpose of our model is the medium-term planning of the mobile edge cloud network, the inclusion of VM orchestration has the aim of providing a correct dimensioning of the network. Hence an actual implementation of such a system is out of scope of this work, but examples are already present (e.g. in OpenStack platform [START_REF] Tacker | [END_REF], [START_REF]Nova[END_REF]).

B. Mobile Edge Cloud Network Topology

Accordingly to the ETSI [START_REF] Patel | Mobile-edge computing introductory technical white paper[END_REF], [START_REF]Mobile Edge Computing (MEC); Technical Requirements[END_REF], the distribution of computing resources into mobile access network should be carefully designed to take into account infrastructure properties. Mobile access networks could be any form of wireless access network disposing of a backhauling wireline infrastructure through which cloudlets can be interconnected. Following the guidelines in [START_REF] Howard | Using carrier ethernet to backhaul lte[END_REF]- [START_REF]Architectural considerations for backhaul of 2g/3g and long term evolution networks[END_REF], a broadband access and back-hauling network, such as a cellular network, can be modeled as a two-level hierarchical network: access points on the field are connected to aggregation nodes, which are then connected to core nodes, as depicted in Fig. 1 (for simplicity, we refer in the following to access points as APs). The APs could be WiFi only, cellular only, or a mix of these common mobile access technologies. Cloudlets can reasonably be placed at either field, aggregation or core level, with connections between an AP and its cloudlet potentially crossing twice each level.

Various physical interconnection network topologies between APs, aggregation nodes and core nodes are commonly adopted: tree, ring or mesh topologies, as well as intermediate hybrid topologies. Moreover, with the emergence of 4G, there is a trend to further mesh back-hauling nodes. A variety of network protocol architectures are typically adopted, from circuitswitched networks to carrier-grade packet-switched networks. The common denominator of such architectures is the ability to create a virtual topology of links directly interconnecting pairs of nodes at a same level with a guaranteed tunnel capacity. Nowadays, with the convergence towards packetswitching carrier-grade solutions at the expense of legacy circuit-switched approaches, bit-rates for pseudo-cables links is set to giga-Ethernet granularities (typically 1 or 10 Gbps).

In this framework, we believe it is appropriate to model the mobile edge cloud network as a superposition of stars of virtual links for the interconnection of aggregation nodes to APs and for the interconnection of core nodes to aggregation nodes, even if nodes can have no physical direct connection. Under the same virtual link provisioning trend, core nodes can be considered as interconnected to each other by a full mesh topology of virtual links, as depicted in Fig. 1. As far as we know, partitioning of traffic from one AP to multiple aggregation nodes, and from one aggregation node to multiple core nodes is not the dominating current practice in backhauling networks; still, such features would not change significantly the nature of our modeling and heuristic described in the next two sections. It is worth noting that the decisions of associating APs to aggregation nodes and placing aggregation nodes can be fully compatible with the current trend of dynamically reprogramming the cellular backhauling network [START_REF] Jin | Softcell: Scalable and flexible cellular core network architecture[END_REF]. Likewise, another customization could correspond to the routing re-optimization for a given cloudlet placement. Moreover, those decisions can also realistically embed association and placement functions in cloud-based Evolved Packet Core architectures [START_REF] Taleb | Ease: Epc as a service to ease mobile core network deployment over cloud[END_REF].

III. MOBILE EDGE CLOUD NETWORK MODEL

In the following, we give a formal definition of the cloudlet design dimensioning problem, and we propose two variants:

A. Problem statement

Our models finds simultaneously: (i) an optimal network design, including cloudlet placement and assignment of APs to cloudlets, and (ii) an optimal routing of the traffic from and to the cloudlets. Its main aim is to provide strategic insights into optimal design policies rather than an operational planning.

From a practical perspective, placing a cloudlet at a location could mean turning on already installed servers, and not only physically installing new machines. Similarly, changing AP to cloudlet assignments would in practice correspond to a re-routing of virtual links over the transport network infrastructure, and not physically changing the interconnection. We consider a solution to be feasible if users' service level agreement is respected; optimal feasible solutions minimize a linear combination of overall installation costs.

Our problem turns out to be hard from both a theoretical and computational point of view. Theoretically, it is strongly NP-Hard, generalizing the traditional uncapacitated facility location problem and its capacitated and single-source variants. Computationally, it is on the cutting edge of those currently under investigation in the facility location literature [START_REF] Addis | Combining very large scale and ilp based neighborhoods for a two-level location problem[END_REF]: stateof-the-art methods are successful when up to two facility levels are considered, but in our models routing optimization, latency bounds and a third location level must be included.

In the following, we introduce the basic models dealing with network design (in III.B); then we add routing aspects (in III.C), thereby completing them for the SP variant. Finally, we discuss how this modeling extends to the DP variant 1 . 1 Complete notation tables for our models and heuristic are included in Appendix Tables A.I, A.II and A.III in Supplementary Materials.

B. Network design

Input (problem data). We assume that a set of suitable locations has been identified for hosting network facilities. Formally, let B be the set of AP locations. Let I, J and K be the set of sites where aggregation, core nodes and cloudlet can be installed, resp.. Let also E ⊆ (B × I) ∪ (I × J) ∪ (J × J) be the set of feasible links between nodes. Let l i , m j , c k be the fixed cost for activating an aggregation node in i ∈ I, a core node in j ∈ J and a cloudlet facility in k ∈ K, resp.. Output (decision variables). We introduce two sets of variables. The first set corresponds to location binary variables: x i take value 1 if an aggregation node is set in i ∈ I; y j take value 1 if a core node is set in j ∈ J; z k take value 1 if a cloudlet is set in k ∈ K. The second set corresponds to network topology binary variables: t s,i take value 1 if an AP link is established between an AP s and an aggregation node i; w i,j and w j,i simultaneously take value 1 if an aggregation link is established between an aggregation node i and a core node j; o m,n take value 1 if a core link is established between two core nodes m and n. In order to model already existing or forbidden links, the corresponding variables can be fixed to value 1 and 0, resp.. Objective function Since our main purpose is the MEC network design, the model goal ( 1) is to minimize installation costs of all network facilities. We do not include the links installation costs as we do not take into consideration the cellular infrastructure dimensioning.

min i∈I lixi + j∈J mjyj + k∈K c k z k (1)
Constraints. A complete MEC network topology results as a by-product of our model, in terms of arrangement of links.

As specified in Section II.B we model this network as a superposition of stars: this has to be intended as a topological rule, which constrains the resulting arrangement of links. Each AP is connected to a single aggregation node, and each aggregation node to a single core node (as depicted in Fig. 1), while a full mesh is built among cores. The following set of constraints enforce our topological rules to be respected: each link (i, j) can be used only for one purpose (i.e. AP, aggregation or core) -(2); aggregation links must be symmetric -(3); core nodes and cloudlet nodes are also aggregation nodes -( 4) and (5); if (i, j) is an AP link then j is an aggregation node -(9), while if (i, j) is an aggregation link, then i is an aggregation node - [START_REF] Ha | The impact of mobile multimedia applications on data center consolidation[END_REF]; if (i, j) is an aggregation link, then either i or j is a core node -(11) -and similarly if (i, j) is a core link, both i and j are core nodes - [START_REF] Pang | A survey of cloudlet based mobile computing[END_REF], conversely if both i and j are core nodes, (i, j) is a core link - [START_REF] Hamilton | Architecture for modular data centers[END_REF], moreover no loops are considered at core links - [START_REF] Desaulniers | Column generation[END_REF]; each AP is connected to either itself when chosen as aggregation, or a different node otherwise -( 6) and ( 14); each aggregation node has an adjacent aggregation link, thereby connecting to a core node - [START_REF]Myoonet[END_REF], which can be the node itself - [START_REF]Mobile Edge Computing (MEC); Technical Requirements[END_REF], at most one aggregation link can be connected to non-core nodes (y i = 0), while an arbitrary number can be connected to core ones (y i = 1) -( 16).

ti,j + wi,j + oi,j ≤ 1

∀(i, j) ∈ E | i = j (2) wi,j = wj,i ∀(i, j) ∈ E (3) xi ≥ yi ∀i ∈ N (4) xi ≥ zi ∀i ∈ N (5) ti,i = xi ∀i ∈ N (6) wj,j = yj ∀j ∈ N (7) oi,i = 0 ∀i ∈ N (8) ti,j ≤ xj ∀(i, j) ∈ E (9) wi,j ≤ xi ∀(i, j) ∈ E (10) wi,j ≤ yi + yj ∀(i, j) ∈ E | i = j (11) 2 • oi,j ≤ yi + yj ∀(i, j) ∈ E | i = j (12) yi + yj -1 ≤ oi,j ∀(i, j) ∈ E | i = j (13) i∈N | j =i∧(i,j)∈E ti,j = 1 -xj ∀i ∈ N (14) j∈N :(i,j)∈E wi,j ≥ xi ∀i ∈ N (15) j∈N | (i,j)∈E∧i =j wi,j ≤ (1 -yi) + |I| • yi ∀i ∈ N (16)

C. Static Planning

Input (problem data). Each AP s ∈ B can connect to a cloudlet located in k ∈ K by a set of paths Ssk (see paths a, b, c and d in Fig. 1). Path p ∈ Ssk can traverse multiple sites and with j ∈ p we denote that site j is traversed by path p. For each AP s ∈ B, let δ u s and δ b s be the number of users connected to s and their overall bandwidth consumption. We assume that servicing each user requires the activation of one VM, and therefore δ u s represents also the number of VMs needed for AP s. It is worth noting that considering multiple VMs per user (i.e., a generic Infrastructure as a Service) is straightforward and can be easily defined; conversely, sharing a VM by multiple users is not straightforward (and may not be the most common edge computing service deployment); these adaptations are out of scope and left to future work.

Let C be the number of VMs that each cloudlet can host. Let d i,j and u i,j be the latency (latency or length are used interchangeably hereafter) and bandwidth capacity of each link (i, j) ∈ E. Let U ∈ [0, 1] be the parameter representing the maximum link utilization (percentage) in the network; indeed, as a common practice in IP traffic engineering with non deterministic loads, links need to have a level of overprovisioning so that they are robust against traffic fluctuations (due to failures, traffic peaks, etc) and hence the risk of congestion, which is particularly important for real-time and interactive services as those considered by MEC [START_REF] Patel | Mobile-edge computing introductory technical white paper[END_REF], [START_REF]Mobile Edge Computing (MEC); Technical Requirements[END_REF].

Finally, we consider static and identical SLAs for all users, defined as the maximum allowed latency a user may experience, assuming it to be represented by three types of constraints: (i) maximum sum of link length in a path D; (ii) maximum number of hops in a path H that according to [START_REF] Fesehaye | Impact of cloudlets on interactive mobile cloud applications[END_REF] affects the effectiveness of cloudlets; (iii) maximum distance allowed between nodes in the network to establish a link d. In Section VI we provide a parametric analysis on these bounds, showing their influence on network planning decisions. 2Output (decision variables). To model routing decision we introduce an additional set of binary variables: r s,k p take value 1 if users in AP s ∈ B are served by cloudlet in k ∈ K, and the corresponding traffic is routed along path p ∈ Ssk . Constraints. Feasible paths are those that satisfy SLA latency requirements defined previously. In order to enforce that only feasible paths are considered, we replace each set Ssk with the following set:

S sk = {p ∈ Ssk : (i,j)∈p d (i,j) ≤ D ∧ |p| ≤ H ∧ d (i,j) ≤ d ∀(i, j) ∈ p} (17)
where by |p| we denote the number of links forming path p. Constraints ( 18)-( 20) impose that each path from AP s ∈ B to cloudlet k ∈ K, traversing either an aggregation node i ∈ I or a core node j ∈ J, can be selected only if that network facility is installed in the corresponding site.

p∈S sk |i∈p r s,k p ≤ xi ∀s ∈ B, ∀k ∈ K, ∀i ∈ I ( 18
)
p∈S sk |j∈p r s,k p ≤ yj ∀s ∈ B, ∀k ∈ K, ∀j ∈ J ( 19
)
p∈S sk r s,k p ≤ z k ∀s ∈ B, ∀k ∈ K (20)
Constraint ( 21) sets to 1 the number of cloudlets used by a single AP, as AP-level load-splitting is typically not performed in backhauling networks. ( 22) enrich ( 20) by further imposing that active cloudlets provide at most C VMs. Constraints [START_REF] Howard | Using carrier ethernet to backhaul lte[END_REF] ensure that capacity of link (i, j) is not exceeded.

k∈K p∈S s,k r s,k p = 1 ∀s ∈ B ( 21
)
s∈B p∈S s,k δ u s r s,k p ≤ Cz k ∀k ∈ K (22) s∈B k∈K p∈S s,k |(i,j)∈p δ b s r s,k p ≤ u (i,j) U (wi,j + oi,j + ti,j) ∀(i, j) ∈ E (23)
Overall, ( 1) -( 23) represent our mobile edge cloud network model with static planning.

D. Dynamic Planning aware of temporal user & VM mobility

In the second variant of our model, we consider the dynamic status of the network. As users move during the planning horizon, they connect to different APs, changing the network load distribution, with the necessity to re-plan the network to re-balance the system. Moreover as they move they may distance themselves from their VM, worsening their QoEs and violating their SLA. In order to re-balance the system and to enforce SLA we introduce VMs mobility in our model.

We partition the planning horizon in periods called timeframes, identified by set T . To consider the changing in the network load distribution, let δ u,t s and δ b,t s be the (average) number of users connected to AP s ∈ B and their overall bandwidth consumption during time-frame t ∈ T . We consider the user mobility during the overall given horizon without making assumptions on the users positions in a specific point in time, yet we assume that in a single time-frame a user can connect to a single AP; in particular, let f s s be the number of users moving from AP s ∈ B to AP s ∈ B during time horizon T . We allow routing decisions to be changed dynamically, i.e. we allow an AP s ∈ B to be assigned to different cloudlets k ∈ K in different time-frames t ∈ T , replacing the variable r s,k p with a set of variables r s,k,t p for each t ∈ T . Constraints ( 18)-( 23) of SP model are extended as the following DP variant:

p∈S sk |i∈p r s,k,t p ≤ xi ∀s∈B,∀k∈K ∀i∈I,∀t∈T (24)
p∈S sk |j∈p r s,k,t p ≤ yj ∀s∈B,∀k∈K ∀j∈J,∀t∈T (25)
p∈S sk r s,k,t p ≤ z k ∀s∈B,∀k∈K ∀t∈T (26) k∈K p∈S s,k r s,k,t p = 1 ∀s∈B ∀t∈T (27)
s∈B p∈S s,k δ u,t s r s,k,t p ≤ Cy k ∀k∈K ∀t∈T (28)
s∈B k∈K p∈S s,k |(i,j)∈p δ b,t s r s,k,t p ≤ u (i,j) U (wi,j + oi,j + ti,j)

∀(i, j) ∈ E, ∀t ∈ T (29)
These are composed by single copies of location variables and |T | copies of each path variable and constraints ( 18)-( 23) of SP model. However, the former are not independent one another, being linked by constraints ( 24), ( 25) and [START_REF]Architectural considerations for backhaul of 2g/3g and long term evolution networks[END_REF].

To include in DP model the user mobility, let variables g k k s s ∈ Z + represent the amount of users connecting through the planning horizon to APs s ∈ B and s ∈ B served by cloudlets in sites k ∈ K and k ∈ K, resp.. Let also binary variables v sk take value 1 if AP s ∈ B is assigned to a cloudlet in k ∈ K in at least one time-frame. Following constraints are needed to enforce coherence among these additional variables:

p∈S sk r s,k,t p ≤ v sk ∀s∈B,∀k∈K ∀t∈T (30)
g k k s s ≥ (v s k + v s k -1)f s s ∀s ,s ∈B ∀k ,k ∈K (31)
In the following we define the set of constraints modeling the three VM mobility technologies presented in Section II.A. a) VM replication: We model the VM replication option including explicitly in our model the routing and congestion assessment arising from cloudlet to cloudlet synchronization traffic. Let Qk k be the set of paths connecting cloudlet facilities installed in k , k ∈ K, through which to route the synchronization traffic of copies of a VM deployed in the two cloudlets. We refer to these as synchronization paths. Let DQ and LQ be the counterpart of D and H for synchronization paths, and let:

Q k k = {p ∈ Qk k : (i,j)∈p d (i,j) ≤ DQ ∧ |p| ≤ HQ ∧ d (i,j) ≤ d ∀(i, j) ∈ p} (32)
represent the set of feasible synchronization paths between k and k . Then, let continuous variables q k k t p ∈ R + represent the amount of synchronization traffic between cloudlet facilities in k ∈ K and k ∈ K routed along path p ∈ Q k k during time-frame t ∈ T . A path p ∈ Q k k can traverse multiple sites and with j ∈ p we denote that site j is traversed by path p. The following constraints enforce coherence among these additional variables:

p∈Q k k q k k t p ≥ s ,s ∈B |s =s Φ(g k ,k s ,s ) ∀k ,k ∈K |k =k
, ∀t ∈ T (33)

p∈Q k k |i∈p q k k t p ≤ xi s ,s ∈B Φ(f s ,s ) ∀i∈I,∀k ,k ∈K ∀t∈T ( 34
)
p∈Q k k |j∈p q k k t p ≤ yj s ,s ∈B Φ(f s ,s ) ∀j∈J,∀k ,k ∈K ∀t∈T (35)
and link utilization constraints (29) become:

(s,k)∈ B×K p∈S s,k |(i,j)∈p r s,k,t p + k ,k ∈K |k =k p∈Q k k |(i,j)∈p q k ,k ,t p ≤ ≤ u (i,j) • U (wi,j + oi,j + ti,j) ∀(i, j) ∈ E, ∀t ∈ T (36)
Function Φ : Z + → R maps the number of moving users g k ,k s ,s to the amount of synchronization traffic they induce among cloudlets. The VM replication variant is therefore obtained by applying (1)-( 16), ( 24)-( 28), ( 30)-( 31), ( 33)- [START_REF] Csáji | Exploring the mobility of mobile phone users[END_REF].

b) Bulk and Live VM Migration: The dynamic association of users to a nearer cloudlet allows an improvement in their QoE, with a possible worsening of the status of the network. Hence the expected number of user migrations given by variables g k k s s has to be limited by the number of migrations that the network infrastructure can handle in an amount of time such that the migration ends before the user moves further, which we will refer to as useful migrations. Given the parameters:

• T w : the temporal window during which the migration of the VM is useful. This values is strictly related to the user's sojourn time in an area T s , and usually T w T s ; • V : the size of the VM file to migrate; the number of migrations that a link can manage is given by:

(1 -U ) • u i,j • T w V (37)
We therefore limit the number of VMs migrations that a single link can handle, with the following constraints:

(k ,k ) ∈K×K p∈Q k ,k | (i,j)∈p Φ -1 q k ,k ,t p ≤ (1 -U ) • u i,j • T w V ∀(i,j)∈E ∀t∈T (38) where Φ -1
is the inverse of function Φ found in [START_REF]Anr abcd project[END_REF], retrieving the number of migration routed through link (i, j). Bulk VM Migration model variant is therefore obtained by the set of equations ( 1)-( 16), ( 24)-( 31), ( 33)-( 35) and [START_REF] Isaacman | Identifying important places in peoples lives from cellular network data[END_REF], while Live VM Migration model variant is obtained by the set of equations ( 1)-( 16), ( 24)-( 28), ( 30)-( 31), ( 33)-( 36) and [START_REF] Isaacman | Identifying important places in peoples lives from cellular network data[END_REF].

IV. HEURISTIC ALGORITHM

As reported in the Introduction, we found adaptations of heuristics from the literature to be unable to produce accurate results; this was one of the main motivations to build our models. Still, our path-based formulations offer great modeling flexibility and present computational challenges at once. In particular, the number of feasible paths in sets S sk and Q k k grows very fast with the network size. In order to obtain good feasible solutions in limited computing time, we implemented two ILP-based heuristics, whose flowcharts are presented in Fig. 2 and3, respectively for SP and DP variants. Both heuristics share the following pre-processing steps (in Fig. 2-Block (a) and Fig. 3-Block (a)):

1) we fix the location of aggregation nodes, and the assignment of APs to them, creating clusters of APs of limited size and minimum worst-case latency through the following heuristic: (i) fix a number F of aggregation nodes to be installed; (ii) fix a maximum number G of APs connected to each aggregation node; (iii) run a PAM k-medoids heuristic [START_REF] Reynolds | Clustering rules: a comparison of partitioning and hierarchical clustering algorithms[END_REF] on the set of APs to choose F baricentric ones; (iv) use such a solution as initialization for a G-capacitated F -center alternating heuristic. This alternating heuristic, in turn, works as follows: (i) fix the locations of aggregation nodes, and solve an ILP for assigning the APs to aggregation nodes, forming clusters where at most G APs are connected, and minimizing the maximum distance between an AP and the center of its cluster; (ii) choose as new center for each cluster the AP minimizing the maximum distance between all other APs in the cluster; then iterate from (i), until no more changes in the solution are observed. 2) we fix the x i variables in our models according to the G-capacitated F -center solution obtained as above, we fix J = K = {i ∈ I : x i = 1}, and we remove from each S sk set all paths in which the AP s is not assigned to the aggregation device of its cluster. After preliminary experiments, we fixed F = 50, G = 1.3 • (|B|/F ). The subsequent steps differ for the SP and DP variants, hence we present them separately.

a) Static Planning Heuristic Algorithm: The number of feasible paths that can link APs and cloudlets can be significant and become intractable with the increase of the nodes in the network. As second step, in Figure 2 [START_REF] Desaulniers | Column generation[END_REF]. Each S sk is replaced by a restricted subset Ssk having tractable size. Then, iteratively, the continuous relaxation of the model described by ( 1)-( 23) is optimized, but including Ssk instead of S sk , and a search for potentially improving variables in Ssk \ S sk is carried out. Linear programming theory guarantees that potentially improving variables are those of negative "reduced cost": if no such a variable is found, then the solution is optimal also for the continuous relaxation of the initial model including the full sets S sk . If, instead, variables are found having negative reduced cost, these are added to the Ssk , and the process is iterated. In our case, the search for variables of minimum reduced cost can be formulated as a constrained shortest path problem of polynomial complexity, and solved with dynamic programming. Preliminary experiments proved this approach to be efficient in terms of both computing time and memory usage [START_REF] Ceselli | Heuristic for static cloudlet location[END_REF].

As the column generation process leads to a fractional solution s, to obtain an integer feasible one, a hierarchical rounding on the variables is executed (Fig. 2-Block (c)): (i) select the location variable f with higher fractional value in s that was not already fixed, and fix it to value one, (ii) propagate the rounding, by fixing to zero all variables that would lead to infeasibility when set to one, (iii) resume column generation, to dynamically generate new paths given the new fixed variables, (iv) if a new fractional solution is found, repeat rounding from step (i); instead, if no feasible solution can be found after fixing, reset f to value zero, undo rounding propagation and resume column generation; if a feasible solution is found, repeat rounding from step (i), otherwise stop rounding with FAIL. (v) Stop with SUCCESS whenever f has a fractional value in s that is lower than a small enough positive threshold .

Instead of choosing an arbitrary f , we perform rounding according to the following hierarchy: (i) cloudlet location variables z k , (ii) core nodes location variables y j , (iii) aggregation nodes location variables x i , (iv) paths variables r s,k p . That is, each hierarchical level is explored only if no previous one contains a fractional variable. Variables related to topological rules are never rounded explicitly. At the end of the rounding process, in case of SUCCESS, a MILP problem remains to fix them, involving a small number of variables, which can be easily optimized by general purpose ILP solvers. Nevertheless, we often observed network topology variables to take integer values directly after rounding: in these cases we skip this last MILP optimization process. In case of FAIL, instead, the solution produced in step (a) is considered. That is, in any case our static planning algorithm produces a feasible solution, unless the instance itself admits no feasible one.

Given an integer solution Ŝ, we try to improve it with an ILP-based very large scale neighborhood search strategy (Fig. 2-Block (d)), exploring a κ-OPT neighborhood [START_REF] Fischetti | Local branching[END_REF]:

(i) we consider only the paths created during the column generation process and the subsequent hierarchical rounding and pricing; (ii) we include the following local-branching constraint

k∈K|z k =1 (1 -z k ) + k∈K|z k =0 z k ≤ κ • k∈K zk (39)
where zk are the fixed values of corresponding variables z k in Ŝ, and κ is the fraction of z k variables whose values are allowed to flip w.r.t. the current solution;

(iii) we solve this restricted model with a general purpose ILP Solver, setting a limit τ on the execution time.

After preliminary experiments, we set = 10 -3 , κ = 30% and τ = 300 seconds.

b) Dynamic Planning Heuristic Algorithm: Optimizing the DP variant is even more involved. First, a copy of each association path r s,k,t p needs to be considered for each timeframe t. Second, the set of sync-paths variables q k ,k ,t p may grow combinatorially as well. Third, the number of variables g k ,k s ,s and constraints (31) -( 33) is polynomial, but too large to be explicitly considered in practice. Therefore we perform column generation also on the set of sync-paths variables, and we relax constraints (31) - [START_REF]Anr abcd project[END_REF] as follows:

q∈Q k ,k q k ,k t p ≥ s ∈B s ∈B Φ(f s ,s ) • (v s k + v s k -1) ∀k ,k ∈K |k =k ∀t∈T (40)
When integrality conditions are enforced, (40) are equivalent to (31) - [START_REF]Anr abcd project[END_REF]. Unfortunately, this is not always true when the continuous relaxations are considered during rounding; we therefore strengthened them with the following inequalities:

v s ,k + v s ,k ≤ 1 , ∀s ,s ∈B k ,k ∈K | f s ,s >0 ∃ p∈S s,k ∃ p∈S s ,k ∃ p∈Q k ,k , ∀t ∈ T (41) v s ,k - k ∈K | ∃p∈S s ,k ∃p∈Q k ,k v s ,k ≤ 0 , ∀s ,s ∈B ∀k ∈K | f s ,s >0 ∧ ∃p∈S s ,k (42)
t∈T p∈S s,k where [START_REF] Secci | Linking virtual machine mobility to user mobility[END_REF] forbid the simultaneous choice of AP-cloudlet associations that does not allow to establish a feasible synchronization path, (42) states that, for each pair of APs with expected users migration, at least a pair of AP-cloudlet associations having a feasible synchronization path has to be activated, and (43) ensure that AP-cloudlet association variable v s,k is activated only if a related path variable r s,k,t p is activated in any time-frame t.

The relaxed model including constraints (1)-( 16), ( 24)-( 28), ( 30), ( 34)-( 36) and ( 40)-( 43) is therefore used in the DP heuristic algorithm, whose structure is depicted in Fig. 3. Steps (b) and (c) of Fig. 3 are analogous to steps (b) and (c) of Fig. 2, but we perform the dynamic generation of both feasible associations paths r s,k,t p and synchronization paths q k ,k ,t p . In both cases we formulated the pricing problem as a constrained shortest path problem, and we designed ad-hoc dynamic programming algorithms to solve it. At the end of the column generation, a fractional solution is available, and we resort to the hierarchical rounding to obtain an integer one. The order of rounding is the same as that used for SP variant. In fact, new continuous variables q k ,k t p do not need to be rounded; the new binary variables v s,k are not rounded explicitly but are fixed by rounding propagation: when a z k variable is fixed to zero, related v s,k variables are fixed to zero as well; when an association path variable r s,k,t p is fixed to one, the related v s,k variable is fixed to one as well.

At the end of the rounding process, we check the compliance with the relaxed constraints on synchronization traffic [START_REF] Ceselli | Heuristic for static cloudlet location[END_REF] and [START_REF]Anr abcd project[END_REF]. Given the AP-cloudlet associations, defined by variables v s,k with value 1, the computation of the related amount of user migration and hence the amount of synchronization traffic to route is straight. If the synchronization paths created until this step are enough to route this amount of synchronization traffic, a feasible solution is found and the optimization process ends successfully. If not, further synchronization paths need to be created (Fig. 3-Block (e)): we fix cloudlets locations variables z k and AP-cloudlet association variables v s,k , and the related amount of synchronization traffic is replaced in the right hand sides of constraints [START_REF] Bahl | Mobile gaming[END_REF]. All other variables are unfixed and a new process of dynamic generation of path variables is executed (Fig. 3-Block (f)): differently from the previous step, we look only for APcloudlet association paths related to variables v s,k whose value was fixed to one. At the end of the iterative hierarchical rounding and column generation process (Fig. 3-Block (g)), if an integer solution is found, then it is also feasible for the original problem; if not, our algorithm stops in a FAIL status. No very large scale local search is performed.

V. DATASET

In order to ground our simulations on real data, we used a dataset collected by Orange mobile, France, in the frame of the ABCD project [START_REF]Anr abcd project[END_REF]. The dataset comes from network management tickets, containing UE data exchange information aggregated in 6 minutes periods. User session is assigned to the cell identifier of the last used antenna. Data are recorded on a per-user basis and cover a large metropolitan area network, including urban, peri-urban and rural areas. We had access to data of a single 24-hour period, originated by 606 LTE 4G APs in an area of 931 km 2 , with a density of ∼ 0.65 APs per km 2 . The number of users served by the considered APs is ∼ 180 thousands, generating an overall daily traffic of 11T B. for each base station s ∈ B are drawn by direct queries from the dataset. Following [START_REF] Greenberg | The cost of a cloud: research problems in data center networks[END_REF] and [START_REF] Beloglazov | Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing[END_REF] we fix costs l i = 0.01, m j = 0.1, and c k = 1, which can be seen as percentages. That is, we give maximum priority to the minimization of cloudlet costs, assuming to be the most relevant, and, as suggested in [START_REF] Greenberg | The cost of a cloud: research problems in data center networks[END_REF], we estimate the network costs to be as about 10% of the overall cloud data center costs. As d i,j values we take the euclidean distances between each pair of APs i, j ∈ B, as the underlying operator physical topology is not available to us. We recall that the topological rules we chose are described in Section III.B and encoded in set of constraints ( 2)-( 16). We fix the bandwidth capacities u (i,j) of each link (i, j) ∈ E to 10 Gbps in both hierarchical levels. Observing the positioning of the APs, we fix the maximum link length d = 7.5 km, corresponding approximately to half the radius of the metropolitan region under consideration, and we limit the paths to four hops. Instead of choosing a particular setting for C, U and D, we perform a parametric analysis on them, as presented in Sect. VI.

2) User Mobility Patterns: Individual user mobility patterns cannot be obtained for confidentiality reasons. Furthermore, allowing migrations even when an AP is visited infrequently would have a strong negative impact on the overall network load, without significantly improving user experience. Trying to cope with this issue we perform binning on data: for each user we consider his two more frequently visited APs during the planning horizon. We restrict to consider possible migrations only between these two locations representing, for instance, home and work places of users, which, following [START_REF] Csáji | Exploring the mobility of mobile phone users[END_REF], [START_REF] Bagrow | Mesoscopic structure and social aspects of human mobility[END_REF], dominate human mobility. Technically, this data is obtained by creating groups of users and obfuscating individual identifiers. Other options may be considered, in absence of such data, to estimate mostly visited places [START_REF] Isaacman | Identifying important places in peoples lives from cellular network data[END_REF].

Summarizing, for each pair of APs s and s let f s ,s be the number of users having s and s as the most frequently visited APs; this parameter is general and can be used with any number of frequently visited locations other than two, without changes. In order to further characterize such user mobility patterns, and to allow third parties to reproduce adequately our findings, we report in Fig. 4 the cumulative distribution function of the distances traveled by users while migrating. We observe that about 20% of users do not move at all during the day and that almost all users move less than the radius of the considered region (i.e. 15km). Moreover, in Fig. 5, we present a histogram reporting on the x axis ranges for number of users. For each range [x , x ] on the x axis, a bar represents the number of pairs of APs s and s having f s ,s ∈ [x , x ]. We can conclude that: (i) the majority of paths are covered by a small number of users, and (ii) about 72% of the possible pairs of APs never appear as most frequent for any user. That is, the mobility is concentrated along a few frequently chosen paths, matching our intuition.

VI. EXPERIMENTAL RESULTS

We implemented our algorithms in C++, using IBM ILOG CPLEX 12.6 [START_REF]IBM ILOG CPLEX 12.6 User Manual[END_REF] to solve both LP and MILP problems. Our experiments ran on an Intel Core 2 Duo 3Ghz workstation equipped with 2GB of RAM. In a preliminary round, we experimented on a dataset of ten small size instances involving 50 APs adapted from the facility location literature [START_REF] Ceselli | Heuristic for static cloudlet location[END_REF]. In these we could obtain valid lower bounds with our framework, measuring a worst case gap in terms of number of additional cloudlets activated in our solutions w.r.t. globally optimal ones. Our solutions were found to be of high accuracy: no extra cloudlets were activated in two cases, one extra cloudlet in seven cases and two extra cloudlets in the remaining case. That is, it was impossible to improve by removing more than a single cloudlet in nine over ten cases, even by assuming the most optimistic scenario. We experimented on the real-world dataset, considering three cloudlet size cases: tiny cloudlet of C = 2 racks, car parking cloudlets of C = 4 racks and C = 5 racks, and a 2-4 DC-room cloudlet with C = 40 racks. Using values from [START_REF] Church | On delivering embarrassingly distributed cloud services[END_REF], we assume one rack to host up to 1500 VMs. Considering bottleneck-free back-hauling networks (U ≤ 1), where latency is approximately directly proportional to the euclidean distances among nodes, we consider three latency bounds D: 'loose', 'mid-level', and 'strict' bounds, corresponding respectively to roughly the urban area radius (15 km), 4/5 of it, and 2/3 of it. These three levels of cloudlet access latency are chosen to correspond to three reference mobile cloud services: delay-tolerant storage box services for the loose case, delay-sensitive remote desktop services for the mid-level case, and delay-critical augmented-reality support services for the strict case. We express these bounds as relative numbers, since there is no available public information on absolute cloudlet network latency requirements, despite partial valuable information can be found at [START_REF] Ha | The impact of mobile multimedia applications on data center consolidation[END_REF], [START_REF] Bahl | Mobile gaming[END_REF].

As already described, the maximum link utilization ( percentage) U needs to be kept as low as possible in order to better master the congestion risk and guarantee the QoE for real-time and interactive services. We evaluate three levels for the maximum link utilization bounds: 'loose', 'mid-level', and 'strict'. The stricter they are, the better interactive service support is expected to be, such as for remote desktop and augmented reality. Storage box (TCP-based) services are fault tolerant, given the bulk transfer nature of its data.

In the following, we report extensive results for the SP variant, then we investigate the parametric scenarii for the DP model with VM live migration, finally comparing the approaches in terms of virtual resource migration volume with VM bulk migration. In the plots, we label every parametric scenario with a pair of letters representing respectively the maximum link utilization percentage level U and the cloudlet access latency level D, as in Table I.

A. Analysis of Static Planning solutions

For the static planning case (see Sect. II.B) we consider the full day average behavior, by averaging the traffic and number of users at each AP over the full day. Combining in every possible way capacity, delay and link utilization bound settings, we get 3

• 3 • 3 = 27 scenarii.
As first fitness measure we consider the number of installed cloudlets, as reported in Fig. 6. We can observe that:

• w.r.t. cloudlet capacity C, trivially the lowest rack capacity leads to the largest number of installed cloudlets (i.e. between 15 and 20 over 50 nodes), with no relevant changes by strengthening delay and utilization bound.

No substantial difference was found between the 4-rack and the 40-rack cases, while intuition suggests a lower number of cloudlets for the 40-rack case: this effect is due to the delay constraints requiring a minimum level of geodistribution. Overall, intermediate size facilities (4 racks) appear as the most appealing option: smaller ones require to install on average one cloudlet every two aggregation nodes, which appears as too much, and larger ones do not reduce the number of required facilities significantly, leading to resource and space waste. • w.r.t maximum link utilization, the number of required cloudlet facilities rapidly grows while moving from midlevel to strict bound, except for the 2-racks case, likely due to the lower aggregation of traffic on a more distributed cloudlet network. • w.r.t. cloudlet access latency, we cannot see clear trends.

On average, the solutions show little sensitivity on the value of D, suggesting that, if a decision maker decides to resort to static models unaware of users and VMs mobility, a location planning could be pursued without specifically taking into account different services. As second fitness measure, we consider the average usage of the enabled cloudlets, whose percentage values are reported in Fig. 7. Such a value is trivially related to the number of enabled cloudlets. We can however observe that:

• tiny cloudlets have always a high average usage, with a slight usage decrease just in the case with strict link utilization, having a higher number of enable cloudlets; • 4-rack cloudlets show a behavior similar to tiny ones on mid-level and loose link utilization (scenarii M-* and L-*); on the other hand, strict constraints on link utilization (scenarii S-*) lead to a remarkable decrease of the usage; • as expected, very big cloudlets always show little average usage, independently of other parameters choice; • the setting of cloudlet access latency bounds has very little impact on the average cloudlet usage. As third fitness measure, we consider the percentage of users whose SLAs are violated after their migration. In details, given a solution S resulting from SP model, we know by the parameter f s ,s that users migrate in the planning horizon between APs s and s ; at the same time, we know, by values of variables r s,k p in S, which are those cloudlets k and k servicing s and s , respectively. If it is possible to construct, after the optimization process, a feasible synchronization path between k and k respecting constraints (32), then we say that the SLA of those f s ,s users are respected; otherwise we say that they are violated. Indeed, if a feasible synchronization path cannot be established, a user may perceive a latency during migrations that exceeds his SLA. Our results are presented in Fig. 8, where we notice that:

• enabling a high number of cloudlets leads to low percentage of users with violated SLA: this is the case when the constraint on maximum link utilization is strict. For the scenario S-L we have no unsatisfied user for neither the 4-racks nor the 40-racks case; • conversely, enabling a low number of cloudlets, the percentage of unsatisfied users increases up to 25%. We argue the reason of this behavior to be the following: when the number of enabled cloudlets is high, it is possible to create a higher number of feasible synchronization paths by taking advantage of the higher number of direct links between core nodes. Indeed, the lack of control on the number of unsatisfied users in SP models is the main motivation to consider dynamic planning ones, which instead allow to explicitly enforce SLA to be never violated.

Finally, on the computational efficiency side, all SP instances had a running time of few minutes, with an average time of 360 sec., a minimum of 56 sec. and a maximum of 821 sec., with no evident differences depending on parameters 3 .

B. Analysis of Dynamic Planning solutions

In a second round of experiments, we tested the behavior of the dynamic models (see Sect. III.D) in the case of two timeframes: from 7 am to 8 pm, and from 8 pm to 7 am. These approximately represent working and resting hours. We compared through simulations the Bulk and Live VM Migration cases. As VM replication mobility technology can be seen as a special case of VM Live Migration with infinitesimal amount of memory to transfer, we have not considered experiments using this technology; however results on VM Live Migration are valid also for VM replication scenario. Moreover we included in our tests also an SP model as reference, using data from the working-hours time-frame only (i.e. from 7 am to 8 pm). This may be seen as a 'worst case' planning option, since it is considering the bottleneck time-frame only; we remark that still no guarantee is obtained on SLA satisfaction, even resorting to such a conservative static option.

We restrict the simulations to the six most interesting scenarii, looking at the SP results. That is, we discard the 2-rack scenarii and the loose cloudlet access latency bound scenarii: the first proved to yield infeasible instances when the demand of the sole working-hours is considered; the second provided less interesting insights in previous analysis.

We set the width of the time window suitable to perform VM orchestration T w to 5 hours, which is less than a half of our time-frames. For the storage synchronization path maximum length, we set DQ = 12.75 km (4/5 of the urban area radius), i.e. we consider the synchronization as a service that requires a mid-level latency bound. The size of the disk for augmentedreality support VMs, requiring strict latency bounds, is 20GB, reasonably lower than the one for remote desktop VMs, that is 60GB, requiring mid-level latency bounds. Conversely, the size of the memory is higher for augmented-reality (8GB) than for remote desktop (4GB). To preserve tractability we defined the mapping function Φ of (33) as the following linear function that considers the synchronization traffic generated by any user as a percentage φ of the average traffic generated by all users:

Φ(x) = x • i∈I t∈T δ u i,t i∈I t∈T δ b i,t • φ
The percentage φ is characterized by the type of mobile cloud service: considering remote desktop VMs, only part of the disk is expected to be modified upon user actions; so φ is set to 70%. Instead, for augmented-reality support VMs disks are expected to be smaller and consequently only small volume need to be synchronized; so φ is set to 30% 3 . a) Dynamic Planning with Live Migration.: At first, we experimented on DP variant with VM Live Migration policy. Our algorithms could find feasible solutions for 9 over 12 of these instances. In the results provided hereafter, the missing solutions are marked with the notation NF, meaning Not Found. In fact, as our heuristic builds the solution by rounding one variable at a time with a two-stage process, at every step there is a chance to perform a rounding that eventually leads to infeasibility. To improve this behavior a diversification mechanism could be implemented. However, since these missing results do not affect the overall understanding of our experiments, we did not further investigate in that direction.

As first fitness measure we consider the number of enabled cloudlets, reported in Fig. 9. We note that, while in the 5-rack case DP enables a slightly higher number of cloudlets w.r.t. SP, the models behave similarly in the 40-rack case.

As second fitness measure we consider the expected number of VM migrations generated by the different planning models; this can be seen as a measure of expected incremental point traffic on the network. Such a value can be computed from the values of variables g k k s s that encode the number of users moving from AP s to AP s associated to cloudlets k and k , resp.. We remark that in DP g k k s s terms are explicitly included as variables in the models, while in SP they can be computed in a post-processing phase, once optimization is over. In order to obtain normalized fitness values, we compute the following upper bound on the number of possible VM migrations:

γ = |T | • (|T | -1) 2 s ∈B f s ,s + |T | 2 • s ,s ∈B|s =s f s ,s
which represents the number of migrations needed if all users are assigned to a different cloudlet in each time slot, and we measure fitness as ( k ,k ∈B,s ,s ∈K g k k s s )/γ. Our results are reported in Fig. 10 (as percentage points).

The fraction of migrated VMs for the DP is always higher than that for the SP, without striking differences among scenarii. It is crucial to consider, however, that only DP has an explicit control on the feasibility of these orchestrations. Therefore, as third fitness measure we consider the percentage of users with violated SLA after migration (Fig. 11). DP guarantees by design 0% of users with violated SLA. On the contrary, SP, which does not give any a-priori guarantee, shows an experimental behavior similar to that presented in Fig. 8: tighter constraints on link utilization lead to a higher number of enabled cloudlets, increasing the possibility to create synchronization paths through a higher number of direct links between core nodes, and hence yielding a low fraction of unsatisfied users. A remarkable scenario is the L-S with 5-rack cloudlets: SP asks to enable 11 cloudlets, requiring ∼18% of all possible VMs migrations, but leaving ∼14% of users unsatisfied; DP asks to enable, during the working-hours First, we observe that SP spreads cloudlets more uniformly in the region, while DP locates the cloudlets in a smaller sub-area near the center of the territory, limiting the maximum distance between two cloudlets to satisfy SLA latency bound. Second, we observe that clusters are not necessarily compact; in fact, capacity restrictions may forbid an area to be associated to its nearest cloudlet. DP tends to create a more involved clustering structure, especially during working-hours. Major changes are observed in pink and light blue clusters, while the remaining tend to keep the same structure over the two time frames.

On the computational efficiency side, while SP instances have execution times in the scale of few minutes, DP instances have execution times that ranges from few hours to several days. In particular, while SP cases have an average execution time of 4 min., with a minimum of 74sec. and a maximum of 17 min., DP cases have and average execution time of ∼ 22 hours, with a minimum of 75 min. and a maximum of ∼ 6 days. Since our model is designed for medium and long term planning, none of them appears to be critical 4 .

b) Nearest Cloudlet Association: In order to further assess the need for considering the association between APs and cloudlets directly within the planning model, we propose the following experiment: given the network resulting by our model we disregard the association of AP to cloudlet, and instead we associate APs to the nearest cloudlet in terms of number of hops. For example, in Fig. 12(d) we can see the cluster of APs associated to the nearest cloudlet using the same network used in Fig. 12(b) and 12(c).

As a first comparison, in Fig. 13 we show the percentage of users with violated SLA after a nearest cloudlet association. As compared with our approach in Fig. 11, we remark that: (i) nearest cloudlet association produces SLA violations even with dynamic planning, while our approach guarantees no As a second comparison, we compute the cloudlet overuse, i.e. the excess over VM capacity C. In Fig. 14 we present the overuse amount, noting that with 40-rack cloudlets there is no overuse, and with tiny 5-rack cloudlets there is a high overuse for several instances of both SP and DP approaches. c) Bulk migration results: Our initial attempts to optimize DP models with VM Bulk migration produced no feasible solutions on any instance of the dataset. Indeed, bulk migration policies clash with the ambition of producing ahead a careful service and synchronization plan; in other terms, bulk migrations can be seen as the result of an unexpected need of synchronization, a human-ordered point operation, rather than a consolidated and automated operation.

Nevertheless, in order to analyze the impact of Bulk Migrations, we proceeded as follows. We produced solutions of DP with VM Live Migration, and we computed the maximum size of a VM file that the network could manage to transfer without violating user SLA. Such a value is unfortunately not directly available after optimizing DP Live Migration models; on the contrary, the problem of finding it can be proved to be NP-Hard. Therefore, we performed the following simplifying assumptions: (i) cloudlets located in aggregation nodes are moved to the corresponding core nodes; (ii) synchronization paths are allowed for an arbitrary number of hops and arbitrary length -that is, synchronization is performed among core nodes only, and only maximum single-link length constraints and single-link latency bounds are kept. Assumption (i) is particularly mild, as any cloudlet placed at aggregation level would represent a bottleneck of the whole network.

The problem of finding the largest file size Γ turns out to be a multicommodity-flow problem modeled as follows:

max Γ (44) s.t. k ,k ∈K f k ,k i,j ≤ (1 -U ) • u • Tw , ∀(i, j) ∈ E J (45) j∈J f k ,k i,j - j∈J f k ,k j,i =      fk k • Γ if i = k 0 if i = k ∧ i = k -fk k • Γ if i = k ∀(k ,k )∈K ∀i∈J (46) f k ,k i,j = 0 , ∀(i, j) ∈ E J | d(i.j) ≥ d (47) f k ,k i,j ≥ 0 (48)
Let: E J be the set of links between core nodes; fk k be the fixed number of VMs to migrate between cloudlets k and k ; and f k ,k i,j be non-negative continuous variables representing the number of VMs to migrate from k to k and whose migration path traverses link (i, j). Inequalities (47) and (45) model single-link length and latency bounds, resp.. Inequalities (46) are flow conservation constraints. That is, model (44)-( 48) is a LP that can be optimized very efficiently.

For each 5-rack cloudlets case where we obtained a feasible solution in the VM Live Migration model, we run this model with a parametric analysis on the link length threshold d: starting from the value used in DP experiments, we decreased it stepwise, until the problem became infeasible.

Our results are collected in Fig. 15. Three different features of each solution are reported: (i) the optimal Γ value, i.e. the maximum VM file size that the network can afford; (ii) the average number of hops of the generated synchronization paths; and (iii) the average length of the generated synchronization paths. Each chart contains a dashed black line, representing the required standard for synchronization paths. These are 3 hops, maximum total length of 12Km and either a 28GB file (8GB memory and 20GB disk) for the augmented reality service or a 64GB file (4GB memory and 60GB disk) for remote desktop. That is, fully feasible solutions would have values above the dashed line in the leftmost chart, and below it in the central and rightmost ones: it is easy to check that in no case it was possible to find one of them. Matching intuition, using high allowed link length values, one can move very large VM files, at the price of generating highly infeasible synchronization paths. We can further note that:

• for augmented reality reference service, using the total link length we can route very big-size VMs (almost 3 times the desired size, see Fig. 15(a)), but with highly infeasible paths (almost 3 times more hops than expected, see Fig. 15(b), and 5 times longer paths, see Fig. 15(c)). However a reasonable trade-off can be reached using 75% of the maximum link length: in this case we can route a 29GB VM file, with an average number of hops of 5 and an average path length that is 50% above the threshold; • for remote desktop reference service we were not able to route the expected VM file size (see Fig. 15(d)): a maximum file size of 29GB can be routed, and still with violations in terms of average number of hops and average paths length. No improvement is achieved by lowering the allowed link length. Moreover using less than 80% of the link length already leads to infeasibility. Summarizing, Bulk Migration seems to be a feasible alternative to Live Migration on Augmented Reality reference services, where the size of synchronization files is still limited; in fact solutions can be found, violating latency and maximum hop constraints only slightly. On the contrary, on Remote Desktop reference services, Bulk Migration does not appear as a viable option. In either case, matching DP models with VM Live Migration proves to be the most appealing option.

VII. CONCLUSION

We provided for the first time at the state of the art a comprehensive mobile edge cloud network design framework for mobile access metropolitan area networks. We formally defined the problem, including two planning model variations: (i) considering a static status of the network, unaware of variations during the planning horizon, and (ii) considering a dynamic network, including load variations and mobility of users and virtual machines, encoding three different virtual machine mobility technologies.

We compared the different planning options extensively for scenarii built over real cellular network datasets, differentiating between different traffic engineering and performance goals for reference mobile cloud services, analyzing: (i) the use of network facilities resources, i.e. number of enabled cloudlets, usage of cloudlet resources, migrated volume and (ii) the compliance with users' SLA. As conclusion we can state that:

• while we guarantee full compliance with users' SLA considering users mobility and dynamic variations of the network, their exclusion from the modeling leads to the infringement of SLA for up to 20% of users; • the increase of use of network resources given by the consideration of users mobility is limited to at most 5 more enabled cloudlet for serving 600 APs, for the Paris metropolitan area network use-case (on real traffic logs); • the simultaneous consideration of the design of the network, the association between APs and cloudlets and the routing is needed to keep compliance with the limited resource and users' SLA: decoupling these design decisions using trivial heuristics leads to SLA infringement for up to 27% of users and in cloudlet capacity over-use; • comparing VM Live Migration and VM Bulk Migration technologies, the former has proved eligible for the use both with delay-critical and delay-sensitive mobile cloud services, while the latter constantly violates limits on network resources and seems to be a feasible alternative only when the size of VM files to synchronize is small. We believe the provided insights can stimulate further researches in the rising research field of mobile cloud networking and mobile edge computing, especially in the field of online routing and cloud migration policies as outlined in [START_REF] Jin | Softcell: Scalable and flexible cellular core network architecture[END_REF], [START_REF] Secci | Linking virtual machine mobility to user mobility[END_REF]. As a future work, it can be interesting to address the problem of online management of multiple VMs, application VMs and network function VMs, using multiple, possibly preinstalled, cloudlet facilities.

Fig. 1 :

 1 Fig. 1: Example of a simplified mobile edge cloud network.

Fig. 2 :

 2 Fig. 2: Structure of the Static Planning algorithm

Fig. 3 :

 3 Fig. 3: Overall structure of the Dynamic Planning algorithm

1 )

 1 Estimation of Model Parameters: Coefficients δ u s and δ b s

Fig. 4 :

 4 Fig. 4: CDF of traveled distances of user flights.

Fig. 5 :

 5 Fig. 5: Histogram of nb. of users covering same flight.

Fig. 6 :

 6 Fig. 6: Number of enabled cloudlets.

Fig. 7 :

 7 Fig. 7: Average usage of cloudlets (%).

Fig. 8 :

 8 Fig. 8: Ratio of users with violated SLA after migration.

Fig. 9 :

 9 Fig. 9: Number of enabled cloudlets.

Fig. 10 :

 10 Fig. 10: Expected fraction of VMs to migrate.

Fig. 11 :

 11 Fig. 11: Percentage of users with violated SLA.

Fig. 12 :

 12 Fig. 12: Clustering produced by AP-cloudlet associations in L-M scenario with 5-rack cloudlets.

Fig. 13 :Fig. 14 :

 1314 Fig. 13: SLA violation (% users) with nearest cloudlet association

  Fig. 15: Bulk Migration post-processing results using 5-racks cloudlets.

TABLE I :

 I Labelling of parametric scenarii

						Cloudlet Access Delay Bound
						Strict	Mid-Level	Loose
	Maximum	Link	Utilization	Bound	Strict Mid-Level Loose	S-S M-S L-S	S-M M-M L-M	S-L M-L L-L
	Related Reference Mobile Cloud Services	Augmented Reality Supp.	Remote Desktop	Storage Box

The formalization of the generalized model that considers multiple SLAs concurrently is presented in Appendix A.1 in Supplementary Materials.

Additional details on execution times are given in the Appendix Fig. A.1 of the Supplementary Materials. In Appendix A.2 of Supplementary Materials we also report additional results on the cloudlet access path length.Summary of the parametrization of the reference mobile services can be found in the Appendix TableA.IV in Supplementary Materials.

Details on execution times are given in the Appendix Fig. A.1 in Supplementary Materials. Analysis on percentage usage of cloudlets and cumulative distribution function of the cloudlet access path lengths does not show further insight, hence we left their discussion in Appendices A.3 and A.4 in Supplementary Materials.

ACKNOWLEDGMENT

This work was partially funded by the ANR ABCD (Grant No: ANR-13-INFR-005) and the FP7 MobileCloud (Grant No. 612212) projects. We thank C. Ziemlicki and S. Uppoor from Orange for the support with cellular data retrieval.


Son Ho-Van
email: son.ho-van@emse.fr

Jérome Douzet

Duyen Le-Quang

Baptiste Bouillot

Jean-Michel Herri

Behavior of cyclopentane hydrates formation and dissociation in pure water and in the presence of sodium chloride

Keywords: Cyclopentane hydrate, Equilibrium temperature, Sodium chloride

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

1. Introduction Nowadays, clathrate hydrates are very important in many applications in both science and engineering aspects. Clathrate hydrates, or simple hydrates, are ice-like non-stoichiometric crystalline compounds consisting of lattice cage-like structures formed by hydrogen-bonded water molecules that enclose different guest molecules stabilizing the lattice structure. The guest molecules can be small molecules such as CO 2 , H 2 , CH 4 , C 2 H 6 , N 2 or relatively large molecules such as Cyclopentane, Neohexane, Dimethyl sulfide, Tetrahydrofuran (THF). Hydrates are mostly stable at low temperature and high pressure conditions which are similar to the deep-sea petroleum operation conditions (0 to 10 °C, tens to hundreds of bars). In the crude oil pipeline, light hydrocarbon gases are soluble in the oil phase at high pressures leading to hydrate formation under appropriate conditions causing a partial plugging and even complete blockage of pipeline (E. Dendy [START_REF] Sloan | Review article Fundamental principles and applications of natural gas hydrates[END_REF]. The blockage due to hydrate formation not only leads to an increase of pressure drop in the pipeline but can also lead to an emergency shutdown or even damage devices and environment, because of the formation of a plug, and after due to the risks associated to its dissociation.

Currently, hydrate is potentially beneficial to be utilized for some applications such as natural gas storage [START_REF] Mimachi | Natural gas storage and transportation within gas hydrate of smaller particle: Size dependence of self-preservation phenomenon of natural gas hydrate[END_REF][START_REF] Sun | Natural gas storage in hydrates with the presence of promoters[END_REF]Sun et al., ), (2005;;[START_REF] Zanota | Improvement of methane storage in activated carbon using methane hydrate[END_REF]; hydrogen storage [START_REF] Veluswamy | Hydrogen storage in clathrate hydrates: Current state of the art and future directions[END_REF] ; carbon dioxide capture [START_REF] Duc | CO 2 capture by hydrate crystallization -A potential solution for gas emission of steelmaking industry[END_REF] ; ground/ocean sequestration (A. [START_REF] Yamasaki | A new ocean disposal scenario for anthropogenic CO 2 : CO 2 hydrate formation in a submerged crystallizer and its disposal[END_REF][START_REF] Burnol | Influence of impurities (nitrogen and methane) on the CO 2 storage capacity as sediment-hosted gas hydrates -Application in the area of the Celtic Sea and the Bay of Biscay[END_REF]; and transportation [START_REF] Aspelund | Ship Transport of CO 2[END_REF] ; isolation of greenhouse gas (Yu-Taek [START_REF] Seo | Efficient Recovery of CO 2 from Flue Gas by Clathrate Hydrate Formation in Porous Silica Gels[END_REF]; gas separation [START_REF] Babu | A review of the hydrate based gas separation (HBGS) process for carbon dioxide pre-combustion capture[END_REF][START_REF] Sloan | Review article Fundamental principles and applications of natural gas hydrates[END_REF]; frozen food [START_REF] Muromachi | Thermodynamic modeling for clathrate hydrates of ozone[END_REF][START_REF] Peters | Production of CO 2 clathrate hydrate frozen desserts by flash freezing[END_REF]; refrigeration and cold thermal energy [START_REF] Darbouret | Rheological study of TBAB hydrate slurries as secondary two-phase refrigerants[END_REF][START_REF] Douzet | Prototyping of a real size air-conditioning system using a tetra-n-butylammonium bromide semiclathrate hydrate slurry as secondary two-phase refrigerant -Experimental investigations and modelling[END_REF][START_REF] Nakajima | Clathrate hydrate formation from cyclopentane-in-water emulsions[END_REF]. In addition, an interesting potential application for gas hydrate is water treatment, especially desalination [START_REF] Bradshaw | Desalination Utilizing Clathrate Hydrates (LDRD Final Report)[END_REF]. Based on the possibility of hydrate in forming an ice-like compound of clean water and guest species, the potential of using hydrates for desalination of water has been investigated and currently being developed at both laboratory and industrial scale.

In fact, offshore well operates under the seafloor, so that the effect of the salinity of aqueous phase in water produced with petroleum is an important factor being considered for hydrate formation [START_REF] Zylyftari | Nucleation of cyclopentane hydrate by ice studied by morphology and rheology[END_REF]. Furthermore, considering natural gas transportation from an offshore to the land-based fields, presence of seawater is an appropriate condition to form natural gas hydrate in the gas pipeline. Seawater is also the environment for carbon dioxide sequestration in the ocean. In addition, hydrate-based desalination of seawater is certainly performed in salty water environment. For many of the mentioned hydrate applications, there is a need to study and understand the hydrate formation in presence of salts, such as NaCl, KCl, MgCl 2 and CaCl 2 , or seawater, in order to develop hydrate-based technologies. It implies describing the liquid thermodynamic, and especially the chemical potential of water, for example by using an eNRTL model [START_REF] Kwaterski | Modelling of gas clathrate hydrate equilibria using the electrolyte nonrandom two-liquid (eNRTL) model[END_REF].

It is well known that, clathrate hydrate stability depends on the guest molecule, and its ability to fit the size of cavities built by water molecules. Some of the guests are solubilized gases such as CO 2 , H 2 , CH 4 , C 2 H 6 , N 2 and they imply to operate a process under high pressure. Cyclopentane is also a hydrate former, and it is a liquid at atmospheric pressure. It is a promising candidate for every industrial process where pressure is a handicap, such as separation processes. In addition, because it is un-miscible with water, it can be recovered easily after dissociation of hydrate.

In this study, we performed experiments on cyclopentane hydrate with the mass fraction of NaCl in aqueous solution from 0 to 26% in order to investigate the behavior of the temperature and conductivity of the mixture during hydrate formation and dissociation. The equilibrium temperatures of cyclopentane hydrate at each salt concentration were also reported.

Experimental

Materials

In this study, the experiments were carried out in the presence of ultrapure water obtained from Milli-Q® Advantage A10 Water Purification System. This system permits to produce water with conductivity σ ≤ 0,055 μS.cm -1 and TOC (total organic carbon content) less than 5 ppm. Cyclopentane (˃95% pure) are supplied by Across, sodium chloride (99.5% pure) is supplied by Sigma-Aldrich. Relevant physical properties of the materials are provided in Table 1.

As we mentioned before, cyclopentane is immiscible in water, therefore, it is needed to disperse cyclopentane into water by mixing. In addition, due to the relatively high melting point of cyclopentane hydrate at atmospheric pressure, measurements can be made above the freezing point of water and assure that ice has not formed.

Experimental apparatus description

Figure 1 presents the experimental apparatus which are installed for studying the thermodynamic equilibrium of cyclopentane hydrate.

The reactor is a jacketed batch vessel (1) which is made from glass applied by Verre Equipments (France) with a total volume of approximate one liter. The vessel is equipped with a double jacket controlled by an external temperature bath which is supplied by the cryostat (2). The cryostat RE 307 supplied by Lauda Ecoline has the operating temperature range from -20 °C to 200 °C with temperature accuracy of ±0.2 °C. The heat transfer fluid is ethylene glycol 44 wt%. The mixture inside the vessel is mixed by an impeller (3) and a motor (7). The temperature probe (PT100) with the uncertainty of ±0.1 °C and conductivity probe are immersed in the solution to measure real-time temperature and conductivity values of the solution. The results are monitored by a computer (9) thanks to two transmitters ( 6), ( 8) and a Labview software installed in the personal computer.

The salt concentration of solution is measured by both ion chromatography Dionex DX-500 IC system (13) and by drying oven Binder (12) at 60 °C from a liquid sample taken from the bottom of the vessel at the end of the experiment, when all cyclopentane hydrate is completely dissociated. This procedure allows to cross-check the initial and final salt concentration of each experiment.

Fig 1. Simplified schematic diagram of the main experimental apparatus

Experimental protocol

Firstly, before each experiment, all the beakers and the vessel were washed and cleaned by absolute ethanol and then by deionized water. About 500 g salt solution was prepared and mixed for 10 min, then 1 ml of solution was taken to measure the salt concentration by ion chromatography in order to compare it to the concentration at the end of experiment when the equilibrium temperature was recorded. The solution was then injected into the glass vessel, followed by cyclopentane with a theoretical stoichiometric composition (n water /n cyclopentane =17) (Sloan, 1998).

The solution was continuously agitated by a stirrer at 300-400 rpm. The cryostat was then started at a setpoint, above the ice equilibrium temperature around 1-2 °C, depending on the salt concentration. When the temperature of sample reached a value close to the set-point, the hydrate formation was initiated by injecting a trace amount of ice (made previously from deionized water), and salt to keep the salt concentration of the sample constant. The temperature and conductivity of sample were continuously measured and recorded. Visual observations were also performed. After around 1-2 hours, when a sufficient amount of hydrate was formed inside the vessel, the cryostat was stopped. It led to the cyclopentane hydrate dissociation due to the heat from environment. When cyclopentane hydrate could not be observed, the temperature and conductivity curve slopes changed immediately. At this time, 1 ml and 5 ml of salt solution at the bottom of the vessel were taken to measure the salt concentration by ion chromatography and drying oven methods respectively. If the initial and final salt concentrations are identical, the equilibrium temperature is then recorded.

Result and discussion

The behavior of cyclopentane hydrate formation and dissociation

The process of formation and dissociation can be recorded from the temperature and the conductivity changes inside the vessel during experiment, due to the both exothermic and endothermic nature of the these two processes respectively, and also due to the change in liquid salt concentration.

Figure 2 presents temperature and conductivity profiles of the experiment in pure water. The abscissa indicates the time lapse (t) from the beginning of the experiment. It can be seen that, at the beginning, the temperature decreased due to the cooling by cryostat. When ice was injected into the vessel at 64 min, the temperature decreased suddenly because of the low temperature of ice. Simultaneously, some hydrate crystals were observed by naked eyes in the vessel. The temperature then slightly increased gradually resulting from the heat release of crystallization. The temperature was stable over the period from 120 to 225 min because the hydrate formation almost finished inside the vessel. A hydrate block was observed in the vessel in this period.

In the first approach, in order to measure the equilibrium temperature, the cryostat was stopped. During the period from 225 to 275 min, cyclopentane hydrates dissociated partially. The temperature inside the vessel rose gradually whereas the temperature of dissociation normally remains constant when the dissociation occurs with pure water. This un-expected non constant temperature dissociation can be explained only by a non-equilibrium dissociation. The temperature in the vessel increased continuously and a shift of temperature must occur between the crystals inside the vessel and the bulk solution. The temperature still increased slightly due to the endothermic nature of the dissociation process. But after, the hydrate dissociation ended at approximately 333 min, we observed a sudden increase of the slope of the temperature curve. Afterward, no hydrate can be observed inside the vessel, and therefore, the final equilibrium temperature was recorded at 7.7 °C. The temperature then increased gradually up to a value close to the ambient temperature.

In the experiment described above in pure water, theoretically, the conductivity can be only affected by two main factors: temperature and phase characteristic of the mixture inside the vessel. However, due to the presence of bubbles and hydrate slurry phase, the conductivity showed illogical tendencies during the experiment.

Fig 2. Temperature and conductivity histories of CP hydrate experiment with pure water

It can be observed in Fig 2 that the conductivity was constant around 1.8 mS/cm from the beginning to the time when ice was added into the vessel. The conductivity then suddenly dropped down to 1.6 mS/cm due to again the low temperature of ice, and then it rose very quickly and strangely up to 2 mS/cm.

During cyclopentane hydrate formation, the conductivity decreased slightly due to the appearance of hydrate crystals on the electrode surface of conductivity probe. It caused preventing partially the contact of the aqueous mixture with the probe. The conductivity then increased slowly, probably due to the increase of temperature inside the vessel. When hydrate dissociated intensely from 275 to 333 min, the electrode of conductivity probe was freer. In addition, during this period, a small increase of the temperature of mixture was also observed. This led to a rise in the mixture conductivity value. However, the conductivity then decreased unexpectedly and slightly after hydrate dissociation finished completely. It can be attributed to air bubbles appearance at the end of experiment. The conductivity dropped from 40 mS/cm to nearly 30 mS/cm during a period from the beginning to 70 min (time of ice adding) due to the initial cooling down. The cyclopentane hydrate formation was observed after injecting ice into the vessel. Although the hydrate formation led to an increase of the NaCl concentration (because this process consumes pure water only and cyclopentane), the conductivity decreased unexpectedly. Indeed, the condense phase was not homogeneous, probably due to the hydrate slurry and also bubbles in the vessel caused by the mixing process.

The conductivity then rose during a period from 250 to 310 min as hydrate dissociated strongly. Theoretically, when hydrate dissociates, pure water from hydrate structures is released leading a decrease in salt concentration and, therefore, in conductivity. In fact, the conductivity increased is this period. It was due to the temperature increase of aqueous mixture, and especially due to the dissociation of hydrate that led the electrode surface to be freer from hydrate slurry in the aqueous mixture.

The slope of conductivity curve increased slightly once no hydrate was observed inside the vessel. Simultaneously, the slope of temperature changed immediately. It indicated the equilibrium temperature of the cylopentane hydrate was 5.7 o C in the presence of 3.5% NaCl, undoubtedly less than the equilibrium temperature in pure water. The conductivity then increased gradually up to about 36 mS/cm at the end of the experiment as a temperature increase resulting from the environment heating. The same behaviors of cyclopentane hydrate formation and dissociation in the presence of different salt concentrations were also observed in all the experiments. Interestingly, at salt concentrations higher than 20% w/w, crystalline rock salt hydrate or hydrohalite (NaCl.2H 2 O) can be easily observed during the crystallization due to the appearance of halite over-saturated solution inside the vessel leading to the formation of these solid crystals.

Fig 5 presents an image of cyclopentane hydrate formation in the presence of 26% NaCl. A noticeable quantity of NaCl.2H 2 O crystals deposited at the bottom of the vessel during the hydrate formation. In fact, this phenomenon has motivated scientists to apply this process for water treatments as desalination and depollution processes. In fact, there was cyclopentane hydrate floating at the surface (composed of pure water and unmiscible cyclopentane after dissociation), and there were salt hydrate crystals (NaCl.2H 2 O) at the bottom.

The equilibrium temperature of cyclopentane hydrate

The equilibrium temperatures of cyclopentane hydrate following the environmental dissociation method in pure water and in the presence of sodium chloride with the different concentrations are summarized in Table 2.

As mentioned in the experimental protocol, at each experiment, ion chromatography and drying oven method were applied to cross-check the results. When the initial and final salt concentrations according to these methods are the same, it means that hydrate dissociation has completely finished, the equilibrium temperature is then recorded.

It can be seen from Table 2 that the equilibrium temperature depends strongly on the salt concentration. In fact, it decreases by increasing of salt concentration. The equilibrium temperature of cyclopentane with pure water in this report, 7.7 °C, is identical to literature (E. Dendy [START_REF] Sloan | Review article Fundamental principles and applications of natural gas hydrates[END_REF], (Erik Gisle Dirdal et al., 2011), and[START_REF] Sefidroodi | Investigation into the strength and source of the memory effect for cyclopentane hydrate[END_REF], while [START_REF] Han | Enhanced efficiency of salt removal from brine for cyclopentane hydrates by washing, centrifuging, and sweating[END_REF] reported the equilibrium temperature of 7.8 °C. It indicates that our equilibrium temperatures of cyclopentane in pure water according to the environmental dissociation method are close to literature data. The equilibrium temperature, °C, ±0.1 o C 7.7 6.9 6.3 5.7 4.9 3.5 2.0 0.9 -1.0 -2.7 -5.0 -7.2 -9.7 -11.0 -13.2

Fig 6. The equilibrium temperature of cyclopentane hydrate according to the different dissociation methods in the presence of NaCl

However, the equilibrium temperature in the presence of 3.5% NaCl according to our study (5.7 °C) is less than the result reported by Han et al (6.6 °C). The reason of this gap is probably due to the difference between two procedures applied to determine the equilibrium temperature.

In order to compare our experimental results with the published literature, our data and the data from Zylyftari et al (2013) and [START_REF] Kishimoto | Crystal Growth of Clathrate Hydrate at the Interface between Seawater and Hydrophobic-Guest Liquid: Effect of Elevated Salt Concentration[END_REF] are presented in Figure 6.

It can be seen from Figure 6 that our experimental results are relative close to the result in literature. However, our equilibrium temperatures are slightly higher than the equilibrium temperatures reported from both publications at all salt concentrations. In fact, Zylyftari used the micro-Differential Scanning Calorimetry (µ-DSC) to determine the equilibrium temperature of cyclopentane hydrate and the heat of hydrate dissociation. Masatoshi and co-workers applied the slow stepwise dissociation method for determining the equilibrium temperature. Figure 6 indicates also that the data from Zylyftari are close to the data from Masatoshi. This illustrates that these two methods can provide accurate equilibrium data. The environmental dissociation method, in this case, is not a very accurate method to obtain the equilibrium temperature. It is probably due to the high heating rate by environment causing the difficulty to obtain correctly the equilibrium temperature of cyclopentane hydrate at the end of the dissociation process. This means that, we may miss the exact point before it is recorded. However, this method provides a good first approximation, and can be combined with a slow dissociation method.

Conclusion

The behavior of cyclopentane hydrate formation and dissociation has been investigated. The experimental results show that the temperature of the sample increased when hydrate formed inside the vessel owing to its natural exothermic characteristic. When hydrate dissociated strongly, the slope of temperature curve decreased, and the temperature was nearly stable during this period due to the heat-releasing of this process. In contrast, the conductivity showed some unexpected trends in pure water and also in the presence of salt. This was due to the appearance of bubbles and hydrate slurry in the bulk and crystals on the system of the electrode. However, at the time when the equilibrium temperature was recorded, the slopes of temperature and also conductivity changed immediately. The change of slopes can provide information on the dissociation process. Our equilibrium data were also compared to data in the published literature. The comparison indicates that our data are relatively close to the others. However, the environmental dissociation method provides values slightly higher compared to the µDSC and slow stepwise dissociation methods. It has motivated us to continuously study the equilibrium temperature of cyclopetane hydrate in order to find the most accurate data.

  Behavior of cyclopentane hydrates formation and dissociation in pure water and in the presence of sodium chloride Son Ho-Van, Jérome Douzet, Duyen Le-Quang, Baptiste Bouillot, Jean-Michel Herri To cite this version: Son Ho-Van, Jérome Douzet, Duyen Le-Quang, Baptiste Bouillot, Jean-Michel Herri. Behavior of cyclopentane hydrates formation and dissociation in pure water and in the presence of sodium chloride. INTERNATIONAL CONFERENCES ON EARTH SCIENCES AND SUSTAINABLE GEO-RESOURCES DEVELOPMENT -ESASGD 2016-, Hanoi University of Mining and Geology, Nov 2016, Hanoï, Vietnam. pp.150 à 157. hal-01466636

Fig 3 .

 3 Fig 3. Images of cyclopentane hydrate formation in pure water

Fig 4 .

 4 Fig 4. Temperature and conductivity histories of CP hydrate experiment with 3.5% NaCl

  Fig 5. Visual observation of cyclopentane hydrate formation in the presence of 26% NaCl at the bottom of the vessel

Table 1 .

 1 Materials physical properties

	Material	Chemical	Mol.weight	Density	Viscosity	Solubility in	Purity	Manufacturer
		formula	g. mol -1	g.cm -3		water
	Cyclopentane	C 5 H 10	70.1	0.751 (25 °C)	0.44 (20 °C) 156 mg/l (25 °C)	95%	Acros
	Sodium chloride	NaCl	58.4	2.16 (25 °C)	-	36.0 g/l (20 °C)	99.5% Sigma-Aldrich
	Water	H 2 O	18.0	1.00 (4 °C)	1.00 (20 °C) -	-	-

Table 2 .

 2 The equilibrium temperature of cyclopentane hydrate in the presence of NaCl

	Salt concentration % wt 0	1	2	3.5	5	8	10	12	14	16	18	20	22	23	26

Acknowledgements

Association pour la recherche et le developpement des methodes et processus industriels (ARMINES) Ministry of Education and Training (MOET), Vietnam; Hanoi University of Mining and Geology.