Long-range dependency

A self-similar phenomenon behaves the same when viewed at different degrees of magnification, or different scales on a dimension (space or time). Self-similar processes can be defined using heavy-tailed distributions, also known as long-tailed distributions. Heavy-tailed distributions can be used to characterise probability density that describe traffic processes such as packet inter-arrival times and burst lengths. Self-similar processes are said to exhibit long-range dependency. [1]

Contents

1 Overview

2 Short-range dependence vs. long-range dependence

3 The Poisson distribution

4 The heavy-tail distribution

5 Modelling self-similar traffic

6 Network performance

7 External links

Overview

The design of robust and reliable networks and network services has become an increasingly challenging task in today's Internet world. To achieve this goal, understanding the characteristics of Internet traffic plays a more and more critical role. Empirical studies of measured traffic traces have led to the wide recognition of self-similarity in network traffic. [2]

Missing image
Self-similar_ethernet_traffic.jpg
This graph shows the self-similar nature of Ethernet traffic

Self-similar Ethernet traffic exhibits dependencies over a long range of time scales. This is to be contrasted with telephone traffic which is Poisson in its arrival and departure process. [3] Presented on the right is a graph taken from [4] showing the self-similarity of Ethernet traffic across numerous time scales.

In traditional Poisson traffic, the short-term fluctuations would average out, and a graph covering a large amount of time would approach a constant value.

Heavy-tailed distributions have been observed in many natural phenomena including both physical and sociological phenomena. Mandelbrot established the use of heavy-tailed distributions to model real-world fractal phenomena, eg. Stock markets, earthquakes, and the weather. [5] Ethernet, WWW, SS7, TCP, FTP, TELNET and VBR video (digitised video of the type that is transmitted over ATM networks) traffic is self-similar. [6]

Self-similarity in packetised data networks can be caused by the distribution of file sizes, human interactions and/ or Ethernet dynamics. [7] Self-similar and long-range dependent characteristics in computer networks present a fundamentally different set of problems to people doing analysis and/or design of networks, and many of the previous assumptions upon which systems have been built are no longer valid in the presence of self-similarity. [8]

Short-range dependence vs. long-range dependence

Missing image
SRDvLRDautocovariance.jpg
The autocorrelation functions of long-range and short-range dependent processes

Long-range and short-range dependent processes are characterised by their autocovariance functions. These autocovariance functions, taken from [9], are depicted to the right.

In short-range dependent processes, the coupling between values at different times decreases rapidly as the time difference increases.

Near zero there exists an exponential decay
The area under it is finite

In long-range processes there is much stronger coupling

The decay of the autocovariance function is hyperbolic, and decays slower than exponentially.
The area under it is infinite. [10]

The Poisson distribution

Before the heavy-tailed distribution is introduced mathematically, the Poisson process with a memoryless waiting-time distribution, used to model traditional telephony networks, is briefly reviewed below.

Assuming pure-chance arrivals and pure-chance terminations leads to the following:

The number of call arrivals in a given time has a Poisson distribution, i.e.:

$P(a)= \left ( \frac{\mu^a}{a!} \right )e^{-\mu},$

where a is the number of call arrivals in time T and $μ$ is the mean number of call arrivals in time T. For this reason, pure-chance traffic is also known as Poisson traffic.

The number of call departures in a given time, also has a Poisson distribution, i.e.:

$P(d)=\left(\frac{\lambda^d}{d!}\right)e^{-\lambda},$

where d is the number of call departures in time T and $λ$ is the mean number of call departures in time T.

The intervals, T, between call arrivals and departures are intervals between independent, identically distributed random events. It can be shown that these intervals have a negative exponential distribution, i.e.:

$P[T \ge \ t]=e^{-t/h},\,$

where h is the mean holding time (MHT). [11]

Information on the fundamentals of statistics and probability theory can be found in the | external links section.

The heavy-tail distribution

Heavy-tailed distributions have properties that are qualitatively different to commonly used (memoryless) distributions such as the Poisson distribution.

The Hurst parameter H is a measure of the level of self-similarity of a time series that exhibits long-range dependence. H takes on values from 0.5 to 1. A value of 0.5 indicates the absence of self-similarity. The closer H is to 1, the greater the degree of persistence or long-range dependence. [12]

Typical values of the Hurst parameter, H:

Many real-world processes give H about 0.73
Exactly self-similarity processes have H = 1
Any pure random process has H = 0.5
Network traffic can have a range of H values, but is generally between 0.5 and 1
All simple stochastic processes with finite local state will tend towards H = 0.5 as the scale becomes arbitrarily large
Phenomena with H > 0.5 typically have a complex process structure.[13]

A distribution is said to have be heavy-tail if:

$P[X>x] \sim x^{- \alpha},\ as \ x \to \mathcal{1}, 0< \alpha <2$

This means that regardless of the distribution for small values of the random variable, if the asymptotic shape of the distribution is hyperbolic, it is heavy-tailed. The simplest heavy-tailed distribution is the Pareto distribution which is hyperbolic over its entire range. Complementary distribution functions for the exponential and Pareto distributions are shown below. Shown on the left is a graph of the distributions shown on linear axes, over a wide range of x values ([14]). To its right is a graph of the complementary distribution functions over a smaller domain, and with a logarithmic range ([15]).

Missing image
SRDvLRDdisttailcomp.gif
CDFs of long-range and short-range dependent processes

Missing image
SRDvLRDcdf.jpg
CDFs of long-range and short-range dependent processes

A characteristic of long-tailed distributions is that the log-log plot of the tail of a long-tailed distribution is approximately linear over many orders of magnitude [16]. If the logarithm of the range of an exponential distribution is found, the resulting plot is linear. In contrast, that of the heavy-tail distribution is still curvilinear. These characteristics can be cleary seen on the graph above to the right. In the graph above left, the condition for the existence of a heavy-tail distribution, as previously presented, is not met by the curve labelled "Gamma-Exponential Tail".

The probability mass function of a heavy-tailed distribution is given by:

$p(x)= \alpha k^{\alpha} x^{- \alpha -1},\ \alpha ,k>0,\ x \ge k$

and its cumulative distribution function is given by:

$F(x)=P[X \le \ x]=1- (\frac{k}{x})^{\alpha}$

where k represents the smallest value the random variable can take.

Readers interested in a more rigorous mathematical treatment of the subject are referred to the | external links section.

Modelling self-similar traffic

Since (unlike traditional telephony traffic) packetised traffic exhibits self-similar or fractal characteristics, conventional traffic models do not apply to networks which carry self-similar traffic. [17]

With the convergence of voice and data, the future multi-service network will be based on packetised traffic, and models which accurately reflect the nature of self-similar traffic will be required to develop, design and dimension future multi-service networks. [18]

Previous analytic work done in Internet studies adopted assumptions such as exponentially-distributed packet inter-arrivals, and conclusions reached under such assumptions may be misleading or incorrect in the presence of heavy-tailed distributions. [19]

Deriving mathematical models which accurately represent long-range dependent traffic is a fertile area of research.

Network performance

Network performance degrades gradually with increasing self-similarity. The more self-similar the traffic, the longer the queue size. The queue length distribution of self-similar traffic decays more slowly than with Poisson sources. However, long-range dependence implies nothing about its short-term correlations which affect performance in small buffers. [20] Additionally, aggregating streams of self-similar traffic typically intensifies the self-similarity ("burstiness") rather than smoothing it, compounding the problem. [21]

Self-similar traffic exhibits the persistence of clustering which has a negative impact on network performance.

With Poisson traffic (found in conventional telephony networks), clustering occurs in the short term but smoothes out over the long term.
With self-similar traffic, the bursty behaviour may itself be bursty, which exacerbates the clustering phenomena, and degrades network performance. [22]

Many aspects of network quality of service depend on coping with traffic peaks that might cause network failures, such as

Cell/packet loss and queue overflow
Violation of delay bounds eg. In video
Worst cases in statistical multiplexing

Poisson processes are well-behaved because they are stateless, and peak loading is not sustained, so queues do not fill. With long-range order, peaks last longer and have greater impact: the equilibrium shifts for a while. [23]

The following graph, taken from [24]presents a queuing performance comparison between processes of varying degrees of self-similarity. Note how the queue size increases with increasing self-similarity of the data, for any given channel utilisation, thus degrading network performance. Missing image
SRDvLRDqueuesize.jpg
This graph compares resultant queue sizes for data of varying degrees of self-similarity

Refernce to additional information on the effect of long-range dependency on network performance can be found in the | external links section.

External links

[25] A site offering numerous links to articles written on the effect of self-similar traffic on network performance.

[26] This site provides a detailed mathematical treatment of long-range dependent processes and heavy-tail distributions.

[27] This site gives a (fairly comprehensive) overview of elementary statistics, probability theory and distribution functions.

[28] A dictionary defining technical statistical words and concepts.

[29] Planet Math is an online mathematics encyclopaedia.