The problems of determining the fractal dimension of a time series obtained using a self-similar traffic generator based on Markov chains with a controlled fractal dimension are stated. Based on numerical experiments to determine the fractal dimension of the generated numerical sequences, statistically significant changes are shown at different scales. The insufficient development of high-performance algorithms and methods for generating self-similar numerical sequences for procedure of traffic simulation in telecommunication systems and networks is indicated. The directions of further research on the management of the multifractality in generators based on Markov chains are proposed.
Mathematical models of a self-similar time series are used to describe telecommunication processes. In the graphs showing the load of the computer’s network channel, self-similarity is determined by the presence of outliers, the amount of which exceeds the classical statistical theory predictions (see Fig. 1). The horizontal axis shows time in arbitrary units, and the vertical shows network load to the maximum throughput ratio.
In most cases, analytical expressions for self-similar traffic predicted QoS parameters cannot be formed, or such transformations can be formed for individual specific situations, therefore, analytical calculations are inadvisable. For this reason, to determine the main indicators of QoS, such as jitter, lateness, average number of failures and others, the simulation with self-similar traffic generators is used. This leads to reducing and simplifying the number of calculations for generators of self-similar traffic with controlled fractal properties, which would allow numerical sequences to have properties as close as possible to the properties of the telecommunication network’s real traffic, which is being studied. Given the relevance of managing the generated traffic’s fractal properties, this paper is devoted to determining the dependence of the traffic model’s fractal properties on the used scale. 2
The analysis of research and publications on the subject revealed the following. In [
Importance of multifractal analysis for information exchange processes in
computer networks is described in [
In [
In [
The results obtained in [
Subsequent works [
The main task of the paper is to analyze the properties of a binary numerical series, which is obtained using a generator based on a graph model of states and the transitions’ probability between them. Such a traffic generator is a typical Markov chains based generator (see Fig. 2). The model contains a number of states that set the initial generated value. The next value is obtained by random transitions, where 0 and 1 are the probabilities of changing the state to the next time quantum, and the probabilities 1 − 0 and 1 − 1define chance of staying in the current state. The specified generator does not use heavy-tail distributions and does not require complex calculations. Any standard verified pseudorandom number generators in the interval [0; 1) with uniform distributioncan be used. Reduced number of operations for calculation is a significant advantage for practical application in simulation modeling systems of telecommunication networks and allows saving computation time for traffic formation [27-30].
The fractal dimension of a numerical series can be described by various metrics, which can lead to getting different misleading values. Using a separate metrics on the model and real data also allows comparing their fractal properties. Therefore, for a generator model that is shown in Fig. 2, a separate numerical series metric is constructed. The coverage width is considered unitary if all consecutive values are not equal, and zero if all consecutive values are equal to 1 or 0. It is easy to obtain an analytical form for calculating the probability of encountering a zero-span segment with elements, which is equal: 1(1 − 0) + 0(1 − 1) .
Based on statistical modeling of generator’s operation, the expected value of the random walk’s magnitude with
steps is obtained, which allows determining the fractal dimension of the series analytically. Moreover, the fractal dimension depends on the resulting numerical sequence length as given by (1).
( , 0, 1) = 2 + 1(1− 0) ln(1− 0)+ 0(1− 1) ln(1− 1) 0+ 1− 1(1− 0) − 0(1− 1) (1)
For the transition probability values 0 = 1 = 0.5, which corresponds to the classical random process, a graph of the fractal dimension dependence on the generated series number of elements obtained by formula (1) is shown in Fig. 3.
The presence of different values of fractal dimension in mathematical objects at
different scaling levels is called multifractality. The presence of multifractality in the
traffic of computer networks is shown in [
The definition in Minkowski's interpretation can be used to determine the fractal
dimension [
= lim →0 − ln(ε) ln( ) (2) where – size or diameter of the subset, that is covering the set which dimension is being determined;
– the minimum number of subsets , that should be used to cover the whole set, which dimension is being determined.
It is not possible to directly apply (2) to a discrete set because a minimum ε exists. Therefore, fixed values of ε should be used.
Let coverings with sizes and
be used to cover the main set ( - for a discrete system is a given natural number; is an unknown coefficient characterizing the selected discrete system). Then, according to the selected subsets, the number of such subsets to cover is ( )and (
). The method for calculating the metric ( ) is quite arbitrary, and is selected according to the values studied in a particular process. For a discrete system, if the definition of the limit is rejected,(3) is obtained from equation (2).
− ln( ) − = ln( ( )), = ln( ) (3) where ln( ), ln( ( )) are calculated for several values of ; and are obtained as a result of applying linear regression to the points (ln( ) , ln( ( ))).
Given the randomness of the numerical series, ( )is also a random variable, with a certain expected value and dispersion.
Hence, the obtained points (ln( ) , ln( ( )))will approach the line, but not necessarily belong to it.
In order to reduce additional calculations and transformations, the process of generating “0”is changed to generate “-1”.As a result, for 0 = 1, the expected value of the generated sequence becomes 0 and the standard deviation equals 1. In addition, the created sequence { 1, 2, … , } is replaced by a cumulative series corresponding to a random walk { 1, 2, … , | = 1 + 2 + ⋯ + }. For such series, the covering width ( ) for a segment with length of discrete elements can be calculated by (4): ( ) = ∑ =0 / −1(max( ∙ +1 … ∙( +1)) − min( ∙ +1 … ∙( +1))) (4)
We propose using the power of two as , because then can also be doubled when constructing reference points for linear approximation. The indicated process for = 8,16,32,64,128 made it possible to construct five points for which a linear approximation determines the Hurst exponent of the test sequence at 0.53 as the inclination angle of the straight line (see Fig. 4): and probabilities to change state 0 = 1 = 0.5.
Theoretical calculations for a random sequence shows that the values should be = 0.5with
= 1.5. This is close to the obtained results.
Classical theory states that for curves on the plane the covering width ( ) should be expressed by the number of squares with sidesize equals , which cover the whole random walk curve. However, the adopted measure (4) is asymptotically equal to the Minkowski–Bouligand dimension. Moreover, with the same values being chosen for , the Hurst exponent matches with the one obtained using R/S analysis, for which the relation to the fractal dimension is already known. 5
Impact analysis of scale selection to the fractal dimension For the purpose of experimental confirmation eleven generated sequences containing 1024 samples (“-1” and “1”, as described in previous paragraph) were used to show the dependence of the numerical series’ fractal dimension on the selected scale. For each of those, the
Hurst exponent was calculated forsets of of these experiments are shown in Tables 1-3.
An independent measurement of the Hurst exponent on an appropriate scale is formed for each of the generation modes, which allows evaluating the statistical processing of the result. The mean of the Hurst exponent and the standard deviation of that mean, which is inversely proportional to the root of the sample length, are found for that result. Based on the standard deviation, a confidence interval of 99% reliability is calculated, which is provided for deviations from the mean ±3 . The boundaries of the calculated reliability interval are respectively shown in the table columns −3 and +3 .
The results from all three tables indicate a change in the Hurst exponent while shifting the scale, which confirms the assumption made in the previous paragraph based on the analytical formula (1) for a simplified metric for calculating fractal dimension. Table 1 shows that, with a high probability of changing the previous state value to the opposite, traffic modulation occurs almost constantly, which leads to a significantly lower probability of outliers. This is reflected in the Hurst exponent values, which differs from 0.37 to 0.41 for various scales. Fig. 5 shows the signal generated with such parameters.
As a result of random walk based on the obtained sequence, the distance from the beginning of the movement will change much slower, because for each step to the side there will be a significantly higher probability of getting the opposite direction in the next time quantum.
The following Table 2 contains results of a numerical experiment with the generator being set to keep or change the current state with an equal probability 0 = 1 = 0.50. In this mode the generator must correspond to the classical random process with the Hurst exponent = 0.5. It is noted from Table 2 that four times change of the parameter gives estimated values of the Hurst exponent with a reliability of 99%. Which is equal to the numerical series on 1024 samples giving lower values for the Hurst exponent than on 256 samples with a reliability of 99%. This indicates the difference in the fractal properties of the numerical sequence at different scales. Using the fact, the appropriate queue length of the service system for which the Hurst exponent will have a value close to 0.5can be chosen and the theory of random Poisson flow can be used without taking into account self-similarity using classical statistics to determine the characteristics of such a service system.
Fig. 6 shows a fragment of the obtained sequence with the generation parameters 0 = 1 = 0.50.
The results of the last experiment with the state change probabilities 0 = 1 = 0.05are shown in Table 3. From the obtained results, it can be concluded that the numerical series has low probability of changing the trends. The numerical sequence is persistent and is able to store trends for some time. However, at the same time, the observed mean value of the Hurst exponent is close to = 0.5 at intervals of 1024 samples. This means that at large distance, the range of the cumulative series does not differ from the classical random sequence, where the difference between the maximum and minimum values increases on average in proportion to the root of the number of steps taken.
At short distances, the Hurst exponent is very different, and reaches mean value of = 0.8. In accordance with this, there is a scale for which self-similar traffic, as in the previous case, will have the properties of a classical random process. A fragment of the obtained signal is shown in Fig. 7.
This paper presented self-similar traffic generators using Markov chains, which differ from their analogues in lower computational power requirements for simulation systems, which makes it possible to increase the performance of information movement modeling in telecommunication systems and computer networks. Further development and study of such systems is relevant.
Based on the simplified metric ( ), an analytical expression is formed for calculating the fractal dimension of the generated binary numerical series based on the Markov chain. The dependence of the fractal dimension on the length of the interval on which it is calculated is noted and the assumption is made that the multifractality properties are repeated on classical metrics, such as numerical dimensions based on R/S analysis or Minkowski-Bouligand dimension.
In order to verify the assumption, an experiment part was carried out which confirmed the assumption of a multifractal numerical sequence obtained by generators on Markov chains with a reliability over than 99%.
Potential future work includes developing methods for controlling multifractality parameters, or opposite task of eliminating the appearance of multifractality.
18. G.A. Kuchuk, O.O. Mozhayev, and O.V. Vorobeyov. Analiz samopodіbnogo traffic. Aerospace and technology. No. 9, p. 173–180, 2006. http: //nbuv.gov.ua/UJRN/aktit_2006_9_35 19. Smirnov A.A., Kuznetsov A.A., Danilenko D.A., Berezovsky A., The statistical analysis of a network traffic for the intrusion detection and prevention systems, Telecommunications and Radio Engineering, Vol 74, Issue 1, Begel House Inc, 2015, pp. 61-78. 20. Smirnov, O., Kuznetsov, A., Kiian, A., Zamula, A., Rudenko, S., Hryhorenko, V., Variance Analysis of Networks Traffic for Intrusion Detection in Smart Grids, 2019 IEEE 6th International Conference On Energy Smart Systems (2019 IEEE ESS), Kyiv, Ukraine April 17-19, 2019, pp. 353-358. 21. Smirnov, O., Kuznetsov, A., Kavun, S., Babenko, B., Nakisko, O., Kuznetsova, K., Malware Correlation Monitoring in Computer Networks of Promising Smart Grids, 2019 IEEE 6th International Conference On Energy Smart Systems (2019 IEEE ESS), Kyiv, Ukraine April 17-19, 2019, pp. 347-352 22. A.A. Kovalenko, G.A. Kuchuk and A.A. Mozhaev. Construction of exponential time scales in the analysis of multiservice network queues. Radio and Computer Systems. No. 7, p. 257–262, 2010, http://nbuv.gov.ua/UJRN/recs_2010_7_52 23. E.V. Dobrovolsky and O.L Nechyporuk, Modeling of Network Traffic Using Context
Methods, Scientific Papers ONAS them. O.S. Popova, No. 1, pp.24-32, 2005. 24. Odarchenko R., Abakumova A., Polihenko O., Gnatyuk S. Traffic offload improved method for 4G/5G mobile network operator, Proceedings of 14th International Conference on Advanced Trends in Radioelectronics, Telecommunications and Computer Engineering (TCSET-2018), pp. 1051-1054, 2018. 25. M. Zaliskyi, R. Odarchenko, S. Gnatyuk, Yu. Petrova. A.Chaplits, Method of traffic monitoring for DDoS attacks detection in e-health systems and networks. CEUR Workshop Proceedings, Vol. 2255, pp. 193-204, 2018. 26. Al-Azzeh J.S., Al Hadidi M., Odarchenko R., Gnatyuk S., Shevchuk Z., Hu Z. Analysis of self-similar traffic models in computer networks, International Review on Modelling and Simulations, № 10(5), pp. 328-336, 2017. 27. Fedushko S., Benova E. Semantic analysis for information and communication threats detection of online service users. The 10th International Conference on Emerging Ubiquitous Systems and Pervasive Networks (EUSPN 2019) November 4-7, 2019, Coimbra, Portugal. Procedia Computer Science, Volume 160, 2019, Pages 254259. https://doi.org/10.1016/j.procs.2019.09.465 28. Fedushko S., Davidekova M. Analytical service for processing behavioral, psychological and communicative features in the online communication. The International Workshop on Digitalization and Servitization within Factory-Free Economy (D&SwFFE 2019) November 4-7, 2019, Coimbra, Portugal. Procedia Computer Science. Volume 160, 2019, Pages 509-514. https://doi.org/10.1016/j.procs.2019.11.056 29. Fedushko S., Trach O., Kunch Z., Turchyn Y., Yarka U. Modelling the Behavior Classification of Social News Aggregations Users. CEUR Workshop Proceedings. 2019. Vol 2392: Proceedings of the 1st International Workshop on Control, Optimisation and Analytical Processing of Social Networks (COAPSN-2019). p. 95–110. http://ceur-ws.org/Vol2392/paper8.pdf 30. Fedushko S., Ustyianovych T. (2020) Predicting Pupil’s Successfulness Factors Using Machine Learning Algorithms and Mathematical Modelling Methods. In: Hu Z., Petoukhov S., Dychka I., He M. (eds) Advances in Computer Science for Engineering and Education II. ICCSEEA 2019. Advances in Intelligent Systems and Computing, vol 938. Springer, Cham. pp 625-636. DOI 10.1007/978-3-030-16621-2_58