Simulation of Self-similarFlowBased on Fractal Gaussian Noise Method

Publications

Share / Export Citation / Email / Print / Text size:

International Journal of Advanced Network, Monitoring and Controls

Xi'an Technological University

Subject: Computer Science, Software Engineering

GET ALERTS

eISSN: 2470-8038

DESCRIPTION

9
Reader(s)
14
Visit(s)
0
Comment(s)
0
Share(s)

SEARCH WITHIN CONTENT

FIND ARTICLE

Volume / Issue / page

Related articles

VOLUME 3 , ISSUE 2 (May 2018) > List of articles

Simulation of Self-similarFlowBased on Fractal Gaussian Noise Method

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

ARTICLE

ABSTRACT

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.

Graphical ABSTRACT

I. 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.

II. 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]:

(1)
r(k)kβ,0<β<1,k

For each m =1,2,3,…, make X(m)={Xmt:t=0,1,2,3,} represents a new sequence. Xmk=1/m(Xkm-m+1++Xkm), 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:

(2)
r(m)(k)=r(k)kβ,0<β<1

When k→∞, X is the exact second order self-similar process, and it is said that H=1-β/2 is its self-similar parameter.

III. 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.

A. 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.

  • 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....2m));

  • 2) The original sequence is weighted, and the weighted coefficient is θi=(122H2)22Hi, 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,....2m), Let X = 0(0), X (2 m) = G (1)

    When j=1:

    X(j*2mi)=X(2m+1i)/2+G(2m+1i)(122H2)22Hi

    When j!=1:

    X(j*2mi)=(X((j1)*2mi)X((j+1)2mi))/2+G(2m+1i+(j+1)/2)

    this is j=1, 3, 5,......2i-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).

B. 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]:

  • 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 f.

  • 2) Hybridization {f1}, a separate exponential random variable with a mean of 1 times each {fi}, gets the sequence {fi'}.

  • 3) Construct a sequence {z1,}. Take the complex sequence {z1,z2,…zn/2}, among |zi|=(f'i)1/2, the phase of zi is randomly distributed between 0∼2π.

  • 4) Solving the complex sequence {z'1,z'2,,z'n/2},

    z'j=0,j=0z'j=zj,0<jn/2z'j=z¯nj,0<jn/2z¯njis the complex conjugate of znj.

  • 5) The inverse Fourier transform of {z'j} 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:

    f(ω,H)=A(ω,H)[|ω|2H1+B(ω,H)]

    In the formula, 0<H<1,-π<ω<π

    A(ω,H)=2sin(πH)Γ(2H+1)(1-cosω)B(ω,H)=[(2πj+ω)]2H-1+(2πj-ω)2H1]jj=1,2,,

    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.

    B(ω,H)B3(ω,H)=ad1+bd1+ad2+bd2+ad3+bd3+(ag3+bg3+ag4+bg4)/8πH

    In the formula, d=-2H-1, g=-2H, ak=2+ω, bk=2-ω

IV. EXPERIMENT AND ANALYSIS OF SELF-SIMILAR SEQUENCES

A. 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

10.21307_ijanmc-2018-043-f001.jpg

B. 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 X={X1,X2,XX3,,XL} and variance of the sequence S(n). Then calculate R/S method statistics:

(3)
RS(n)=1S(n)[max0tn(Y(t)tnY(n))min0tn(Y(t)tnY(n))]

It is known by statistical properties, RS(n)cnH. We can do the logarithm of both sides: logRS(n)logc+Hlogn, among, log c is a constant. logRS(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.

C. 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

10.21307_ijanmc-2018-043-f002.jpg
TABLE I.

TEST RESULTS OF SELFSIMILAR SEQUENCE GENERATED BY R/S ALGORITHM (RMD ALGORITHM)

10.21307_ijanmc-2018-043-tbl1.jpg

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)

10.21307_ijanmc-2018-043-tbl2.jpg

V. 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.

ACKNOWLEDGMENT

This research is supported by the project found of National-Local joint Engineering Laboratory of Advance Network and Monitoring Control (Grant No. GSYSJ2016015).

This research is supported by the Pre Research Management Center (Grant No. 41402020202).

References


  1. Leland W E, Aqqu M S, Willinger W, et al. On theself-similar nature of Ethernet traffic (extended version)[J]. IEEE/ACM Transactions on Networking, 1994, (1), P:1-15.
    [CROSSREF]
  2. Lee YH, Kassam SA. Generalized median filtering and related nonlinear filtering techniques[J]. IEEE Transactions on Acoustica, Speech, Signal Processing, 1985, 33(3):672-683.
    [CROSSREF]
  3. Mandelbort B B, Van Ness J. Fractional Brownian motions, factional noises and applications[J]. 1968, 10(4):422-437.
  4. Zhu Xiao-Wen, Tan Xian-Hai, Chen Baixiu. Research on modeling of network traffic based on (MK)-FBM[J]. Railway Computer Application, 2009, 18(6): 10-13.
  5. Li Lin-Feng Qiu Zheng-Ding. An Iterative Method to Estimate Hurst Index of Self-similar Network Traffic[J]. Journal of Electronics& Information Technology. 2006, 28(12):136-158.
  6. Xu Mingwei, Tong Aijun. Network performance testing based on self-similar modeling[J]. Computer Engineering and Applications, 2002, 38(5): 56-59.
  7. Fu Lei-Yang, Wang Ruchuan, Wang Haiyan, et al. Implementation and application of computing self-similar parameter by R/S approach to analyze network traffic[J]. Transactions of Nanjing University of Aeronautics & Astronautics, 2007, 39(3): 358-362.
  8. Wang Xin. Modeling and prediction of self-similar network traffic [D]. Beijing: THU, 2003.
  9. Wang Xifeng, Gao Ling, Zhang Xiaoluan. Analysis and research on self-similar network traffic forecast[J]. Computer Technology and Development, 2007, 17(11): 42-45.
XML PDF Share

FIGURES & TABLES

Figure 1.

Self-similar Sequence Generated by RMD Algorithm and Fourier Algorithm

Full Size   |   Slide (.pptx)

Figure 2.

Scattersof three sample sequence generated by R/S detected algorithm

Full Size   |   Slide (.pptx)

TABLE I.

TEST RESULTS OF SELFSIMILAR SEQUENCE GENERATED BY R/S ALGORITHM (RMD ALGORITHM)

Full Size   |   Slide (.pptx)

TABLE II.

TEST RESULTS OF SELF-SIMILAR SEQUENCE GENERATED BY R/S ALGORITHM (FOURIER ALGORITHM)

Full Size   |   Slide (.pptx)

REFERENCES

  1. Leland W E, Aqqu M S, Willinger W, et al. On theself-similar nature of Ethernet traffic (extended version)[J]. IEEE/ACM Transactions on Networking, 1994, (1), P:1-15.
    [CROSSREF]
  2. Lee YH, Kassam SA. Generalized median filtering and related nonlinear filtering techniques[J]. IEEE Transactions on Acoustica, Speech, Signal Processing, 1985, 33(3):672-683.
    [CROSSREF]
  3. Mandelbort B B, Van Ness J. Fractional Brownian motions, factional noises and applications[J]. 1968, 10(4):422-437.
  4. Zhu Xiao-Wen, Tan Xian-Hai, Chen Baixiu. Research on modeling of network traffic based on (MK)-FBM[J]. Railway Computer Application, 2009, 18(6): 10-13.
  5. Li Lin-Feng Qiu Zheng-Ding. An Iterative Method to Estimate Hurst Index of Self-similar Network Traffic[J]. Journal of Electronics& Information Technology. 2006, 28(12):136-158.
  6. Xu Mingwei, Tong Aijun. Network performance testing based on self-similar modeling[J]. Computer Engineering and Applications, 2002, 38(5): 56-59.
  7. Fu Lei-Yang, Wang Ruchuan, Wang Haiyan, et al. Implementation and application of computing self-similar parameter by R/S approach to analyze network traffic[J]. Transactions of Nanjing University of Aeronautics & Astronautics, 2007, 39(3): 358-362.
  8. Wang Xin. Modeling and prediction of self-similar network traffic [D]. Beijing: THU, 2003.
  9. Wang Xifeng, Gao Ling, Zhang Xiaoluan. Analysis and research on self-similar network traffic forecast[J]. Computer Technology and Development, 2007, 17(11): 42-45.

EXTRA FILES

COMMENTS