Self-similar Network Traffic

The observation that traffic in packet-switched networks shows self-similar and long-range dependent behaviour goes back to local area Ethernet investigations made by Willinger et al. [4]. In the sequel, a lot of empiric studies have been made that confirm the self-similar nature of packet-switched traffic in local and wide area networks and for different kinds of applications [5]. While exact or asymptotic self-similarity does not always exactly fit to observed empiric traffic samples, it still comes closer to empiric observations than Poisson-based traffic models do. In particular, the effects of burstiness at different time scales and long-range dependence (see below) cannot be modelled by Poisson traffic models.

Mathematically speaking, let $\hat{Y}(t), \ t > 0$ be the number of packets traversing a link during the time interval $[t, t + \delta_t).$ Then the properties of the sequence $\hat{X}_1, \hat{X}_2, \ldots, \hat{X}_m, \ m \in \mathbb{N}$ with

$$\hat{X}_k := \hat{Y} (k \cdot \delta_t), \ k \in [1..n]$$

are investigated. $\hat{Y}(t)$ and $\hat{X}_k$ are assumed to be realizations of stationary stochastic processes $(Y(t), \ t \geq 0)$ and $(X_k, \ k \in \mathbb{N}),$ respectively. In the following, the description of the properties of self-similar time series will concentrate on the theoretical values $Y(t)$ and $X_k.$ It should be clear, that the empirically observed number of packets must be interpreted as realizations of these stochastic processes.

For the analysis of the properties of the time series $(X_k, \ k \in \mathbb{N}),$ it makes sense to introduce the scaled sample

$$X^{(m)}_k := \frac{1}{m} \left[ X_{(k-1)m + 1} + \cdots + X_{km} \right],$$

the scaled variance

$$\sigma^{(m)} := \frac{1}{n_m - 1} \sum_{k=1}^{n_m} X^{(m)}_k - \bar{X}^{(m)},$$

where $n_m$ denotes the number of scaled samples (it is assumed that $n / n_m \in \mathbb{N}$) and $\bar{X}^{(m)}$ denotes the mean

$$\bar{X}^{(m)} := \frac{1}{n_m} \sum_{k=1}^{n_m} X^{(k)} \ \left(= \frac{1}{n} \sum_{k=1}^{n} X_k \right),$$

and the autocorrelation functions

$$\rho(k) := \frac{E(X_l - \mu) \cdot E(X_{l+k} - \mu)}{Var(X_l)}$$

and

$$\rho^{(m)}(k) := \frac{E(X^{(m)}_l - \mu) \cdot E(X^{(m)}_{l+k} - \mu)}{Var(X^{(m)}_l)},$$

respectively.

The following definition is taken from [7].
Definition: The time series $X := (X_k, \ k \in \mathbb{N})$ is called asymptotically second order self-similar with self-similarity parameter or Hurst parameter $H ,$ if the second-order statistics of $m^{1-H} x$ converge as follows:

$$\lim_{m \to \infty} m^{1-H} \sigma^{(m)} = \sigma^2 0 < \sigma^2 < \infty.$$ (1)

$$\lim_{m \to \infty} \rho^{(m)}(k) = \frac{1}{2} \left[ (k+1)^{2H} - 2k^{2H} + (k-1)^{2h} \right].$$ (2)

If equities (1) and (2) are valid for all $m \in \mathbb{N}$ and not only for the limit, the time series is said to be exactly self-similar of second order.
$\Box$

For the modeling of traffic in packet-switched networks, only the range $1/2 < H < 1$ is relevant. With the presented mathematical framework, the main properties of self-similar time series with $H$ within this range can be expressed as follows [1]

• burstiness at different time scales / high variability
  The variability of the samples $X^{(m)}_1, X^{(m)}_2, \ldots$ remains high with increasing $m,$ which means that
  $$\sigma^{(m)} \sim c \cdot m^{2H}$$    for large $$m.$$
• slowly decaying autocorrelation function
  Slowly decaying in this context means that the autocorrelation function $\rho(k), \ k \in \mathbb{N}$ of the stochastic process $(X_k, \ k \in \mathbb{N}),$ decays as $c_1 \cdot k^{-\alpha}$ for large $k$ with some $c_1 > 0$ and some $0 < \alpha < 1.$ In contrast, Poisson traffic has exponential decay $(\rho(k) \sim c_2 \cdot \beta^{-k}, \ 0 < \beta < 1$ for large $k).$ As a consequence, for long-range-dependent traffic, we have $\sum_{k} \rho(k) = \infty$ (for Poisson traffic: $\sum_{k} \rho(k) < \infty$).

There are a variety of methods for the generation of self-similar and long-range dependent traffic for simulation experiments:

1. Superposition of alternating renewal processes with power-tailed soujourn distributions
   An alternating renewal process has two states ON and OFF which are alternately visited. The superposition of multiple ON-OFF-processes with power-tailed sojourn distributions leads to a good approximation of self-similar and long-range dependent traffic. The resulting stochastic processes are not exactly self-similar but asymptotically self-similar (see [6,2,8] for details).
   
   
2. $M/G/\infty-$queueing system based generation
   If the service time distribution of an $M/G/\infty-$ queueing system has infinite variance, then the queue length process is long-range dependent and will yield a good approximation to a self-similar process [2].
   
   
3. Fractional Gaussian noise and fractional Brownian motion
   Fractional Gaussian noise (FGN) and fractional Brownian motion (FBM) play an important role for experiments using the superposition of alternating renewal processes as self-similar traffic generators, since the limiting properties of the superposition method can be expressed in terms of FBM [8]. For a survey on approaches for synthetic generation of FGN and a wavelet-based approach for FGN generation see [3].
   
   
4. Methods based on modulated Poisson processes
   Two other approaches based on a distinct selection of the rate function of a modulated Poisson processe (also called doubly stochastic Poisson processes, DSPP) are shown in [6]: The first approach uses the superposition of multiple fractal renewal processes as the rate function of a Poisson process (fractal-binomial-noise-driven Poisson process, FBNDP). The second approach which is called fractal-shot-noise-driven Poisson point process (FSNDP) uses a fractal shot noise process for the rate function of the Poisson process.

Last modified: