The main reason leading to a buffer overflow is the presence of a long-term dependence in network traffic due to its self-similarity, as a result of which the total cumulative effect in a wide range of delays can significantly differ from that observed in a short-term dependent process [1]. To eliminate self-similarity of network traffic, various models and traffic transformation devices are used, one of which is the asynchronous simulation model described in [2][3][4], for which there is a software implementation [5].
An important indicator of the operation of this model is the queue size used in the traffic transformation process. Since, due to limited computer resources, the queue cannot have an infinite size, the problem arises of predicting the queue size depending on the measure of self-similarity of the input traffic, which is the Hurst exponent.
The solution to the problem of finding the optimal buffer size for a given value of the Hurst exponent H can be found using the methods of regression analysis, based on simulation data obtained using the developed software [5].
Since machine learning includes many methods, at the initial stage, for further comparison with more complex models built, in particular, using deep learning methods, it is advisable to consider only methods of pairwise regression analysis, isotonic regression and support vector machines.
Let us involve a quality metric (penalty), which is a complex score and considers both packet loss during traffic transformation and inefficient use of buffer space.
Next, we choose the best model for predicting the queue size, depending on the Hurst exponent of the input flow, using the following quality metrics: coefficient of determination; root mean square error of regression; mean absolute error; penalty score value.
When setting the problem, special attention should be paid to testing the resulting models. In this case, the classical approach, which consists in dividing the entire data set into training and test samples, is not acceptable. Since on the test sample we will get the estimated number of lost packets and, therefore, the estimated penalty based on the difference between the predicted and actual buffer sizes, the obtained models must be tested by simulating traffic transformation with a queue size limitation, based on the results of applying the tested model for determining the size of the queue to the sequence being converted. This task is not trivial and will not be discussed in this article.
The simulation model presented in [2] provides transformation of the input flow of packets, which is obviously self-similar, into a given distribution law, in particular, into an exponential one. The object of transformation is a one-dimensional distribution density of time intervals between packets of the input flow. Using the developed model, 11,000 tests were carried out and data were obtained for statistical analysis.
Since the amount of losses in the general case does not give any information about the efficiency of using the queue in the process of the transformation traffic, to assess the quality of the resulting model, we introduce a quality metric -the penalty score, which takes into account not only the amount of losses, but also not rational use of buffer memory.
Let define i y as the true value of the queue size in the sample, ˆi y is the predicted value of the queue size in the sample corresponding to the true value i y . If îi yy , we will penalize the learning system by îi yy . If îi yy , the amount of the penalty will depend on the value of the difference
with i the amount of the penalty will be i and 0 -otherwise. Let us illustrate this with an example (Figure 1). In the second case 2 ŷy and the penalty is 0, it is assumed that ŷ is the preferred queue size for 2 y . In the third case 3 ŷ y , the amount of the penalty is determined from the expression
Thus, the amount of the penalty score will be determined from the equation:
The total penalty for all trials is determined as the arithmetic mean between the penalties for each trial:
where n is the number of tests. In the process of training the model, it is necessary to ensure the minimum value of the penalty for all tests, in other words min p . The presented system of penalties provides for the introduction of three hyperparameters: , and , where 0
and 0 . Let's set the hyperparameter values as follows:
.
Figure 2 shows a scatter plot of queue size in dependence of Hurst exponent. The figure clearly shows that there is a certain correlation between the Hurst exponent and the buffer size [4].
Let us first group the tests by the value of the Hurst exponent and then select 30 groups to estimate the spread of the queue size. Next, we can build a box-plot for each group. It follows from Figure 3 that the largest amount of outliers from above is observed for the first 10 groups, which corresponds to the Hurst exponent value close to 0.5. Consequently, at these values of the Hurst exponent, losses may occur due to the fact that the required buffer size will be greater than the predicted one.
For groups from 28 to 30, there are significant outliers from the bottom, which leads to inefficient use of buffer memory.
Machine learning is a subset of artificial intelligence that studies and explores algorithms that can learn without direct programming. Linear regression is a typical representative of machine learning algorithms [7].
There are the following tasks solved by machine learning: supervised learning, unsupervised learning, reinforcement learning, active learning, knowledge transfer, etc. Regression (as well as classification) belongs to the class of supervised learning problems, when a certain target variable must be predicted for a given set of features of the observed object. As a rule, in supervised learning problems, experience E is represented as a set of pairs of features and target variables:
. In the case of linear regression, the feature description of an object is a real vector m xR , where R is the set of real numbers and the target variable is a scalar yR . The simplest measure of the quality L for the regression problem is
where ŷ is an estimate of the real value of the target variable [7,8].
Let us restore the dependence shown in Figure 2 using the methods of regression analysis. The basis of regression analysis is the method of least squares (OLS), according to which the function y f x is taken as the regression equation such that the sum of the squares of the differences would satisfy
Using the methods of pairwise regression analysis, we will carry out a statistical analysis of the data obtained by transforming an input self-similar flow distributed according to the Pareto law into a flow having an exponential distribution. Let us examine the methods widely used in practice, which allow finding the buffer size for the input flow with a given Hurst exponent.
In this case, the relationship between the Hurst exponent H and queue size ŷ is determined according to the linear equation: (1) The result of the fitting for the current model is shown on Figure 4. Thus we obtained the statistically significant result. In Table 1 the quality metrics values are shown for the obtained linear regression model. The obtained value of the coefficient of determination suggests that only about 58% of cases of changes in the Hurst exponent lead to a change in the size of the queue within the framework of the linear model. The obtained result is unsatisfactory for practice, therefore, in the simplest case, it makes sense to consider other methods using the methods of linearization of nonlinear dependencies. As a result, the nonlinear dependence can be reduced to linear, and then, the least squares method can be used.
For the hyperbolic regression, the relationship between H and ŷ can be described as follows: We obtain the regression equation using the least squares method:
The result of the fitting for the current model is shown on Figure 5.
The first hyperbolic model report is built using the statsmodels package of the Python programming language
Thereby, we obtained the statistically significant result. In Table 2 the quality metrics values are shown for the obtained first hyperbolic regression model. The obtained value of the coefficient of determination suggests that about 45% of cases of changes in the Hurst exponent lead to a change in the size of the queue. This is much worse than the value of the coefficient of determination of the linear model. For this reason, it makes sense to consider a different hyperbolic regression model: The result of the fitting for the current model is shown on Figure 6.
The second hyperbolic model report is built using statsmodels package of the Python programming language Accordingly we obtained the statistically significant result. In Table 3 the quality metrics values are shown for the obtained second hyperbolic regression model. The obtained value of the coefficient of determination is about 59%, which is slightly better than the linear model.
In the case of the power regression, the relationship between H and ŷ is: The exponential function is internally linear, therefore, estimates of the unknown parameters of its linearized form can be calculated using the classical least squares method. The regression equation is:
(4) The result of the fitting for the current model is shown on Figure 7.
The power model report is built using statsmodels package of the Python programming language Thus we obtained the statistically significant result. In Table 4 the quality metrics values are shown for the obtained power regression model.
The obtained value of the coefficient of determination is 70%, which is much better than the coefficient of determination of the linear model.
For the exponential regression, the relationship between H and ŷ is: , In this way we obtained the statistically significant result. In Table 4 the quality metrics values are shown for the obtained exponential regression model. The obtained value of the coefficient of determination indicates that about 74% of cases of changes in the Hurst exponent lead to a change in the size of the queue in the framework of the exponential model, which is the best result when using the methods of paired regression analysis. An analysis of the amount of the penalty gives the same result.
Let us carry out a comparative analysis of the results obtained and then build graphs of the regression equations (1-5) (Figure 9). It is obvious that exponential regression most closely fits the relationship between the Hurst exponent and the buffer size.
The trivial paired regression models described above do not adequately describe the dependence of the queue size on the Hurst exponent, so we complicate the model. One possible way is the isotonic regression usage.
In statistics, isotonic regression or monotonic regression is a method of fitting a free-form line to a sequence of observations under the following constraints: the fitted free-form line should be non-decreasing (or not increasing) over the domain, and should lie as close as possible to the observations [13]. In the process of constructing an isotonic curve, the following problem is solved [13]:
where the value of the weighting factor is 0 i w . This gives a vector that consists of the non-decreasing elements that are closest in terms of the root mean square error. In practice, this list of elements forms a piecewise linear function.
Let us train the isotonic regression model using the scikit-learn package of the Python 3 programming language [9] and build a graph corresponding to the model built using isotonic regression (Figure 10)
In Table 6 the quality metrics values are shown for the obtained isotonic regression model. The obtained value of the coefficient of determination suggests that about 92% of cases of changes in the Hurst exponent lead to a change in the size of the queue within the framework of this model, which is much better than the models built on the basis of pair regression methods. Moreover, the value of the penalty for isotonic regression is two times less than the corresponding value for paired regression.
Support Vector Machines (SVM) is a linear algorithm used in classification and regression problems (for regression problems it is called SVR -Support Vector Regression). The main idea of the method is to construct a hyperplane that separates the sampled objects in an optimal way [10][11][12].
Support vector machines maximize the padding of objects, which is closely related to minimizing the likelihood of overfitting. Moreover, it makes it very easy to go to the construction of a nonlinear dividing surface due to the nuclear transition [10,119].
Let us train the model based on SVR. The nonlinear nature of the relationship between the Hurst exponent value and the queue size indicates the need to choose a radial basis kernel for the SVR model. This model was trained using the scikit-learn package of the Python 3 programming language [12]. In Figure 11 the graph of the relationship between queue size and Hurst exponent is shown. In Table 7 the quality metrics values are shown for the obtained support vector regression model. The obtained value of the coefficient of determination is about 90%, which is slightly worse than that of the method using isotonic regression. However, the penalty for this method is less than for isotonic regression.
The research results are presented in Table 8 for estimating and choosing the best method for predicting queue size from the Hurst exponent.
Based on the data of the pivot table, it can be concluded that the best predictive ability based on the introduced quality metric is a model built using the support vector machine. Within the framework of this study, it can be concluded that the complication of SVR by transition to the rectifying space does not lead to an improvement in the quality of learning.
Thus, we investigated seven models that allow to predict the size of the queue when transforming an input flow with a Pareto distribution into an output flow with an exponential distribution depending on the Hurst exponent of the input flow, built on the basis of regression analysis methods.
The unacceptability of the classical approach, which consists in dividing the entire dataset into training and test samples, is shown. Since, within the framework of the set task, the obtained models must be tested by simulation modeling of traffic transformation with a limit on the queue size, based on the results of applying the tested model for determining the queue size to the sequence being converted.
Since the amount of losses in the general case does not give any information about the efficiency of using the queue in the process of converting traffic, to assess the quality of the resulting model, a penalty was introduced that takes into account not only the amount of losses, but also not rational use of buffer memory.
The best for the selected quality metrics are the isotonic regression and the support vector regression. It managed to to reduce the penalty score for these models by more than two times in comparison with the trivial linear model. The use of these models will make it possible to more efficiently use the buffer space of the RAM of telecommunication network switching nodes. The usage of these models will make it possible to more efficiently use the buffer space of the RAM in telecommunication network switching nodes. Nevertheless, the obtained models do not belong to strong machine learning models, therefore, the additional researches are required using decision trees ensembles and neural networks.