Moussa Kafal
email: moussa.kafal@cea.fr

Member, IEEE Wafa Ben Hassen

Jaume Benoit

A Performance Analysis of Optimization Algorithms for Wiring Network Reconstruction and Diagnosis based on Reflectometry

Keywords: Complex wire networks, topology reconstruction, inverse problems, optimisation algorithms

During the last decade, time domain reflectometry (TDR) methods have formed the cornerstone for the diagnosis of transmission line networks. They have been adopted recently to the blind characterization of networks, thanks to graph theory and optimization based algorithms. Using a single testing point, it became possible to reconstruct the topology of a black-boxed network while returning precise estimates of branch lengths and most importantly load impedances. In other words, disconnecting the network for testing purposes is no longer needed. In this paper, we opted to perform a comparative analysis to study the effect of different optimisation based algorithms on the applicability of the aforementioned method. Particularly, we designed CAN bus networks based on real aeronautical cables of increased complexity to investigate their performance in terms of precision and computational burden.

I. INTRODUCTION

In the era of Internet of Things (IoT), electrical wiring and interconnect systems (EWIS) are massively hosted everywhere in many fields such as transportation systems, communication networks, power grids, etc., where the transfer of energy and information is a fundamental pillar to ensure the optimal system operation [START_REF] Auzanneau | Wire troubleshooting and diagnosis: Review and perspectives[END_REF]. Yet wiring faults and failures originated from aging, corrosion and vandalism, etc., are inevitable and can lead to problems with the quality of power and communication, blackouts, aircraft crashes, and fires, etc.

Much research has been done to determine viable methods for the location of wiring faults. This effort has been spurred on by catastrophic accidents that has occurred. A reliable method for locating wiring problems is needed for the safety of the general public. With life and limb at stake, the expense of maintaining faulty wiring is a driving force in funding the development of better fault location methods. Currently, several methods are available to determine wire fault locations.

The most widely used technique is reflectometry. Thereby, a high-frequency signal is injected into the network under test (NUT) [START_REF] Furse | A critical comparison of reflectometry methods for location of wiring faults[END_REF]. The reflected signal is rich of information about changes of cable impedances which is in turn valuable to monitor wiring faults. Over the last decade, many variants of reflectometry have been developed targeting specific applications and trying to bypass inherent limitations. This included the well known Time Domain Reflectometry (TDR) [START_REF] Smith | Analysis of spread spectrum time domain reflectometry for wire fault location[END_REF], Frequency Domain Reflectometry (FDR) [START_REF] Furse | Frequency-domain reflectometry for on-board testing of aging aircraft wiring[END_REF], Ultra Wide Band (UWB) based TDR [START_REF] Buccella | Detection and localization of defects in shielded cables by time-domain measurements with uwb pulse injection and clean algorithm postprocessing[END_REF], and Spectrum Time Domain Reflectometry (STDR) [START_REF] Furse | Spread spectrum sensors for critical fault location on live wire networks[END_REF], etc. They use different incident signal and signal processing methods.

Raw reflectometry data can be quite complicated and very difficult to analyze once branched networks are addressed [START_REF] Griffiths | The invisible fray: A critical analysis of the use of reflectometry for fray location[END_REF]. In fact, this is mainly caused by junctions, network terminations, etc. that lead to the occurrence of multiple reflections. On the other hand, improved reflectometry methods used the baseline approach to bypass this problem. In baselining, the reflectometry response of the faulty NUT is compared with that of a reference healthy version of it, which can be either retrieved by measurements or computed from simulations. This operation ideally removes the spurious echoes generated by impedance discontinuities like junctions, leaving only those echoes initially generated by the interaction between the testing signals and the faults in order to enable the detection, location, and characterization of different types of faults [START_REF] Abboud | A matched-pulse approach for soft-fault detection in complex wire networks[END_REF].

Accordingly, mapping the tested network is a direct way to diagnose faults. In fact, this would allow reconstructing the topology of a totally or partially unknown network, and thus serve as a reference healthy model of the NUT. This will later form the basis of baselining for reflectometry methods enabling continuous monitoring of an EWIS. Besides, most fault detection techniques outside the scope of reflectometry also rely on the prior knowledge of the network's topology for their proper applicability [START_REF] Kafal | A review on the application of the time reversal theory to wire network and power system diagnosis[END_REF].

Within this context, considerable work has been realized in the state-of-art towards developing and optimizing techniques dedicated for wired network mapping [START_REF] Blum | A continuous cost function for the reconstruction of wired networks from reflection measurements[END_REF], [START_REF] Shi | Identification of wire network topology using impedance spectroscopy[END_REF]. A vast majority relied on the tenets of reflectometry to measure the response of a tested network from one or more of its extremities [START_REF] Smail | Reconstruction of faulty wiring networks using reflectometry response and genetic algorithms[END_REF]. This was followed by solving the inverse problem, where a response provided by a direct model is iteratively improved to finally align with the measured response. This became possible, thanks to the wide selection of optimization algorithms.

In literature, many authors have been working on merging reflectometry with different optimization based techniques for the sake of EWIS mapping [START_REF] Boudjefdjouf | Diagnosis of multiple wiring faults using time-domain reflectometry and teaching-learning-based optimization[END_REF]- [START_REF] Smaïl | Detection and location of defects in wiring networks using time-domain reflectometry and neural networks[END_REF]. However, most relied on the prior knowledge of the network's topology and were confined to estimating the branch lengths. Besides, predefined loads were imposed at the extremities of the tested network which were mainly open or short circuits. In practice, disconnecting the network from its loads is unattainable in many applications (nuclear power-plants, aeronautics, etc.), and the beforehand awareness of its scheme is generally impossible.

In a recent development, the authors of [START_REF] Kafal | Blind diagnosis of a blackboxed fully-loaded wiring network for configuration structuring and fault monitoring[END_REF]- [START_REF] Benoit | Procede, mis en oeuvre par ordinateur, de reconstruction de la topologie d'un reseau de cables, utilisant un algorithme genetique[END_REF], proposed integrating the graph theory with the optimization based algorithms to solve the inverse problem of measured TDR responses for totally unknown networks. These joint graphoptimization-reflectometry (GOR) techniques enabled a blind reconstruction of the tested network accompanied with estimating branch lengths and returning precise assessment of the load impedances.

The present paper, is intended to present a full-scale comparative study of several optimization techniques in the GOR method and investigate thoroughly the advantages and disadvantages of each as a function of several parameters including the computational time, complexity of the network, hardware implementation, accuracy, etc. The study will be backed up with experimental validations using real-life complex wiring networks.

II. METRICS OF THE GOR BASED METHODS

The GOR methods have shown to be efficient in mapping obscure wiring networks using a single-extremity measured TDR response followed by resolving the inverse problem. In what follows we will try to explain different elements and stages composing these techniques.

A. Wave Propagation Model

A direct model is capable of describing the propagation of high frequency electromagnetic waves along a Transmission Line TL in the time domain: the model is based on the telegrapher's equations given by (1a) &(1b), where the perunit-length electrical parameters matrices R, L, C and G are computed by a Finite Element Method FEM [START_REF] Paul | Analysis of multiconductor transmission lines[END_REF].

∂v(x, t) ∂x = -Ri(x, t) -L ∂i(x, t) ∂t (1a) ∂i(x, t) ∂x = -Gv(x, t) -C ∂v(x, t) ∂t (1b)
Despite the fact that time domain analysis as the Finite Difference Time Domain method (ABCD) provides accurate full-wave solutions over large frequency bands, they can be computationally heavy, slow and inefficient. On the contrary, frequency domain techniques, particularly, the ABCD matrix method offers excellent fidelity and computational efficiency since they avoid the explicit use of differential equations [START_REF] Lu | An efficient method for analysis of arbitrary nonuniform transmission lines[END_REF]. An important advantage of this approach is that the transmission line modelling arises naturally in the frequency domain. Therefore the consideration of frequency dependent parameters can be carried out in a simple way compared with the time-domain.

ABCD parameters, also known as the transmission line parameters, provide the link between the supply and receiving end voltages and currents of a two-port network model. In fact, any transmission line branch can be modeled as such. The two-port network is regarded as a "black box" with its properties specified by a matrix of numbers. This allows the response of the network to signals applied to the ports to be calculated easily, without solving for all the internal voltages and currents in the network.

Since we are dealing with NUTs of tree-like structures, ABCD matrix method makes it possible to analyze such networks, thanks to its cascading property. As such, each branch composing a NUT could be separately analyzed and then cascaded with other branches splitting from it to return the overall behavior of the NUT. With this in mind, an in-house solver developed at CEA under MATLAB provided an accurate model of reflectometry responses for any branched network. Accordingly, the simulated TDR response of the NUT model is simply the inverse Fourier transform (IFFT) of the computed end voltage.

Having derived a direct model to provide the simulated TDR response of an assigned NUT, solving the inverse problem of the measured TDR response of the unknown network entails several variable sets. This includes the NUT's topology, the branch lengths and the load impedances.

B. Branched network as a Graph

Network topology is a generic name that refers to all properties arising from the structure or geometry of a network. If each element or a branch of a network is represented on a diagram by a line irrespective of the characteristics of the elements, we get a graph. Hence network topology is network geometry. Thus topology deals with the way in which the various elements are interconnected at their terminals without considering the properties and type of the elements connected. This method is considered to be a more systematic approach to the analysis of branched TL networks.

The Graph theory forms a convenient mathematical representation of a network describing the relationship between lines and points [START_REF] West | Introduction to graph theory[END_REF]. As such, a graph is a pair of sets G = (N Ed), where N is a set of vertices or nodes and Ed is a set of edges formed by pairs of nodes [START_REF] Newman | The structure and function of complex networks[END_REF]. Accordingly, a tree-liked TL network can be represented by a graph whose nodes N are loads and junctions while the edges Ed are the TL branches connecting the nodes. A hypothesized numerical model of a generic network can thus be set based on the tenets of Graph theory, whose components are to be iteratively changed to meet those of the measured network. This an inverse problem to be solved.

C. Solving the Inverse Problem

The term "inverse problem" is generally understood as the problem of finding a specific physical property, or properties, of the medium under investigation, using indirect measurements [START_REF] Tarantola | Inverse problem theory and methods for model parameter estimation[END_REF]. It can be seen as the reverse process of a forward problem, which concerns with predicting the outcome of some measurements given a complete description of a physical system. In our case study, having measured the TDR response of an unknown TL network, retrieving the network's parameters (topology, branch lengths, and load impedances) is possible by solving this inverse problem.

Optimization algorithms are central approaches in solving inverse problems as the recovery of the unknown parameters is formulated as an optimization problem [START_REF] Polak | Optimization: algorithms and consistent approximations[END_REF]. An optimization problem consists in maximizing or minimizing some function relative to some set, representing a range of choices available in a certain situation. The function allows comparison of the different choices for determining which might be best.

More formally we define the optimization problem as

optimize f (x), x ∈ S (2)
where optimize stands for min or max f : IR n → IR denotes the objective function, that we assume throughout at least continuously differentiable, and S ⊆ IR n is the feasible set, namely the set of all admissible choices for x. x represents in our investigation the set of the NUT graph's variables, namely N and Ed. To obtain the best candidate solutions that mostly align with the actual tested network, we will solve the optimization problem of the following objective function

F obj = ∞ t=0 V s (t) -V m (t) 2 1 + t 2 dt (3)
with V s (t) and V m (t) being the time domain reflectometry responses of the hypothesized simulated and measured networks, respectively. From now on-wards, the temporal variable t will be dropped for the sake of simplicity. Fig. 1 presents a mesh plot of the objective function evaluation of eq. 3 for a single point-to-point network with N being a single load impedance, while E d being the length of the sole branch. Notably, the function appears to be non-convex with several minima and maxima. Indeed, the situation is expected to worsen with complex branched networks composed of several junctions connecting numerous branches and terminated with a number of loads. To cope with such a problem, global optimization algorithms are efficient numerical techniques capable of solving inverse problems with non-convex objective functions suffering from local minima and maxima [START_REF] Weise | Global optimization algorithms-theory and application[END_REF]. In fact, they have shown promising results in converging to the function's global minimum or maximum.

Accordingly, we have adopted several global optimization algorithms in our study namely, the genetic algorithm (GA) as in [START_REF] Kafal | A non destructive reflectometry based method for the location and characterization of incipient faults in complex unknown wire networks[END_REF], [START_REF] Kafal | A joint reflectometry-optimization algorithm for mapping the topology of an unknown wire network[END_REF], [START_REF] Hassen | Power cable network topology reconstruction using multi-carrier reflectometry for fault detection and location in live smart grids[END_REF], particle swarm algorithm (PSO) as done in [START_REF] Kafal | Blind diagnosis of a blackboxed fully-loaded wiring network for configuration structuring and fault monitoring[END_REF], in addition to the surrogate (SG) and simulated annealing (SA) algorithms for the first time to such application. The purpose is to conduct a performance analysis to compare the results obtained when applying each of the considered optimization algorithms relative to several parameters as NUT's complexity, computational time, etc. In what follows we will briefly explain each of the considered algorithms.

1) Genetic algorithm: GAs are adaptive heuristic search algorithms based on the evolutionary ideas of natural selection and genetics [START_REF] Davis | Handbook of genetic algorithms[END_REF]. As such, they represent an intelligent exploitation of a random search used to solve optimization problems. GAs simulate the survival of the fittest by starting with a random sample set (initial population) of potential solutions (chromosomes). Each chromosome is coded as a finite length vector of variables which are analogous to genes. These solutions then undergo recombination and mutation (like in natural genetics), producing new children, and the process is repeated over various generations. Each individual (or candidate solution) is assigned a fitness value (based on its objective function value) and the fitter individuals are given a higher chance to mate and yield more "fitter" individuals until an eventual convergence is reached. As a result, an optimal population is produced that will now contain the optimal solutions.

2) Particle swarm algorithm: PSO is a relatively recent heuristic search approach founded on the concept of swarm intelligence (SI) that is based on the idea of collaborative behavior and swarming in biological populations [START_REF] Kennedy | Particle swarm optimization (pso)[END_REF]. As a population-based technique, PSO is regarded to be conceptually simple as only few parameters need to be regulated. The population, often referred to as swarm, is composed of n candidate solutions known as particles. Each particle i = 1, 2, 3..., n in the swarm space has an identity defined by its position p i , in addition to its moving velocity v i . In fact, the displacement of a particle in space is controlled by a well defined strategy based on its own best known position pbest i as well as the global best known position gbest i of the entire swarm. Equations 4 summarize the moving mechanism. It is important to note that, w i is the inertia weight specific to each particle, r 1 &r 2 are random numbers uniformly generated between [0, 1], while c 1 &c 2 are learning acceleration factors.

v t+1 i = w i v t i + c 1 r t 1 (pbest t i -p t i ) + c 2 r t 2 (gbest t i -p t i ) p t+1 i = p t i + v t+1 i (4)
As an illustration, the particles' convergence towards the best solution is likely determined by their fitness which is controlled by a predefined objective function F obj specific to each application. Namely, the position p i determines each particle's fitness that is updated regularly at each iteration iter of the PSO algorithm according to what has been defined in equations 4. The process is repeated until a specific criterion is reached which might be the maximum number of iterations, the stalking state time after which no improvements can be detected, etc.

3) Surrogate optimization algorithm: SG is a global solver for time-consuming objective functions [START_REF] Lange | Optimization transfer using surrogate objective functions[END_REF]. It is black-box optimization technique that is well-suited for problems whose objective functions are very expensive to evaluate with no analytical or derivative information available. The main idea of SG is to iteratively construct models to approximate the blackbox functions (globally) and use them to search for optimal solutions. A common simple-form approach for surrogatebased methods is as follows:

-Phase 1 (design): Let k := 0. Select and evaluate a set S 0 of starting points. -While some given stopping criteria are not met:

. Phase 2 (model): From the data (x, f (x))|x ⊆ S k , construct a surrogate model s k (.) that approximates the black-box function. . Phase 3 (search): Use s k (.) to search for a new point to evaluate. Evaluate the new chosen point, and update the data set S k . Assign k := k + 1. 4) Simulated annealing algorithm: SA is an optimization method which mimics the slow cooling of metals, that is characterized by a progressive reduction in the atomic movements that reduce the density of lattice defects until a lowest-energy state is reached [START_REF] Van Laarhoven | Simulated annealing[END_REF]. In a similar way, at each virtual annealing temperature, the simulated annealing algorithm generates a new potential solution (or neighbour of the current state) to the problem considered by altering the current state, according to a predefined criterion. The acceptance of the new state is then based on the satisfaction of the Metropolis criterion, and this procedure is iterated until convergence.

It has been proved that by carefully controlling the rate of cooling of the temperature, SA can find the global optimum. SA's major advantage over other methods is an ability to avoid becoming trapped in local minima. The algorithm employs a random search which not only accepts changes that decrease the objective function, but also some changes that increase it.

D. GOR method implementation

The flowchart shown in Fig. 2, illustrates the step-by-step the GOR procedure proposed to blindly reconstruct unknown networks. As can be seen, it starts by measuring the TDR response V m of the tested NUT using one extremity while others are left connected to their loads. Indeed, measuring the reflectometry response can be accomplished by connecting the testing extremity of the NUT to one of the ports of a vector network analyzer (VNA), the TDR response is simply the IFFT of the scattering parameter S 11 . However, that is also possible by relying on any of the existing reflectometry measuring devices.

Once V m is collected, solving the inverse problem commences by adopting graph theory to generate a generic network model with two sets of variables N and E d . The inhouse TL line solver described in sec. II-A is devoted to return the TDR response V s of any hypothesized NUT. N and E d are then iteratively changed, thanks to global optimization techniques, until convergence occurs between V s and V m , i.e. the minimal fitness value of F obj is reached. This marks the proper reconstruction of the tested unknown network, by retrieving its topology,branch lengths and load impedances.

III. PERFORMANCE ANALYSIS

A experimental setup based on practical industrial elements is conducted in order to serve as a profound demonstration for comparing the performance of the proposed GOR approach relative to different optimization algorithms. Three different complexity NUTs will be tested. Although, they canâ Ȃ Źt cover the entire range of possible combination of networks, but they are mostly found in practice.

A. Experimental setup

Figs. [START_REF] Smith | Analysis of spread spectrum time domain reflectometry for wire fault location[END_REF] show the three NUTs considered in our study. They are Controller Area Network (CAN) bus NUTs commonly used in aeronautics due to their reliability for data communication in mission and safety critical applications in aircrafts. The least complex structure is a single Y-junction network and the most complex is an NUT composed of 7 branches connected via two junctions. The networks are designed using RG-316 50 Ω coaxial cables. For simplicity, passive element resistors with randomly chosen impedances were created to serve as loads. In fact, this does not bring any limitation to the application of our method, as any other kind of passive loads could be considered. The testing port of each network was connected to an E5071C KEYSIGHT VNA covering a frequency range from 9.5 KHz to 4.5 GHz. Acquisition was done over a total bandwidth of 2 GHz, a frequency step 1 MHz, an intermediate-frequency filter bandwidth set to 100 kHz and an input power set to a 0-dBm harmonic excitation signal. The time domain TDR response V m is obtained by applying an IFFT to the measured frequency domain S 11 parameter.

B. Result discussion

Having acquired V m for each NUT of Figs. 3, the GOR algorithm detailed in sec. s applied. Each of the aforementioned optimization algorithms explained in sec. II-C is enforced at a time. Executing the GOR procedure was accomplished using a state-of-art PC employing an Intel 2.53 GHz CPU processor.

Regardless the optimization algorithm deployed, the proposed GOR methodology was capable of correctly returning the network's topology. However, the processing time differed from one to another, as well as the estimated branch lengths and load impedances. In order quantify the obtained results, we opted to compute ∆ L = (|(L a -Lr)/L a |) × 100 and ∆ Z = (|(Z a -Zr)/Z a |) × 100, the length and impedance % errors respectively. La and Z a are the actual NUT branch lengths and load impedances, while Lr and Z r are the reconstructed ones. T is the time needed to execute the GOR process. Fig. 4 presents a reflectogram showing the measured V m and reconstructed V s TDR responses after applying the GOR procedure implementing the GA algorithm on the single Y-junction NUT of Fig. 3 (a). Actually, the right topology was identified and precise estimates of the branch lengths and load impedances were obtained which can be noticed from the close agreement between V m and V s .

Tables I, II, III& IV display a qualitative assessment of ∆ L , ∆ Z , and T for each of the three NUTs of Figs. 3 with respect to the optimization algorithm deployed. Several features need to be commented. First of all, as already stated the right NUT topology was eventually reconstructed. Besides, it can be noticed that the length error ∆ L doesn't exceed 2.8% for the single Y-junction NUT for all adopted optimization algorithms. GA and PSO appear to outperform SG and SA algorithms with a ∆ L below 0.5%, i.e. a roughly 8 mm change estimate from the actual branch length. Although, it is expected that this error increases with an increased complexity of the network addressed, PSO does not over-top the 1% length error even with the double Y-junction 7 branch NUT, which is a remarkably great result. However, SG and SA show a deteriorated performance with ∆ L escalating to 7.5% for the NUT of Fig. 3(c).

Estimating the impedances of loads at the extremities seems to be a harder task, where results obtained show a ∆ Z reaching over 70% for the double Y-junction 7 branch network with the SA algorithm. Nevertheless, the PSO algorithm keeps an impedance error not exceeding 15%, which is quite acceptable for the reconstruction of loads.

Noteworthy, the adopted algorithms show efficiency in terms of the total duration needed for post-processing with a maximum latency below half an hour for the most complex network studied. Particularly, PSO needs no more than 3.5 minutes when testing the 7 branched network. Particularly, the vast majority of NUTs in aeronautical applications have structures that do not surpass in complexity the three considered topologies. To sum up, PSO algorithm overshoots the other considered optimization algorithms when implemented in the GOR method. It has surpassed them in terms of length and impedance errors as well as the computational complexity. GA comes in second place with good performance even with complex branched networks. However, SA and SG can only be applied for simple networks composed of no more than 4 branches but can mess-up once several junctions are addressed.

IV. CONCLUSION

In this paper we recalled the GOR method, a technique capable of blindly reconstructing branched TL networks. It is an incorporation of TDR techniques, graph theory and optimization based algorithms. Particularly, the method's ability to retrieve the tested NUT's topology with precise estimates of branch lengths and load impedances using a single testing port is an important feature for fault diagnosis of complex wiring networks.

Several optimization algorithms, namely GA, PSO, SG, and SA have been adopted to solve the inverse problem of the measured TDR response in the GOR method. The objective was to assess the performance of each in terms of computational cost and precision. An experimental setup based on real aeronautical CAN bus networks with an increasing complexity were deployed for the purpose. Results obtained have shown the ability of all algorithms to reconstruct the right topology. However, PSO outperformed other algorithms with a significant few mm error for branch lengths and several ohms for load impedances when testing a complex network composed of 7 branches interconnected by 2 junctions. More importantly was the few minutes it took to execute the whole process. In fact, this makes it well-suited for future implementation of real-time monitoring. Future work will need to deal with the applicability of the presented techniques for a complete network scanning under unstable network circumstances manifested by the presence of vibrations, noise, etc.. Besides, executing the technique while the NUT is normally operating shall be very interesting.

Fig. 1 :

 1 Fig.1:A mesh plot of the fitness function evaluation of a single branch network.

Fig. 2 :

 2 Fig. 2: Flowchart of GOR methods.

Fig. 3 :

 3 Fig. 3: Topologies of the CAN bus wire networks used for the experimental validation of the GOR method with (a): single Y-junction, (b) double Y-junction 5 branch, and (c) double Y-junction 7 branch networks.

Fig. 4 :

 4 Fig. 4: The measured and simulation-reconstructed TDR reflectometry responses of the unknown network of Fig. 3(a).

TABLE I :

 I Table showing the actual and estimated branch lengths and load impedances for the NUT of Fig. 3 (a) with the computing time.

						Double Y-Junction 5-Branch NUT
	Algo.	L 1 (3 m)	L 2 (2.5 m)	L 3 (3.5 m)	L 4 (2.75 m)	L 5 (1 m)	Z 1 (100 Ω)	Z 2 (70 Ω)	Z 3 (15 Ω)	T
	GA	3.006	0.2%	2.491	0.36%	3.485 0.42%	2.759	0.32%	0.992	0.8%	110	10%	82	17%	18	20%	2.5 min
	PSO	2.998	0.06%	2.505	0.2%	3.488 0.34%	2.748	0.07%	1.002	0.2%	105	5%	76 8.5%	16	6.6%	1.5 min
	SG	2.992	0.26%	2.483	0.68%	3.530 0.85%	2.760	0.36%	1.019	1.9%	122	22%	84	20%	10	33.3%	4 min
	SA	3.098	3.2%	2.515	0.6%	3.600 2.85%	2.685	2.36%	0.958	4.2%	75	25%	40	30%	24	60%	7.5 min

TABLE II :

 II Table showing the actual and estimated branch lengths and load impedances for the NUT of Fig. 3 (b) with the computing time.

						Double Y-Junction 7-Branch NUT
	Algo.	L 1 (3 m)	L 2 (2.5 m)	L 3 (1 m)	L 4 (3.5 m)	L 5 (2.75 m)	L 6 (3.65 m)	L 7 (1.75m)
	GA	3.009	0.3%	2.488	0.48%	0.987	1.3%	3.455	1.28%	2.725	0.9%	3.69	1.1%	1.79	2.28%
	PSO	3.005	0.16%	2.511	0.44%	1.009	0.9%	3.532	0.91%	2.765	0.54%	3.635	0.4%	1.662	0.72%
	SG	3.090	3%	2.475	1%	1.040	4%	3.430	2%	2.653	3.5%	3.496	4.2%	1.687	3.6%
	SA	2.88	4%	2.437	2.5%	0.94	6%	3.307	5.5%	2.598	6.5%	3.387	7.2%	1.618	7.5%

TABLE III :

 III Table showing the actual and reconstructed branch lengths for the network of Fig. 3 (c).

					Double Y-Junction 7-Branch NUT
	Algo.	Z 1 (100 Ω) Z 2 (30 Ω)	Z 3 (70 Ω)	Z 4 (15 Ω)	Z 5 (150 Ω)	T
	GA	115	15%	24	20%	58.8	16%	19	26.6%	180	20%	6 min
	PSO	109	9%	33	10%	69	12.8%	13	13.3%	172	8%	3.5 min
	SG	121	21%	42	40%	52	25.7%	25	66.6%	110	26.6%	11.8 min
	SA	128	28%	15	50%	96	37.1%	4	73.3%	98	34.6%	21.5 min

TABLE IV :

 IV Tableshowingthe actual and reconstructed load impedances for the network of Fig.3 (c) with the computational latency.


Nazim Haouchine

Pariskhit Juvekar

Alexandra Golby

Sarah Frisken

COMPUTER METHODS IN BIOMECHANICS AND BIOMEDICAL ENGI-NEERING: IMAGING AND VISUALIZATION Predicted Microscopic Cortical Brain Images for Optimal Craniotomy Positioning and Visualization

Keywords: Image-guided Neurosurgery, Physics-based Simulation, Image Analogy, Computer-aided Interventions, Visualization

During a craniotomy, the skull is opened to allow surgeons to have access to the brain and perform the procedure. The position and size of this opening are chosen in a way to avoid critical structures, such as vessels, and facilitate the access to tumors. Planning the operation is done based on pre-operative images and does not account for intra-operative surgical events. We present a novel image-guided neurosurgical system to optimize the craniotomy opening. Using physics-based modeling we define a cortical deformation map that estimates the displacement field at candidate craniotomy locations. This deformation map is coupled with an image analogy algorithm that produces realistic synthetic images that can be used to predict both the geometry and the appearance of the brain surface before opening the skull. These images account for cortical vessel deformations that may occur after opening the skull and is rendered in a way that increases the surgeon's understanding and assimilation. Our method was tested retrospectively on patients data showing good results and demonstrating the feasibility of practical use of our system.

Introduction and Background

A craniotomy is the surgical removal of part of the bone from the skull to expose the brain, for example to provide access for tumor resection. Surgeons often use well-established image-guidance systems where a patient's head is registered with a pre-operative MRI scan [START_REF] Fraser | Brainlab image guided system[END_REF], [START_REF] Bucholz | The history, current status, and future of the stealthstation treatment guidance system[END_REF]) to plan the location and size of the craniotomy before beginning surgery. Those systems help surgeons navigate to prepare the patient and locate the tumor. Using the registered pre-operative MRI scans, the surgeons draw a target on the patient's skin (see Figure 1-d), then opens the skin and cuts the bone to open the skull. The target size and location is chosen to provide optimal access to the tumor while avoiding vessels and other critical structures.. However, several factors, including opening the skull, head position, changes in osmotic pressure and loss of cerebral spinal fluid, can cause the brain to shift upon opening. Thus the planned craniotomy may not provide optimal nhaouchine@bwh.harvard.edu or adequate exposure, increasing patient risk and surgical complexity.

Related Work: A large amount of work has been dedicated to understanding and compensating for intra-operative brain shift using various types of intra-operative imaging techniques [START_REF] Morin | Brain-shift compensation using intraoperative ultrasound and constraint-based biomechanical simulation[END_REF], [START_REF] Bayer | Intraoperative imaging modalities and compensation for brain shift in tumor resection surgery[END_REF], [START_REF] Miga | Clinical evaluation of a model-updated image-guidance approach to brain shift compensation: experience in 16 cases[END_REF], [START_REF] Sun | Near real-time computer assisted surgery for brain shift correction using biomechanical models[END_REF], [START_REF] Kuhnt | Brain shift compensation and neurosurgical image fusion using intraoperative mri: Current status and future challenges[END_REF] [START_REF] Reinertsen | Intra-operative correction of brain-shift[END_REF] [START_REF] Ji | Mutual-information-based image to patient re-registration using intraoperative ultrasound in image-guided neurosurgery[END_REF] [START_REF] Rivaz | Deformable registration of preoperative mr, pre-resection ultrasound, and post-resection ultrasound images of neurosurgery[END_REF]). The objective of these methods is to compensate for brain shift by updating the pre-operative scans using intra-operative data after dura-opening. Several planning systems have been proposed to anticipate brain shift based on brain anatomy, head positioning, craniotomy size, and other surgical variables [START_REF] Miga | Computational modeling for enhancing soft tissue image guided surgery: An application in neurosurgery[END_REF]. In the context of trajectory planning for Deep Brain Stimulation, [START_REF] Essert | Automatic computation of electrode trajectories for deep brain stimulation: A hybrid symbolic and numerical approach[END_REF] proposed a geometric method based on a database of brain shift cases to build a template of possible defomations. [START_REF] Bilger | Brain-shift aware risk map for deep brain stim-9 ulation planning[END_REF] proposed a method to estimate a brain shift risk map using a simulation that gathers statistics on the displacement of anatomical landmarks from different clinical studies. This risk map can be visualized pre-operatively using a color-coded scheme based on vessels proximity. This method was later improved by [START_REF] Hamzé | Anticipation of brain shift in deep brain stimulation automatic planning[END_REF] using more advanced models.

In contrast to estimating brain deformation for pre-operative planning or intraoperative guidance, using brain shift to optimize the location and size of the craniotomy is a little studied problem. Optimizing the craniotomy has been addressed in retrospective studies for evaluating insertion trajectory accuracy [START_REF] Chen | Optimal entry point and trajectory for endoscopic third ventriculostomy: evaluation of 53 patients with volumetric imaging guidance[END_REF]) and burr hole placement [START_REF] Rai | Optimizing burr hole placement for craniotomy: A technical note[END_REF]). Although focused on burr holes, these studies, undertaken with more than 50 patients, highlight the importance of choosing the optimal entry point and size.

Motivation and Contribution: Recently, surgeons tend to favor smaller craniotomies to minimize patient exposure. However, accessing tumors while avoiding blood vessels, sulcal folds and other critical structures are the main goal for when choosing the craniotomy position and size. We propose a unique system for optimizing craniotomy opening placement and size. Because it is very difficult (if not impossible) to accurately estimate patient-specific brain shift pre-operatively [START_REF] Frisken | A comparison of thin-plate spline deformation and finite element modeling to compensate for brain shift during tumor resection[END_REF]), we introduce a cortical brain deformation map that estimates possible brain deformation. This maps considers the location, the patient's head position w.r.t gravity and a user-defined deformation amplitude. For each candidate, a miscrocopic image is generated that synthesizes brain surface appearance using an advanced image analogy technique. To the best of our knowledge, no similar methods have been proposed.

Method

Problem Formulation and Approach overview

Our approach, illustrated in Figure 1, involves a composition function Θ that predicts brain surface deformation and appearance before skull opening at chosen head positions.

Let M S,P,V be the 3D surface geometry of the brain accounting for the skull, the parenchyma and the vessels (denoted by their respective subscript) derived from preopertative MRI scans, and let P be the 3D representation of the actual patient's head in the operating room. We assume that P and M S can be registered before starting the procedure. This registration can be done with well-established imageguided neurosurgical systems [START_REF] Fraser | Brainlab image guided system[END_REF], [START_REF] Bucholz | The history, current status, and future of the stealthstation treatment guidance system[END_REF]) Hung [START_REF] Hsieh | A kinect-based medical augmented reality system for craniofacial applications using image-to-patient registration[END_REF] and is outside of the scope of our work. Using this registration, surgeons can chose a candidate opening position p c and size r c of the craniotomy opening (see Figure 1-d). Our system provide the surgeon with an intuitive tool to chose the best candidate {p c , r c }.

The composition Θ aims at predicting an image I that accounts for possible brain deformation while providing a visually understandable output. The deformation is representedd as a displacement field computed using the function D. D is computed from pre-defined brain physical properties (gravity, brain elasticity and viscosity), the position of the craniotomy p c , a user-defined deformation parameter γ and the preoperative brain surface M S,P,V . D can be used to transform the deformation from 3D space into an in-plane stress map in 2D space. This projection produces an annotated image that draws the boundaries of the different structures of a cortical brain surface, namely the parenchyma, the vessels and the skull. Using an the analog image pair (J , J label ) (see Figures 3-a and3-b), chosen randomly from a pre-defined database of microscope images of cortical surfaces, the labeled regions are composited, pixel-perpixel, to generate a the final image I. The composition function as

I = Θ analogy D(M P,V , p, γ), J , J label , (1)
A new image I is predicted for each candidate {p c , r c } to allow surgeons to chose the optimal one. The composition function Θ is a parametric function that takes into account intra-operative events, i.e.: patient's head position M S , the amount of deformation γ.

FEM-based Brain Shift Model

Initial brain shift is caused by several factors, including cerebro-spinal fluid (CSF) loss and gravitational positioning [START_REF] Elias | Cortical and subcortical brain shift during stereotactic procedures[END_REF]). The amount of CSF loss is hard to anticipate, even with sophisticated models [START_REF] Hamzé | Anticipation of brain shift in deep brain stimulation automatic planning[END_REF]). The most accurate ways to compensate for brain shift use intra-operative imaging after skull opening [START_REF] Luo | An integrated multi-physics finite element modeling framework for deep brain stimulation: Preliminary study on impact of brain shift on neuronal pathways[END_REF]). However, in our case such information cannot be used since we aim to estimate brain deformation before opening the skull. Instead we rely on a parametric physics-based modelling to predict the geometry of the cortical surface subject to brain shift.

In our simulation we use a non-linear geometric finite element model with a linear constitutive law [START_REF] Felippa | A unified formulation of small-strain corotational finite elements: I. theory[END_REF]) where the volume of the brain parenchyma is meshed as a set of hexahedral elements. Following the work from [START_REF] Bilger | Biomechanical simulation of electrode migration for deep brain stimulation[END_REF], we model the pressure created by the CSF on the brain as external forces applied on the surface of the parenchyma M P . These external forces are integrated into the global brain motion formulation following:

Ku Brain stiffness = M P dgh(m)∂M P CSF loss pressure + H T λ Skull contact + g Gravity (2)
where d is the density of CSF (≈ 1007 kg/m 3 ), g is the norm of gravity and h is the distance between a point m on the surface and the fluid level. This force is computed on each element of the brain mesh that corresponds to the immersed surface. The stiffness matrix K encodes the elasticity of the parenchyma and is built following textbook parameters [START_REF] Elias | Cortical and subcortical brain shift during stereotactic procedures[END_REF]), g is the gravity force while H T λ gathers the contacts between the brain and the inner part of the skull. The matrix H contains the known constraints directions and is unknown and has to be computed. λ are Lagrange multipliers containing the constraint force intensities. A linear complementary system is obtained, and is solved using a Gauss-Seidel algorithm [START_REF] Cotin | New approaches to catheter navigation for interventional radiology simulation[END_REF]).

Equation 2 the computation of brain deformations, which consists of updating the positions vector u, based on the position of the head w.r.t gravity and the amount of CSF loss. While the relative head position can be deduced from the registration step, the CSF loss quantity is unpredictable. We propose to estimate brain shift based on a model of maximal shift (which represents the worst scenario). The amount of CSF loss can be manually adjusted by surgeons in a spectrum of values introduced by [START_REF] Elias | Cortical and subcortical brain shift during stereotactic procedures[END_REF] that actually depict the leaked volume. For simplicity, this parameter, which we denote γ, can take values between 0% and 100%, where 0% means no brain shift and 100% means half the CSF has leaked out.

Cortical Deformation Map

The deformation map D aims at updating the geometry of the cortical surface M at a selected position p c w.r.t to the CSF amount γ. This step consists of creating an in-plane displacement map (in 2D) from the volumetric deformation (in 3D) estimated from equation 2. This consists of projecting the surface displacement δM (P,V) that is linearly mapped to the displacement field δu computed from equation 2. This projection is done following a projection matrix Π that simulate the surgical microscope camera. Its intrinsic parameters are defined according to pre-defined focal length f cam and image size w × h, while its position is set to be at a distance d cam from the candidate position. These parameters values are taken from a textbook and do not account for lens distortions.

D(M

(P,V) , p c , γ) = Np i=1 Π • T (M P,V (i), δu γ ) (3)
where M P,V (i) corresponds to the i th triangle of either the parenchyma or the vessels surface around the entry point p c , with i ∈ N pc ; T is a linear mapping function that maps the surface M P,V to the volume u following their barycentric coordinates; and δu γ is the displacement field computed from Eq. 2 with an amount γ of CSF loss. The opening size r c is not included in the computation of the displacement field and does not have a physical impact. In practice, the function D will produce an image of size w × h that encodes the displacement field around an entry point. An example of the output stress map for different regions of the brain is illustrated in Figure 2.

Sub-cortical Deformation

In order to propagate the surface deformation to tumors and other sub-cortical structures, we use a linear geometrical barycentric mapping function. We restrict the impact of the cortical vessel deformations to the immediate underlying structures. Formally speaking, if we denote the vector of vertices representing a 3D tumor by M T , we can express each vertex M T (i) using barycentric coordinates of facet vertices u, such that

M T (i) = 3 j=1 φ j (x i , y i , z i )u j (4)
where φ(x, y, z) = a + bx + cy with (a, b, c) being the barycentric coordinates of the triangle composed of nodal points u j , with 1 ≤ j ≤ 3. This mapping is computed at rest and remains valid during the deformation.

Microscopic Image Synthesis via Analogy

Synthesizing the final image I using analogy requires to have three input images: a source image J , its corresponding labeled image J label and a labeled target image I label . The labeled images represent a semantic annotation of the brain surface seen through a microscope. They are annotated with three classes: parenchyma, vessels and the skull. J label is annotated manually while I label is annotated automatically from the output image of the deformation map D, where J label (j) = {0, 1, 2} if the j th pixel belongs to the background, the parenchyma M P or the vessels M V respectively. The opening size r c is defined by the surgeon and permits the delimitation of the background, and can take the form a circle or an ellipsoid. We used the patch-based image analogy technique proposed by [START_REF] Li | Combining markov random fields and convolutional neural networks for image synthesis[END_REF]. This technique relies on convolutional neural networks to transfer a texture from J to I constrained by their semantic labels J label and I label respectively. This method is inspired by the former work on neural style transfer introduced in [START_REF] Gatys | Image style transfer using convolutional neural networks[END_REF] where an equilibrium between a content error and a style error is optimized. Because we are only interested in transferring the source style without keeping the target content, the optimization scheme (describe in details by [START_REF] Li | Combining markov random fields and convolutional neural networks for image synthesis[END_REF]) is reduced to minimize the style error solely. A example is illustrated in Figure 3 3. Results

We tested our method retrospectively on 4 patients dataset. These consisted of T1 contrasted MRI scans and microscopic images of the actual craniotomy. The cortical vessels, the parenchyma and the skull were segmented using 3D Slicer (Kikinis et al. ( 2014)) (see first column of Fig. 4). The brain parenchyma was meshed using CGal (The CGAL Project (2020)) in order to obtain a hexahedral volume of 9400 elements. We used the framework Sofa [START_REF] Faure | Sofa: A multi-model framework for interactive physical simulation[END_REF]) to simulate the deformations. Brain stiffness was set to 12000 Pa. The virtual camera was set with a focal f cam = 500 at a distance d cam = 25 cm of the brain surface. We first tested our method on 3 cases to obtain a predicted output image. For each case we used a different amount of CSF loss γ with the values 55%, 40% and 15% for case 1, case 2, and case 3 respectively. We also used and a different style image J for each case. Qualitative results are illustrated in We further tested our method on case 4 with a maximal brain shift (γ = 95%). In this particular case the patient had previously undergone a carniotomy, so an estimate of the opening was possible from the pre-operative MRI scans. Using this opening, we generated an expected image that represents the position of the vessels without any brain shift w.r.t the segmented opening. We used our method with a maximal brain shift prediction and measured an average of 5.62 mm difference between the expected and predicted image. This error is used to rectify the opening position on patient's skin and well as it's size. Figure 5 gives an example of how our tool could be used to plan an optimal craniotomy (case 4 ). Surgeons could move the proposed craniotomy location around on the surface of the head and adjust its size while visualizing the predicted microscope view through the proposed craniotomy.

Discussion

Usability in the Opertating Room: In current clinical practice, neurosurgeons use registration software (e.g., BrainLab Fraser et al. (2009), Medtronic [START_REF] Bucholz | The history, current status, and future of the stealthstation treatment guidance system[END_REF]) to register preoperative MRI to the patient before performing the craniotomy. With the help of an optical pointer, surgeons can then select a point on the patient's head (shaved) and visualize the point in the preoperative images. The deformation model is a "maximal brain shift model" that takes the worst case scenario to build the stress map. This parameter can also be adjusted by the surgeon, but a maximal value will ensure the optimal exposure. Our method would simply extend the current practice by displaying a predicted synthetic microscopic image of the exposed brain with an optimized craniotomy opening at the selected point on the head. Our solution can thus easily be integrated into current clinical practice and can alse serve to position not only the craniotomy but also patient's head.

Deep Brain Shift: Although brain shift impacts underlying structures, the goal of our solution is to plan the optimal craniotomy given a maximal expected shift of the cortical surface (see Figure 5). While brain shift at the depth of the tumor is important for ensuring more complete resections, shift at the surface at the beginning of surgery impacts "access" to the tumor; if the brain has shifted and the craniotomy is too small or badly placed, the neurosurgeon may not have safe access to the tumor due the presence of cortical blood vessels or proximity to functional cortex. Our method integrates a rigid-to-deformable mapping (See Section 2.4) that permits to propagate cortical brain shift to underlying structures making it suitable for both cortical and sub-cortical deformation.

Visualization: We proposed a neural style transfer method that can transfer 3 regions of a typical craniotomy, the parenchyma, the vessels and the background. While these 3 labels are enough, one can add the brain sulci as an additional label that can help surgeon's correpond MRI scans with the synthetize image. Technically speaking, this amounts to update the label image J label so that it accounts for an additional label that depicts the sulcis and segment the brain folds from the MRI scans.

Conclusion

We have addressed the little studied problem of optimizing a craniotomy opening for tumor resection and proposed a novel and versatile solution. We have introduced a parametric, physics-based deformation map to predict possible brain shift based on the amount of CSF loss and the gravitational head position, and used image generation to predict the view of the craniotomy that the surgeon will see through the microscope. Surgeons can use this approach to adjust the planned craniotomy based on predicted brain deformation images. Our retrospective experiments on patients data show good results in estimating brain deformation as well as predicting cortical microscopic images. Although our method does not provide a solution to compensation for brain shift, we strongly believe that our interactive tool can help surgeons in reducing patients' brain exposure without disrupting the actual clinical routines.

Future work will integrates our tool into an end-to-end system capable of performing the pre-to intra-operative registration. This integration will permit us to include registration errors in the estimation of the deformation map since those errors can be as significant as the actual brain shift [START_REF] Frisken | A comparison of thin-plate spline deformation and finite element modeling to compensate for brain shift during tumor resection[END_REF]. In addition we plan to test our method on more date and to test it clinically to measure surgeons' feedback.

Figure 1 .

 1 Figure 1. Components of our approach: (a) intra-operativelly, surgeons chose a candidate opening position pc on patient's head P; the point is represented by a green circle (b) a pre-operative model M S,P,V is built from MRI scans. The chosen opening position is located on the pre-operative model after a rigid registration; (c) a microscopic image I is synthesized before opening the skull , taking into account possible brain deformations via function D. The output displacement field is represented with arrows; (d) Surgeons can optimize the craniotomy opening position pc and size rc from predicted images in (c) before starting the procedure. Our method can be plugged to the actual method (framed in pink) already used in the opertatin room.

Figure 2 .

 2 Figure 2. Output of the cortical brain deformation map: an in-plane deformation map is computed depending on the position of the opening position pc, the amount of CSF loss γ and head gravitational positioning.

Figure 3 .

 3 Figure 3. Image analogy: given a source image J in (a) and its annotated images J label in (b) we want to synthesize a target image J in (d) following its annotation image I label in (c). Yellow represents the background, red the vessels and green represents the parenchyma.

Figure 4 .

 4 Figure 4. Retrospective results on 4 patients. First column: pre-operative MRI scans with the region of interest framed in red around the cortical vessels. Second column: The output of the cortical deformation map is in the bottom right corner. Third column: Predicted microscopic image with random style transfer. Fourth column: ground truth microscopic image acquired intra-operatively. Row 1, row 2, row 3 and row 4 correspond to case 1, case 2, case 3 and case 4 respectively.

Figure 4 .

 4 Figure4. We measured the dice coefficient between the generated image and the actual image with the values 85%, 77% and 92% for case 1, case 2 and case 3 respectively.We further tested our method on case 4 with a maximal brain shift (γ = 95%). In this particular case the patient had previously undergone a carniotomy, so an estimate of the opening was possible from the pre-operative MRI scans. Using this opening, we generated an expected image that represents the position of the vessels without any brain shift w.r.t the segmented opening. We used our method with a maximal brain shift prediction and measured an average of 5.62 mm difference between the expected and predicted image. This error is used to rectify the opening position on patient's

Figure 5 .

 5 Figure 5. Rectification of a craniotomy opening (case 4). From the pre-operative planing, the surgeon expects to see (a), the predicting output with brain shift permits to visualize (b), in order to obtain (c) surgeon can update the position and radius of the opening following the rectified target (d). The actual craniotomy view is shown in (d). The underlying tumor is represented by blue dashed lines.

Table 1 .

 1 Quantitative measurements on 4 patients.

		Case 1	Case 2	Case 3	Case 4
	CSF Loss Amount (%)	55	40	15	95
	Avg. Cortical Shift (mm)	3.21	2.32	1.23	5.62
	Dice Coefficient (%)	85	77	92	81

Acknowledgement(s)

This work was supported by the Brigham and Women's Hospital [Research Pilot grant]; NIH [R01 EB027134-01,R01 NS049251].


Francis Laniel

Damien Carver

Julien Sopena

Franck Wajsburt

Jonathan Lejeune

Marc Shapiro

MemOpLight: Leveraging application feedback to improve container memory consolidation

Keywords: Linux, container, memory, memory consolidation

The container mechanism amortizes costs by consolidating several servers onto the same machine, while keeping them mutually isolated. Specifically, to ensure performance isolation, Linux relies on memory limits. These limits are static, despite the fact that application needs are dynamic; this results in poor performance. To solve this issue, MemOpLight uses dynamic application feedback to rebalance physical memory allocation between containers focusing on under-performing ones. This paper presents the issues, explains the design of MemOpLight, and validates it experimentally. Our approach increases total satisfaction by 13% compared to the default.

I. INTRODUCTION

A cloud provider is allowed to consolidate the logical servers of different clients on the same underlying machine, thus amortizing cost [START_REF] Xing | Virtualization and Cloud Computing[END_REF]. Each client has the responsibility to correctly size the virtual resources that they rent in order to ensure that they execute smoothly [START_REF] Amazon | Amazon Compute Service Level Agreement[END_REF], [START_REF]SLA summary for Azure services[END_REF], [START_REF] Ovh | CONDITIONS PARTICULIÈRES DU SERVICE OVH PUBLIC CLOUD[END_REF]. However, there is a trade-off. The execution of one logical server should not disturb the others: the logical servers should remain isolated from one another. In self-managed clouds, the goal is to maximize, on any single machine, the number of applications that respect their SLO (Service Level Objectives) with the minimal amount of hardware.

To ensure both consolidation and isolation, a common approach is to use Virtual Machines (VM). Unfortunately, a VM is heavyweight and waste resources. Resource transfer between VM is complex and difficult to automate [START_REF] Kvm | Automatic Ballooning[END_REF], [START_REF] Mammedov | Features/CPUHotplug[END_REF]. A recent alternative is the "container", a group of processes with sharing and isolation properties [START_REF] Amazon | Amazon Elastic Container Service[END_REF], [START_REF]Microsoft Web App for Containers[END_REF], [START_REF] Alibaba | Alibaba Container Service[END_REF], [START_REF] Ovh | OVH Kubernetes[END_REF]. Containers support security (e.g., a file in one container cannot be accessed by another), ease of deployment (e.g., it is possible to start a container with a simple shell command) and fine-grain resource control (e.g., a container can be pinned to a specific CPU core) [START_REF] Inc | What is a Container?[END_REF].

To ensure memory performance isolation, i.e., guaranteeing to each container enough memory for it to perform well, the administrator limits the total amount of physical memory that the container's processes can use. If it exceeds its limits, some of its memory will be reclaimed, making it available to others. Notably, the Linux kernel reclaims pages from the file page cache, resulting in a performance decrease in containers that perform I/O [START_REF]The kernel development community[END_REF].

In previous work, we showed that the memory consolidation provided by the limit mechanism is imperfect [START_REF] Laniel | Highlighting the Container Memory Consolidation Problems in Linux[END_REF].

Moreover, the limits size are static, and do not adapt to the containers' dynamic behavior. This is a problem, because it is hard to estimate, a priori, the required amount of memory satisfying an application's performance objectives [START_REF] Gregg | Working Set Size Estimation[END_REF], [START_REF] Nitu | Working Set Size Estimation Techniques in Virtualized Environments: One Size Does not Fit All[END_REF]. Furthermore, the metrics available to the kernel to evaluate its policies (e.g., frequency of page faults, I/O requests, use of CPU cycles, etc.) are not directly relevant to performance. Indeed, the application performance is better characterized by application-level metrics, such as response time or throughput [START_REF] Weiner | PSI -Pressure Stall Information[END_REF].

To solve these problems, we propose a new approach, called the Memory Optimization Light1 (MemOpLight). It is based on application-level feedback from containers. Our mechanism aims to rebalance memory allocation in favor of unsatisfied containers, while not penalizing the satisfied ones. As a side effect, this improves overall resource consumption while consolidating memory. MemOpLight is intended to be used by cloud providers, to make better use of the underlying infrastructure, while guaranteeing good performance to client tasks. The memory of containers receiving low load can be reclaimed, in order to improve performance of these receiving high ones. Our experiments show that MemOpLight increases throughput up to 29.2% compared to the default for the sysbench benchmark accessing a mysql database.

Our main contributions are the following: (i) The design of a simple feedback mechanism, from application to kernel. (ii) An algorithm for adapting container memory allocation. (iii) An implementation in Linux and its experimental evaluation. We organize the remainder of our paper as follows. Section II presents some technical background. Section III summarizes the issues with existing Linux mechanisms. Section IV presents MemOpLight. Section V compares its performance with existing Linux mechanisms. In Section VI, we review related work. Finally, we conclude and discuss future work in Section VII.

II. TECHNICAL BACKGROUND

Containers are based on the Linux cgroup structure for grouping a number of processes [START_REF] Hiroyu | Cgroup And Memory Resource Controller[END_REF], [START_REF] Rosen | Namespace and cgroups, the basis of Linux containers[END_REF], [START_REF]Memory Resource Controller[END_REF], [START_REF] Zhuang | Taming memory related performance pitfalls in linux Cgroups[END_REF]. A cgroup limits the collective resource usage of its processes. Particularly, the total amount of physical memory used across all the processes of a cgroup is capped by the max and soft limits, which we describe later. In the rest of this section, we study how Linux manages the memory of containers under memory pressure, i.e. when free physical memory is scarce.

A. No limits

When memory pressure occurs, and if the max and the soft limits are not set, memory is reclaimed from all containers. For instance, if the memory requirements of some container decreases, the kernel reallocates unused memory to another container. This constitutes memory consolidation. Unfortunately, as Linux allocates unused memory to the file cache, it does not enforce memory performance isolation [START_REF]The kernel development community[END_REF]. Therefore, I/O of one container can impede another container's performance without increasing the performance of the former. In summary, when no limits are set, memory consolidation occurs, at the expense of memory performance isolation.

B. The max and soft limit mechanism

To solve this problem, Linux provides the max and the soft limits to guide the memory reclamation of containers. By default, these limits are unset; it is up to the user to set them through sysfs. A container's memory footprint cannot exceed its max limit. Even if there are free pages, the kernel will not allocate them to a container that has reached its max limit. If a process needs physical memory, and its container has already reached its max limit, the kernel may reallocate memory from another process of the same container, but not from another container. This mechanism ensures isolation, by avoiding that some container would starve the others.

The soft limit is similar, except that it is active only when there is memory pressure. A container's allocation may occasionally exceed its soft limit if there is free physical memory. To guarantee good performance under memory pressure, the administrator should set the soft limit to approximate the container's Working Set (WS) size [START_REF] Denning | The working set model for program behavior[END_REF]. Unfortunately, it is hard to estimate WS size [START_REF] Gregg | Working Set Size Estimation[END_REF], [START_REF] Nitu | Working Set Size Estimation Techniques in Virtualized Environments: One Size Does not Fit All[END_REF].

To summarize, container memory footprint is limited by the soft limit when memory pressure occurs, and by its max limit at all times. However, these settings are not dynamically related to the containers' current memory needs; they may be higher (impeding memory consolidation) or lower (impeding memory performance isolation).

III. MEMORY CONSOLIDATION VS. MEMORY PERFORMANCE ISOLATION

In this Section, we recapitulate our previous experiment showing that containers do not ensure memory performance isolation and memory consolidation at the same time [START_REF] Laniel | Highlighting the Container Memory Consolidation Problems in Linux[END_REF].

To highlight this problem, we stressed a mysql database, widely used in industry, with a dynamic load generated by sysbench, an OLTP benchmark well-known in research [22], [START_REF] Kopytov | sysbench[END_REF]. We first run a reference experiment with a single container, to establish a baseline for the ideal performance and resource consumption of the application. Then, we run the same experiment with two containers using different limits configurations. We compared their performance and resource consumption to the baseline. The containers' memory needs fluctuated over time due to variation in received load. When the limits are not set, memory consolidation occurs, but imperfectly and there is no memory performance isolation. The max limit ensures memory performance isolation, but thwarts memory consolidation. The soft limit is similar under memory pressure, but allows memory consolidation when memory abounds. We conclude from this experiment that existing mechanisms are insufficient as they do not ensure memory consolidation and memory performance isolation. Table I summarizes these results.

Furthermore, the max and soft limit are static and thus cannot adapt to dynamic behaviors, especially when the application has a low level of activity, as opposed to being completely stopped [START_REF] Barroso | The Datacenter as a Computer: An Introduction to the Design of Warehouse-Scale Machines, Second edition[END_REF], [START_REF] Barroso | The Case for Energy-Proportional Computing[END_REF], [START_REF] Meisner | PowerNap: eliminating server idle power[END_REF], [START_REF] Liu | A Measurement Study of Server Utilization in Public Clouds[END_REF].

IV. MEMORY OPTIMIZATION LIGHT (MEMOPLIGHT) A. MemOpLight's functioning

It is difficult to do better with the static limits and the limited information available to the kernel. The kernel only has access to low-level metrics such as the CPU cycles used or the I/O bandwidth. Theses are, at best, proxies for application-level Quality of Service (QoS), and are not representative of the needs of modern applications.

Instead, we propose to base memory reclamation on performance metrics perceived by the application. The container itself declares its current level of QoS, according to its own, application-specific metrics (e.g. latency for a web server, frame rate for a streaming application, etc.), compared to some performance objectives. We associate a traffic light color to different states of performance:

• GREEN: The container has reached its maximum level and would not benefit from more resources. For instance, a web server has no requests waiting. • YELLOW: The container is satisfied with its QoS, but it would do better with more resources. For example, a web server has pending requests in a queue but has answered the earlier with sufficiently low response time.

• RED: The container is not satisfied, e.g. a web server is not able to answer requests under a certain latency. Initially a container starts in the RED state.

Our approach is based on three components. a) User-kernel communication: We develop a communication mechanism between user and kernel, so a container can communicate its state of performance to the kernel. The Linux kernel provides multiple mechanism for this purpose (e.g., syscall, ioctl, sysfs, socket, etc.). We choose the sysfs because it is less intrusive for the kernel and has a file-oriented API which is easy to use by users. b) Probe: A container is equipped with an application probe, which indicates its color, based on some applicationspecific. The probe could either exploit existing information in the application, or be a separate script that collects information about the application. For mysql, we developed a script that reads the database log and analyzes the request latency. In our prototype, the probe compares the transaction latency of mysql, which executes inside the container, to some SLO and informs Linux through sysfs every second. Specifically, a container with high throughput declares itself green if its throughput equals the SLO and has no transactions waiting. With low throughput, it is green if it handles ≈ 200 t/s. If it cannot respect its SLO, it is red. Otherwise, if it has transactions waiting, it is yellow. c) MemOpLight: Our third component is an algorithm that executes when memory is scarce. MemOpLight extends the Linux Page Frame Reclaim Algorithm (PFRA) [START_REF] Bovet | Understanding the Linux kernel: from I/O ports to process management[END_REF]. When a container needs memory, it takes it from the free physical pages. The PFRA activates when a memory threshold is reached, i.e. when free physical memory becomes scarce. It aims to reclaim memory and bring the free physical memory above the threshold. Regarding containers, the PFRA has two parts. The first one consists in recycling memory from one container (local reclaim) while the other reclaims memory from all containers (global reclaim). MemOpLight modifies the PFRA behavior and reclaims memory from containers based on their colors, there are multiple cases shown in Table II.

We make two design decisions. The first is to reclaim from both green and yellow containers when there is a red one. By doing so, we hope to maximize the number of satisfied containers quickly. The other is to limit the rate of reclamation to a small fraction of each container's footprint (we chose 2% each second) in order to avoid performance oscillations. Indeed, if a container declares itself as green or yellow, this must mean that its WS fits into its current physical memory allocation.

This mechanism tends to adapt the amount of memory to what is required for each container to be satisfied. Memory reclaimed from one container can be used by other containers to improve their own performance and satisfaction.

Other, more detailed, technical decisions are documented by comments in the code itself. We implemented as a modification of Linux code to invoke the MemOpLight algorithm once per second when there is memory pressure. If MemOpLight fails to reclaim memory, the soft limit mechanism activates and so the PFRA. Our modifications amount to ≈ 400 lines of code [START_REF] Laniel | Thesis_linux[END_REF].

B. Probes

The probe can be seen as a MAPE loop which takes places in user space while our modifications to the Linux kernel correspond to another loop which executes in kernel space [START_REF] Kephart | The vision of autonomic computing[END_REF]. In more detail, the probe does three different things:

1) It collects information about the application.

2) It compares this to a SLO, which was provided by container's owner at its startup, to evaluate its performance state. 3) Finally, it communicates the application's performance state as the green, yellow or red colour to the Linux kernel. For a web server, a probe might simply read the response time from the server's log and compare it to the SLO. If the response time is higher, then the web server performance is declared to be RED, otherwise GREEN. Another simple example is a streaming application: in this case using all three colours is appropriate. If streaming application sustains the SLO frame rate with high video quality, its state of performance is GREEN. If it has to degrade video quality to sustain the SLO, its declares its state as YELLOW. Otherwise, i.e. if it cannot respect its SLO, its performance is declared RED. There is a trade-off between precision (which is important in cloud environment where clients are charged for the memory they use) and the overhead of communicating the colour frequently [START_REF] Amazon | Amazon EC2 Pricing[END_REF], [START_REF] Google | VM instances pricing[END_REF].

V. EVALUATION A. Description of the experiment

The goal of our experiment is to show that MemOpLight ensures both memory performance isolation and memory consolidation as opposed to existing Linux kernel mechanisms [START_REF] Laniel | Thesis_experiments[END_REF].

1) Metrics and baseline: Our experiment studies three metrics: throughput, memory footprint and disk I/O. We define throughput as the number of transactions that the benchmark is able to process in one second. A transaction is a set of SQL requests that read from a database. Memory footprint is the amount of memory used by the container during a given one-second period. Disk I/O counts the number of reads done by the container during a second. Throughput is measured from the benchmark output; memory size and disk activity are gathered by docker. To compare fairly, we need reference numbers for these metrics. These numbers were collected by running a reference experiment with a single container that executes the scenario of container A as described in Table III.

2) Two-container experiments: Our experiments feature two concurrent containers, A and B, executing an OLTP workload. Both experience changes in activity. To test satisfaction, we arbitrarily set the SLO of container A to processing 1700 t/s and B 1100 t/s. By doing so, we simulate the fact that A bought a better cloud offer than B. The SLO are pictured as colored dashed lines in figures 1a to 4a [START_REF] Beyer | Site reliability engineering: how Google runs production systems[END_REF]. When both containers are offered high load, we expect to observe memory performance isolation. When one of the containers receives high load, and the other receives low load or is stopped, we expect memory consolidation to let the former reach the maximum throughput. Accordingly, the experiment goes through six phases, each lasting 180 seconds, as described in Table III.

We use the notation: ϕ n (a, b) where n is the phase number, a corresponds to the load of container A and b that of container B. Possible values for a and b are h (high), l (low), i (intermediate) and s (container is stopped). During phase ϕ 1 (h, h), physical memory is smaller than the combined size of the databases, hence memory pressure occurs. The size of the page cache decreases, causing an increase in physical disk I/O, hence a decrease in application throughput. In ϕ 2 (h, l), if memory consolidation is effective, A should be able to take memory from B, and increase its throughput. We expect both containers to have low throughput in ϕ 3 (h, i), similarly to ϕ 1 (h, h). In ϕ 4 (l, l), containers should be able to answer all the transactions. ϕ 5 (i, h) mirrors ϕ 3 (h, i). During ϕ 6 (s, h), as A stops completely, B should be able to reach maximum performance.

We run this scenario ten times and compute the mean and standard deviation of throughput, memory and disk I/O every second, plotted in Figure 1 to Figure 4.

3) Experimental environment: Our experimental machine is part of the Grid'5000 testbed [START_REF] Balouek | Adding virtualization capabilities to the Grid'5000 testbed[END_REF], [START_REF] Laniel | Thesis_g5kscripts[END_REF]. It has two In-tel®Xeon®Gold 6130 CPU clocked at 2.1 GHz, with 192 GB of DDR4 memory and an SSD [START_REF] Intel | Intel Xeon Processor gold 6130[END_REF]. To create memory pressure, we artificially limit memory size, by running the experiments within a VM restricted to 4 CPU cores and 3 GB of memory.

We use qemu 3.1.0 as the VM hypervisor, docker 19.03.2 and its python library docker-py 4.0.2 to manage containers [START_REF] Qemu | Qemu[END_REF], [START_REF] Docker | Docker CE[END_REF], [START_REF]docker-py[END_REF], [START_REF] Laniel | Thesis_scripts[END_REF]. Our benchmark is sysbench oltp [START_REF] Kopytov | sysbench[END_REF]. We modified the benchmark code in order to be able to vary the throughput [START_REF]Thesis_sysbench[END_REF]. The benchmark reads requests from a mysql 5.7 database [22], [START_REF]Thesis_images[END_REF]. We run our experiments on Linux 4.19 [START_REF] Kroah-Hartman | Linux 4.19[END_REF].

Our two containers (A and B) run with two cores each. Each one reads a database of 4 GB.

B. Baseline experiment with one container

After running the reference experiment, we measure the maximum throughput to be 2000 transactions per second (t/s). The maximum memory footprint and maximum disk I/O are measured at 2.8 GB and 100 reads per second respectively. These values are pictured in Figures 1 to 4 as dashed black horizontal lines.

We arbitrarily set "low" throughput to 10% of high throughput, i.e., 200 t/s. Low throughput is depicted as horizontal dotted black lines in Figure 1a to Figure 4a. We also define "intermediate" throughput as 1500 t/s.

C. Conventionnal mechanisms with two containers

Let us briefly interpret figures 1 to 3. A more detailled analysis is available in previous work [START_REF] Laniel | Highlighting the Container Memory Consolidation Problems in Linux[END_REF].

Without any limit set, ϕ 1 (h, h) of Figure 1a shows that there is no isolation, since containers have the same throughput. In this figure, in ϕ 2 (h, l), A increases its performance, because B receives low load, but it does not reach its reference level. During ϕ 6 (s, h), as A stops, B is able to increase its memory footprint, as shown in Figure 1b, and so reaches the reference performance.

Figure 2a depicts the situation when the max limit is set to 1.8 GB for A and 1 GB for B. A has better performance than B in ϕ 1 (h, h). This can be explained by looking at the same phase in Figure 2b. Indeed, container footprints follow their max limits, so A has more memory than B. Note that, in ϕ 6 (s, h), where A is stopped, B cannot increase its performance because its footprint is blocked by its max limit.

The soft limit results are similar to that of max limit. The only difference occurs in ϕ 6 (s, h) of Figure 3a, where B reaches reference performance. Indeed, as A is stopped, there is no more memory pressure and B can increase its footprint as shown in Figure 3b.

Table I, presented earlier, summarizes these results.

D. MemOpLight with two containers

MemOpLight is designed to consolidate memory while ensuring memory performance isolation. To verify this, we run again the experiment this time enabling MemOpLight. We plot the results in Figure 4.

ϕ 1 (h, h), ϕ 3 (h, i) and ϕ 5 (i, h) in Figure 4a follow the same pattern as the same phases in Figure 3a. Figure 4b shows that, like Figure 3b, when both containers receive high or intermediate load, their memory footprints follow their soft limits (ϕ 1 (h, h), ϕ 3 (h, i) and ϕ 5 (i, h)). A has then a larger footprint than B, this shows that MemOpLight ensures memory performance isolation. Moreover, in these phases, performance of containers A and B are better than with max and soft limits. On average, container A answers to 1351, 1362 and 1370 transactions per second compared to 1290, 1314 and 1358 with the max limit; this represents an increase of respectively 4.7%, 3.7% and 0.9%. With MemOpLight, container B handles almost 933, 999 and 1036 transactions per second while it processes only 894, 968 and 978 transactions per second with the max limit; resulting in an increase of 4.4%, 3.2% and 5.9%. These increases can be explained because MemOpLight permits converging to a balance where containers stop stealing memory each other.

Like ϕ 6 (s, h) in Figure 3b, when A stops completely, there is no more memory pressure, B's footprint grows and permits it to increase its performance to the maximum throughput. MemOpLight's dynamic nature brings a real benefit in ϕ 2 (h, l). During this phase, B receives low load and A a high one. As shown in Figure 4b, there is a memory transfer from container B to container A. Since container B has no requests in its queue, its memory is reclaimed until finding the threshold where it can still answer to 200 t/s. The application feedback permits finding this memory configuration without previous static analysis. MemOpLight maximizes memory consolidation so container A's throughput equals its SLO.

Table IV summarizes all the previous measurements. B has lower performance with MemOpLight and would have better performance with no limits set. This behavior is normal, since in the latter case there is no memory performance isolation. Nonetheless, this is not expected in cloud since a client could have paid more than another so one client would have a better offer than the other.

In summary, MemOpLight increases performance of containers by redistributing memory following their needs.

E. MemOpLight with eight containers

To confirm that MemOpLight adapts to application loads thanks to application feedback, we now run an experiment with 8 containers. Along the phases, which each lasts for 120 seconds, containers receive high, intermediate or low load. The container loads were chosen randomly to cover different cases and put MemOpLight in difficulty.

The scenario and its characteristics are described in Table V. The first column is SLO. The second one shows the values for max and soft limits. The other columns describe the load at each phase of the experiment. Throughput can have multiple values:

• High: The container receives 2500 t/s. Black cells, in Table V, depicts phases where containers receive high load.

• Intermediate : The container receives its SLO ±5% t/s.

In Table V, gray and light gray cells show phases with intermediate load.

• Low: The container sustains only 200 t/s. The different phases of the scenario can be grouped to form 4 different periods. In ϕ 1 and ϕ 2 , the system is highly loaded. ϕ 3 is a transition between highly and lowly loaded. In ϕ 4 , the containers receive low loads. During ϕ 5 to ϕ 9 , the system is moderately busy but container loads increase over time.

In this experiment, we focus on the respect of SLO and the global performance. Figure 5 plots the average throughput of containers generated across 10 runs for different mechanisms. The global throughput is depicted by the height of the bars while the different colors indicate the throughput of each container. Hatched colors emphasize throughput that is above SLO. Figure 6 focuses on the respect of the SLO. It plots the colors of containers over time during the sixth run of our experiment. To plot this Figure, we activate the probes for all mechanisms. As we discussed in Section IV-B, the probe has no overhead.

In ϕ 1 and ϕ 2 , the system is overloaded since almost all containers receive high or intermediate loads. The global per-formance is lower with limits not set, e.g. 836453 transactions (t.) compared to 895317.8 t. and 898728 t. for max and soft limits, because containers are fighting for memory so it is used ineffectively. For these phases, MemOpLight achieves the best global performance (927651 t. in ϕ 1 and 937413 t. in ϕ 2 ). Indeed, with MemOpLight, once containers reach a memory balance they stop fighting for memory. Even containers which have less memory have better performance because they use it effectively. ϕ 3 is a transition phase between highly and lowly loaded. This phase shows if mechanisms are able to adapt to this change. During this phase, max and soft limits permit better performance than limits not set in ϕ 3 (779570 t. and 762521 t. compared to 729834 t.). As depicted in Figure 5d, MemOp-Light permits a better global performance (788909), thanks to its dynamic behavior. Figure 6d shows that MemOpLight permits to containers to converge faster to their SLO.

In ϕ 4 , containers continue to receive low loads. In this phase, the max and soft limits activate so they block memory consolidation and impede container performance (583156 t. and 580914 t. compared to 714737 t. without limits set). MemOplight offers the same performance as with limits not set (723084 t. vs. 714737 t.). With MemOpLight, all containers are satisfied, since there are only green containers in ϕ 4 in Figure 6d. It also permits to more containers to exceed their SLO since hatched zones are bigger.

In ϕ 5 to ϕ 9 , the system is moderately busy but container loads increase over time. Figure 6d shows that MemOpLight maximizes container satisfaction. Moreover, at the beginning of each phase, we can see that containers reach satisfaction more quickly thanks to the dynamic application feedback. During these phases, note that peaks of red can be explained because the benchmark offers an average load, not a constant one.

This experiment shows that MemOpLight permits consolidation and isolation as shown in Table VI and Table VII. Table VI presents performance for each container with all the tested mechanisms. One can see that MemOpLight supports better performance for five of the eight containers. Where MemOpLight performs worse, the difference is only about 0.6%, 2.3% and 1.9% for container B, G and H compared to the experiment with limits not set. Overall, MemOpLight reaches 122.6 millions t. which is 8.9% better than with limits not set. Table VII shows fraction of time where containers are satisfied. This time is the sum of yellow and green time. MemOpLight maximizes the number of satisfied containers. It also increases the time passed satisfied throughout the whole experiment from 44% to 57%. Thus, MemOpLight enhances efficiency, since it improves performance with the same hardware.

In summary, MemOpLight improves throughput and enables containers to be more satisfied.

F. Study of MemOpLight parameters

MemOplight has two parameters that can be tuned: the percent of memory reclaimed each period and the duration of a period. In its implementation, we also chose to reclaim memory from yellow containers, this choice can be discussed.

In this subsection, we first study the impact of these parameters on MemOpLight's performance. For that, we run again the experiment featuring two containers. Then, we modify MemOpLight to create MemOpLightNoYellow where yellow containers are not reclaimed. To compare them, we use again the experiment with eight containers. Unfortunately and due to lack of space, we cannot display the associated figures.

First, we set the reclaim period to be 1 s, and the percent to the following values: 1%, 2%, 5% and 10%. The results for this different values are quite the same. This behavior is due to the using of the PFRA to reclaim memory. This mechanism offers a function which has a memory size to reclaim as parameter. But, this parameter is only indicative, the kernel does whatever it can.

We now fix the memory percent to 2% and use this values for the reclaim period: 1 s, 2 s, 5 s and 10 s. This time, the results are totally different and a reclaim period of 10 s shows bad performance. Particularly, for ϕ 2 (h, l), a period of 10 s leads to a median throughput of 1456 t/s compared to the 1638 t/s offered by a period of 1 s. This represents a decrease of 10.6%. So, the reclaim period has to conform with the application activity, if the application reacts quickly to event, the period has to be short, otherwise it can be longer.

To finish, we study the impact of not reclaiming memory from yellow containers by comparing MemOpLight and Mem-OpLightNoYellow. MemOplight performs better than Mem-OpLightNoYellow, because containers exceed more their SLO in some phases. More precisely, the averaged total transactions is 122.6 millions for MemOpLight and 118.9 for MemOp-LightNoYellow. The global satisfaction also drops from 57% to 52%.

If yellow containers are not reclaimed, there are fewer containers to reclaim, so red containers can less improve their performance. Moreover, yellow containers could need a lot of memory to become green. For these reasons, the yellow state is important and the performance results proved it.

VI. RELATED WORK

Since MemOpLight scales memory according to containers needs, we relate our work to auto-scaling. Auto-scaling con-sists in adding or removing resources or replicas to follow application needs.

Products with auto-scaling already exist [START_REF] Amazon | AWS Auto Scaling Guide de l'utilisateur[END_REF], [START_REF] Barr | New AWS Auto Scaling -Unified Scaling For Your Cloud Applications[END_REF], [START_REF]Microsoft Azure: Autoscaling[END_REF], [START_REF]Google Cloud : Équilibrage de charge et scaling[END_REF], [START_REF]kubernetes/autoscaler[END_REF]. The majority of the existing approaches use horizontal scaling (i.e. add or delete a VM or a container).

Amazon's approach is particularly relevant, because it supports vertical scaling, i.e., giving to or taking resources from a VM or a container [START_REF] Amazon | AWS Auto Scaling Guide de l'utilisateur[END_REF]. Compared to our solution, Amazon focus on all resources. Allocated resources can be modified dynamically thanks to prediction. This dynamic scaling will add or remove resources to maintain their use at fixed levels. The predictive scaling analyzes up to 14 days of a metric use and is able to make predictions 2 days in the future. The prediction grain is one hour. This auto scaling will add or delete resources to conform with the prediction. If the prediction was too weak the dynamic scaling will be activated. The predictive scaling is based on machine learning. MemOpLight can extend this scaling in case of memory pressure or to increase precision since it activates each second.

In research, auto-scaling also exist [START_REF] Kriushanth | Load balancer behavior identifier (LoBBI) for dynamic threshold based auto-scaling in cloud[END_REF], [START_REF] Lorido-Botran | A Review of Auto-scaling Techniques for Elastic Applications in Cloud Environments[END_REF], [START_REF] Moore | Transforming reactive auto-scaling into proactive auto-scaling[END_REF], [START_REF] Rao | A Distributed Self-Learning Approach for Elastic Provisioning of Virtualized Cloud Resources[END_REF]. Some use horizontal scaling [START_REF] Kriushanth | Load balancer behavior identifier (LoBBI) for dynamic threshold based auto-scaling in cloud[END_REF], [START_REF] Moore | Transforming reactive auto-scaling into proactive auto-scaling[END_REF]. Lorido-Botran et al. do horizontal scaling for containers [START_REF] Lorido-Botran | A Review of Auto-scaling Techniques for Elastic Applications in Cloud Environments[END_REF]. They monitor the requests received by their web application during a given period. They analyze and predict the number of requests to come during the next period. Then, they compute the number of containers needed to face those requests. Our approach can extend theirs by adding memory scaling to horizontal scaling. Dupont et al. base their approach on MAPE-K loop [START_REF] Dupont | Experimental Analysis on Autonomic Strategies for Cloud Elasticity[END_REF]. Their approach is innovative in the way that, when a peak of load occurs, they scale the software running by either add/remove function (e.g. security features, logging, etc.) or increase/decrease quality of execution (e.g. decreasing video quality). Their work can be related to us in the sense that we do not scale horizontally or vertically, we just do better with what we have.

Carver et al. focus on containers [START_REF] Carver | ACDC: Advanced consolidation for dynamic containers[END_REF]. Since, under memory pressure, all memory cgroups are reclaimed they propose to modify Linux memory reclamation algorithm, to target first the least recently active container. This solution avoids performance drop of active containers because they are not reclaimed anymore. As they do not take into account application feedback, it is possible that a green container is always recently activated and thus, never gives up its memory under their solution. MemOpLight could be used in combination with this solution to decide from which green container the kernel should reclaim memory based on the activity.

Compared to all these works, ours is unique in the way that we ensure container satisfaction. MemOpLight is also original in the way that it bases its reclaim on containers' performance as reported by probes. Our mechanism is implemented into the Linux kernel and profits from a global view of resources usage, compared to user space solutions which only have access to the application resources usage.

VII. CONCLUSION AND FUTURE WORK

In this paper, we showed that current Linux mechanisms do not combine memory consolidation and memory performance isolation. By default, there is no memory performance isolation. Memory consolidation is only partially effective. Memory performance isolation can be achieved, at the expense of memory consolidation, using the max and soft limits.

We presented MemOpLight to provide memory consolidation. An application probe gives information about a container's satisfaction to the kernel. The kernel reacts by reallocating memory in favor of unsatisfied containers, without overly depriving the others. Evaluation shows that containers are satisfied more often thanks to memory consolidation.

In future work, we will test MemOpLight with a real web server application. We also plan to modify the probe to compute an average on feedback instead of giving an instant one. Another perspective is to be able to estimate the WS size of containers by using an application probe. Indeed, it is possible to reclaim memory from a container until it indicates it has "bad" performance. The memory footprint before the transition from "good" performance to "bad" one equals approximately the WS size. We also plan to scale other resources (e.g. CPU time or disk bandwidth) according to containers needs.

Fig. 2 :Fig. 3 :Fig. 4 :

 234 Fig. 1: No limits set

Fig. 5 :

 5 Fig. 5: Average throughput of eight containers during each phase with different mechanisms

Fig. 6 :

 6 Fig. 6: Containers' colors during the 5th run with different mechanisms

TABLE I :

 I Summary of memory consolidation and memory performance isolation of existing mechanisms in Linux

	Mechanism used	Memory consolidation	Memory performance isolation
	limits not set	weak	no
	max limit	no	yes
	soft limit	no (under memory pressure)	yes

TABLE II :

 II The different reclamation cases of MemOpLight

	Red cgroups	Yellow cgroups	Result
	0	0	No cgroups are reclaimed
			from.
	0	≥ 1	Green cgroups are reclaimed
			from.
	≥ 1	0	Green cgroups are reclaimed
			from.
	≥ 1	≥ 1	Green cgroups are reclaimed
			from first then yellow ones.

TABLE III :

 III Summary of memory consolidation and memory performance isolation of existing mechanisms in Linux

	Phases	Container A	Container B
	ϕ 1 (h, h)	high load	high load
	ϕ 2 (h, l)	high load	low load
	ϕ 3 (h, i)	high load	intermediate load
	ϕ 4 (l, l)	low load	low load
	ϕ 5 (i, h)	intermediate load	high load
	ϕ 6 (s, h)	stopped	high load

TABLE IV :

 IV Median value of measured throughput, averaged over 10 runs, in each phase of each experiment (in t/s rounded to the nearest integer)

	Transactions	Phases	ϕ 1 (h, h)	ϕ 2 (h, l)	ϕ 3 (h, i)	ϕ 4 (l, l)	ϕ 5 (i, h)	ϕ 6 (s, h)
	Container		A	B	A	B	A	B	A	B	A	B	B
	Input load		2000	2000	2000	200	2000	1500	200	200	1500	2000	2000
	Limits not set		1053	1043	1374	196	1054	1168	195	197	1195	1145	1751
	Max limit		1290	894	1411	196	1314	968	196	660	1358	978	962
	Soft limit		1268	879	1423	197	1299	969	196	794	1360	970	974
	MemOpLight		1351	933	1670	195	1362	999	196	197	1370	1036	1723

TABLE V :

 V Throughput in each phase of experiment (in transactions per second)

	Containers	SLO (t/s)	Limit (if set)	ϕ 1	ϕ 2	ϕ 3	ϕ 4	ϕ 5	ϕ 6	ϕ 7	ϕ 8	ϕ 9
	A	1800	1400 MB	2500	1710	2500	200	1890	200	200	200	2500
	B	1600	1000 MB	1520	2500	2500	200	2500	200	1520	2500	200
	C	1400	800 MB	1330	1470	200	1470	2500	1330	1470	200	1470
	D	1400	800 MB	2500	1470	200	200	200	1470	200	2500	2500
	E	1200	600 MB	1140	1140	200	2500	1260	2500	2500	2500	200
	F	1200	600 MB	2500	1260	200	2500	200	2500	1260	1260	2500
	G	1000	400 MB	2500	200	2500	200	200	200	200	950	950
	H	800	400 MB	840	2500	200	200	760	200	760	760	2500

TABLE VI :

 VI Total containers' throughputs (in million of requests with different mechanisms, averaged over 10 runs)

	Mechanism	Containers	A	B	C	D	E	F	G	H	Total
	No limits set		15.2 14.5 17.3 11.9 18.7 15.9	8.8 10.3	112.6
	Max limit		13.6 13.8 13.8	8.5	14.9	9.9	4.6	6.8	85.9
	Soft limit		17.1	17.4	17.6 12.6 17.5 13.4 7.3	9.5	112.4
	MemOpLight		17.5	17.3	18.4 13.7 20.2 16.8 8.6 10.1	122.6

TABLE VII :

 VII Fraction of time (in percent) where container is satisfied (i.e. yellow or green) according to mechanisms (averaged over 10 runs)

	Mechanism	Containers	A	B	C	D	E	F	G	H	Total
	No limits set		42 23	8	35 69 39 62	71	44
	Max limit		60 35	5	37 73 15 53 35	39
	Soft limit		56 42 11 35 64 16 53 32	39
	MemOpLight		58 44 42 52 76 53 67	67	57

Our solution uses the colors of traffic lights to indicate container performance.