# Smoothing the Sample Autocorrelation of Long-Range-Dependent Traffic

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

---

## Abstract

This paper depicts our work in smoothing the sample autocorrelation function (ACF) of traffic. The experimental results exhibit that the sample ACF of traffic may be smoothed by the way of average. In addition, the results imply that the sum of sample ACFs of traffic convergences. Considering that the traffic data used in this research is long-range dependent (LRD), the latter may be meaningful for the theoretical research of LRD traffic.


---

## Body

## 1. Introduction

Letx(t(i)) be a sample record of teletraffic time series (traffic for short), where t(i) for i∈N (the set of natural numbers) 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) on a packet-by-packet basis. We use a real-traffic trace named BC-Aug89 recorded on an Ethernet at the Bellcore Morristown Research and Engineering facility, which contains 1,000,000 packets [1]. It was used in the pioneering work for revealing some statistical properties of traffic in fractals, such as self-similarity and long-range dependence (LRD) [2, 3].Note 1.
The statistical properties described in the early literature, for example, [2, 3], turn to be ubiquitous in today’s traffic, according to the research stated in [4, 5]. Thus, the trace measured in 1989 keeps its value in the research of general patterns of traffic.The word traffic is a collective noun. In addition to the traffic on a packet-by-packet basis as previously described, it may imply the time series called interarrival times, which is in the form (see [6, 7])
(1)s(i)=t(i+1)-t(i).
The term traffic may also imply the time series named accumulated traffic, denoted by y(n), on an interval-by-interval basis, which is given by
(2)y(n)=∑i=nT(n+1)Tx(i),
where T is the interval width. It stands for the accumulated bytes of arrival traffic in the nth interval.Note 2.
The statistical properties ofx(t(i)), s(i), and y(n) may be identical [5].Note 3.
The attributes of traffic are application dependent. More other meanings of traffic are available. It may mean the packet count [2]. In some applications, one may be interested in the number of connections within a given time interval [4], the packet size or the number of packets on a flow-by-flow basis [8], envelopes of traffic [9], or traffic bounds [10].This paper relates to the aggregated trafficx(t(i)). Figure 1 illustrates four types of the series of BC-Aug89. Let the interval width be T=1024. Then, we obtain y(n) of BC-Aug89 according to (2), as shown in Figure 2. Note that the pattern of x(t(i)) is consistent with that of x(i) that represents the size of the ith packet. Besides, the statistics of x(i) and y(n) may generally be identical [5]. Therefore, in what follows, we will use x(i) for the discussions instead of x(t(i)) for the purpose of simplicity.Illustrations of real-traffic trace BC-Aug89. (a) Timestamp seriest(i). (b) Interarrival times s(i). (c) Traffic in packet size x(t(i)). (d) Traffic in packet sizex(i).
(a)
(b)
(c)
(d)Figure 2
Accumulated traffic of BC-Aug89 with the interval widthT=1024.Remark 1 (burstiness).
Without considering the Ethernet preamble, header, or CRC, the Ethernet protocol forces all packets to have at least a minimum size of 64 bytes and at most the maximum size of 1518 bytes. The fixed limit of 1518 bytes is specified by IEEE standard without technical reason. Thus, it is often the case that the packet size of traffic may take the same value within a short period of time as Figure1(c) shows. In addition, traffic has the behavior of “burstiness.” By burstiness, one implies that there would be no packets transmitted for a while, then flurry of transmission, no transmission for another long time, and so forth if one observes traffic over a long period of time [11, 12]. This phenomenon, indicated in Figures 1(b)–1(d), was described as intermittency by Tobagi et al. [13].Note 4.
The intermittency of a random function is conventionally discussed in the field of turbulence [14], but we note that it is also a phenomenon of traffic.The traffic seriesx(i) is LRD. Denote its autocorrelation function (ACF) by r(k) in the stationarity case. Then,
(3)r(k)=E[x(i)x(i+k)],
where E is the mean operator and k is lag. Its power spectrum density (PSD) denoted by S(ω) is the Fourier transform of r(k):
(4)S(ω)=F[r(k)],
where F is the operator of the Fourier transform, ω=2πf, where f is the frequency. Note that the PSD of x(i) belongs to 1/f noise [15]. Thus, even from a view of data processing, r(k) is preferred [16], because S(ω) is divergent at ω=0. In addition, the correlation model of traffic is desired in networking; see the statement of Paxson and Floyd [17, p. 5] as follows. The issue of “how to go from the pure correlational structure, expressed in terms of a time series of packet arrivals per unit time, to the details of exactly when within each unit of time each individual packet arrives” has not been solved. For this reason, we discuss the issue of ACF estimation of LRD traffic.The remainder of this paper is as follows. In Section2, we shall brief the preliminaries. Smoothing the sample ACF of traffic is discussed in Section 3. A case study is shown in Section 4. Discussions and future work are in Section 5, which is followed by conclusions.


## 2. Brief of Time Series

Denote by{xl(t)} a set of sample functions for l∈N and 0<t<∞, and xl(t)∈R (set of real numbers) is the lth sample function. A process consists of a set of sample functions [18, 19].Note 5.
In the case of traffic, requiring a set of sample functions{xl(t)} for l∈N at a specific point in networks may be unrealistic since one can only measure a single history of traffic trace at that specific point. One may never achieve a set of sample records of real traffic in the sense of repeated experiments under the exactly same conditions for 0<t<∞. Therefore, in traffic engineering, we are interested in a sample function x(t) instead of a process.Note 6.
We consider a time seriesx(t) that is a random function. In this research, the terms of random function, time series, or process are interchangeable if there are no confusions.


### 2.1. Moment

Denote byp(x,t) the probability density function (PDF) of a random function x(t), which is usually written as p(x) in short. Then, the following is called its moment of order n:
(5)mn(t)=E[xn(t)]=∫-∞∞xnp(x,t)dx.
The moment of a random function is consistent with the moment of a force in physics as well as mechanics in expression [20]. It serves as a useful tool to represent certain important characteristics of a random function.


#### 2.1.1. Mean and Mean Square

Using the concept of the moment, one may conveniently represent the mean ofx(t) as its first-order moment given by
(6)m1(t)=μ(t)=E[x(t)]=∫-∞∞xp(x,t)dx.
The second moment of x(t) may be its mean square value denoted by
(7)m2(t)=Ψ(t)=E[x2(t)]=∫-∞∞x2p(x,t)dx.Note 7.
The mean ofx(t) represents its average value around which x(t) fluctuates.Note 8.
The mean square ofx(t) stands for its strength or average power. To explain this, we assume that x(t) is a voltage exerting on a resistor of one Ohm. In this case, x2(t) is the power the resistor consumes at time t. Therefore, (7) implies the average power. Hence, the strength of x(t).


#### 2.1.2. ACF

Now, we consider the product ofx(t) at two points, say x(t1)x(t2) for t1≠t2. Since both x(t1) and x(t2) are random variables, we denote by p(x1,t1;x2,t2) the joint PDF of x(t1) and x(t2). With the help of the concept of moment, E[x(t1)x(t2)] may be expressed in the form
(8)r(t1,t2)=E[x(t1)x(t2)]=∬-∞∞x(t1)x(t2)p(x1,t1;x2,t2)dx1dx2.
The function r(t1,t2) in (8) is called the ACF of x(t). It represents how one random variable x(t1) at time t1 correlates with the other x(t2) at another time t2. In other words, it represents the correlation of x(t) at two different points t1 and t2.Note 9.
In the case oft1=t2=t, the ACF of x(t) reduces to its mean square:
(9)r(t1,t2)|t1=t2=E[x(t)x(t)]=∫-∞∞x2(t)p(x,t)dx.Note 10.
The term of the second-order moment ofx(t) may imply the moments of order 2, which in the wide sense or in general include mean square (7) and ACF (8).Note 11.
If we consider the moments ofx(t) up to 2, x(t) is called 2-order random function, which plays a role in engineering. The moments of orders higher than 2 correspond to the case of higher order statistics, which we do not discuss in this paper.


#### 2.1.3. PSD

The Fourier transform of the ACFr(t,s) is given by
(10)S(ω,t)=∫-∞∞r(t,s)e-jωsds,j=-1.
It represents the energy distribution of x(t).Note 12.
In general,mn(t) is time dependent. Therefore, the mean, mean square, ACF, and PSD may generally be time dependent. In the stationary case, they are independent of time.


#### 2.1.4. Weak Stationarity

If all moments ofx(t) do not vary with time, x(t) has the property of strong stationarity. If the moments up to 2 are independent of time, irrelevant of the moments of order higher than 2, we say that x(t) is of weak stationarity or stationary in the wide sense.Note 13.
In the case of weak stationarity,μ(t) and Ψ(t) are constants. The ACF only replies on the time lag τ=|t-s|. Hence, r(t,s)=r(τ). Consequently, S(ω,t)=S(ω).


### 2.2. Central Moment

Often, one may be interested in a random function with mean zero. For random functions with mean zero, the previous expression regarding the moment (5) is extended to the central moment expressed by
(11)mcn(t)=E{[x(t)-μ(t)]n}=∫-∞∞[x(t)-μ(t)]np(x,t)dx.


#### 2.2.1. Variance and Standard Deviation

The central moment of order 2 given by(12)mc2(t)=E{[x(t)-μ(t)]2}=∫-∞∞[x(t)-μ(t)]2p(x,t)dx
is usually denoted by σ2(t) called the variance of x(t). The standard deviation, denoted by stdev(t), is given by
(13)stdev(t)=σ2(t)=σ(t).Note 14.
How much the variation ofx(t) away from its mean μ(t) is characterized by its variance or standard deviation.Remark 2.
Analysis of variance (ANOVA) is a branch of statistics, which plays a role in many aspects of techniques, especially in the fields of statistics tests and experimental design [21–23].


#### 2.2.2. Autocovariance

In the case of mean zero, one uses the autocovariance function denoted byC(t1,t2) (ACF for short again) to characterize the correlation property of [x(t)-μ(t)]. It may be given by
(14)C(t1,t2)=E{[x(t1)-μ(t1)][x(t2)-μ(t2)]}=∬-∞∞[x(t1)-μ(t1)][x(t2)-μ(t2)]×p(x1,t1;x2,t2)dx1dx2.Note 15.
Whent1=t2=t, C(t1,t2) reduces to σ2(t):
(15)C(t,t)=E{[x(t)-μ(t)]2}=σ2(t).Remark 3.
ACF analysis is an important branch in statistics; see, for example, [19, 23–28].Remark 4.
A Gaussian random function is uniquely determined by its ACF [29, 30].
As a matter of fact, the PDF of a Gaussian random function is given by(16)p(x)=12πσexp[-(x-μ)22σ2],-∞<x<∞.
In (16), σ can be determined by (15) while μ can be obtained from the following:
(17)C(t,t)=r(t,t)-μ2(t).
Hence, Remark 4 results.Note 16.
Ifx(t) is weak stationary, its μ(t) and σ(t) are constants. Its ACF depends only on lag:
(18)C(t1,t2)=C(|t1-t2|)=C(τ),τ=|t1-t2|.
We list two properties of ACF below.P1:
ACF is an even function:r(τ)=r(-τ), C(τ)=C(-τ).P2:
r(0)≥r(τ), C(0)≥C(τ).Note 17.
P1 is obvious because the correlation betweenx(t1) and x(t2) is always equal to that between x(t2) and x(t1). P2 is natural because the correlation between the same point x(t1) and x(t1) always reaches its maximum.Without loss of generality for the statistical analysis of random functions, one may adopt the concept of normalized random functions. By normalized, we meanr(0)=1 or C(0)=1. Therefore, a normalized random function may be obtained by x(t)/C(t,t).


### 2.3. Computational Methods

Previous expressions in (5)~(15) regarding the mean, variance, and ACF of a random function x(t) are associated with its PDF. That implies that they can be determined under the condition that the PDF is known. However, that may usually be too restrictive in practical applications in engineering. Fortunately, Wiener et al. proposed a computation approach using time average without relating to its PDF if x(t) is ergodic [18, 31, 32].Note 18.
It may be very difficult if not impossible for one to test the ergodicity by a sample function of a traffic trace. In practice, one may simply assume that a traffic tracex(t) is ergodic.In what follows, we suppose thatx(t) is causal. By causal, we mean that x(t) is defined for 0≤t<∞ and x(t) = 0 for t<0. In addition, we only consider x(t) in the weak stationary sense. By using the time average, therefore, the mean of x(t) is given by
(19)μ=E[x(t)]=limT→∞1T∫0Tx(t)dt.
Its mean square is written by
(20)Ψ=E[x2(t)]=limT→∞1T∫0Tx2(t)dt.
Its ACF is expressed by
(21)r(τ)=E[x(t)x(t+τ)]=limT→∞1T∫0Tx(t)x(t+τ)dt.
Its variance is given by
(22)σ2=E{[x(t)-μ]2}=limT→∞1T∫0T[x(t)-μ]2dt.
Similarly, its autocovariance is given by
(23)C(τ)=E{[x(t)-μ][x(t+τ)-μ]}=limT→∞1T∫0T[x(t)-μ][x(t+τ)-μ]dt.In what follows, we only consider random functions with mean zero. Accordingly,r(τ) is equal to C(τ), and Ψ=σ2 unless otherwise stated.We write the PSD ofx(t) by
(24)S(ω)=∫-∞∞r(τ)e-jωτdτ.
Alternatively, r(τ) can be expressed by
(25)r(τ)=12π∫-∞∞S(ω)ejωτdω.


### 2.4. Defaulted Assumptions in Conventional Time Series

In the field of conventional time series, the following assumptions are usually defaulted [18, 21–37].(i)
The mean ofx(t) exists.(ii)
The variance ofx(t) exists.(iii)
S(0)=∫-∞∞r(τ)dτ is convergent.However, the above may be untrue for LRD traffic; see, for example, [16, 38, 39], which we shall not discuss more in this paper.


## 2.1. Moment

Denote byp(x,t) the probability density function (PDF) of a random function x(t), which is usually written as p(x) in short. Then, the following is called its moment of order n:
(5)mn(t)=E[xn(t)]=∫-∞∞xnp(x,t)dx.
The moment of a random function is consistent with the moment of a force in physics as well as mechanics in expression [20]. It serves as a useful tool to represent certain important characteristics of a random function.


### 2.1.1. Mean and Mean Square

Using the concept of the moment, one may conveniently represent the mean ofx(t) as its first-order moment given by
(6)m1(t)=μ(t)=E[x(t)]=∫-∞∞xp(x,t)dx.
The second moment of x(t) may be its mean square value denoted by
(7)m2(t)=Ψ(t)=E[x2(t)]=∫-∞∞x2p(x,t)dx.Note 7.
The mean ofx(t) represents its average value around which x(t) fluctuates.Note 8.
The mean square ofx(t) stands for its strength or average power. To explain this, we assume that x(t) is a voltage exerting on a resistor of one Ohm. In this case, x2(t) is the power the resistor consumes at time t. Therefore, (7) implies the average power. Hence, the strength of x(t).


### 2.1.2. ACF

Now, we consider the product ofx(t) at two points, say x(t1)x(t2) for t1≠t2. Since both x(t1) and x(t2) are random variables, we denote by p(x1,t1;x2,t2) the joint PDF of x(t1) and x(t2). With the help of the concept of moment, E[x(t1)x(t2)] may be expressed in the form
(8)r(t1,t2)=E[x(t1)x(t2)]=∬-∞∞x(t1)x(t2)p(x1,t1;x2,t2)dx1dx2.
The function r(t1,t2) in (8) is called the ACF of x(t). It represents how one random variable x(t1) at time t1 correlates with the other x(t2) at another time t2. In other words, it represents the correlation of x(t) at two different points t1 and t2.Note 9.
In the case oft1=t2=t, the ACF of x(t) reduces to its mean square:
(9)r(t1,t2)|t1=t2=E[x(t)x(t)]=∫-∞∞x2(t)p(x,t)dx.Note 10.
The term of the second-order moment ofx(t) may imply the moments of order 2, which in the wide sense or in general include mean square (7) and ACF (8).Note 11.
If we consider the moments ofx(t) up to 2, x(t) is called 2-order random function, which plays a role in engineering. The moments of orders higher than 2 correspond to the case of higher order statistics, which we do not discuss in this paper.


### 2.1.3. PSD

The Fourier transform of the ACFr(t,s) is given by
(10)S(ω,t)=∫-∞∞r(t,s)e-jωsds,j=-1.
It represents the energy distribution of x(t).Note 12.
In general,mn(t) is time dependent. Therefore, the mean, mean square, ACF, and PSD may generally be time dependent. In the stationary case, they are independent of time.


### 2.1.4. Weak Stationarity

If all moments ofx(t) do not vary with time, x(t) has the property of strong stationarity. If the moments up to 2 are independent of time, irrelevant of the moments of order higher than 2, we say that x(t) is of weak stationarity or stationary in the wide sense.Note 13.
In the case of weak stationarity,μ(t) and Ψ(t) are constants. The ACF only replies on the time lag τ=|t-s|. Hence, r(t,s)=r(τ). Consequently, S(ω,t)=S(ω).


## 2.1.1. Mean and Mean Square

Using the concept of the moment, one may conveniently represent the mean ofx(t) as its first-order moment given by
(6)m1(t)=μ(t)=E[x(t)]=∫-∞∞xp(x,t)dx.
The second moment of x(t) may be its mean square value denoted by
(7)m2(t)=Ψ(t)=E[x2(t)]=∫-∞∞x2p(x,t)dx.Note 7.
The mean ofx(t) represents its average value around which x(t) fluctuates.Note 8.
The mean square ofx(t) stands for its strength or average power. To explain this, we assume that x(t) is a voltage exerting on a resistor of one Ohm. In this case, x2(t) is the power the resistor consumes at time t. Therefore, (7) implies the average power. Hence, the strength of x(t).


## 2.1.2. ACF

Now, we consider the product ofx(t) at two points, say x(t1)x(t2) for t1≠t2. Since both x(t1) and x(t2) are random variables, we denote by p(x1,t1;x2,t2) the joint PDF of x(t1) and x(t2). With the help of the concept of moment, E[x(t1)x(t2)] may be expressed in the form
(8)r(t1,t2)=E[x(t1)x(t2)]=∬-∞∞x(t1)x(t2)p(x1,t1;x2,t2)dx1dx2.
The function r(t1,t2) in (8) is called the ACF of x(t). It represents how one random variable x(t1) at time t1 correlates with the other x(t2) at another time t2. In other words, it represents the correlation of x(t) at two different points t1 and t2.Note 9.
In the case oft1=t2=t, the ACF of x(t) reduces to its mean square:
(9)r(t1,t2)|t1=t2=E[x(t)x(t)]=∫-∞∞x2(t)p(x,t)dx.Note 10.
The term of the second-order moment ofx(t) may imply the moments of order 2, which in the wide sense or in general include mean square (7) and ACF (8).Note 11.
If we consider the moments ofx(t) up to 2, x(t) is called 2-order random function, which plays a role in engineering. The moments of orders higher than 2 correspond to the case of higher order statistics, which we do not discuss in this paper.


## 2.1.3. PSD

The Fourier transform of the ACFr(t,s) is given by
(10)S(ω,t)=∫-∞∞r(t,s)e-jωsds,j=-1.
It represents the energy distribution of x(t).Note 12.
In general,mn(t) is time dependent. Therefore, the mean, mean square, ACF, and PSD may generally be time dependent. In the stationary case, they are independent of time.


## 2.1.4. Weak Stationarity

If all moments ofx(t) do not vary with time, x(t) has the property of strong stationarity. If the moments up to 2 are independent of time, irrelevant of the moments of order higher than 2, we say that x(t) is of weak stationarity or stationary in the wide sense.Note 13.
In the case of weak stationarity,μ(t) and Ψ(t) are constants. The ACF only replies on the time lag τ=|t-s|. Hence, r(t,s)=r(τ). Consequently, S(ω,t)=S(ω).


## 2.2. Central Moment

Often, one may be interested in a random function with mean zero. For random functions with mean zero, the previous expression regarding the moment (5) is extended to the central moment expressed by
(11)mcn(t)=E{[x(t)-μ(t)]n}=∫-∞∞[x(t)-μ(t)]np(x,t)dx.


### 2.2.1. Variance and Standard Deviation

The central moment of order 2 given by(12)mc2(t)=E{[x(t)-μ(t)]2}=∫-∞∞[x(t)-μ(t)]2p(x,t)dx
is usually denoted by σ2(t) called the variance of x(t). The standard deviation, denoted by stdev(t), is given by
(13)stdev(t)=σ2(t)=σ(t).Note 14.
How much the variation ofx(t) away from its mean μ(t) is characterized by its variance or standard deviation.Remark 2.
Analysis of variance (ANOVA) is a branch of statistics, which plays a role in many aspects of techniques, especially in the fields of statistics tests and experimental design [21–23].


### 2.2.2. Autocovariance

In the case of mean zero, one uses the autocovariance function denoted byC(t1,t2) (ACF for short again) to characterize the correlation property of [x(t)-μ(t)]. It may be given by
(14)C(t1,t2)=E{[x(t1)-μ(t1)][x(t2)-μ(t2)]}=∬-∞∞[x(t1)-μ(t1)][x(t2)-μ(t2)]×p(x1,t1;x2,t2)dx1dx2.Note 15.
Whent1=t2=t, C(t1,t2) reduces to σ2(t):
(15)C(t,t)=E{[x(t)-μ(t)]2}=σ2(t).Remark 3.
ACF analysis is an important branch in statistics; see, for example, [19, 23–28].Remark 4.
A Gaussian random function is uniquely determined by its ACF [29, 30].
As a matter of fact, the PDF of a Gaussian random function is given by(16)p(x)=12πσexp[-(x-μ)22σ2],-∞<x<∞.
In (16), σ can be determined by (15) while μ can be obtained from the following:
(17)C(t,t)=r(t,t)-μ2(t).
Hence, Remark 4 results.Note 16.
Ifx(t) is weak stationary, its μ(t) and σ(t) are constants. Its ACF depends only on lag:
(18)C(t1,t2)=C(|t1-t2|)=C(τ),τ=|t1-t2|.
We list two properties of ACF below.P1:
ACF is an even function:r(τ)=r(-τ), C(τ)=C(-τ).P2:
r(0)≥r(τ), C(0)≥C(τ).Note 17.
P1 is obvious because the correlation betweenx(t1) and x(t2) is always equal to that between x(t2) and x(t1). P2 is natural because the correlation between the same point x(t1) and x(t1) always reaches its maximum.Without loss of generality for the statistical analysis of random functions, one may adopt the concept of normalized random functions. By normalized, we meanr(0)=1 or C(0)=1. Therefore, a normalized random function may be obtained by x(t)/C(t,t).


## 2.2.1. Variance and Standard Deviation

The central moment of order 2 given by(12)mc2(t)=E{[x(t)-μ(t)]2}=∫-∞∞[x(t)-μ(t)]2p(x,t)dx
is usually denoted by σ2(t) called the variance of x(t). The standard deviation, denoted by stdev(t), is given by
(13)stdev(t)=σ2(t)=σ(t).Note 14.
How much the variation ofx(t) away from its mean μ(t) is characterized by its variance or standard deviation.Remark 2.
Analysis of variance (ANOVA) is a branch of statistics, which plays a role in many aspects of techniques, especially in the fields of statistics tests and experimental design [21–23].


## 2.2.2. Autocovariance

In the case of mean zero, one uses the autocovariance function denoted byC(t1,t2) (ACF for short again) to characterize the correlation property of [x(t)-μ(t)]. It may be given by
(14)C(t1,t2)=E{[x(t1)-μ(t1)][x(t2)-μ(t2)]}=∬-∞∞[x(t1)-μ(t1)][x(t2)-μ(t2)]×p(x1,t1;x2,t2)dx1dx2.Note 15.
Whent1=t2=t, C(t1,t2) reduces to σ2(t):
(15)C(t,t)=E{[x(t)-μ(t)]2}=σ2(t).Remark 3.
ACF analysis is an important branch in statistics; see, for example, [19, 23–28].Remark 4.
A Gaussian random function is uniquely determined by its ACF [29, 30].
As a matter of fact, the PDF of a Gaussian random function is given by(16)p(x)=12πσexp[-(x-μ)22σ2],-∞<x<∞.
In (16), σ can be determined by (15) while μ can be obtained from the following:
(17)C(t,t)=r(t,t)-μ2(t).
Hence, Remark 4 results.Note 16.
Ifx(t) is weak stationary, its μ(t) and σ(t) are constants. Its ACF depends only on lag:
(18)C(t1,t2)=C(|t1-t2|)=C(τ),τ=|t1-t2|.
We list two properties of ACF below.P1:
ACF is an even function:r(τ)=r(-τ), C(τ)=C(-τ).P2:
r(0)≥r(τ), C(0)≥C(τ).Note 17.
P1 is obvious because the correlation betweenx(t1) and x(t2) is always equal to that between x(t2) and x(t1). P2 is natural because the correlation between the same point x(t1) and x(t1) always reaches its maximum.Without loss of generality for the statistical analysis of random functions, one may adopt the concept of normalized random functions. By normalized, we meanr(0)=1 or C(0)=1. Therefore, a normalized random function may be obtained by x(t)/C(t,t).


## 2.3. Computational Methods

Previous expressions in (5)~(15) regarding the mean, variance, and ACF of a random function x(t) are associated with its PDF. That implies that they can be determined under the condition that the PDF is known. However, that may usually be too restrictive in practical applications in engineering. Fortunately, Wiener et al. proposed a computation approach using time average without relating to its PDF if x(t) is ergodic [18, 31, 32].Note 18.
It may be very difficult if not impossible for one to test the ergodicity by a sample function of a traffic trace. In practice, one may simply assume that a traffic tracex(t) is ergodic.In what follows, we suppose thatx(t) is causal. By causal, we mean that x(t) is defined for 0≤t<∞ and x(t) = 0 for t<0. In addition, we only consider x(t) in the weak stationary sense. By using the time average, therefore, the mean of x(t) is given by
(19)μ=E[x(t)]=limT→∞1T∫0Tx(t)dt.
Its mean square is written by
(20)Ψ=E[x2(t)]=limT→∞1T∫0Tx2(t)dt.
Its ACF is expressed by
(21)r(τ)=E[x(t)x(t+τ)]=limT→∞1T∫0Tx(t)x(t+τ)dt.
Its variance is given by
(22)σ2=E{[x(t)-μ]2}=limT→∞1T∫0T[x(t)-μ]2dt.
Similarly, its autocovariance is given by
(23)C(τ)=E{[x(t)-μ][x(t+τ)-μ]}=limT→∞1T∫0T[x(t)-μ][x(t+τ)-μ]dt.In what follows, we only consider random functions with mean zero. Accordingly,r(τ) is equal to C(τ), and Ψ=σ2 unless otherwise stated.We write the PSD ofx(t) by
(24)S(ω)=∫-∞∞r(τ)e-jωτdτ.
Alternatively, r(τ) can be expressed by
(25)r(τ)=12π∫-∞∞S(ω)ejωτdω.


## 2.4. Defaulted Assumptions in Conventional Time Series

In the field of conventional time series, the following assumptions are usually defaulted [18, 21–37].(i)
The mean ofx(t) exists.(ii)
The variance ofx(t) exists.(iii)
S(0)=∫-∞∞r(τ)dτ is convergent.However, the above may be untrue for LRD traffic; see, for example, [16, 38, 39], which we shall not discuss more in this paper.


## 3. Smoothing Sample ACF of Traffic

Previous discussions require that-∞<t<∞. Even in the case of x(t) being causal, 0<t<∞ is always required. However, that requirement may not be satisfied in practice in general since traffic x(t) can be measured only in a finite time interval.


### 3.1. Sample ACF

Suppose that one records trafficx(t) in [0,T]. Then, he or she attains a sample ACF of x(t), which may be estimated by r1(τ):
(26)r1(τ)=1T∫0Tx(t)x(t+τ)dt.Note 19.
The sample ACFr1(τ) may yet be a representative of the true ACF r(τ) in a way. Mathematically, r1(τ)=r(τ) under the condition of T→∞. Unfortunately, the condition T→∞ may be physically unrealizable.Now, assume that there is another person who measures the traffic at the same point in networks, but he does the measurement in the time interval[T,2T]. Then, the sample ACF is obtained by
(27)r2(τ)=1T∫T2Tx(t)x(t+τ)dt.
Due to the randomness of x(t), errors in numerical computations, and errors in the measurement of traffic data, though the width of [T,2T] is equal to that of [0,T], one has, in general,
(28)r2(τ)≠r1(τ).Denote byrn(τ) the sample ACF of x(t) in the interval [(n-1)T,nT] for n=1,2,…,N. Then,
(29)rn(τ)=1T∫(n-1)TnTx(t)x(t+τ)dt.
For the similar reasons we explained in (28), one generally has
(30)rm(τ)≠rn(τ)form≠n.Note 20.
It may be quite reasonable to consider each sample ACFrn(τ) as an estimate of the true ACF of x(t), but neither may be so appropriate unless T is large enough. In fact, rn(τ) is a random variable [32].


### 3.2. Smoothed Sample ACF

Denote byr^(τ) the ACF estimate of x(t). The estimate r^(τ) is a random variable again. It has its distribution in the general form of (31). The issue studying the concrete form of (31) is interesting, but it is beyond the scope of this paper:
(31)Prob[r^(τ)].
In this research, we are interested in good estimate of r(τ). By good estimate, we mean that both its bias and variance are small. Since
(32)E[rn(τ)]=1T∫(n-1)TnTE[x(t)x(t+τ)]dt=r(τ),
the sample ACF rn(τ) is unbiased. Therefore, what one is interested in is to find a way such that Var[r^(τ)] is small. The literature about this is relatively rich; see, for example, [31] and references therein. A simple way to reduce Var[r^(τ)] is average. That is, one may compute r^(τ) by the average of the sample ACFs as follows assuming that both limT→∞rn(τ) and limN→∞r^(τ) exist:
(33)r^(τ)=1N∑n=1Nrn(τ).
In that case, Var[r^(τ)] is inversely proportional to N [31]:
(34)Var[r^(τ)]isproportionalto1N.The above implies the assumptions that bothlimT→∞rn(τ) and limN→∞r^(τ) exist. The research of whether limT→∞rn(τ) or limN→∞r^(τ) exists is attractive, but it is out of the scope of the paper. In the experimental research discussed in this paper, we assume that both exist.Note 21.
The previous expression needs, for the purpose of ACF estimation of real-trafficx(t), purposely sectioning the sample record of a traffic trace x(t) into a set of blocks such that the number of blocks, that is, the average count N, is large enough for the desired level of Var[r^(τ)].Note 22.
ACF estimater^(τ) is the average of the sample ACFs or the sum of the sample ACFs divided by N. Other smoothing methods are available; see, for example, [40].The previous discussions take the usage of integral. In numerical computations, the integral above should be replaced by summation. In the discrete case, we replaceT by I for i=1,2,…,I. In addition, rn(τ) is replaced by rn(k) and x(t) by x(i). Thus, we have
(35)rn(k)=1I∑(n-1)InIx(i)x(i+k).The above computation does not follow (35) directly. In practice, the fast Fourier transform (FFT) and its inverse (IFFT) are suggested. More precisely, in the interval [(n-1)I,nI], according to the Wiener theorem [18–20, 23, 31, 32, 34, 35], we have
(36)rn(k)=IFFT{|FFT[x(i)]|2}for(n-1)I≤i≤nI.
Then,
(37)r^(k)=1N∑n=1Nrn(k).Note 23.
Usually,I as well as N take the form of 2M, where M is a positive integer.Note 24.
Ifx(i) is for i=0,1,…,I-1, the part of rn(k) for k=0,1,…,(I-1)/2 is enough for the analysis purpose because rn(k)=rn(-k). For example, when one sets I=1024, rn(k) is for k=0,1,…,511.


## 3.1. Sample ACF

Suppose that one records trafficx(t) in [0,T]. Then, he or she attains a sample ACF of x(t), which may be estimated by r1(τ):
(26)r1(τ)=1T∫0Tx(t)x(t+τ)dt.Note 19.
The sample ACFr1(τ) may yet be a representative of the true ACF r(τ) in a way. Mathematically, r1(τ)=r(τ) under the condition of T→∞. Unfortunately, the condition T→∞ may be physically unrealizable.Now, assume that there is another person who measures the traffic at the same point in networks, but he does the measurement in the time interval[T,2T]. Then, the sample ACF is obtained by
(27)r2(τ)=1T∫T2Tx(t)x(t+τ)dt.
Due to the randomness of x(t), errors in numerical computations, and errors in the measurement of traffic data, though the width of [T,2T] is equal to that of [0,T], one has, in general,
(28)r2(τ)≠r1(τ).Denote byrn(τ) the sample ACF of x(t) in the interval [(n-1)T,nT] for n=1,2,…,N. Then,
(29)rn(τ)=1T∫(n-1)TnTx(t)x(t+τ)dt.
For the similar reasons we explained in (28), one generally has
(30)rm(τ)≠rn(τ)form≠n.Note 20.
It may be quite reasonable to consider each sample ACFrn(τ) as an estimate of the true ACF of x(t), but neither may be so appropriate unless T is large enough. In fact, rn(τ) is a random variable [32].


## 3.2. Smoothed Sample ACF

Denote byr^(τ) the ACF estimate of x(t). The estimate r^(τ) is a random variable again. It has its distribution in the general form of (31). The issue studying the concrete form of (31) is interesting, but it is beyond the scope of this paper:
(31)Prob[r^(τ)].
In this research, we are interested in good estimate of r(τ). By good estimate, we mean that both its bias and variance are small. Since
(32)E[rn(τ)]=1T∫(n-1)TnTE[x(t)x(t+τ)]dt=r(τ),
the sample ACF rn(τ) is unbiased. Therefore, what one is interested in is to find a way such that Var[r^(τ)] is small. The literature about this is relatively rich; see, for example, [31] and references therein. A simple way to reduce Var[r^(τ)] is average. That is, one may compute r^(τ) by the average of the sample ACFs as follows assuming that both limT→∞rn(τ) and limN→∞r^(τ) exist:
(33)r^(τ)=1N∑n=1Nrn(τ).
In that case, Var[r^(τ)] is inversely proportional to N [31]:
(34)Var[r^(τ)]isproportionalto1N.The above implies the assumptions that bothlimT→∞rn(τ) and limN→∞r^(τ) exist. The research of whether limT→∞rn(τ) or limN→∞r^(τ) exists is attractive, but it is out of the scope of the paper. In the experimental research discussed in this paper, we assume that both exist.Note 21.
The previous expression needs, for the purpose of ACF estimation of real-trafficx(t), purposely sectioning the sample record of a traffic trace x(t) into a set of blocks such that the number of blocks, that is, the average count N, is large enough for the desired level of Var[r^(τ)].Note 22.
ACF estimater^(τ) is the average of the sample ACFs or the sum of the sample ACFs divided by N. Other smoothing methods are available; see, for example, [40].The previous discussions take the usage of integral. In numerical computations, the integral above should be replaced by summation. In the discrete case, we replaceT by I for i=1,2,…,I. In addition, rn(τ) is replaced by rn(k) and x(t) by x(i). Thus, we have
(35)rn(k)=1I∑(n-1)InIx(i)x(i+k).The above computation does not follow (35) directly. In practice, the fast Fourier transform (FFT) and its inverse (IFFT) are suggested. More precisely, in the interval [(n-1)I,nI], according to the Wiener theorem [18–20, 23, 31, 32, 34, 35], we have
(36)rn(k)=IFFT{|FFT[x(i)]|2}for(n-1)I≤i≤nI.
Then,
(37)r^(k)=1N∑n=1Nrn(k).Note 23.
Usually,I as well as N take the form of 2M, where M is a positive integer.Note 24.
Ifx(i) is for i=0,1,…,I-1, the part of rn(k) for k=0,1,…,(I-1)/2 is enough for the analysis purpose because rn(k)=rn(-k). For example, when one sets I=1024, rn(k) is for k=0,1,…,511.


## 4. A Case Study

Using the real-traffic trace BC-Aug89 in this case study, we setI=2048. Figure 2 illustrates the 16 sample ACFs for i∈[(n-1)2048,n2048] with n=1,…,16. The ordinate is in log. From Figure 3, we see that sample ACFs rn(k) differ from each other. Each sample ACF consists of a certain amount of fluctuations.Illustrations of sample ACFs. (a)r1(k). (b) r2(k). (c) r3(k). (d) r4(k). (e) r5(k). (f) r6(k). (g) r7(k). (h) r8(k). (i) r9(k). (j) r10(k). (k) r11(k). (l) r12(k). (m) r13(k). (n) r14(k). (o) r15(k). (p) r16(k).
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
(j)
(k)
(l)
(m)
(n)
(o)
(p)Using the technique of average may reduce the variance of the sample ACF. Denote byR16(k) the average of rn(k) for n=1,…,16. Denote by R32(k) the average of rn(k) for n=1,…,32. Denote by R64(k) the average of rn(k) for n=1,…,64. Figures 4, 5, and 6, respectively, indicate the smoothed sample ACFs R16(k), R32(k), and R64(k). It can be seen that the fluctuations in Figure 3 are considerably reduced in R16(k). As a result, the larger the average count, the smoother the curve of the sample ACF estimate; see Figures 5 and 6.Figure 4
Smoothed sample ACF with average count 16.Figure 5
Smoothed sample ACF with average count 32.Figure 6
Smoothed sample ACF with average count 64.Note 25.
ThoughVar[r^(τ)] is inversely proportional to the averages count N, over-large N may be unnecessary for improving an estimate. For instance, by eye, one may see that the one in Figure 6 does not show much improvement as that in Figure 5.


## 5. Discussions and Future Work

The previous exhibits the obvious effects of smoothing sample ACFs by average. However, there are critical points that need discussions regarding the smoothing of sample ACFs of traffic.Traffic is LRD [1–5]. According to Taqqu’s law, it is heavy tailed [41]. Resnick et al. [42] explained an important result in the aspect of sample ACF of heavy-tailed time series. It was stated in [42] that the sample ACF of heavy-tailed series may be random when the sample size approaches infinity if the series is with infinite variance. The case study in Section 4 demonstrates that the sum of sample ACFs is convergent. Consequently, the sample ACF is convergent too. Thus, may we infer that traffic, at least the data used there, is with finite variance? The answer to that question may be desired in traffic theory. We shall work on it in the future.Finally, it is noted that the relationship between the sample size and the variance of the sample ACF refers to [43]. In addition, the relationship between the sample size and the variance bound of the sample ACF of fractional Gaussian noise with LRD is described in [44].


## 6. Conclusions

We have discussed the smooth effect of sample ACFs of traffic by average. Future research whether traffic is with finite variance or infinite one has been noted.



---

*Source: 631498-2013-06-13.xml*