Entropies and entropic criteria

Introduction

This chapter focuses on the notions of entropy and of maximum entropy distribution which will be characterized according to different perspectives. Beyond links with applications in engineering and physics, it will be shown that it is possible to build regularization functionals based on the use of a maximum entropy technique, which can then possibly be employed as ad hoc potentials in data inversion problems.

The chapter begins with an overview of the key properties of information measures, and with the introduction of various concepts and definitions. In particular, the Rényi divergence is defined, the concept of escort distribution is presented, and the principle of maximum entropy that will be subsequently used will be commented on. A conventional engineering problem is then presented, the problem of source coding, and it shows the benefit of using measures with a different length than the standard measure, and in particular an exponential measure, which leads to a source coding theorem whose minimum bound is a Rényi entropy. It is also shown that optimal codes can be easily calculated with escort distributions. In Section 1.4, a simple state transition model is introduced and examined. This model leads to an equilibrium distribution defined as a generalized escort distribution, and as a byproduct leads once again to a Rényi entropy. The Fisher information flow along the curve defined by the generalized escort distribution is examined and connections with the Jeffreys divergence are achieved. Finally, various arguments are obtained which, in this framework, lead to an inference method based on the minimization of the Rényi entropy under a generalized mean constraint, that is to say, taken with Chapitre rédigé par Jean-François BERCHER. regard to the escort distribution. From subsection 1.5.3, the main concern is about the minimization of the Rényi divergence subject to a generalized average constraint. The optimal density that solves this problem, and the value of the corresponding optimal divergence are given and characterized. The main properties of any entropy that may be related are defined and characterized. Finally, it is shown how to practically calculate these entropies and how it can be envisaged to use them for solving linear problems.

Some entropies in information theory

The concept of information plays a major role in a number of scientific and technical fields and in their applications. Moreover, information theory, "the Shannon way", meets the theories of physics, mutually fertilizing each other; these interactions have been exploited by Jaynes [JAY 57a, JAY 57b] since 1957, are discussed for example by Brillouin [BRI 62] and more recently in the fascinating work of [MER 10]. We will further give a simple model of phase transition that yields a Rényi entropy.

A fundamental question in information theory is of course the measure, or the definition, of the information. Several approaches are possible. The first is pragmatic and accepts as measure of valid information the measures that appear by themselves when solving a practical problem. The second is axiomatic, which starts with a certain number of reasonable properties or postulates, and then carries on with the mathematical derivation of the functions that exhibit these properties. This is the point of view adopted originally by Shannon, in his fundamental article [SHA 48a, SHA 48b], and that has led to a number of subsequent developments, among which [ACZ 75] and [ACZ 84] will be cited (where the author warns against the excesses of generalizations: "I wish to urge here caution with regard to generalizations in general, and in particular with regard to those introduced through characterizations. (...) There is a large number of "entropies" and other "information measures" and their "characterizations", mostly formal generalizations of (1), ( 19), ( 16), ( 24), ( 17), (23) etc. popping up almost daily in the literature. It may be reassuring to know that most are and will in all probability be completely useless."

Similarly, Rényi himself [CSI 06, RÉN 65] stressed that only quantities that can actually be used in concrete problems should be considered as information measures, in agreement with the pragmatic approach (As a matter of fact, if certain quantities are deduced from some natural postulates (from "first principles") these certainly need for their final justification the control whether they can be effectively used in solving concrete problems).

Main properties and definitions

We will however remind here the main properties used for the caracterizations of information measures. If P , Q, R refer to discrete probability distributions for n events, with p k the probability associated to the k-th event k = 1, . . . , n, then noting H(P ) = H(p 1 ,p 2 , . . . , p n ) the information measure related to distribution events P , the main properties are as follows:

-(P1) symmetry: H(p 1 ,p 2 , . . . , p n ) does not depend on the order of the events;

-(P2) H(p,1 -p) is a continuous function of p; -(P3) H(1/2,1/2) = 1; -(P4) recursion (branching): H n+1 (p 1 q 1 ,p 1 q 2 ,p 2 , . . . , p n ) = H n (p 1 ,p 2 , . . . , p n ) + p 1 H 2 (q 1 ,q 2 ); - (
H n+1 (p 1 q 1 ,p 1 q 2 ,p 2 , . . . , p n ) = H n (p 1 ,p 2 , . . . , p n ) + m(p 1 )H 2 (q 1 ,q 2 ).

Simple consequences

The first four postulates are Faddeev's axioms [FAD 56], that suffice to uniquely characterize the Shannon entropy:

H(P ) = - n i=1 p i ln p i [1.1]
If the recursion postulate is evaluated but an additivity requirement is added, then the class of possible solutions is much wider, and includes in particular the Rényi entropy, which will be referred further in the text. The replacement of the P4 recursion by a general recursion postulate, P8, with m(p 1 p 2 ) multiplicative m(p 1 p 2 ) = m(p 1 )m(p 2 ) and especially m(p) = p q leads to the entropy of order q:

H q (P ) = 1 2 1-q -1 n i=1 p q i -1 [1.2]
which was introduced by [HAV 67], independently by Daróczy [DAR 70], and then rediscovered in the field of statistical physics by C. Tsallis [TSA 88]. For q 1, these entropies are subadditive, but are not additive. In the case of q = 1, by l'Hôpital's rule, the entropy of order q = 1 is none other than the Shannon entropy. In statistical physics, a significant community has formed around the study of nonextensive thermodynamics (non-additive in fact) [TSA 09] based on the use of the Tsallis entropy, on associated maximum entropy distributions and on the extension of classical thermodynamics. In Faddeev's axiomatics, Rényi [RÉN 61] has proposed to replace the recursion postulate by the additivity property, and add a property of mean entropy, which specifies that the entropy of the union of two incomplete probability distributions is equal to the weighted average of the two entropy distributions. When the mean being used is an arithmetic mean, the only solution is the Shannon entropy. On the other hand, by using an exponential mean, the entropy that appears is a Rényi entropy:

H q (P ) = 1 1 -q ln n i=1 p q i [1.3]
Another way to apprehend the Rényi entropy is to note that the Shannon entropy is the arithmetic mean, with weights p i , of the basic information I i = -ln p i associated to the different events. By replacing the arithmetic mean by a Kolmogorov-Nagumo average, the entropy becomes:

H ψ (p 1 , . . . , p n ) = ψ -1 p i ψ(-ln p i )
Under an additional additivity condition and under the condition lim p→0 H ψ (p, 1 -p) = 0, this entropy is either the Shannon entropy, the Rényi entropy, with q 0. Again, by l'Hospital's rule, the Shannon entropy is met once again for q = 1. Furthermore, for q = 0, the Rényi entropy becomes the Hartley entropy, the logarithm of the number of events of non-zero probability.

Entropies and divergences in the continuous case

In the continuous case, the definition used for the Shannon entropy associated with a density f (x) is:

H[f ] = -f (x) ln f (x) dx [1.4]
However, it should be noted that this expression only results from the transition to the limit of the discrete case up to an additive constant tending to infinity (see for example [PAP 81]). Therefore, the concern is rather about differential entropy. However, Jaynes has lucidly noted that, since [JAY 63, p. 202], it is necessary to introduce a measure m(x) accounting for "points density" shifting the procedure to the limit; this measure conferring in addition a coordinate change invariance to the resulting information, which is not the case of [1.4]. The corresponding differential entropy then takes the form:

H[f ] = -f (x) ln f (x) m(x) dx [1.5]
This form is similar to a Kullback-Leibler divergence [KUL 59] (or I-divergence in Csiszár's terminology) between two probability distributions with densities f (x) and g(x) relatively to a common measure µ(x), and which is defined by:

D(f ||g) = f (x) ln f (x) g(x) dµ(x) [1.6]
by assuming g absolutely continuous relatively to f, and with the convention 0 ln 0 = 0. When g is uniform, with respect to µ, the Kullback divergence becomes, in absolute value, a µ-entropy. In the case where µ is the Lebesgue measure, the differential Shannon [1.5] entropy appears once again; in the discrete case, if µ is the counting measure, then [1.1] will appear again. It is easily shown, by application of Jensen's inequality that the Kullback divergence is defined as non-negative, D(f ||g) 0 with equality if and only if f = g. It can thus be understood as a distance between distributions, although it is not symmetric and does not check not the triangle inequality.

In the same way, continuous versions of Rényi and Tsallis entropies can be defined. For an entropy index q = 1:

S q [f ] = 1 1 -q f (x) q dµ(x) -1 [1.7]
is the Tsallis entropy and:

H q [f ] = 1 1 -q ln f (x) q dµ(x) [1.8]
that of Rényi. These two entropies are tantamount to the Shannon entropy for q = 1. Divergence can also be associated to them; for example, the Rényi divergence:

D q (f ||g) = 1 q -1 ln f (x) q g(x) 1-q dµ(x) [1.9]
which is also defined as non-negative (by Jensen's inequality), and is reduced to the Kullback divergence when q → 1.

Maximum entropy

The principle of maximum entropy is widely used in physics, and can rely on a large number of arguments: counts, axioms, etc. The principle has been particularly highlighted by Jaynes [JAY 57a] "Information theory provides a constructive criterion for setting up probability distributions on the basis of partial knowledge, and leads to a type of statistical inference which is called the maximum entropy estimate. It is the least biased estimate possible on the given information; i.e., it is maximally noncommittal with regard to missing information", and we will confine ourselves here to recall its relevance in terms of statistics, by following Ellis [ELL 99] (theorem 2 for example).

If f N is the empirical distribution corresponding to the collection of N random variables according to a density distribution g relatively to µ, then the probability Q of finding f N in a set B is roughly (see Ellis [ELL 99] for more correct formulations), and for large N :

Q (f N ∈ B) ≈ exp -N inf P ∈B D(f ||g) [1.10]
It can be thus derived, by iterating reasoning on subsets of B, that the absolutely predominant distribution in B is the one that achieves the minimum Kullback distance to g: there is concentration of all the probability on the closest distribution to g. A minimum distance Kullback principle can thus be derived, or equivalently, if g is uniform, a principle of maximum entropy. Among all the distributions of a set B, the density that minimizes D(f ||g) should be selected. When the point of interest is, as in statistical physics, the probability of finding an empirical mean x N , that is to say, the mean under f N , in a set C, then a result with large level 1 deviations is obtained, which indicates that:

Q (x N ∈ C) ≈ exp -N inf x∈C F(x) [1.11]
where F(x) is the rate function F(x) = inf P :x=E[X] D(P ||µ). This result suggests thus to select the most probable element, that which achieves the minimum of F(x) on C. The shift from a problematics of distributions to a problematics of means is known as the contraction principle.

Escort distributions

We will also use in the remainder of this chapter the notion of escort distribution. These escort distributions have been introduced as a tool in the context of multifractals [BEC 93, CHH 89], with interesting connections with standard thermodynamics. Escort distributions are proving useful in source coding, where they enable optimal code words to be obtained whose mean length is bounded by a Rényi entropy [BER 09]. This is what we will present in 1.3.3. We will then find these escort distributions in the framework of a state transition problem, Section 1.4.

If f (x) is a probability density, then its escort of order q 0 is:

f q (x) = f (x) q f (x) q dµ(x) [1.12]
provided that the informational generating function M q [f ] = f (x) q dµ(x) is finite.

We can easily see that if f q (x) is the escort of f (x), then f (x) is itself the escort of order 1/q of f q (x). When q decreases, the escort comes closer to a uniform distribution whereas when q increases, density modes are amplified. This can be specified: as a matter of fact, it can be shown, in the compact support case that D(f q ||U ) > D(f ||U ) for q > 1, and that D(f q ||U ) < D(f ||U ) for q < 1, which means that f q is further away from the uniform than f when q > 1 and closer otherwise.

The concept of escort distribution can also be expanded in order to take into account two densities f (x) and g(x) according to:

f q (x) = f (x) q g(x) 1-q f (x) q g(x) 1-q dµ(x) [1.13] when M q [f, g] = f (x) q g(x) 1-q dµ(x) < ∞. This generalized escort distribution is simply a weighted geometrical mean of f (x) et g(x). Of course, if g(x)
is a uniform measure whose support includes that of f (x), then the generalized escort is reduced to the standard escort [1.12]. This generalized escort appears in the analysis of the effectiveness of hypotheses tests [CHE 52] and allows the best possible exponent to be defined in the error probability [COV 06, chapitre 11]. When q varies, the generalized escort describes a curve that connects f (x) and g(x). Finally, we will call generalized moments the moments taken with respect to an escort distribution: the generalized of order p associated to the standard escort of order q will be:

m p,q [f ] = |x| p f q (x) dx = |x| p f (x) q dµ(x) f (x) q dµ(x) [1.14]

Source coding with escort distributions and Rényi bounds

In this section, the advantage of the Rényi entropy and escort distributions is illustrated within the framework of source coding, one of the fundamental problems of information theory. After a very brief reminder of the context of source coding, a source coding theorem is described linking a new measure of mean length and the Rényi entropy. It is then shown that it is possible to practically calculate the optimal codes by using the concept of escort distribution. Details about these elements as well as other results are given in [BER 09].

Source coding

In source coding, considering a set X = {x 1 , x 2 , . . . , x N } of symbols generated by a source with respective probabilities p i where coding is to associate to each symbol x i a code word c i , with length l i , expressed with an alphabet of D elements. It is well known that if the lengths verify Kraft-Mac Millan inequality:

N i=1 D -li 1 [1.15]
then there exists a uniquely decodable code with these elementary lengths. In addition, any uniquely decodable code satisfies Kraft-Mac Millan inequality [1.15]. Shannon's source coding theorem indicates that the mean length L of word codes is bounded from below by the source entropy, H 1 (p), and that the best uniquely decodable code satisfies:

H 1 (p) L = i p i l i < H 1 (p) + 1 [1.16]
where the logarithm used in the Shannon entropy is calculated in base D, and noted log D . This result indicates that the Shannon entropy H 1 (p) is a fundamental limit to the minimal mean length for any code built for the source. The lengths of the optimal word codes are given by:

l i = -log D p i [1.17]
The characteristic of these optimal codes is that they assign the shortest words to the most probable symbols and the longest words to the rarest symbols.

Source coding with Campbell measure

It is well known that the Huffman algorithm provides a prefix code that minimizes the mean length and approaches the optimal length limits l i = -log D p i . However other forms of length measurement have also been considered. In particular the first, that of Campbell [CAM 65], is fundamental. It has been seen, by relation [1.17], that the lowest probabilities lead to longer word codes. However, the cost of using a code is not necessarily a linear function of its length, and it is possible that the addition of a letter to a long word is much more expensive than the addition of the same letter to a short word. This led Campbell to propose a new measure of mean length, by introducing an exponential penalty of the lengths of the word codes. This length, the Campbell length, is a generalized Kolmogorov-Nagumo average associated with an exponential function:

C β = 1 β log D N i=1 p i D βli [1.18]
with β > 0. The remarkable result of Campbell is that, in the same way as the Shannon entropy places a lower bound on the average length of the word codes, the Rényi entropy of order q, with q = 1/(β + 1), is the lower bound of the mean Campbell length [1.18]:

C β H q (p) [1.19]
A simple demonstration of the result is given in [BER 09]. It is easy to see that equality is obtained for:

l i = -log D P i = -log D p q i N j=1 p q j [1.20]
Clearly, the lengths l i obtained in this way can be made smaller than the optimal Shannon's lengths, by choosing a quite small parameter q, which then tends to standardize the distribution, then actually enhancing the the lowest probabilities. Thus, the procedure effectively penalizes the longest word codes and provides word codes of different lengths than Shannon's, with eventually shorter word codes associated with the low probabilities.

Source coding with escort mean

For the usual mean length measure L = i p i l i , there is a linear combination of the elementary length, weighted by probabilities p i . In order to increase the impact of the most important lengths associated with low probabilities, the Campbell length uses an exponential of the elementary lengths. Another idea is to modify the weights in the linear combination, such that to increase the importance of the words with low probabilities. A simple way to achieve this is to standardize the initial probability distribution, and to use the weights achieved by this new distribution rather than p i . Naturally, this leads to use a mean taken with an escort distribution:

M q = N i=1 p q i j p q j l i = N i=1 P i l i [1.21]
In the case of the imaginary source that would have a distribution P the standard statistics mean is M q , and Shannon's classical source coding theorem can immediately be applied:

M q H 1 (P ) [1.22]
with equality if:

l i = -log D P i [1.23]
or exactly the lengths [1.20] obtained for Campbell's measure. The simple relation l i = -log D P i obtained for the minimization of M q under the constraint supplied by Kraft-Mac Millan's inequality has an immediate but important application. As a matter of fact, it simply suffices to provide the escort distribution P rather than the initial distribution p to an standard encoding algorithm, for example a Huffman algorithm, to obtain an optimized code for the Campbell length C β , or in a similar manner, for the measurement of length M q . Table 1.1 gives a simple example with D = 2 : we have used a standard Huffman algorithm, with the initial distribution, then its escorts of order q = 0.7 and q = 0.4. pi q = 1 q = 0,7 q = 0,4 0,48 0 0 00 0,3 10 It is important to note that specific algorithms have been developed for the mean Campbell length. The above connection provides an easy and immediate alternative. Another important point is that these codes have practical applications: they are optimal for the minimization of the probability of buffer overflowing [HUM 81] or, with q > 1, for maximizing the probability of receiving a message in single send of limited size.

A simple transition model

In the previous section, we have seen emerging, and appreciated the significance of the Rényi entropy and escort distributions for a source coding problem. In this section, we will show that these two quantities are also involved in an equilibrium, or a transition model framework, between two states. It has actually been noted that extended thermodynamics, associated to the Tsallis and Rényi entropies, seems particularly relevant in the case of deviations from the conventional Boltzmann-Gibbs equilibrium. This suggests then to amend the conventional formulation of the conventional approach of maximum entropy (or of the the minimum of divergence) and to imagine an equilibrium characterized by two (and no longer a single) distributions: rather than selecting the nearest distribution of a reference distribution under a mean constraint, an intermediary distribution p q (x) is desired, in a sense that needs clarification, between two references p 0 (x) et p 1 (x). This construction, as well as some of its consequences, are also described in [BER 12].

The model

Considering two density states with probabilities p 0 (x) and p 1 (x) at point x of the phase space, and searching for an intermediate state according to the following scenario. The initial state system p 0 , subject to a generalized force, is moved and held at a distance η = D(p||p 0 ) of p 0 . On the other hand, the system is attracted towards a final state p 1 . As a result, the new intermediate state p q is chosen such that it minimizes its divergence from the attractor p 1 while being maintained at a distance η of p 0 . As illustrated in figure 1.1, the intermediate probability density is "aligned" with p 0 and p 1 and at the intersection with the set D(p||p 0 ) = η, a circle of radius η centered on p 0 . More specifically, by taking densities relatively to the Lebesgue measure, the problem can be formulated as follows:

   min p D(p||p 1 ) under D(p||p 0 ) = η and p(x) dx = 1 [1.24]
The solution is given by the following proposition. PROPOSITION 1.1.-If q is a real positive that D(p q ||p 0 ) = η and if M q (p 1 ,p 0 ) = p 1 (x) q p 0 (x) 1-q dx < ∞, then, the solution of the problem [1.24] is given by:

p q (x) = p 1 (x) q p 0 (x) 1-q p 1 (x) q p 0 (x) 1-q dx [1.25] REMARQUE.
-When p 0 is uniform and with compact support, the standard escort distribution [1.12] is met once again. If media is not compact and uniform distribution improper, it is possible to simply change the formulation by taking as a constraint a fixed entropy H(p) = -η, and then the escort distribution is obtained. Let us evaluate the divergence D(p||p q ). For all densities p such that constraint D(p||p 0 ) = η is satisfied, it yields: D(p||p q ) = p(x) ln p(x) p q (x) dx = p(x) ln p(x) q p(x) 1-q p 1 (x) q p 0 (x) 1-q dx + ln M q (p 1 ,p 0 )

= q p(x) ln p(x) p 1 (x) dx + (1 -q) p(x) ln p(x) p 0 (x) dx + ln M q (p 1 ,p 0 ) = q D(p||p 1 ) + (1 -q)η + ln M q (p 1 ,p 0 ) [1.26]
By taking p = p q , the last equality becomes:

D(p q ||p q ) = q D(p q ||p 1 ) + (1 -q)η + ln M q (p 1 ,p 0 ) [1.27]
Finally by subtracting [1.26] and [1.27], it gives:

D(p||p q ) -D(p q ||p q ) = q (D(p||p 1 ) -D(p q ||p 1 )) [1.28]
Since q 0 and D(p||p q ) 0 with equality if and only if p = p q , it finally yields D(p||p 1 ) D(p q ||p 1 ) which proves the proposition 1.1. When η varies, the function q(η) is increasing, with still D(p q ||p 0 ) = η. For η = 0 it gives q = 0 and for η = D(p 1 ||p 0 ) it gives q = 1. Therefore, when q varies, p q defines a curve that links p 0 (q = 0) to p 1 (q =1), and beyond for q > 1, see figure 1.1. REMARQUE.-It is interesting to also note that results have shown that work dissipated during a transition can be expressed as a Kullback-Leibler divergence [PAR 09]. In this context, with a Halmitonian pair following the impulse, the constraint D(p||p k ) = η, k = 0 where 1, can be interpreted as a bound on the average work dissipated during the transition from p to p k .

The Rényi divergence as a consequence

Finally, it is interesting to note that the Rényi divergence appears as a byproduct of our construction. As a matter of fact, as a direct consequence of [1.27] and of the definition of the Rényi divergence [1.9], the minimum Kullback information can be expressed as:

D(p q ||p 1 ) = 1 - 1 q (η -D q (p 1 ||p 0 )) [1.29]
By taking a uniform measure for p 0 , the Rényi entropy is revealed.

D(p q ||p 1 ) = 1 - 1 q (η + H q [p 1 ]) [1.30]
The Kullback-Leibler divergence is not symmetrical. Since the beginning, Kullback and Leibler have introduced a symmetrical version, returning again to the Jeffreys divergence. In our case, this Jeffreys divergence is a simple affine function of the Rényi divergence:

J(p 1 ,p q ) = D(p 1 ||p q ) + D(p q ||p 1 ) = (q -1) 2 q (D q (p 1 ||p 0 ) -η) [1.31]
This equality is a simple consequence of the relation [1.26], with p = p 1 , and the relation [1.27]. It can be noted, as a significant consequence, that the minimization of the Jeffreys divergence between p 1 and p q under certain constraints, is therefore equivalent to the minimization of the Rényi divergence with the same constraints.

Fisher information for the parameter q

The generalized escort distribution p q defined a curve indexed by q linking distributions p 0 and p 1 for q = 0 and q = 1. It is interesting to evaluate the attached information to the parameter q of the generalized distribution. This Fisher information is given by:

I(q) = 1 p q (x) dp q (x) dq 2 dx = dp q (x) dq ln p 1 (x) p 0 (x) dx [1.32]
where the right term is obtained using the relation:

dp q (x) dq = p q (x) ln p 1 (x) p 0 (x) - d ln M q dq [1.33]
and the fact that: dp q (x) dq dx = d dq p q (x) dx = 0 by Leibniz's rule. It can also be shown that this Fisher information is equal to the variance, with respect to the distribution p q , of the likelihood ratio.

Finally, it is possible to identify the integral of the Fisher information along the curve, the "energy" of the curve, at the Jeffreys divergence. More specifically, the following proposal is given. PROPOSITION 1.2.-The integral of the Fisher information, from q = r to q = s is proportional to the Jeffreys divergence between p r and p s :

(s -r) s r I(q) dq = J(p s ,p r ) = D(p s ||p r ) + D(p r ||p s ) [1.34]
With r = 0 et s = 1, it therefore yields that:

1 0 I(q) dq = J(p 1 ,p 0 ) = D(p 1 ||p 0 ) + D(p 0 ||p 1 ) [1.35]
To demonstrate [1.34], it is sufficient to integrate [1.32]:

s r I(q) dq = s r dp q (x) dq ln p 1 (x) p 0 (x) dx dq = (p s (x) -p r (x)) ln p 1 (x) p 0 (x) dx
Taking into account the fact that ln p s /p r = (s -r) ln p 1 /p 0 , we then get [1.34].

Finally, if θ i , i = 1..M is a set of intensive variables depending on q, then

d ln p dq = M i=1
∂ ln p ∂θi dθi dq and the Fisher information q can be expressed according to the Fisher information matrix of θ. In these conditions, and for the generalized escort distribution, the result is that the "thermodynamic divergence" for the transition is none other than the Jeffreys divergence [1.35]:

J = 1 0 I(q) dq = M i=1 M j=1 1 0 dθ i dq [I(θ)] i,j dθ dq dq = D(p 1 ||p 0 )+D(p 0 ||p 1 ) [1.36]
1.4.4. Distribution inference with generalized moment constraint

Assuming now that the p 1 distribution is imperfectly known, but that additional information is available under the form of a mean value, achieved with distribution p q . This mean is the generalized mean [1.14], which is used in non-extensive statistical physics; It has here the clear interpretation of a mean obtained from the equilibrium distribution p q . The problem that arises now is then the determination of the most general distribution compatible with this constraint.

The idea of minimizing the divergence to p 1 can be retained as in the problem [1.24] which has led us to the equilibrium distribution with generalized escort. Since the Kullback divergence is directed, the direction will be retained by minimizing D(p q ||p 1 ) for q < 1 and D(p 1 ||p q ) for q > 1. In both cases, the divergence is expressed as an affine function of the Rényi divergence D q (p 1 ||p 0 ), see [1.29], and these minimizations are finally equivalent to the minimization of the Rényi divergence under the generalized mean constraint.

Similarly, the concern could be about the minimization of the symmetric Jeffreys divergence between p q and p 1 . However, we have noted in [1.31] that this is also expressed as a simple affine function of the Rényi divergence: Its minimization is therefore equivalent to the minimization of the Rényi divergence under a generalized mean constraint.

Finally, the Jeffreys divergence J(p 1 ,p q ) is proportional to the thermodynamic divergence, the integral of the Fisher information, as shown in [1.34], for q > 1 as well as for q < 1. Therefore, the minimization of the thermodynamic divergence between p q and p 1 is also equivalent to the minimization of the Rényi divergence.

These different arguments very legitimately lead us to search for distribution p 1 as the distribution minimizing the Rényi divergence of index q, under the generalized mean constraint.

Minimization of the Rényi divergence and associated entropies

In previous paragraphs we have described a framework enabling the Rényi information, the escort distributions and generalized moments to appear naturally. In addition, we in have derived an inference distribution method: the minimization of the Rényi information, with information available in the form of generalized moments. In this section, we will first give the expression for the density that minimizes the Rényi divergence, then we will describe some properties of the associated partition functions. Finally, we will show how new entropic functionals can be derived of which a few examples will be given. Some of these results, but also some extensions can be referred to in [BER 08].

Minimisation under generalized moment constraint

We will first consider a generalized moment of any order [1.14], whose expression is mentioned below:

m p,q [f ] = |x| p f q (x) dµ(x) = |x| p f (x) q g(x) 1-q dµ(x) f (x) q g(x) 1-q dµ(x) [1.37]
The problem is then considered:

F q (m) =    min f D q (f ||g) under m = m p,q [f ] and f (x) dµ(x) = 1 [1.38]
The minimum obtained is of course a function of m, that will be noted F q (m). It is a contracted version of the Rényi divergence, which defines an "entropy" in the space of possible means m. In [BER 11], we have considered a more general problem, in which the indices of the generalized moment and of the Rényi divergence are not identical. In any case, the result here obtained is as follows.

PROPOSITION 1.3.-The density G γ which achieves the minimum in the problem [1.38] is given by:

G γ (x) = 1 Z ν (γ,x p ) (1 -(1 -q)γ (|x| p -xp )) ν + g(x) [1.39]
or equivalently by:

G γ (x) = 1 Z ν (γ) (1 -(1 -q)γ|x| p ) ν + g(x) [1.40]
with ν = 1/(1 -q), xp an eventual translation parameter, γ and γ selected scaling parameters chosen such that the generalized constraint moment is satisfied, and finally where (x) + = max(0,x). Quantities Z ν (γ,x p ) and Z ν (γ) are partition functions that allow the standardization of the density. For q = 1, density G γ (x) becomes an exponential density:

G γ (x) = 1 Z ν (γ) exp (-γ (|x| p -xp )) g(x) [1.41]
with respect to g(x).

In the case p = 2, a Gaussian density is thus found once again. Density G γ is sometimes called "generalized Gaussian". It should noted once more that γ and γ are determined by the relation:

γ = γ 1 + γ ν xp [1.42]
In the case of expression [1.40], the demonstration is here proposed. The approach is rather similar in the case of density [1.39].

As in [BER 11], let A(γ) = 1/Z(γ). It immediately yields:

f q G 1-q γ dµ(x) = A(γ) 1-q M q [f, g] × (1 -(1 -q)γ|x| p ) + f q g 1-q M q [f, g] dµ(x) A(γ) 1-q (1 -(1 -q)γ m p,q [f ]) M q [f, g] [1.43]
with M q [f, g] = f a g 1-q dµ(x), where m p,q [f ] refers to the generalized, and where the inequality results from the fact that the support (1 -(1 -q)γ|x| p ) + can be included in that of f q g 1-q . From [1.43] it directly gives, with f = G γ :

M 1 [G γ ] = 1 = A(γ) 1-q (1 -(1 -q)γ m q,p [G γ ]) M q [G γ , g] [1.44]
Thus, for all distributions f of generalized m p,q [f ] = m and for γ such that G γ has the same moment m p,q [G γ ] = m, then the combination of [1.43] and [1.44] results in:

f q G 1-q γ dµ M q [f, g] M q [G γ , g]
Finally the Rényi divergence of order q can thus be expressed as:

D q (f ||G γ ) = ln f q G 1-q γ dµ(x) 1 q-1 [1.45] ln M q [f, g] M q [G γ , g] 1 q-1 = D q (f ||g) -D q (G γ ||g) [1.46]
By the non-negativity of the divergence, it thus ensues that:

D q (f ||g) D q (G γ ||g) [1.47]
for all distributions f of generalized m p,q [f ] = m p,q [G γ ] = m, and with equality if and only if f = G γ .

A few properties of the partition functions

Some important properties of partition functions Z ν (γ,x p ) associated to the optimal density G γ are given here (see [BER 08]). These properties will be essential for the characterization of entropic functionals F q (x). E ν refers to the statistic mean taken relatively to the optimum density distribution [1.39], with ν = 1/(1 -q). It is also important to realize, from now on, that the escort density of order q of [1.39] is none other than this same density G γ but with an exponent ν -1, such that:

m p,q [G γ ] = E ν-1 [X] [1.48]
The successive partition functions are linked by:

Z ν (γ,x p ) = E ν-1 1 - γ ν (|x| p -x p )) Z ν-1 (γ,x) [1.49]
As a direct result, it can be seen that Z ν (γ,x p ) = Z ν-1 (γ,x p ) if and only if

x p = E ν-1 [|X| p ] .
Using Leibniz's rule, the derivative with respect to γ can be obtained and is given by:

d dγ Z ν (γ,x p ) = -E ν-1 [|X| p -x p ] + γ dx p dγ Z ν-1 (γ,x p ) [1.50]
under the condition that x p is really differentiable with respect to γ. Similarly:

d dx p Z ν (γ,x p ) = - dγ dx p E ν-1 [|X| p -x p ] + γ Z ν-1 (γ,x p ) [1.51] Thus, if x p = E ν-1 [|X| p ]
, then taking into account the equality of the partition functions of rank ν and ν -1, it gives:

d dγ ln Z ν (γ,x p ) = γ dx p dγ [1.52]
or even:

d dx p ln Z ν (γ,x p ) = γ [1.53]
On the other hand, when x p is an independent parameter of γ, say x p = m, then:

d 2 Z ν (γ,m) dγ 2 = ν -1 ν E ν-2 (X -m) 2 Z ν-2 (γ,m) [1.54]
and similarly:

d 2 Z ν (γ,m) dm 2 = ν -1 ν γ 2 E ν-2 (X -m) 2 Z ν-2 (γ,m) [1.55]
which, considering the fact that (ν -1)/ν = q > 0, the fact that partition functions are strictly positive, shows that if x p = m and γ are independent, then the partition Z ν (γ,m) is convex in its two variables.

Finally, the solution of the problem [1.38] can be expressed, that is F q (m), from the partition function. By direct calculation, it actually yields:

D q (G γ ||g) = 1 q -1 ln Z qν (γ,x p ) - q q -1 ln Z ν (γ,x p ) [1.56]
which is simply reduced to:

F q (m) = D q (G γ ||g) = -ln Z ν (γ,m) = -ln Z ν-1 (γ,m) [1.57]
for the value of γ such that the constraint is satisfied, or m p,q

[G γ ] = E ν-1 [X] = xp = m.
1.5.3. Entropic functionals derived from the Rényi divergence Thus, the solution of the minimization problem of the Renyi divergence of order q viewed as a function of constraint, defines an "entropic functional". Different functionals will be associated with the several specifications of the reference density g(x), as well as with the various values of the index q. We will see that the functions in question present interesting properties. Therefore, a set of functions is potentially available that can be eventually used as objective functions or regularization terms.

The main characterization of F q (m) is as follows.

PROPOSITION 1.4.-The entropy F q (m), defined by [1.38], is non-negative, with a single minimum m g , the average of g, and F q (m g ) = 0. The entropy is a pseudoconvex function for q ∈ [0,1) and strictly convex for q 1. The Rényi divergence D q (f ||g) is always non-negative, and zero only for f = g. Since functionals F q (m) are defined as the minimum of the divergence D q (f ||g), they are always non-negative. Based on [1.53], it gives d dx ln Z ν (γ,x) = γ. Thus, functionals F q (x) are only presenting a single singular point in γ = 0. For this value of γ, it yields G γ=0 = g, and D q (g||g) = 0. Under these conditions, F q (x) has a unique minimum for x = m g , the mean of g, and F q (m g ) = 0. Therefore, it follows that F q (x) is unimodal and does not present any points of inflection with a horizontal tangent; this is sufficient to claim that F q (x) is pseudo-convex, as referred to by Mangasarian [MAN 87]. Let us now examine the convexity for q 1. If f q is the generalized escort distribution given by [1.13], then the equality D q (f ||g) = D 1/q (f q ||g) holds. Subsequently, searching for the distribution f that achieves the minimum of D q (f ||g) with a generalized mean constraint, that is to say, taken with respect to f q , is equivalent to searching the distribution f q that minimizes D 1/q (f q ||g), under a standard moment constraint. In these circumstances, given p 1 and p 2 the two densities that minimize D 1/q (f q ||g) under constraints x 1 = E fq [X] and x 2 = E fq [X]. Then, F q (x 1 ) = D 1/q (p||g), and F q (x 2 ) = D 1/q (p 2 ||g). In the same way, given F q (µx 1 + (1 -µ)x 2 ) = D 1/q ( P ||Q), where P is the optimal escort distribution of mean µx 1 + (1 -µ)x 2 . Distributions P and µp 1 + (1 -µ)p 2 then have the same mean. Thus, when D 1/q (f q ||g) is a strictly convex function f q , that is to say for q 1 it follows that D 1/q ( P ||g) < µD 1/q (p 1 ||g) + (1 -µ)D 1/q (p 2 ||g), or F q (µx 1 + (1 -µ)x 2 ) < µF q (x 1 ) + (1 -µ)F q (x 2 ) and entropy F q (x) is a strictly convex function.

Even provided with this interesting characterization, a practical significant problem still remains: how to analytically or numerically determine the entropies F q (x) for a reference density g and a given index entropy q. The problem amounts to determine the parameter γ such that the optimal generalized mean density [1.39] has a specified value m. A simple manner of proceeding consist in recalling the fact that if xp is a fixed parameter m, independent of γ, then the derivative relation [1.50] is reduced to:

d dγ Z ν (γ,m) = (m -E ν-1 [|X| p ]) Z ν-1 (γ,m) [1.58]
Therefore, it can be seen that it suffices to search for the extrema of the partition function Z ν (γ,m) to obtain a γ such that m = E ν-1 [|X| p ] . Since we have seen that Z ν (γ,m), with fixed m, is strictly convex, then this extremum is unique and is a minimum. Finally, the value of the entropy is simply given by [1.57]:

F q (m) = -ln Z ν (γ,m).
The search for the expression of F q (m) therefore requires to compute the partition function then to solve d dγ Z ν (γ,m) = 0 with respect to γ. With the exception of a few special cases, this resolution does not seem analytically possible, and entropy F q (m) is given implicitly. In the particular case where g is a Bernoulli measure, it is possible to obtain an analytic expression for F q (m), this for any q > 0. For other reference densities g, it is possible to obtain analytic expressions when q → 1. These points are detailed in [BER 08], where in addition different densities of reference g are studied, and corresponding entropies numerically evaluated according to the scheme previously mentioned. As an example, the numerical results obtained in the case where p = 1 and a uniform density in the interval [0,1] are given in Fig. 1.2. For q 1, a family of convex functions is correctly obtained over (0,1), minimum for the mean of g, or 0.5, as we have indicated above. For q < 1, a family of non-negative, unimodal functions, also minimal in x = m g = 0.5 is obtained. respectively for q 1 and q ∈]0,1[

Entropic criteria

Based on the previous figures, it is apparent that the minimization of F q (x) under certain constraints automatically provides a solution in the interval (0,1). In addition, the parameter q can be used to adjust the curvature of the function or the penalty on the boundaries of the domain. It is thus interesting to use these entropies when the purpose is to solve inverse problems. More specifically, an entropy criterion can be used such as F q (x) as objective function. The whole of this section will be restricted to the case p = 1. When considering a linear inverse problem y = Ax, with x k the components of x, then this can be formulated as:

min x k F q (x k ) under y = Ax [1.59]
This then corresponds to select among possible solutions the solution whose components are of minimum entropy. It should be noted that it is assumed here, implicitly, that the criterion was separable into its components. In reality, if we define F q (x) as the Rényi divergence under the generalized mean constraint, then, even when assuming that components are independent, it yields a density on x similar to [1.39], which is not separable. In order to obtain a separable criterion, which is both more consistent with intuition and easier to use, we amend the formulation by searching the density product that achieves the minimum of the Rényi divergence under generalized mean constraint, which leads effectively to the separable criterion. Thus, the previous problem [1.59] can also be read as:

       min x    min f D q (f ||g) under f = k f k and x = E fq [X] under y = Ax [1.60]
where E fq [X] refers to the generalized mean, that is to say, taken with respect to the escort distribution of order q. The point of concern here is therefore a "maximum entropy" problem which consists in selecting a solution x, seen as the generalized mean of a minimum Rényi divergence distribution with a reference density g. Entropies k F q (x k ) being pseudo-convex, it is known that minimization under linear constraints leads to a single minimum (see for example [CAM 08, theorem 4.4.1]). Now let us examine how it is possible to obtain a solution of [1.59], even in the case where the entropies have no explicit expression. The solution corresponds to a stationary point of the Lagrangian L(λ,x) associated to the problem [1.59], and the objective is therefore to solve: where, for any c k , the corresponding generalized mean x k can be calculated as the unique solution of the problem:

x k = arg min x (ln Z ν (-c k ,x) + c k x)
It is thus possible to solve the problem [1.59] which provides a unique "maximum Rényi entropy" solution to the inverse linear problem y = Ax, problem where various constraints can be included, including support, through the reference density g, and where the form of the criteria can be adjusted by means of the index entropy q.

In the case where data y would be imperfect, it is possible to minimize the entropy criterion under a constraint provided by a statistic (for example, residual χ 2 ) rather than with an exact constraint. It is also possible to use the entropy criterion with a data-fidelity term.

In the case where q = 1, the Rényi divergence is reduced to the Kullback divergence, the generalized moments to the usual moments, and the optimal density to an exponential density [1.41] with respect to g.

Under these conditions, the log-partition function is written ln Z ∞ (-c k ,x k ) = -c k x k + ln exp (c k x k ) g(x k ) dµ(x k ), the problem [1.66] becomes: and the optimal solution is given by the derivative of the log-partition function with respect to c k . This latter approach has been developed in works supervised by Guy Demoment [LEB 99].

  Example of binary codes, for different values of q

  Figure1.1. Equilibrium between the states p0 and p1: the search for the equilibrium distribution is carried out in all of the distributions within a difference fixed at p0, D(p||p0) = η, and at a minimal Kullback distance of p1. The resulting equilibrium distribution pq, the generalized escort distribution is "aligned" with p0 and p1, and at the intersection of the set D(p||p0) = η.

  Figure1.2. Entropy Fq(x) for a uniform reference, respectively for q 1 and q ∈]0,1[

FF-(

  q (x k ) + λ t (y -Ax) q (x k ) -c k x k + λ t y [1.62] with c k = λ t A k . Using the fact that:F q (x k ) = -ln Z ν (γ * ,x k ) = -inf γ ln Z ν (γ,x k )as we have seen in Subsection 1.5.3, it thus gives:ln Z ν (γ * ,x k ) -c k x k + λ t y [1.63] ln Z ν (γ * ,x k ) + c k x k ) [1.64]However, by the relation [1.53], it follows:d dx k (ln Z ν (γ * ,x k ) + c k x k ) = γ * + c k [1.65]which yields γ * = -c k , and x k is the associated generalized mean. Finally, the concern is therefore about solving:max λ λ t yk (ln Z ν (-c k ,x k ) + c k x k ) [1.66]

  c k x k ) g(x k ) dµ(x k )

Titre de l'ouvrage, à définir par \title[titre abrégé]{titre}

Titre de l'ouvrage, à définir par \title[titre abrégé]{titre}

Ni=1 p i = 1. The role of source


David García-Pérez

Juan Ángel Lorenzo Del Castillo

Yahya Al-Hazmi

Josep Martrat

Konstantinos Kavoussanakis

Alastair C Hume

Celia Velayos López

Giada Landi

Tim Wauters

Michael Gienger

David Margery

Cloud and Network facilities federation in BonFIRE

Keywords: Multi-cloud, Federation, Future Internet, Services, Testbed, Bandwidth on Demand, Network QoS

In recent years we have seen how Cloud Computing is changing the way of doing businesses and how services are delivered over the Internet. This disruption is a major challenge for Service Providers and Independent Software Vendors when creating new services and software applications for the Cloud. BonFIRE 10 offers a federated, multi-site cloud testbed to support large-scale testing of applications, services and systems. This is achieved by federating geographically distributed, heterogeneous clouds testbeds where each exposes unique configuration and/or features while giving to the experimenters (users) an homogeneous way to interact with the facility. All those testbeds are controlled by a central set of services commonly denominated "Broker". Additionally, Bon-FIRE is federated with different network facilities like the Virtual Wall, FEDERICA and AutoBAHN to provide high-level interfaces to network control functionality, in order to simulate diverse network QoS scenarios, enabling vertical federation.

Introduction

Cloud computing is steadily gaining significance not only in the field of IT infrastructure and service hosting and operation, but also in telecommunication services. This encourages cloud providers to develop new technologies to enhance their services in order to increase customer satisfaction on the one hand; and to promote strategies to build new business models on the other. In this market, cloud service providers, having different kinds of resources offering different levels of service quality, succeed not only by competition but also by collaboration between each other. There are several advantages of such collaborations for both cloud service suppliers and cloud service customers. Among the advantages for cloud service providers are complementarity of the offered resources to improve resource utilization; and combination of services in order to offer efficient end-to-end solutions. On the other hand, customers have the ability to combine resources and services from different cloud computing providers to create their own environments [START_REF] Al-Hazmi | A Monitoring System for Federated Clouds[END_REF].

Cloud service providers might offer different types of services, with different APIs, various delivery conditions and prices, etc. Therefore, collaboration across cloud infrastructures that interoperate requires mechanisms for resource federation. Federated resources have to be managed at the federation level so as to be offered to users in as uniform a fashion as possible. Several resource management mechanisms are to be specified and standardized at the federation level: resource description, discovery, reservation, provisioning, orchestration, monitoring, and release. Furthermore, mechanisms are required for authentication and authorization, resource control and information exchange across cloud infrastructures.

To this end, cloud federation [START_REF] Keahey | Sky Computing[END_REF][START_REF] Rochwerger | Reservoir-When One Cloud is Not Enough[END_REF][START_REF] Vandenberghe | Architecture for the Heterogeneous Federation of Future Internet Experimentation Facilities[END_REF] architectures should be designed to include the necessarily mechanisms and fulfill all collaboration requirements. The different Cloud federation architectures proposed in the literature [START_REF] Ferrer | OPTIMIS: A Holistic Approach to Cloud Service Provisioning[END_REF] can be classified into three different models as follows:

-Cloud aggregation: [START_REF] Tordsson | Cloud Brokering Mechanisms for Optimized Placement of Virtual Machines Across Multiple Providers[END_REF] different partners cooperate to integrate their cloud infrastructures into a unique virtual facility. This architecture usually requires a higher degree of coupling. -Cloud bursting or Hybrid Clouds: [START_REF] Sotomayor | Virtual Infrastructure Management in Private and Hybrid Clouds[END_REF][START_REF] Moreno-Vozmediano | Multicloud Deployment of Computing Clusters for Loosely Coupled MTC Applications[END_REF] combines the existing on premise infrastructure (private cloud) with resources of one or more public clouds. -Brokering: [START_REF] Tordsson | Cloud Brokering Mechanisms for Optimized Placement of Virtual Machines Across Multiple Providers[END_REF] employs a central "broker" component that intermediates between user requests and several Cloud infrastructures.

There are many challenges related to cloud federation that affect interoperability (e.g. different APIs) and portability (e.g. different VM formats) [START_REF] Petcu | Portability and Interoperability Between Clouds: Challenges and Case Study[END_REF].

BonFIRE [START_REF] Hume | BonFIRE: A Multi-cloud Test Facility for Internet of Services Experimentation[END_REF] offers a Future Internet, Federated testbed, that supports large-scale testing of applications, services and systems over multiple, geographically distributed, heterogeneous Cloud and network testbeds. The design of BonFIRE is based in four pillars: Observability, Control, Advanced Features, and Easy of Use. The BonFIRE infrastructure gives the experimenters the ability to control and monitor the execution of their experiments to a degree that is not found in traditional Cloud facilities. The available testbeds allow the evaluation of cross-cutting effects of converged service and network infrastructures. In order to do so, the testbeds expose a set of capabilities beyond those normally provided by production cloud services in a commercial environment, enabling what we define as "Research by Experimentation". In terms of classification, BonFIRE employs a central broker to expose a homogeneous API and interact with the testbeds. Additionally, BonFIRE includes and federates with private and public clouds and can thus be used to model cloud-bursting scenarios.

The remainder of the paper is structured as follows; Section 2 introduces the different facilities federated and the reason why Brokering was selected as federation solution. Section 3 presents the BonFIRE federation architecture. Section 4 introduces the different tools developed to homogenize access to all Cloud sites. Section 5 introduces the different set of experiments used to validate the platform. Finally, Section 6, presents the conclusions and future work.

BonFIRE Federated Clouds and Networks

BonFIRE allows users to execute experiments that use compute, network, storage, site-link and router resources. The experiments are controlled by a set of central services, collectively called the Broker, that interact with the testbeds. In this way, the BonFIRE users can test their applications, services, or systems in different Cloud configurations (e.g. deploy across multiple multi-clouds, or experiment with different Cloud managers available through BonFIRE) using a single, homogeneous interface.

At the core of BonFIRE are seven Cloud testbeds that are located at EPCC (UK), INRIA (France), PSNC (Poland), HLRS (Germany), iMinds (Belgium), Wellness Telecom (Spain) and HP (UK) (fig. 1). All testbeds present different features regarding structure, networking, and resources. Users can also create resources on Amazon EC2 using the BonFIRE interface.

Integration of the BonFIRE Cloud facilities and their interconnection with external facilities is key in BonFIRE. Horizontal (i.e. of similar functionality) integration is achieved through the integration of the different facilities as well as Amazon. Additionally, BonFIRE offers vertical integration of Cloud and network facilities. This enables cross-layer testing to propagate service-level requirements down to the connectivity levels. The iMinds Virtual Wall facility allows experimentation using controlled, emulated networks. BonFIRE is also interconnected with two external facilities to provide vertical integration at the network level. These are the G ÉANT AutoBAHN Bandwidth-on-Demand (BoD) system; and the FEDERICA computing network architectures e-infrastructure.

BonFIRE Federation Architecture

BonFIRE provides resource level operations through an implementation of the Open Cloud Computing Interface11 (OCCI) standard. The OCCI was designed for remote management interactions with cloud computing infrastructures. It is an open protocol that is resource-vendor independent, cloud-manager neutral, and can be extended.OCCI acts as the user API for the service lifecycle management of BonFIRE-supported resources. Originally limited to compute, storage, The BonFIRE implementation of OCCI enables defining different kinds of resources with various possible configurations. For instance, a user can create a compute resource and configure it on demand with one of multiple instance types (lite, small, medium, large, or custom), with one or multiple disks (disk image and external storages), with one or more network interfaces, etc. The BonFIRE OCCI supports several management operations and various states of resources. For instance, the possible management operations of a compute resource include: create, stop, resume, shutdown, and delete.

The Resource Manager (RM) (fig. 2) is the lowest layer of the BonFIRE architecture that may be accessed by the end-users, providing the entry point for the users to interact with BonFIRE at resource level. The RM exposes the BonFIRE OCCI interface and maintains the current set of experiments and all the resources associated to them. User operations on non-experiment resources are passed to the Enactor and then on to the appropriate interconnected testbed. User operations on experiment resources are executed at the RM level.

Due to the heterogeneity of BonFIRE Cloud testbeds, the mapping between BonFIRE OCCI and the testbed native interfaces was implemented in different layers. The role of the Enactor is to hide from the RM and from the OCCI the technical details of how to communicate with each specific testbed or external facility. The Enactor receives OCCI requests from the RM and adapts them to a suitable testbed format. When the Enactor gets the information back from the testbed, it transforms the reply again into BonFIRE OCCI.

Canonical BonFIRE images are generated centrally to provide the Debian squeeze Linux distribution in different sizes for the Xen, KVM and ESX hypervisors. The BonFIRE OCCI supports contextualisation at the time of the creation of the VMs and all images also support this; for instance, software can be installed automatically after booting, and also parameters may be passed directly into the virtual machine on instantiation. As a federated infrastructure, every BonFIRE site receives the same contextualisation information in the VM creation request, but they are free to use it according to each site's own particularities.

BonFIRE offers a private address space for each infrastructure provider, e.g. the whole network subnet 172.18.0.0/16. Due to that, all the created VMs are assigned to a dedicated private network offered by a local provider in its Bon-FIRE address range. In order to connect the several VM instances at different locations, a BonFIRE-wide VPN was established, which allows communication between separated virtual machines and internal BonFIRE services. For the VPN network installation, the tinc software was used. The tinc service allows the creation of a decentralized network, so there is no single point of failure if one instance loses its connection. Figure 1 gives a brief overview of the whole BonFIRE infrastructure and shows the different IP ranges of the providers.

User Management

Identity management and authorization is done centrally in BonFIRE. On the one hand, a central LDAP database stores user credentials (username, password and ssh public key) and group membership. On the other, an authorization service stores site access rights as wells as usage limits and peak resource usage for each group. Indeed, groups are a key BonFIRE functionality, that enables efficient collaboration. Group membership is managed by the Principal Investigator of an experiment.

Interactions with BonFIRE services are authenticated against the LDAP database using HTTP basic authentication over ssl. The first service called must authenticate the user, and will carry user information in a dedicated HTTP Header when calling other services. This information is trusted by the service called if and only if the requester can themselves be authenticated using clientside authentication permitted by ssl. In particular, all testbeds in the federation must be configured to authenticate central servers and trust user and group information sent to them using HTTP headers.

The Resource Manager is in charge of doing all authorization by calling the accounting service to check, based on group membership, whether a given user can create or access resources. It will also create temporary credentials and add these, as well as the public keys of all users allowed to access resources, into the context information carried by the OCCI requests. Temporary credentials are used by code running inside the resources that needs to call the BonFIRE API.

Access to resources is secured through SSH. SSH gateways are operated by BonFIRE sites to allow access to the BonFIRE VPN. A classical master-slave configuration is used for LDAP, with slaves on all gateways. This approach avoids a single point of failure, relieves the load on the central database and propagates changes very quickly. VMs are configured with the public keys of users allowed to access them. This allows users to connect to any gateway and, from there, to any VM in the BonFIRE VPN.

Cloud Testbeds

Depending on Cloud Manager technology, BonFIRE currently offers the following five different types of Cloud testbed:

-OpenNebula: The currently operated OpenNebula version 3.6 includes an implementation of an OCCI server based on the OCCI draft 0.8. In order to provide valuable cloud functionality, additional fields of use were added by the BonFIRE developers in order to improve and extend the whole OCCI software stack of OpenNebula. -HP Cells: The OCCI at HP Cells is completely stateless, so there is nothing that can get out of sync with the BonFIRE cental services or with the Cells state. BonFIRE-specific information such as groups, users, etc. are not stored, so the information retrieved on each request from the Enactor is filtered according to the permissions of the requesting user. This OCCI server was implemented specifically to support the BonFIRE project.

-Virtual Wall: The Virtual Wall emulation testbed is not a typical cloud environment, as it lacks the ability to dynamically add computes to an already running experiment. However, its functionality offers a first step to bridge the gap between network and cloud experimentation. The Virtual Wall offers the same OCCI resources as the other testbeds in BonFIRE, but their implementation is very different due to its underlying framework, Emulab.

For instance, the Virtual Wall maps Compute resources to physical nodes, which prevents virtualisation, but allows the experimenter to take full control of the hardware. In response to the need of experimenters to share larger amounts of storage between different Compute resources, the Virtual Wall implements a notion of shared storage based on the Network File System (NFS). -VMWare vCloud: vCloud does not offer by default an OCCI API. Similar to the case of HP Cells, an OCCI server was developed inside the BonFIRE project that interacts with the VMWare vCloud Director API to support VMWare Cloud facilities. The OCCI server is stateless, all the requests coming from the Enactor are translated and mapped to the proprietary API. -Amazon EC2: The Amazon EC2 endpoint at the Enactor makes use of the API that Amazon provides to connect remotely to their Cloud services. The endpoint only allows to manage two kind of resources: storages and computes that are mapped to their Amazon equivalents, volumes or images and instances. In order to deal with the large volume of information returned, BonFIRE caches some OCCI queries in the Enactor, like listings of EC2's numerous storage resources.

Network testbeds

BonFIRE supports experimentation and testing of new scenarios from the services research community, focused on the convergence of services and networks.

In order to support network experimentation, BonFIRE is federated with the iMinds Virtual Wall testbed; and is interconnected with two network facilities: FEDERICA and AutoBAHN. The most distinctive features of the iMinds Virtual Wall are related to its networking capabilities. Whereas the other BonFIRE testbeds only provide a best-effort variant of the Network resource, the Virtual Wall implements three different types of Network resources: Default Networks that provide basic connectivity between two or more Computes; Managed Networks that provide controllable QoS (parameters that can be adjusted are bandwidth, packet loss rate and delay) over the network links; and Active Networks, that, on top of the functionality of Managed Networks, also provide the possibility to control the background traffic (UDP and TCP connections with dynamically adjustable packet size and throughput) on a network link. These networks provided by the Virtual Wall are emulated, using the Emulab software.

FEDERICA is an infrastructure composed of computers, switches and routers connected by Gigabit Ethernet circuits. Through the Slide-based Federation Architecture (SFA) paradigm, FEDERICA offers to BonFIRE experimenters iso-lated network slices by means of virtualizing routers. This interconnection is aimed to help experimenters to investigate application performance through better control of the underlying network. The following changes were carried out in BonFIRE to incorporate these new network resources: the router resource was added to the BonFIRE OCCI and the network resource was enhanced with two new attributes: network link and vlan. Finally, since FEDERICA offers an SFA interface as federation API, it was necessary to implement an SFA endpoint at Enactor level. The FEDERICA SFA interface expects a unique XML request, where all the slice resources and their configuration are specified. This differs from the BonFIRE architecture, where each resource is requested in a single OCCI call. The main function of the BonFIRE SFA endpoint is to transform BonFIRE's OCCI information model to the SFA information model.

The federation between BonFIRE and the AutoBAHN beta-functionality offered by the G ÈANT facility allows the experimenters to request QoS guaranteed network connectivity services between VMs deployed on EPCC and PSNC testbeds. Overcoming the Best Effort limitation of the public Internet, dedicated network services can be established on demand for each experiment, with guarantees in terms of bandwidth, reduced jitter and service reliability. This option is fundamental to offer a controlled connectivity between VMs, so that the experimenters can evaluate the performance of their applications in environments able to emulate a variety of network conditions.

In BonFIRE, a BoD service is represented by a new type of OCCI resource: the site link. Once the resource is created, it can be used to connect two networks created in the BonFIRE sites at the edge of the site link: the traffic between the VMs attached to these networks is routed through the dedicated service. The processing of the OCCI requests for site link resources is managed at the enactor through a dedicated AutoBAHN end-point that is in charge of translating the OCCI specification into the AutoBAHN BoD service format. The Enactor endpoint acts as an AutoBAHN client.

Practical Experimentation Tools

In response to user-demand, BonFIRE exposes various tools and interfaces to its users. The main API is based on OCCI, an interface familiar to the target users, i.e. Cloud application developers. However, interacting with OCCI may be very cumbersome as the size of the deployments grows, and the format is not easily human-readable.

In order to increase usability, BonFIRE offers other client tools, building on the BonFIRE API. These include: an intuitive web Portal to interact graphically with all components; a BonFIRE Experiment Descriptor written in JSON or OVF; a general-purpose RESTful client that uses the Restfully library to allow interaction via Ruby scripting; and a set of Command Line Interface Tools that can be used interactive or programmatically. Extensive, tutorial-based user documentation accompanies the BonFIRE tools.

The feedback of the experimenters to the diversity of available tools was very positive. They found it very easy to start creating experiments with the web Portal and progress later to more complex scenarios in which they created their own programs based on the available tools to create and access their experiments. The BonFIRE Portal is key to this progression, as it includes intuitive builders for OCCI and for the experiment descriptor.

Validation of the platform

Validation of the federated cloud and network platform was designed into several phases. In the early stages of the project, three of the core partners of BonFIRE performed Cloud experimentation in several aspects: from application benchmarking in Cloud Computing to study of malicious paterns in applications [START_REF] Ragusa | A Framework for Modeling and Excuting of Infrastructure Contention Experiments[END_REF][START_REF] Engen | Predicting Application Performance for Multi-Vendor Clouds using Dwarf Benchmarks[END_REF]. In a second phase, we performed two Open Calls, in the first one four independent companies or research groups performed experiments using Bon-FIRE with topics ranging from service composition, virtual clusters, security, or multimedia [START_REF] Gomez | Experimenting Virtual Clusters on Distributed Clound environemtns using BonFIRE[END_REF][START_REF] Wajid | Testing Optimization in Service EcoSystems (TEOS)[END_REF][START_REF] Naqvi | Analysing Impact of Scalability and Heteroneneity on the Performance of Federated Cloud Security[END_REF], in the second one, five new experiments ranging from Cloud elasticity, QoS in federated Clouds, testing of commercial home security and management solutions, multimedia interfaces, or orchestration between users and cloud resources 12 . Finally, BonFIRE has just started its Open Access initiative for new users to come and use for free the platform.

Conclusions and Future Work

BonFIRE enables Research by Experimentation founded on federation of heterogeneous, cloud and network testbeds and facilities. The BonFIRE Cloud federation model is based on a central broker component that interacts between the user requests, the experimenters, and the different infrastructures. This broker offers to the users an OCCI-based interface that exposes all the Cloud and network features as resources.

The BonFIRE interface exposes to the users an homogeneous view of the heterogeneous testbeds it encompasses. Still, the interface exposes the different characteristics that make each federated site unique. Additionally, user management is centralized; all sites are in one unique WAN network that eases communication between VMs located at different Clouds; and the VMs in all federated Clouds, independently of the employed Cloud Manager, can be contextualized in the same way.

The BonFIRE project is still ongoing. In terms of federation, BonFIRE is working towards a cache facility, which will accelerate resource listings from sites. Unlike other BonFIRE functionalities, this is implemented with tight coupling between sites and central services; the sites are enhance to push events about the state of the resources in the BonFIRE Message Queue. BonFIRE is also investigating OpenStack as a potential target Cloud Manager.

BonFIRE is open for free use by organizations and individuals not within the consortium. Over 2013 and 2014 BonFIRE expects to engage an increasing number of experimenters accessing the cloud federated facility.

Fig. 1 .

 1 Fig. 1. BonFIRE Cloud Federation Infrastructure.

Fig. 2 .

 2 Fig. 2. Lowest level BonFIRE architecture.

http://www.bonfire-project.eu

http://www.occi-wg.org

At the time of writting, those experiments were still being executed in the BonFIRE platform, more information about them it is is available in the project webpage: http://www.bonfire-project.eu.

Acknowledgments. BonFIRE is funded by the EU 7th Framework Programme (FP7/2007-2013) under grant agreement number 257386 and 287938.