Self-Similarity of Network Data Analysis
Introduction In computer networks, self-similarity is a feature of network data transfer dynamics. When modeling network data dynamics the traditional time series models, such as an autoregressive moving average model are not appropriate. This is because these models only provide a finite number of parameters in the model and thus interaction in a finite time window, but the network data usually have a long-range dependent temporal structure. A self-similar process is one way of modeling network data dynamics with such a long range correlation. This article defines and describes network data transfer dynamics in the context of a self-similar process. Properties of the process are shown and methods are given for  graphing and estimating parameters modeling the self-similarity of network data.
Definition Suppose  be a weakly stationary (2nd-order stationary) processwith mean , variance , and autocorrelation function .Assume that the autocorrelation function  has the form as , where and  is a slowly varying function at infinity, that is  for all .For example,  and  are slowly varying functions.Let ,where , denote an aggregated point series over non-overlapping blocks of size , for each  is a positive integer.=== Exactly self-similar process ===*  is called an exactly self-similar process if there exists a self-similar parameter  such that  has the same distribution as . An example of exactly self-similar process with  is Fractional Gaussian Noise (FGN) with . '''Definition:Fractional Gaussian Noise (FGN)'''  is called the Fractional Gaussian Noise, where  is a Fractional Brownian motion.=== exactly second order self-similar process ===*  is called an exactly second order self-similar process if there exists a self-similar parameter  such that  has the same variance and autocorrelation as .=== asymptotic second order self-similar process ===*  is called an asymptotic second order self-similar process with self-similar parameter  if  as ,
Some relative situations of Self-Similar Processes === Long-Range-Dependence(LRD) ===Suppose  be a weakly stationary (2nd-order stationary) process with mean  and variance . The Autocorrelation Function (ACF) of lag  is given by '''Definition:'''A weakly stationary process is said to be "Long-Range-Dependence" if A process which satisfies  as  is said to have long-range dependence. The spectral density function of long-range dependence follows a power law near the origin. Equivalently to ,  has long-range dependence if the spectral density function of autocorrelation function, , has the form of  as  where ,  is slowly varying at 0.also see=== Slowly decaying variances ===When an autocorrelation function of a self-similar process satisfies  as , that means it also satisfies  as , where  is a finite positive constant independent of m, and 0<β<1.
Estimating the self-similarity parameter "H" === R/S analysis ===Assume that the underlying process  is Fractional Gaussian Noise. Consider the series , and let .The sample variance of  is '''Definition:R/S statistic'''If  is FGN, then Consider fitting a regression model :, whereIn particular for a time series of length  divide the time series data into  groups each of size , compute  for each group.Thus for each n we have  pairs of data ().There are  points for each , so we can fit a regression model to estimate  more accurately. If the slope of the regression line is between 0.5~1, it is a self-similar process.=== Variance-time plot ===Variance of the sample mean is given by .For estimating H, calculate sample means  for  sub-series of length .Overall mean can be given by , sample variance .The variance-time plots are obtained by plotting  against and we can fit a simple least square line through the resulting points in the plane ignoring the small values of k.For large values of , the points in the plot are expected to be scattered around a straight line with a negative slope .For short-range dependence or independence among the observations, the slope of the straight line is equal to -1.Self-similarity can be inferred from the values of the estimated slope which is asymptotically between –1 and 0, and an estimate for the degree of self-similarity is given by === Periodogram-based analysis ===Whittle's approximate maximum likelihood estimator (MLE) is applied to solve the Hurst's parameter via the spectral density of . It is not only a tool for visualizing the Hurst's parameter, but also a method to do some statistical inference about the parameters via the asymptotic properties of the MLE. In particular,  follows a Gaussian process. Let the spectral density of ,, where, and  construct a short-range time series autoregression (AR) model, that is ,with .Thus, the Whittle's estimator  of  minimizesthe function , where  denotes the periodogram of X as  and . These integrations can be assessed by Riemann sum.Then  asymptotically follows a normal distribution if  can be expressed as a form of an infinite moving average model.To estimate , first, one has to calculate this periodogram. Since is an estimator of the spectral density, a series with long-range dependence should have a periodogram, which is proportional to  close to the origin. The periodogram plot is obtained by plotting against .Then fitting a regression model of the  on the  should give a slope of . The slope of the fitted straight line is also the estimation of . Thus, the estimation  is obtained.Note:There are two common problems when we apply the periodogram method. First, if the data does not follow a Gaussian distribution, transformation of the data can solve this kind of problems. Second, the sample spectrum which deviates from the assumed spectral density is another one. An aggregation method is suggested to solve this problem. If  is a Gaussian process and the spectral density function of  satisfies  as , the function,, converges in distribution to FGN as .
References * P. Whittle, "Estimation and information in stationary time series", Art. Mat. 2, 423-434, 1953. * K. PARK, W. WILLINGER, Self-Similar Network Traffic and Performance Evaluation, WILEY,2000. * W. E. Leland, W. Willinger, M. S. Taqqu, D. V. Wilson, "On the self-similar nature of Ethernet traffic", ACM SIGCOMM Computer Communication Review 25,202-213,1995. * W. Willinger, M. S. Taqqu, W. E. Leland, D. V. Wilson, "Self-Similarity in High-Speed Packet Traffic: Analysis and Modeling of Ethernet Traffic Measurements", Statistical Science 10,67-85,1995.