A New Multifractal Model based on Multiplicative Cascade

INTRODUCTION

The complexity of modern communication network leads to a total change in modeling of teletraffic data, so that we should analyze and design a new generation of network protocols and network management to improve the network Quality of Service (QoS). Various models based on self-similarity theory and monofractal processes have been adequately studied, e.g., fARIMA model proposed for video traffic (Garret and Willinger, 1994), the forecasting method using fractals proposed for software system (Cao and Zhu, 2010). However, the study of Feldmann et al. (1998, 1999) has showed that Wide Area Network (WAN) traffic data possesses more complex behavior of multi-scaling, making the monofractal models inadequate in describing the WAN traffic.

Multifractal cascades (Krishna et al., 2003) were proposed as a possible model for broadband traffic data. This is a relatively new territory for multiplier cascade process to establish a network traffic model. Multifractal Wavelet Model (MWM) proposed by Riedi et al. (1999) and Variable Variance Gaussian Multiplier (V.V.G.M) model proposed by Krishna et al. (2003) are both based on the multifractal cascade. The V.V.G.M model is simpler than the MWM and computationally less complex. Moreover, V.V.G.M is also superior to MWM in the statistical properties. Although, Gaussian distribution could well model a lot of optimal system about the signal and noise, it is not suitable for describing the non-Gaussian (especially the heavy-tailed) signals.

In this study, a new network traffic model named Variable Scale parameter Cauchy Multiplier (V.S.C.M) model is proposed, which is based on the binomial multiplicative multifractal cascade processes. On comparison of the multifractal performance between the original data and the V.S.C.M process, the Cauchy model with variable scale parameter can fit binomial random multiplier very well.

MULTIFRACTAL OF THE NETWORK TRAFFIC

For detecting the multifractal nature of the traffic data, a key parameter is the multifractal spectrum f(α). Moment method for estimating the spectrum (Wang et al., 2009) is adopted. Suppose random data set is considered as a sampling of the multiplier estimators on the interval [0,1] at a scale of 1/2^N.

Partition function: We use an intermediate parameter partition function (Krishna et al., 2003) and it is defined as:

(1)

where,

with a fixed value m. The partition function depends on the scaling nature exhibited by the value m, it is as follow:

(2)

taking logarithms, we can get:

Fig. 1:	Partition function of Aug89 traffic

(3)

where, C is a constant. If log χ^X_m(q) exhibits linearity with log m, it indicates that the data is multifractal in nature.

Multifractal spectrum: τ(q) is the slope of log-log regression curve. With the discussion of literature (Okoroafor, 2008; Wang et al., 2009), the multifractal spectrum can be obtained by Legendre Transform (Krishna et al., 2003) of τ(q). The relation is as follows:

(4)

where, α is the local Hölder exponent. The local Hölder exponent of monofractal is a constant, so if α changes largely in the multifractal spectrum, the traffic data is considered as multifractal. Our original traffic data (file BC-pAug89.tl) contains 2¹⁶ byte-level traffic at the scale of 0.01s, which was collected by Bellcore researchers in August 1989(named Aug89). The data can be considered as the multiplicative cascade data at stage 16. Figure 1 is the partition function and Fig. 2 is the multifractal spectrum. It indicates that the data is multifractal in nature.

BINOMIAL MULTIPLICATIVE CASCADE

For modeling binomial multiplicative cascade (Vieira and Ling 2006), we expect that the multipliers of every stage are different and we can obtain the multiplier from a certain distribution.

There is a unit interval [0, 1]. At each stage, this measure is divided by multiplying with ratios r and 1-r. Suppose the initial measure is preserved, random multiplier r_j is chosen from a probability distribution fR_j (r_j) at stage j (0≤r_j≤1). If fR_j (r_j) is symmetric about:

Fig. 2:	Multifractal spectrum f(α) of Aug89 traffic

Fig. 3:	Binomial cascade process

so that both r_j and 1-r_j have the same probability distribution.

And here, X^N_i(i = 1,...,2^N) denotes the cascade construction at stage N. Every point in X^N_i can be expressed as the product of several random variable μ_i = m₁m₂...m_N, where, m_j, (j = 1,...,N) indicates random variable r_j or 1-r_j. Figure 3 illustrates the above concept (r_ji is the specific values of the random number r_j).

ESTIMATION OF MULTIPLIER DISTRIBUTIONS

X^N_i(i = 1,...,2^N) is the data at stage N (with the resolution 2^-N), so the data at stage (N-1) is obtained by aggregating the consecutive values at stage N over non overlapping blocks of size two. As the same, if we have the data at stage (N-j), X_i^N-j(i = 1,...,2^N-j), then the data at stage (N-j-1) (lesser resolution 2^-(N-j-1)) can be obtained by using the same method as above:

(5)

Fig. 4:	Stage 5 histogram and stage 6 histogram of multipliers. (a) Multiplier distribution between stage 5 and 6 and (b) multiplier distribution between stage 6 and 7

Fig. 5:	Estimation of Cauchy distribution. (a) Measured position parameter α and (b) Measure scale parameter b

When the aggregates form one point at the coarsest scale, stop the procedure. The multipliers from stage j to j+1 can be written as (Vieira and Ling, 2006).

(6)

where,

are the samples of the multiplier distribution fR_j(r_j) at stage j. We can obtain the multiplier distribution at stage j from the histogram.

We aggregate the original data (Aug89) according to the algorithm mentioned earlier. Figure 4a and b shows the probability density function for the multipliers between stage 5 and 6 and stage 6 and 7, respectively.

The variable scale parameter Cauchy multiplier: It can be seen from the Fig. 4 that taking a Cauchy distribution of the appropriate parameter as the multipliers distribution is more suitable than the Gaussian distribution. The Cauchy distributions are centered at α = 0.5 (Fig. 5a), but scale parameter b of the Cauchy distributions is varied with the stage (Fig. 5b). Using the curve fitting techniques, the equation for the scale parameter b can be written as:

(7)

where, j (j = 1,....,16) is the stage.

In summary, we start from the coarsest value of aggregate and multiply it with multiplier values chosen from the aforementioned distribution. Finally, we obtain the synthesized data at stage N. The model is named as V.S.C.M model.

SIMULATION RESULTS

In this study, we aggregate the initial traffic data (Aug89) to obtain the coarsest value. Begin with this value, generate random numbers obeying C(0.5,b(j)) distribution at stage j; multiply the starting aggregate value by multipliers generated at each stage.

Fig. 6:	Comparison of high order moments. (a) The 1st moment, (b) The 2nd moment, (c) The 3rd moment and (d) The 4th moment

Fig. 7:	Partition function: V.S.C.M

The comparison of the moments of aggregated data and original data is shown in Fig. 6a-d. It can be seen that V.S.C.M model best fits the statistical nature of data for all moments up to 4.

Same as Fig. 1 and 7 show log-log partition function of V.S.C.M aggregated data. Visually, the logχ^X_m(q) of original data exhibits linearity with logm, so is the aggregated data.

Fig. 8:	Comparison of τ(q)

Moreover, the slops of the two are basically the same. It is illustrated that the aggregated data is multifractal in nature.

Figure 8 compares the τ(q) of original data and aggregated data and Fig. 9 compares the f(α) curve. This shows that α changes in a large range, which is also clearly illustrated that the aggregated data is multifractal in nature.

Fig. 9:	Comparison of f(α)