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

Demetres D. Kouvatsos, Salam A. Assi

► To cite this version:

Demetres D. Kouvatsos, Salam A. Assi. On the Analysis of Queues with Heavy Tails: A Non-Extensive Maximum Entropy Formalism and a Generalisation of the Zipf-Mandelbrot Distribution. Performance Evaluation of Computer and Communication Systems (PERFORM), Oct 2010, Vienna, Austria. pp.99-111, 10.1007/978-3-642-25575-5_9. hal-01586893

HAL Id: hal-01586893

https://inria.hal.science/hal-01586893

Submitted on 13 Sep 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On the Analysis of Queues with Heavy Tails: A Non-Extensive Maximum Entropy Formalism and a Generalisation of the Zipf-Mandelbrot Distribution

Demetres D. Kouvatsos and Salam A. Assi

Networks and Performance Engineering Research Group (NetPEn),
Informatics Research Institute (IRI), University of Bradford, Bradford, BD7 1DP, UK
D.Kouvatsos@Bradford.ac.uk, S.A.Assi@Leeds.ac.uk

**Abstract.** 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 short-range interactions. Focusing on 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.

**KeyWords:** Performance evaluation, extensive maximum entropy (EME) formalism, non-extensive maximum entropy (NME) formalism, generalised exponential (GE), traffic burstiness, self-similarity, short-range dependence (SRD), long-range dependence (LRD), queueing systems, Zipf-Mandelbrot (Z-M) distribution.

## 1 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., [20]).

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., [6, 19]). Some analytic mechanisms for estimating the tail index of Internet traffic with heavy tails were reported by Rezaul and Grout [19], based on the Pareto distribution. Further analytic studies can be found in [1, 10, 14, 15]. These works are based on the optimisation of generalisations of the classical Boltzmann-Gibbs-Shannon entropy function (c.f.,[4, 21]), such as those proposed in the diverse fields of Quantification Theory [8], Statistical Physics [23] and Information Theory [18].

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., [8, 23]), 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 [22]. 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 [16] 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

## 2.1 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)$ [4, 21] is defined by

$$H^*(p_N) = -c \sum_{n=1}^{N} p_N(n) \log p_N(n) \quad (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” [7] 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” [7].

By analogy, traffic flows in queues with short-range dependence (SRD), such as those represented by Poisson (regular), compound Poisson (bursty) [12] and batch renewal (BR) (correlated) [13] 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., [9]), as a method of inductive inference (c.f., [22]) 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., [12, 13]) types of state probabilities for single server queues.

## 2.2 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” [7]. 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 [23] 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 - \sum_{n=1}^{N} p_{q,N}(n)^q)/(q-1) \quad (2)$$

where $c(c > 0)$ is a positive constant, $q$ is a real number known as the ‘non-extensivity’ 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 \to 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 [23] is identical to the one devised earlier by Havrda-Charvat [8] 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 normalisation and mean (generalised internal) energy constraint, it was shown (c.f., [23]) that the NME state probability is of the Z-M type distribution [16], 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., [1, 10, 14, 15, 23]).

NME solutions for infinite and finite capacity queues were first established in [1, 14] by maximising the extensive Havrda-Charvat entropy [8] and other generalised entropy measures (e.g., [18]), 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 [23] in Statistical Physics was adopted by Karmeshu and Sharma [10] 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 [17] 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 [15] for single server queues with infinite and finite capacities, based on the reinterpretation of a proposed heuristic generalisation of the Norros formula [17].

### 3 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 \in S\}$, belonging in closed convex set $\Omega$, 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 - \sum_{S_n \in S} p_q(S_n)^q) / (q - 1) \quad (3)$$

subject to normalisation and the mean value constraints, namely

$$\sum_{S_n \in S} p_q(S_n) = 1 \quad (4)$$

$$\sum_{S_n \in S} f_{k,q}(S_n) p_q(S_n) = F_{k,q} \quad (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 [18].

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) = \frac{1}{Z_q} \left[ 1 + (1 - q) \sum_{k=1}^{m} \beta_k f_{k,q}(S_n) \right]^{\frac{1}{q-1}} \quad (6)$$

where $\{\beta_k\}, k = 1, 2, ..., m\}$ are the Lagrangian multipliers corresponding to the constraints (4), $Z_q = \exp\{\beta_0\}$ is the normalizing constant and $\beta_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.

## 4 The NME Formalism as a Method of Inductive Inference for Non-extensive Systems

The principles of EME [9] and minimum relative entropy (MRE), a generalisation, were shown in [22] 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 [22] 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., [22]) on the credibility of the NME formalism, as a method of inductive inference, is investigated below.

## 4.1 Uniqueness

Adopting the notation of Section 3, let $f_{q,N}, h_{q,N} \in \Omega$ 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}) = \alpha H^*(f_{q,N}) + (1 - \alpha)H^*(h_{q,N}) \le H^*(\alpha f_{q,N} + (1 - \alpha)h_{q,N}) \quad (7) $$

Since the set $\Omega$ is convex, there is a distribution (i.e., weighted average) given by $\alpha f_{q,N} + (1 - \alpha)h_{q,N}$, which belongs to $\Omega$ 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} \in \Omega$ having the same maximum entropy in $\Omega$. Thus, the Havrda-Charvat-Tsallis NME formalism satisfies the axiom of uniqueness (c.f., [22]).

## 4.2 Invariance

Following the analytic methodology in [22], let $\Gamma$ be a coordinate transformation from state $S_n \in S, n = 1, 2, ..., N$ to state $R_n \in R, n = 1, 2, ..., N$), where $R$ be a transformed set of $N$ possible discrete states $\{R_n, n = 1, 2, ..., N\}$ with $(\Gamma p_{q,N})(R_n) = J^{-1}p_{q,N}(S_n)$, where $J$ is the Jacobian $J = \partial(R_n)/\partial(S_n)$. Moreover, let $\Gamma\Omega$ be the closed convex set of all probability distributions $\Gamma p_{q,N}$ defined on $R$ such that $\Gamma p_{q,N}(R_n) > 0$ for all $R_n \in R, n = 1, 2, ..., N$ and $\sum_{n=1}^N \Gamma p_{q,N}(R_n) = 1$.

It can be clearly seen that, transforming of variables from $S_n \in S$ into $R_n \in R$, the Havrda-Charvat-Tsallis extended entropy function (c.f., (6)) is transformation invariant, namely

$$ H^*(p_{q,N}) = H^*(\Gamma p_{q,N}) \quad (8) $$
Thus, since the minimum in $\Gamma\Omega$ corresponds to the minimum in $\Omega$, the NME formalism satisfies the axiom of invariance.

## 4.3 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) = \text{Pr}\{X = x_n\}$ and $g_{q,N}(y_n) = \text{Pr}\{Y = y_n\}$, respectively.

Assuming that $Q$ and $R$ are independent systems, then using the joint probability, $h_{q,N}(x_k, y_n) = \text{Pr}(x_k, y_n)$, $k, n = 1, 2, ..., N$ and the definition of (6), it clearly follows that

$$H^*[h_{q,N}] \neq H^*(f_{q,N}) + H^*(g_{q,N}) \quad (9)$$

The inequality (9) 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., [22]). 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 \to 1$ limit, equation (9) becomes

$$H^*[h_{q,N}] = H^*(f_{q,N}) + H^*(g(Y_{q,N})) \quad (10)$$

The equality (9) verifies that the joint EME state probability distribution, as expected, satisfies the axiom of system independence (c.f., [22]. 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.

## 4.4 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 $\xi_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}) \in \Omega_i$, where $\Omega_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) \in \Omega$, where $\Omega$ 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) = \sum_i \xi_i H_i^*(f_{q,i}) \quad (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 [22].

## 5 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 (6), 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., [12]), 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 $\lambda$, the squared coefficient of variation (SCV) of the interarrival times, ($Ca^2$), the mean service rate $\mu$ 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., [1, 10, 14, 15]), where the constraints of the associated NME solutions include, in addition, the non-extensivity parameter, $q$ (c.f., [8, 23]), or, equivalently, the Hurst self-similarity parameter, $H$ (c.f., [3]) such that $q = 1.5 - H, 1/2 < q, H < 1$ (c.f., [10, 15, 19]).

Note that a heuristic generalization of Norros formula [17], for the estimation of the buffer capacity of a storage system (under a fBm input process), was conjectured in [15]. 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 abstract generalised self-similar (gS-S) arrival process with parameters $H, \lambda$ and $Ca^2$ and a GE-type service time distribution completely defined by $\mu$ and $Cs^2$. This MQL heuristic expression is given by
$$L_H = \frac{\rho^{\frac{1}{2(1-H)}}}{2^{\frac{1}{2(1-H)}}} \left( \frac{[1 - \rho + Ca^2 + \rho Cs^2]^{\frac{1}{2(1-H)}}}{(1 - \rho)^{\frac{H}{1-H}}} \right) \quad (12)$$

where H takes values in the interval $\frac{1}{2} < H < 1$ [15]. Note that the heuristic formula (12) takes explicitly into account the adverse combined impact of traffic burstiness (via the SCVs $Ca^2$ and $Cs^2$) and self-similarity (via parameter $H$) on queueing system performance. The expression (12) reduces correctly to the Norros formula [17] when $Ca^2 = Cs^2 = 1$. Moreover, for $H = \frac{1}{2}$ (i.e., $q \to 1$) equation (12) yields the mean queue length formula of a stable GE/GE/1 queue [12].

## 5.1 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 $\lambda$, interarrival time SCV, $Ca^2$ and Hurst self-similarity parameter, $H$ and iii) a GE-type service time distribution with mean service rate, $\mu$ and service time SCV, $Cs^2$. Moreover, at any given time, let $p_{q,N}(n), n = 0, 1, \dots, 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., [14, 15]): Normalisation, server utilisation $Uq, N = 1 - p_{q,N}(0)$, MQL, $L_{q,N} = \sum_{n=0}^{N} np_{q,N}(n)$ and full buffer state probability, $\phi_{q,N} = p_{q,N}(N)$, where $\phi_{q,N}$ satisfies the flow balance condition, namely

$$\lambda(1 - \pi_{q,N}) = \mu U_{q,N} \quad (13)$$

where $\pi_{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, \dots, 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 - \sum_{n=0}^{N} p_{q,N}(n)^q / (q-1)) \quad (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) = \frac{1}{Z_{q,N}} [1 + \alpha_N(1-q)n + \beta_N(1-q)h_{q,N}(n) + \gamma_N(1-q)s_{q,N}(n)]^{\frac{1}{q-1}} \quad (15)$$

where $\beta_N$, $\alpha_N$ and $\gamma_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) = \begin{bmatrix} 0, & n = 0 \\ 1, & n \neq 0 \end{bmatrix}. \quad (16)$$

$$s_{q,N}(n) = \begin{cases} 0, & n < N \\ 1, & n = N \end{cases} \quad (17)$$

and $Z_{q,N}$ is the normalizing constant expressed by

$$Z_{q,N} = \sum_{n=0}^{N} [1 + \alpha_N(1-q)n + \beta_N(1-q)h_{q,N}(n) + \gamma_N(1-q)s_{q,N}(n)]^{\frac{1}{q-1}} \\ = \zeta \left[ \frac{1}{1-q}, \frac{1+\beta_N(1-q)h_{q,N}(n)+\gamma_N(1-q)s_{q,N}(n)}{\alpha_N(1-q)} \right] \quad (18)$$

where $\frac{1}{1-q} > 1, q > 0$ and $\zeta$ denotes the Hurwitz-Zeta function (c.f., [2]).

Note that a direct derivation of the NME solution (15), can be seen in [15]. As $N \to \infty$, the NME solution, $p_{q,N}(n)$ (15) becomes identical to that of the corresponding infinite capacity queue with heavy length tails [14, 15]. Moreover, at the limit $q \to 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 [12].

For $q < 1, \rho < 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., [15]) and also to the one associated with Tsallis original solution (c.f., [10]), namely

$$p_N(n) \sim n^{\frac{1}{1-q}}, \quad \frac{1}{2} < q < 1 \quad (19)$$

The Newton-Raphson numerical method can be applied, as in [10] and [15], 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 $\alpha_N$ and $\beta_N$ are asymptotically invariant to the buffer size, $N$ i.e., $\alpha_N = \alpha$ and $\beta_N = \beta$, where $\alpha$ and $\beta$ are the Lagrange multipliers of the corresponding infinite capacity queue. Moreover, the blocking probability, $\pi$, can be computed by using the flow balance condition (13).
# 6 Numerical Results

This section presents four typical numerical experiments (c.f., Figs. 1-3(b)) illustrating the credibility of the NEM 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 $\rho$ 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 $\rho$ under moderate traffic burstiness (variability) at $Ca^2 = 3$, the utilisation $U_{q,N}$ for smaller values of non-extensivity parameter $\frac{1}{2} < q < 1$ is progressively decreasing. This indicates that increasing self-similarity 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 [5], the

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** The relation between $p_{q,N}(n)$ and $n$ for a gS-S/GE/1/N queue with $Ca^2 = 4$, $Cs^2 = 9$, $N = 20$, $\lambda = 0.8$, $\mu = 1.0$ and $\{q = 0.6, 0.7, 0.8, 0.9\}$.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>**Fig. 2.** The relation between $p_{q,N}(n)$ and $n$ for a gS-S/GE/1/N queue with $Cs^2 = 9$, $N = 5$, $q = 0.6$, $\lambda = 0.8$, $\mu = 1.0$ and $\{Ca^2 = 1, 3, 8, 16\}$.</figcaption></figure>
<figure><img src="image_4.png" /><figcaption>**Fig. 3.** The relation between $U = 1 - p_{q,N}(0)$ and $\rho$ 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$.</figcaption></figure>

acute transition from low to high utilisation for lower values of $q$, as the pa-
rameter $\rho$ attains increasing values, is a typical attribute of self-similarity and/or
LRD network traffic with moderate variability (c.f., [10, 15]).

However, this utilisation ‘anomaly’ of the plot $U_{q,N}$ versus $\rho$ 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 $\rho$ reaches a more distinguished pattern as the adverse impact of higher traffic burstiness on utilisation $U_{q,N}$, even for small values of $\rho$, is quite evident. In particular, the curves of Fig. 3(b) have a much lower intersection point towards $\rho \to 0$ whilst those in Fig. 3(a) are quite independent from each other up to a higher threshold value of $\rho$. 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 1 - 3(b)) 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.

**7 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., [22]), 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., [11]), 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 multi-service heterogeneous networks taking into account merging, splitting and departing flow steams of bursty and $S-S$ traffic processes.

## References

1. Assi, S.A.: An Investigation into Generalised Entropy Optimisation with Queueing Systems Applications. MSc Dissertation, Dept. of Computing, School of Informatics, University of Bradford (2000)

2. Bateman, H.: Higher Transcendental Functions. McGraw-Hill, New York, NY, 1 (1953)

3. Beran, J.: Statistics for Long-Memory Processes. Chapman & Hall, ISBN 0-412-04901-5 (1994)

4. Chakrabarti, C.G., Kajal, De.: Boltzmann-Gibbs Entropy: Axiomatic Characterisation and Application. Internat. J. Math. & Math. Sci. 23(4), 243-251 (2000)

5. Choudhury, G.L., Whitt, W.: Long-tail Buffer-content Distributions in Broadband Networks. Performance Evaluation 30, 177-190 (1997)
6. Crovella, M.E., Lipsky, L.: Long-lasting Transient Conditions in Simulations with Heavy-Tailed Workloads. Proc. of Winter Simulation Conference, 1005–1012 (1997)

7. Tsallis Statistics, Statistical Mechanics for Non-extensive Systems and Long-Range Interactions. Notebooks, http://www.cscs.umich.edu/crshalizi/notabene/tsallis, html (23:22 29 Jan 2007)

8. Havrda, J.H., Charvat, F.: Quantification Methods of Classificatory Processes: Concept of Structural Entropy. Kybernatica 3, 30–35 (1967)

9. Jaynes, E.T.: Information Theory and Statistical Mechanics. Physical Review 106, 620–230 (1957)

10. Karmeshu, Sharma, S.: Long Tail Behaviour of Queue Lengths in Broadband Networks: Tsallis Entropy Framework. Technical Report, School of Computing and System Sciences, J. Nehru University, New Delhi, India (August 2005)

11. Karmeshu, Sharma, S.: q-ExponentiaL Product-Form Solution of Packet Distribution in Queueing Networks: maximisation of Tsallis Entropy. IEEE Communication Letters 10(8), 585-587(2006)

12. Kouvatsos, D.D.: Entropy Maximization and Queueing Network Models. Annals of Operation Research 48, 63–126 (1994)

13. Kouvatsos, D.D., Awan, I., Fretwell, R., Dimakopoulos, G.: A Cost-Effective Approximation for SRD Traffic in Arbitrary Multi-Buffered Networks. Computer Networks 34, 97–113 (2000)

14. Kouvatsos, D.D., Assi, S.A.: An Investigation into Generalised Entropy Optimisation with Queueing System Applications. In the Proceedings of the 3rd Annual Postgraduate Symposium on the Convergence of Telecommunications, Networking and Broadcasting (PGNet 2002), M. Merabti (Ed.), Liverpool John Moores University Publisher, 409–414 (2002)

15. Kouvatsos, D.D., Assi, S.A.: On the Analysis of Queues with Long Range Dependent Traffic: An Extended Maximum Entropy Approach. Proceedings of the 3rd Euro-NGI Conference on Next Generation Internet Networks - Design and Engineering for Heterogeneity, Trodheim, Norway, 226–233 (May 2007)

16. Mandelbrot, B.B.: The Fractal Geometry of Nature. W.H. Freeman, New York (1982)

17. Norros, I.: A Storage Model with Self-similar Input. Queueing Systems and their Applications 16, 387–396 (1994)

18. Renyi, A.: On Measures of Entropy and Information. Proceedings of the 4th Berkely Symposium Math Stat And Probability 1, 547–561 (1961)

19. Rezaul, K.M., Grout, V.: A Comparison of Methods for Estimating the Tail Index of Heavy-tailed Internet Traffic. in 'Innovative Algorithms and Techniques in Automation, Industrial Electronics and telecommunications, Dordrecht: Springer, 219–222 (2007)

20. Sahinoglu, Z., Tekinay, S.: On Multimedia Networks: Self-similar Traffic and Network Performance. IEEE Communication Magazine 37, 48–52 (1999)

21. Shannon, C.E.: A Mathematical Theory of Communication. Bell Syst. Tech. J. 27, 379–423 & 623–656 (1948)

22. Shore, J.E., Johnson, R.W.: Axiomatic Derivation of the Principle of ME and the Principle of Minimum Cross-Entropy. IEEE Transaction on Information Theory IT-26, 26–37 (1980)

23. Tsallis, C.: Possible Generalisation of Boltzmann-Gibbs Statistics. Journal of Statistical Physics 52(1-2), 479–487 (1988)