Estimating the Intensity of Long-Range Dependence in Real and Synthetic Traffic Traces

Abstract

This paper examines various techniques for estimating the intensity of Long-Range Dependence (LRD). Trial data sets with LRD are generated using Fractional Gaussian noise and Markov modulated Poisson process. The real data set collected in IITiS PAN is also used.

1 Introduction

Many empirical and theoretical studies have shown the self-similar and LRD characteristics of the network traffic [1–4]. These features have a great impact on a network performance [3, 5, 6]. They enlarge mean queue lengths at buffers and increase packet loss probability, reducing this way the quality of services provided by a network [7]. That is why it is necessary to take into account this feature when you want to create a realistic model of traffic sources [8, 9].

Various modelling techniques are currently used for generating the LRD traffic. The majority of them is based on non-Markovian approach [10–13]. The advantage of these models is that they give a good description of the traffic with the use of few parameters. Their drawbacks consist in the fact that they do not allow the use of traditional and well known queueing models and modeling techniques for computer networks performance analysis. There are also Markov based models to generate a LRD traffic over a finite number of time scales [8, 14–17]. This approach makes possible the adaptation of traditional Markovian queueing models to evaluate network performance.

In this work we investigate long-range dependence in the synthetic data generated from Fractional Gaussian noise traffic source and Markovian traffic source. We also use for our analysis the realistic packet traffic trace collected in IITiS PAN.

Section 2 briefly describes the distinction between the terms: Self-similarity and Long-Range Dependence. Section 3 demontrates Fractional Gaussian noise as an example of exactly self-similar traffic source. Section 4 shortly describes the Markovian traffic source which is sufficient to generate long-range dependent traffic over several time scales. Section 5 presents the intensity of LRD estimation for real and synthetic traffic traces. Some conclusions are presented in Sect. 6.

2 The Distinction Between Self-Similarity and Long-Range Dependence

Over the last two decades, long-range dependency (LRD), self-similarity and heavy-tailed distributions have dominated Internet traffic analysis. Extensive measurements have revealed these phenomena in network traffic.

In the literature the terms long-range dependence and self-similarity are often used without distinction, although they are not equivalent concepts [18].

A continuous time process $Y(t)$ is exactly self-similar with the Hurst parameter $H$ if it satisfies the following condition [19]:

$$ Y(t)\mathop {=}\limits ^{d}a^{-H} Y(at) $$

for $t\ge 0$, $a\ge 0$ and $0<H<1$. The above equality is in the sense of finite dimensional distributions and the Hurst parameter expresses the degree of the self-similarity [20]. The process $Y(t)$ may be nonstationary [21].

In the case of network traffic one usually has to deal with time series rather than a continuous process. In that context the above definition can be summarized as follows. Let $X(t)$ be a stationary sequence representing increment process (e.g. in bytes/second). The corresponding aggregated sequence having level of aggregation $m$:

$$ X^{(m)}(k)=\frac{1}{m}\sum ^m_{i=1}X((k-1)m+i),\quad k=1,2,\ldots $$

is obtained by averaging $X(t)$ over nonoverlapping blocks of length $m$. The following condition is satisfied for a self-similar process:

$$ X\mathop {=}\limits ^{d}m^{1-H} X^{(m)} $$

for all integers $m$. A stationary sequence $X$ is second-order self-similar if for all $m$, $m^{1-H} X^{(m)}$ has the same variance and auto-correlation as $X$. A stationary sequence $X$ is asymptotically second-order self-similar if $m^{1-H} X^{(m)}$ has the same variance and auto-correlation as $X$ as $m\rightarrow \infty$.

Asymptotically second-order self-similar processes are also called long-range dependent processes and this is a property exhibited by network traffic [19]. Long-range dependence of data means that the behavior of a time-dependent process shows statistically significant correlations across large time scales and self-similarity describes the phenomenon in which the behavior of a process is preserved irrespective of scaling in space or time [2]. Figure 1 shows as an example the fluctuation over differents time scales for IITiS trace described in Sect. 5.

Fig. 1.

Self-similar processes exhibit similar fluctuations over different time scales (IITiS trace)

The autocorrelation function od LRD process decays very slowly and if the Hurst parameter is between $0.5$ and $1$, the autocorrelation has an asymptotically behavior. If the Hurst parameter is smaller or equal to $0.5$, the process exhibits SRD (Short-Range Dependence). Second-order stationary process whose autocorrelation function decays hyperbolically is asymptotically second-order self-similar [22]. For this reason the term self-similarity is often used interchangeably with the long-range dependence [19].

3 Fractional Gaussian Noise

Fractional Gaussian noise (fGn) has been proposed as a model [23] for the long-range dependence postulated to occur in a variety of hydrological and geophysical time series. Nowadays, fGn is one of the most commonly used self-similar processes in network performance evaluation [18]. Let $B_h(t)$ be a fractional Brownian motion process. Then the sequence of increments:

$$ X(t)=B_h(t)-B_h(t-1) $$

is an exactly self-similar stationary Gaussian process with zero mean, referred to as fGn process.

The autocorrelation function of fGn process is given by [2]:

$$ \rho ^{(m)}(k)=\rho (k)=\frac{1}{2}\left[ (k+1)^{2H}-2k^{2H}+(k-1)^{2H}\right] \!\!, $$

which is sufficient condition for second-order selfsimilarity. The fGn process is the only stationary Gaussian process that is exactly self-similar [24].

For $0.5<H<1$ the autocorrelation decays hyperbolically [25]:

$$ \rho (k)\sim H(2H-1)k^{2H-2} $$

so the process exhibits long-range dependence.

The spectral density of fGn process is given by [18]:

$$ f(\lambda )=c|e^{J\lambda }-1|^2\sum ^{\infty }_{i=-\infty }|2\pi i+\lambda |^{2H-1}, $$

where $\lambda \in [-\pi ,\pi ]$, $0.5<H<1$ and $c$ is a normalization constant such that $\int ^{\pi }_{-\pi }f(\lambda )d\lambda =Var(X)$.

The important problem is the systhetic generation of sample paths (traces) of self-similar processes [18]. In this paper we use the fast algorithm for generating approximate sample paths for a fGn process, first introduced in [26].

4 Markovian Model of LRD Traffic

Many researchers discussed the suitability of Markovian models to describe IP network traffic that exhibits self-similarity and long-range dependence [8, 14, 15, 17, 21]. They concluded that matching LRD is only required within the time scales of interest to the system under research [21, 27, 28].

In consequence, more traditional traffic models such as Markov Modulated Poisson Process may still be used for modeling LRD traffic. Markov Modulated Poisson Process (MMPP) is a widely used tool for the teletraffic models analysis. To generate LRD traffic we use in this paper the MMPP model proposed in [29], and precisely described in [17]. This model consists of $d$ two-state MMPP models. The $i$-th MMPP ($1\le i \le d$) can be parameterized by two square matrices:

$$ \mathbf{D}_\mathbf{0}^i= \left[ \begin{array}{cc} -(c_{1i}+\lambda _{1i})&{}c_{1i}\\ c_{2i}&{}-(c_{2i}+\lambda _{2i}) \end{array}\right] $$

$$ \mathbf{D}_\mathbf{1}^i= \left[ \begin{array}{cc} \lambda _{1i}&{}0\\ 0&{}\lambda _{2i} \end{array}\right] \!\!. $$

The element $c_{1i}$ is the transition rate from state 1 to 2 of the $i$-th MMPP and $c_{2i}$ is the rate out of state 2 to 1. $\lambda _{1i}$ and $\lambda _{2i}$ are the traffic rate when the $i$-th MMPP is in state 1 and 2 respectively. The sum of $\mathbf{D_0}^i$ and $\mathbf{D_1}^i$ is an irreducible infinitesimal generator $\mathbf{Q}^i$ with the stationary probability vector:

$$ \overrightarrow{\pi }_i=\left( \frac{c_{2i}}{c_{1i}+c_{2i}},\frac{c_{1i}}{c_{1i}+c_{2i}}\right) \!\!. $$

The superposition of these two-state MMPPs is a new MMPP with $2^d$ states and its parameter matrices, $\mathbf{D_0}$ and $\mathbf{D_1}$, can be computed using the Kronecker sum of those of the $d$ two-state MMPPs [30]:

$$ (\mathbf{D}_0,\mathbf{D}_1)=\left( \oplus ^d_{i=1}\mathbf{D_0}^i,\oplus ^d_{i=1}\mathbf{D_1}^i\right) \!\!. $$

Let $N_t^i$ be a number of arrivals from the $i$-th MMPP in time slot $(0,t]$. The variance time for this MMPP can be expressed as:

$$ Var\{N_t^i\}=(\lambda ^*_i+2k_{1i})t-\frac{2k_{1i}}{k_{2i}} \left( 1-e^{-k_{2i}t}\right) $$

where:

$$ \lambda ^*_i=\frac{c_{2i}\lambda _{1i}+c_{1i}\lambda _{2i}}{c_{1i}+c_{2i}} $$

$$ k_{1i}=(\lambda _{1i}-\lambda _{2i})^2\frac{c_{1i}c_{2i}}{(c_{1i}+c_{2i})^3} $$

$$ k_{2i}=c_{1i}+c_{2i}. $$

The second-order properties are determined by this three entities: $\lambda ^*_i$, $k_{1i}$ and $k_{2i}$. The covariance function of the number of arrivals in two time slots of size ${\varDelta }t$ is expressed by [29]:

$$\begin{aligned} \gamma _i(k)\!&=\!\frac{(\!\lambda _{1i}\!-\!\lambda _{2i}\!)^2c_{1i} c_{2i}e^{-((c_{1i}c_{2i})(\!k-1\!){\varDelta }t)}}{(c_{1i}+c_{2i})^4} \cdot \left( \!1\!-\!2e^{-((c_{1i}+c_{2i}){\varDelta }t)}\!+\!e^{-((c_{1i}+c_{2i})2{\varDelta }t)}\!\right) \!\\&=\frac{k_{1i}}{k_{2i}}e^{-(k_{2i}(k-1){\varDelta }t)} \cdot \left( 1- 2e^{(-k_{2i}{\varDelta }t)}+e^{(-k_{2i}2{\varDelta }t)}\right) \\&\approx \frac{({\varDelta }t)^2(\lambda _{1i}-\lambda _{2i})^2c_{1i}c_{2i} e^{-((c_{1i}+c_{2i})(k-1){\varDelta }t)}}{(c_{1i}+c_{2i})^2}=({\varDelta }t)^2k_{1i}k_{2i}e^{-(k_{2i}(k-1){\varDelta }t)}. \end{aligned}$$

Article [29] illustrates that a superposition of four described above two-state MMPP models suffices to replicate second-order self-similar behaviour over several time scales.

5 Long-Range Dependence Estimation

The Hurst parameter characterizes a process in terms of the degree of self-similarity and LRD [31]. The degree of self-similarity and LRD increases with increasing of $H$ [32]. A Hurst value smaller or equal to $0.5$ means the lack of self-similarity or the presence of SRD [33]. A Hurst parameter greater than $0.5$ means the existance of LRD [31].

Table 1. The IITiS traffic classification

In our works three types of LRD traffic traces were considered. Two of them: fGn traffic source and MMPP traffic source have been described in Sects. 3 and 4. We also used a trace of real Internet traffic collected from the network of IITiS institute serving $<\!\!50$ academic users. This data set has been collected during the whole May 2012 on the Internet gateway of our Institute [4, 34]. The datasets contains different subsets of network protocols. Table 1 gives a summary description of the IITiS traffic data analyzed in the paper.

There are many methods of estimating this parameter. In order to estimate the true values of the Hurst parameter we used in our works five estimators:

• aggregate variance method,

• R-S Plot,

• method based on periodogram,

• local Whittle’s estimator,

• Wavelet based method.

We used the statistical package $R$ mentioned in [35].

The aggregate variance method was described in [35–38]. This technique is time-domain based. It considers $Var(X^{(m)})$, where the aggregated process $X^m$ is a time series derrived from $X$ by aggregating it over blocks of size $m$. The aggregated sequence is then plotted versus $m$ after taking logarithm. The estimated value of Hurst parameter is obtained by fitting a simple least squares line through the resulting points in the plane. The asymptotic slope between $-1$ and $0$ suggests LRD and estimated Hurst parameter is given by $H=1-\mathrm {slope}/{2}$. Figure 2 shows as an example the variance-time plot for IITiS trace.

Fig. 2.

Variance-time (left) and R-S (right) plots (IITiS trace)

The R-S Plot method [35, 37, 39] is one of the oldest Hurst parameter estimator. Let $R(n)$ be the range of the data aggregated over blocks of length $n$ and $S^2(n)$ be the sample variance of data aggregated at the same scale. For a stochastic process $X$ the rescaled range of $X$ over a time interval $n$ is defined as the ratio ${R}/{S}$:

$$ \frac{R}{S}(n)=S^{-1}(n)\left[ \max _{0\le t\le n} \left( X(t)-t \overline{X}(n)\right) -\min _{0\le t\le n} \left( X(t)-t \overline{X}(n)\right) \right] $$

where $\overline{X}(n)$ is the sample mean over the time interval $n$ and $S(n)$ is standard deviation. For LRD processes, the ratio has the following characteristic for large $n$:

$$ \frac{R}{S}\sim \left( \frac{n}{2}\right) ^H. $$

A log-log plot of $\frac{R}{S}(n)$ versus $n$ should have a constant slope $H$ as $n$ becomes large. Figure 2 shows as an example the R-S plot for IITiS trace.

The method using Periodogram [35, 37, 40] is frequency domain method, the periodogram is defined by:

$$ I_X(\omega )=\frac{1}{2\pi n}\left| \sum ^{n}_{j=1}X_je^{ij \omega }\right| ^2. $$

A log-log plot $I_X(\omega _{n,k})$ versus $\omega _{n,k}=\frac{2\pi k}{n}$ should have a slope of $1-2H$ around $\omega =0$. Figure 3 shows as an example the periodogram for IITiS trace.

Fig. 3.

Periodogram (left) and Wavelet (right) based analysis (IITiS trace)

Local Whittle’s estimator assumes only a functional form for the spectral density at frequencies near zero. To estimate Hurst parameter one should minimize the function:

$$ Q(H)=\sum _j\left[ \log f_j(\omega _j)+\frac{\log I_X(\omega _j)}{f_j(\omega _j)}\right] $$

where $I_X(\omega )$ is the periodogram and $f(\omega )=c\omega ^{2H-1}$.

Wavelet analysis is successfully used to measure the Hurst parameter [35]. Wavelets can be thought of as akin to Fourier series, but using waveforms other than sine waves. Figure 3 shows as an example the wavelet analysis for IITiS trace. The estimator fits a straight line to a frequency spectrum derived using wavelets.

Table 2 gives the the obtained Hurst parameters for one day IITiS traces:

• trace 1 – 6 002 874 samples,

• trace 2 – 13 874 610 samples,

• trace 3 – 36 135 490 samples.

In the case of Wavelets based method a $95\,\%$ confidence interval should be interpreted only as a confidence interval on the fitted line. Our previous work [4] did not confirm the relationship between the degree of LRD and the number of transmitted packet of a given type. One can see a little agreement between the estimators.

Table 2. Hurst parameter estimates for IITiS data traces

Table 3 shows the obtained Hurst parameters for MMPP data traces:

• MMPP 1 – input parameters: $d=5$, $n=6$, $\lambda ^*=3.5$, $H=0.75$ and $\rho =0.6$,

• MMPP 2 – input parameters: $d=5$, $n=6$, $\lambda ^*=3.5$, $H=0.6$ and $\rho =0.6$,

• MMPP 3 – input parameters: $d=4$, $n=5$, $\lambda ^*=9.985$, $H=0.79$ and $\rho =0.0213$.

The fGn model and the MMPP 3 model were used to simulate the LRD data using a theoretical Hurst parameter and the same theoretical mean as the IITiS data. Different Hurst parameters have been chosen to represent a low and a high level of long-range dependence in data. The models are run to produce 200 000 packets. The MMPP 1 and MMPP 2 models have the example parameters described above.

Table 3. Hurst parameter estimates for MMPP data traces

As can be seen the MMPP model is more inconsistent than the fGn model (see Table 4).

Table 4. Hurst parameter estimates for fGn data traces

6 Conclusions

The article confirms that although the Hurst parameter is well defined mathematically, it is problematic to measure it properly [35]. There are several methods to estimate the Hurst parameter but they often produce conflicting results [2]. Many researchers conclude that wavelet technique generally is faring well in comparative studies [31, 35].

Our results demonstrate the best agreement among the estimators results in the case of fGn model. In the case of real traffic the differences estimators predictions are more visible. This confirms the opinion that the problems with real-life data are worse than those faced when measuring and characterizing synthetic data [35]. Real data can have periodicity, trends and quantisation effect and obtained results are more dependent on the sampling rate than in the case of synthetic traffic traces.