# Convergence of Sample Autocorrelation of Long-Range Dependent Traffic

Authors: Ming Li; Wei Zhao
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

We depict our work on a fundamental issue in the theory of long-range dependent traffic in the aspect of the convergence of sample autocorrelation function (ACF) of real traffic. The present results suggest that the sample ACF of traffic is convergent. In addition, we show that the sample size has considerable effects in estimating the sample ACF of traffic. More precisely, a sample ACF of traffic tends to be smoother when the sample size increases.


---

## Body

## 1. Introduction

Start with the meaning of the convergence of a sample autocorrelation function (ACF) of a stationary random functionx(t) for t∈(0,∞). Denote by xT(t) a sample record of x(t) with length T, that is, xT(t)=x(t) for t∈(0,T). Let rT(τ) be the ACF of xT(t), meaning rT(τ)=E[xT(t)xT(t+τ)] for t, t+τ∈(0,T). Then, we say that rT(τ) is convergent if limT→rT(τ)=r(τ) exists, where r(τ) is the ACF of x(t). Otherwise, rT(τ) is divergent or does not exist. In the discrete case, x(t) is replaced by x(i)(i=0,…,∞),  xT(t) is substituted by xI(i) for  i=0,…,I-1, and rT(τ) is replaced with rI(k)(k=0,…,I-1). When limI→∞rI(k)=r(k) exists, where r(k) is the ACF of x(i), we say that rI(k) is convergent. That is the meaning of the convergence or existence of a sample ACF of a random function.The issue described above may be unnecessary to treat in the field of conventional second-order random functions because an ACF of a conventional 2-order random function generally exists [1–6]. However, the issue whether a sample ACF of teletraffic (traffic for short) time series with long-range dependence is convergent or not is worth discussing.The research by Resnick et al. [7] stated that the sample ACF of stable random functions with infinite variance may be random when the sample size approaches infinity instead of being convergent. The example of such a type of random functions includes α-stable processes with infinite variance [7, Page 798]. Recall that traffic modeling using α-stable processes was described by reports, such as Karasaridis and Hatzinakos [8], Barbe and McCormick [9]. On the other side, the reports by Field et al. [10, 11] discussed the traffic modeling using the standard Cauchy distribution, which implied that traffic is of infinite variance because variance of a random function obeying the Cauchy distribution is infinite [2–4]. Therefore, a sample ACF of traffic may be divergent if it is of infinite variance. Nonetheless, correlations of traffic play a role in practice; see, for example [12–22], just to cite a few. Consequently, the answer to the question whether a sample ACF of traffic is convergent or not is desired from the point of view of the theory of traffic. This paper aims at exhibiting that sample ACFs of real-traffic data are convergent.The rest of the paper is organized as follows. Problem statement is described in Section2. Results are explained in Section 3. Discussions are given in Section 4, which is followed by conclusions.


## 2. Problem Statement

In what follows, we assume that trafficx(i) is causal. By causal, we mean that x(i) is defined for i≥0 and x(i)=0 if i<0. In the interval [0,I], the sample ACF of xI(i) is given by
(1)rI(k)=1I∑i=0I-1x(i)x(i+k).
For Il≠Im, assuming Il<Im, we have,
(2)rIl(k)≠rIm(k),k=0,…,Il-1.
What is previously mentioned may be expressed by
(3)rIl(k)+ΔIl(k)=rIm(k),k=0,…,Il-1,
where ΔIl(k) is a fluctuation noise. Further, For Il≠Im≠In, assuming Il<Im<In, we have
(4)rIm(k)+ΔIm(k)=rIn(k),k=0,…,Il-1.
In general, if rI(k) is convergent, we have
(5)∑k=0Il-1|ΔIm(k)|≤∑k=0Il-1|ΔIl(k)|.
More precisely, in the case of rI(k) being convergent, we have
(6)limIl→∞rIl(k)=limIm→∞rIm(k)=r(k).
Consequently, the above means that
(7)limIl→∞ΔIl(k)=0.
Since a real-traffic data series is always of finite length and because the true ACF of x(i) is never achieved, the issue we treat in this research is to investigate whether rI(k) tends smoother when I becomes larger. If that is so, we infer that rI(k) is convergent. If not, it is divergent.


## 3. Results

Before showing the results, we brief the real-traffic data used in this section. Letx(t(i)) be a sample record of traffic, where t(i) is the series of timestamps, indicating the timestamp of the ith packet arriving at a server. Thus, x(t(i)) represents the packet size of the ith packet recorded at time t(i). Note that the pattern of x(t(i)) is consistent with that of x(i) that represents the size of the ith packet on a packet-by-packet basis.We use two real-traffic traces. One is named BC-pOct89 that contains 1,000,000 packets. It was recorded on an Ethernet at the Bellcore Morristown Research and Engineering Facility [23], which is now Telcordia Technologies (http://en.wikipedia.org/wiki/Telcordia_Technologies), made by Will Leland and Dan Wilson. The other is DEC-PKT-1 with 3.3 million packets. It was made by Jeff Mogul of Digital’s Western Research Lab [24]. The former was used in the pioneering research of the fractal statistics of traffic in [25, 26]. The latter was utilized by Paxson and Floyd in [27]. We cite relatively recent articles [28–30] for the nice description of the basic statistics of traffic.Figure1 is the plot of the first 2048 data points of traffic trace BC-pOct89. Figure 2 indicates the plots of sample ACFs of BC-pOct89 with different sample sizes as follows.(i)
Figure2(a): sample ACF of BC-pOct89 with the sample size I=211=2048.(ii)
Figure2(b): sample ACF of BC-pOct89 with the sample size I=212=4096.(iii)
Figure2(c): sample ACF of BC-pOct89 with the sample size I=213=8192.(iv)
Figure2(d): sample ACF of BC-pOct89 with the sample size I=214=16384.(v)
Figure2(e): sample ACF of BC-pOct89 with the sample size I=215=32768.(vi)
Figure2(f): sample ACF of BC-pOct89 with the sample size I=216=65536.(vii)
Figure2(g): sample ACF of BC-pOct89 with the sample size I=217=131027.Figure 1
Plot of packet-size series of traffic trace BC-pOct89 on a packet-by-packet basis.Sample ACFs of BC-pOct89 with the different sample sizes. (a) Sample ACF of BC-pOct89 with the sample sizeI=2048. (b) Sample ACF of BC-pOct89 with I=4096. (c) Sample ACF of BC-pOct89 with I=8192. (d) Sample ACF of BC-pOct89 with I=16384. (e) Sample ACF of BC-pOct89 with I=32768. (f) Sample ACF of BC-pOct89 with I=65536. (g) Sample ACF of BC-pOct89 with I=131027.
(a)
(b)
(c)
(d)
(e)
(f)
(g)From Figure2, we obtain the following observations.Observation 1.
The sample ACF of BC-pOct89 with different sample sizes obeys a certain deterministic function.Observation 2.
The fluctuation of a sample ACF of BC-pOct89 decreases as the sample size increases.In order to refine Observation2, we demonstrate the first 1024 points of the sample ACFs in the sense of zoom as shown in Figure 3. Thus, comes the following consequence.First 1024 points of sample ACFs of BC-pOct89 with the different sample sizes. (a) First 1024 points of sample ACF of BC-pOct89 with the sample sizeI=4096. (b) First 1024 points of sample ACF of BC-pOct89 with I=8192. (c) First 1024 points of sample ACF of BC-pOct89 with I=16384. (d) First 1024 points of sample ACF of BC-pOct89 with I=32768. (e) First 1024 sample ACF of BC-pOct89 with I=65536. (f). First 1024 sample ACF of BC-pOct89 with I=131027.
(a)
(b)
(c)
(d)
(e)
(f)Consequence 1. The sample ACF of BC-pOct89 is convergent.The demonstrations of the sample ACF of DEC-PKT-1 are given in the appendix.


## 4. Discussions

The modeling of the sample ACF of BC-pOct89 may be fractional Gaussian noise (fGn), which is appropriate when the time scaling is large [31, 32], or the generalized fGn [33]. Both BC-pOct89 and DEC-PKT-1 may be well described by the generalized Cauchy (GC) correlation structure [34]. The theme of this research is the convergence of sample ACF of traffic instead of correlation modeling of traffic. From the present results, nevertheless, one may infer that (5), (6), and (7) hold.The data used on this research were measured in the last century, more precisely, BC-pOct89 in 1989 and DEC-PKT-1 in 1995. However, the research by Borgnat et al. [35] suggested that statistics of traffic remain identical from the early age of the Internet to today. Therefore, we infer that sample ACF of traffic today may be convergent.Though we utilized traffic data in this research, the methodology described in this research might be possible for investigating the convergence of sample ACFs of other data series, for example, those in [36–43]. Finally, we note that this research does not imply something that might deviate from the point of view in traffic modeling using Levy stable structure, such as stable Levy motion [44], Levy flights [45], α-stable models [8] or the standard Cauchy distribution [10, 11], when those correspond to random functions with infinite variance such that they may yield divergent sample ACF. Rather, we suppose that it seems still faraway to thoroughly understand the statistics of traffic, without contradictions, with its commonly used models that may not be enough as Mandelbrot stated for modeling fractal random functions in general [46], but things may need developing; see, for example, Cohen and Lindner [47], Denby et al. [48], and Lazarou et al. [49].


## 5. Conclusions

We have exhibited that the sample ACFs of real-traffic data are convergent. Consequently, the sample ACFs of traffic exist. We have shown that the sample ACFs of traffic become smoother when the sample size increases.



---

*Source: 725730-2013-07-16.xml*