Florent Jacquemard

Pierre Donat-Bouillud

Jean Bresson

A Term Rewriting based Structural Theory of Rhythm Notation Research report -ANR-13-JS02-0004-01

We present a tree-based symbolic representation of rhythm notation suitable for processing with purely syntactic theoretical tools such as term rewriting systems or tree automata. Then we propose an equational theory, defined as a set of rewrite rules for transforming these representations. This theory is complete in the sense that from a given rhythm notation the rules permit to generate all notations of equivalent durations. It can be used to explore the space of Using complementary tree automata formalisms, one can restrict the search space according to notations preferences regarding e.g. metre or other user defined syntactic constraints.

Introduction

Term Rewriting Systems (TRSs) [START_REF] Dershowitz | Rewrite systems[END_REF] are well established formalisms for tree processing (transformation and reasoning). With solid theoretical foundations, they are used in a wide range of applications, to name a few: automated reasoning, natural language processing, foundations of Web data, etc. TRSs perform in-place transformations in trees by the replacement of patterns, as defined by oriented equations called rewrite rules. They are a classical model for symbolic computation, used for rule-based modeling, simulation and verification of complex systems or software (see e.g. the languages TOM 3 and Maude4 ). Tree Automata (TAs) [START_REF] Comon | Tree Automata Techniques and Applications[END_REF] are finite state recognizers of trees which permit to characterize specific types of tree-structured data (regular tree languages). They are often used in conjunction with TRSs, acting as filters in the explorations of sets of trees computed by rewriting.

It is also common to use trees to represent hierarchical structures in symbolic music (see [START_REF] Rizo | Symbolic music comparison with tree data structures[END_REF] for a survey). For instance, the GTTM [START_REF] Lerdahl | A Generative Theory of Tonal Music[END_REF] uses trees to analyse inner relations in musical pieces. Trees are also a natural representation of rhythms, where durations are expressed as a hierarchy of subdivisions. Computer-aided composition (CAC) environments such as Patchwork and OpenMusic [START_REF] Assayag | Computer Assisted Composition at Ircam : PatchWork and OpenMusic[END_REF][START_REF] Bresson | OpenMusic: Visual Programming Environment for Music Composition, Analysis and Research[END_REF] use structures called rhythm trees (RTs) for representing and programming rhythms [START_REF] Agon | Representation and Rendering of Rhythm Structures[END_REF]. Such hierarchical, notation-oriented approach (see also [START_REF] Rizo | Symbolic music comparison with tree data structures[END_REF]) is complementary to the performance-oriented formats corresponding to the MIDI notes' onsets and offsets in standard computer music systems. It also provides a more structured representation of time than music notation formats such as MusicXML [START_REF] Good | Lessons from the Adoption of MusicXML as an Interchange Standard[END_REF] or Guido [START_REF] Hoos | Representing Score-Level Music Using the GUIDO Music-Notation Format[END_REF], where durations are expressed with integer values. As highly structured representations, trees enable powerful manipulation and generation processes in the rhythmic domain (see for instance [START_REF] Haddad | Livre Premier de Motets: The Concept of TimeBlocks in OpenMusic[END_REF]), and enforce some structural constraints on duration sequences.

In this paper, we propose a tree-structured representation of rhythm suitable for defining a set of rewriting rules (i.e. oriented equations) preserving rhythms, while allowing simplifications of notation. This representation bridges CAC rhythm structures with formal tree-processing approaches, and enables a number of new manipulations and applications in both domains. In particular, rewriting rules can be seen as an axiomatization of rhythm notation, which can be applied to reasoning on equivalent notations in computer-aided music composition or analysis.

After some preliminary definitions in Section 1, we introduce our tree representations of rhythms in Section 2. Section 3 presents the rewriting rules proposed based on this representation, and Section 4 finally states some properties of this general representation framework.

Preliminary Definitions

Let us assume given a countable set of variables X , and a ranked signature Σ which is a finite set of symbols, each symbol being assigned a fixed arity. We denote as Σ p the subset of Σ of symbols of arity p.

Trees. A Σ-labelled tree t (called tree for short in the rest of the paper) is either a single node, called root of t and denoted by root(t), labeled with a variable x ∈ X or one constant symbol of a 0 ∈ Σ 0 , or it is made of one node also denoted by root(t) and labeled with a symbol a ∈ Σ n (n > 0), and of an ordered sequence of n direct subtrees t 1 , . . . , t n .

In the first case, the tree t is simply denoted x or a 0 . In the second case, t is denoted a(t 1 , . . . , t n ), root(t) is called the parent of respectively root(t 1 ), . . . , root(t n ), and the latter are called children of root(t). Moreover, for all i,

1 < i ≤ n, root(t i-1 ) is called the previous sibling of root(t i ). For 1 ≤ i ≤ p, the previous cousin of root(t i ) is either -root(t i-1 ) if i > 1, or
the last children of the previous cousin of the parent root(t) if i = 1 and if this node exists.

Note that a tree has a previous cousin iff it has a super-tree. In other terms, the previous cousin of a node ν in a tree t is the node immediately at the left of ν in t, at the same level. A node in a tree t with no children is called a leaf of t. In the following, we will consider the sequence of leaves of a tree t as enumerated by a depth-first-search (dfs) traversal. The set of trees built over Σ and X is denoted T (Σ, X ), and the subset of trees without variables T (Σ). The definition domain of a tree t ∈ T (Σ, X ), denoted by dom(t), is the set of nodes of t. The size |t| of t is the cardinality of dom(t). Given ν ∈ dom(t): t(ν) ∈ Σ ∪ X is the label of ν in t, t| ν is the subtree of t at node ν, t[t ] ν is the tree obtained from t by replacement of t| ν by t . We define the depth of a single-node tree x or a 0 as 0 and the depth of a(t 1 , . . . , t n ) as 1+ the maximal depth of t 1 , . . . , t n .

Pattern Matching. We call pattern over Σ a finite sequence of trees of T (Σ, X ) of length n ≥ 1, denoted as t 1 ; . . . ; t n (the symbol ; denotes the cousin relation). The size of a pattern is the sum of the sizes of its constituting trees.

A substitution is a mapping from variables of X into trees of T (Σ, X ) with a finite domain. The application of substitutions is homomorphically extended from variables to trees and patterns: σ a(t 1 , . . . , t p ) = a σ(t 1 ), . . . , σ(t p ) and σ t 1 ; . . . ; t n = σ(t 1 ); . . . ; σ(t n ).

A tree t matches a pattern t 1 ; . . . ; t n at node ν with substitution σ if there exists a sequence of successive cousins ν 1 , . . . , ν n in dom(t) such that ν 1 = ν and t| νi = σ(t i ) for all 1 ≤ i ≤ n. When there exists such a sequence of cousins, we write t[t 1 ; . . . ; t n ] ν for the iterated replacement t[t 1 ] ν1 . . . [t n ] νn .

Term Rewriting. A rewrite rule is a pair of patterns of same length denoted 1 ; . . . ; n → r 1 ; . . . ; r n and a tree rewrite system (TRS ) over Σ is a finite set of rewrite rules over Σ.

A tree s ∈ T (Σ, X ) rewrites to t ∈ T (Σ, X ) with a TRS R over Σ, denoted by s --→ R t (R may be omitted when clear from context) if there exists a rewrite rule 1 ; . . . ; n → r 1 ; . . . ; r n ∈ R, a node ν ∈ dom(s) and a substitution σ over Σ such that s matches 1 ; . . . ; n at ν with σ and t = s[σ(r 1 ); . . . ; σ(r n )] ν . The reflexive and transitive closure of --→ R is denoted by --→ * R , and the reflexive, symmetric and transitive closure by ← --→ * R . This definition strictly generalizes the standard notion of term rewriting [START_REF] Dershowitz | Rewrite systems[END_REF], which corresponds to the particular case of rewrite rules with patterns of length one (i.e. trees). Our notion of rewriting cousin-patterns can be captured by extensions of rewriting such as the spatial programming language MGS [START_REF] Bigo | Self-assembly of musical representations in MGS[END_REF].

Tree Automata. A tree automaton (TA, [START_REF] Comon | Tree Automata Techniques and Applications[END_REF]) A over a signature Σ is a tuple Q, Σ, F, ∆ where Q is a finite set, disjoint from Σ, of state symbols with arity 0, F ⊆ Q is the subset of final states and ∆ is a set of standard rewrite rules of the form: a(q 1 , . . . , q n ) → q, where a ∈ Σ n , and q 1 , . . . , q n , q ∈ Q. The language L(A, q) of A in the state

q ∈ Q is the set of trees t ∈ T (Σ) such that t --→ * ∆ q. The language of A is L(A) = q∈F L(A, q).
A set of trees L ⊆ T (Σ) is called regular if it is the language of a TA. The class of regular tree languages is effectively closed under union (construction by disjoint union of TAs), under intersection (construction by Cartesian product of TAs) and under complementation (by determination with a subset construction and inversion of final and non-final state sets). Given a TA A and a tree t, it is decidable in polynomial time whether L(A) = ∅ and whether t ∈ L(A).

Ranked Tree Representation of Rhythm Notation

We propose a tree-structured representation of rhythms based on a special ranked signature. well suited for processing with term rewriting systems

Signature

We consider a particular signature Σ rn for expressing rhythm notations. It contains the following symbols of arity zero (constant symbols): n (representing a note), r (rest), s (slur), d (dot), and o (for composition of durations, as explained below). Moreover, Σ rn contains a subset P of symbols denoted as prime integers, each p ∈ P having arity p, and a copy P = {p | p ∈ P}, where p has also arity p. More precisely, P is assumed to contain a (small) prime integer max(P), assumed fixed throughout the paper, and all prime numbers smaller than max(P), i.e. P = {2, 3, 5, . . . , max(P)}. Typically, max(P) = 11. The symbols of P ∪ P will be used to build tuplets defined by equal subdivision of a duration. We shall also use below a set Θ rn of auxiliary symbols for intermediate computation steps. It contains δ i p for all p ∈ P and 0 ≤ i < p, of arity p, and γ i p for all p ∈ P and 1 ≤ i ≤ p, of arity p -i + 1, α i for all i ≤ max(P) and # of arity 1, ⊥ and Err of arity 0.

Tree Semantics

Intuitively, a tree of T (Σ rn ) represents a sequence of notes and rests, denoted by symbols n and r in the leaves, their duration being encoded in the structure of the tree. The symbols s and d are used to group the durations of successive leaves. The symbol o is used to group the durations of successive cousins, and possibly further subdivise the summed duration.

Formally, given a tree t ∈ T (Σ rn , X ), we associate recursively a duration value, denoted dur t (ν), to each node ν ∈ dom(t) as follows:

-If ν = root(t), then dur t (ν) is a number of beats n ≥ 1 associated to t (t can represent e.g. one or several beats or a whole bar). -Otherwise, let ν 0 be the parent of ν in t and let p be the arity of t(ν 0 ), dur t (ν) = dur t(ν0 ) p + cdur t (ν), where

• cdur t (ν) = dur t (ν ) if ν has a previous cousin ν such that t(ν ) = o, • cdur t (ν) = 0 otherwise.
A tree t ∈ T (Σ rn ) \ {o} represents a sequence val (t) of durations. Let k ≥ 1 be the number of leaves of t not labeled by o and let ν 1 . . . , ν k be the enumeration of these leaves in dfs. The duration sequence of t is defined as ds(t) = t(ν 1 ), dur t (ν 1 ) , . . . , t(ν k ), dur t (ν k ) . Let i 1 , . . . , i +1 ( ≥ 0) be an increasing sequence of indices defined as follows: i 1 = 1, i 2 , . . . , i is the subsequence of indices of nodes in {ν 2 . . . , ν k } labeled by n or r, i +1 = k + 1.

The rhythmic value val (t) of t is the sequence of pairs u 1 , . . . , u , where for each j, 1 ≤ j ≤ ,

u j = t(ν ij ), i=ij+1-1 i=ij dur t (ν i )
According to this definition, the first component of each pair u j is either n or r, and the second component is the sum of the durations of next leaves labeled by s or d. For convenience, we shall omit the first components of pairs, and denote val (t) as a sequence of durations, where the duration of rests r are written in brackets to distinguish them from durations of notes n. Example 4. Examples of the interpretation of s and d in terms of notation are given in Figure 3. In the tree 3(a), a note of duration 1 2 is dotted, extending its duration to 3 4 . The rhythm value of 3(b) and 3(c) is the same as for 3(a), but the notation 3(a) is more recommended (see [START_REF] Gould | Behind Bars: The Definitive Guide to Music Notation[END_REF]). ♦ We define as equivalent the trees representing the same actual rhythm.

Definition 1. Two trees t 1 , t 2 ∈ T (Σ rn ) are equivalent iff val (t 1 ) = val (t 2 ).
The tree equivalence relation is denoted t 1 ≡ t 2 . This notion of equivalence makes it possible to characterize different notations of the same rhythm, like e.g. the trees (a), (b) and (c) in Figure 3.

Interpretation of Trees into Common Western Notation

Our tree representation has been integrated in OpenMusic [START_REF] Bresson | OpenMusic: Visual Programming Environment for Music Composition, Analysis and Research[END_REF] with conversion functions to and from RT. We are also planning conversion to GUIDO and MusicXML. The previous examples showed how the interpretation of trees of T (Σ rn ) as Common Western Notation is generally straightforward. We describe here some aspects that need particular treatments. We have already said a few words about the case of dots (symbol d), see Example 4. Let us present below another example about tuplets beaming using the symbols of P.

Note that the above semantics make no difference between the symbols of P and P. The symbols of P are actually used to provide information on rendering beams when converting trees to musical notation.

Example 5. Figure 4 presents different ways of beaming a sextuplet (see [START_REF] Gould | Behind Bars: The Definitive Guide to Music Notation[END_REF]). The three trees are equivalent. In 4(b) and 4(c) the division is respectively bipartite and tripartite. In 4(a), the division is unclear. The symbols 2 and 3 ∈ P at the top of the trees 4(b) and 4(c) indicate that there must be only one beam between subtrees (the value one corresponds to the depth of 2 and 3). The default rendering, in 4(a), with label 3 ∈ P, is that the number of beams between subtrees is the same as the number of beams in subtrees. In Figure 5, similar variants are presented at the scale of a whole bar. Note that the value associated to each tree of Figure 5 is 4 beats, and 1 beat for each tree of Figure 4. ♦ At this point, let us make a few remarks about the above tree semantics. 1) In the tree of Figure 3(a), the dot symbol d labels a leaf node of duration 1 2 , which comes after another leaf node labelled by n and of duration 1 4 . This may seem counter-intuitive with respect to standard rhythm notation: we could expect the node of duration 1 2 to be labeled by n and the node of duration 1 4 to be labeled by d. However in our tree semantics, we have chosen to always represent rooted or tied notes by a n followed by some s or d, to avoid ambiguities.

2) Labels d must be used with care for ensuring a correct interpretation into notation. Section 2.4 will discuss some constraints to be satisfied for this sake.

3) The interpretation of the slur symbol s and the dot symbol d is the same regarding durations. This is also the case of p ∈ P and p ∈ P. The symbols d and p ∈ P have been introduced only to give notationrelated information, and the choice of one symbol over the other equivalent will be only dictated by notation preferences (see also Section 2.4).

(a) [ 1 2 ] 1 2 1 2 1 2 1 2 1 2 1 2 [ 1 2 ] 2 2 2 r n 2 n n 2 2 n n 2 n r (b) [ 1 2 ] 1 2 1 2 1 2 1 2 1 2 1 2 [ 1 2 ] 2 2 2 r n 2 n n 2 2 n n 2 n r (c) [ 1 2 ] 1 2 1 2 1 2 1 2 1 2 1 2 [ 1 2 ]
Fig. 5. Tuplet beaming with symbols of P (one bar).

4) The symbols of P and P are somehow redundant with tree structure, since every inner node is labeled with its degree. This technical facility however allowed us to define our trees in the algebra T (Σ rn ) over a ranked signature Σ rn .

Syntactical Restrictions and Tree Automata

In general, several notations can be associated to the same rhythmic value, and the preferences regarding the notation details may depend on varied factors like the metre, usage, or personal preferences of the author. For instance, we have seen in Example 4 (Figure 3) that the dot symbol d produces the same rhythm value as the slur symbol s, but different notations. Also, separating innermost beams by using p ∈ P instead of p ∈ P, like in Figures 4(b) and 4(c) and Figure 5, can be useful to reflect the correct subdivisions of a tuplet (following the metre) or indicate accentuations, see [START_REF] Gould | Behind Bars: The Definitive Guide to Music Notation[END_REF]. Some constraints regarding notation details can be expressed using tree automata (TAs) over Σ rn . TAs in this case correspond to "style files" for rhythm notation.

The first and most important TA that we need in this context is the one characterizing trees with correct interpretation as notation. For instance, following the above remark (2), one can build a TA checking that the d symbols are well placed. This TA recognizes the set of trees of T (Σ rn ) where a symbol d can only occur in a pattern of the form 2(2(x, n), d) or 2(n, 2(d, x)) is a regular language. We can also extend to double dots by also allowing patterns of the form 2(2(2(x, n), d), d) or 2(n, 2(d, 2(d, x))).

Moreover, the compositional properties of TAs make it possible to combine (by union, intersection, complementation) arbitrarily different notation constraints expressed as TAs. For instance, in a binary metre, there exists a TA that allows beaming as in Figure 4(b) and forbids beaming as in Figure 4(c).

Rewrite Rules

We define a set of rewrite rules on trees, which do not change the rhythmic values (i.e. the actual rhythm), but may change its notation. These rules can therefore be used to produce equivalent notations of a same rhythm. The set of rewrite rules over Σ rn defined in this section will be called R rn .

Normalization Rules

The following rules reflect the semantical equivalence between dots and slurs (Example 4),

d → s (1)
and between symbols of P and their counterpart of P (Example 5).

p(x 1 , . . . , x p ) → p(x 1 , . . . , x p ) p ∈ P

Addition of rests. Unlike notes, successive rests are always summed up implicitly. Following this principle, we can decide to merge subdivisions of rests, with standard rewrite rules of the form 2(r, r) → r, 3(r, r, r) → r, etc., which are generalized into p(r, . . .

r p ) → r p ∈ P (3)
The use of slurs is useless with rests, hence we have also this rule with cousin patterns of length 2

r; s → r; r (4)
Similarly, the following rule complies with the semantics of o, o; r → r; r

Normalization of s. According to the semantics of symbols of P, we can simplify fully tied tuplets with standard rewrite rules: 2(s, → s, 3(s, s, s) → s, etc., generalized into p(s, . . . , s) → s p ∈ P

We have also 2(n, s) → n, 3(n, s, s) → n, etc., generalized into p(n, s, . . . , s) → n p ∈ P

Normalization of o. The following rule replaces o by s when possible.

o; s → s; s

The semantics presented in Section 2.2 make it possible to sum up the durations corresponding to cousin nodes labeled by o, and then subdivide the duration obtained by this sum. Following this principle, we can sometimes simplify a pattern beginning with a sequence of o's, according to the value of the sum and the number of subdivision. The base case is the subdivision by 1, corresponding to the atomic note n o; n → n; s

For a subdivision by 2, we have the following rewrite rules with variables: o;

This transformation is simulated in several steps, using the auxiliary symbols of Θ rn . For p = 2, we have a first left-to-right pass with

1; 2(x 1 , x 2 ) → δ 0 2 (#(x 1 ), #(x 2 )); ⊥ 1; δ 0 2 (x 1 , x 2 ) → δ 1 2 (α 1 (x 1 ), x 2 ); ⊥ 1; δ 1 2 (x 1 , x 2 ) → δ 0 2 (x 1 , α 2 (x 2 )); ⊥ β; δ 0 2 (x 1 , x 2 ) → β; γ 0 2 (x 1 , x 2 ) β = 1 β; δ 1 2 (x 1 , x 2 ) → β; Err β =
followed by a right-to-left pass with

γ 0 2 (α 1 (x 1 ), x 2 ); ⊥ → 1; γ 0 2 (x 1 , x 2 ) γ 0 2 (#(x 1 ), x 2 ); ⊥ → x 1 ; γ 1 2 (x 2 ) γ 1 2 (α 2 (x 2 )); ⊥ → 1; γ 1 2 (x 2 ) γ 1 2 (#(x 2 )) → x 2
In general, the left-to-right pass involves the following rules

1; p(x 1 , . . . , x p ) → δ 0 p (#(x 1 ), . . . , #(x p )); ⊥ (11)
1;

δ i p (x 1 , . . . , x p ) → δ j p (x 1 , . . . , α i+1 (x i+1 ), . . . , x p ); ⊥ 0 ≤ i < p, j = (i + 1) mod p (12)
β; δ 0 p (x 1 , . . . , x p ) → β; γ 1 p (x 1 , . . . , x p ) β = 1 (13)
β; δ i p (x 1 , . . . , x p ) → β; Err β = 1, i > 0 ( 14
)
and the second right-to-left pass is done with

γ i p (α i (x i ), x i+1 , . . . , x p ); ⊥ → 1; γ i p (x i , . . . x p ) 1 ≤ i ≤ p (15)
γ i p (#(x i ), x i+1 , . . . , x p ); ⊥ → x i ; γ i+1 p (x i+1 , . . . , x p ) 1 ≤ i < p (16)
γ p p (#(x p )) → x p (17)
Example 6. Figure 6 presents a rewrite sequence from the tree in Figure 3(c) into 3(b), and from 3(a) also into 3(b). The nodes of application of rewrite rules are marked by circles, and rewrite rules are indicated. This shows that using the above rewrite rules, we can explore the equivalent trees of Figure 3.

♦ 2 2 n o 2 n s --→ (9) 2 2 n n 2 s s --→ (6) 2 2 n n s
←-- (1) 2 2
n n d Fig. 6. Rewrite sequences starting from the trees of Figure 3(c) and 3(a). The applied rewriting rule is between parenthesis.

Subdivision Equivalence

Finally, we propose standard rewrite rules for redefining subdivisions, such as

2(x 1 , x 2 ) → 3(2(o, o), 2(x 1 , o), 2(o, x 2 )) 2(x 1 , x 2 ) → 5(2(o, o), 2(o, o), 2(x 1 , o), 2(o, o), 2(o, x 2 )) 3(x 1 , x 2 , x 3 ) → 2(3(o, x 1 , o), 3(x 2 , o, x 3 )) . . .
The general form of these rules is p(x 1 , . . . , x p ) → p p(u 1,1 , . . . , u 1,p ), . . . , p(u p ,1 , . . . , u p ,p ) (

where p, p ∈ P, p = p , for all 1 ≤ i ≤ p , 1 ≤ j ≤ p, u i,j ∈ {o, x 1 , . . . , x p } and the sequence u 1,1 , . . . , u Example 7. Applying the above rules to the tree of Figure 3(d), we obtain the rewrite sequence depicted in Figure 7. The result is a simpler tree representing the same durations. ♦

Properties

We show that the rewrite rules of R rn are correct, in the sense that they preserve rhythmic values of trees, and complete, in the sense that given a tree t, it is possible to reach all trees equivalent to t using the rewriting rules of R rn .

For these properties to hold, we need to consider a restriction to so called well-formed trees, based on the following conditions related to the symbol o. A node ν in a tree t ∈ T (Σ rn ) is called dandling if it is labeled by o and it is not the previous cousin of a node in dom(t). Let us define recursively the simplified duration sdur t by sdur t (ν) = dur t (ν) if ν = root(t), sdur t (ν) = sdur t(ν0) p otherwise, where ν 0 is the parent of ν and p is the arity of t(ν 0 ). A tree t ∈ T (Σ rn ∪ Θ rn ) is called o-balanced if for all ν, ν ∈ dom(t) such that ν is the previous cousin of ν and t(ν) = o, it holds that sdur t (ν) = sdur t (ν ). Equivalently, the multisets of labels on the two paths from ν and ν up to the root of t are equal. Intuitively, it means that successive cousin nodes labeled by o represent the same duration. (the multisets of labels from these nodes are both {2, 2}). The situation is the same for the tree 2(d): the three successive cousin nodes labeled by o, o and 5 all have a sdur t of 1 4 (multiset {2, 2}). ♦

Note that the rhythmic value val (t) is defined in Section 2.2 for any tree t ∈ T (Σ rn ) and not only for well-formed trees. This condition is however necessary for the correctness of rules [START_REF] Haddad | Livre Premier de Motets: The Concept of TimeBlocks in OpenMusic[END_REF][START_REF] Hoos | Representing Score-Level Music Using the GUIDO Music-Notation Format[END_REF][START_REF] Lerdahl | A Generative Theory of Tonal Music[END_REF][START_REF] Malt | Some Considerations on Brian Ferneyhough's Musical Language Through His Use of CAC[END_REF][START_REF] Rizo | Symbolic music comparison with tree data structures[END_REF](16)(17). The set of wellformed trees of T (Σ rn ) is unfortunately not regular and even not context-free [START_REF] Comon | Tree Automata Techniques and Applications[END_REF], because it contains the set of well-balanced binary trees as a particular case.

Example 9. The tree of Figure 3(c) can be rewritten into the tree 2(2(n, o), n) by rule [START_REF] Comon | Tree Automata Techniques and Applications[END_REF]. The latter tree is however not well-formed because of the dandling o-node. ♦ Proposition 1. For all well-formed trees t 1 , t 2 ∈ T (Σ rn ), t 1 ≡ t 2 iff t 1 ← ---→ * Rrn t 2 . Let us sketch the proof of Proposition 1. First, as R rn is defined over Σ rn ∪ Θ rn and not simply Σ rn , we must extend the definition of val and the notion of well-definition to the trees of T (Σ rn ∪ Θ rn ). Roughly, we need to sum the durations of contiguous o, ⊥, s, and α i Moreover, we extend the definition of val to patterns made of o's or ⊥'s or s's and one other tree. We show by a case analysis that for each rewrite rule 1 ; . . . ; n → r 1 ; . . . ; r n ∈ R rn , and for each substitution σ grounding for the rule (i.e. such that σ( 1 ),. . . , σ( n ), σ(r 1 ),. . . , σ(r n ) do not contain variables), val σ( 1 ); . . . ; σ( n ) = val σ(r 1 ); . . . ; σ(r n ) . The if direction of Proposition 1 then follows from a lifting of this result to the application of contexts, in order to consider rewriting at inner nodes (not only the root node). The proof of the only if direction works by structural induction on t 1 and t 2 .

We can use the result of Proposition 1 in order to explore rhythm notations equivalent to a given tree, for instance for simplification like in Figures 6 and7. In our context, it is reasonable to assume a bounded depth for trees. By Kruskal lemma, it follows that the number of trees to consider is finite.

Conclusion

The choice of a representation determines the range of possible operations on a given musical structure, and thereby has a significant influence on compositional and analytical processes (see [START_REF] Haddad | Livre Premier de Motets: The Concept of TimeBlocks in OpenMusic[END_REF][START_REF] Malt | Some Considerations on Brian Ferneyhough's Musical Language Through His Use of CAC[END_REF] for examples in the domain of rhythm structures). In this paper we proposed a formal tree-structured representation for rhythm inspired by previous theoretical models for term rewriting. Based on this representation, tree rewriting can be seen as a mean for transforming rhythms in composition or analysis processes. In a context of computer-aided composition for instance, this approach can make it possible to suggest to a user various notations of the same rhythmic value, with different complexities. Similarly, the rewrite sequence of Figure 7 can be seen as a notation simplification for a given rhythm. An important problem in the confluence of the defined rewrite relation, i.e. whether different rewriting from a single tree will eventually converge to a unique canonical form. For a quantitative approach, it is possible to use standard complexity measures for trees (involving depth, number of symbols etc.). We can therefore imagine that this framework being used as a support for rhythm quantification processes [START_REF] Agon | Kant: a Critique of Pure Quantification[END_REF] in computer-aided composition environments like OpenMusic.

The tree format that we are proposing has similarities with the Patchwork/OpenMusic Rhythmic Tree (RT) formalism [START_REF] Agon | Representation and Rendering of Rhythm Structures[END_REF]. 6 Still, these two formats present a number of important differences. While RTs represent durations with integers labeling nodes (the subdivision ratios), our representation only uses the tree structure (i.e., the labels in P are not formally needed) and labels in a finite (and small) set for leaves. This specificity makes the representation more amenable to purely syntactical processing, when RT processing needs arithmetic. Trees of T (Σ rn ) and OM RTs are meant to be complementary, and some functions for converting trees back and forth between these two formats have been implemented. The definition domains of these functions are characterized by TA.

As mentioned in Section 2.4, it is also possible to use a TA to complement the rewriting rules and control the rhythm simplification processes by filtering out rewritten trees that do not correspond to actual notations (e.g. because of misplaced d), or/and restricting the search space to trees corresponding to acceptable or preferred notations. This approach is comparable to the use of schemas for XML data processing.

Note that the symbol n could be replaced by several symbols encoding pitches in order to represent actual melodies. Similar tree-based encodings have been used in [START_REF] Bernabeu | Melodic Identification Using Probabilistic Tree Automata[END_REF] for the search of melodic similarities. Finally, other rewrite rules can be considered, including ones that do not preserve durations or rhythmic values. In this case, tree rewriting could constitute a novel creative approach to rhythm transformation in compositional applications. Another application could be the formalization of summarization of music by pruning trees like in [START_REF] Rizo | Symbolic music comparison with tree data structures[END_REF].

Example 1 .Fig. 1 .

 11 Fig. 1. Simple trees of T (Σrn) with their corresponding rhythmic notations and values.

Example 2 .Fig. 2 .

 22 Fig. 2. Example of trees of T (Σrn): summation with symbol o.

Fig. 3 .

 3 Fig. 3. Trees of T (Σrn) with slurs and dots.

Fig. 4 .

 4 Fig. 4. Tuplet beaming with symbols of P (one beat).

Fig. 7 .

 7 Fig. 7. Rewrite sequence starting from the tree in Figure 3(d).

Definition 2 .Example 8 .

 28 A tree t ∈ T (Σ rn ) is well-formed iff it is o-balanced and without dandling nodes. All the trees of Figure3are well-formed. The tree 2(a) is o-balanced because the two successive leaves labeled by o and n have both a sdur t of1 4

  2(x 1 , x 2 ) → x 1 ; x 2 , o; o; o; 2(x 1 , x 2 ) → o; x 1 ; o; x 2 ,and so on for each multiple of 2. For a subdivision by 3, we have o; o; 3(x 1 , x 2 , x 3 ) → x 1 ; x 2 ; x 3 etc. The general form of the expected transformations is

o; . . . ; o kp-1 ; p(x 1 , . . . , x p ) → o; . . . ; o k-1 ; x 1 ; o; . . . ; o k-1 ; x 2 ; . . . ; o; . . . ; o k-1 ; x p

  1,p , . . . , u p ,1 , . . . , u p ,p has the form o, . . . , o, x 1 p , . . . , o, . . . , o, p

p

.

http://tom.loria.fr

http://maude.cs.illinois.edu

In the examples and figures of this paper, when not specified otherwise with a time signature, we will consider that the duration associated to each of the trees is 1 beat (this duration can also be found by summing the indicated fractional durations).

A rhythm tree RT is defined as a pair d, S where d ∈ N is a duration and S = s0, . . . , sn is a sequence of subdivisions where for all 1 ≤ i ≤ n, si is either a tree or a ratio. Formally, si ∈ N or si is a RT.


Bogdan Nicolae
email: bogdan.nicolae@ie.ibm.com

Andrzej Kochut
email: akochut@us.ibm.com

Alexei Karve
email: karve@us.ibm.com

Discovering and Leveraging Content Similarity to Optimize Collective On-Demand Data Access to IaaS Cloud Storage

Keywords: similarity, deduplication, cloud storage, on-demand data access, collective I/O

A critical feature of IaaS cloud computing is the ability to quickly disseminate the content of a shared dataset at large scale. In this context, a common pattern is collective on-demand read, i.e., accessing the same VM image or dataset from a large number of VM instances concurrently. There are various techniques that avoid I/O contention to the storage service where the dataset is located without relying on pre-broadcast. Most such techniques employ peer-to-peer collaborative behavior where the VM instances exchange information about the content that was accessed during runtime, such that it is possible to fetch the missing data pieces directly from each other rather than the storage system. However, such techniques are often limited within a group that performs a collective read. In light of high data redundancy on large IaaS data centers and multiple users that simultaneously run VM instance groups that perform collective reads, an important opportunity arises: enabling unrelated VM instances belonging to different groups to collaborate and exchange common data in order to further reduce the I/O pressure on the storage system. This paper deals with the challenges posed by such a solution, which prompt the need for novel techniques to efficiently detect and leverage common data pieces across groups. To this end, we introduce a low-overhead fingerprint based approach that we evaluate and demonstrate to be efficient in practice for a representative scenario on dozens of nodes and a variety of group configurations.

I. INTRODUCTION

One of the main features that has contributed to the growing popularity of Infrastructure-as-a-Service (IaaS) cloud computing is the elastic on-demand provisioning of resources: users can bring up a whole virtual cluster and reconfigure it dynamically with a simple click of a button. However, as the user interface grows simpler and the types of workloads diversify,achieving efficient on-demand VM provisioning is a non-trivial task.

A particularly difficult challenge in this context is the collective on-demand read pattern, i.e., provisioning a large number of inter-dependent VMs (e.g. part of the same virtual cluster running a large scale distributed application) that concurrently read (typically) a part of the content from the same VM (virtual machine) disk image (e.g., boot and launch applications) or from a large dataset (e.g., shared input data). This pattern is often encountered in the context of largescale HPC (high performance computing) and data-intensive applications. Obviously, there is a need to minimize the provisioning time and guarantee scalability despite a growing number of VMs, otherwise users do not perceive IaaS as truly on-demand and lose interest, while at the same time cloud providers lose potential profit by not efficiently leveraging their computational resources.

Despite widespread need for scalable, high-performance solutions that handle the collective on-demand read pattern, IaaS cloud providers offer limited support in this regard. Most often, in an attempt to avoid any bottlenecks due to I/O contention to the storage service where the VM images and datasets are stored, it is very common to broadcast the full content to the local storage of the VM instances before allowing any read. However, most of the time, this approach is sub-optimal because of two reasons: (1) not all content is actually read; and (2) reads need to wait for the whole broadcast to finish. Thus, approaches that deliver content onthe-fly as needed in order to eliminate these two disadvantages saw increasing adoption, despite the added complexity of having to deal with the I/O contention to the storage service.

One major direction that addresses the problem of I/O contention for on-the-fly data delivery during collective reads is the use of peer-to-peer collaborative techniques. In this class of solutions, the VM instances are aware of each other's previously accessed data that is locally available and prefer to exchange the needed data among themselves rather than interact with the decoupled storage service, which risks the creation of bottlenecks due to I/O contention. Although related to pre-broadcast techniques (which are typically implemented as BitTorrent-like protocols), the focus in this context falls on how to detect and anticipate what content is actually needed during the runtime of a VM instance, in order to be able to prefetch it from the other VM instances as early as possible.

However, despite the success of such techniques to improve the performance and scalability of collective reads, most of the time they require foreknowledge about what VM instances are related and what dataset or VM image they share and read in a concurrent fashion. This is a significant limitation for large IaaS cloud datacenters where a large number of users share the infrastructure simultaneously, because there are multiple opportunities for VM instances to collaborate and exchange identical pieces of data even if they belong to different users for which the relationship between the VM instances, their access pattern and the data they are reading is unknown. This aspect is particularly important in light of several studies that confirm a large amount of redundancy among VM images, with the data duplication degree reported up to 94% [START_REF] Jin | The effectiveness of deduplication on virtual machine disk images[END_REF], [START_REF] Jayaram | An empirical analysis of similarity in virtual machine images[END_REF], [START_REF] Schwarzkopf | Efficient storage of virtual machine images[END_REF].

In this paper, we focus precisely on this aspect. Our proposal envisions to organize the VM instances in a large universal group where they constantly exchange advertisements about the pieces of data (chunks) they read on-the-fly. Thus, the opportunity to exchange chunks in order to avoid I/O bandwidth contention goes beyond groups that form around individual collective reads, effectively enabling such groups that exist simultaneously to help each other out and further improve the overall scalability and performance. The key novelty in this context is how to efficiently detect and leverage such inter-group content similarity, considering the extra difficulty related to the lack of foreknowledge when operating such a large universal group.

We summarize our contributions as follows:

• We introduce a series of general principles that form a collective content exchange strategy optimized to handle the case when multiple VM instance groups simultaneously perform collective reads on potentially different datasets (Section III-A).

• We design a series of algorithms that materialize the aforementioned principles. We introduce low-overhead asynchronous techniques to identify and leverage on-thefly content similarity between groups of VM instances that perform collective reads based on pre-calculated fingerprints (Sections III-B).

• We propose a hypervisor-transparent implementation as an independent FUSE module that implements our approach in userspace. Furthermore, we show how this FUSE module can be integrated in a typical IaaS architecture (Sections III-D and III-C).

• We experimentally evaluate the benefits of our approach on the Shamrock testbed by performing experiments on dozens of nodes for a representative scenario and a variety of group configurations (Section IV).

II. RELATED WORK

Content similarity detection is typically performed by means of deduplication, which is broadly classified into static and content-defined. Static approaches split the input data into equally sized chunks, which are then compared among each other (either byte-by-byte or, for increased performance, based on their hash values) in order to identify and eliminate duplicates. While simple and fast, static approaches suffer from misalignment issues (i.e insertions or deletions lead to the impossibility to detect duplicates). To deal with such misalignment issues, content defined approaches [START_REF] Muthitacharoen | A low-bandwidth network file system[END_REF] were proposed. Essentially, they involve a sliding window over the data and that hashes the window content at each step using Rabin's fingerprinting method [START_REF] Rabin | Fingerprinting by random polynomials[END_REF]. Many storage systems have adopted and refined deduplication techniques [START_REF] Zhu | Avoiding the disk bottleneck in the data domain deduplication file system[END_REF], [START_REF] Dubnicki | Hydrastor: a scalable secondary storage[END_REF], [START_REF] Guo | Building a high-performance deduplication system[END_REF], [START_REF] Nicolae | Towards Scalable Checkpoint Restart: A Collective Inline Memory Contents Deduplication Proposal[END_REF]. Specifically in the context of IaaS clouds, deduplication techniques have proven effective at reducing the amount of space and network bandwidth necessary to store and transfer VM images. Several studies report significant reductions that can reach up to 94% [START_REF] Jin | The effectiveness of deduplication on virtual machine disk images[END_REF], [START_REF] Jayaram | An empirical analysis of similarity in virtual machine images[END_REF], [START_REF] Schwarzkopf | Efficient storage of virtual machine images[END_REF]. This potential has been exploited in dedicated VM image repositories such as VMAR [START_REF] Shen | Vmar: Optimizing i/o performance and resource utilization in the cloud[END_REF] and Squirrel [START_REF] Razavi | Squirrel: Scatter hoarding vm image contents on iaas compute nodes[END_REF] in order to store VM images (either fully or partially) in a deduplicated fashion. Utilizing content similarity in workloads from production storage systems is discussed in [START_REF] Koller | I/o deduplication: Utilizing content similarity to improve i/o performance[END_REF]. Several optimizations specifically targeting the performance of reading deduplicated data during on-demand accesses have also been recently proposed [START_REF] Mao | Read-performance optimization for deduplication-based storage systems in the cloud[END_REF]. Furthermore, outside of storage, deduplication has demonstrated important benefits in the area of live migration [START_REF] Deshpande | Live gang migration of virtual machines[END_REF], [START_REF] Al-Kiswany | Vmflock: Virtual machine co-migration for the cloud[END_REF].

Techniques to fetch data from storage services to VM instances are broadly classified into pre-broadcast and ondemand. Pre-broadcast techniques use various scalable mechanisms (e.g., multi-cast [START_REF] Hibler | Fast, scalable disk imaging with frisbee[END_REF], application level broadcasttrees [START_REF]SCPTsunami[END_REF] to peer-to-peer protocols [START_REF] Schmidt | Efficient distribution of virtual machines for cloud computing[END_REF], [START_REF] Wartel | Image distribution mechanisms in large scale cloud providers[END_REF], [START_REF] Reich | Vmtorrent: Scalable p2p virtual machine streaming[END_REF]) to deliver a shared dataset from the storage service to multiple VM instances in advance, such that it can be used later without worrying about bottlenecks due to I/O bandwidth contention. However, on the downside, the broadcast can take a long time to finish and potentially delivers more content than is actually needed during runtime. On-demand techniques on the other hand eliminate both disadvantages at the cost of dealing with the I/O bandwidth contention during runtime. This approach is widely used in IaaS datacenters for virtual disk images using copy-on-write: a locally stored QCOW2 image is instantiated from a shared backing image that is located remotely on the image store (e.g. NFS server). In an attempt to alleviate the I/O contention, various solutions ranging from decentralizing the storage (e.g. by using parallel file system [START_REF] Schmuck | Gpfs: A shared-disk file system for large computing clusters[END_REF], [START_REF] Weil | Ceph: a scalable, high-performance distributed file system[END_REF]) to using dedicated repositories [START_REF] Nicolae | Going back and forth: Efficient multi-deployment and multi-snapshotting on clouds[END_REF]) and specialized prefetching techniques [START_REF] Nicolae | Optimizing multi-deployment on clouds by means of self-adaptive prefetching[END_REF] have been proposed.

In a broader sense, collaborative caching has been explored in the MPI-IO context [START_REF] Nisar | Scaling parallel i/o performance through i/o delegate and caching system[END_REF]. Our own previous work [START_REF] Nicolae | Leveraging Collaborative Content Exchange for On-Demand VM Multi-Deployments in IaaS Clouds[END_REF] explores how to improve collective reads to a shared virtual disk image by means of pushing accessed chunks among the members of the group, in an attempt to anticipate and avoid direct access to the storage service.

This paper focuses on exploiting content similarity on-thefly in order to enable multiple VM instances, even if they belong to different dissemination groups, to collaborate, identify and exchange identical chunks of data in order to minimize the I/O pressure on the storage service under concurrency. To our best knowledge, we are the first to focus on this aspect in particular.

III. SYSTEM DESIGN

This section describes the design principles and algorithms behind our approach (Sections III-A and III-B), how to apply them in a cloud architecture (Section III-C) and finally how to efficiently implement them in practice (Section III-D).

Note that in the description of our approach, we focus on virtual disk images as the content accessed by collective reads. However, our approach can be easily adapted to handle any kind of generic unstructured dataset that can be represented as a sequence of bytes.

A. Design Principles 1) Copy-on-Reference Local Mirroring:

To facilitate ondemand VM disk image access, we leverage copy-onreference, initially introduced for process migration in the V-system [START_REF] Theimer | Preemptable remote execution facilities for the v-system[END_REF]. To this end, our approach exposes a private local view of the virtual disk image stored remotely on the VM repository to the hypervisor. We call this local view a mirror. From the perspective of the hypervisor, the local mirror appears to have already fetched and created a copy of all necessary content, however, the mirror gets populated with content only as needed during runtime. It is logically partitioned into fixed-sized chunks. Whenever the hypervisor needs to read a region of the image, all chunks covered by the region that are not already locally available are fetched from a remote source and copied locally (i.e., "mirrored"). Once all content is available locally, the read can proceed.

2) Collaborative Chunk Advertisement and Exchange: One of the major issues that plain copy-on-reference approaches face when dealing with collective reads is the I/O contention to the image store. This happens regardless of whether the store is centralized or decentralized, because the VM instances mostly follow the same I/O access pattern and thus access the same chunk simultaneously. Thus, it is important to develop techniques that reduce the I/O pressure on the image store in order to improve the performance and scalability of copy-onreference. In this context, a natural idea is to let the mirrors collaborate and inform each other about what chunks they already posses, such that it is possible to directly fetch the chunks from other remote mirrors rather than the image store itself. To this end, we propose a peer-to-peer collaborative scheme where the mirrors advertise chunks to each other prefetch any missing chunk soon as an advertisement about it has been received, in anticipation of future read requests that will access that chunk. How to select what peer to talk to and when to decide if prefetching actually helps or just wastes network bandwidth (because no read request actually needs the chunks) is outside the scope of this work. We discuss some initial ideas related to the latter aspect in our previous work [START_REF] Nicolae | Leveraging Collaborative Content Exchange for On-Demand VM Multi-Deployments in IaaS Clouds[END_REF], where we propose a different prefetching mechanism based on pushes. With respect to the peers involved in the exchange, we opted for a circular double-linked list: we fix a predefined ordering of all mirrors in a ring and create links to the previous and next node in the ring. Thus, each peer has three potential sources from where it can fetch chunks: its neighbors in the ring and the original source of the VM image. To avoid I/O contention to the peer that advertised the chunk, we use a load-balancing strategy: if multiple neighbors advertised the same chunk, the one that has the least number of pending requests that need to be served is selected.

3) Fingerprint-Based Content-Aware Advertisements:

When the VM instances need to access the same virtual disk concurrently, the process of advertising chunks to other peers is straightforward: it is enough to include information about the chunk offset in order to uniquely identify a chunk. Under such circumstances, this approach is optimal, because only a minimal information about the chunk needs to be included in the advertisement, which means advertisements spread fast and thus improve the chance that a chunk can be obtained from another peer rather than the original source. Thus, a naïve solution to deal with multiple concurrent groups of VM instances (where each group competes for a different virtual disk image) is to establish a peer-to-peer collaborative chunk advertisement and exchange scheme within each group. Again, such an approach would be optimal if the original virtual disk images are completely disjoint. However, as discussed in Section II, in practice there is a large degree of redundancy with respect to the content of virtual disk images, which means many chunks are identical despite belonging to different images and being located at different offsets. As a consequence, it is important to be able to extend the chunk advertisements and exchanges beyond the scope of a single group, especially since the potential to alleviate the I/O pressure on the image store grows with an increasing group size. Thus, a much better idea is to form a single group with all VM instances where they advertise and exchange chunks regardless of what virtual disk image they need to access. However, the problem of how to identify identical chunks is not as simple as exchanging chunk offsets anymore, because content-identical chunks might have different offsets in different images. Using a naïve solution that advertises full chunks is not feasible, as this would lead to an explosion of network traffic. To deal with this situation, we propose to use much smaller fingerprints that represent the content of the chunk and can be used for a quick comparison. Such an approach is often implemented using strong hash functions (e.g., SHA-1), for which it can be shown that the chance of collisions (i.e., obtaining the same fingerprint for two different chunks) is negligible in practice [START_REF] Nicolae | Towards Scalable Checkpoint Restart: A Collective Inline Memory Contents Deduplication Proposal[END_REF]. While the size of a fingerprint is significantly larger than the size of an offset (e.g., 8 bytes for a 64 bit value vs. 20 bytes for SHA-1), this increase in advertisement size does not significantly delay the propagation of advertisements (as discussed in Section IV-E).

4) Storage-Agnostic Chunk Pre-Hashing and Optimized Lookup: One of the major advantages of using a fingerprintbased advertisement scheme is the fact that duplicated content can be detected and exchanged on-the-fly. This aspect holds regardless of whether the image store has de-duplication support or not. If the image store does not support deduplication (which is a common occurrence in production), then the benefits of our approach are obvious. However, even if the image store supports de-duplication and holds only unique chunks (as implemented by some related work discussed in Section II), this brings little benefit in our context, because the VM instances still need to access the same chunk multiple times if they are not aware of each other's content. On the other hand, in order to be effective, the fingerprint advertisement scheme needs to incur minimal overhead compared with a scheme that directly advertises offsets. To this end, we avoid the calculation of fingerprints during runtime in favor of a scheme that performs a pre-calculation: whenever a new virtual disk image is added to the image store, the fingerprints corresponding to each offset are calculated and stored in a separate map file. Thus, whenever a VM instance needs to mirror content locally, it first opens the map file and preloads all fingerprints in an optimized look-up table. Note that it is possible for the same chunk to appear multiple times in the same disk image. However, the data structures that enable efficient bi-directional lookup are optimized for bijections. To deal with this situation, we introduce a second uni-directional look-up table that associates each chunk offset to a unique parent offset that acts as a representative for the chunk content. Thus, whenever a read request is issued, the actual offsets are first converted into parent offsets, which in turn are associated to unique fingerprints whenever an interaction with other peers is needed.

B. Algorithms

In this section, we show how to implement the design principles discussed in the previous section using a series of algorithmic descriptions. To simplify the understanding, we assume a scenario where each mirror handles a single image. However, the algorithms can be easily extended in practice to implement a mirror that can share common chunks between multiple VM instances that are co-located on the same node.

The local mirror corresponding to the virtual disk image (denoted M irror) is split into fixed sized chunks. Each chunk of the M irror can be in one of the four possible states (denoted State): REM OT E (the chunk was not yet locally mirrored), W AIT (the peer has asked another for the chunk and is waiting for the reply), LOCAL (the chunk was successfully prefetched and mirrored locally, but was not yet read) and READ (the chunk was needed by a read operation).

The READ operation is detailed in Algorithm 1. In a nutshell, it ensures that all chunks that cover the range of f set, size from M irror are locally available, after which it redirects the read request to the local mirror. More specifically, first the parent offset p of a chunk is calculated. This information is maintained in the P arentOf f set uni-directional data structure. Once p is known, any reference to the original chunk is equivalent to a reference to the chunk corresponding to p. Thus, if p is in the process of being prefetched, then it waits for the prefetching to finish. If the prefetching was not successful (i.e., it timed out), then it reverts to the image store. Reverting to the image store is not immediate: the read request for the chunk is accumulated in the Original set and handled only after all chunks were processed, which avoids waiting for repository unnecessarily. If a chunk is not locally available or in the process of being prefetched (REM OT E state), then READ attempts to fetch it from another peer that advertises it (all advertisements for a chunk are accumulated in the Source set). If such a peer (denoted P eer) exists, then READ picks Algorithm 1 Read the range (of f set, size) into buf f er from disk image 1: function READ(buf f er, of f set, size)

2:

Original ← ∅

3:

for all chunk ∈ Image such that chunk ∩ (of f set, size) = ∅ do in parallel for all p ∈ Original do in parallel return read (of f set, size) into buf f er from M irror 29: end function the one that is the least loaded (i.e., it has a minimal number of pending requests it needs to answer to), fetches the chunk from it and finally advertises the chunk to the neighbors. The advertisement is based on the fingerprint of the chunk p, which is pre-loaded in the bi-directional look-up table F ingerprint. If no neighboring peer holds the chunk, then it reverts to the image store (i.e. the chunk is added to Original). In either case, the state of the chunk becomes READ. Once all chunks are processed, the ones scheduled to be read from the image store (Original set) are finally fetched, mirrored locally and advertised to the neighbors. At this point, all chunks needed by the read operation are locally available and the M irror can be used to fill the buf f er where the result is stored.

The collaborative chunk advertisement and exchange scheme is performed asynchronously by BACKGROUND EXCHANGE, detailed in Algorithm 2. In a nutshell, it listens for advertisements about new chunks from all its neighbors and whenever it receives one, first it performs a reverse look-up in the F ingerprint map to obtain the parent offset p for the chunk fingerprint referred to by msg. Then, it adds the originating P eer to the corresponding end while 22: end procedure Source[p] set. If the payload received from any peer is a request for a chunk, it will send the chunk as a reply if the chunk is actually mirrored locally, otherwise it will instruct the requester to look for an alternative. Whenever a chunk is received as a reply, the M irror will be updated with its content and the state will be updated to LOCAL. Furthermore, the chunk is advertised asynchronously to all neighbors.

Note that the local mirror also supports write operations: once a chunk is overwritten, it is invalidated and cannot be used in the collaborative chunk exchange any longer (i.e., it is not advertised anymore to other peers and any remote peer trying to fetch it will fail). However, this mode limits the potential to exchange chunks under write-intensive scenarios, which is why the mirror is typically used as read-only backing file for higher level copy-on-write layers (e.g., QCOW2).

C. Architecture

We depict a simplified IaaS cloud architecture that integrates our approach in Figure 1. For better clarity, the building blocks that correspond to our own approach are emphasized with a darker background.

The VM image store is the storage service responsible to hold the VM disk images that are accessed concurrently during collective reads. The only requirement for the image store is to be able to support random-access remote reads, which gives our approach high versatility to adapt to a wide range of options: centralized approaches (e.g., NFS server), parallel filesystems or other dedicated services that specifically target VM storage and management [START_REF] Nicolae | Going back and forth: Efficient multi-deployment and multi-snapshotting on clouds[END_REF], [START_REF] Hansen | Scalable virtual machine storage using local disks[END_REF]. In particular, solutions that de-duplicate VM image content [START_REF] Shen | Vmar: Optimizing i/o performance and resource utilization in the cloud[END_REF] are well complemented by our approach, as discussed in Section III-A.

The cloud user has direct access to the VM image repository and is allowed to upload and download VM images from it. Furthermore, the cloud user also interacts with the cloud middleware through a control API that enables launching and terminating multi-deployments. In its turn, the cloud middleware will interact with the hypervisors deployed on the compute node to instantiate the VM instances that are part of the multi-deployment.

Each hypervisor interacts with the local mirror of the VM disk image as if it were a full local copy of the VM disk image template. To facilitate this behavior, the mirroring module acts as a proxy that traps all reads of the hypervisor and takes the appropriate action: it populates the local mirror on-demand only in a copy-on-reference fashion while using the peer-topeer chunk advertisement and exchange protocol described in Section III-A to pre-populate regions that are likely to be accessed in the future based on the collective access pattern.

D. Implementation

We implemented the mirroring module as file system in userspace on top of FUSE (File system in USerspacE). This has two advantages in our context: [START_REF] Jin | The effectiveness of deduplication on virtual machine disk images[END_REF] it is transparent to the hypervisor (and thus portable); (2) it enables easy interface to the image store (regardless of the access interface) as well as easy prototyping of the collaborative chunk advertisement and exchange protocol, because all communication between the peers happens in userspace.

The collaborative chunk advertisement and exchange strategy runs in its own thread, which synchronizes with the main FUSE thread through the data structures presented in Section III-B. We rely on the Boost C++ collection of libraries for the implementation of high performance bi-directional maps and look-up tables used for the translation between parent offsets and fingerprints. The fingerprints themselves can be calculated using any strong hash function, however, for the purpose of this work we opted for SHA-1. Note that the mirroring module only uses the fingerprints and never calculates them (which is the responsibility of additional external tools or the image store itself if it has de-duplication support). We implemented our own external tool that prehashes a virtual disk image using a configurable chunk size based on the SHA-1 implementation provided by OpenSSL.

The communication between the mirroring modules is implemented on top of Boost ASIO, a high performance asynchronous event-driven library which is part of the standard Boost package. Since the chunk exchange and prefetching scheme is not a pre-condition for correctness (i.e. it is always possible to fall back to the original source in order to fetch the missing chunks), we have opted for a lightweight solution that performs gossiping through UDP communication channels. This has the potential to significantly reduce networking overhead at the cost of unreliable communication. Given the sensitivity of our approach to the timely dissemination of advertisements, especially when considering the extra overhead of sending SHA-1 fingerprints, the choice of using UDP has much more benefits compared to the drawbacks of unreliability (which is quite low within a datacenter).

IV. EVALUATION

This section evaluates the benefits of our approach experimentally based on a real-life scenario often encountered in practice.

A. Experimental Setup

Our experiments were performed on the Shamrock testbed of the Exascale Systems group of IBM Research Ireland. For the purpose of this work, we used a reservation of 32 nodes interconnected with Gigabit Ethernet, each of which features an Intel Xeon X5670 CPU (12 cores), HDD local storage of 1 TB and 128 GB of RAM.

We simulate a cloud environment using QEMU/KVM as the hypervisor. On each node, we deploy a VM that is allocated two cores and 8 GB of RAM. The guest operating system is a recent Debian Sid, whose backing image is stored on a NFS server that is accessible through the Gigabit Ethernet link. The format of the image is RAW and its total size is 4 GB. Each VM instance is booted from a locally-derived QCOW2 image. Furthermore, the network interface of each VM uses the virtio driver and is bridged on the host with the physical interface in order to enable point-to-point communication between any pair of VMs. The I/O caching mode of QEMU/KVM is the default (i.e. cache=writeback).

B. Workload

As a motivating scenario for our evaluation we choose a setting where users need to instantiate a large number of VMs and configure them on-the-fly using a shared repository. Often, such a repository includes software packages and configuration files. In order to save space, software packages are often compressed. Thus, a common operation is to read the compressed stream of bytes from the repository and unpack its content into the local storage of the VM instance.

The repository is abstracted as a read-only virtual disk that is formatted using the ext4 file system to hold a series of compressed software packages. This virtual disk is mounted after boot and used to install all necessary components. Since the content of the repository is delivered on-the-fly only when needed (i.e. the virtual disk corresponding to the repository is not pre-copied), users typically consolidate all their software packages in a single large repository from which each VM instance can cherry-pick the needed components. Users prefer this approach to other on-demand solutions (e.g. setting up an extra VM instance as a FTP server), both because it is easier to setup (i.e., no extra overhead to configure a FTP server) and because it is more cost-effective (i.e., no extra dedicated VM needs to act as the repository). However, due to the popularity of some software packages, the repositories compiled by the users often overlap to a large degree. To capture this aspect in our evaluation, we compiled two repositories as RAW virtual disks of 2 GB that include the content summarized in Table I. This content is representative of two users that run business analytics workloads at large scale using either Hadoop and DB2 or WebSphere and DB2. For the rest of this paper, we refer to the two repositories as Repo-1 and Repo-2.

For the purpose of this work, both Repo-1 and Repo-2 are stored on the same NFS server where the OS image of the VM instances is stored. The experiments consist in booting a number of VM instances (up to 32, each on a dedicated physical node), a part of which mounts Repo-1, while the rest mounts Repo-2. This corresponds to two different users, each with its own repository, that need to simultaneously instantiate a set of VM instances. To emphasize the importance of detecting and leveraging content duplication during on-the-fly concurrent dissemination of data, we assume all VM instances run the same workload: unzip the common Netw DB2 Info Ctr V10.5.tar.gz package, which is part of a DB2 on-the-fly installation.

Note that the nature of the data accessed by the workload (gzip archive) does not exhibit any internal redundancy. This is ideal in our context, because the lack of intra-repository duplication excludes from the measurements any benefits that could result from fetching unique chunks only once within the same group. Thus, the benefits observed in the experiments are exclusively the result of the ability to exchange the chunks between the groups. However, when intra-duplication is present, we anticipate even greater benefits for our approach.

C. Methodology

We compare three approaches throughout our evaluation: a) Direct on-demand access: In this setting, the repository image residing on the NFS server is directly attached as a read-only snapshot to its corresponding VM instances. In this setting, the VM instances operate in complete isolation and read in parallel all necessary content directly from the NFS server, which greatly simplifies the setup, but creates a high degree of I/O contention. Such an approach is widely used in production and relevant as a baseline for comparison. We denote this approach nfs-direct.

b) Collaborative on-demand offset-identical chunk exchange: In this setting, the repository image residing on the NFS server is mirrored on-demand on the local storage of the node that hosts the VM instance. The mirror is aware of the other concurrently running VM instances that share the same repository image and advertises the accessed chunks to them. At the same time, it reacts to the advertisements received from other VM instances by prefetching any missing chunks from them in order to avoid accessing the NFS server if those missing chunks are needed in the future. Since the chunks refer to the same repository image, any exchange between the VM instances involves only a minimal amount of information about the chunk: it's offset. However, there are no exchanges between VM instances that do not share the same repository image. This approach aims to implement a solution that performs optimally in the case when all VM instances are aware of the information they are sharing. We denote this approach as collab-simple.

c) Collaborative on-demand content-aware chunk exchange: Similar to the previous setting, the repository image residing on the NFS server is mirrored on-demand on the local storage of the node that hosts the VM instance. However, the mirror implements our approach and is aware of any other VM instances, exchanging advertisements with them regardless whether they share the same repository image or not. In this case, the advertisements are larger compared to the previous case, because they include the SHA-1 fingerprint of the chunk as payload rather than the offset (20 bytes vs. 8 bytes). Furthermore, there is extra overhead needed to translate from the fingerprint to the chunk offset and back. However, other than these differences, every other aspect is identical to the previous setting. We denote this approach collab-dedup.

For both collab-simple and collab-dedup, the chunk size is fixed at 32 KB, which results in a total of 65536 chunks for both Repo-1 and Repo-2, out of which 24559 are accessed by the workload. In the case of collab-dedup, all chunks belonging to Repo-1 and Repo-2 and pre-hashed using SHA-1 and indexed in a corresponding fingerprint file before the experiment begins.

These approaches are compared based on the following metrics:

Completion time: This is the total time required to run the workload. We report average values per VM instance, as well as extremes (i.e. time for all VM instances to complete), both of which are directly relevant for the user, because in many cases it is necessary to wait for all VM instances to finish the initialization step before they can be used. A low value indicates better overall performance.

Source and amount of network traffic: This is the average received network traffic generated by on-demand reads of the package during the workload. It is broken down by source, indicating the amount read from the NFS server, the amount pre-fetched from other VM instances in anticipation of read requests and the amount fetched on-demand from other VM instances as a direct consequence of read requests. This information is important from the IaaS cloud provider perspective, because it shows how much the I/O pressure on the NFS server can be reduced thanks to collaborative chunk exchanges.

D. Scalability and performance

Our first series of experiments aims to study the weak scalability of all three approaches under a variable distribution of the VMs that access either Repo-1 or Repo-2. To this end, we fix three representative configurations: (1) all VMs access only Repo-1; (2) 25% of the VMs access Repo-1, while the rest access Repo-2; and (3) half of the VMs access Repo-1, while the other half access Repo-2. For each configuration, we gradually increase the number of concurrent VMs that run the workload described in Section IV-B. To emphasize the I/O pressure on the NFS server due to contention, we start all VM instances simultaneously.

The average completion time for all three configurations is depicted in Figure 2(a), Figure 2(b) and Figure 2(c) respectively. As expected, with an increasing number of VMs, the average completion time is increasing, because more VMs compete for the same chunks. In the case of nfs-direct, the only source to fetch the chunks from is the NFS-server. Thus, all VM instances compete for the I/O bandwidth of the NFS server, regardless of the distribution between Repo-1 and Repo-2. This is directly observable in the shape of the curves corresponding to nfs-direct in all three figures: there is an almost perfect overlap between them. At the extreme of 32 VM instances, the average completion time for nfs-direct is around 189s in all three cases, which amounts to a low throughput of around 4 MB/s.

In the case of collab-simple and collab-dedup, the slope of the curves is more gentle, showing a major improvement in scalability. This is especially visible for the case when all VM instances access Repo-1 (Figure 2(a)): the average completion time remains almost constant for both approaches with only little difference between them (15.85s for collab-simple and 16.66s for collab-dedup). Compared with nfs-direct at the extreme of 32 VM instances, the average completion time Fig. 2. Study of scalability and performance for a set of concurrent VMs of which each is mounting one of two different virtual disk repositories but access identical overlapping content (unzip a compressed software package present in both repositories). The size of the compressed software package is 762 MB. was reduced by more than 91% in both cases. Interesting to note is also the low overhead of our approach compared with collab-simple: exchanging more information about each chunk (fingerprint vs. offset) and translating offsets to fingerprints in both directions has a minimal performance impact (up to 4%) even when only a single group of VM instances that share the same repository is present (which favors the collab-simple approach).

However, when the VM instances access both Repo-1 and Repo-2, a large gap between collab-simple and collab-dedup starts to become visible: at the extreme of 32 VM instances, collab-dedup is on the average 2.05x faster than in the case when 50% of the VMs access Repo-1 (Figure 2(c)). These results are easy to understand: in the case of collab-simple each of the VM groups corresponding to Repo-1 and Repo-2 act in isolation and advertise the chunks only among themselves. Thus, each chunk is fetched at least twice from the NFS server by at least one of the members of each group. In the case of collab-dedup, all VMs act as a single group and advertise the same content-identical chunks among themselves, effectively halving the I/O pressure on the NFS server. When 25% of the VMs access Repo-1 (Figure 2(b)), collab-dedup is 1.88x faster than collab-simple. This can be explained by the fact that collab-simple can propagate the chunks much better in the significantly larger group corresponding to Repo-2.

To verify this effect for symmetry, we ran two extra experiments: (1) 25% of the VMs access Repo-2 and the rest Repo-1; and (2) all VMs access Repo-2. Armed with these two new experiments, we depict in Figure 2(d) a comparison between collab-dedup and collab-simple for a fixed number of 32 VM instances with a gradual increase in the number of VMs accessing Repo-1 from 0 to 32. As expected, the maximal difference is when the two VM groups are equally sized, with little difference observable when all VMs belong to the same group.

Furthermore, as explained in Section IV-C, besides the aver- age completion time per instance, an important aspect to study is also the extremes of the completion time (i.e. corresponding to the fastest and the slowest instance). To this end, we zoom on the completion times for the maximal deployment of 32 VM instances in Table II. As can be observed, in the case of collab-simple and collab-dedup, there is little variation between the average and the minimum or maximum: no more than 6% is observable. However, the same does not hold for nfs-direct: the slowest VM instance has a completion time that is almost twice as high as the fastest. This effect can be traced back to the high degree of contention, which causes read requests not to be served in a fair fashion, resulting in uneven delays. Thus, it can be noted that the collaborative chunk exchange strategy not only leads to a dramatic improvement in the scalability and performance, but also in terms of I/O fairness.

E. Network traffic

In this section we study the network traffic generated during the experiments presented in the previous section. We focus on the average amount of content received from remote sources in the case of 32 concurrent VM instances, broken down by source and type. More specifically, we are interested in understanding how much of the content is fetched from the NFS server and how much of the content is fetched from the other peers (in the case of collab-simple and collab-dedup). Furthermore, for the content fetched from the other peers (i.e. chunks of 32 KB), we make a distinction between the chunks that were advertised and pre-fetched before they were needed (peers-prefetch) and those chunks that were advertised but were fetched as a consequence of a read request (peers-get).

The results are depicted in Figure 3. All three approaches fetch the same total amount of information, with nfs-direct exclusively accessing the NFS server. However, in the case of collab-simple and collab-dedup, the majority of the chunks are obtained by a VM instance from other peers rather than the NFS server. This explains why a reduction of 91% in average completion time in the case when all VM instances access Repo-1 is possible for both collab-simple and collab-dedup when compared with nfs-direct. Particularly interesting to note is the difference between collab-simple and collab-dedup: despite both accessing only Repo-1, collab-simple manages to prefetch a slightly larger amount of chunks than collab-dedup, because it receives the adver- tisements faster, which enables it to avoid waiting during read calls. However, even if collab-dedup needs to wait for more chunks to be fetched during read calls, the delay is minimal, because it still receives advertisements in time to be able to fetch the missing content from other peers, which limits the performance overhead to less than 4% (as shown in the previous section). This effect is directly observable when comparing the amount of chunks fetched from the NFS server: it remains the same in both cases.

However, when moving to the case in which the number of VM instances that access Repo-1 is 50% and 25%, the interactions with the NFS server double for collab-simple when compared to collab-dedup. This confirms the speed-up of up to 2x for collab-dedup over collab-simple discussed in the previous section. Interesting to note in these two cases is the fact that collab-simple manages to prefetch an even higher amount of chunks than in the previous case, with only a small amount of chunks fetched on-demand from other peers. This is explained by the fact that the increasing I/O pressure on the NFS server introduces more latencies that can be exploited to finish more prefetch operations. However, this achievement is overshadowed by the need to access twice as many chunks from the NFS server. By contrast, collab-dedup maintains a constant proportion of accesses to the NFS server, which remains the same across all three cases.

V. CONCLUSIONS

In this paper we have proposed a novel approach to deal with unrelated groups of VM instances that perform collective on-demand read access patterns simultaneously. Our proposal is based on the idea of detecting and exchanging identical content on-the-fly both inside and outside of the groups, which reduces the overall I/O pressure on the cloud storage system to a higher degree than what techniques designed to deal with individual groups can achieve.

To demonstrate the benefits of our approach, we ran extensive experiments using a representative scenario for variable group compositions and multiple concurrency configurations. Our key findings are as follows: we observed a speedup of completion time up to 11x compared with a naïve solution that directly reads from the cloud storage for each VM instance individually. Also, we observed a speed-up of 1.88x-2x compared with collaborative schemes optimized for individual groups. The maximum speedup is reached when the groups are of equal size. Even when there is a single group, our approach exhibits a low performance overhead (4%) compared with an approach that is specifically optimized for a single group. Furthermore, we show excellent scalability both in terms of performance and consumption of the I/O bandwidth of the cloud storage (negligible growth when increasing the number of VM instances).

In future work we plan to explore several promising avenues. First, we did not explore what happens when the groups are not operating simultaneously and/or access common content at different times. How to leverage and anticipate such de-synchronizations can provide further potential for improvement. Second, our approach treats all chunks individually, both in terms of advertisements and exchanges. Thus, it would be interesting to understand and exploit correlations between chunks (e.g., what clusters of chunks go together and could be advertised and prefetched as a group).

Fig. 1 .

 1 Fig.1. Cloud architecture that integrates our approach (dark background)

  Weak scalability when 25% of VMs access Repo-1 and 75% of VMs access RepoWeak scalability when 50% of VMs access Repo-1 and 50% of VMs access RepoPerformance of 32 VMs when gradually increasing the number of VMs that access Repo-1

Fig. 3 .

 3 Fig.3. Network traffic broken down by source and type for 32 VM instances and different group sizes corresponding to Repo-1 and Repo-2. Abbreviations are used for the three approaches as follows: nfs stands for nfs-direct, cs stands for collab-simple and cd stands for collab-dedup.

  Algorithm 2 Collaborative chunk advertisement and exchange with other peers 1: procedure BACKGROUND EXCHANGE

	2:	while true do
	3:	msg ← listen for any message from any peer
	4:	hash ← extract chunk fingerprint from msg
	5:
	7:	mirror chunk p locally
	8:	State[p] ← LOCAL
	9:	advertise F ingerprint[p] to neighbors
	10:	end if
	11:	if msg = fetch request then
	12:	send chunk to requester
	13:	end if
	14:	if msg = advertisement from P eer then
	15:	Source[p] ← Source[p] ∪ {P eer}
	16:	if State[p] = REM OT E then
	17:	State[p] = W AIT
	18:	ask P eer to send chunk p
	19:	end if
	20:	end if
	21:

p ← find parent p for hash in F ingerprint 6: if msg = fetch reply and State[p] = W AIT then