Pierre Vuillemin
email: pierre.vuillemin@onera.fr.

Charles Poussot-Vassal

Daniel Alazard

G H -G

G J H2

Poles Residues Descent Algorithm for Optimal Frequency-Limited H 2 Model Approximation

Model approximation of multiple-inputs/multipleoutputs (MIMO) linear dynamical systems over a bounded frequency range can be expressed as an optimization problem in terms of the frequency-limited H2-norm. In this paper, a new formulation of the frequency-limited H2 model approximation error is presented and its gradient derived. It is then used in a descent algorithm which does not require to solve any Lyapunov equation but one initial eigenvalue problem. The efficiency of the method is illustrated through numerical benchmarks.

I. INTRODUCTION A. Context and problem statement

The H 2 optimal model approximation problem has been extensively addressed and several effective algorithms have been developed [START_REF] Van Dooren | H 2 -optimal model reduction of MIMO systems[END_REF], [START_REF] Gugercin | H 2 model reduction for Large-Scale linear dynamical systems[END_REF], [START_REF] Gugercin | An iterative SVD-Krylov based method for model reduction of large-scale dynamical systems[END_REF], [START_REF] Poussot-Vassal | An Iterative SVD-Tangential Interpolation Method for Medium-Scale MIMO Systems Approximation with Application on Flexible Aircraft[END_REF] and successfully applied to industrial use case (see for instance [START_REF] Poussot-Vassal | Business jet large-scale model approximation and vibration control[END_REF]). The underlying framework for these approaches is the interpolation of complex functions by means of particular Krylov subspaces construction and Petrov-Galerkin conditions enforcement.

Whenever the entire frequency response of the model is not needed or not accurately known, approximating the initial system such that the reduced-order one accurately reproduces its behaviour over a bounded frequency range only can be more adequate [START_REF] Vuillemin | A frequency-limited H 2 model approximation method with application to a medium-scale flexible aircraft[END_REF]. Here, an optimization procedure based on the poles/residues representation of the system is developed to achieve this objective. The idea is similar to what have been done in [START_REF] Beattie | A trust region method for optimal H 2 model reduction[END_REF] for the H 2 case.

Problem 1: Let consider a n u inputs, n y outputs MIMO LTI continuous dynamical systems of order n described by H : C → C ny×nu , a H ny×nu p matrix complex-valued function 1 , represented by

H(s) = C(sI n -A) -1 B + D ∈ C ny×nu , (1)
where A ∈ R n×n , B ∈ R n×nu , C ∈ R ny×n and D ∈ R ny×nu . The goal is to find a reduced order model of order r n, described by

Ĥ(s) = Ĉ(sI r -Â) -1 B + D ∈ C ny×nu , (2)
where  ∈ R r×r , B ∈ R r×nu , Ĉ ∈ R ny×r and D ∈ R ny×nu such that Ĥ(s) minimizes the frequency-limited H 2norm, denoted H 2,ω -norm (see Definition 1), of the error system, i.e.

Problem 1 has recently been addressed in [START_REF] Petersson | Model reduction using a frequencylimited H 2 -cost[END_REF] through the gramian formulation of the H 2,ω -norm. Grounded on this formulation, the authors have derived a gradient which can be used in an optimization scheme. In this paper, the newly proposed spectral formulation of the H 2,ω -norm [START_REF] Vuillemin | A spectral expression for the frequency-limited H 2 -norm[END_REF] is used to express the approximation error and to derive a gradient. Both are then used in a descent algorithm. Instead of Lyapunov equations and Fréchet derivatives, this formulation only requires to solve one single initial eigenvalue problem.

B. Notations and paper structure

The paper is divided as follows : Section II recalls preliminary results related to the H 2,ω -norm. Then, in Section III, new expressions for the H 2,ω approximation error and its gradient are presented, as well as a complex optimization algorithm scheme for optimal H 2,ω model approximation. In Section IV, the proposed approach is applied on standard benchmark models to illustrate its efficiency. Section V finally concludes this paper.

The notations used throughout this paper are the following : elements with . are relative to the error model, elements with . refer to the reduced order model, λ i and φ i are i-th pole and residue of the system, respectively. j denotes the complex variable, i.e. j 2 = -1, Re(z) denotes the real part of z and atan (z) is the complex arctangent of z (see [START_REF] Haber | The complex inverse trigonometric and hyperbolic functions[END_REF], [START_REF] Vuillemin | A spectral expression for the frequency-limited H 2 -norm[END_REF] for further details). A T is the transpose of A, A H its conjugate transpose and A * its conjugate. tr (A) and diag(A) denote the trace and diagonal of A respectively, the Hadamard product of matrices is denoted , the element of A located at the i-th row and the j-th column is denoted [A] ij .

II. PRELIMINARY RESULTS ON THE H 2,ω -NORM

A. Generalities

The H 2,ω -norm has been suggested in [START_REF] Anderson | Measures of merit for multivariable flight control[END_REF] as the restriction of the H 2 -norm over a bounded frequency range (see Definition 1). It has recently been used in robust analysis [START_REF] Masi | Robust finitefrequency H 2 analysis[END_REF] and in model reduction [START_REF] Petersson | Model reduction using a frequencylimited H 2 -cost[END_REF] and is of great interest in many applicative problem such as aircraft model approximation and control.

Definition 1 (H 2,ω -norm): Given a continuous MIMO LTI dynamical system H(s) described as in (1), the frequency-limited H 2 -norm of H(s), denoted H H2,ω , is the restriction of its H 2 -norm over a bounded frequency range [0 ω], ω ∈ R + , and is given as

H 2 H2,ω := 1 2π ω -ω tr H(jν)H(-jν) T dν. (4)
J H2,ω = n i=1 n k=1 tr φ i φ T k λ i + λ k a ω,i + r i=1 r k=1 tr φi φT k λi + λk âω,i - n i=1 r k=1 tr φ i φT k λ i + λk (a ω,i + âω,k ) . . . + r i=1 tr φi DT âω,i - n i=1 tr φ i DT a ω,i + ω π tr D DT (18)
The H 2,ω -norm is usually computed by mean of the frequency-limited gramians [START_REF] Gawronski | Model reduction in limited time and frequency intervals[END_REF], but a new formulation based on the eigenvalues and residues of the system has been recently proposed by the authors in [START_REF] Vuillemin | A spectral expression for the frequency-limited H 2 -norm[END_REF], allowing faster computation and applicability to large-scale models. For stable systems with simple poles only, H2 H2,ω can indeed be written as

H 2 H2,ω = tr n i=1 n k=1 φ i φ T k λ i + λ k a ω,i + ω π DD T . . . - n i=1 φ i D T a ω,i (5)
where a ω,i = 2 π atan ω λ i and φ i = lim s→λi (s-λ i )H(s).

Remark 1: (Strictly proper case) If H(s) ∈ C ny×nu is strictly proper, then (5) becomes

H 2 H2,ω = tr n i=1 -a ω,i φ i H T (-λ i ) , (6)
which is very similar to the H 2 expression [2, chap. 5],

H(s) 2 H2 = tr n i=1 φ i H T (-λ i ) , (7)
excepted from the weighting coefficients a ω,i , i = 1, . . . , n, specific to the H 2,ω -norm. Remark 2 (Frequency interval): The H 2 -norm can also be restricted to the interval

Ω = [ω 1 ω 2 ]. Indeed H 2 H2,Ω = H 2 H 2,[ω 1 ,ω 2 ] = H 2 H2,ω 2 -H 2 H2,ω 1 . (8)
As a consequence, all the results presented in this paper are directly extensible to more complex frequency intervals.

Note that if H(s) is stable and strictly proper then,

lim ω→∞ H H2,ω = H H2 . (9)
Thus model approximation in the H 2,ω -norm generalises the H 2 -norm case [START_REF] Vuillemin | A spectral expression for the frequency-limited H 2 -norm[END_REF].

B. About the H 2,ω -norm computation

To efficiently compute the H 2,ω -norm (5), the residues φ i should not be explicitly computed. Indeed, by noting X ∈ C n×n and Y = X -1 the right and left eigenvectors of A, respectively, and e i the canonical basis column vector, it turns out that

tr φ i φ T k = tr CXe i e T i Y B(CXe k e T k Y B) T = e T k (CX) T CX M1 e i e T i Y B(Y B) T M2 e k . (10)
Since M 1 and M 2 are symmetric,

tr φ i φ T k = [M 1 ] k,i [M 2 ] i,k = [M 1 ] i,k [M 2 ] i,k . (11)
Consequently, by denoting L the matrix defined by

[L] i,k = 1 λ i + λ k , (12)
it comes that

n i=1 n k=1 tr φ i φ T k λ i + λ k a ω,i = 1 T (M 1 M 2 L)    a ω,1 . . . a ω,n    , (13)
where 1 denotes the column vector filled with ones and the Hadamard product. Similarly,

n i=1 tr φiD T aω,i = diag Y BD T CX    aω,1 . . . aω,n    . ( 14
)
III. MAIN RESULTS In order to derive an efficient optimization scheme, the H 2,ω mismatch error and its associated gradient are firstly derived, then used to construct a descent procedure. From now on, Problem 1 is restricted to stable models 2 with simple poles only. Under the latter assumption, H(s) and Ĥ(s) can be written as,

H(s) = n i=1 φi s -λi + D (15)
where Re(λ i ) < 0, i = 1, . . . , n, and

Ĥ(s) = r i=1 φi s -λi + D, (16)
where Re( λi ) < 0, i = 1, . . . , r. Formulation (5) of the H 2,ω -norm can then be used to express the H 2,ω mismatch error.

A. Expression of the H 2,ω mismatch error, J H2,ω

The following Theorem expresses the H 2,ω mismatch error between the full-order and reduced order models.

Theorem 1: Given a n-th order model H(s) and a r-th order model Ĥ(s), described by ( 15) and ( 16), respectively, the H 2,ω -norm of the approximation error

J H2,ω = H -Ĥ 2 H2,ω , (17)
is given by relation [START_REF] Van Dooren | H 2 -optimal model reduction of MIMO systems[END_REF], where

D = D -D, a ω,i = 2 π atan ω λ i and âω,i = 2 π atan ω λi . for m = 1, . . . , r, ∂J H2,ω ∂ λ * m = - r i=1 ĉ * m ĉT i bi bH m âω,i + â * ω,m ( λi + λ * m ) 2 + 2 π ω ( λ * 2 m + ω 2 )( λi + λ * m )
. . .

+ n i=1 ĉ * m c T i b i bH m a ω,i + â * ω,m (λ i + λ * m ) 2 + 2 π ω ( λ * 2 m + ω 2 )(λ i + λ * m ) + 2 π b * m DT ĉH m ω λ * 2 m + ω 2 (19) ∂J H2,ω ∂ b * m = r i=1 bT i ĉi ĉH m λi + λ * m âω,i + â * ω,m - n i=1 b T i c i ĉH m λ i + λ * m a ω,i + â * ω,m + DT ĉH m â * ω,m (20)
∂J H2,ω ∂ĉ * m = r i=1 ĉT i bi bH m λi + λ * m âω,i + â * ω,m - n i=1 c T i b i bH m λ i + λ * m a ω,i + â * ω,m + Db H m â * ω,m (21)
∂J H2,ω ∂ D = - r i=1 ĉT i bi âω,i + n i=1 c T i b i a ω,i - 2 π ω D. (22)
Proof: See Appendix. With reference to relation [START_REF] Van Dooren | H 2 -optimal model reduction of MIMO systems[END_REF], one can notice that, as for the H 2 case, the approximation error is composed of the H 2,ωnorm of the initial system (first term), the H 2,ω -norm of the reduced-order model (second term) and some additional cross terms.

It is important to note that formulation (16) of Ĥ(s) implicitly imposes that the residues φi , i = 1, . . . , r, are of rank one. It does not have any impact on the expression of the error, but for the optimization procedure, in order to force them to be of rank one, residues must be written as φi = ĉT i bi where ĉi ∈ C 1×ny and bi ∈ C 1×nu . Problem 1 is thus restricted to the determination of ĉi , bi , λi , i = 1, . . . , r and D which minimize J H2,ω . For notation consistency, the residues φ i of the initial system H(s) will also be written as the product φ i = c T i b i where c i ∈ C 1×ny and b i ∈ C 1×nu , i = 1, . . . , n.

J H2,ω and Ĥ are thus functions of r(n y + n u + 1) + n u n y parameters in the general case and r(n y + n u + 1) in the strictly proper case. In the H 2 framework described in [START_REF] Beattie | A trust region method for optimal H 2 model reduction[END_REF], additional constraints were added to the norms of ĉi and bi thus reducing the number of decision variables to r(n y +n u ). Yet, to fit in the complex optimization framework stated in [START_REF] Sorber | Unconstrained optimization of real functions in complex variables[END_REF], here, no constraint is added.

B. Expression of the conjugate gradient,

∂J H 2,ω ∂z *
J H2,ω is a real function of complex variables z = λi , ĉi , bi , their complex conjugates z * and D. As recalled in [START_REF] Sorber | Unconstrained optimization of real functions in complex variables[END_REF], such a function is non analytic in z. The common way of dealing with such kind of functions consists in writing them as functions of the real and imaginary parts of z. Yet it is more convenient to keep J H2,ω as a function of complex variables, that is why the complex optimization framework, presented in [START_REF] Sorber | Unconstrained optimization of real functions in complex variables[END_REF], has been preferred. In this framework, J H2,ω can be minimized indifferently in the complex or real spaces by constructing optimization schemes based on the scaled conjugate cogradient 2

∂J H 2,ω
∂z * . That is why, in what follows, J H2,ω [START_REF] Van Dooren | H 2 -optimal model reduction of MIMO systems[END_REF] is derived with respect to λ * i , ĉ * i , b * i , and D without differentiating the real or complex parts. The following Theorem holds.

Theorem 2: Given a n-th order model H(s) and a r-th order model Ĥ(s) described by ( 15) and ( 16), respectively, the complex derivatives of the approximation error J H2,ω [START_REF] Van Dooren | H 2 -optimal model reduction of MIMO systems[END_REF] with respect to λ * m , b * m , ĉ * m , and D are given by the equations ( 19), ( 20), ( 21) and ( 22), respectively.

Proof: The gradient is obtained through straight derivation of the error expression [START_REF] Van Dooren | H 2 -optimal model reduction of MIMO systems[END_REF].

As for the H 2,ω -norm, the conjugate gradient of J H2,ω can be computed efficiently through matrix/vectors products (see Section II-B).

C. Descent Algorithm for Residues and Poles Optimization (DARPO)

The error J H2,ω and the gradient

∂J H 2,ω ∂z *
presented in Theorems 1 and 2 are now used in a complex gradient descent algorithm, called DARPO. The basic optimization scheme is described in Algorithm 1. The following remarks can be made :

• Step 2 : the initialization is done by selecting a perturbated subset of the initial system parameters which corresponds to the highest residues in the considered frequency bands. The initialization can also be done with another model approximation algorithm, DARPO would then be a refining part. ∂z * | z=z k , the derivative of J H2,ω (z k +α k p k ) with respect to α k when α k = 0, falls below a tolerance > 0.

• Step 6 : the descent direction is symbolically chosen here as the opposite of the conjugate gradient, but in practice, a quasi-newton procedure, like BFGS, is implemented. • Step 11 : by constructing arbitrary eigenvectors X r associated to the eigenvalues of the reduced-order model, its state-space representation can be obtained as,

 = X r diag( λ(k) 1 , . . . , λ(k) r )X -1 r B = X r b(k)T 1 . . . b(k)T r T Ĉ = ĉ(k)T 1 . . . ĉ(k)T r X -1 r . (23)
• The approximation is done either over a simple frequency band Ω = [0 ω] or over an union of K frequency bands

Ω = K k=1 ω (k) 1 ω (k) 2 , ω (k) 1 < ω (k) 2 < ω (k+1) 1
where ω (K) 2 can be infinite if and only if the system is strictly proper.

Algorithm 1 Optimization scheme of DARPO

Require: A ∈ R n×n , B ∈ R n×nu , C ∈ R ny×n , D ∈ R ny×nu , [0 ω]
with ω > 0 and r ∈ N * . 1: Compute the eigenvalues of A and their associated right and left eigenvectors X and Y , respectively. 2: Choose an initial point z 0 composed of

λ(0) i , ĉ(0) i , b (0)
i , i = 1, . . . , r, and D(0) . 3: k ← 0. 4: while not converged do 5:

Compute J H2,ω (z k ) and

∂J H 2,ω ∂z * | z=z k . 6: Set p k = -2 ∂J H 2,ω ∂z * | z=z k . 7:
Choose α k such that J H2,ω (z k + α k p k ) satisfies the complex strong Wolfe conditions [START_REF] Sorber | Unconstrained optimization of real functions in complex variables[END_REF].

8:

Set

z k+1 = z k + α k p k . 9: k ← k+1. 10: end while 11: Use λ(k) i , ĉ(k) i , b(k) i , i = 1, . . . , r to construct Â, B, Ĉ .
Note that, grounded on the optimization scheme described in Algorithm 1, DARPO can be used in two main ways :

• given an order r, it will find a r-th order model Ĥ(s) which minimizes J H2,ω , • given a relative H 2,ω error E H2,ω , it will find a reducedorder model Ĥ(s) which satisfies

100 J H2,ω H H2,ω = 100 H -Ĥ H2,ω H H2,ω ≤ E H2,ω ,
by iteratively increasing the order r of Ĥ(s) and performing an optimization for each r. The DARPO is made available in the MORE Toolbox 3 [START_REF] Poussot-Vassal | Introduction to MORE: a MOdel REduction Toolbox[END_REF] with the following Matlab sequence [Hr,out] = moreLTI(H,r,'DARPO',opt), where H is the full-order model and opt is the list of options (see the web site for further information).

Remark 3: Once the eigenvalues and associated eigenvectors of the initial model are computed (step 1), steps 4 to 10 in Algorithm 1 are cheap since they involve matrix/vector and Hadamard products only.

IV. NUMERICAL APPLICATIONS

In this section, the efficiency of DARPO, is illustrated through several examples. The method is compared (i) to the Frequency-Limited Balanced Truncation (FL-BT [START_REF] Gawronski | Model reduction in limited time and frequency intervals[END_REF]) and to the Frequency-Limited Iterative SVD-Tangential Interpolation Algorithm (FL-ISTIA [START_REF] Vuillemin | A frequency-limited H 2 model approximation method with application to a medium-scale flexible aircraft[END_REF]), in the H 2,ω case 3 http://w3.onera.fr/more/ Interval and (ii) to the Iterative Tangential Interpolation Algorithm (ITIA or MIMO IRKA [START_REF] Van Dooren | H 2 -optimal model reduction of MIMO systems[END_REF], [START_REF] Gugercin | H 2 model reduction for Large-Scale linear dynamical systems[END_REF]), to the Iterative SVD-Tangential Interpolation Algorithm (ISTIA [START_REF] Gugercin | An iterative SVD-Krylov based method for model reduction of large-scale dynamical systems[END_REF], [START_REF] Poussot-Vassal | An Iterative SVD-Tangential Interpolation Method for Medium-Scale MIMO Systems Approximation with Application on Flexible Aircraft[END_REF]) and to the Balanced Truncation (BT), in the H 2 case.

A. Fixed approximation order r

For the first application, the International Space Station (ISS) model [START_REF] Leibfritz | Description of the benchmark examples in COMPleib 1.0[END_REF] is considered. This 270-th order MIMO (3 inputs and 3 outputs) model is reduced to a 16-th order model over the frequency intervals (i)

Ω 1 = [0 3] , (ii) Ω 2 = [0 12], (iii) Ω 3 = [12 ∞] and (iv) Ω 4 = [0 ∞].
The relative errors are reported in Table I.

On this example, the proposed approach leads to slightly better results than other algorithms excepted when the approximation is done over Ω 2 where DARPO directly falls into a local minimum. The initialization is a key step in non convex optimization problems and even if the current selection method is often satisfactory, further studies are required to improve it. In particular, the current initialization method does not enable to create poles in the case where there is not enough poles from the full-order model in the desired frequency band.

Figure 1 shows the decrease of the approximation error J H2,ω for DARPO when Ω 4 is considered, highlighting the efficiency of the descent scheme. Indeed the algorithm starts with an error of 21% and ends with 10% only. Moreover it stops with a relative error better than the ITIA.

To illustrate what can be achieved when multiple frequency-bands are considered, one transfer of the ISS model is reduced to an order 16 over Ω = [6 12] [35 70]. The frequency responses of the full-order model and the reduced-order one are plotted in Figure 2. This feature can be useful from an engineering point of view (e.g. for control) since it enables to capture precisely some modes which are not necessarily in the same frequency band.

B. Fixed H 2,ω error

In this section, three models are reduced by DARPO such that a relative error smaller than E H2,ω = 1 % (over a particular frequency band) is reached. The models are also reduced with other approaches for the resulting order r. The models used here are the ISS model, the Clamped Beam Model (CBM, 270 states, SISO) and the Los Angeles Hospital Model (LAH, 48 states, SISO) [START_REF] Leibfritz | Description of the benchmark examples in COMPleib 1.0[END_REF].

The results are reported in Table II. Moreover the decrease of the approximation error for the ISS model when Ω = [0 12] is plotted in Figure 3 where each black dashed vertical line corresponds to an increase of 2 in the order r.

Table II shows that all the methods lead to similar results for each case. Yet, only DARPO enables to really watch the approximation error directly and stop the increase of the approximation order when the relative error requirement is fulfilled while other techniques require a time consuming trial and error approach. As expected, Figure 3 shows that there is an important decrease of the H 2,ω approximation error each time the order r increases.

C. Very large-scale settings

The main cost of the proposed approach lies in the computation of the initial system eigenvalues and eigenvectors (step 1 in Algorithm 1). Indeed, to fully compute the H 2,ω -norm of the error and its gradient, all of them are required (due to the 4 Here the result was unstable so the modified version of the frequencylimited balanced truncation, described in [START_REF] Gugercin | A survey of model reduction by balanced truncation and some new results[END_REF], has been used. cross terms). Despite very effective iterative algorithms exist for large-scale eigenvalues problems [START_REF] Saad | Iterative Methods for Sparse Linear Systems[END_REF], it can becomes very time and memory consuming. In this Section, some hints are given to bypass this difficulty. The H 2 -norm of a large-scale system can be quite well estimated by only considering the highest contribution among the poles/residues couples. These poles/residues couples can be determined efficiently by using the Dominant Poles Algorithm [START_REF] Rommes | Efficient computation of multivariable transfer function dominant poles using subspace acceleration[END_REF]. Yet it still requires a lot of computation. However, in the H 2,ω case, when the frequency band is bounded, there is potentially less poles/residues couples that have a major impact on the H 2,ω -norm (this is especially true for very flexible structures where only poorly damped modes matter).

As an illustration, let reduce the ISS model with DARPO using (i) all the eigenvalues and their corresponding eigenvectors and (ii) only the eigenvalues which have a magnitude below ω. When only some eigenvalues are used, the algorithm is denoted sDARPO for sparse DARPO. As the error given by sDARPO is not exact, it is recomputed afterwards. The resulting relative errors obtained with DARPO and sDARPO are reported in Table III, where the number of used eigenvalues is indicated in brackets.

Since the system is very flexible, this procedure works well, indeed there is only few difference between the approximation given by DARPO and sDARPO. Yet, it might fails for models with a lot of real or highly damped modes (like heat flow model).

V. CONCLUSION

In this paper a new expression for the frequency-limited H 2 model approximation error has been presented, grounded on its poles/residues representation. Its gradient has been derived and a new complex descent algorithm (DARPO) has been presented. This formulation leads to a fast computation of the error and its gradient once the eigenvalues and eigenvectors of the initial system have been computed. This newly proposed approximation algorithm yields to very satisfactory results. Moreover it provides the very appealing feature of selecting a model with an user defined mismatch error instead of the classical reduced order. Several examples have been presented to illustrate the efficiency of the method.

APPENDIX

Proof of Theorem 1

The proof comes from writing the H 2,ω -norm of the error in terms of the residues φi and poles λi , i = 1, . . . , n + r of the error system H(s), (30)

Fig. 1 .

 1 Fig. 1. Evolution of J H 2,ω against the iteration using DARPO (ISS model, r = 16, Ω 4 = [0 ∞]).

Fig. 2 .

 2 Fig. 2. Frequency responses of the full-order model and the reduced-order one (ISS model,r = 16, Ω = [6 12] [35 70], DARPO).

Fig. 3 .

 3 Fig. 3. Decrease of J H 2,ω with respect to the iteration when the order is not fixed (ISS model, Ω = [0 12], DARPO).

1 π

 1 ωtr D DT . (25)The poles/residues of H(s) are composed of the poles/residues of H(s) and -Ĥ(s), indeed, by supposing they are ordered asλi = λ i if i = 1, . . . , n λi if i = n + 1, . . . , n + r,(26) φi= φ i if i = 1, . . . , n φi if i = n + 1, . . . , n + r,(27)the sums in (25) can then be divided as follow, âω,i + r i=1 tr φi DT âω,i.

TABLE I Relative

 I H 2,ω errors (in %) obtained after reduction of the ISS model to a 16-th order model over different frequency-bands.

		Ω DARPO FL-BT or BT FL-ISTIA	ITIA
	[0 3]	0.3847	0.7378	0.3871	-
	[0 12]	1.4526	1.2529	1.4714	-
	[12 ∞]	8.8753	17.7489	13.9143	-
	[0 ∞]	10.0857	10.0935	11.9822	15.7460

TABLE II Relative

 II H 2,ω errors (in %) after reduction of the different models to the order r reached by DARPO when its relative error falls below 1%.

TABLE III Relative

 III

H 2,ω errors (in %) obtained with DARPO and sDARPO after reduction of the ISS model to an order 10 for several Ω.

The integral (4) exists for unstable systems, but the expression (5) is then more complex (see[START_REF] Vuillemin | A spectral expression for the frequency-limited H 2 -norm[END_REF]).


Kaveh Razavi

Ana Ion

Genc Tato

Kyuho Jeong

et al.. Kangaroo: A Tenant- Renato Figueiredo

Guillaume Pierre

Thilo Kielmann

la diffusion de documents scientifiques de niveau

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

I. INTRODUCTION

Cloud applications are extraordinarily varied, ranging from one-person projects to huge collaborative efforts, and spanning every possible application domain. Many applications start with modest computing resource requirements which vary thereafter according to the success or failure of their authors. However, they all need to define their resources as a combination of instance types selected from a standard list.

Infrastructure providers promote horizontal scaling (the addition or removal of VMs of identical types) as a practical solution for applications which need to vary their resource usage over time. However, although this provides a simple and efficient model for the infrastructure providers, it presents stringent limitations for cloud tenants. First, standard instance types seldom match the exact resource requirements of particular applications. As a consequence, cloud applications rarely utilize all the resources offered by their VMs. Second, cloud platforms offer little support for fine-grained VM placement. However, as we show later in this paper, co-locating compatible workloads in the same physical machine can bring up to an order of magnitude performance improvements.

To address these challenges this paper proposes Kangaroo, a tenant-centric nested infrastructure. Kangaroo executes cloud applications in VMs running within VMs that are allocated from the infrastructure providers. This nested infrastructure enables fine-grained resource allocation and dynamic resizing.

When a set of nested VMs outgrow the available capacity of their hosting VM, they can be live-migrated to another possibly new larger VM through a programmable interface. This also allows co-locating complementary workloads in the same machine, which in turn increases resource utilization while improving performance. Finally, Kangaroo runs indifferently within VMs hosted by any cloud provider such as Amazon EC2 and private clouds. It can therefore live-migrate unmodified applications across cloud providers and across different types of virtual machine monitors (VMMs), without disrupting application behavior.

Our evaluations based on microbenchmarks and real-world applications show that Kangaroo's fine-grained resource allocation can significantly reduce resource usage compared to horizontal scaling, while co-locating compatible workloads brings order-of-magnitude performance improvements. Livemigrating workloads across VMs and across cloud providers exhibits acceptable overheads, without imposing any downtime nor application modifications.

The remainder of this paper is organized as follows: Section II discusses the background and our motivation for this work. Sections III and IV respectively present Kangaroo's architecture and implementation. Section V presents evaluations and, after discussing the related work in Section VI, Section VII concludes.

II. MOTIVATION AND BACKGROUND

We describe our motivation for this work by formulating some important tenant requirements that are currently not available in infrastructure providers (Section II-A). We then discuss why it is sometimes difficult or against the interest of the providers to implement these requirements (Section II-B). After establishing our motivation, we take a detailed look at nested virtualization, the driving technology behind Kangaroo that provides the desired tenant requirements (Section II-C).

A. Tenant requirements

There are three desired tenant requirements that current providers do not support.

1) Fine-grained VM Allocation: Currently, whenever a tenant needs to scale out, she has the choice between a number of instance types that provide the tenant with various amount of resources. These instance types are defined statically, and they reflect resource requirements of various classes of applications. For example, a tenant with a compute-bound workload can acquire a VM from the class of instance types that provide a high number of cores, or a number of GPUs if the workload can run on GPUs.

This "instance type" abstraction creates a static granularity in which resources can be acquired from a provider. From the tenant's point of view, the static nature of this abstraction is limiting: It does not capture the requirements of all possible applications, and for the ones that it does, it is often not an exact match. This results in provisioning of unnecessary resources for the sake of the ones necessary.

As an example, assume that a tenant needs to allocate 10 cores with 2 GB of memory for a certain application. Since this amount of resources is asymmetrical, it is very unlikely that the provider has an instance type with these exact resource requirements. The tenant has two choices: 1) Either allocate one VM from an instance type with the same number of cores, but excessive amount of memory, or 2) a number of VMs from smaller instance types that provide the same number of cores. The former results in over-provisioning of memory and hence waste of money, and the later results in high core-to-core latency, possibly affecting performance. Even with balanced resource requirements, it can easily be that there is no matching instance type.

Since the tenant knows the requirements of her application the best, she should be able to define instance types dynamically, and be able to allocate VMs from it.

2) Control over VM placement: A tenant has the best knowledge about how the components of her application communicate with each other. Naturally, the closer the components that communicate with each other are, the better networking performance they observe. This means that the tenants should have control over the mapping of their VMs to the underlying infrastructure. Further, the flexibility of controlling VM placement opens up interesting resource management possibilities that we will discuss in Section IV-C.

Currently, there is no or very limited support for controlled placement of VMs on the infrastructure's physical resources. For example, Amazon EC2 does not provide any support for co-location of most of its instance types. There is some support for placement of cluster compute instance types within a network switch, but these instance types are only targeted towards very specific high performance computing applications that can afford the premium price of these instance types [START_REF]Amazon EC2 pricing: Compute optimized -current generation[END_REF]. Google Compute Engine has recently announced some support for migrating VMs between physical resources, but this feature is currently only exposed to the provider (i.e., Google) for maintenance, rather than the tenants [START_REF]Google Compute Engine Live Migration Passes the Test[END_REF].

Ideally, the tenant should be informed about how her VMs are mapped to physical resources of the provider, and be able to migrate them whenever necessary.

3) Unified Provider API: Different infrastructure providers expose different set of APIs for allocating VMs on their resources. While there is substantial effort in standardization of this API [START_REF]OCCI[END_REF], [START_REF]Open Grid Forum[END_REF], it takes a long time for providers to adopt a new standardized API. Abstracting away this API through a library (e.g., libcloud [START_REF]libcloud[END_REF], boto [START_REF]boto[END_REF]) only partially solves this problem; Applications still need to be aware of low-level details of the provider as the libraries cannot abstract away the complete API, and not all providers support the same features.

As a direct result, usually it is tedious to port an application that is written for one provider to another. To make the matter worse, different providers have adopted different virtualization technologies (e.g., Xen, KVM, Hyper-V, etc.) which means that it is typically not possible to run a VM using a certain virtualization technology on another. Thus, even if the API is standardized and adopted by providers, it is still not straightforward to simply migrate an application from one provider to another.

The final requirement is the ability to avoid vendor lock-in by using a unified API for allocating VMs, and the possibility for migrating an application without changing its code or any downtime.

B. Infrastructure Provider Conflicts

Implementing the tenants' requirements is not always straightforward for the providers. As we shall see, it may also not be in their interest.

1) Fine-grained VM Allocation: Static instance types allow for simpler scheduling, physical resource provisioning, and pricing. Providing support for fine-grained VM allocation means more engineering effort, and possibly less flexibility in physical resource management that directly translates into higher operational cost.

2) Control over VM placement: Without tenant support for VM migration, the provider has the complete control over the location of all tenants' VMs. It can migrate the VMs at will for resource management purposes such as scaling out/in its physical resources. Supporting tenant-controlled VM placement makes it difficult, if not impossible, to perform these simple resource management tasks.

3) Unified Provider API: Infrastructure providers started appearing before any coordinated standardization effort, and so did the virtualization technologies that the providers adopted. It will be a substantial engineering effort to provide a new set of API while preserving and maintaining the old one. Further, the vendor lock-in helps keeping a stable user base that a standard API threatens.

Given these facts, we propose a tenant-centric architecture that implements the desired high-level tenant requirements. The basic building-block for our architecture is nested virtualization, which we discuss next.

C. Nested Virtualization

Nested virtualization enables the execution of virtual execution units in an already virtualized environment by running a VMM inside a VM. While nested virtualization introduces performance overhead compared to a UNIX process, it can provide better isolation, security [START_REF] Zhang | CloudVisor: Retrofitting protection of virtual machines in multi-tenant cloud with nested virtualization[END_REF], reproducibility [START_REF] Wannous | Virtualization and Nested Virtualization for Constructing a Reproducible Online Laboratory[END_REF], more control over VMs acquired from the infrastructure providers [START_REF] Williams | The Xen-Blanket: virtualize once, run everywhere[END_REF], and support for VMM development and migration [START_REF] Wasserman | Nested Virtualization: Shadow Turtles[END_REF].

For running the second layer VMs, the user can choose between full virtualization or operating system virtualization (i.e., containers). Each choice come with different possible technologies that can be deployed. We first discuss the nonfunctional properties that are important for this work, and then compare different technologies according to these properties. We consider four non-functional properties to be of importance to Kangaroo:

1) Hardware support: Recently, processors have started exposing specific mechanisms to support virtualization (e.g., Extended Page-tables [START_REF] Yang | Extending KVM with new Intel Virtualization technology[END_REF] and EPT) and nested virtualization (e.g., nested EPT [START_REF] Wasserman | Nested Virtualization: Shadow Turtles[END_REF]). While hardware-assisted (nested) virtualization is attractive in terms of delivering close to baremetal performance, it is not yet available on all infrastructure providers. Hence, a nested virtualization technology that adopts these hardware technologies is limited to providers that offer VMs executing on supported hardware.

2) Stack modification: Different technologies make different assumptions on the extent to which the provider's software stack can be modified to accommodate their requirements. Tenants obviously have a preference for technologies that requires fewer (or no) software modifications, to be able to adopt as many providers as possible.

3) Performance: "All problems in computer science can be solved by another level of indirection"1 , but there is (almost) always an associated trade-off. Here, there is a performance penalty associated with nesting. By adding yet another layer of virtualization, the application performance inside the nested VM degrades. An ideal solution has minimal impact on the application performance.

4) Migration:

Virtualization enables migration by abstracting away the underlying hardware. VM (live) migration provides endless possibilities in terms of resource management [START_REF] Clark | Live migration of virtual machines[END_REF], [START_REF] Hines | Post-copy based live virtual machine migration using adaptive pre-paging and dynamic self-ballooning[END_REF]. The ability of a nested VMM to migrate its VMs is important for a tenant-centric approach to infrastructure resource management. Table I summarizes virtualization solutions according to these criteria. While HVX, Xen-blanket and Turtles have been explicitly designed for nested scenarios, LXC and QEMU are used in non-nested environments as well. In the rest of this section, we describe these solutions in detail.

1) LXC: Linux Containers [START_REF] Lxc | [END_REF] are a light-weight operating system-level solution for running multiple isolated Linux systems on the same host. An LXC container does not own an entire OS stack, but it reuses functionalities provided by its host's kernel. Each container runs in a virtual environment characterized by its own CPU, memory, block I/O access and network bandwidth. As no actual VMM is available, resource management, isolation, and security are provided directly by the Linux kernel using cgroups [START_REF]Control Groups[END_REF], namespaces [START_REF]Linux namespaces[END_REF], SELinux [START_REF]SELinux[END_REF], and AppArmor [START_REF]The AppArmor security project[END_REF].

LXCs represent a low-overhead alternative to full-fledged VMs, suitable for nested scenarios. In [START_REF] Xavier | Performance evaluation of container-based virtualization for high performance computing environments[END_REF], the authors show 2) QEMU: An alternative approach is emulation. QEMU [START_REF]QEMU[END_REF] is a popular open-source virtualization solution available in Linux and Windows environments. It implements hardware virtualization, where an application sees an abstract interface which completely hides the physical characteristics of a platform. This gives the VM's OS the illusion it is running on its own hardware. While QEMU supports hardware acceleration via KVM, its emulation capabilities makes it a good candidate for running nested VMs without relying on any hardware support or the first layer VMM. In order to execute guest code, instructions are dynamically interpreted at runtime using a method called binary translation. QEMU however provides portability at the expense of significant performance degradation.

3) HVX: QEMU's dynamic binary translation model is also leveraged by the HVX [START_REF] Fishman | HVX: Virtualizing the cloud[END_REF] nested VMM for running unmodified VMWare, KVM and Hyper-V VMs over virtual resources. In single-layer virtualization scenarios, VMMs often utilize the hardware extensions to efficiently execute a VM. However, in a virtual environment, these extensions are no longer available. To preserve performance, HVX translates the nested VM's ring-0 code to enforce security and correctness, and directly executes unprivileged nested VM's ring-3 code.

Designed specifically for nested environments, HVX represents a competitive alternative for container-based solutions. However, this is a proprietary solution that would increase the cost incurred by the end users.

4) Turtles:

The Turtles project optimizes nested executions by modifying the first-layer VMM [START_REF] Ben-Yehuda | The Turtles project: Design and implementation of nested virtualization[END_REF]. Turtles is an extension to KVM, which is integrated in Linux, making it a popular virtualization solution. Turtles follows the single-level support for nested virtualization. All the privileged operations generated by the layer two VMM are recursively trapped and forwarded to the lowest one. Normally, this approach would add a significant overhead, but in Turtles' case, it is limited by the use of a series of optimizations at CPU, memory and I/O level such as multi-dimensional page tables and multi-level device assignment. Although KVM is a widely used VMM, the constraint of modifying the first level VMM limits its usability to private data-centers, making this solution unsuitable for scenarios that also target public providers.

5) Xen-blanket:

Xen-blanket proposes a tenant-centric approach for efficiently implementing nested virtualization [START_REF] Williams | The Xen-Blanket: virtualize once, run everywhere[END_REF]. The second layer VMM is represented by a modified Xen implementation capable of running paravirtualized VMs on top of hardware-assisted VMs. The solution preserves existing Xen functionalities, such as VM migration, but it also enforces the paravirtualized specific limitation of being unable to run unmodified VMs. Xen-blanket obtains good performance for the nested VMs at the expense of requiring specific drivers for each type of first layer VMM. Fig. 1: A nested architecture that virtualizes an infrastructure provider and satisfies the desired tenant requirements not available in infrastructure providers today.

6) Hardware Support for Nested Virtualization:

The performance of nested environments can be significantly improved with recent progress in processor architecture from both Intel and AMD. For example, Intel's new Haswell line introduces VMCS shadowing, a feature which allows a nested VMM to access processor virtualization extensions directly, which improves the performance of nested VMs.

While these nested extensions seem to primarily target security and reliability of cloud services, we believe that they can also be leveraged to provide better resource management support for tenants without the associated performance penalty.

D. Discussion

We discussed our motivations for this work in this section.

We then looked at nested virtualization, an important building block for Kangaroo. After comparing existing solutions, we decided to use LXCs for our nested infrastructure to preserve performance. LXCs also start up faster than VMs, potentially benefiting soft real-time cloud applications (e.g. autoscalers) that would otherwise require support for scalable VM start up from the providers [START_REF] Razavi | Scalable Virtual Machine Deployment Using VM Image Caches[END_REF], [START_REF] Razavi | Squirrel: Scatter Hoarding VM Image Contents on IaaS Compute Nodes[END_REF]. However, since LXCs do not have proper support for migration yet, we have used QEMU for our cross-provider migration benchmarks described in Section V-C.

III. ARCHITECTURE

In this section, we first describe our nested architecture, and then formulate some research questions that come with it.

The tenant requirements discussed in Section II-A rely on basic infrastructure support. We employ nested virtualization as discussed in Section II to enable the possibility of a "virtual infrastructure" that can potentially provide the users this necessary support.

Figure 1 shows our proposed architecture. In this architecture, VMs of different instance types from different infrastructure providers are allocated to back our virtual infrastructure. On top of this virtual infrastructure, we allocate nested VMs from tenant-defined instance types, effectively resolving the first tenant requirement (fine-grained VM allocation).

Further, the tenant is in control of the mapping between nested VMs and infrastructure VMs. She can choose the infrastructure VM for allocating nested VMs, and if necessary migrate nested VMs from one infrastructure VM to another, effectively providing support for the second tenant requirement (control over VM placement).

To manage this virtual infrastructure, we expose a common API to the tenants, and translate it to that of the "real" infrastructure providers. This translation effort is done only once for the virtual infrastructure, and then reused by all tenants through the single virtual infrastructure API. Writing applications against this unified virtual infrastructure API allows tenants to run their applications on different infrastructure providers without any change to the code. Further, since the tenant is in control of the virtualization technology of the nested VMs, she can migrate an entire application across providers without downtime, effectively satisfying the third tenant requirement (unified provider API).

Our nested architecture should implement all requirements discussed in Section II-A. To that end, we need to address a number of research challenges:

• What are the trade-offs in implementing a virtual infrastructure? (Section IV-A)

• What kind of networking primitive is necessary to provide connectivity between nested VMs? (Section IV-B).

• How does a virtual infrastructure API look like? (Section IV-C).

• What are the performance implications of running a virtual infrastructure? (Section V).

In the next section, we describe our implementation of this proposed architecture to address these questions.

IV. IMPLEMENTATION

Our implementation of the proposed architecture in Section III consists of three main components:

1) Kangaroo creates a tenant-centric virtual infrastructure on top of VMs allocated from different providers by configuring these VMs as OpenStack compute nodes [START_REF]OpenStack Compute Nodes[END_REF], and creating nested VMs on tenants' requests. We elaborate further on Kangaroo in Section IV-A. 2) IPOP sm provides network connectivity between nested VMs, by implementing a virtual switch and an overlay spanning various providers' IP networks. IPOP sm is a fork of the IPOP project [START_REF]IPOP Project[END_REF] that extends the functionalities of a peer-to-peer IP overlay to a virtual layer-2 switch by forwarding ARP messages in its controller. We discuss the reasons for choosing a switch-based virtual overlay and the highlevel details of our implementation in Section IV-B. 3) Skippy implements the virtual infrastructure provider API by extending libcloud's OpenStack plugin [START_REF]OpenStack libcloud plugin[END_REF]. We elaborate on this API and the implementation of Skippy in Section IV-C.

A. Kangaroo

Our virtual infrastructure exposes an interface to its tenants for allocating (nested) VMs. This interface is then implemented by the infrastructure cloud middleware. Instead of designing and implementing our own API and middleware, we decided to reuse an existing API (OpenStack compute API [START_REF]OpenStack Compute API[END_REF]) and its implementation (OpenStack). The benefits of doing so are twofold: 1) tenant applications that are written against OpenStack are backwards-compatible, and 2) we do not need a new middleware implementation, and we can reuse features from an existing implementation.

Kangaroo is a "configuration" of OpenStack, with a number of scripts to 1) prepare an infrastructure VM to be configured as an OpenStack compute node by running OpenStack's compute and network services on top of that VM, or 2) to prepare an infrastructure VM to be removed from OpenStack when necessary.

Figure 2 shows the high-level architecture of Kangaroo. We use one infrastructure VM hosting an OpenStack controller. This controller can also be configured to run nested VMs if desired. Kangaroo can either be scaled out/in manually or programmatically through Skippy, discussed in Section IV-C. We need a network interface for management traffic between the OpenStack controller and its compute (VM) nodes. In situations where there is no direct connectivity between OpenStack's controller and the compute VMs, we can reuse the same facility that we have developed for nested VM communication, discussed in Section IV-B.

B. IPOP sm

We first discuss the requirements for communication among nested VMs, and then we describe IPOP sm , a network overlay implementation that meets these requirements.

Since in Kangaroo the tenant is in control of VM placement, naturally, the nested VMs that communicate the most should be placed as close to each other as possible. Thus, the network overlay should optimize for the cases when nested VMs are co-located (i.e., running on the same infrastructure VM). The second requirement is to provide seamless connectivity between nested VMs when they are not placed on the same infrastructure VM, and when they migrate. IPOP sm addresses these requirements without requiring any modifications or privileged access to infrastructure VMs. IPOP sm supports the ARP layer-2 protocol by intercepting and tunneling packets through a peer-to-peer overlay. IPOP sm uses Linux bridges for providing connectivity between nested VMs running on the same infrastructure VM, and an ethernet over peer-to-peer overlay to provide connectivity between nested VMs running on different infrastructure VMs. IPOP sm reuses most of IPOP's functionality to automatically establish, monitor, and maintain peer-to-peer tunnels to provide connectivity between endpoints that are behind NATs -in this case, our nested VMs. As shown in Figure 2, by configuring OpenStack to treat IPOP sm 's interface as the (nested) VMs network, and infrastructure provider interface as the management network, we accomplish seamless integration of IPOP sm with Open-Stack. We now focus on the internal details of IPOP sm .

Figure 3 overviews ARP handling in IPOP sm . Each IPOP sm 's endpoint can be slaved to a Linux bridge that connects multiple interfaces. IPOP sm 's endpoint listens on the ARP traffic over the bridge, and reacts to ARP requests whenever necessary. There are four types of ARP traffic that the IPOP sm 's endpoint needs to deal with: 1) Local ARP request: forward this request to others. 2) Local ARP response: forward this response to the other endpoints, and cache this response for a certain period of time. 3) Remote ARP request: If the information is available in the local cache (i.e., IP is located in the local bridge), send a response for that IP while changing the destination MAC address to that of its own. All traffic for the local (nested VM) interface slaved by the bridge will be received by the endpoint and will be forwarded to the right interface. If the information is not available in the cache, forward the request to the local bridge. 4) Remote ARP response: change the source MAC address of the response and forward it to the bridge. From this point, the endpoint will receive all the local traffic for this IP, and will forward it to the appropriate endpoint.

These ARP handling mechanisms provide the abstraction that all nested VMs are located on the same LAN. Since the endpoint is not in the path for local nested VMs communi-add compute node(provider, typep)

Adds an infrastructure VM of typep from provider as a compute node to Kangaroo.

remove compute node(compute node)

Removes the specified infrastructure VM from Kangaroo. This call might trigger migration of nested VMs from this infrastructure VM. add type(core, memory, etc.)

Adds a VM type with the specified resource requirements to Kangaroo. allocate(compute node, type)

Allocates a nested VM from the specified type on the specified compute node (i.e. infrastructure VM). migrate(vm id, compute node)

Migrates the specified nested VM to the specified compute node. Table II shows the network bandwidth achieved with qperf in different scenarios on two VMs on the DAS4 cluster connected via 1 GbE (details in Section V). Two LXCs running on the same VM achieve up to about one order of magnitude better networking performance compared to two VMs located on different physical hosts. The former is the common case in Kangaroo, whereas the latter is the common case in infrastructure providers today. We have left optimizing nested VM communication over IPOP sm as future work. We will show in Section V-B1, how this improved networking performance can benefit overall performance of co-located services.

C. Skippy

As discussed earlier, we use OpenStack as our infrastructure middleware. Hence, regardless of the infrastructure provider, the tenant will use this unified API for allocating (nested) VMs. We extend this API to support the management operations on the tenant's virtual infrastructure provider. These operations include scaling out/in the virtual infrastructure, support for creating VM types dynamically (Section II-A1), and control over (nested) VM placement and migration (Section II-A2). This extension effectively provides the tenants with a software-defined virtual infrastructure.

Table III explains the details of our proposed virtual infrastructure management API. Using this API, the tenant can scale up her virtual infrastructure by attaching new infrastructure VMs from different providers as new compute nodes to Kangaroo. New VM types can be created by specifying the required resources such as cores, memory, etc. Using these VM types, the tenant can ask for nested VMs, on the specified compute node. Finally, the tenant can initiate migration of nested VMs from a source infrastructure VM to a destination infrastructure VM, potentially migrating her workload from a certain provider to another. Skippy is our implementation of this proposed API as a library that cloud applications can use. Skippy is implemented as an extension of libcloud's OpenStack plugin [START_REF]OpenStack Compute API[END_REF]. libcloud provides us with the basis for scaling out/in Kangaroo on different infrastructure providers (the first two calls in Table III), and the OpenStack plugin that Skippy is based upon, provides us with the original OpenStack API (The last three calls in Table III).

D. Summary

We described our implementation of Kangaroo and IPOP sm that follows the nested architecture discussed in Section III. We also discussed Skippy, our implementation of a software-defined virtual infrastructure provider for scaling out/in Kangaroo, allocation of nested VMs on desired compute nodes (i.e., infrastructure VMs), and migration of nested VMs across compute nodes. Skippy provides the necessary mechanisms for efficient resource management to a higherlevel entity with the knowledge of applications' resource requirements (e.g. a Platform-as-a-Service).

V. EVALUATION

We evaluate various aspects of our nested infrastructure in this section. In Section V-A, we briefly describe our use-case ConPaaS [START_REF] Pierre | ConPaaS: a Platform for Hosting Elastic Cloud Applications[END_REF], an open-source Platform-as-a-Service (PaaS), that we have ported to Kangaroo. We show that ConPaaS services on top of Kangaroo can benefit from 1) better resource utilization (Section V-B2), 2) better performance due to co-location, and 3) with minimal interference with other independent workloads (Section V-B1). Further, we show that Kangaroo can live-migrate nested VMs with an acceptable overhead (Section V-C1), and it can live-migrate a real-world application consisting of two ConPaaS services between Amazon EC2 and our local OpenNebula provider within a matter of minutes without any change to the services (Section V-C2).

Our experiments were conducted on two cloud platforms: a private OpenNebula environment available on the DAS4/VU cluster [START_REF]DAS-4 clusters[END_REF] and Amazon EC2. On DAS4 we utilized medium instances equipped with 4 GB of memory and 4 cores running on physical nodes connected via 1 Gb/s Ethernet. For the EC2 experiments, we utilized different instance types, so we specify their flavor for each experiment. On the infrastructure VMs, we are running Ubuntu 14.04, and for the nested VMs, we are running Debian Squeeze. For the experiments in Sections V-B, we have used LXCs for nesting, and for the experiments in Section V-C, we have used QEMU emulation. We are planning to repeat the migration experiments with LXCs, as soon as CRIU [START_REF]CRIU[END_REF] is properly integrated in libvirt-lxc [START_REF]LXC container driver[END_REF].

A. ConPaaS and Integration with Kangaroo

ConPaaS is an open-source framework that provides a runtime environment for hosting applications on infrastructure clouds. Addressing both high performance and Web applications, ConPaaS supports a broad range of services: web hosting services (PHP, Java), storage services (MySQL DB, Scalarix NoSQL, XtreemFS POSIX FS), high performance services (MapReduce, TaskFarming, High-Throughput Condor), In addition, the service catalog can be complemented by user defined implementations. Figure 4 shows the architecture of ConPaaS. Each service consists of a manager VM, and a set of agent VMs. The manager VM performs management tasks for the service such as scaling decisions, and the agent VMs perform the actual work. The agent VMs are scaled out/in by the managers in response to variation in workload. In ConPaaS terms, an application is an orchestration of a number of services. For example, a WordPress application consists of a web service and a database service. The application logic (i.e., the management of service managers), as well as user authentication, and accounting are implemented by the ConPaaS director.

While the careful separation of duties in ConPaaS has resulted in a clean and robust design, resource allocation can become wasteful on a public infrastructure provider since the instance types do not match the requirements of different components. Hence, we believe ConPaaS is a good candidate to benefit from the resource management flexibility that Kangaroo provides.

We have ported ConPaaS to Kangaroo with minimal efforts since ConPaaS supported OpenStack already. We just exposed Skippy's API for adding and removing virtual compute nodes, as well as defining new instance types to ConPaaS director and to ConPaaS managers. We further exposed a mechanism to migrate ConPaaS services and applications using Skippy's migration capabilities. In the rest of this section, we show how ConPaaS benefits from these new mechanisms.

B. Co-location

One of the privileged operations that is possible in a nested platform such as Kangaroo is control over VM placement. Consequently, ConPaaS can implement co-location policies that can maximize resource utilization to reduce cost, while improving performance due to improved networking performance. We show these improvements using a number of ConPaaS services.

1) Performance:

We compare the performance of Word-Press, a real-world ConPaaS application using VMs acquired from Amazon EC2 and from Kangaroo running on top of a VM that is also acquired from Amazon EC2. WordPress consists of two ConPaaS services: PHP and MySQL. Each of the services require two VMs (four VMs in total). When running directly on top of Amazon EC2, we chose m1.small for VM allocation, the smallest instance type with sustained performance. At the time of writing this paper, this translates into 0.104 $ monetary cost per hour (4 × 0.026 $). When running on Kangaroo, we chose a single t2.medium to run all nested containers. This translates into 0.052 $ monetary cost per hour, which is half of the non-nested case. Figure 5 shows the mean response time of WordPress when increasing the number of concurrent requests using the AB benchmark [33]. The response time of ConPaaS using Kangaroo is about an order of magnitude better than the response time of ConPaaS when using Amazon EC2 VMs directly and remains constant till a hundred concurrent requests. The reason for this improvement is mostly due to co-location of the PHP service and MySQL that avoids a round trip network delay between these services.

In the next section, we look at the resource utilization of WordPress application in both scenarios to better understand why such performance numbers are achievable despite 50% saving in cost.

2) Resource Utilization: We look at the resource utilization of the aforementioned WordPress application. We have measured the amount of idle CPU cycles and memory while executing the same benchmark that we discussed in the previous section. Figure 6 shows the results for both CPU and memory. It is clear that the ConPaaS WordPress is wasting resources when using Amazon EC2's VMs. This is because the smallest suitable instance type is not a match for different components of the ConPaaS services. In the case of Kangaroo however, the resources are more efficiently utilized.

In spite of the cost reduction due to more efficient resource utilization, performance is not affected, as the two services target different resources: PHP is a CPU bound service, while MySQL under high load stresses storage and memory. Consolidating services with different resource requirements by means of nesting is directly reflected in the price paid by the end user, opening opportunities for new pricing models for PaaS environments.

3) Disjoint Workloads: Service co-location is not only useful for tightly coupled services, but also in the case of disjoint workloads. We have conducted tests in which a PHP service (CPU bound) is running along with a memcached (memory bound) service, sharing the same first layer VM (t2.medium instance). Both services are tested against heavy load using AB and memslap [START_REF]Memslap[END_REF] benchmarks. As shown in Figure 7, there is no performance degradation for any of the services as a result of their co-location. The PHP service maintains the mean response time close to 25 ms (for a hundred concurrent requests), even when increasing the concurrency level of the memslap client. At the same time, the linear trend shown by running the memcached service in isolation is not affected by the additional computational load incurred by the PHP service. The mean response time in this benchmark is smaller than the benchmark described in Figure 5 since there is no MySQL service in the loop.

C. Migration

One of the interesting possibilities with Kangaroo is the possibility of migrating tenant's workload between infrastructure VMs without support from the providers. This opens up interesting possibilities in terms of resource management, and cross provider migration. In this section, we first quantify migration times of nested VMs via synthetic microbenchmarks (Section V-C1), and then we explore a scenario where an entire application is live-migrated across providers without any change to the application's code (Section V-C2).

1) Single VM: As described earlier, Kangaroo supports provider-independent live-migration of the nested VMs. We ran a series of microbenchmarks to measure the migration time of a nested VM with 1 GB of memory under different workloads. We used stress [START_REF]Stress workload generator[END_REF] as a synthetic workload generator inside the nested VM. We varied the amount of consumed memory by stress and with and without an I/O bound thread.

Our nested VMs use a 3.2 GB virtual disk. OpenStack offers two options for sharing the disk contents of the mi-grated VM: 1) block migration (the disk is copied during the migration process), and 2) shared file systems (the images of the guests are accessible for all the compute nodes through a shared file system). We opted for block migration so that the VM is not impacted by the overhead of accessing the image over the network. In addition, OpenStack was configured to utilize qcow2 images, so that the transferred data is limited only to the blocks that were changed during the life time of the nested VM. Finally, we configured Kangaroo to use the QEMU's pre-copy live-migration. Figure 8 shows the migration time of a nested VM between two VMs running on different DAS4/VU physical hosts. In the case of memory-bound workloads the migration time increases linearly, and peaks in I/O intensive scenarios. In all cases, the nested VM could live-migrate within a few minutes. These numbers can be easily improved by means of more advanced migration facilities such as post-copy migration [START_REF] Hines | Post-copy based live virtual machine migration using adaptive pre-paging and dynamic self-ballooning[END_REF], but they are sufficiently small for our proof-of-concept prototype.

2) Entire Application: One of the important aspects related to migrating an application from one infrastructure provider to another is the downtime encountered by the end users. Currently, the process for performing cross provider migration includes shutting down the application, updating the VM images to make it compatible with the VMM of the new provider, and then starting the application again in the new environment. Along with the downtime incurred by this cold migration process, this approach raises significant technical challenges on the end user side. For example, the end user may need to rewrite parts of her application to make it compatible with the new provider's environment. Kangaroo's unified API, complemented by its support for VM placement, solves the cross provider migration problem and can migrate an entire application from one provider to another without downtime or change to the application code.

We experimented with cross-provider migration by deploying WordPress, a real-world application, and live-migrated it from Amazon EC2 to our local DAS4 OpenNebula provider. The migration was initiated with a single ConPaaS command that identifies the application, and the destination provider.

As mentioned before, WordPress utilizes two of the Con-PaaS services, PHP and MySQL. Each service runs with two nested VMs (a manager and an agent) so in total the application used four VMs. The nested VMs were using 1 GB of memory and a single core. Initially the nested guests were running on a single infrastructure VM on Amazon EC2 (t2.medium).

Upon the migration request, ConPaaS started a VM on the OpenNebula deployment on DAS4, and contextualized it as an OpenStack compute node. As soon the VM became online, ConPaaS initiated the nested VMs migration to the new VM.

The total time from the moment the application migration command was issued to the moment when the last nested VM finished its migration was a little under 10 minutes (8m54s, 9m42s, 8m5s for successive executions). Without Kangaroo, migrating a PaaS environment from EC2 to a private Open-Stack cloud took about 30 minutes of application downtime and about 45 minutes of total migration time [START_REF]Cloud Foundry Cloud Migration[END_REF], while relying heavily on user intervention for performing all the cold migration steps. Our approach is fully automated and significantly reduces the total migration time.

D. Summary

We evaluated the Kangaroo framework and showed that service co-location and careful management of resources provides up to an order-of-magnitude performance improvement while also reducing the monetary costs due to efficient utilization of infrastructure resources. Further, access to the second-layer VMM enables applications such as ConPaaS to utilize previously unavailable operations like migration. We have successfully live-migrated a WordPress application from Amazon EC2 to our local DAS4 in less than 10 minutes.

VI. RELATED WORK

There has been a number of efforts to create nested infrastructures to complement the properties of current infrastructure providers, which we study in Section VI-A. Containers have also been extensively employed to build better PaaS architectures, which we look at in Section VI-B.

A. Nested Infrastructures

Inception [START_REF] Liu | Inception: Towards a nested cloud architecture[END_REF] lays the ground for a new infrastructure model where VMs acquired from public providers are used as an infrastructure layer for a second infrastructure middleware. The authors emphasize the reduced constraints on the new (virtual) provider with regard to deploying and running the infrastructure, and the increased flexibility in resource management. Inception proposes a layer-2 network overlay to provide connectivity between the nested VMs. HVX [START_REF] Fishman | HVX: Virtualizing the cloud[END_REF] proposes a similar nested model, and uses hSwitch for providing layer-2 connectivity between the nested VMs. Kangaroo's architecture is similar to both Inception and HVX, but it offers much more: 1) it provides dynamic membership for the infrastructure VMs, making it possible to scale out/in the virtual infrastructure whenever necessary. This has been made possible by IPOP sm 's support for joining/leaving the layer-2 overlay network without any need for (re)configurations, even when infrastructure VMs are behind NAT. 2) Skippy provides a convenient API for programming the virtual infrastructure, paving way for a new era of softwaredefined infrastructures for the tenants. Further, to the best of our knowledge, this is the first study to extensively evaluate real-world applications on top of these nested infrastructures. Spilllner et al. analyze the feasibility of using a resource broker in a nested cloud environment in order to optimize resource allocation in relation to the utilization cost [START_REF] Spillner | Analysis of overhead and profitability in nested cloud environments[END_REF]. They show that nesting does not degrade the performance of applications considerably, and argue that tenants can resell the extra resources that they do not need to increase their resource utilization and decrease the cost. Kangaroo takes a different approach by allowing the tenants to partition the rented resources according to the needs of their applications.

Nesting has also been employed to improve the security and reliability of infrastructure clouds. CloudVisor [START_REF] Zhang | CloudVisor: Retrofitting protection of virtual machines in multi-tenant cloud with nested virtualization[END_REF] builds a thin VMM inside a VM to protect the application workload against breaches in the first level VMM (controlled by the infrastructure provider). RetroVisor [START_REF] Wailly | RetroVisor: Nested virtualization for multi IaaS VM availability[END_REF] replicates user workload inside multiple nested VMs, each running inside a nested but different VMM. In this model, if any of the VMMs is exposed to a vulnerability, it can be seamlessly replaced by another.

B. Container-based platforms

Platform providers have long noticed that the interface exposed by current infrastructure providers does not allow for flexible resource management. Further, handling more than a single infrastructure API results in extra development efforts and makes maintenance difficult. To address these issues, they often rely on containers (e.g., LXC).

Heroku [START_REF]Heroku[END_REF] is a platform provider that can be used in order to run web services on top of Amazon EC2. The services run in LXCs, which are managed both by the end user for scaling purposes and by the Heroku engine in order to detect and restart when failed. While similar to Kangaroo, Heroku applications need to be written in certain programming languages, while Kangaroo is an infrastructure provider and agnostic to the type of applications that it runs. Docker [START_REF]Docker[END_REF] is a deployment tool that eases environment replication using LXCs. A user-space API allows bundling an application and all its dependencies in order to be run in an isolated container on another physical host or VM. Docker is compatible with Kangaroo, and Kangaroo users can use Docker for building the environment for their applications.

Deploying Docker, Heroku, and other similar platform providers (e.g., Cloud Foundry [START_REF]Cloud Foundry Cloud Migration[END_REF], OpenShift [START_REF]OpenShift[END_REF], etc.) over a cloud infrastructure, and then using these solutions to create services that run in separate containers build up to a nested architecture similar to our solution. Infrastructure providers such as Amazon [START_REF]EC2 Container Service (ECS)[END_REF], Microsoft [START_REF]Windows Server containers[END_REF], and Google [START_REF]Containers on Google Cloud Platform[END_REF] are also beginning to offer native container support over their VMs. However, Kangaroo enables more extensive features such as cross cloud migration, seamless integration of multiple providers, and the ability to allocate resources that match tenants' requirements through tenant-controlled co-location.

VII. CONCLUSIONS

Infrastructure clouds revolve around the notion of pay-peruse, where tenants only pay for the resources that they use. In reality however, the providers only allow VM allocation from a fixed number of instance types (e.g., small, medium, large, etc.). This typically creates a mismatch between tenants' requirements and the resource allocation policy, which results in the underutilization of tenant resources. Further, providers do not allow co-location or migration of tenants' VMs that could potentially improve the performance of their applications, and in turn reduce their operation costs.

To address these issues, we designed and implemented a tenant-centric software-defined cloud infrastructure named Kangaroo. Kangaroo is based on running OpenStack on top of VMs acquired from infrastructure providers. According to their application requirements, the tenants can allocate nested VMs from Kangaroo. To provide connectivity between these nested VMs, we designed and implemented IPOP sm , a layer-2 overlay network based on the IPOP project. Through our proposed infrastructure management API, tenants can programmatically scale out/in the size of their virtual infrastructure, define new instance types, and co-locate or migrate their nested VMs within their software-defined virtual infrastructure.

Through deployment of real-world applications on Amazon EC2, we showed that Kangaroo can provide an order of magnitude performance improvements while cutting down the operation cost of the applications by half. We also successfully migrated an entire WordPress application, consisting of several VMs, from Amazon EC2 to our local OpenNebula cloud in under ten minutes using a single command, without downtime, or change to the application code.

Fig. 2 :

 2 Fig. 2: Kangaroo configures infrastructure VMs as its compute nodes by running Open-Stack compute and network services as part of VMs' contextualization. Communication between nested VMs located on different infrastructure VMs is made possible with IPOPsm, discussed in Section IV-B

2 Fig. 4 :

 24 Fig. 4: ConPaaS architecture.

Fig. 5 :

 5 Fig. 5: Mean resp. time of WordPress under an increasing number of concurrent requests.

Fig. 6 :

 6 Fig. 6: Idle resources of WordPress under an increasing number of concurrent requests.

Fig. 7 :

 7 Fig. 7: Benchmarking co-located services with disjoint workloads.

Fig. 8 :

 8 Fig. 8: Migration of a single nested VM under different workloads.

TABLE I :

 I Comparison of different technologies for nested virtualization.

		Hardware support	Stack modification	Performance Migration
	LXC	no	++	++	no
	QEMU	no	++	-	yes
	HVX	no	++	++	yes
	Turtles	yes	-	++	yes
	Xen-blanket	yes	+	+	yes

TABLE II :

 II Comparison of qperf performance between different virtualized environment.

TABLE III :

 III The extended infrastructure management API implemented by Skippy.

	cation, their packets will directly go though the infrastructure
	VM's memory. This means that the communication between
	nested VMs hosted on the same infrastructure VM goes
	through memory, without virtualization overhead, satisfying
	the first requirement discussed earlier. Further, in cases where
	the communicating nested VMs are hosted on different in-
	frastructure VMs, they can still communicate with each other
	through this IP overlay, satisfying the second requirement.

David Wheeler that regardless of the type of workload, LXC containers exhibit similar performance to that of native execution. However, as containers share the kernel with their host, usage scenarios are restricted to Linux guests. Although currently live-migration is not included in the LXC framework yet, this feature is already provided by the CRIU project[START_REF]CRIU[END_REF] and awaits integration with popular cloud projects such as OpenStack.

ACKNOWLEDGMENTS

This work is partially funded by the FP7 Programme of the European Commission in the context of the Contrail project under Grant Agreement FP7-ICT-257438, the HAR-NESS project under Grant Agreement FP7-ICT-318521, the Dutch public-private research community COMMIT/, and the National Science Foundation under Grants No. 1339737 and 1234983. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation. The authors would like to thank Stefania Costache and Ana Oprescu for their valuable feedback on an early draft.