Description for Packet Switch

Abstract

The arrival process description is important problem for analysis of the packet switches that can be considered as queueing systems. Such queueing systems are the appropriate models for the study of the stochastic characteristics. The accuracy of the results of the model study is largely determined by the correctness of the description of the arrival process. This paper proposes a method to solve the problem of choosing a distribution type to describe arrival process at the teletrafic system input. The authors introduce a criterion for choosing the distribution type based on the error minimization in the estimates of the mean value and coeficient of variation in the delay times in the teletrafic system. Sometimes measurement results characterizing the arrival process are available. In this case, the correctness of the proposed distribution is also checked using the goodness-of-fit test. The paper provides case studies on how the proposed method can be applied to the process of choosing the distribution type in question.

Keywords

• goodness-of-fit test
• relative error

-

Statement The stated problem can be considered a special case of estimating the distance between functions [ 1 ]. In the teletrafic theory, this problem has some peculiarities. In this article, an entity that should be serviced by the queueing system is called a request. Typical example of the request is IP packet that is processed by a packet switch. For systems with queues [ 2, 3 ], the reliable information about the requests arrival interval distribution at the input of the object nEvelop-O

CEUR Workshop Proceedings htp:/ceur-ws.org IS N1613-073

CEUR Workshop Proceedings (CEUR-WS.org) Workshop on information technology and scientific computing in the framework of the X International Conference under study is normally obtained based on measurements of packet trafic. If measuring is not possible, the proposed hypothesis should be thoroughly reasoned.

Based on measurements, step function () is formed, for which an interval of constant time is usually selected on the abscissa axis. In some cases, function () can be convenient to use if the initial distribution replacement simplifies the further model analysis. Function () is usually chosen from a set of known random value distributions [ 4 ].

For the analysis of most teletrafic models, it is suficient to know the first and second moments of the request delay time in the system — (1) and (2). Interestingly, most of the known relations [ 2, 3 ] rely on delay time coeficient of variation instead of the second moment. That’s why the proximity of values (1) and to the values obtained using measurements of function () determines whether distribution () has been chosen appropriately. Therefore, relative errors in evaluating values (1) and denoted below as 1 and 2, respectively, should not exceed the predefined thresholds.

We can choose value for function () based on the considerations given in [ 5 ]. Values of function () at points that are multiples of are known. Figure 1 shows distribution functions () and () up to value 8 on the abscissa axis. For example, parameter 3 defines the diference between two distributions at point 3 . In this example, we observe the maximum diference between functions () and () at point 8 .

1

F(t), A(t) 0 1 2 3 4 5 6 7 8

The proximity of functions () and () is normally measured by checking if they belong to the same distribution class using an appropriate goodness-of-fit test [ 6 ]. This approach does not allow us to make assertions about the values of errors in evaluating the characteristics at the teletrafic system output.

Figure 2 shows the simplest model of a teletrafic system as a so-called “black box”. Function () represents the distribution of the request processing times in the teletrafic system. In other words, it defines the set of operations on functions () or () . Two distributions at the model output are of practical interest: request delay time () and time interval () at which the processed requests leave the teletrafic system.

F(t) F(t) or A(t)

BB((tt))

S(t) and D(t)

This paper only covers distribution () . Moreover, the analysis of function () is limited to estimating values (1) and . 2. Choosing Distribution Based on Measurements Let us assume that the measurements were made correctly and we obtained step function () with increment at point . Some increments can evaluate to zero. Generally, index varies from zero to , that is, for ≥ , condition () ≡ 1 is true. It is convenient to represent function () as the Laplace-Stieltjes transform [ 7 ] denoted as () .

The first and second moments of the distribution, (1) and (2), are determined according to the corresponding rules by diferentiation of function () . Standard deviation and coeficient of variation are calculated based on values (1) and (2) [ 4 ].

Approximating distribution () is normally chosen using the least squares method [ 8 ]. In some cases, it is reasonable to use the weighted least squares method [ 9 ]. In this case, normally, the following inequalities are true: (1) ≠ (1), (2) ≠ (2), ≠ and ≠ . These inequalities introduce additional errors in the evaluation of characteristics (1) and .

A methodological approach based on the following operations can help us minimize these errors: • First, the most appropriate type of two-parameter distribution () is selected using a suitable goodness-of-fit test [ 6 ]. • Then, we determine such parameters of distribution () , for which equations (1) = (1) and = (or = if it simplifies the calculations) are true.

So, the distribution parameters are calculated by solving a system of two equations. 3. Choosing Distribution Using Goodness-of-Fit Test Pearson’s chi-squared test [ 6 ], also known as 2, is often used to test the hypothesis that the sample belongs to the theoretical distribution () . Some researchers prefer the KolmogorovSmirnov test for this purpose [ 10 ]. Some other tests may also be chosen.

A goodness-of-fit test is an important step in solving the stated problem, which should be described in terms of “necessity and suficiency” [ 11 ]. Replacing function () with distribution () should be interpreted as a necessity but cannot be considered suficient. Indeed, goodnessof-fit tests cannot provide numerical estimates of errors that occur when further operations are performed on distribution () . Alternatively, if function () and distribution () are not close to each other [ 1 ], an acceptable diference in characteristics (1) and can be unstable within the load range under study. Besides, this narrows the application scope of the proposed method for choosing distribution () .

However, we cannot insist that the condition, which was hereinafter treated as necessary, is indispensable. When solving some specific tasks, the mentioned tests may indicate that the chosen hypothesis is false while the evaluation accuracy of characteristics (1) and can be acceptable. A simple example, in which two moments are the same while distribution functions difer significantly, will be given below in this paper. Therefore, it appears that the obtained results will be still more valuable if we use proven laws of mathematical statistics. 4. Proposed Method for Choosing Distribution Measuring trafic multiple times at diferent packet switches shows that function () belongs to a class of distributions that are defined on a limited interval. They are denoted with the lower index “ ” (the first letter in word “limited”). The lower index “ ” (the first letter in word “unlimited”) is used to denote distributions that take possible values along the entire positive semiaxis. The applied approximations () introduce an error, which is usually very dificult to evaluate. Therefore, it is appropriate to look for an approximation to function () in the () class.

A particular interest in the functions of the () class is related to a beta distribution [ 12, 13 ]. It can be useful in studying functions () with a high value of the coeficient of variation, which is typical of packet multiservice networks. Other distributions [ 4 ], such as parabolic, uniform, and others, are also relevant. When the derivative of function () has several extrema, we can use a combination of two or more distributions that belong to the () class.

To get a conclusive estimate, it is suficient to consider an example of using a beta distribution defined on the interval [0;1]. In this case, its density () is determined by the following relation [ 4 ]: () = Γ( + ) Γ()Γ( )

−1 (1 − ) −1 .

Variable is a dimensionless value. It can be defined as time divided by value . The following conditions are true for the distribution parameters in formula (1): > 0, > 0 . The relations for calculating the mathematical expectation of the request arrival interval value (1) and its coeficient of variation are given, for example, in [ 4 ]: , =

√ ( + + 1) .

(1) (2) (3)

It is evident that (1) < 1. Having fixed value (1), we change the parameters of the chosen approximating distribution to obtain the necessary values for coeficient of variation calculate parameters and , it is necessary to solve a system of two equations, which provides . To the following result: = [1 − (1) (1 + 2 )] [1 − (1)] (1) 2 , = 1 − (1) (1 + 2 ) .

2 1.0

Comparing two distributions with a 5% significance level according to Pearson’s chi-squared test showed that the beta distribution can be used in further research. Then, we should choose a teletrafic system model, which would allow us to evaluate errors in calculating values (1) and . In this paper, a packet switch is considered a teletrafic system. The request (IP packet) processing time can be safely considered a constant value [ 14, 15 ]. Therefore, in the Kendall’s notation [ 3 ], the model under study can be represented as //1 . The designation “ ” in the first position specifies the nature of the arrivals process, as determined by the beta distribution. If the arrivals process is defined based on measurements, the letter “ ” [ 3 ] should be put in the first position.

Later, we will describe the impact of request processing time distribution () on the evaluation accuracy of values (1) and . For this reason, for the sake of generality, the processing time for the //1 model is denoted below as moment (1). Values (1) should be chosen in such a way as to investigate the dependence of errors 1 and 2 on model load . According to the above-mentioned designations, load is defined by the relation of (1) to (1). In this paper, the load range of 0.1 ⩽ ⩽ 0.9 is selected based on two considerations. The load of less than 0.1 is of no practical interest in terms of compliance with the Quality of Service targets. The load greater than 0.9 is not typical of the teletrafic system’s operating processes and requires additional research.

The proposed range of load change is suficient to analyze the operation modes of a model being a teletrafic system, when the object under study functions in standard conditions, which allow us to assume that the number of waiting places in a queue is unlimited. This hypothesis is true if the real capacity of the bufer memory is rated for the loss probability at the approximate level of 0.001, as stated by the International Telecommunication Union Standardization Sector in Recommendation Y. 1541 [ 16 ]. The validity of this assumption was established in [ 17 ].

For the model under study, the values of errors 1 and 2 in the given range did not exceed 1.5%. This is quite acceptable for the tasks in the telecommunication network design. Several similar models with other step function types have shown acceptable estimates for errors 1 and 2 in the given range of the load change.

The change in distribution () , which allows us to analyze the change in values 1 and 2 when the coeficient of variation of the request processing time is increased to 2.0, showed that the corresponding errors are within the same range. It means that the obtained estimates of errors 1 and 2 are almost invariant with the request processing time distribution.

The type of function () , for which Pearson’s chi-squared test discards the hypothesis that this function is similar to beta distribution () , was chosen artificially using variations in values of increments . The analysis of such functions () and () showed that errors 1 and 2 begin to grow significantly and often exceed 20%. Generally, this value is not considered acceptable for the analysis of the teletrafic system characteristics.

The results confirm an intuitive conclusion that the positive result of the goodness-of-fit test should be considered a “necessary” condition for applying the proposed method for choosing function () . This statement is based on the understanding that the goodness-of-fit test is indicative of a relatively small distance between the functions [ 1 ].

However, as the analysis was limited to using only one distribution, it does not allow us to apply this statement to all types of functions () . If we limit the types of function () to the distributions that passed the goodness-of-fit test, it will meet the “beauty in science” criterion [ 18 ]. 5. Errors Related to Diferent Types of Distributions The condition that the two moments of functions () and () should be equal can be met for several types of the approximating distribution. This brings up the question about the preferred type of distribution () . It may happen that some distributions will show very close values of errors 1 and 2.

This assumption is based on the results given in [ 19 ]. This monograph presents a graph of Hurst exponent dependence [ 20 ] on coeficient of variation for two types of distributions, a gamma distribution and Weibull distribution [ 4 ]. The mentioned graph is reproduced in Figure 4. According to the graphs, the maximum deviation of the corresponding dependencies does not exceed 5%.

Errors of type 1 and 2 for diferent distributions () but with identical first and second moments, respectively, are of practical interest. The variance or the coeficient of variation can be used instead of the second moment if this simplifies the required calculations.

Let us consider three types of distribution () . The first and second types are the same as the distributions shown in Figure 4. The third type is a hyperexponential distribution [ 4 ]. All the described functions belong to the () family. For all three distributions, (1) = 1 and = 2. Table 1 shows the values of the skewness and kurtosis [ 4 ], which significantly difer for the distributions under study.

However, the pattern of change in the three curves that represent the density graphs of the distributions under study, has a common nature, which is illustrated in Figure 5 and confirmed by the 2 test. In other words, functions 1 () , 2 () and 3 () are close to each other [ 1 ]. For this reason, any distribution can be chosen as an approximating dependence if values (1) and are the same.

0.5 0.4 0.3 0.2 0.1 fu1(x), fu2(x), fu3(x)

Probability density function of hyperexponential distribution

Probability density function of Weibull distribution

Probability density function

of gamma distribution 0 2 4 6 8 10 x

The last statement was verified by modeling a teletrafic system of type //1 [ 3 ]. As in the previous experiment, the load change was selected in the range of 0.1 ⩽ ⩽ 0.9 . The values of errors 1 and 2 do not exceed 11%, which is quite acceptable for solving most of the practical problems. It seems appropriate that, among the alternative functions of type () , we select a function with skewness closest to a similar value obtained by measuring the parameters of the approximated distribution. This statement relies on the use of the skewness in the relation in order to evaluate the quantile of the IP packet delay time, as recommended in [ 16 ].

If the measurements do not match the approximating distribution but they have identical values (1) and , there may be significant errors in further analysis of the teletrafic models. Figure 6 shows an example of two such functions for distributions () . It should be emphasized that, while two densities are clearly diferent, they have the same values (1) and . Moreover, both distributions have the same values of the skewness coeficient, which is equal to zero due to the symmetry of functions 1 () and 2 () .

2.5 2.0

This example with functions 1 () and 2 () demonstrates a radical divergence of distributions where values (1) and are the same. For these two functions, error 1 is small. It amounts to a few percent for the given range of the model load. The situation with error 2 is diferent: the error almost reaches 100% when the model is under high load. This indicates that comparing only the mean values of random variables can yield false results. 6. Discussion of Results and Further Research Directions The proposed method of choosing distribution () is characterized by very high accuracy in evaluating the indicators of the quality of service for the multiservice trafic service presented as a set of IP packets. This method is similar to the procedure proposed in [ 21 ] for the analysis of the stochastic characteristics of models with queues. This fact also indicates that the proposed method for calculating characteristics (1) and is acceptable.

However, it should be noted that, in theory, there could be some specific models with lower accuracy in evaluating the indicators of the quality of service for the multiservice trafic. Therefore, from this perspective, additional research is necessary to solve the following three tasks.

The first task is to establish the relations between the values of errors 1 and 2 and values , or, possibly, only . The method for determining values was shown in Figure 1.

The second task is to introduce the Mahalanobis distance as a measure of the distance between functions [ 22 ]. This approach appears to be very productive because it has shown good results in studying the systems similar to the model described in this paper.

The third task is to study the aspects of how the proposed method can be applied for step functions () , with several extrema on the histogram. Changes in the packet multiservice trafic in emergencies [ 23 ] showed that sometimes several extrema are registered on the histograms that provide the basis for constructing step functions () .

References

[1] A. O. Vatulyan , Measure distances between functions , Soros Educational Journal 6 ( 2000 ) 123 - 127 .

[2] S. N. Stepanov , Teletrafic theory: concepts , models, applications, Hotline-Telecom, Moscow, 2015 .

[3] L. Kleinrock , Queueing Systems: Volume I - Theory , Wiley, New York, NY, 1975 .

[4] R. N. Vadzinsky , Handbook of probability distributions, Science, Saint-Petersburg, 2001 .

[5] A. N. Sokolov , Methods for Analyzing the IP Packet Delays in a Next-Generation Network , Ph.D. thesis , The Bonch-Bruevich Saint-Petersburg State University of Telecommunications, Saint-Petersburg, Russia, 2011 .

[6] G. Kramer , Mathematical methods of statistics, Mir, Moscow, 1975 .

[7] V. A. Ditkin , A. P. Prudnikov , Integral Transforms and Operational Calculus , Nauka, Moscow, 1974 .

[8] G. A. Korn , T. M. Korn, Mathematical Handbook for Scientists and Engineers , Dover Publications, 2013 .

[9] I. V. Bychkov , V. I. Zorkaltsev , A. V. Kazazaeva , Weight coeficients in the weighted least squares method , Siberia Journal of Computational Mathematics 18 ( 2015 ) 275 - 288 .

[10] H. W. Lilliefors , On the kolmogorov-smirnov test for normality with mean and variance unknown , Journal of the American Statistical Association 62 ( 1967 ) 399 - 402 .

[11] E. D. Bloch , Proofs and Fundamentals: A First Course in Abstract Mathematics, Springer, 2011 .

[12] 3GPP , Technical Specification Group Radio Access Network; Study on RAN Improvements for Machine-type Communications , Technical Report TR 37.868 V11.0 . 0 , 3GPP , Sophia Antipolis , 2011 .

[13] A. K. Levakov , Character of incoming ip-packet flow under emergencies, Vestnik Sviazy ( 2017 ) 4 - 7 .

[14] B. D. Cabrera , G. J. , L. W. , R. K. Mehra , On the statistical distribution of processing times in network intrusion detection , in: Proceedings of the 43rd IEEE Conference on Decision and Control , IEEE , Bahamas, 2004 , pp. 75 - 80 .

[15] M. Fukushima , T. Yakine, Performance Analysis of a Diferentiated Service Router , Kyoto University, 2001 .

[16] ITU-T , Network performance objectives for IP-based services , Recommendation Y.1541, ITU-T , Geneva , 2011 .

[17] N. A. Sokolov , Telecommunication Network Planning Tasks, Communication technology , Saint-Petersburg , 2012 .

[18] N. A. Sokolov , The aesthetic criterion application for analysis of the of telecommunication systems evolution scenarios , International Journal of Open Information Technologies 7 ( 2019 ) 48 - 52 .

[19] N. F. Bakhareva , V. N. Tarasov , Approximate methods and models of queuing. The study of computer networks , Publishing House of Samara Scientific Center of the Russian Academy of Sciences, Samara , 2011 .

[20] H. E. Hurst, Long-term storage of reservoirs: an experimental study , Transactions of the American Society of Civil Engineers 116 ( 1951 ) 770 - 799 .

[21] T. I. Aliev , Approximation of probability distributions in queueing models , Scientific and Technical Journal of Information Technologies, Mechanics and Optics ( 2013 ) 88 - 93 .

[22] G. J. McLachlan , Mahalanobis distance, Resonance ( 1999 ) 20 - 26 .

[23] A. K. Levakov , N. A. Sokolov , Three algorithms for trafic limitation in emergencies , in: Selected Papers of the IX Conference ”Information and Telecommunication Technologies and Mathematical Modeling of High-Tech Systems”, Moscow , 2019 , pp. 84 - 91 .