Demetres D Kouvatsos
email: d.kouvatsos@bradford.ac.uk

Salam A Assi
email: s.a.assi@leeds.ac.uk

On the Analysis of Queues with Heavy Tails: A Non-Extensive Maximum Entropy Formalism and a Generalisation of the Zipf-Mandelbrot Distribution

Keywords: Performance evaluation, extensive maximum entropy (EME) formalism, non-extensive maximum entropy (NME) formalism, generalised exponential

A critique of a non-extensive maximum entropy (NME) formalism is undertaken in conjunction with its application into the analysis of queues with heavy tails that are often observed in performance evaluation studies of heterogeneous networks exhibiting traffic burstiness, self-similarity and/or long range dependence (LRD). The credibility of the NME formalism, as a method of inductive inference, for the study of non-extensive systems with long-range interactions is explored in terms of four consistency axioms of extensive systems with shortrange interactions. Focusing on a a general physical system and, as a special case, a single server queue with finite capacity, it is shown that the NME state probability is characterised by a generalisation of the Zipf-Mandelbrot (Z-M) type distribution depicting heavy tails and asymptotic power law behaviour. Typical numerical experiments are employed to illustrate the adverse combined impact of traffic burstiness and self-similarity on the behaviour of the queue. A reference to open issues relating to the NME formalism and open queueing networks is included.

Introduction

Empirical traffic characterisation studies in networks of diverse technology and the Internet have shown that traffic flows often exhibit burstiness, self-similarity and/or long-range dependence (LRD) causing performance degradation and the formation of queues with heavy length tails and asymptotic power law behaviour (e.g., [START_REF] Sahinoglu | On Multimedia Networks: Self-similar Traffic and Network Performance[END_REF]).

Traffic distributions with such properties are often employed to generate workloads in simulation modelling for performance evaluation studies of high speed networks. These, however, tend to be rather inflexible, computationally expensive and may display unusual characteristics (e.g., [START_REF] Crovella | Long-lasting Transient Conditions in Simulations with Heavy-Tailed Workloads[END_REF][START_REF] Rezaul | A Comparison of Methods for Estimating the Tail Index of Heavytailed Internet Traffic[END_REF]). Some analytic mechanisms for estimating the tail index of Internet traffic with heavy tails were reported by Rezaul and Grout [START_REF] Rezaul | A Comparison of Methods for Estimating the Tail Index of Heavytailed Internet Traffic[END_REF], based on the Pareto distribution. Further analytic studies can be found in [START_REF] Assi | An Investigation into Generalised Entropy Optimisation with Queueing Systems Applications[END_REF][START_REF] Karmeshu | Long Tail Behaviour of Queue Lengths in Broadband Networks: Tsallis Entropy Framework[END_REF][START_REF] Kouvatsos | An Investigation into Generalised Entropy Optimisation with Queueing System Applications[END_REF][START_REF] Kouvatsos | On the Analysis of Queues with Long Range Dependent Traffic: An Extended Maximum Entropy Approach[END_REF]. These works are based on the optimisation of generalisations of the classical Boltzmann-Gibbs-Shannon entropy function (c.f., [START_REF] Chakrabarti | Boltzmann-Gibbs Entropy: Axiomatic Characterisation and Application[END_REF][START_REF] Shannon | A Mathematical Theory of Communication[END_REF]), such as those proposed in the diverse fields of Quantification Theory [START_REF] Havrda | Quantification Methods of Classificatory Processes: Concept of Structural Entropy[END_REF], Statistical Physics [START_REF] Tsallis | Possible Generalisation of Boltzmann-Gibbs Statistics[END_REF] and Information Theory [START_REF] Renyi | On Measures of Entropy and Information[END_REF].

This paper explores a non-extensive maximum entropy (NME) formalism for the study of queueing systems with long range interactions and heavy tails. The methodology is based on the optimization of Havrda-Charvat-Tsallis generalised entropy function (c.f., [START_REF] Havrda | Quantification Methods of Classificatory Processes: Concept of Structural Entropy[END_REF][START_REF] Tsallis | Possible Generalisation of Boltzmann-Gibbs Statistics[END_REF]), subject to suitable mean value constraints. The credibility of the NME formalism, as a method of inductive inference for non-extensive systems with long range interactions, is assessed in terms of four potential consistency axioms for extensive systems proposed in [START_REF] Shore | Axiomatic Derivation of the Principle of ME and the Principle of Minimum Cross-Entropy[END_REF]. Moreover, the NME formalism is applied into the analysis of a general system Q and, as a special case, a single server queue with finite capacity, where formal connections are made between the NME state probabilities and a generalisation of the Zipf-Mandelbrot (Z-M) type distribution [START_REF] Mandelbrot | The Fractal Geometry of Nature[END_REF] depicting heavy queue tails and asymptotic power law behaviour. The concepts of the Boltzmann-Gibbs-Shannon entropy and Havrda-Charvat-Tsallis entropy are reviewed in Section 2. The NME formalism and a generalisation of the Z-M distribution are highlighted in Section 3. The suitability of the NME formalism, as a method of inductive inference, is addressed in Section 4. The NME state probability of a single server queue with finite capacity and heavy tails is reviewed in Section 5. Typical numerical experiments are included in Section 6. Concluding remarks and a reference to open issues relating to the NME analysis of open queueing network models follow in Section 7.

2 On the Interpretation of the Classical and Generalised Entropies

The Classical Entropy Function

For a general system Q with an integer number of possible (microscopic) configurations or states N (N > 0) and 'short-range interactions', the classical entropy function, H * (p N ) [START_REF] Chakrabarti | Boltzmann-Gibbs Entropy: Axiomatic Characterisation and Application[END_REF][START_REF] Shannon | A Mathematical Theory of Communication[END_REF] is defined by

H * (p N ) = -c N n=1 p N (n) log p N (n) (1)
where c(c > 0) is a positive constant and {p N (n), n = 1, 2, ..., N } are the associated event or state probabilities. The entropy function H * (p N ) can be interpreted as a measure of uncertainty or information content that is implied by p N about a physical system Q with short-range interactions such as "the formation of chemical bonds" and "holding matter together" [START_REF]Statistical Mechanics for Non-extensive Systems and Long-Range Interactions[END_REF] in Statistical Physics. In this context, quantities such as 'energy and entropy' are considered as 'extensive' variables in the sense that the overall energy of the system Q with short-range interactions is "proportional to the system size" [START_REF]Statistical Mechanics for Non-extensive Systems and Long-Range Interactions[END_REF]. By analogy, traffic flows in queues with short-range dependence (SRD), such as those represented by Poisson (regular), compound Poisson (bursty) [START_REF] Kouvatsos | Entropy Maximization and Queueing Network Models[END_REF] and batch renewal (BR) (correlated) [START_REF] Kouvatsos | A Cost-Effective Approximation for SRD Traffic in Arbitrary Multi-Buffered Networks[END_REF] processes, influence the creation of single queues and networks, where the state and entropy variables are extensive. In this context, the extensive maximum entropy (EME) formalism (c.f., [START_REF] Jaynes | Information Theory and Statistical Mechanics[END_REF]), as a method of inductive inference (c.f., [START_REF] Shore | Axiomatic Derivation of the Principle of ME and the Principle of Minimum Cross-Entropy[END_REF]) for determining the form of the EME state probability distribution, is based on the maximisation of the extensive entropy function, H * (p N ), subject to normalisation and suitable mean value constraints. The implementation of the EME formalism is achieved by applying the method of Lagrange's undetermined multipliers leading to the characterisation, for example, of modified geometric (Geo) and generalised Geo (GGeo) (e.g., [START_REF] Kouvatsos | Entropy Maximization and Queueing Network Models[END_REF][START_REF] Kouvatsos | A Cost-Effective Approximation for SRD Traffic in Arbitrary Multi-Buffered Networks[END_REF]) types of state probabilities for single server queues.

A Generalised Entropy Function

For a general system Q with an integer number of possible (microscopic) configurations or states N (N > 0) and 'long-range interactions', such as gravity in Statistical Physics, "energy and entropy are no longer extensive quantities" [START_REF]Statistical Mechanics for Non-extensive Systems and Long-Range Interactions[END_REF]. This increases the complexity of the physical system for which the state probability distribution associated say, with energy, can no longer be determined by maximizing the Boltzmann-Gibbs-Shannon entropy function, H * (p N ).

To address this problem, Tsallis [START_REF] Tsallis | Possible Generalisation of Boltzmann-Gibbs Statistics[END_REF] proposed a generalisation of the extensive entropy function, H * (p N ) to a 'non-extensive' entropy measure, H * (p q,N ), namely

H * (p q,N ) = c(1 - N n=1 p q,N (n) q )/(q -1) (2)
where c(c > 0) is a positive constant, q is a real number known as the 'nonextensivity' parameter, which measures the degree of long-range interactions and {p q,N (n), n = 1, 2, ..., N } are the associated state probabilities of system Q. As q → 1, H * (p q,N ) reduces to the Boltzmann-Gibbs-Shannon entropy, H * (p N ).

The non-extensive H * (p q,N ) entropy function proposed in [START_REF] Tsallis | Possible Generalisation of Boltzmann-Gibbs Statistics[END_REF] is identical to the one devised earlier by Havrda-Charvat [START_REF] Havrda | Quantification Methods of Classificatory Processes: Concept of Structural Entropy[END_REF]in the field of Quantification Theory for classification processes. Maximizing H * (p q,N ) in the context of the canonical(statistical) ensemble in Statistical Physics, subject to the normalization and mean (generalised internal) energy constraint, it was shown (c.f., [START_REF] Tsallis | Possible Generalisation of Boltzmann-Gibbs Statistics[END_REF]) that the NME state probability is of the Z-M type distribution [START_REF] Mandelbrot | The Fractal Geometry of Nature[END_REF], having heavy tails and asymptotic power law behaviour.

By analogy, self-similar input traffic processes, such as fractional Brownian (fBm), influence the formation of queues with LRD traffic flows and 'long-range interactions'. In this case, the state and entropy variables are non-extensive leading, respectively, to NME state probabilities of the Z-M and generalised Z-M (G-Z-M) types, subject to appropriate constraints (c.f., [START_REF] Assi | An Investigation into Generalised Entropy Optimisation with Queueing Systems Applications[END_REF][START_REF] Karmeshu | Long Tail Behaviour of Queue Lengths in Broadband Networks: Tsallis Entropy Framework[END_REF][START_REF] Kouvatsos | An Investigation into Generalised Entropy Optimisation with Queueing System Applications[END_REF][START_REF] Kouvatsos | On the Analysis of Queues with Long Range Dependent Traffic: An Extended Maximum Entropy Approach[END_REF][START_REF] Tsallis | Possible Generalisation of Boltzmann-Gibbs Statistics[END_REF]).

NME solutions for infinite and finite capacity queues were first established in [START_REF] Assi | An Investigation into Generalised Entropy Optimisation with Queueing Systems Applications[END_REF][START_REF] Kouvatsos | An Investigation into Generalised Entropy Optimisation with Queueing System Applications[END_REF] by maximising the extensive Havrda-Charvat entropy [START_REF] Havrda | Quantification Methods of Classificatory Processes: Concept of Structural Entropy[END_REF] and other generalised entropy measures (e.g., [START_REF] Renyi | On Measures of Entropy and Information[END_REF]), subject to normalisation and generalised exponential (GE) type queueing theoretic mean value constraints. The original NME solution of the Z-M type derived by Tsallis [START_REF] Tsallis | Possible Generalisation of Boltzmann-Gibbs Statistics[END_REF] in Statistical Physics was adopted by Karmeshu and Sharma [START_REF] Karmeshu | Long Tail Behaviour of Queue Lengths in Broadband Networks: Tsallis Entropy Framework[END_REF] for the NME study of a single server queue with infinite capacity, subject to the normalisation and mean queue length (MQL) constraint. The latter was based on a formula devised by Norros [START_REF] Norros | A Storage Model with Self-similar Input[END_REF] for the estimation of the buffer capacity of a simple storage system with a fBm input process. This NME solution, however, is invalid for single server queues at equilibrium as it violates the Little's law at the service centre of the queue. More recently, NME solutions of a G-Z-M type were determined in [START_REF] Kouvatsos | On the Analysis of Queues with Long Range Dependent Traffic: An Extended Maximum Entropy Approach[END_REF] for single server queues with infinite and finite capacities, based on the reinterpretation of a proposed heuristic generalisation of the Norros formula [START_REF] Norros | A Storage Model with Self-similar Input[END_REF].

A Non-Extensive Maximum Entropy Formalism and a Generalisation of the Z-M Distribution

Consider a general non-extensive system Q with long-range interactions that has a set S of possible discrete states {S 0 , S 1 , S 2 , ...}, which may be finite or countable infinite and state {S n , n = 0, 1, ...} may be specified arbitrarily. Suppose the available information about Q places a number of constraints on the state probabilities {p q (S n ), S n ∈ S}, belonging in closed convex set Ω, where q is the non-extensivity parameter. Without loss of generality, it is assumed that the constraints take the form of mean values of several suitable functions {f 1,q (S n ), f 2,q (S n ), ..., f m,q (S n )}, where m is less than the number of feasible states.

A NME framework can be established to determine the form of p q (S n ) that maximises the Havrda-Charvat-Tsallis entropy, H * (p q ), namely

H * (p q ) = c(1 - Sn∈S p q (S n ) q )/(q -1) (3)
subject to normalisation and the mean value constraints, namely

Sn∈S p q (S n ) = 1 (4) Sn∈S f k,q (S n )p q (S n ) = F k,q (5)
where c(c > 0) is a positive constant and {F k,q , k = 1, 2, ..., m} are the prescribed mean values defined on the set of functions {f k,q (S n ), k = 1, 2, ..., m}.

Note that H * (p q ) can be described as a low-order truncation of Renyi's information theoretic entropy [START_REF] Renyi | On Measures of Entropy and Information[END_REF]. By employing the Lagrange's method of undetermined multipliers, the maximisation of H(p q ), subject to mean value constraints ( 4)-( 5), determines a least biased NME solution for the state probabilities, namely

p q (S n ) = 1 Z q 1 + (1 -q) m k=1 β k f k,q (S n ) 1 q-1 (6)
where {β k }, k = 1, 2, ..., m} are the Lagrangian multipliers corresponding to the constraints (4), Z q = exp{β 0 } is the normalizing constant and β 0 is the Lagrangian multiplier determined by the normalisation constraint.

The NME solution (6) can be interpreted as a G-Z-M type distribution depicting heavy queue tails and asymptotic power law behaviour. [START_REF] Chakrabarti | Boltzmann-Gibbs Entropy: Axiomatic Characterisation and Application[END_REF] The NME Formalism as a Method of Inductive Inference for Non-extensive Systems

The principles of EME [START_REF] Jaynes | Information Theory and Statistical Mechanics[END_REF] and minimum relative entropy (MRE), a generalisation, were shown in [START_REF] Shore | Axiomatic Derivation of the Principle of ME and the Principle of Minimum Cross-Entropy[END_REF] to be uniquely correct methods of inductive inference for extensive systems, subject to a prior probability estimate and new information given in the form of suitable mean values. The approach adopted in [START_REF] Shore | Axiomatic Derivation of the Principle of ME and the Principle of Minimum Cross-Entropy[END_REF] was based on the fundamental assumption that the use of the EME and MRE principles, as methods of inductive inference for extensive systems, should lead to consistent results when there are different ways to solve a problem by taking into account the same information. This fundamental requirement was formalised in terms of four consistency axioms, namely uniqueness, invariance, system independence and subset independence.

It was shown that optimizing any function other than entropy or relative entropy will lead to inconsistencies unless the function in question and the entropy or relative entropy share, respectively, identical maxima or minima. In other words, given new constraint information, there is a unique distribution satisfying these constraints that can be chosen by a procedure based on EME and MRE formalisms complying with the consistency axioms.

The relevance of the four consistency axioms for extensive systems (c.f., [START_REF] Shore | Axiomatic Derivation of the Principle of ME and the Principle of Minimum Cross-Entropy[END_REF]) on the credibility of the NME formalism, as a method of inductive inference, is investigated below.

Uniqueness

Adopting the notation of Section 3, let f q,N , h q,N ∈ Ω be two distinct probability distributions defined on the set of states S of the non-extensive system Q having the same non-extensive entropy functions, namely H * (f q,N ) = H * (h q,N ).

Using the NME solution ( 6), it can be shown that

H * (f q,N ) = H * (h q,N ) = αH * (f q,N ) + (1 -α)H * (h q,N ) ≤ H * (αf q,N + (1 -α)h q,N ) (7)
Since the set Ω is convex, there is a distribution (i.e., weighted average) given by αf q,N + (1 -α)h q,N , which belongs to Ω and has an extended maximum entropy greater than H * (f q,N ) = H * (h q,N ). Therefore, there cannot be two distinct probability distributions f q,N , h q,N ∈ Ω having the same maximum entropy in Ω. Thus, the Havrda-Charvat-Tsallis NME formalism satisfies the axiom of uniqueness (c.f., [START_REF] Shore | Axiomatic Derivation of the Principle of ME and the Principle of Minimum Cross-Entropy[END_REF]).

Invariance

Following the analytic methodology in [START_REF] Shore | Axiomatic Derivation of the Principle of ME and the Principle of Minimum Cross-Entropy[END_REF], let Γ be a coordinate transformation from state S n ∈ S, n = 1, 2, ..., N to state R n ∈ R, n = 1, 2, ..., N ), where R be a transformed set of N possible discrete states {R n , n = 1, 2, ..., N } with

(Γ p q,N )(R n ) = J -1 p q,N (S n ), where J is the Jacobian J = ∂(R n )/∂(S n ).
Moreover, let Γ Ω be the closed convex set of all probability distributions Γ p q,N defined on R such that Γ p q,N (R n ) > 0 for all R n ∈ R, n = 1, 2, ..., N and

N n=1 Γ p q,N (R n ) = 1.
It can be clearly seen that, transforming of variables from S n ∈ S into R n ∈ R, the Havrda-Charvat-Tsallis extended entropy function (c.f., [START_REF] Crovella | Long-lasting Transient Conditions in Simulations with Heavy-Tailed Workloads[END_REF]) is transformation invariant, namely

H * (p q,N ) = H * (Γ p q,N ) (8)
Thus, since the minimum in Γ Ω corresponds to the minimum in Ω, the NME formalism satisfies the axiom of invariance.

System Independence

Consider two general non-extensive systems Q and R each of which having a finite set of N, N > 0 possible discrete states {x n , n = 1, 2, ..., N } and {y n , n = 1, 2, ..., N }, respectively. Moreover, let X and Y be the random variables describing the state of the systems Q and R, respectively, with corresponding state probabilities f q,N (x n ) = P r{X = x n } and g q,N (y n ) = P r{Y = y n }, respectively.

Assuming that Q and R are independent systems, then using the joint probability, h q,N (x k , y n ) = P r(x k , y n ), k, n = 1, 2, ..., N and the definition of ( 6), it clearly follows that

H * [h q,N ] = H * (f q,N ) + H * (g q,N ) (9)
The inequality [START_REF] Jaynes | Information Theory and Statistical Mechanics[END_REF] implies that, in information theoretic terms, the joint NME state probability distribution of two independent non-extensive systems Q and R defies, due to the presence of long-range interactions, the axiom of system independence (c.f., [START_REF] Shore | Axiomatic Derivation of the Principle of ME and the Principle of Minimum Cross-Entropy[END_REF]). Thus, this attribute of the NME formalism, as a method of inductive inference, is clearly most suitable for the quantitative studies of non-extensive dynamic systems with heavy queue tails and asymptotic power law behaviour. Note that in the case of q → 1 limit, equation ( 9) becomes

H * [h q,N ] = H * (f q,N ) + H * (g(Y q,N ) (10)
The equality ( verifies that the joint EME state probability distribution, as expected, satisfies the axiom of system independence (c.f., [START_REF] Shore | Axiomatic Derivation of the Principle of ME and the Principle of Minimum Cross-Entropy[END_REF]. This is an appropriate property of the EME formalism as a method of inductive inference for the study of extensive systems with short-range interactions.

Subset Independence

Consider a general non-extensive system Q that has wlog a finite number, L(L > 0), of disjoint sets of discrete states {S * i , i = 1, 2, ..., L}, whose union is S. Let {x ij , i = 1, 2, ..., L; j = 1, 2, ..., L i } be a conditional state belonging to the set {S * i , i = 1, 2, ..., L i }, where L i is the finite number of possible conditional states in S * i . Moreover, let ξ i be the probability that a state of the system Q is in the set {S * i , i = 1, 2, ..., L i } and let probability f q,i (x ij ) ∈ Ω i , where Ω i , is the closed convex set of all probability distributions on S * i . Moreover, let x be an aggregate state of system Q and probability f q (x) ∈ Ω, where Ω is the closed convex set of all probability distributions on S.

Using the definition of the extended entropy function (c.f.,( 6)), it can be shown that

H * (f q ) = i ξ i H * i (f q,i ) (11)
where H * i (f q,i ) is the extended conditional entropy function defined on the set of states S i , i = 1, 2, ..., L. Therefore, maximising the generalised aggregate entropy function, H * (f q ), subject to an aggregate set of available constraints, it is equivalent to maximising each generalised conditional entropy function, H * i (f q,i ), individually, subject to a conditional set of available constraints. Thus, the Havrda-Charvat-Tsallis NME formalism satisfies the axiom of subset independence [START_REF] Shore | Axiomatic Derivation of the Principle of ME and the Principle of Minimum Cross-Entropy[END_REF].

A Finite Capacity Queue with Heavy Length Tails

In this section, the NME solution for the state probability distribution of a single server finite capacity queue is devised, as a special case of the NME solution [START_REF] Crovella | Long-lasting Transient Conditions in Simulations with Heavy-Tailed Workloads[END_REF], in terms of the normalisation, server utilisation, mean queue length and full buffer state probability constraints. As it became evident from the earlier analysis of queues with short-range interactions, based on the classical ME formalism (c.f., [START_REF] Kouvatsos | Entropy Maximization and Queueing Network Models[END_REF]), the selection of these constraints is motivated by the fact that they may, generally, capture the main system characteristics and they can be expressed in terms of known input system parameters, such as the mean arrival rate λ, the squared coefficient of variation (SCV) of the interarrival times, (Ca 2 ), the mean service rate µ and the SCV of the service times, (Cs 2 ). By analogy, this behaviour has also been observed in the analysis of queues with long range interactions (c.f., [START_REF] Assi | An Investigation into Generalised Entropy Optimisation with Queueing Systems Applications[END_REF][START_REF] Karmeshu | Long Tail Behaviour of Queue Lengths in Broadband Networks: Tsallis Entropy Framework[END_REF][START_REF] Kouvatsos | An Investigation into Generalised Entropy Optimisation with Queueing System Applications[END_REF][START_REF] Kouvatsos | On the Analysis of Queues with Long Range Dependent Traffic: An Extended Maximum Entropy Approach[END_REF]), where the constraints of the associated NME solutions include, in addition, the non-extensivity parameter, q (c.f., [START_REF] Havrda | Quantification Methods of Classificatory Processes: Concept of Structural Entropy[END_REF][START_REF] Tsallis | Possible Generalisation of Boltzmann-Gibbs Statistics[END_REF]), or, equivalently, the Hurst self-similarity parameter, H (c.f., [START_REF] Beran | Statistics for Long-Memory Processes[END_REF]) such that q = 1.5 -H, 1/2 < q, H < 1 (c.f., [START_REF] Karmeshu | Long Tail Behaviour of Queue Lengths in Broadband Networks: Tsallis Entropy Framework[END_REF][START_REF] Kouvatsos | On the Analysis of Queues with Long Range Dependent Traffic: An Extended Maximum Entropy Approach[END_REF][START_REF] Rezaul | A Comparison of Methods for Estimating the Tail Index of Heavytailed Internet Traffic[END_REF]).

Note that a heuristic generalization of Norros formula [START_REF] Norros | A Storage Model with Self-similar Input[END_REF], for the estimation of the buffer capacity of a storage system (under a fBm input process), was conjectured in [START_REF] Kouvatsos | On the Analysis of Queues with Long Range Dependent Traffic: An Extended Maximum Entropy Approach[END_REF]. This formula was reinterpreted as a MQL constraint, L H , in the NME analysis of a stable single server gS-S/GE/1 queue with infinite capacity, an abstact generalised self-similar (gS-S) arrival process with parameters H, λ and Ca 2 and a GE-type service time distribution completely defined by µ and Cs 2 . This MQL heuristic expression is given by

L H = ρ 1 2(1-H) 2 1 2(1-H)   1 -ρ + Ca 2 + ρCs 2 ] 1 2(1-H) (1 -ρ) H 1-H   ( 12
)
where H takes values in the interval 1 2 < H < 1 [START_REF] Kouvatsos | On the Analysis of Queues with Long Range Dependent Traffic: An Extended Maximum Entropy Approach[END_REF]. Note that the heuristic formula [START_REF] Kouvatsos | Entropy Maximization and Queueing Network Models[END_REF] takes explicitly into account the adverse combined impact of traffic burstiness (via the SCVs Ca 2 and Cs 2 ) and self-similarity (via pararameter H) on queueing system performance. The expresion [START_REF] Kouvatsos | Entropy Maximization and Queueing Network Models[END_REF] reduces correctly to the Norros formula [START_REF] Norros | A Storage Model with Self-similar Input[END_REF] when Ca 2 = Cs 2 = 1. Moreover, for H = 1 2 (i.e., q → 1) equation ( 12) yields the mean queue length formula of a stable GE/GE/1 queue [START_REF] Kouvatsos | Entropy Maximization and Queueing Network Models[END_REF].

An NME State Probability as a G-Z-M Type Distribution

Consider a single server gS-S/GE/1/N queue with i) finite capacity, N ii) a gS-S arrival process with mean arrival rate λ, interarrival time SCV, Ca 2 and Hurst self-similarity parameter, H and iii) a GE-type service time distribution with mean service rate, µ and service time SCV, Cs 2 . Moreover, at any given time, let p q,N (n), n = 0, 1, .., N , be the state probability of having n, say, messages in the queue.

Suppose that the prior information about the state probability can be expressed in terms of the following mean value constraints (c.f., [START_REF] Kouvatsos | An Investigation into Generalised Entropy Optimisation with Queueing System Applications[END_REF][START_REF] Kouvatsos | On the Analysis of Queues with Long Range Dependent Traffic: An Extended Maximum Entropy Approach[END_REF]): Normalisation, server utilisation U q, N = 1 -p q,N (0), MQL, L q,N = N n=0 np q,N (n) and full buffer state probability, φ q,N = p q,N (N ), where φ q,N satisfies the flow balance condition, namely

λ(1 -π q,N ) = µU q,N (13)
where π q,N is the blocking probability that an arrival message find a full capacity queue.

The form of the NME queue length distribution, p q,N (n), n = 0, 1, ..., N of the gS-S/GE/1/N queue can be characterised by maximising the Havrda-Charvat-Tsallis non-extensive entropy,

H * (p q,N ) = c(1 - N n=0 p q,N (n) q /(q -1) (14)
subject to the normalisation and the aforementioned constraints: server utilisation, MQL and full buffer state probability.

The NME state probability of the gS-S/GE/1/N can be clearly reduced from the generic G-Z-M solution (6 and is given by

p q,N (n) = 1 Z q,N [1 + α N (1 -q)n + β N (1 -q)h q,N (n) + γ N (1 -q)s q,N (n)] 1 q-1 (15)
where β N , α N and γ N are the Lagrangian multipliers corresponding to the server utilisation, MQL and full buffer state probability constraints. Moreover, h q,N (n) and s q,N (n) are auxiliary functions clearly defined by

h q,N (n) = 0, n = 0 1, n = 0 . ( 16
)
s q,N (n) = 0, n < N 1, n = N (17)
and Z q,N is the normalizing constant expressed by

Z q,N = N n=0 [1 + α N (1 -q)n + β N (1 -q)h q,N (n) + γ N (1 -q)s q,N (n)] 1 q-1 = ζ 1 1-q , 1+β N (1-q)h q,N (n)+γ N (1-q)s q,N (n) α N (1-q)
(18) where 1 1-q > 1, q > 0 and ζ denotes the Hurwitz-Zeta function (c.f., [START_REF] Bateman | Higher Transcendental Functions[END_REF]). Note that a direct derivation of the NME solution [START_REF] Kouvatsos | On the Analysis of Queues with Long Range Dependent Traffic: An Extended Maximum Entropy Approach[END_REF], can be seen in [START_REF] Kouvatsos | On the Analysis of Queues with Long Range Dependent Traffic: An Extended Maximum Entropy Approach[END_REF]. As N → ∞, the NME solution, p q,N (n) (15) becomes identical to that of the corresponding infinite capacity queue with heavy length tails [START_REF] Kouvatsos | An Investigation into Generalised Entropy Optimisation with Queueing System Applications[END_REF][START_REF] Kouvatsos | On the Analysis of Queues with Long Range Dependent Traffic: An Extended Maximum Entropy Approach[END_REF]. Moreover, at the limit q → 1, p q,N (n) reduces to the ME solution for the state probability p q,N (n) of the GE/GE/1/N queue [START_REF] Kouvatsos | Entropy Maximization and Queueing Network Models[END_REF].

For q < 1, ρ < 1 and for large number of messages n, p q,N (n) follows asymptotically, as expected, a power law, which turns out, as expected, to be identical to the one obtained for a stable gS-S/GE/1 (c.f., [START_REF] Kouvatsos | On the Analysis of Queues with Long Range Dependent Traffic: An Extended Maximum Entropy Approach[END_REF]) and also to the one associated with Tsallis original solution (c.f., [START_REF] Karmeshu | Long Tail Behaviour of Queue Lengths in Broadband Networks: Tsallis Entropy Framework[END_REF]), namely

p N (n) ∼ n -1 1-q , 1 2 < q < 1 (19)
The Newton-Raphson numerical method can be applied, as in [START_REF] Karmeshu | Long Tail Behaviour of Queue Lengths in Broadband Networks: Tsallis Entropy Framework[END_REF] and [START_REF] Kouvatsos | On the Analysis of Queues with Long Range Dependent Traffic: An Extended Maximum Entropy Approach[END_REF], to implement the NME solutions of single server queues with infinite and finite capacities, respectively. For illustration purposes, the computational implementation of the NME solution is simplified by assuming that the Lagrange multipliers α N and β N are asymptotically invariant to the buffer size, N i.e., α N = α and β N = β, where α and β are the Lagrange multipliers of the corresponding infinite capacity queue. Moreover, the blocking probability, π, can be computed by using the flow balance condition [START_REF] Kouvatsos | A Cost-Effective Approximation for SRD Traffic in Arbitrary Multi-Buffered Networks[END_REF].

Numerical Results

This section presents four typical numerical experiments (c.f., Figs. 123) illustrating the credibility of the NME solutions and also assess the combined impact of bursty and self-similar traffic flows on the performance of the queue.

A plot of the queue length distribution p q,N (n) of a finite capacity gS-S/GE/1/N queue versus state n for different values of non-extensivity parameter q = 1.5-H is shown in Fig. 1. It can be seen that decreasing values of q impose gradually, as expected, heavier long tails on the state probabilities, p q,N (n) .

The queue length distribution p q,N (n) versus n for q = 0.6 and different values of Ca 2 is shown in Fig. 2. It can be observed that, for small states n, higher input traffic burstiness (i.e., variability) has no much influence, as expected, on the tails of the state probabilities. However, as the values of state n increase beyond a small threshold value, traffic burstiness imposes progressively, in the presence of high self-similarity, heavier tail behaviour on the state probabilities.

The relationship between the utilisation, U q,N and ρ for Ca 2 = 3, 20 and different values of q is plotted in Figs. 3(a) and 3(b). It can be observed in Fig. 3(a) that for smaller values of ρ under moderate traffic burstiness (variability) at Ca 2 = 3, the utilisation U q,N for smaller values of non-extensivity parameter 1 2 < q < 1 is progressively decreasing. This indicates that increasing selfsimilarity in traffic flows does not have an adverse effect on queue performance when the server is underutilised. Note that, as it was observed earlier in [START_REF] Choudhury | Long-tail Buffer-content Distributions in Broadband Networks[END_REF], the acute transition from low to high utilisation for lower values of q, as the parameter ρ attains increasing values, is a typical attribute of self-similarity and/or LRD network traffic with moderate variability (c.f., [START_REF] Karmeshu | Long Tail Behaviour of Queue Lengths in Broadband Networks: Tsallis Entropy Framework[END_REF][START_REF] Kouvatsos | On the Analysis of Queues with Long Range Dependent Traffic: An Extended Maximum Entropy Approach[END_REF]). However, this utilisation 'anomaly' of the plot U q,N versus ρ in Fig. 3(a) is no longer valid as the traffic displays 'burstier' characteristics with Ca 2 being equal to the increased value from 3 to 20. As it can be seen in Fig. 3(b), the relationship between U q,N and ρ reaches a more distinguished pattern as the adverse impact of higher traffic burstiness on utilisation U q,N , even for small values of ρ, is quite evident. In particular, the curves of Fig. 3(b) have a much lower intersection point towards ρ → 0 whilst those in Fig. 3(a) are quite independent from each other up to a higher threshold value of ρ. The extremal type of behaviour displayed by the curves of Fig. 3(b) illustrates the adverse impact of traffic flows with combined high burstiness and self-similarity on the performance of the queue.

The numerical experiments of Figures (Figures 123)) demonstrate the credibility and robustness of the power-type NME queue length distributions and assess effectively the adverse combined impact of traffic variability and self-similarity on queue performance.

Conclusions

An exploration of the NME formalism for the study of non-extensive systems with long range interactions was undertaken, based on the maximization of the Havrda-Charvat-Tsallis entropy function, subject to new information in the form of suitable mean value constraints. The credibility of NME formalism, as a method of inductive inference, was formally assessed in terms of four consistency axioms for the EME and MRE formalisms for extensive systems (c.f., [START_REF] Shore | Axiomatic Derivation of the Principle of ME and the Principle of Minimum Cross-Entropy[END_REF]), namely uniqueness, invariance, system independence and subset independence. It was established that the NME solution satisfies three of these consistency axioms, namely uniqueness, invariance and subset independence, but it did not comply with the axiom of system independence, due to the long-range interactions in non-extensive systems. Thus, the NME formalism was shown to be a most suitable method of inductive inference for the study of dynamic systems with heavy queue tails and asymptotic power law behaviour. Furthermore, it was determined that the NME state probability distribution of a general physical system, Q is characterised by a G-Z-M type distribution depicting bursty and heavy tails with asymptotic power law behaviour. Typical numerical experiments focusing on the special case of a gS-S/GE/1/N queue with finite capacity were included to highlight the credibility and robustness of the NME solution and related performance metrics and also verify the adverse combined impact of traffic burstiness and self-similarity on the performance of the queue.

The NME formalism for single server gS-S/GE/1/N queues with or without finite capacity provides simple but efficient analytic building blocks towards further advances into the theoretical characterisation of underlying bursty and S-S arrival processes and service time distributions associated with exact/approximate NME state probabilities, as appropriate. Although exact NME product form solutions for arbitrary open queueing network models (QNMs) are not possible (c.f., [START_REF] Karmeshu | q-ExponentiaL Product-Form Solution of Packet Distribution in Queueing Networks: maximisation of Tsallis Entropy[END_REF]), nevertheless analytic NME product-form approximations and queue-by-queue decomposition algorithms may be established. The latter can be linked, to a tolerable accuracy, with approximate marginal state probabilities and related performance metrics for QNMs of converging multiservice heterogeneous networks taking into account merging, splitting and departing flow steams of bursty and S-S traffic processes.

Fig. 1 .

 1 Fig. 1. The relation between pq,N (n) and n for a gS-S/GE/1/N queue with Ca 2 = 4, Cs 2 = 9, N = 20, λ = 0.8, µ = 1.0 and {q = 0.6, 0.7, 0.8, 0.9}.

Fig. 2 .

 2 Fig.2. The relation between pq,N (n) and n for a gS-S/GE/1/N queue with Cs 2 = 9, N = 5, q = 0.6, λ = 0.8, µ = 1.0 and {Ca 2 = 1, 3, 8, 16}.

Fig. 3 .

 3 Fig. 3. The relation between U = 1 -pq,N (0) and ρ for a gS-S/GE/1/N queue with Cs 2 = 4, N = 20, {q = 0.6, 0.7, 0.8, 0.9} and (a) Ca 2 = 3 or (b) Ca 2 = 20.


Connie U Smith

Catalina M Lladó
email: cllado@uib.es

Model Interoperability for Performance Engineering: Survey of Milestones and Evolution

Next generation Software Performance Engineering tools will exploit a model interoperability paradigm that uses the performance modeling tool best suited to the software/hardware architecture issues and the life cycle stage of the assessment. The paradigm allows the use of existing tools to the extent possible without requiring extensive changes to them. The performance model solution should be transparent to the user. Significant milestones have been accomplished in the evolution of this paradigm. This paper covers key results in the areas of Model Interchange Formats, model transformations, tools, specification of experiments and results, and extensions for real-time and component-based systems. It then offers conclusions on next steps and the future of the model interoperability paradigm.

Introduction

Software performance engineering (SPE) is a systematic, quantitative approach to constructing software systems that meet performance requirements [START_REF] Smith | Performance Solutions: A Practical Guide to Creating Responsive, Scalable Software[END_REF]. SPE uses performance models to provide data for the quantitative assessment of the performance characteristics of software systems as they are developed. SPE has evolved over more than 30 years and has been demonstrated to be effective during the development of many large systems.

Although sound performance analysis theories and techniques exist, they are not widely used because they are difficult to understand and require heavy modeling effort throughout the development process [START_REF] Woodside | The future of software performance engineering[END_REF]. Consequently, software engineers usually resort to testing to determine whether the performance requirements have been satisfied. To ensure that these theories and techniques are used, they must be made more accessible-integrated into the software development process and supported with tools.

First generation performance engineering tools were developed for users with modeling expertise. Examples include [START_REF] Beilner | Towards a performance modeling environment: News on HIT[END_REF][START_REF] Grummitt | A performance engineer's view of systems development and trials[END_REF]40]. To use them for SPE requires performance specialists to work with developers to obtain software design and performance data for evolving software. The principal problem is the gap between software developers who need the techniques and the performance specialists who have the skill to conduct studies with first generation modeling tools. This limits the ability of developers to explore the design alternatives.

The ideal next generation SPE tool will provide support for many SPE tasks in addition to the obvious requirements for performance modeling. The ideal SPE tool will use the performance modeling tool best suited to the software/hardware architecture issues and life cycle stage of the assessment. It also requires a costeffective solution that works with existing tools to the extent possible without requiring extensive changes to them. The performance model solution process should be transparent to the user of the SPE tool.

Model interoperability seeks cooperation among existing tools that perform different tasks. Thus, model interoperability makes it possible to create a software specification in a development tool, then automatically export the model description and specifications for conducting performance assessments, then obtain results for considering architectural and design options.

This paper examines the milestones in the evolution from first generation performance modeling tools for SPE to the model interoperability framework. Note that our focus was initially on tools for SPE, however the model interoperability framework supports general performance engineering tasks for a variety of modeling tools and application domains. The following sections address the significant milestones. We then offer conclusions on next steps and the future of the model interoperability paradigm.

Version 1 Model Interchange Formats

A model interchange format (MIF) is a common representation for performance model data that can be used to move models among modeling tools. A user of several tools that support the format can create a model in one tool, and later move the model to other tools for further work without the need to laboriously translate from one tool's model representation to the other. For example, an analyst might create a model of a server platform to conduct several studies, then move the model to a tool better suited to network analysis.

MIFs require minor extensions to tool functions (import and export) or creation of an external translator to convert file formats to/from interchange formats. They enable easy comparison of results from multiple tools, and the use of tools best suited to the task. Without a shared interchange format, two tools would need to develop a custom import and export mechanism. Additional tools would require a custom interface to every other tool resulting in a N(N-1) requirement for customized interfaces. With a shared interchange format, the requirement for customized interfaces is reduced to 2N.

Related, earlier work in this area is limited. Beilner advocated hierarchical and modular descriptions of models and showed how multiple solution techniques can be used with these model descriptions. The HIT environment demonstrated the feasibility of this approach [START_REF] Beilner | Towards a performance modeling environment: News on HIT[END_REF]. Likewise, the Esprit Integrated Modelling Support Environment, IMSE, integrated several individual modeling tools and showed the potential of interchanging tools for performance studies [START_REF] Hillston | A tool to enhance model exploitation[END_REF]. We seek a mechanism for a loose connection among a variety of modeling tools.

MIFs originated in the VLSI community with the Electronic Design Interchange Format (EDIF) for exchanging VLSI design information among design tools. Subsequently the software community adopted this paradigm for the Case Data Interchange Format (CDIF) standard [START_REF]CDIF -CASE Data Interchange Format Overview[END_REF]. In the CDIF standard, the information to be transferred between two tools is known as a model. The contents of a model are defined using a meta-model. A meta-model defines the information structure of a small area of CASE (such as data modeling) known as a Subject Area. Each meta-model is, in turn, defined using a meta-meta-model. The original meta-meta-model is based on the Entity-Relationship-Attribute (ERA) approach.

MIFs for performance modeling were first introduced at the 1995 Tools Conference in Heidelberg. The Software Performance Model Interchange Format (S-PMIF) defined the SPE information requirements for CASE tools with a meta-model and a transfer format for interchange among software performance modeling tools [START_REF] Smith | Panel presentation: A performance model interchange format[END_REF]. The Performance Model Interchange Format (PMIF) for the interchange of queueing network models (QNM) was proposed in a panel session and subsequently published in [START_REF] Smith | A performance model interchange format[END_REF]. The session had a lively debate about the concept of model interoperability. It was generally agreed that the concept was good, but the debate centered on the content of the proposals and whether they were ready for technology transfer.

The initial work by Smith and Williams was funded by the National Science Foundation. Without additional funding and without tools to facilitate implementation, the work remained dormant for several years.

Version 2 PMIF

With the advent of XML (Extensible Markup Language) tools, MIF implementation became feasible. In 2004, Smith and Lladó developed Version 2 of PMIF [START_REF] Smith | Performance model interchange format (PMIF 2.0): XML definition and implementation[END_REF]. Version 2 converted the meta-model to UML and implemented the XML transfer formats. Modifications were required to exchange QNM among unlike tools. The primary difference was the addition of routing probabilities because the number of visits alone could be insufficient information for some QNM topologies. Probabilities are specified with Transit elements for routing among nodes and for workload entry. Number of visits was retained for tools that must specify the service time per visit rather than total service demand. Other minor changes improved convenience and eliminated redundancy.

We implemented a prototype export mechanism from the SPE•ED software performance modeling tool [40] into pmif.xml, and a prototype import mechanism from pmif.xml into the Qnap system performance modeling tool [START_REF] Potier | QNAP2: A portable environment for queueing systems modelling[END_REF]. Subsequent work implemented the reverse exchange exporting from Qnap and importing to SPE•ED further demonstrating the soundness of PMIF 2 [START_REF] Smith | Performance Model Interchange Format (PMIF 2): A comprehensive approach to queueing network model interoperability[END_REF].

The CDIF strategy is export everything you know and provide defaults for other required information; import the parts you need and make assumptions if you require data not in the meta-model. Everything you know is not necessarily everything you use. For example, SPE•ED uses visits to specify routing, but it knows about probabilities, and it is relatively easy to calculate them.

We used the prototypes to study several examples. Our use of unlike tools helped us find limitations in the meta-model and find a general way to resolve them. Example solutions confirmed that the pmif.xml transfer was successful. The examples provided a set of models that are well documented, with reproducible results, that may be used by others who wish to explore the pmif.xml approach to model interoperability.

Flurry of Related Work

After establishing the viability of performance model interchange formats, there was a flurry of activity among researchers building on this work. It is described in the following sections.

Design Models to Performance Models

Cortellessa, et.al. collaborated on an unified approach using S-PMIF [START_REF] Smith | From UML models to software performance results: An SPE process based on XML interchange formats[END_REF], derived from the original SPE meta-model. They demonstrated the viability of a complete path from software design to performance validation, based on existing tools that were not designed to interact with each other.

This overall process is beneficial because no single monolithic tool is good for everything. Early in development one needs to quickly and easily create a simple model to determine whether a particular architecture will meet performance requirements. Precise data is not available at that time, so simple models are appropriate for identifying problem areas. Later in development, when some performance measurements are available, more detailed models such as Queueing Network Models (QNM), Stochastic Petri Nets (SPN), or Process Algebra (PA) models can be used to study intricacies of the performance of the system. At that time, tools that provide features not in the simpler models are desirable. These industrial strength models are seldom appropriate earlier in development because constructing and evaluating them requires additional time and expertise that is seldom justified when performance details are sketchy at best.

Thus S-PMIF is an intermediate representation between design models and system performance models. It is useful for studying software architecture and design options. Other researchers go directly from software models to system performance models [START_REF] Gu | XSLT transformation from UML models to LQN performance models[END_REF][START_REF]A model transformation framework for the automated building of performance models from UML models[END_REF][START_REF] Marzolla | UML-PSI: the UML performance simulator (tool paper)[END_REF][START_REF] Balsamo | Performance evaluation of UML software architectures with multiclass queueing network models[END_REF][START_REF] Savino | Extending UML to manage performance models for software architectures: A queuing network approach[END_REF]. These approaches use XML to transfer design specifications into a particular solver.

Lopez-Grao et al. propose a method to translate several UML diagram types to analyzable GSPN models where performance requirements are annotated according to the UML SPT (Schedulability, Performance and Time) profile [START_REF] López-Grao | From UML activity diagrams to stochastic Petri nets: Application to software performance engineering[END_REF]. As a slightly more general approach, Gu and Petriu present in [START_REF] Gu | From UML to LQN by XML algebra-based model transformations[END_REF] a process to transform UML models to Performance Models that can be later specialized for different performance modeling formalisms.

MIF Extensions

Lately, efforts have developed intermediate models between various design models (different UML diagrams, different UML versions, non UML approaches, etc.) and various system performance modeling tools. Woodside et al. [START_REF] Woodside | Performance by unified model analysis (PUMA)[END_REF] propose the Core Scenario Model (CSM), claiming that it captures the essence of performance specification and estimation as expressed in the UML SPT profile. Grassi et al. [START_REF] Grassi | From design to analysis models: A kernel language for performance and reliability analysis of component-based systems[END_REF] focus on the construction of software systems according to the component-based development (CBD) approach. They propose KLAPER (Kernel Language for Performance and Reliability analysis) as an intermediate language between software specification models and performance models. KLAPER is defined as a MOF (Meta-Object Facility) metamodel, which can also be transformed to/from KLAPER models.

Cortellessa investigated the possibility of building an unified ontology for software performance modeling [START_REF] Cortellessa | How far are we from the definition of a common software performance ontology?[END_REF]. His study originates from the comparison of three existing metamodels, (i.e. CSM, SPT, PMIF), identifies intersecting areas among the metamodels, and at the same time provides a roadmap to work towards merging metamodels into a unifying ontology.

Harrison et al. [START_REF] Harrison | A general performance model interchange format[END_REF] generalized the PMIF specifications by considering more abstract collections of interacting nodes using concepts compatible with the Reverse Component Agent Theory (RCAT). The interactions are more general in that they synchronize transitions between a pair of nodes rather than describing traffic flows.

MIF Tools

Lladó and colleagues developed a Web Service for solving QNM using PMIF [START_REF] Rossello | A web service for solving queueing networks models using PMIF[END_REF]. This established the feasibility of a plug-and-play approach for model interoperabilty and provided a foundation for other implementations. Cortellessa and colleagues built a Web Service to a collection of QNM tools along with a tool for creating a PMIF specification from a GUI based tool [START_REF]WEASEL, a web service for analyzing queueing networks with multiple solvers[END_REF].

The PMIF schema supports syntactic validation of models: it confirms that the XML file contains everything it is supposed to, that IDREFS point to a declared ID, etc. Even if the PMIF is syntactically valid, however, the models might be semantically incorrect. Lladó and colleagues developed a specification for semantic validations and a tool to confirm that a PMIF model is correct before attempting to convert it to a tool-specific file [START_REF] García | Performance model interchange format: Semantic validation[END_REF][START_REF] Smith | Performance Model Interchange Format (PMIF 2): A comprehensive approach to queueing network model interoperability[END_REF].

Woodside and colleagues developed a tool architecture, PUMA (Performance by Unified Model Analysis) as a framework into which different kinds of software design tools can be plugged as sources, and different kinds of performance tools can be plugged as targets [START_REF] Woodside | Performance by unified model analysis (PUMA)[END_REF].

Automation of Experiments and Results

Interchange formats have been defined for queueing network models (PMIF), software performance models (S-PMIF), layered queueing networks (LQN), UML, Petri Nets and other types of models. In each interchange format, a file specifies a model and a set of parameters for one run. Automating experiments requires 3 steps: specifying the experiment; executing one or more model runs and collecting output from those runs; and converting the output into meaningful results for the experiment. Each is addressed in the following sections. Figure 1 shows these steps. The performance model MIF is in the top-left while the experiment specification (Ex-SE) is shown at the top-right. These files are combined and used as input for one or more performance modeling tools. Each tool generates the performance metric output as specified for each experiment. The last step transforms the output into desired results as specified by the Results-SE.

Experimentation

Some general approaches to experimentation have been proposed:

-Zeigler [START_REF] Zeigler | Theory of Modeling and Simulation: Integrating Discrete Event and Continuous Complex Dynamic Systems[END_REF] has proposed a framework for modeling and simulation that included an experimental frame of the conditions under which the system or its model are to be exercised. -The IMSE Experimenter tool facilitates performance modeling studies within the Integrated Modeling Support Environment (IMSE) [START_REF] Hillston | A tool to enhance model exploitation[END_REF] . -The James II simulation modeling framework [START_REF] Himmelspach | Component-based models and simulations for supporting valid multi-agent system simulations[END_REF] allows any experiment definition that has a suitable plug-in for reading and converting the experiment definition (i.e., an instance of IExperimentReader).

Some modeling tools provide an ability to solve models multiple times while varying parameter values. Most current performance modeling tools have a Graphical User Interface (GUI) that leaves it to the user to conduct model experiments. Tools developed before GUIs were prevalent, however, provided experimentation features as part of their user interface: Qnap [START_REF] Potier | QNAP2: A portable environment for queueing systems modelling[END_REF], LQN [3], HIT and Hi-Slang [2].

Tools for other types of modeling have similar capabilities:

-Probabilistic Symbolic Model Checker (PRISM) [START_REF] Kwiatkowska | Prism: Probabilistic model checking for performance and reliability analysis[END_REF], provides a GUI that finds undefined constants in the model and queries the user for a value. -The Network Simulator [START_REF] Potier | The ns Manual[END_REF] has an object-oriented script language TCL that lets the user set up the model topology, place agents, inject events, etc. -the Möbius modeling environments [START_REF] Courtney | Design of experiments within the möbius modeling environment[END_REF] supports higher level experimental design with two types of two-level experimental design strategies: Plackett-Burman and two-level factorial design, and two types of response surface designs (central composite and Box Behnken).

Smith, Lladó and colleagues incorporated elements from these approaches to provide a comprehensive model interoperability solution for experimentation. We defined the Experiment Schema Extension (Ex-SE) for specifying a set of model runs and the output desired from them [START_REF] Smith | Interchange formats for performance models: Experimentation and output[END_REF][START_REF] Smith | Automatic generation of performance analysis results: Requirements and demonstration[END_REF]. The Ex-SE has the expressive power to specify iterations, alternations, assignments of values, actions based on model results and more. This schema extension provides a means of specifying performance studies that is independent of a given tool paradigm.

We use the term Schema Extension because it is used in combination with a host schema and customized to refer to solutions and outputs provided by the host. For example, we have specific instances of Ex-SE for Queuing network models and Petri net models. Figure 2 shows the schema extension instance for PMIF models, PMIF-Ex.

Experiment specifications can be created with an XML editor, with a GUI tool for describing experiments and generating the XML, or by exporting an experiment definition along with the model interchange format from a tool with experimentation functionality. Figure 3 shows a screenshot of the experimenter editor for PIPE2 [START_REF]Platform Independent Petri[END_REF], a Petri net modeling and analysis tool.

Model Output

An Output schema extension Output-SE is added to the host schema to specify the XML format to be used for output from the experiments. Like the Ex-SE it is customized to the type of output supported by the host schema.

The PMIF Output-SE includes:

a solution ID for relating the output to the experiment the value used for Ranges or other variables used in that solution the OutputWorkload (overall results by workload) -OutputNode (overall results by Node) -OutputNodeWorkload (results by Workload for Nodes).

Tools without experimentation need an Experimenter tool to interpret the experiment, invoke the tool for each <Solve>, and return the output. This can be Fig. 2. Experiment Schema Extension, PMIF instance a general tool that can work with multiple solvers, or tools with experimentation can adapt their Import mechanism to generate the tool specifications for the experiment. This is a more efficient implementation because the tool only needs to be invoked once, and the model does not need to be parsed multiple times.

Lladó and colleagues have developed a tool, EXperiment Output to Spread-Sheet (EXOSS), that takes the XML output from one or more experiments and produces a spreadsheet (xls) file for easily viewing the performance output. The tool works with PMIF queueing network models and Petri net models. It has also been integrated into the PIPE2 Petri net modeling tool.

Experiment Results

The IMSE Experimenter has an experimental plan with at least one analysis specification that describes how experimental results are obtained from model outputs. Thus, outputs from multiple runs can be used to obtain overall measures (e.g., mean, standard deviation). The PRISM GUI also provides the ability to specify a graph of the results and to export it in several formats (png, jpg, eps).

We examined Use Cases for building and analyzing performance model results then studied the output metrics and results that are most often desired for the Use Cases [START_REF] Smith | Automatic generation of performance analysis results: Requirements and demonstration[END_REF]. A review of published papers found some examples of common tables of results, such as response times for workloads with varying workload intensities, measured versus model results for response time and utilization for multiple workloads, etc. We also found common charts with line plots, columns or bars showing throughput versus response time; response time versus service time; number of users versus response time, etc.

Our conclusion for both QNMs and Petri net models is that the primary results are tables and charts. In the future, more sophisticated techniques for visualization of results may be desired, such as images of multidimensional colored surfaces. We did not address those types of results -we will leave that to the tools that render these types of images. Those tools usually can import the performance values to be displayed from a file and it should be straightforward to transform tool output into such a file format.

The most common format for tables and charts is xls as in spreadsheet tools such as Excel and OpenOffice Calc. However, the most common document preparation system for research publications is LaTeX. Our approach supports transforming the output metrics to tables and charts in xls and LaTeX. The results for an experiment are transformed into one or more tables/charts. Several tools have been implemented for experiment results [START_REF] Smith | Automatic generation of performance analysis results: Requirements and demonstration[END_REF].

Multiple Domains

In [START_REF] Smith | Interchange formats for performance models: Experimentation and output[END_REF], Ex-SE was illustrated with an instance of the extension in which the interchange schema was the PMIF and also LQN. The Ex-SE is compatible with a large number of interchange formats including: PMIF, S-PMIF, LQN, GPMIF, and Petri Net xml specifications. In general, one appends the Experiment type definition into the other XML schema, and changes the Variable type specifications to match new schema if necessary.

Petri nets are different from QNM and other performance model paradigms because they provide additional representation and analysis capabilities in addi-tion to performance analysis. Examples include constraints on tokens in places, invariant analysis, reachability analysis, and so on.

Lladó and colleagues presented a specific, extended instantiation of the Ex-SE for Petri nets (PN-Ex) [START_REF] Melià | An experimental framework for PIPEv2.5[END_REF] and analogous extensions to the Output and Results specifications. Both the Output-SE and the Results-SE required specification of an array of values instead of a single value.

The Experiment Schema Extension is not limited to use with models. It could be used with a measurement experimenter. Some of the terminology should be customized, such as changing Solve to Run, and changing the SolutionTypes to something such as ToolSpecification.

6 Real-time and Component-Based Systems Some work has addressed the performance analysis of component-based systems. Wu and Woodside use an XML Schema to describe the contents and data types that a Component-Based Modeling language (CBML) document may have [START_REF] Wu | Performance modeling from software components[END_REF]. CBML is an extended version of the Layered Queuing Network (LQN) language that adds the capability and flexibility to model software components and component-based systems. Becker et al. address components whose performance behavior depends on the context in which they are used [START_REF] Becker | Model-based performance prediction with the palladio component model[END_REF]. They address sources of variability such as loop iterations, branch conditions, and parametric resource demand, and then use simulation to predict performance in a particular usage context. Grassi et al. extend the KLAPER MOF meta-model to represent reconfigurable component-based systems in [START_REF] Grassi | A model-driven approach to performability analysis of dynamically reconfigurable component-based systems[END_REF]. It is to be used in autonomic systems and enable dynamic reconfiguration to meet QoS goals. These approaches are performance-centric in that they create/adapt a model of component based systems specifically for performance assessment. We prefer to work with generally accepted architecture representations, and use a common interchange format (S-PMIF) that allows the use of a variety of performance modeling tools to provide performance predictions for architecture and design alternatives.

Moreno, Smith and Williams have extended the S-PMIF to include features necessary for evaluating real-time, component-based systems [START_REF] Moreno | Performance analysis of real-time component architectures: A model interchange approach[END_REF]. They subsequently presented a substantially modified S-PMIF, version 2.0, that adapted the meta-model so that it can be expressed in terms of the Ecore meta-meta-modelthe core meta-model of the Eclipse Modeling Framework. Several changes were made to better align S-PMIF 2.0 with other performance-related meta-models (PMIF, LQN, and ICM), to clarify terminology, and simplify the M2M transformations [START_REF] Moreno | Performance analysis of real-time component architectures: An enhanced model interchange approach[END_REF]. This work demonstrated the use of the model interoperability approach for component-based real-time systems, and implemented a M2M prototype to transform an intermediate constructive model (ICM) to S-PMIF.

We found that preserving the type hierarchy and associations of the S-PMIF meta-model in the schema facilitates the implementation of S-PMIF interchange support by tools using strongly typed modeling technologies to generate the XML such as EMF or ATL. This work opened a door to allow the performance analysis of CCL specifications with other analysis tools without the need for additional integration effort. This means that standard SPE models can easily be used for analysis of systems specified in CCL. We demonstrated the ease with which the S-PMIF can be employed to transform additional design notations into software performance models, thus building on the previous UML-based approaches. In the future, it may be possible to unify the various interchange formats as suggested by [START_REF] Cortellessa | How far are we from the definition of a common software performance ontology?[END_REF]. In the meantime, it makes sense to extend the meta-models as necessary to create a superset of the necessary information for performance assessment.

Conclusions

This paper introduced the model interoperability approach for Software Performance Engineering. It presented significant milestones and stepping stones in the evolution of the approach: Version 1 Model Interchange Formats; Version 2 PMIF; Flurry of work in model transformations, MIF extensions and MIF tools; Automation of experiments and results; and Extensions for real-time and component-based systems. Our focus was initially on tools for SPE, however the model interoperability paradigm supports general performance engineering tasks for a variety of modeling tools and application domains.

MIFs provide a mechanism for exchanging performance models among tools. The exporting and importing tools can either support the MIF or provide an interface to read/write model specifications from/to a MIF file. The comparison of multiple solution techniques across tools can lead to a wide range of benefits. It is a significant result that MIFs can be used by anyone to exchange information relatively easily between two tools that provide a file input/output capability. It does not require the tool developer to modify code to be of use.

The basic version of PMIF 2 supports queueing network models that may be solved using efficient, exact solution algorithms. It was appropriate to restrict the domain for initial research. Our future work will create an extended PMIF and the supporting tools to cover model features that are supported by most simulation-based tools.

S-PMIF 2 is substantially different from the 2005 version. So, for instance, prototypes developed for the earlier version would have to be modified if they are to support the additional features. Model interchange formats and interfaces, however, must be relatively stable to be viable. S-PMIF was based on concepts embodied in two earlier model interchange formats: EDIF for VLSI designs and the CDIF for software design interchange. Creators of EDIF envisioned the stability problem and addressed it by using a concept of levels that add functionality at each successive level and giving ownership to a standards organization that managed changes. S-PMIF 2 adds a level for analyzing Real-time systems; future levels may add features for additional types of analysis. Tools can continue to support a lower level without change, or may opt to modify interfaces to support additional functionality and/or other changes. Future work should use the newest version, even for the basic level. Using a standard organization to manage the contents of model interchange formats should be considered.

The Experimental Schema Extension (Ex-SE) allows specification of multiple model runs along with the results that are desired from them. The schema extensions provide a means of specifying performance studies that is independent of a given tool paradigm.

Our future work will address a general purpose Experimenter tool with its corresponding editor. We also plan to develop templates for the most frequent results. We will extend the framework to support models that provide simulation solutions and other analysis techniques including real time systems analysis. An interesting extension will include creating rules for specifying threshold values and highlighting results in tables that exceed the threshold. Moreover, we plan to develop a GUI based transformation tool from output to results which will simplify the specification of the most common tables and graphs.

Model interoperability enables the use of the best tool(s) for the particular performance assessments. Early work demonstrated the benefit of comparing results from multiple tools; errors were found in several published case studies. Additional work is needed on model to model transformations among CSM, S-PMIF, PMIF, eDSPN, and others to enable comparison of results from multiple model paradigms. One approach is to unify the various interchange formats as suggested by [START_REF] Cortellessa | How far are we from the definition of a common software performance ontology?[END_REF]. Another is to ensure that sufficient modeling power is in each MIF to enable the M2M transformations.

The schemas and other information are available at www.spe-ed.com/pmif/. Several prototypes with source code are at dmi.uib.es/ ~cllado/mifs.

Fig. 1 .

 1 Fig. 1. interoperability framework

Fig. 3 .

 3 Fig. 3. PIPE2 experiment editor

Acknowledgements

This work is partially funded by the TIN2009-11711 project of the Ministerio de Educacion y Ciencia, Spain. Smith's participation was sponsored by US Air Force Contract FA8750-09-C-0086.