Xi'an Technological University
Subject: Computer Science, Software Engineering
eISSN: 2470-8038
SEARCH WITHIN CONTENT
Li Jie ^{*} / Lu Ying ^{*} / Tang Junyong ^{*}
Keywords : Self-similarity, Traffic Flow, FGN, R/S
Citation Information : International Journal of Advanced Network, Monitoring and Controls. Volume 3, Issue 2, Pages 66-70, DOI: https://doi.org/10.21307/ijanmc-2018-043
License : (CC-BY-NC-ND-4.0)
Published Online: 07-May-2018
The conventional network traffic flow models are mostly based on Poisson model. With the continuous development of network services, studies found that the actual network traffic has a long-range dependence (LRD) now and in a very long time, which is a kind of self-similarity. In this paper, RMD and Fourier algorithm were adopted to simulate and analyze a self-similar model of FGN. They generated the necessary sequence of self-similar traffic. Then the article uses R/S method to verify H value of the generated sequence of self-similar traffic in order to verify the self-similarity of the self-similar traffic sequence. The existence of self-similarity is verified by experiments, and the advantage and disadvantage of RMD and Fourier algorithm are analyzed.
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.
A statistical process of stable covariance is investigated X={Xt:t=0,1,2,3...}, the mathematical expectation of the process is that μ=E[X_{t}] is constant, the variance σ^{2}=E[(X_{t}-μ)^{2}] is a finite value, the auto correlation function r(k)=E[(X_{t}-μ)(X_{t+k}-μ)]/σ^{2}, k=1,2,3,…, it’s only related to k. X_{t} 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 $${X}^{(\text{m})}=\left\{{X}^{\text{m}}{}_{t}:t=0,1,2,3,\dots \right\}$$ represents a new sequence. $${X}^{\text{m}}{}_{k}=1/m({X}_{\text{km-m+1}}+\dots +{X}_{\text{km}})$$, 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.
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.
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.
1) 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....2^{m}));
2) The original sequence is weighted, and the weighted coefficient is $${\theta}_{i}=\sqrt{\begin{array}{c}(1-{2}^{2H-2})\\ {2}^{2{H}_{i}}\end{array}}$$, background sequence is D(i)=G(n)θ i(i is the number of iterations);
3) The number of iterations is m, generates foreground sequence X=X(n)(n=1,2,3,....2^{m}), Let X = 0(0), X (2 m) = G (1)
When j=1:
When j!=1:
this is j=1, 3, 5,......2^{i}-1
4) 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 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]:
1) 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 $$\sqrt{f}$$.
2) Hybridization {f_{1}}, a separate exponential random variable with a mean of 1 times each {f_{i}}, gets the sequence $$\left\{{f}_{i}^{\text{'}}\right\}$$.
3) Construct a sequence {z_{1},}. Take the complex sequence {z_{1},z_{2},…z_{n/2}}, among $$\left|{z}_{i}\right|={(f{\text{'}}_{i})}^{1/2}$$, the phase of z_{i} is randomly distributed between 0∼2π.
4) Solving the complex sequence $$\left\{{\text{z}}^{\text{'}}{}_{1},{\text{z}}^{\text{'}}{}_{2},\cdots ,{\text{z}}^{\text{'}}{}_{n/2}\right\}$$,
5) The inverse Fourier transform of $$\left\{z{\text{'}}_{j}\right\}$$ is obtained, and the approximate sample point {x_{i}} 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, a_{k}=2kπ+ω, b_{k}=2kπ-ω
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.
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 = {X_{1}, X_{2}, X_{3},…,X_{L}}, calculate the partial sum $$X=\{{X}_{1},{X}_{2},{X}_{X3},\dots ,{X}_{L}\}$$ and variance of the sequence S(n). Then calculate R/S method statistics:
It is known by statistical properties, $$\frac{R}{S}(n)\approx c{n}^{H}$$. We can do the logarithm of both sides: $$\mathrm{log}\frac{R}{S}(n)\approx \mathrm{log}c+H\mathrm{log}n\u2019$$, among, log c is a constant. $$\mathrm{log}\frac{R}{S}(n)$$ 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.
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′
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.
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.