Elizabeth Strouse

AND Dan Timotin
email: dan.timotin@imar.ro

Mohamed Zarrabi
email: mohamed.zarrabi@math.u-bordeaux1.fr

A SZEG Ö TYPE THEOREM FOR TRUNCATED TOEPLITZ OPERATORS

Keywords: 2010 Mathematics Subject Classification. 47B35, 30J10, 47A45 Model spaces, truncated Toeplitz operators, Szegö Theorem

Truncated Toeplitz operators are compressions of multiplication operators on L 2 to model spaces (that is, subspaces of H 2 which are invariant with respect to the backward shift). For this class of operators we prove certain Szegö type theorems concerning the asymptotics of their compressions to an increasing chain of finite dimensional model spaces.

The Toeplitz operators are compressions of multiplication operators on the space L 2 (T) to the Hardy space H 2 ; the multiplier is called the symbol of the operator. With respect to the standard exponential basis, their matrices are constant along diagonals; if we truncate such a matrix considering only its upper left finite corner, we obtain classical Toeplitz matrices.

It does not come as a surprise that there are connections between the asymptotics of these Toeplitz matrices and the whole Toeplitz operator, or its symbol. A central result is Szegö's strong limit theorem and its variants (see, for instance, [4] and the references within), which deal with the asymptotics of the eigenvalues of the Toeplitz matrix.

 for a more recent survey. Although classical Toeplitz matrices have often been a starting point for investigating truncated Toeplitz operators, the latter may exhibit surprising properties.

It thus seems natural to see whether an analogue of Szegö's strong limit theorem can be obtained in this more general context. Viewed as truncated Toeplitz operators, the Toeplitz matrices act on model spaces corresponding to the inner functions u(z) = z n , and Szegö's theorem is about the asymptotical situation when n → ∞. The natural generalization is then to consider a sequence of zeros (λ j ) in D, and to let the truncations act on the model space corresponding to the finite Blaschke product associated to λ j , 1 ≤ j ≤ n.

Such a result has been obtained in [START_REF] Böttcher | Borodin-Okounkov and Szegö for Toeplitz operators on model spaces[END_REF]; it deals with the asymptotics of the determinant of a truncated Toeplitz operator. Let us note that in the case of classical Toeplitz operators and matrices one has different variants of Szegö's Theorem, either in terms of the determinant of the truncation, or in terms of the trace, and one can pass from one to the other. However, this is no longer true in our generalized context, where the two different classes of results do not have a visible connection.

The purpose of this paper is to find an analogue of the trace type Szegö Theorem. We manage to obtain a complete result in the case when (λ j ) is not a Blaschke sequence. The Blaschke case seems to be less prone to an elegant solution, and we have only partial conclusions.

The technique we use is inspired by one of the approaches to the Szegö Theorem that is based on approximation by circulants (see for instance, [START_REF] Gray | Toeplitz and Circulant Matrices: A Review[END_REF]). In our case we use the analogue of circulants for truncated Toeplitz operators, namely elements in the so-called Sedlock algebras [START_REF] Sedlock | Algebras of truncated Toeplitz operators[END_REF].

The plan of the paper is the following. After a rather extensive preliminary section that introduces the basic notions, we discuss the special case of finite dimensional model spaces. We introduce then the Sedlock algebras in Section 3, and prove a result important in its own right, Theorem 3.2, which gives an alternate identification of these algebras. Sedlock algebras on finite dimensional model spaces are briefly discussed in Section 4, after which Section 5 develops the approximation technique based on them. The main result, Theorem 6.1, is proved in Section 6. The last section discusses through some examples the problems that appear when considering Blaschke sequences.

1. Preliminaries 1.1. Model spaces. Let H 2 be the Hardy space of square integrable functions on the circle with negative Fourier coefficients equal to 0. We recall that a model space is a subspace of H 2 which is invariant for the backwards shift, and that every such space is of the form K B = H 2 ⊖ BH 2 where B is an inner function, i.e., an element of H 2 of modulus 1 almost everywhere. We write P B for orthogonal projection from L 2 onto K B .

We will often make the supplementary assumption that B(0) = 0. In this case B is defined by B = z B.

The reproducing kernels for K B at the points λ ∈ D are the functions

k B λ (z) = 1 -B(λ)B(z) 1 -λz , z ∈ D.
When B has an angular derivative in the sense of Caratheodory at a point in ζ ∈ T, that is, when the nontangential limit of B and B ′ exist in ζ with the limit of B in ζ of module 1, then all functions in K B have a radial limit in ζ, and the corresponding reproducing kernel k B ζ belongs to K B . We have

k B ζ (z) = 1 -B(ζ)B(z) 1 -ζz = ζB(ζ) B(ζ) -B(z) ζ -z , z ∈ D.
We also use the fact that

(1.1) k B ζ 2 = k B ζ (ζ) = lim z→ζ 1 -B(ζ)B(z) 1 -ζz = ζB ′ (ζ) B(ζ) = |B ′ (ζ)|.
(The last equality follows from the fact that all of the above terms are positive real numbers.)

1.2. Truncated Toeplitz operators. If φ ∈ L 2 , then the map f → P B φf is linear from the dense subspace H ∞ ∩ K B to K B .
When this map is bounded, it can be extended to a bounded linear operator on the whole K B , that will be denoted by T B [φ] = P B M φ |K B and called a truncated Toeplitz operator. For φ(z) = z one obtains the compressed shift, which we will denote by S B . The closed linear space of all bounded truncated Toeplitz operators on K B will be denoted by T B . The function φ is called the symbol of the operator. It is known [START_REF] Sarason | Algebraic properties of truncated Toeplitz operators[END_REF] that any operator in T B has a symbol φ in K B + K B , which is unique in case B(0) = 0. Such a symbol is called standard. Also, if B(0) = 0 we see that 1 ∈ K B , so that the orthogonal complement of the constants in K B equals zK B . Thus:

K B + K B = K B ⊕ zK B
and standard symbols can be uniquely written in the form φ + + φ -, with φ + ∈ K B and φ -∈ zK B . Moreover, using the fact that for any inner function U the map h → zh U is an involution on K U one sees that

{φ -: φ -∈ zK B } = { Bψ -: ψ -∈ zK B }
and so we will write our standard symbol (uniquely) as ψ + + Bψ -with ψ + ∈ K B and ψ -∈ zK B .

For α ∈ T one defines S α B = S B + α(1 ⊗ B). One can check easily that the operators S α B (called modified compressed shifts) are unitary. It is proved in [START_REF] Sarason | Algebraic properties of truncated Toeplitz operators[END_REF] that the modified compressed shifts belong to T B .

Suppose now that a ∈ D, and define b a (z) = z-a 1-āz ; b a (z) is an automorphism of the unit disk. We set B a = B • b a . The following result, that we will have the opportunity to use below, is Proposition 4.1 of [START_REF] Cima | Truncated Toeplitz operators: spatial isomorphism, unitary equivalence, and similarity[END_REF].

Lemma 1.1. The formula

(1.2) U a (f ) = b ′ a • f • b a = 1 -|a| 2 1 -āz f • b a
defines a unitary operator U a from K B to K B a , and for any symbol φ we have

U a T B [φ]U * a = T B a [φ • b a ].
1.3. Clark Measures. The following measures have been introduced by Clark [START_REF] Clark | One dimensional perturbations of restricted shifts[END_REF].

For α ∈ T, the function α+B(z) α-B(z) has positive real part, and therefore, by Herglotz theorem, there exists a finite positive measure µ B α on T such that

(1.3) ℜ α + B(z) α -B(z) = T P r,t (ζ)dµ B α (ζ), where P r,t (ζ) = 1-r 2 |ζ-re it | 2 is the Poisson kernel.
The measure is singular, and in case B(0) = 0 we have µ B α = 1. A result of Alexandrov states that for every continuous function f

(1.4) T f dm = T T f dµ α dm(α),
where m is the normalized Lebesgue measure. We will often write µ α instead of µ B α when there is a single inner function B involved. We note that the Clark measures µ b α are defined in the same way for any function b in the unit ball of H ∞ . In particular for the zero function b = 0, for every α, µ b α is the normalized Lebesgue measure.

The next theorem combines results from [START_REF] Clark | One dimensional perturbations of restricted shifts[END_REF] and [START_REF] Poltoratskii | Boundary behavior of pseudocontinuable functions[END_REF].

Theorem 1.2. Suppose that B is an inner function, α ∈ T, and µ α is defined by (1.3). Then any function f ∈ K B has a radial limit f * almost everywhere with respect to µ α , the operator V :

K u → L 2 (µ α ) defined by V f = f * is unitary, and V S α B = M z V .
Suppose now that λ j ∈ D, j ≥ 1. Define, for n ≥ 1,

(1.5)

B n = n j=1 (- |λ j | λ j b λj )
(By convention, in case λ j = 0, the corresponding factor will be -b 0 = -z.) The following lemma is well known; we provide a proof for completeness. Proof. The sequence (B n ) n converges uniformly on every compact set of D to the function B, where B is the zero function in case (i) and the infinite Blaschke product with zeros λ j in case (ii). For 0 ≤ r < 1 and t ∈ R, the Poisson kernel is defined by

P re it (ζ) = 1-r 2 |ζ-re it | 2 = n∈Z r |n| e -int ζ n . We have T P re it (ζ)dµ Bn α (ζ) = ℜ α + B n (re it ) α -B n (re it ) → ℜ α + B(re it ) α -B(re it ) = T P re it (ζ)dµ B α (ζ).
Since span{P re it ; 0 ≤ r < 1, t ∈ R} is dense in the space of continuous functions, we get that (µ Bn α ) n converges in the weak star topology to µ B α . Now the proof is finished since µ B α is the normalized Lebesgue measure when B ≡ 0.

The behavior of the Clark measures with respect to change of variable by an automorphism of the disc is given by the next lemma, whose proof is a simple change of variable in (1.3). 1.4. The Cauchy transform. For the next facts about Cauchy transforms we refer to [START_REF] Cima | The Cauchy Transform[END_REF]. If µ is a Borel measure on T, its Cauchy transform K µ is the analytic function on D defined by

K µ (z) = T 1 1 -ζz dµ(ζ).
The following lemma summarizes the properties of the Cauchy transform that we need.

Lemma 1.5. Suppose µ is a Borel measure on T. Then:

(1) K µ ∈ H p for all 0 < p < 1. (2) K µ ≡ 0 if and only if dµ = φ dm for some φ ∈ H 1 0 , where H 1 0 = {f ∈ H 1 , f (0) = 0}.
Suppose Λ = (λ j ) j≥1 , and each λ j is repeated m j times, with m j a finite integer or infinite. We will denote by L Λ the linear span of z m k m+1 λj and zm km+1 λj , with j ≥ 1 and 0 ≤ m < m j . The next lemma is probably known, but we have not found an appropriate reference.

Lemma 1.6. Suppose ∞ j=1 (1 -|λ j |) = ∞. Then L Λ is dense in C(T). Proof. Suppose µ is a Borel measure on T such that T z m k m+1 λj (z) dµ = T zm km+1 λj (z) dµ = 0
for all j ≥ 1 and 0 ≤ m < m j . By replacing µ, if necessary, with 1 2 (µ + μ) and 1 2i (µ -μ), we may assume that µ is real. We have then K

µ (λ j ) = 0 for all j ≥ 1 and 0 ≤ m < m j . Since K µ ∈ H p for 0 < p < 1, if it is not identically zero its zeros would have to satisfy the Blaschke condition. So K µ ≡ 0, and then by Lemma 1.5 µ = φ dm for some φ ∈ H 1 0 . Since µ is real, φ is real almost everywhere. Therefore φ ≡ 0 and µ ≡ 0, which finishes the proof.

If B n is defined by (1.5), then each of the functions z m k m+1 λj belongs to B n for sufficiently large n. This remark yields the next corollary.

Corollary 1.7. Suppose ∞ j=1 (1 -|λ j |) = ∞, and B n is defined by (1.5). Then ∞ n=1 (K Bn + K Bn ) is dense in C(T).

Finite dimensional model spaces

Let us suppose now that u = B is a finite Blaschke product of order N . In this case K B is of dimension N and contains only rational functions with poles outside the closed unit disc (more precisely, in the reciprocals of the zeros of B); we have dim K B = N and dim

T B = 2N + 1. The measure µ B α is concentrated on the roots ζ α k (k = 1, . . . , N ) of the equation B(ζ) = α,
and is given by the formula

(2.1) µ B α = N k=1 1 |B ′ (ζ α k )| δ ζ α k .
The functions in K B as well as the standard symbols of TTOs have well defined values with respect to µ B α . We will have the opportunity to use the next lemma, which completes (1.1).

Lemma 2.1. Suppose B = n j=1 b λj . Then we have:

(i) |B ′ (e it )| = e it B ′ (e it ) B(e it ) = n j=1 1 -|λ j | 2 |e it -λ j | 2 = d dt Arg B(e it ). (ii) For all ζ ∈ T we have |B ′ (ζ)| ≥ 1 2 n j=1 (1 -|λ j |).
Proof. (i) The second equality is just a computation, using the formula for B.

Taking absolute values, we deduce the first equality.

For the third equality, note that

Arg B(e it ) = ℑ log(B(e it )) = ℑ   n j=1 log b λj (e it )   .
Differentiating with respect to t, we obtain

d dt Arg B(e it ) = ℑ   n j=1 i 1 -|λ j | 2 |e it -λ j | 2   = n j=1 1 -|λ j | 2 |e it -λ j | 2
as required. Part (ii) is a consequence of (i), once we note that for all ζ ∈ T and λ ∈ D we have 1 -|λ| ≤ |ζ -λ| ≤ 1 + |λ|, and therefore

1 -|λ| 1 + |λ| ≤ 1 -|λ| 2 |ζ -λ| 2 ≤ 1 + |λ| 1 -|λ| .
D ν = N k=1 ν k k B ζ α k k B ζ α k ⊗ k B ζ α k k B ζ α k .
Then D ν is a function of S α B , and therefore belongs to T B . In particular, we will denote ∆ α B = D µ B α ; thus

(2.3) ∆ α B := N k=1 1 |B ′ (ζ α k )| k B ζ α k k B ζ α k ⊗ k B ζ α k k B ζ α k ,
The next lemma gives more information about the unitary operators that have appeared in Lemma 1.1.

Lemma 2.2. Suppose a ∈ D, α ∈ T, and the operator U a :

K B → K B a is defined by (1.2). (i) For each k = 1, . . . , N , U a (k B ζ α k ) = b ′ -a (ζ α k )k B a η α k . where η α k = b -a (ζ α k ). (ii) If ν = N k=1 ν k δ ζ α k , then U a D ν U * a = D ν a ,
where

ν a = N k=1 ν k δ η α k . (iii) We have U a ∆ α B U * a = D νa α , where νa α = 1 |b ′ -a • b a | µ B a α = |b ′ a |µ B a α .
Proof. For g ∈ K B a we have

g, U a (k B ζ α k ) = U * a g, k B ζ α k = (U * a g)(ζ α k ) = b ′ -a (ζ α k )g(η α k ),
which proves (i).

To prove (ii), we use (i) to check the action of the left hand side operator on the reproducing kernels. Thus

U a D ν U * a (k B a η α k ) = b ′ a (η α k )U a D ν (k B ζ α k ) = ν k b ′ a (η α k ) b ′ -a (ζ α k )k B a η α k = ν k k B a η α k . (iii) is a consequence of (ii): if ν = µ B α , then ν a = N k=1 1 |B ′ (ζ α k )| δ η α k = N k=1 1 |(B a ) ′ (η α k )| • |b ′ -a (ζ α k ) δ η α k = N k=1 1 |(B a ) ′ (η α k )|| • |(b ′ -a • b a (η α k )| δ η α k = 1 |b ′ -a • b a | µ B a α = |b ′ a |µ B a α .

Sedlock algebras

Sedlock algebras have been introduced in [START_REF] Sedlock | Algebras of truncated Toeplitz operators[END_REF], where it was shown that they are the only algebras contained in T B . The family of Sedlock algebras is indexed by a parameter α ∈ C ∪ {∞}. We will be interested only in α ∈ T, in which case the Sedlock algebra B B α is defined to be the commutant of the unitary operator S α B . In [12,

) = 0. A bounded operator A is in B B α if and only if A = T B [φ + α B(φ -φ(0))] for some φ ∈ K B .
Using Theorem 1.2, one can connect the two descriptions of the Sedlock algebras, as shown by the next theorem. Theorem 3.2. Let B be an arbitrary inner function satisfying B(0

) = 0. Suppose T = T B [φ + α B(φ -φ(0))] ∈ B B α .
Then the function φ has radial limits almost everywhere with respect to µ α . If we denote the limit function by φ * , then φ * ∈ L ∞ (µ α ), and T = φ * (S α B ).

Proof. The first part of the statement follows from Theorem 1.2, since φ ∈ K B . The operator V :

K B → L 2 (µ α ) defined by V f = f * is unitary, and V S α B = M z V . Since B B α = {S α B } ′ , we have V T V * ∈ {M z } ′ , and thus V T V * = Φ(M z ) = M Φ for some Φ ∈ L ∞ (µ α ).
On the other hand, it follows from Proposition 3.2 of [START_REF] Sedlock | Algebras of truncated Toeplitz operators[END_REF] that, when we write an operator T ∈ B α as T = T B [φ + α B(φ -φ(0))], we can identify φ as φ = T 1. So

φ * = V φ = V T 1 = M Φ V 1 = M Φ 1 = Φ. Thus T = V * φ * (M z )V = φ * (S α B
), which ends the proof of the theorem. Some consequences for operators in the Sedlock class B B α can be immediately deduced.

Corollary 3.3. With the above notations, if we decompose µ α = µ c α + µ a α in its continuous and atomic parts, and the support of µ a α is the sequence (η n ) n , then:

(i) T B [φ+α B(φ-φ(0))] is compact if and only if φ * = 0 µ c α -almost everywhere, while φ * (η j ) → 0. (ii) If p is a positive real number, T B [φ + α B(φ -φ(0))] is in the class C p if and only if φ * = 0 µ c α -almost everywhere and n |φ * (η n )| p < ∞. (iii) If p ≥ 1 is an integer and T = T B [φ + B(φ -φ(0))] ∈ C p , then Tr T p = n φ * (η n ) p .

Sedlock algebras and finite Blaschke products

Let us suppose now that B is a finite Blaschke product such that B(0) = 0. Then, for α ∈ T, the measure µ B α is given by (2.1). As noted above, for each

k, k B ζ α k is an eigenvector of S α B associated to the eigenvalue ζ α k . Therefore, if φ ∈ K B , Theorem 3.2 implies that (4.1) T B [φ + α B(φ -φ(0))] = N k=1 φ(ζ α k ) k B ζ α k k B ζ α k ⊗ k B ζ α k k B ζ α k , If T = T B [φ + B(φ -φ(0))] and ν = N k=1 ν k δ ζ α k , it follows from (4.1) and (2.2) that (4.2) Tr(D ν T p ) = N k=1 ν k φ p (ζ α k ) = T φ p dν.
In particular, We may integrate with respect to α to obtain some interesting consequences.

Lemma 4.1. With the above notations, we have

T ∆ α B dm(α) = T B 1 |B ′ | . Proof. For f ∈ K B , we have f = N k=1 f, k B ζ α k k B ζ α k k B ζ α k k B ζ α k
. By (1.4), we get

T ∆ α B (f )dm(α) = T N k=1 1 |B ′ (ζ α k )| f, k B ζ α k k B ζ α k k B ζ α k k B ζ α k dm(α) = T T f, k B ζ k B ζ k B ζ k B ζ dµ B α (ζ) dm(α) = T 1 |B ′ (ζ)| f (ζ)k B ζ dm(ζ) = T B 1 |B ′ | (f ).
From (4.3) and Lemma 4.1 follows the next corollary.

Corollary 4.2. With the above notations (including

T = T B [φ + α B(φ -φ(0))]),
we have

Tr T B 1 |B ′ | T p = φ p dm.

Approximating by circulants

In this section we will develop a procedure, in the case B(0) = 0, for deriving properties of a truncated Toeplitz operator from a closely associated element of a Sedlock algebra. The idea comes from the case of classical Toeplitz matrices (see, for instance, [9, Chapter 4]) and it is based on an enlargement of the model space.

Fix α ∈ T, and let B be a finite Blaschke product with B(0) = 0 and ψ be a (general) standard symbol for a truncated Toeplitz on K B . Thus ψ ∈ K B + K B is of the form ψ = ψ + + Bψ -with ψ + ∈ K B and ψ -∈ zK B. Let u be an inner function that is a multiple of B; that is, u = Bv for some inner function v. Obviously, ψ is also a standard symbol for a truncated Toeplitz operator on K u (since K B + K B ⊂ K u + K u ). We intend to show that, if we set φ = ψ + + αvψ - then we can have good estimates for the difference between T u [ψ] and the operator

T u [φ + αū(φ -φ(0))] in B u α . Notice that φ ∈ K B ⊂ K u and that φ(0) = ψ + (0) (since ψ -(0) = 0).
We see that:

φ + αū(φ -φ(0)) = ψ + + ᾱvψ -+ αū(ψ + + ᾱvψ --ψ + (0)) = ψ + + Bψ -+ ᾱvψ -+ αū(ψ + -ψ + (0)) = ψ + ᾱvψ -+ αū(ψ + -ψ + (0))
and thus

(5.1)

T u [φ + αū(φ -φ(0))] -T u [ψ] = ᾱT u [vψ -] + αT u [ū(ψ + -ψ + (0))].
We can now show that the norms of the two operators on the right hand side of (5.1) do not depend on which inner function u we choose. We will interpret these operators as operators on all of L 2 , rather than just on the subspace K u . We use throughout the computations below the fact that ψ, ψ + , ψ -are all bounded functions.

We use repeatedly that

K u = K B ⊕ BK v = K v ⊕ vK B and that P vKB = M v P B M v .
This gives us that:

T u [vψ -] = P u M vψ-P u = P u M vψ-(P B + P BKv ).
But, it is clear that Im(M vψ-P BKv ) ⊂ uH 2 and so P u M vψ-P BKv = 0. Thus:

T u [vψ -] = P u M vψ-P B = (P v + P vKB )M vψ-P B .
Now we use the fact that Im(M vψ-P B ) ⊆ vH 2 so that P v M vψ-P B = 0 to obtain that:

(5.2)

P u M vψ-P u = P vKB M vψ-P B = M v P B M ψ-P B .
So T u [vψ -] is obtained by multiplying with the operator T B [ψ -] by a unitary operator. In particular, the norm (uniform or Schatten-von Neumann) of T u [ψ -] depends only on B and ψ and is independent of the choice of v.

In our analysis of the second operator, we simplify the notation by denoting ψ 0 = ψ + -ψ + (0) so that ψ 0 ∈ zK B . We have

P u M ūψ0 P u = P u M ūψ0 (P v + P vKB ). Now, using the fact that K v ⊂ vH 2 -and that ψ 0 ∈ K B ⊂ BH 2 -we see that Im(M ūψ0 P v ) ⊂ ūBvH 2 -= H 2 -. So it is clear that P u M ūψ0 P v = 0. Thus P u M ūψ0 P u = P u M ūψ0 P vKB .
Next we notice that:

P u M ūψ0 P vKB = P u M ūψ0 M v P B M v = P u M Bψ0 P B M v . Since ψ 0 ∈ K B we know that Bψ 0 ⊂ H 2 -. But, an element of K B is a function h ∈ H 2 which
is orthogonal to BH 2 and when we multiply such a function by a (bounded) element of H 2 -we get an element h 1 of L 2 which is orthogonal to BH 2 and is therefore orthogonal to BK v . Thus we can conclude that (5.3)

P u M ūψ0 P u = (P BKv + P B )M Bψ0 P B M v = P B M Bψ0 P B M v .
So, just as in the first case, we have obtained that any norm (uniform or Schattenvon Neumann) of T u [ū(ψ + -ψ + (0))] is independent of the choice of v. We summarize the conclusion of our argument in the following lemma.

T u [φ + αū(φ -φ(0))] -T u [ψ] p ≤ C p ,
where C p is a finite constant independent of v.

A Szegö theorem for non-Blaschke sequences

Suppose now that λ j ∈ D, j ≥ 1. As in Section 1. Tr

T Bn 1 |B ′ n | (T Bn [ψ]) p → T ψ p dm.
If ψ is real-valued, then for every continuous function g on [inf ψ, sup ψ] we have

(6.2) Tr T Bn 1 |B ′ n | g(T Bn [ψ]) → T g • ψ dm.
The proof of the theorem will use a series of intermediate results which have interest in themselves. The basic technique is introduced in the next lemma. Then for any ψ ∈ K BN + K BN and p ∈ N we have

Tr(D νn (T Bn [ψ]) p ) → ψ p dν. Proof. If ψ = ψ + + BN ψ -∈ K BN + K BN , we define φ n = ψ + + ᾱ Bn BN ψ -and φn = φ n + α Bn (φ n -φ n (0)) for n ≥ N . Applying
Tr D νn T Bn [ψ] k T Bn [ψ] -T Bn [ φn ] T Bn [ φn ] p-k-1 ≤ M D νn • T Bn [ψ] -T Bn [ φn ] 1 → 0. Now, according to (4.2), we have Tr(D νn T Bn [ φn ] p ) = φ p n dν n . Since B n (ζ α n,k ) = α, we have ψ(ζ (n) j ) = φ n (ζ (n)
j ) for all j = 1, . . . , n, and thus the last integral is ψ dν n , which by (i) converges to ψ dν.

Next, with a suitable assumption on the symbol, we eliminate the restriction

B(0) = 0. Lemma 6.3. Let (1 -|λ j |) = ∞,
B n be as above, α ∈ T fixed, and ∆ α Bn as defined by (2.3)

. Suppose ψ ∈ (K B -λ 1 N + K B -λ 1 N ) • b λ1 and p ∈ N. Then (6.3) Tr(∆ α Bn (T Bn [ψ]) p ) → ψ p dm.
Proof. Denote a = -λ 1 , so B N (-a) = 0, Then for any n ≥ N we have

B a n (0) = B n • b a (0) = B n (-a) = 0.
We have, by Lemma 1.1 and Lemma 2.2 (iii)

Tr(∆ α Bn (T Bn [ψ]) p ) = Tr((U a ∆ α Bn U * a )(U a T Bn [ψ]U * a ) p ) = Tr(D νa,n α (T B a n [ψ • b a ]) p ), where νa,n α = 1 |b ′ -a • b a | µ B a n α .
Consider the sequence of measures νa,n α . By Lemma 1.

3 (i), νa,n α → 1 |b ′ -a • b a | m.
On the other hand,

D νa,n α = ∆ α Bn = sup 1≤j≤n 1 |B ′ n (ζ (n) j )| ≤ sup ζ∈T 1 |B ′ n (ζ)| ≤ 2 n j=1 (1 -|λ j |) ,
where the last inequality is a consequence of Lemma 2.1 (ii).

The assumption on

ψ implies that ψ • b a ∈ K B a N + K B a N . Therefore, applying Lemma 6.2, Tr(∆ α Bn (T Bn [ψ]) p ) = Tr(D νa,n α (T B a n [ψ • b a ]) p ) → 1 |b ′ -a • b a | (ψ • b a ) p dm.
By Lemma 1.4, the last integral is precisely ψ p dm, which finishes the proof.

The next step is to integrate with respect to α ∈ T in order to obtain a version of (6.1) for a restricted class of functions ψ.

Lemma 6.4. Let (1 -|λ j |) = ∞, B n be as above, ψ ∈ (K B -λ 1 N + K B -λ 1 N ) • b λ1 , and p ∈ N. Then Tr T Bn 1 |B ′ n | (T Bn [ψ]) p → T ψ p dm.
Proof. By Lemma 6.3 we have for each α ∈ T (6.4)

Tr(∆ α Bn (T Bn [ψ]) p ) → ψ p dm.
On the other hand, from Lemma 4.1 it follows that

T Tr(∆ α Bn (T Bn [ψ]) p )dm(α) = Tr T ∆ α Bn dm(α) (T Bn [ψ]) p = Tr T Bn 1 |B ′ n | (T Bn [ψ]) p .
Then (6.4) together with Lebesgue's dominated convergence theorem imply that

Tr T Bn 1 |B ′ n | (T Bn [ψ]) p → T T ψ p dm dm(α) = T ψ p dm. But Tr T Bn 1 |B ′ n | P k (T Bn [ψ]) -Tr T Bn 1 |B ′ n | g(T Bn [ψ]) ≤ T Bn 1 |B ′ n | 1 (P k -g)(T Bn [ψ]) ≤ 1 + |λ 1 | 1 -|λ 1 | P k -g ∞
where on the last line we have used (6.5). Since obviously

T P k • ψ -g • ψ dm ≤ P k -g ∞ ,
letting k → ∞ proves (6.2).

In the classical case of Toeplitz matrices, we have

B n = z n , |B ′ n | ≡ n, and T Bn 1 |B ′ n | = 1 n I.
We obtain therefore a version of a classical Szegö limit theorem: if T n are truncated Toeplitz matrices corresponding to the symbol a, then

1 n Tr T p n → T a n dm.
It is interesting to compare Theorem 6.1 with the main result in [START_REF] Böttcher | Borodin-Okounkov and Szegö for Toeplitz operators on model spaces[END_REF], where a formula is obtained for the asymptotics of det T Bn [ψ]. In the classical case the determinant and the trace versions of the Szegö limit theorem are closely connected, and one can deduce one version from the other. This seems not to be the case for general truncated Toeplitz operators.

Blaschke sequences

Theorem 6.1 concerns sequences that do not satisfy the Blaschke condition. It is possible to obtain Szegö results for Blaschke sequences, but these are less elegant and require supplementary hypotheses. First, Lemma 6.3 is true for a Blaschke sequence, provided we add the condition ∆ α Bn → 0. Similarly, Lemma 6.4 is true if we assume that ∆ α Bn → 0 for almost all α ∈ T. As for the main Theorem 6.1, a new complication arises, since Lemma 1.6 is no longer true.. We do, however, have the following precise result; recall that the space L Λ is defined in section 1, before Lemma 1.6.

Theorem 7.1. Suppose that (λ j ) is a Blaschke sequence (i.e. that ∞ j=1 (1-|λ j |) < ∞) and each λ j is repeated m j times, with m j a finite integer. Let B n be given by (1.5) and p ∈ N. Suppose that, for some fixed i ≥ 1, ψ • b -λi ∈ L Λ .

(1) If α ∈ T and if ∆ α Bn → 0, then

(7.1) Tr(∆ α Bn (T Bn [ψ]) p ) → ψ p dµ B α .
(2) If ∆ α Bn → 0 for almost all α ∈ T, then

Tr T Bn 1 |B ′ n | (T Bn [ψ]) p → T ψ p dm.
Unfortunately, it does not seem possible to give simple conditions that would characterize those sequences for which (7.2) ∆ α Bn → 0.

The next two examples suggest the intricacy of the problem. First we give an example of a Blaschke sequence for which (7.2) is satisfied.

Example 7.2. Suppose (λ j ) is a sequence of points in D obtained by choosing m 2 evenly distributed points on each circle of radius r m = 1 -1 m 4 . We have then

(1 -|λ j |) = m m 2 • 1 m 4 < ∞,
and therefore the sequence is Blaschke. Fix m ∈ N. For any e it ∈ T there exists a j ∈ N such that |λ j | = r m and |e it -λ j | ≤ 10 m 2 ; therefore, using Lemma 2.1

P λj (e it ) = 1 -|λ j | 2 |e it -λ j | 2 ≥ 1/m 4 100/m 4 = 1 100 .
and so, for any e it ∈ T, Example 7.3. The second example exhibits the opposite behavior. We show that, for certain Blaschke sequences (λ j ) the hypothesis (7.2) is not satisfied, and, in the case where α = 1, λ 1 = 0 and ψ = z, the conclusion (7.1) is also false; that is:

Tr(∆ 1 Bn T Bn [ψ]) → ψ dµ B 1 .
So, let (λ j ) be a real valued Blaschke sequence with λ 1 = 0. We will add other hypotheses as necessary. Following the approximation procedure of Section 5 for the finite Blaschke product B 2 (z) = -z(-b λ2 (z)) (where B n is defined by (1.5) and the remark after it), we set N = 2, ψ(z) = z and v = n j=3 (-b λj ). Then u = B n = B 2 v, ψ + = 0, ψ -= b λ2 (z), and φ = B n /z. Formula (5.1) then becomes

T Bn [B n /z + Bn (B n /z -B n /z(0))] -T Bn [z] = T Bn [B n /z].
From (4.3) and the fact that B n ≡ 1 on the support of µ Bn 1 , we obtain

Tr ∆ 1 Bn T Bn [B n /z + Bn (B n /z -(B n /z)(0))] = T B n /z dµ Bn 1 = T z dµ Bn 1 .
Thus, for n → ∞,

Tr ∆ 1 Bn T Bn [B n /z + Bn (B n /z -(B n /z)(0))] → T z dµ B 1 .
So, in order to achieve our purpose of showing that

Tr(∆ 1 Bn T Bn [z]) → T z dµ B 1 ,
we have to prove that

(7.3) Tr(∆ 1 Bn T Bn [B n /z]) → 0.
We next use [START_REF] Sarason | Algebraic properties of truncated Toeplitz operators[END_REF]Section 5], where it is shown that Now we begin putting hypotheses on the rest of the sequence (λ j ). We suppose that, λ j ր 1 and that λ j > 1/2 for j ≥ 2, which implies that We have then, starting with (7.4),

T Bn [B n /z] = kBn 0 ⊗ k Bn 0 . Denote by ζ n k the solutions to B n (ζ) = 1. Notice that, since -1 is such a solution, ζ n 1 = -1. We have ∆ 1 Bn = n k=1 1 |B ′ n (ζ n k )| k Bn ζ n k k Bn ζ n k ⊗ k Bn ζ n k k Bn ζ n k = n k=1 1 |B ′ n (ζ n k )| 2 (k Bn ζ n k ⊗ k Bn ζ n k ) (since k Bn ζ n k 2 = k Bn ζ n k (ζ n k ) = |B ′ n (ζ n k )| by (1.1)). Using the usual formulas (x ⊗ y)(z ⊗ t) = z, y (x ⊗ t), Tr(x ⊗ y) = x, y , we obtain ∆ 1 Bn T Bn [B n /z] = n k=1 1 |B ′ n (ζ n k )| 2 kBn 0 , k Bn ζ n k (k Bn ζ n k ⊗k Bn 0 ) = n k=1 kBn 0 (ζ n k ) |B ′ n (ζ n k )| 2 (k Bn
| Tr ∆ 1 Bn T Bn [B n /z] | ≥ 1 |B ′ n (-1)| 2 - n k=2 1 |B ′ n (ζ n k )| 2 ≥ 4 9 - 1 9π n k=2 1 |B ′ n (ζ n k )| ≥ 4 9 - 1 9π > 1 3 .
Therefore the inequality (7.3) is proved, which concludes the example.

Lemma 1 . 3 .

 13 Fix α ∈ T, and consider for each n the measure µ Bn α . (i) If (1 -|λ j |) = ∞, then µ Bn α converges in the weak star topology to normalized Lebesgue measure. (ii) If (1 -|λ j |) < ∞, then µ Bn α converges in the weak star topology to µ B α , where B = ∞ j=1 (-|λj | λj b λj ) is the infinite Blaschke product with zeros λ j .

Lemma 1 . 4 .

 14 With the above notations, we have µB a α = (b -a ) * (|b ′ -a |µ B α ).

For

  each α ∈ T the reproducing kernels k B ζ α k , k = 1, . . . , N , form an orthogonal base of K B . The operator S α B has as eigenvalues ζ α k (k = 1, . . . , N ), with corresponding eigenvectors k B ζ α k . Consider a measure ν = N k=1 ν k δ ζ α k concentrated on the points ζ α k and define the operator D ν by (2.2)

  Proposition 3.2] Sedlock characterizes the algebra B B α as the set of truncated Toeplitz operators with symbols of the form φ + αS B (Bzφ) = φ + αP B (Bφ), where φ ∈ K B . If B(0) = 0 we have P B (Bφ) = B(φ -φ(0)), and thus Sedlock's result yields the following Lemma. Lemma 3.1. Suppose B(0

Lemma 5 . 1 .

 51 Suppose α ∈ T, ψ = ψ + + Bψ -∈ K B + K B . If u = Bv for some inner function v, and φ = ψ + + ᾱvψ -, then T u [φ + αū(φ -φ(0))] ∈ B uα and, for any 0 < p ≤ ∞, we have

  3, define, for n ≥ 1, B n = n j=1 (-|λj | λj b λj ). The next theorem may be considered the central result of this paper; it gives a Szegö theorem for truncated Toeplitz operators. Theorem 6.1. Suppose (1 -|λ j |) = ∞, B n is defined as above, ψ ∈ C(T), and p ∈ N. Then (6.1)

Lemma 6 . 2 .

 62 Fix N ∈ N, α ∈ T, assume B N (0) = 0, and denote by ζ α n,k , k = 1, . . . , n, the roots of the equation B n (z) = α. Suppose that for each n ≥ N we are given an atomic measure ν n = n k=1 ν n k δ ζ α n,k ; denote by D νn the corresponding diagonal operator as defined by (2.2). Assume that (i) ν n is weakly convergent to some measure ν. (ii) D νn → 0.

  Lemma 5.1 for B = B N and u = B n we obtain that the trace norm T Bn [ψ]-T Bn [ φn ] 1 is bounded by a constant independent of n. Therefore, using condition (ii), | Tr(D νn (T Bn [ψ]) p ) -Tr(D νn (T Bn [ φn ]) p )| ≤

  If we fix N , and choose n ≥ max{j ∈ N :|λ j | = r m , 0 ≤ m ≤ N }, then inf{|B ′ n (ζ) : ζ ∈ T} ≥ N/100.So in this case inf{|B ′ n (ζ)| : ζ ∈ T} → ∞ when n → ∞, and thence ∆ α Bn → 0, for any α ∈ T.

1 2 .have kBn 0 =≡ 1 , so k Bn 0 (ζ n k ) = 1 .

 12011 Bn T Bn [B n /z] = We B n /z, so kBn 0 (ζ n k ) = B n (ζ n k ) ζn k = ζn k ,while k Bn 0 Thus we have arrived at the formula (7.4) Tr ∆ 1 Bn T Bn [B n /z]

1 -λ 2 j1 -λ 2 j|ζ -λ j | 2 . 2

 2222 we assume that the λ j tend sufficiently fast to 1, we may assume that |B ′ n (-1)| ≤ 3/2. To estimate the remaining sum, remember that by Lemma 2.1 (i) we have|B ′ n (ζ)| = n j=1 |ζ -λ j | 2 = 1 + n j=2It follows that for fixed ζ, |B ′ n (ζ)| increases to |B ′ (ζ)|, while for fixed n it increases on both half circles of T as we are getting closer to 1.Finally, we add the assumption that the sequence λ j has been chosen so that |B ′ (ζ)| ≤ 11/10 for all ζ belonging to the arc J that connects e i/10 and e -i/10 and contains -1.Then, for ζ ∈ J, |B ′ n (ζ)| ≤ |B ′ (ζ)| ≤ 11/10, and so, by Lemma 2.1, d dt Arg B n (e it ) ≤ 11/10. Since d dt Arg B n (e it ) ≤ 11/10 for t ∈ [1/10, π], we have | Arg B n (-1) -Arg B n (e i/10 )| ≤ 11/10(π -θ) ≤ 11π/10. Suppose ζ n 2 = e iη2 is the next zero of B n (ζ) = 1 going from -1 towards 1 on the upper semicircle. Then η 2 ∈ (0, 1/10), and, since | Arg B n (-1)-Arg B n (e iη2 )| = 2π, we must have | Arg B n (e i/10 ) -Arg B n (e iη2 )| ≥ 9π/10. But, using Lagrange's formula, there is some point θ 0 ∈ (η 2 , 1/10) such that | Arg B n (e i/10 ) -Arg B n (e iη2 | = iη2 )|, the last inequality being a consequence of 0 < η 2 < θ 0 . Therefore |B ′ n (e iη2 )| ≥ 9π. A similar argument can be used on the lower semicircle. Finally, since |B ′ n (ζ)| increases as we are getting closer to 1, we may conclude that |B ′ n (ζ n k )| ≥ 9π for any k ≥

We may now go to the proof of the main theorem.

Proof of Theorem 6.1. Suppose now ψ ∈ C(T) and p ∈ N. Let ǫ > 0 be given. Corollary 1.7 implies that n (K B -λ 1

where . ∞ is the supremum norm; we assume also that ψ ∞ , ψ N ∞ ≤ M .

Applying now Lemma 6.4 to ψ N , we see that there exists n 0 such that for n ≥ n 0 we have

≤ pM p-1 ǫ.

Using (4.4), we have

The above estimate proves formula (6.1). Suppose now that ψ is real valued and g is continuous on [inf ψ, sup ψ]. Note that T Bn [ψ] is then a bounded self-adjoint operator with spectrum contained in [inf ψ, sup ψ]. Let (P k ) k∈N be a sequence of polynomials that converges to g uniformly on [inf ψ, sup ψ].

By (6.1), for every k we have


Shripad Nadgowda
email: shnadgow@in.ibm.com

Praveen Jayachandran
email: praveen.j@in.ibm.com

Akshat Verma
email: akshatverma@in.ibm.com

I2Map: Cloud Disaster Recovery based on Image-Instance Mapping

Virtual machines (VMs) in a cloud use standardized 'golden master' images, standard software catalog and management tools. This facilitates quick provisioning of VMs and helps reduce the cost of managing the cloud by reducing the need for specialized software skills. However, knowledge of this similarity is lost post-provisioning, as VMs could experience different changes and may drift away from one another. In this work, we propose the I2Map system, which maintains a mapping between each instance and the golden master image from which it was created, consisting of a record of all changes to the instance since provisioning. We motivate that this mapping can aid several cloud management activities such as disaster recovery, system administration, and troubleshooting. We build a host-based disaster recovery solution based on I2Map, which is ideally suited for low cost cloud VMs that do not have access to dedicated block-based storage recovery solutions. Our solution deduplicates changes across VMs and needs to replicate only the unique changes, significantly reducing replication traffic on end hosts. We demonstrate that I2Map is able to deliver on tight recovery time and recovery point objectives of the order of minutes with low overhead. Compared to state-of-the-art host-based recovery solutions, I2Map is able to save 50-87% network bandwidth on the primary data center.

Control overhead: Although, host-based techniques have a low cost and complexity of implementation, they have the disadvantage of having an agent running on each of the VMs. The agent uses network, CPU and memory resources leading to application impact. It is critical to control the overhead incurred by this agent and ensure that running applications are not affected. Handle large files with small changes: Large files (e.g., log files) could undergo few minor changes or additions. How do we avoid transmitting the entire file each time they are modified? Handle high load: When the load is high, the agent should not consume more resources. The overhead needs to be bounded. Handle rapid updates to the same file: Rapid updates are typically correlated with high load. How can we handle rapid updates within the bounded resources? Scaling deduplication: Deduplication often requires centralization. How do we scale deduplication in a cloud with thousands of servers?

I2Map

Introduction

Enterprises are moving their IT infrastructure to cloud in order to gain greater flexibility in acquiring and relinquishing resources on demand, focus on core capabilities, reduce costs and avoid capital lock-in. Despite the obvious advantages of the cloud delivery model, CIOs remain skeptical about its potential with concerns primarily regarding availability. A survey [START_REF]Performance in the cloud[END_REF] attributes increasing customer reluctance to move to the cloud to the problem of poor performance. For instance, outages in Amazon's EC2 and AWS [START_REF]Amazon: Summary of the AWS Service Event in the US East Region[END_REF] have costed companies millions of dollars. While most cloud providers offer high availability services [START_REF]Amazon: Using Amazon Web Services for Disaster Recovery[END_REF][START_REF]IBM: SmartCloud Virtualized Server Recovery[END_REF][START_REF]VMware: vSphere Site Recovery Manager[END_REF][START_REF] Dell | [END_REF], these come at a premium that is unaffordable for many enterprises. Block-based storage replication solutions such as [START_REF]NetApp: Back to Basics: Deduplication[END_REF][START_REF]IBM: Global Mirror Whitepaper[END_REF] require expensive specialized storage controllers, storage area networks, or other hardware. Network-based replication is performed by a separate component from SAN/NAS or the hosts and can work between multi-vendor products. However, these solutions require intelligent switches which are expensive. Highly available cloud services at an affordable cost remains a distant dream. There is a need for solutions that can work with commodity hardware, is cheap, and yet provides good recovery performance.

Host-based solutions [START_REF] Associates | ARCServe[END_REF][START_REF] Neverfail | Continuous Availability Suite: Neverfail Solution Architecture[END_REF] are cheaper and less complex than storage-based or network-based solutions as they can be implemented completely in software. They do not require any specialized hardware. They are usually file-based and asynchronous, and work by trapping and forwarding write changes to the replication target. Their overheads and performance are also typically worse than the other two approaches.

The core idea of this work is to leverage the similarity of virtual machines (VMs) in a data center to provide a low-cost host-based disaster recovery solution. A few standardized 'golden master' images are used to provision VMs in a cloud, to ensure quick provisioning and to reduce management costs. Hence, VMs which are provisioned from the same golden master tend to be similar to one another. However, knowledge of this similarity is lost post-provisioning as instances could be used for different purposes and may drift away from one another. We build I2Map, which maintains a record of all changes to an instance, as a mapping between the instance and the golden master image from which it was provisioned. A light-weight agent running on each VM records all changes and transmits them to a set of aggregators. The aggregators deduplicate these changes across VMs, store only the unique changes, and maintain the mapping for each VM. A snapshot-mirroring technique can then be applied to backup the aggregators on to a remote site. This recovery process allows us to trade-off recovery performance for cost. We evaluate I2Map on representative activities such as installing new software, patching the operating system, and running hadoop-based applications. We demonstrate that individual VMs can receive good recovery performance of a few minutes without having to invest in dedicated and specialized hardware. We conduct a 24-hour highload case study experiment where we recover a failed VM within a recovery time of 20 minutes and having a recovery point of less than 4 minutes. We show that I2Map uses 50-87% lesser network bandwidth on the primary data center compared to the state-ofthe-art host-based recovery solutions.

The image-instance mapping can potentially be used for other applications such as system administration or troubleshooting failures. We discuss these as part of future work in Section 7. For the rest of this paper, we focus on the disaster recovery solution.

The rest of this paper is organized as follows. We provide some background and motivate our problem and solution in Section 2. We present the design of I2Map in Section 3. Section 4 describes our implementation of I2Map and certain optimizations we performed. We evaluate I2Map and report the results in Section 5. Section 6 discusses related work, and Section 7 highlights the limitations and other potential applications of I2Map. We finally conclude this paper in Section 8.

Background and Motivation

The motivation for our work stems from two important trends in cloud computing.

The first trend is increased standardization and automation of IT services delivery in clouds. Virtual servers are created automatically from virtual image templates and managed via standard tools and processes [START_REF] Viswanathan | Rapid adjustment and adoption to MIaaS clouds[END_REF]. Applications are deployed from standard software catalog, which contain standardized version of popular middleware and application software. Cloud computing providers use standardization to drive automation of IT delivery as well as to keep the costs down. It has been widely reported that standardization allows system management costs to be significantly reduced [START_REF]White Paper: Executive Summary[END_REF]. Standardization of virtual image templates, software catalog and management tools lead to high similarity in cloud managed servers. Servers in a data center are already known to exhibit high similarity [START_REF] Campello | Coriolis: Scalable VM Clustering in Clouds[END_REF][START_REF] Jayaram | An Empirical Analysis of Similarity in Virtual Machine Images[END_REF] and standardization increases content similarity in virtual machines even further.

The second trend that drives our work is the increasing use of commodity servers and storage in infrastructure clouds. This helps cloud present a low-cost IT model by achieving significant cost-savings. While there are several block-based disaster recovery solutions [START_REF]Amazon: Using Amazon Web Services for Disaster Recovery[END_REF][START_REF]IBM: Global Mirror Whitepaper[END_REF][START_REF]IBM: SmartCloud Virtualized Server Recovery[END_REF][START_REF] Dell | [END_REF][START_REF]NetApp: Back to Basics: Deduplication[END_REF] that provide replication across different availability zones, they all require high-end servers and storage technologies like SAN. By contrast, clouds often use commodity servers with attached storage. Commodity hardware does not contain enterprise features like high-availability, block-level replication, fault tolerance and these features need to be implemented at cluster management layer. Disaster recovery is a popular system management functionality, which is impacted by use of commodity hardware. Disaster recovery is often characterized by the Recovery Time Objective (RTO) or the time taken to recover a protected server, the Recovery Point Objective (RPO) or the maximum period of data loss, and the impact of replication on application performance. In a low-cost cloud, disaster recovery depends on host-based replication, which leads to high network traffic and impacts application performance.

In this work, we conjecture that standardization-induced similarity in cloud managed servers can significantly improve system management. Virtual servers instantiated from common image templates and with software deployed from a common catalog, share common content. However, current system management technologies work within virtual server boundaries and are unable to leverage this similarity. If we can create a succinct representation of instances as they evolve from a common image template and software catalog, this representation captures the similarity between instances in an instantly usable format. We call this representation an image-instance mapping called I2Map and capture it as a tree, where the master image is the root and each leaf node is a virtual server instance.

We use the I2Map tree to implement improved disaster recovery in low cost clouds. Replicating the I2Map tree to a secondary site is enough to recreate all the virtual servers on the secondary site. Hence, disaster recovery is trivially supported using the I2Map tree. The I2Map tree keeps only one copy of an update even if the update is made across a large number of cloud instances. Hence, the tree automatically eliminates redundancy and reduces network traffic, while replicating the tree on a secondary site. We also design techniques to ensure that the tree can be created without propagating updates from end hosts, leading to low traffic overhead even within the primary site.

Design

In this work, we design and build I2Map, a host-based disaster recovery solution that leverages redundancy in operations across VMs in a data center. We first outline the challenges we faced, describe the I2Map architecture, and then highlight the key design ideas that helped overcome the challenges.

Design Challenges

Identify duplicates across VMs without transferring data: Every write operation incurs an overhead with storage-based deduplication. Network-based techniques deduplicate only across data centers after bytes have been transmitted over the internal network. Host-based replication techniques deduplicate changes only on the backup server. Can we exclude duplicates across VMs without transferring the actual data? In this section, we present the architecture and main components of our I2Map disaster recovery solution. A light-weight agent runs on each VM that continuously monitors and reports meta-information regarding any changes on the VM. Dedicated aggregator machines collect reports from all the VMs, identify duplicates, request for and retrieve unique data from the agents running on the VMs. The aggregators also maintain information regarding which files are contained in each VM. Snapshots of the aggregators are backed up on to a remote site periodically. As copies of the aggregators are available on the remote site, any VM can be easily retrieved using its golden master image and the catalog of changes to the file system for the VM.

The I2Map agent comprises of three components. A file system monitor such as iWatch in Linux, monitors all changes to the file system. A Parser identifies files with changes to their meta-information (such as permissions and ownership) or to their content. A report of these changes (without file content) is sent to the aggregators. Files with changes in content are added to a job queue. The Master module picks up files from the job queue and computes Rabin fingerprints [START_REF] Rabin | Fingerprinting by random polynomials[END_REF]. Rabin fingerprinting creates cryptographic hashes for variable size shift-resistant blocks. The hashes for each block are then transmitted to the aggregators. The Dedup Engine on the aggregator identifies blocks that are unique and requests one of the VMs holding each block to transmit the contents. The Data Handler on the agent receives these requests and transmits all blocks requested from it. The Backup engine on the aggregator maintains the I2Map tree and records the changes to the file system for each VM. Periodically, snapshots of the aggregator are transmitted to a remote recovery site. Recovery for any VM can then be performed on-demand on the remote site. We describe the functioning of each of these modules in detail in Section 4.

Key Design Ideas

We next highlight and discuss certain key design ideas that enabled us overcome the challenges identified in Section 3.1. Two-round data transfer: In order to ensure that duplicate data is not transferred from a protected host, we transfer data from agent to aggregator in a two round scheme. In the first round, fingerprints of file segments are sent to the aggregator. The aggregator maintains a hash index of fingerprints for all data that it has aggregated and requests data only for segments that are not already present in its hash index.

Separating deduplication and replication:

We separate duplicate identification from data replication. Duplicate identification and aggregation of unique data is handled using a two round protocol between agent and aggregator. Data replication to secondary site is performed independently by the aggregators. This allows duplicate elimination to work at LAN speed, while replication can be performed at WAN speed. Variable size duplicate identification: For each file that is written, the agent computes a Rabin fingerprint. Rabin fingerprints are shift-resistant, as the division into variablesize blocks and hash computation is based on the content of each block rather than any fixed offset. The hashes for the various blocks are sent to the aggregator. Therefore, even if a small change is made to a large file, only a small block of data around the change will need to be transmitted to the aggregator. The remaining blocks will be identified by the aggregator as duplicates of blocks already present and will not have to be transmitted. This helps us to reduce the overhead of file-based replication significantly. Pipelining fingerprint computation with data transfer: A two-round protocol can lead to high Recovery Point Objective (RPO), if the rounds were serialized. Further, both rounds may need to perform disk I/O for a file segment. In order to speed up the process of identifying duplicates and aggregating unique data, we pipeline the different operations performed on the agent. The Parser, Master, and Data Handler are implemented as separate threads in order to allow them to progress parallelly acting on different data elements. Further, Master and Data Handler use a producer-consumer cache to minimize disk I/O. Master populates the cache with file segments, when it computes the fingerprints in the first round. In the second round, when Data Handler needs to send data, it reads the file segment from the cache, instead of reading it again from the disk. Change coalescing: The agent's parser module looks ahead and identifies multiple successive writes to a file within a short duration and transmits information only once to the aggregator. This change coalescing helps I2Map deal with rapid updates to a file even during periods of high load. Agent throttling: We allow the agent to be configured with a throttling parameter, in order to ensure that it does not consume too much of the CPU and memory resources of the VM. This further reduces the overhead and ensures that applications that generate high I/O load operate smoothly. Stable aggregator mapping: In order to scale to large data centers, we allow multiple aggregators to be created in I2Map. If multiple agents find common content, duplicate elimination requires all (or at least most) agents to send this content to the same aggregator. Clearly, this requires aggregator mapping to be defined based on content. Further, if a part of the file changes, we would like to send only the changed content to the aggregator. This places a restriction that the aggregator mapping should not change due to a small change in content. In order to deal with these conflicting requirements, we use hash of the first 4KB of a file to map its aggregator. Changes in other parts of the file do not lead to change in aggregator. Also, files across VMs with the same content, map to the same aggregator most of the time, meeting both our requirements.

Implementation

In this section, we describe the implementation of I2Map and highlight important optimizations that helped us keep overhead in check.

I2Map Agent

The agent comprises of three modules as depicted in Figure 1, implemented in Python.

iWatch and Parser

The agent, at its core uses iWatch, a real-time file monitoring utility written in perl, based on iNotify, a file change notification system in the linux kernel. We monitor the entire file system excluding device files and temporary files in folders such as /dev. Whenever a file's contents or metadata (including permissions and ownership) is modified, iWatch generates a log. The Parser module thread checkpoints the log, processes all entries up to the checkpoint, and then zeroes all lines up to the checkpoint. This ensures that the iWatch log file is never too large, and I2Map does not incur the overhead of opening a large file to read.

The Parser computes a hash of the first 4KB of each file that is written. This hash is used to decide which aggregator is in charge of holding the file (we choose the first 4KB only, to ensure content-based stable mapping). The vector space of all the hash values is evenly split among all the aggregators and each aggregator is responsible for managing files with hash values in its vector space. The Parser creates reports, one for each aggregator, with meta-information regarding all changes to files managed by that aggregator. Information regarding files that are deleted are sent to all aggregators, and the aggregator to which the file is relevant can then delete the file. Files that are modified are treated as a delete followed by a create.

The Parser also adds any files that are newly created or have changed in content on to a job queue. The job queue contains the ID of the aggregator responsible for the file along with certain file meta-data. However, before adding the file entry, the Parser takes a peek at the job queue. If an entry already exists for the file, then the Parser skips entering the file again into the job queue. This allows the agent to optimize during periods of rapid writes, when a file is written multiple times in quick succession.

Master

The Parser and the Master share a producer-consumer relationship with respect to the elements in the job queue (Figure 2). The job queue is controlled by a lock and both the Parser and the Master need to acquire the lock before writing to it. The Master picks up each file entry written by the Parser, and computes a Rabin fingerprint for the file, implemented in C. The Rabin fingerprint divides each file into variable-sized blocks based on the content rather than any fixed offset. This makes these blocks shift-resistant, that is, for example changes to the start of a file will not affect all the blocks. The fingerprint consists of cryptographic hash values for each of the blocks. The Master sends the hash values for blocks of each file to the corresponding aggregator, as identified in the job queue. In our implementation, we did not limit the size of the job queue, as we observed that the size never grew beyond 700 entries, with each entry being less than 30 bytes.

In order to ensure that even under high I/O load the agent does not consume too much of the VM's resources, I2Map can be configured with a throttling parameter. For instance, a throttling parameter of 67% would run the agent for 5s and then sleep for the next 10s. In our implementation, we kept the awake time to be constant at 5s, and alter the sleep time based on the throttling parameter. We observed that the Rabin fingerprinting and the actual data transfer were the costliest operations, while the parser was extremely light-weight. A crucial design choice was to selectively throttle the Master and the Data Handler, but not the Parser. Apart from throttling the most time-consuming tasks of the agent, this had the added advantage that any duplicate file writes within the VM would be safely omitted by the parser, as the file has not yet been read by the Master. Separating these modules into parallel threads and having the job queue as a shared resource between them was important to achieve this.

Data Handler

The Data Handler responds to requests from each aggregator, with the content of the specific blocks of files requested by that aggregator. We noticed that we were reading the file twice, once for computing the Rabin fingerprint and a second time for the block transfer. This was adversely affecting performance. To alleviate this problem, we introduced a key-value store cache (Figure 2). When computing the Rabin fingerprint, the Master would write the blocks onto this cache. The Data Handler will look into the cache first for each block, and will read the file system only if it is unable to find the block in the cache. If found, the Data Handler would remove the entry from cache, after use. The Data Handler also removes those entries from the cache, which the aggregator already has and does not require. This ensures that only file segments not yet processed by the Data Handler stay in cache.

This considerably helped improve performance. From our experiments, we observed that typically the cache had about 400-500 entries (even for data-intensive hadoop experiments), with each entry holding a Rabin fingerprint for a block. The lag between computing the Rabin fingerprint and the data transfer was always small enough to keep the cache small. We limited the cache to 1000 entries and Rabin fingerprint blocks were restricted to a maximum size of 64KB, ensuring that the cache had a maximum size of 64MB. Since the workload is scan-based, we never replace unprocessed entries from the cache. Instead, the Master waits till a cache block is made available by the Data Handler. We also conducted a few overload experiments where the cache was fully utilized and tested a few replacement algorithms. We observed that not replacing entries in the cache, if the cache was full performed the best.

When transmitting blocks of requested files to an aggregator, the Data Handler sends at most 500 blocks at a time, to ensure that packet sizes aren't too big. We used a base64 encoding for file transfer as some files, especially those written by hadoop, had certain special characters.

Aggregator

The aggregator consists of two main modules. The Dedup Engine communicates with the agents and identifies blocks that are unique. For each unique block, it requests the contents of the block from one of the VMs holding it. The Backup Engine maintains a record of all the files and blocks (among those managed by this aggregator) contained in each VM. An I2Map tree is constructed for each golden-master image, where the master image is the root, and each leaf node is a virtual machine instance. Edges in the tree represent changes to files. If a set of VMs experience the same changes to files (e.g., a patch is applied), the Dedup Engine would ensure that only one copy of the change is stored. Replicating this tree on a remote site is sufficient for disaster recovery, as any VM can now be recreated by starting with its golden master image.

Interestingly, for the disaster recovery use case, I2Map does not even need to create the entire tree. Instead, what we maintain is a list of instances that are relevant for each update to the tree. For example, if a file got overwritten in 5 instances, we store the change along with the 5 instances, whose I2Map tree contain the change. The I2Map tree is thus stored as a set of nodes (one node for the golden master and one node for each instance). The intermediate nodes, which capture the transition from a golden master to an instance are not stored. Instead, a list of all changes are stored along with the impacted instances. Multiple updates to the same file segment are merged leading to a compact I2Map tree, whose size is proportional to the minimum set of changes needed to convert a golden master to any required instance.

Remote Recovery

The remote recovery site maintains periodic incremental snapshots of all aggregators. Snapshots are taken at 5 minute intervals (a configurable parameter) for each aggregator. We use Linux rsync [START_REF] Tridgell | The rsync algorithm[END_REF] to transmit the snapshots to the recovery site. Prior to taking a snapshot, the aggregator waits for any packets sent on the wire, freezes all operations for an instant, and takes a filesystem dump of the database and tree. This operation, including taking the snapshot, takes less than a second. In the event of a site failure, the aggregators are recreated and the I2Map tree with record of changes to files is used to recreate VMs. We perform incremental recovery by merging updates for each VM periodically (default is 24 hours). This does not require a live VM at the recovery site as only the updates are gathered and stored in an offline VM image. When recovery is triggered, the latest updates are merged and an instance is provisioned from this image.

The Recovery Point Objective (RPO), or the worst-case duration for which recovery cannot be guaranteed, that I2Map can support depends on two factors -the maximum time lag of all agents to send data to the aggregators, and the snapshot interval. The RPO for host failure is the lag between agents and aggregator, whereas the RPO for site failure is the sum of the two lags. We show in our evaluation that I2Map can guarantee an RPO of less than 4 minutes for host failures and an RPO of less than 9 minutes for site failure, sufficient for most non-critical applications (assuming 70 MBps within the primary site, 700-3300 KBps over WAN, and 1 GB data generated per minute).

Aggregators maintain a heartbeat among one another. In the event of an aggregator failure, one of the live aggregators (e.g., a chosen leader) takes up the responsibility of storing content on behalf of the failed aggregator. Agents are intimated accordingly. Recovery is initiated for the aggregator using snapshots on the remote site. Until recovery for the aggregator is complete, the acting aggregator may not be able to perform efficient deduplication. This, however, does not compromise safety of the system.

Evaluation

We evaluate I2Map on a heterogeneous set of 6 VMs running Ubuntu 10.04.2 64-bit. The VMs were hosted on 2 IBM BladeCenter servers, one with 4 cores 2.33GHz and 8GB memory, and the other with 8 cores 3GHz and 16GB memory. The memory and CPU specifications of the VMs are shown in Table 5. We did not set an upper limit to the CPU available for a VM, and it was bounded only by the availability of resources on the server hosting it. The aggregator was run on a physical server with an 8-core 2.27GHz Xeon processor and 16GB memory. Recovery is performed on a server with 24-core 3.07GHz Xeon(R) processor and 64GB memory. The primary site was located in New Delhi and the remote recovery site was located in Bangalore, over 2000kms away. We observed speeds of about 70MBps within the primary site (between the agents and the aggregators). The WAN bandwidth between New Delhi and Bangalore varied with time of the day and was between 700KBps to 3.3MBps. With better network speeds, our recovery performance will only improve. We evaluate I2Map based on several metrics. We define dedup as the ratio of the total bytes written on a VM to the bytes transferred from the VM to the aggregators. 1 -1/dedup captures the reduction in network traffic for each VM by I2Map over state-of-the-art host-based replication solutions. We also define dedup aggr, which is the aggregated measure of the total bytes written across all VMs to the total bytes transferred from all VMs to the aggregator. This is a measure of savings in storage and network transfer within the data center due to I2Map over state-of-the-art techniques. We measure the (time lag) between when a file is written and when it is transmitted to the aggregator (if requested by the aggregator). This measure captures the RPO for host failure and together with the time taken to transfer from the aggregators to the remote recovery node, represents the RPO for site failure. We also measure the CPU and memory utilization (CPU Util and Mem Util) of our agent running on each VM to quantify the overhead of our approach. Finally, in the event of an actual failure of a VM, we measure the recovery time objective (RTO) achieved by I2Map.

Micro Experiments

In this section, we describe micro experiments that we conducted to analyze the performance of I2Map. We chose three common activities in a cloud -namely, software installation from a software catalog, patching VMs in a change window, and running clustered applications, for these experiments.

Software Installation

For this experiment we downloaded and installed two software along with all their dependencies, with a 150s sleep time between the two. This process was repeated in sequence on 6 VMs. We chose freecad, an open source autocad software, and avgscan, an anti-virus scanning software, for their relatively large size and the number of dependencies with other software and libraries. It is possible that some VMs already had the dependent software and didn't need them to be installed. Freecad had a download size of 60.6MB and an install size of 197MB. Avgscan had a download size of about 100MB and a similar install size. The software installation scenario is one where a large number of files are written within a very short duration of time. For each file modified or added on a VM, we monitored the time at which the Parser (iWatch), Master (Rabin), and Data Handler handled the file. We plot this in Figure 3(a) for one of the VMs (other VMs were similar). The difference between the successive operations shows the time lag in executing these steps. Observe that the Freecad installation wrote about 1250 files in about 20s (the iWatch curve), and the data handler was able to catch up with this load at around 170s. The figure also shows that the Rabin fingerprinting and the data transfer took nearly equal amount of time. Avgscan, on the other hand, writes only about 150 files (has bigger files than Freecad). I2Map is able to handle this load better and has a lag of only about 30s, with most of the delay being due to the data transfer. Hence, I2Map is able to achieve an RPO for host failure of less than 3 mins.

Figures 3(b) and (c) show the CPU and memory usage of I2Map during this experiment for one VM. We notice that CPU utilization is below 10% except for a couple of brief spikes and the memory usage is less than 250MB, which for servers today is less than 10% of total available memory. Note that this experiment was run without throttling and the resource consumption can be made even lower with throttling.

We next take a closer look at the time lag of I2Map over the course of the experiment. At any given time instant, the time lag is measured as the amount of time required by I2Map to process and transmit files written up to that time instant, and plotted in Figure 4 for three VMs. The lag increases in spurts when files are written, but then tapers down as I2Map catches up. Unlike vm-1 and vm-3, vm-6 does not have a large spike at the start of the experiment as files were quickly identified as duplicates. However, it has a sharp increase in time lag for the avgscan installation (it was the first to perform it), where it had several files to transmit to the aggregators. These files were identified as duplicates for the other VMs and the experiment concluded earlier for them. Overall, the time lag never increased beyond 160s, which is sufficiently low compared to the aggregator snapshot period and the recovery point objective. We summarize the average lag and the average CPU and memory usage for each of the six VMs in Table 5.1. The average lag is less than 100s, and the average CPU and memory utilization is less than 5% and 170MB respectively. Note that the installation was performed on vm-1 first before the other VMs, and so vm-1 was responsible for transferring most of the data to the aggregators. This was the reason why vm-1 consumed more CPU and memory compared to the other VMs. This is also corroborated in Table 3, which shows for each VM the number of file system change notifications, the number of notifications processed after the Parser eliminated intra-VM duplicates, the number of bytes written to disk and the number of bytes transferred to aggregators. We make several interesting observations. First, while around 1400 unique files were written during the experiment (from Figure 3), 20000-40000 file writes were generated on each VM. However, I2Map only processed less than 3000 notifications for each VM. This justifies our design choice of pipelining and change coalescing for multiple changes to the same file. Any storage-based deduplication technique such as [START_REF]NetApp: Back to Basics: Deduplication[END_REF][START_REF] Dell | [END_REF] incurs an overhead for each of the 20000-40000 file writes. In terms of the number of bytes, observe that vm-1 transmitted only 276MB, compared to the 447MB written to disk. This is primarily due to the division into blocks performed by Rabin fingerprinting and any blocks that did not change would not be transmitted to the aggregators, justifying the use of variable size blocks. The other VMs transfer negligible amounts of data to the aggregator as they were similar to vm-1 and our two-round data transfer protocol helped them eliminate transfer of duplicate data. vm-6 was an exception as it was the first to have avgscan installed. It therefore transmitted an additional 80MB. If every write were to be captured and replicated, like in other host-based solutions, without the 'deduplication before data transfer' feature of I2Map, a total of 2660MB of data would need to be transferred. In comparison, I2Map transfers only 358.6MB of data between the agents and the aggregators, a reduction by a factor of over 7 (dedup aggr).

Patching In our next micro experiment, we apply a set of 55 security patches for Ubuntu on 6 VMs. For one of the VMs, vm-6, 19 of these patches were relevant, while for the other VMs, 49-52 patches were relevant (10 patches were not relevant for at least one VM excluding vm-6). The total download size of the 55 patches was about 480MB, with 4 patches each about 100MB, and 30 patches each less than 500KB. We used Tivoli Endpoint Manager [START_REF]Tivoli Endpoint Manager[END_REF], an endpoint management tool, to apply the patches in an automated fashion. The experiment took between 130 and 170 minutes to complete on each of the VMs. In Figure 5(a) we present the split between when Parser (iWatch), Master (Rabin), and Data Handler process each file for one sample VM, vm-2. Over 3000 files are modified in about 140 minutes. We observe that the time lag is less than 100s most of the time. The CPU utilization is less than 10%, except for a couple of spikes, and the memory usage is less than 120MB as shown in Figures 5(b) and(c). Similar to the software install experiment, Figure 6 depicts the time lag of I2Map over the course of the experiment. As most patches are small in size, we see many small spikes in the time lag. The larger patches take longer to download and are processed in the second half of the experiment with fewer spikes. A summary of the average lag and the average CPU and memory usage for each VM is presented in Table 4. The average time lag is less than 80s for all the VMs. Unlike the software installation experiment, where the first VM transferred all the data to the aggregators, the patches were applied in different orders on the VMs. Hence, the overhead is more or less uniform across all the VMs. Table 5 summarizes the deduplication information for the patch experiment similar to Table 3. The intra-VM deduplication and change coalescing of I2Map reduces the number of writes that need to be processed to about 16000 from about 60000 total writes. This is not as significant a reduction as in the software install case, as the same files are not rewritten multiple times and the time between file writes is longer reducing the amount of intra-VM deduplication possible. The deduplication achieved is mainly due to multiple patches writing the same files. The total data change is split into unique data and dedup data in Table 5. Unique data represents the amount of data that is unique to that VM, and dedup data represents the amount of data that is found in at least one other VM. Observe that a large fraction of the data written on each VM has duplicates. vm-6 is an exception with a larger fraction of unique data. Since, it had only 19 patches relevant, TEM got to apply patches on vm-6 ahead of the other VMs (patches on all 6 VMs were started simultaneously). Hence, a bulk of the data got transferred from vm-6 on to the aggregators, serendipitously achieving load-balancing. The total amount of data transferred to the aggregators was 708MB, only a half of the 1440MB (1281MB + 159MB) of total data written across all the VMs (dedup aggr = 2.03).

Hadoop Sort Our third and final micro experiment is with running the Hadoop Teragen-Terasort application on a cluster of 5 VMs. Terasort is a distributed sort algorithm on 1GB data, that is created by Teragen. The sorted data is written separately from the input data. Hadoop uses a distributed file system that is append-only. This creates a challenge for I2Map as it creates and appends data on to large files. It waits until a block reaches 64MB and then writes the block to disk. Further, we employ triple replication of data within Hadoop's file system, so the experiment wrote 6GB of data in all by the end of the experiment. Identifying and leveraging this replication is critically dependent on the shift-resistant blocks created by the fingerprint. The triple replication also means that a tremendous amount of data is written within a very short amount of time, stress testing both the disk as well as I2Map. If ineffective, we may end up transferring a lot of duplicate data. Unless specified otherwise, we use a default value of 67% throttling for this experiment, where the agent is awake for 5s and then sleeps for 10s. We observe from Figure 7(a) that the time lag never exceeds 100s. This is better compared to the install and patch experiments as data writes are more or less uniform and don't happen in a burst. However, CPU and memory usage are higher as observed in Figures 7(b) and(c). This can be attributed to the larger file sizes, the append-only behavior of hadoop, and the triple replication (the total amount of data written during this experiment is 6GB in about 450s). Figure 8 shows the time lag as a function of the process time for one VM for different values of the throttling parameter. The lag uniformly increases till about 80s. Then, we observe a pause in file writes till about 225s, as hadoop gathers data till it can write 64MB blocks. This is followed by another set of writes. More strikingly, increasing the throttling does not discernably increase the time lag, suggesting that much of the lag is due to the network transfer between the agent and the aggregators. This is encouraging as a better network would help reduce the overhead of I2Map.

Table 6 shows the average lag and overhead for each of the VMs and the aggregator for the above experiment. The average lag is more or less uniform and less than 60s for all the VMs. vm-4 handled the maximum data transfer (as we show in Table 8), which explains the higher lag and overhead seen. The aggregator doesn't perform any file based computations, and only needs to dedup file blocks and receive data from the agents, leaving it with a relatively low memory footprint, but a higher CPU consumption. Even at such a high load, one aggregator can handle 17 agents without throttling and up to 25 agents with throttling, which is an acceptable management overhead (the system can easily scale by adding more aggregators as needed). The above experiment was conducted with the default throttling value of 67%. We ran the experiment with 50% (5s wake and 5s sleep) and 75% (5s wake and 15s sleep) throttling, the results of which are presented in Table 7. The average overhead values typically decrease as we increase throttling, but is not strictly the case. This aberration is an artifact of how hadoop assigns jobs to nodes and is not something we can explicitly control. While the overall CPU and memory utilization can be reduced using throttling, we observe that the time lag increases only marginally for increasing throttling values. We summarize the deduplication information for the 5 VMs in Table 8. As noted earlier, this experiment has significantly fewer file writes, but each write is for a large chunk of data. This would mean that we will need to process most of the file writes as they are sufficiently separated in time from one another. The effectiveness of I2Map is demonstrated by the high volume of data in each VM identified as duplicate with at least one other VM. Further, compared to the total amount of data generated, 8163.7MB, the amount of data actually transferred is only 2103MB across all VMs, which is a reduction by a factor of 3.88 (dedup aggr). Summary Our micro-benchmark experiments establish the effectiveness of I2Map. We are able to ensure an RPO of less than 3 minutes for VM and host failure, reduce the replication traffic by a factor of 2 to 7.5 (dedup aggr), while using less than 5% CPU and 400MB memory during periods of intense I/O loads. The reduction in replication traffic translates into network bandwidth savings of 50 -87% (1 -1/dedup aggr) in the primary data center, compared to state-of-the-art host-based recovery solutions. We are able to reduce the number of file changes we process by a factor of 2 to 10 due to change coalescing and need only 1 aggregator per 25 managed VMs. While our experiments were conducted with 6 VMs, having a larger pool of VMs using I2Map will only increase the deduplication possible. Under normal operation, we believe we can achieve even better performance at lower resource overheads.

Case Study

We conducted a 24 hour case study where we mimicked a real-world scenario where an application is running continuously at high load, is then brought down, the operating system is patched, rebooted, and the application is restored once again. At the end of the 24 hours we artificially failed one VM, which triggered recovery. In this section, we report results from this experiment, including I2Map's recovery performance. We successively ran Teragen-Terasort on hadoop on the 6 VMs. Between every two runs of Teragen-Terasort we added a think time derived from a lognormal distribution with a mean of 120s. About 19 hours into the experiment, we brought down the hadoop application and started patching the VMs. This patch experiment was similar to the micro-experiment that we conducted, and lasted about 3 hours. Once patching of all VMs completed, we rebooted the VMs and restored the hadoop application. A Gannt chart showing the duration of each hadoop run and the think time between them is plotted in Figure 5.2. Overall, the hadoop-based application was running for 87.6% of the time. This is a very high load (as most enterprise systems run at a load of about 25%), created to stress-test I2Map. Notice the long sleep time between about 1150 and 1330 minutes, which was when the patching experiment was conducted.

Figure 10 shows the average and maximum time lag for agents to transfer files to the aggregator, as well as the average CPU and memory usage for each VM. We observe that the average lag is less than 1.5 minutes and the maximum lag at any instant is about 4 minutes. Thus, I2Map is able to achieve an RPO for host failures of approximately 4 minutes, even during periods of high write load. Including the time to transmit snapshots to the recovery site, the RPO for site failures is less than 9 minutes. This is very competitive compared to a best guarantee of 15 minutes provided by many commercial disaster recovery solutions [START_REF]VMware: vSphere Site Recovery Manager[END_REF][START_REF] Dell | [END_REF]. The average CPU usage was under 1% for all the VMs, and the memory usage was less than 140MB. Despite heavy load from the hadoop application, I2Map was able to operate with minimal overhead on the agents.

Snapshots of the aggregator were taken every 5 minutes and transmitted to the remote recovery site using Linux rsync [START_REF] Tridgell | The rsync algorithm[END_REF]. Figure 11(a) shows the snapshot lag, the duration of time between when a snapshot was taken and when it was fully saved on the remote site, for each snapshot. This is primarily the delay over the network between the primary site and the remote backup site. Observe that the maximum lag is about 7.5 minutes, which happens whenever a new run of hadoop is started and Teragen generates new data. For most snapshots the lag is negligible. Figure 11(b) shows the amount of data transferred for each incremental snapshot, which is about 1 -1.7 GB for the large spikes. Most snapshots transmit only about 100MB of data. The total data transferred across the Delhi-Bangalore WAN during the course of the experiment was about 26GB.

In comparison, the total data written on all the 5 VMs taken together was about 70GB. The total aggregated deduplication dedup aggr can be calculated as 70/26 = 2.69. At the end of 24 hours, we artificially failed a VM, which triggered recovery on the remote site. We mounted a copy of the golden master image corresponding to the VM, identified files belonging to the VM, and wrote their current version on to the mounted copy. This recovered the VM to its last known state. This process involved writing 14.88GB of data and took 719s, at 21.19MBps. If a snapshot was being transferred to the remote site when the VM failed, then recovery may be delayed until completion of the transfer, adding up to 8 minutes to the recovery time. Hence, the total recovery time achieved by I2Map for this experiment can be estimated as 12 -20 minutes for a VM with plenty of writes, which is highly competitive with commercial DR solutions.

Related Work

Disaster recovery, as a concept, has existed for over three decades. Today, it forms the cornerstone of business continuity and every major IT service provider has a disaster recovery solution. These solutions require NAS/SAN arrays, storage controllers, smart network switches, or other specialized hardware. With the gaining popularity of the cloud, enterprises are looking to reduce their IT-spend and disinvest in hardware. In a bid to meet the expectations of their clients, cloud service providers are building lowcost clouds using commodity off-the-shelf hardware. In this section, we discuss the pros and cons of various replication and disaster recovery technologies. They can be broadly classified into storage-based, network-based, and host-based solutions.

There are several storage-based recovery solutions for cloud. Block-based storage replication requires expensive NAS/SAN arrays and storage controllers. But, they have the advantage of being independent of the operating system running on the server. Amazon's AWS provides multiple disaster recovery solutions that use Amazon S3 for backup [START_REF]Amazon: Using Amazon Web Services for Disaster Recovery[END_REF]. These are either snapshot-based or storage replication solutions and do not perform any deduplication across VMs. IBM's GlobalMirror [START_REF]IBM: Global Mirror Whitepaper[END_REF] provides an extremely high-end disaster recovery solution. It replicates all updates over a SAN and provides an RPO of 3-5 seconds. Other examples are VMware's Site Recovery Man-ager [START_REF]VMware: vSphere Site Recovery Manager[END_REF] and IBM's SmartCloud Virtualized Server Recovery [START_REF]IBM: SmartCloud Virtualized Server Recovery[END_REF]. Notably, the lowest RPO guarantee provided by VMware's Site Recovery Manager [START_REF]VMware: vSphere Site Recovery Manager[END_REF] is 15 minutes. We have demonstrated that I2Map's host-based solution can provide a comparable RPO, perform deduplication, and work using commodity hardware.

There are several disaster recovery solutions that do perform different kinds of deduplication. Dell's AppAssure [START_REF] Dell | [END_REF] deduplicates and compresses data on the WAN while replicating storage disks. We argue that deduplicating data on the WAN is still too late as costly storage and network resources are consumed within the primary data center to support disaster recovery. NetApp's storage solutions [START_REF]NetApp: Back to Basics: Deduplication[END_REF] are specialized storage devices that perform deduplication using the Data ONTAP operating environment and the WAFL file system. They report that each write operation incurs a 7% additional overhead, in return for considerable savings in storage, which also translates into lower network bandwidth consumed when replicating the data across a WAN, using their SnapMirror solution [START_REF] Patterson | Snapmirror: File system based asynchronous mirroring for disaster recovery[END_REF]. However, deduplication can only be performed across VMs stored on the same storage device and comes with the cost burden of additional specialized hardware.

Network-based disaster recovery solutions perform deduplication on the bytes transmitted over the network. While useful, they do not leverage deduplication within the primary data center. Individuals VMs or servers are still required to transmit all their data across the local network. Some examples include Riverbed [START_REF]Riverbed Technologies: Riverbed Whitewater WAN Optimization and Steelhead Cloud Storage[END_REF] and EMC's Re-coverPoint [START_REF] Emc | EMC RecoverPoint Support for Cisco MDS 9000 SANTap Service: Intelligent Fabric-based Data Replication[END_REF]. Citrix cloud solution for disaster recovery [START_REF]Citrix: Citrix Cloud Solution for Disaster Recovery[END_REF] uses a combination of storage-based and network-based optimizations.

Host-based solutions have the advantage of not requiring specialized hardware and not locking the user into using a specific kind of storage device. Disadvantages include solution being dependent on the operating system used and having an agent running on the host and using its computing resources. Examples of existing solutions include CA's ARCserve [START_REF] Associates | ARCServe[END_REF] and Neverfail [START_REF] Neverfail | Continuous Availability Suite: Neverfail Solution Architecture[END_REF]. Neither of them perform deduplication on the primary data center. While ARCserve performs deduplication of data on the backup server (after the individual VMs have transmitted all their data), Neverfail uses what they call WANsmart in-line data deduplication, a form of network-based deduplication.

The concept of transmitting only the incremental changes relative to a base VM and dynamically synthesizing them at the time of provisioning has been used in the context of Cloudlets [START_REF] Ha | Just-in-time provisioning for cyber foraging[END_REF]. VM-based cloudlets have been proposed as offload sites for resource intensive or latency sensitive computations for mobile multimedia applications. The technique in [START_REF] Ha | Just-in-time provisioning for cyber foraging[END_REF] works by creating a binary difference between VM images, which is computed only on-demand when required. This is not a disaster recovery solution where continuous monitoring and data replication is desired.

In summary, there are a wide range of disaster recovery solutions that use a variety of technologies, have different requirements, and support different RTO and RPO guarantees. However, these solutions do not cater to the express need of low-cost clouds to support an efficient disaster recovery solution that can perform effective and early deduplication within and across VMs without transferring data, and work with commodity hardware. The I2Map disaster recovery solution presented in this paper addresses this concern, and its various optimizations ensure a competitive RPO and RTO guarantee along with low overhead on the VMs.

The disaster recovery solution presented in this paper caters to a specific need for having a low-cost, low-overhead solution that can work with commodity hardware. However, it does have its limitations. As with other host-based solutions, it requires an agent to be running on each VM, using up its computing resources. While we have demonstrated that the overhead can be contained to less than 5%, for many security-critical applications it may be inadmissible to have an agent (trusted as it might be) running on the VM. I2Map is not suitable for such applications. A majority of system management tools require agents (e.g., for monitoring, patching, backup) and we believe that having a well-tested agent with minimal performance impact may be acceptable to a large fraction of customers. Also, if the data is encrypted in the file system, I2Map will be unable to perform deduplication across VMs effectively. Security over the network is another issue faced by all DR solutions. This can be overcome by adding a layer of encryption before transmitting over network. Further, our current implementation of I2Map works only for linux-based VMs and new agents need to be developed for supporting any other operating systems.

Another issue that we have not investigated in this paper is the requirement and load on aggregators. If we were to scale up our disaster recovery solution to several hundred VMs, we may need more aggregators. This is an additional cost burden and we need ways to reduce the number of aggregators needed. The two round data transfer using aggregators does have its advantages, as it ensures that duplicate data is not transferred from protected hosts. Further, the aggregators separate the protected hosts from any WAN overheads, in case the transfer over the WAN were to be slow. As part of future work, we intend to study the costs and benefits of aggregators, especially at scale.

A limitation of all DR solutions (including I2Map) is that they only recover the state of the disk and not the memory. The state of memory is far more dynamic and one would have to quiesce any running applications in order to get a snapshot of memory. This is done in certain scenarios (e.g., live migration of a VM), but would be prohibitively expensive to perform on a regular basis and is not required by I2Map.

The notion of similarity captured by the I2Map tree can be used for performing other data center management tasks as well. The first is in troubleshooting software failures. For instance, system administrators routinely apply software upgrades and patches on a large set of VMs in the data center. If some of these upgrades fail, they have no clue to the cause of the failure. Analyzing the I2Map tree for similarities and differences between VMs could provide crucial insight into why the upgrade might have failed, and could even provide clues to how the situation can be remedied. Second, similarity between VMs as captured by the I2Map tree can also be used in assigning admins to VMs in a data center. Each admin could manage their VMs better, if they were all similar and had the same software. We intend to explore these applications of I2Map in our future work.

Conclusion

In this paper, we present I2Map, a host-based disaster recovery solution. I2Map leverages similarity across VMs in a data center and performs intra-and inter-VM deduplication to reduce the overhead of the solution. It maintains a mapping between instances and the golden master image from which it was created as an I2Map tree, which captures all the changes to the instance with respect to the master image. Unlike existing disaster recovery solutions, I2Map does not require any expensive specialized storage devices or hardware. It separates deduplication and replication, allowing deduplication to be performed even before any data is transferred from a protected host. Extensive evaluation demonstrates that I2Map provides competitive recovery point and recovery time objective of the order of minutes, with low overhead.

Fig. 1 .

 1 Fig. 1. Architecture of I2Map.

Fig. 2 .

 2 Fig. 2. Detailed Design of I2Map Agent

Fig. 3 .

 3 Fig. 3. (a)Time plot showing the split between iWatch, Rabin, and data transfer on vm-1 (b) CPU Utilization (c) Memory Usage

6 Fig. 4 .

 64 Fig. 4. Time lag vs process time plot for three VMs.

Fig. 5 .

 5 Fig. 5. (a) Time plot showing the split between iWatch, Rabin, and data transfer on vm-2 (b) CPU utilization (c) Memory usage

6 Fig. 6 .

 66 Fig. 6. Time lag vs process time plot for 3 VMs.

Fig. 7 .

 7 Fig. 7. (a) Time plot showing the split between iWatch, Rabin, and data transfer on vm-2 (b) CPU Utilization (c) Memory Utilization

Fig. 8 .

 8 Fig. 8. Time lag vs process time plot for different values of throttling agent process.

Fig. 9 .

 9 Fig. 9. Gannt chart showing duration of each hadoop run during the case study experiment.

Fig. 10 .

 10 Fig. 10. Average time lag, and overhead for each VM.

Fig. 11 .

 11 Fig. 11. Snapshot Backup Lag and Data Transfer.

Table 1 .

 1 Virtual Machine Specifications

	VM-ID Memory (MB) vCPUs CPU Reservation
	vm-1	1024	4	0
	vm-2	2048	2	684
	vm-3	2048	2	684
	vm-4	2048	2	1500
	vm-5	3072	4	2300
	vm-6	3072	2	0

Table 2 .

 2 Average time lag and overhead for each VM.

	VM-ID Avg Lag (sec) Avg %CPU Avg Mem (MB)
	vm-1	78	4.97	170
	vm-2	52	1.30	33
	vm-3	100	2.81	148
	vm-4	88	3.80	114
	vm-5	82	1.65	67
	vm-6	64	2.41	170

Table 3 .

 3 Comparison of dedup values with and without removing duplicate writes for each VM.

Table 4 .

 4 Average time lag, and overhead for each VM.

	VM-ID Avg Lag (sec) Avg %CPU Avg Mem (MB)
	vm-1	58	1.14	106
	vm-2	69	1.24	148
	vm-3	75	0.98	94
	vm-4	65	1.19	143
	vm-5	46	1.80	207
	vm-6	72	1.05	112

Table 5 .

 5 Comparison of dedup values with and without removing duplicate writes for each VM.

	VM-ID Total FS Notifications Processed Notifications Unique Data (MB) Dedup Data (MB) Transferred Data (MB) Dedup
	vm-1	63017	16990	10	212	38	5.84
	vm-2	32877	10038	10	124	62	2.16
	vm-3	62533	16789	13	209	101	2.20
	vm-4	63064	16916	10	199	36	5.81
	vm-5	55000	15112	10	184	74	2.62
	vm-6	58323	3890	106	353	397	1.16
	Total			159	1281	708	2.03

Table 6 .

 6 Overhead for each VM and on aggregator.

	VM-ID Avg Lag (sec) Avg %CPU Avg Mem (MB)
	vm-1	41	2.46	360
	vm-2	33	1.33	257	Avg %CPU Avg Mem (MB)
	vm-3	38	2.02	363	36.86	103
	vm-4	59	8.91	361
	vm-5	50	2.86	257

Table 7 .

 7 Average time lag for different values of throttling agent process.

		Throttle 50%	Throttle 75%
	VM-ID Avg Lag (sec) %CPU Avg Lag (sec) %CPU
	vm-1	35	2.64	43	1.43
	vm-2	37	1.91	39	1.80
	vm-3	46	5.95	64	7.78
	vm-4	51	3.36	62	1.67
	vm-5	53	3.30	61	2.03

Table 8 .

 8 Comparison of dedup values with and without removing duplicate file writes on VM.

	VM-ID Total FS Notifications Processed Notifications Unique Data (MB) Dedup Data (MB) Transferred Data (MB) Dedup
	vm-1	93	67	0.66	910	90	10.11
	vm-2	135	79	0.02	1136	270	4.20
	vm-3	132	85	0.02	1617	67	24.13
	vm-4	90	69	0.03	1174	669	1.75
	vm-5	188	139	0.02	3326	1007	3.30
	Total			0.7	8163	2103	3.88