This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
INTRODUCTION
The study of network traffic flow plays an important role in improving network structure, improving network performance and improving network security. The traditional business model is based on the poisson process, which is a short-range correlation model. In the 1990 s, Leland and others in the literature[1]for the first time explicitly put forward the network traffic with self-similarity, and proves that the self-similarity of network traffic flowis network business data flow within a long time both have a long self-similarity. After that, the researchers observed and analyzed some existing networks, and found that no matter how the network topology, number of users and service types changed, this self-similarity always exist. Based on FBM model, the simulation generation experiment of flow sequence was carried out using RMD and Fourier transform method respectively, and the self-similar sequences generated by R/S algorithm were used to verify and analyze the results.
DEFINITION OF THE SELF-SIMILAR PROCESS OF NETWORK TRAFFIC
A statistical process of stable covariance is investigated X={Xt:t=0,1,2,3...}, the mathematical expectation of the process is that μ=E[Xt] is constant, the variance σ2=E[(Xt-μ)2] is a finite value, the auto correlation function r(k)=E[(Xt-μ)(Xt+k-μ)]/σ2, k=1,2,3,…, it’s only related to k. Xt can be understood as the number of network business entities that arrive in t unit time. It is assumed that the autocorrelation function of X has the following form[2]:
For each m =1,2,3,…, make represents a new sequence. , k=1,2,3,… stands for the aggregation of length m. If X(m) also defines a generalized stationary random process, r(m)(k) represents the auto correlation function of X(m). If for all m, there are:
When k→∞, X is the exact second order self-similar process, and it is said that H=1-β/2 is its self-similar parameter.
FBM FLOW MODEL AND SIMULATION MODELING
In the network modeling of traffic flow, the parameters of use less as far as possible to the actual requirements of the network traffic modeling, another is required to produce synthetic data sequence to show similar features and measurement data. In the modeling of network traffic flow, it is required to model the traffic flow of the actual network with as few parameters as possible. In addition, the required synthetic data sequences are required to display similar characteristics to the measured data. The fractal Brownian motion FBM is a kind of convenient traffic model. The model is based on the Fractal Gaussian Noise(FGN) process, which is an incremental process ofFGN[3].
In the simulation experiment, the FBM model is modeled and studied by the random mid-point method and the discrete Fourier transform method, which results in thetraffic flow of the Fractal Gaussian Noise. Moreover, the network traffic sequences generated by different algorithms are compared, and their performance is analyzed. The network traffic sequences generated by different algorithms are compared for different self-similarity coefficients, and then analyze their performance.
Random Mid-Point Method
The random mid-point method (RMD method) is used to generate simulation sequences by gradual subdivision method. The greatest advantage of this method is its rapidity. Algorithm principle: Firstly, itdivides the time interval [0,T], and then calculates the arithmetic mean of the left and right points, iterates to get the midpoint value and addsan offset. Based on matlab simulation platform, RMD algorithm steps are written as follows [4,5] :
The original business flow data is performed by the weighted iteration of the pseudo-random sequence (by mathematical algorithm, the random number is calculated according to the law of random number). The foreground sequence is generated, performance analysis is performed on the foreground sequence, and the model parameters are constantly adjusted so that the performance of the foreground sequence matches the original sequence, and finally the practical RMD model is formed.
In matlab, randn() in M language is used to generate a pseudo-random sequence with mean value of 0 and variance of 1 as the original sequence(G=G(n)(n=1,2,3....2m));
The original sequence is weighted, and the weighted coefficient is , background sequence is D(i)=G(n)θ i(i is the number of iterations);
The number of iterations is m, generates foreground sequence X=X(n)(n=1,2,3,....2m), Let X = 0(0), X (2 m) = G (1)
When j=1:
When j!=1:
this is j=1, 3, 5,......2i-1
The foreground sequence after iteration is difficult to analyze mathematically, and let’s do the cosine of it, SY=cos(X), The resulting sequence is finally obtained-SY(n)(n=1,2,3,...2m).
Fourier Transform Method
Fourier transform method is to obtain the business data by Fourier transform of the spectrum of Fractal Gssian-Noise, which has high accuracy. The basic idea is to produce a spectrum, and then fast Fourier inversion for this spectrum.
Based on matlab simulation platform, the steps of fast Fourier inversion conversion are as follows [6]:
Tectonic sequence {f1,f2,…fn/2}, fi=f(2πj/n, H) in it, The power spectrum of the FGN process from 2π/n to π is respectively corresponding to the corresponding frequency. The amplitude of the frequency domain sample of the self-similar sequence is .
Hybridization {f1}, a separate exponential random variable with a mean of 1 times each {fi}, gets the sequence .
Construct a sequence {z1,}. Take the complex sequence {z1,z2,…zn/2}, among , the phase of zi is randomly distributed between 0∼2π.
Solving the complex sequence ,
The inverse Fourier transform of is obtained, and the approximate sample point {xi} of FGN is obtained. The focus of this method is the calculation of spectrum. That is to say the power spectrum[5] of FGN process is:
In the formula, 0<H<1,-π<ω<π
The main difficulty in calculating power spectrum is the infinite sum. Now precise formula hasn’t been found, and an approximate formula is used instead.
In the formula, d=-2H-1, g=-2H, ak=2kπ+ω, bk=2kπ-ω
EXPERIMENT AND ANALYSIS OF SELF-SIMILAR SEQUENCES
The Generation of Self-similar Sequence
When using MATLAB simulation., RMD algorithm and Fourier transform method were used respectively. The self-similar sequence with a similar parameter of 0.7, 0.8 and 0.9 was set, and the sequence length was 8192. FIG. 1(a) is the result of RMD algorithm when H=0.9, and (b) is the result of Fourier transform method when H=0.9.
Figure 1.
Self-similar Sequence Generated by RMD Algorithm and Fourier Algorithm
The Common Parameter Estimation Method in the Process of Self-similarity
In this paper, R/S method and variance time curve method are used to test the self-similarity of generation sequences. For self-similar time series X = {X1, X2, X3,…,XL}, calculate the partial sum and variance of the sequence S(n). Then calculate R/S method statistics:
It is known by statistical properties, . We can do the logarithm of both sides: , among, log c is a constant. is the vertical axis, log n is the horizontal axis curve fitting, Because the curves of the two curves are linear, the curves can be fitted with straight lines. And then the slope of the line is an estimate of the hurst exponent.
Self-similarity Detection of Generating Sequence
For the random sequences generated by RMD algorithm, this paper uses the R/S method to estimate the Hurst parameters. In the RMDS algorithm, when H=0.7, 0.8 and 0.9, the self-similar parameter H value of the sequence is detected. As shown in fig. 2, two dotted lines in the scatter plot generated by the test results show a line with a slope of 1 and a slope of 0.5. There are many scattered points in the graph which can be obtained by linear fitting. The slope of the line is the hurst parameter, whose value is between 0.5 and 1, and the specific data is shown in table 1. H specifies the theoretical value for the algorithm, and H’ is the detection of H value. In order to better verify the matching degree of the estimated value and the theoretical value, the relative error can be used to represent. This: Fourier Algorithm ΔH = (H′−H)/H′
Figure 2.
Scattersof three sample sequence generated by R/S detected algorithm
TABLE I.
TEST RESULTS OF SELFSIMILAR SEQUENCE GENERATED BY R/S ALGORITHM (RMD ALGORITHM)
It can be seen from table I and table II that the obtained value is basically matching with the theoretical value of the original self-similar flow, and its relative error is small, thus proving the correctness of the simulation algorithm. The self-similar sequences generated by RMD and Fourier transform are compared. We can see that: The RMD algorithm has no complicated functions to participate in the calculation, the calculation process is clear, the speed is fast, and the self-similar sequence can be generated quickly, but the accuracy of the generation sequence of Fourier transform method is relatively high. The RMD algorithm and Fourier transform method can directly select the variable values that can affect the self-similar characteristics of the generation sequence; However, the RMD algorithm generates the sample data sequence through the continuous segmentation interval, and the generated sequence is within two endpoints. Therefore, it is important to choose which endpoint is the endpoint of the initial segmentation, which has an influence on the self-similar characteristics of the resulting data sequence, which will bring instability to the later self-similarity parameter estimation.
TABLE II.
TEST RESULTS OF SELF-SIMILAR SEQUENCE GENERATED BY R/S ALGORITHM (FOURIER ALGORITHM)
CONCLUSION
The self-similarity of network traffic determines the behavior characteristics of the network, and only self-similar modeling can accurately describe the actual situation of the network. Based on FBM model, the flow sequence is generated by RMD and Fourier transform method respectively. This experiment shows that the simulation algorithm is effective.
