Fitting Fractional Brownian Motion

In the following we compare fractional Brownian motion (FBM) sources to their fitted MAP models. The FBM is a self-similar continuous time continuous valued stochastic process whose increment is fractional Gaussian noise [47]. As a traffic source model it is defined by three parameters: the mean input rate (E[N1]), the variance parameter (V ar[N1]), and the self-similarity parameter (H). One way to use FBM as a traffic model is to consider its increments in subsequent intervals as the amount of data arrived to the network [55]. To compare the FBM source with a MAP the increments has to be rounded to an integer value and negative values has to be substituted by 0. This way we are given the number of arrivals in each time-slot. For queuing analysis the arrival instances have to be given. Given the number of arrivals in an interval, we assume that the arrival instance of each arrival is distributed uniformly in the interval.

We used the method described by Paxson [61] to generate FBM traffic. The parameters of the traffic were E[N1] = 5, V ar[N1] = 50 and H = 0.8. Figure 8.17 gives variance-time plots for the fitted MAP models for different timepoints of setting IDC, while Figure 8.18 depicts the queuing experiments with 80 % utilization.

As for the first two measured datasets, the approximation of the queueing behavior is poor. In this case too, the irregularity in the long-term behavior can be the reason. For the FBM itself the long-term behavior is completely described by the Hurst parameter. However, since we need non-negative integer values, an altered version of the FBM trace is used as traffic trace whose long-term behavior is more complex.

Figure 8.19 stresses the importance of the analytic analysis of approximating traffic traces. In the figure one may observe how the variance-time plot of the arrival trace generated using a MAP approaches the analytically computed variance-time plot as the number of the generated arrivals increases. The importance of analytic analysis may be seen looking at the numerical parameters of the resulting models

1e-05

1 10 100 1000 10000 100000 1e+06 1e+07

Variance

Figure 8.17: MAPs with different timepoints of IDC matching for the traffic generated by FBM

1e-06

Figure 8.18: Queue length distribution for the traf-fic generated by FBM

1e-05 0.0001 0.001 0.01 0.1 1

1 10 100 1000 10000 100000 1e+06 1e+07

Variance

Aggregation level

analytic, (2,1) 1e7 arrivals 1e6 arrivals

Figure 8.19: Variance-time plots of the generated traffic traces

as well. For the first approximation of the third measured trace the initial probability of the slowest phase of the hyperexponential PH distribution is about 2 × 10⁻⁹, the intensity of this phase is about 2.5 × 10⁻⁷. The MMPP with which this PH arrival process is superposed has mean arrival rate equal to 0.75. Based on these numbers it is clear that generating 10¹⁶arrivals is hardly enough to see the steady state properties of the MAP.

Chapter 9

A Markovian Point Process

Exhibiting Multifractal Behavior and its Application to Traffic Modeling

The statistical analysis of some experimental traffic traces suggested a self-similar behavior over a range of time scales [78]. Since measured data sets are finite (the large ones contain 10⁶− 10⁸ samples) the statistical properties of these data sets could be studied only over a range of time scales and the asymptotic behavior is determined from the range of known time scales.

The importance of the observed self-similar behavior lies in the fact that the queue length and the waiting time distribution of packet queues with self-similar traffic significantly differs from the ones with

“regular traffic”.

In the early 90’s the research was focused on checking the self-similar behavior and the evaluation of the scaling parameter of self-similarity (referred to as Hurst parameter). It has to be noted that the majority of the practically applied statistical tests (e.g., variance-time plot, R/S plot) checks only the second order properties of the data sets and provides information only on the second order self-similarity of the analyzed data set. (Actually, there are self-similar processes, like the fractional Gaussian noise [55], that are completely characterized by their first and second order behavior, but measured data sets are usually far more complex).

The first observations of self-similarity in measured traffic processes resulted in a fertile research for applying complex mathematical models in traffic engineering. The two main goals of these research efforts were to find “solvable” mathematical models with identical (or similar) properties and to create random sequence generators with predefined statistical properties. Some of the considered models are: fractional

Gaussian noise [47, 55], traditional [14] and fractional ARIMA process [30], fractal [71] and Markovian models (MMPP, MAP) [2, 69, 35]. A valuable advantage of Markovian models is that effective numer-ical methods are available to analyze systems with Markovian arrival processes [52, 43]. Furthermore, Markovian models also represent a simple and computationally effective way of generating random data series.

Unfortunately, some of the statistical properties of measured data sets differ from the ones of self-similar processes. The fact that the observed scaling behavior differs from the one of self-self-similar processes suggested the application of multifractal models to better capture the behavior of measured data sets [26]. A common approach to study multifractal models is wavelet analysis. Riedi et al. proposed a wavelet model to approximate the scaling behavior of measured data sets and based on this model they presented an algorithm to generate random sequences with similar scaling behavior [67]. The proposed method shows a good fit according to several statistical tests, but it is computationally rather expensive and does not allow any numerical analysis of queues.

Based on the mentioned advantages of Markovian models there is a need to approximate multifractal behavior with Markovian models. In this paper we propose Markovian models of a special structure to approximate the multifractal scaling behavior of measured data sets.

The flexibility of Markovian models in exhibiting complex stochastic behavior along the practically interesting time scales is known from previous works [69, 2, 35]. This paper attempts to extend this set of results with approximating multifractal models. The proposed MAP structure is motivated by the unnormalized Haar wavelet transform representation of finite sequences as it is applied also in the multifractal wavelet model of Riedi et al. [67].

The rest of the chapter is organized as follows. The proposed MAP structure, its analysis and a simple parameter estimation procedure are introduced in Section 9.1. Section 9.2 investigates various numerical properties of the proposed MAP structure and gives an example of fitting to a measured data set.

9.1 The Proposed MAP Structure

To exhibit multifractal behavior we propose to apply a special MAP, a Markov modulated Poisson process (MMPP) whose background CTMC has a symmetric¹ n-dimensional cube structure and the arrival intensities are set according to the variation of the arrival process at the different time scales. We believe that other MAP structures can also exhibit multifractal behavior. Our special choice is motivated by the generation of the Haar wavelet transform. Basically the Haar wavelet transform evaluates the variation of the data set at different aggregation levels (time scales), and similarly, the proposed MAP

structure provides different variation of the arrival rate at different time scales.

The composition of the proposed MAP structure follows a very similar pattern as the generation of the Haar wavelet transform. Without loss of generality, we assume that the time unit is such that the long-term arrival intensity is one. A MAP of one state with arrival rate 1 represents the arrival process at the largest (considered) time scale. This MAP, which corresponds to the zero-dimensional cube, is represented by the infinetisimal generator of its underlying Markov chain

Q⁽⁰⁾ = [ 0 ] and by D1(0)= [ 1 ] . (9.1)

Note that D0(0)

can be obtained simply as

D0(0)= Q⁽⁰⁾− D¹⁽⁰⁾. (9.2)

Assuming that we are given the descriptors having n − 1 dimensions, Q⁽ⁿ⁻¹⁾ and D1(n−1), the nth dimension is introduced as

where ⊕ and ⊗ stand for Kronecker sum and Kronecker product, respectively.

To picture the construction, hereinafter we give the descriptors for the one-, two-, and three-dimensional cases. In order to keep the matrices readable, zero-entries are omitted and diagonal elements of the generator of the underlying Markov chain are signed with •. The descriptors are

Q⁽¹⁾=

D1(2)=

An n-level MAP of the proposed structure is composed by 2ⁿ states and it has n + 2 parameters.

Parameters γ and λ define the considered time scales, and parameters a1, a2, . . . , andetermine the variance of the arrival process at the n considered time scales. It can be seen that the ratio of the largest and the smallest considered time scales is γⁿ. Having a fixed n (i.e., fixed cardinality of the MAP), any ratio of the largest and the smallest considered time scales can be captured by using a sufficiently large γ.