The solution to the problem of estimating the probability of exceeding a given value by a random value is discussed, in particular, estimating the small and very small probabilities of packet loss due to buffer overflows. It is shown that statistics of extreme values is an effective means of solving the problems of this class. With the appropriate choice of the structure of the extrapolation formula, which underlies the extreme values, it is possible to significantly accelerate the computational experiment. The use of the Extreme Value Theory method in combination with the Monte Carlo method for estimating small and very small values of the probabilities of random variables allows us to reduce the simulation time by 4-5 tens compared to the classical Monte Carlo method. Demonstrated the solution to the problem of calculating the buffer capacity for Weibull traffic based on the admissible probability 10-6 of its overflow.
A feature of the traffic of modern packet-switched info-communication networks is its
large-scale invariance (fractality). Fractal traffic is described by long-term
dependencies (LTD). The concept of a pulsating structure is often used in this context [
An adequate description of fractal traffic is given by probability distributions with
heavy tails [
The Weibull distribution, hereinafter W(c, b), is widely used in the technique and it is distributions with heavy tails with the distribution function of y values: F ( y) 1 e( y)c , y 0. (1) *
The distribution W(c, b) can be obtained as a function of the exponential distribution. Let X be a random variable that has an exponential distribution Fx X 1 ex. Then the random variable Y has a Weibull distribution Y X 1/с . Really
Fy (Y ) P(Y y) P X 1/с y P X yc 1 eyc 1 e y1/c c . The resulting final expression is a function for the Weibull distribution.
Let us compare the values of the tails W(c, b) and exponentially distributed random variables with the same probability of their observation (2) (3) e y1/c c ex y1/c c x yc x y x1/c .
From the relation, y x1/c it follows that for values x> 1 and c <1 value y> x, that is, the “tail” of the W(c, b) distribution is heavier than the “tail” of the exponential distribution.
“Heavy tail” means that in distributions with heavy tails, significant (large) values of a random variable are more likely (more often) than the same values, for example, in an exponential distribution.
The fractal properties of traffic have a significant effect on the characteristics of the
network [
An effective means of solving problems of this class is the statistics of extreme
values [
The purpose of the paper is to present a solution to the problem of calculating the buffer capacity for "heavy" traffic, based on the admissible probability Pover≤10-6 of its overflow. 2
We consider the network node as a queuing system (QS) of class G|G|1|m. To describe
the recurrent flow of applications and/or service time, we use the probability
distribution with a heavy tail - the Weibull distribution. With the ON-OFF model, the Pareto
distribution is more often considered. However, the Weibull distribution with the form
parameter c<1 has all finite moments. This makes the distribution W(c, b) suitable for
modeling the convergence of tail parts in a heavy multiplexing environment [
We set the task of calculating the required buffer capacity as the problem of finding the dependence the probability P of failure (loss of claim) on the size of the buffer m (m=0, 1, 2, ...). This will allow for any predetermined admissible1 loss probability P* to determine the corresponding smallest admissible buffer size m* by the formula following from (4):
P (m) m* –1 (P * ), (4) (5) where -1 is the inverse of the function . Assuming that the function is monotonically decreasing2, we can state that the inverse function -1 exists3. Thus, having solved the main problem, we can, for any given quality level (that is, for any maximum admissible probability of losses P*), by the formula (5) determine the smallest buffer size m* that provides it.
In solving this problem, we will rely on the method of extreme values (Extreme
Value Theory, EVT) [
The theory of extreme values is based on the postulate that for a large number of initial distributions F(x), the distribution of maxima Fn(x) taken from samples of size n tends to an asymptote of the form lim F n (bn an ) exp( exp( x)), (6) where an and bn are parameters estimated from independent sample values of a continuous random variable X.
A class of distributions converging to the asymptote (6) is called exponential. Weibull distribution belongs to this class.
The EVT method was developed to analyze continuous random variables.
The classical expression obtained using EVT for approximating the "tails" of
continuous distributions belonging to the exponential class has the form [
The accuracy of the approximation can be estimated by comparing the results obtained by the EVT method with the results calculated from the corresponding theoretical distributions
To this end, a computer model was constructed to simulate Weibull and exponential distributions. The following results were obtained from the experiment with the model sampling.
In the Table. 1 shows the results of modeling the “tail” of the Weibull distribution e(x/b)c with parameters c=0,5; b=1. The results of an experimental study of the use of the EVT method for estimating the tail of known theoretical distributions show a rather high approximation accuracy – for the same tail values the probabilities are of the same order of smallness.
Therefore, it can be argued that the function constructed by the EVT method and approximating the tail of the distribution is equivalent to the theoretical function.
Also, a comparison of the values of the Weibull “tails” and the exponential distribution for probabilities of the same order of smallness shows how much the Weibull “tail” is heavier than the exponential one.
The process of receipt and servicing of requirements in the QS with a limited queue
(hereinafter referred to as the limited buffer – LB ) can be considered as a regenerative
process [
During the busy interval, requirements arrive and leave the system. The regeneration
point in the model coincides with the moment the request arrives, which catches the
service node unoccupied [
From the analysis of the QS model with an unlimited queue (hereinafter referred to
as the unlimited buffer - UB) [
Due to the stationary nature of the QS, the analysis of events in one employment interval is equivalent for all intervals.
The maximum value of the queue Li in the UB achieved during the escalation process at the i-th employment interval does not depend on the number of escalation and reduction processes, nor the number of requests served in this interval and does not depend on the length of the employment gap.
The value of Li depends only on the time intervals between arrivals and service intervals. Since these times are random variables, the value Li for i is also a random variable. When observing an infinite number of employment intervals, it can be argued that the maximum value of the queue L has a probability distribution function of its values.
This allows us to finally recognize that the probability of losing requests in an LB with a capacity of N (probability of buffer overflow) is a function of the tail of the distribution of the values of the maximum value L, starting with the value L=N+1.
Therefore, if the distribution function for L=N is F(x), then the probability of losses is Ploss(N) f Q(N 1) f 1 F(N). (8) that is, it is a distribution function of the tail of the probabilities of the values of the maximum queue length in the UB.
Experimental estimates of the required capacity of the limit buffer
The queue in the buffer is a discrete random variable. To describe the probability
function of the values of the “tails” of discrete random values, for expression (4) is
obtained extension in the form [
Q x R an exp( x bn 1 nK an ), (9) were an and bn are the coefficients calculated from the sample data; K – the average number of applications received at the entrance of the QS for the regeneration period; n is the number of values in the sequences into which the sampling sequence is composed of the maximum values of the queue at the regeneration intervals; R exp xan – the constant R depends on the value of the interval 2x=hi-hi-1 between the values hi and hi-1 of the discrete values x.
Let Ploss_ad be the admissible value of the probability of losses due to the excess of the buffer capacity N.
We set the value of Ploss_ad and solve (9) concerning the variable x=N. We obtain an expression for estimating the value of the buffer capacity N, which provides the value of the probability of losses Ploss (N) ≤ Ploss_ad (N), in the form (10) where x is the nearest integer not less than x.
To use expression (10) to determine the required value of the capacitance of the LB, it is necessary to calculate the coefficients, an and bn from the sample data K , ab, and bn.
For this purpose, a simulation model of a single-phase QS with LB was realized. The simulation model reproduced the periods of regeneration of receipt of applications in the buffer and their servicing. The maximum values of the queues and their processing were taken into account.
The model corresponded to four types of QS: M|W|1, W|W|1, W|M|1, and M|M|1 with load factors = 0,5; 0,7; 0,9 for each type of QS. The simulation was carried out for the given values of the probability of losses Ploss_ad: 10-4, 10-6, 10-8, 10-10.
Tables 1-4 show the simulation results for this source data and PM is the value of the probability of losses obtained from the Monte Carlo simulation with the found values of the buffer capacity N.
The corresponding values of Ploss_ad and PM presented in the tables are of the same order of smallness, which confirms the sufficient accuracy of the calculated results by expression (10).
Also, a comparative analysis of the calculated data in Tables 1-3 with the data in Table 4 confirms the fact that the packet traffic, in which receiving of requests are described as distribution with heavy tails, requires significantly more significant amounts of the buffer memory in network nodes.
Ploss_ad
Fractal models are difficult to analytically interpret. The presented method for
calculating the buffer capacity under the conditions of “heavy” traffic described by the
Weibull distribution is relatively simple and efficient. The use of the EVT method in
combination with the Monte Carlo method for estimating small and very small values
of the probabilities of random variables allows us to reduce the simulation time by 4–5
tens in comparison with the classical Monte Carlo method [
The EVT method was developed to approximate extreme statistics of distributions
of an exponential class [
However, the case of small values of the shape parameter (c<1) is of particular
interest since Weibull distributions with such parameters occupy an intermediate place
between distributions with an exponential decrease in tails (exponential distribution,
gamma distribution) and “heavy-tailed” distributions with power-law descending tails
of the Zipf-Pareto type [
In the same work [
In our opinion, this is a significant point, since it expands the Weibull distribution capabilities to describe real traffic.