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 described using heavy-tailed distributions, also known as long-tailed distributions. Example of such processes include traffic processes such as packet inter-arrival times and burst lengths. Self-similar processes are said to exhibit long-range dependency. [http://dept.ee.wits.ac.za/~kennedy/elen5007/coursepack/course/selfsim.htm]

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 criticalrole. Empirical studies of measured traffic traces have led to the wide recognition ofself-similarity in network traffic. [http://citeseer.ist.psu.edu/438672.html]

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. [http://www.cs.bu.edu/brite/user_manual/node42.html] Presented on the right is a graph 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, e.g. Stock markets, earthquakes, climate, and the weather. [http://www.cs.bu.edu/brite/user_manual/node42.html] Ethernet, WWW, SS7, TCP, FTP, TELNET and VBR video (digitised video of the type that is transmitted over ATM networks) traffic is self-similar. [http://dept.ee.wits.ac.za/~kennedy/elen5007/coursepack/course/selfsim.htm]

Self-similarity in packetised data networks can be caused by the distribution of file sizes, human interactions and/ or Ethernet dynamics. 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. [http://www.cs.bu.edu/pub/barford/ss_lrd.html]

hort-range dependence vs. long-range dependence

Long-range and short-range dependent processes are characterised by their autocovariance functions. 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. [http://www.cs.kent.ac.uk/people/staff/pfl/presentations/longrange/]

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. [http://dept.ee.wits.ac.za/~kennedy/elen5007/coursepack/course/selfsim.htm]

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. [http://www.cs.kent.ac.uk/people/staff/pfl/presentations/longrange/]

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!\}\; ight\; )e^\{-mu\},$

where "a" is the number of call arrivals in time "T", and $mu$ 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!\}\; ight)e^\{-lambda\},$

where "d" is the number of call departures in time "T" and $lambda$ 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). [http://dept.ee.wits.ac.za/~kennedy/elen5007/coursepack/course/rndmcllr.htm]

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

The heavy-tail distribution

A distribution is said to have a heavy-tail if

:

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.

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. [http://dept.ee.wits.ac.za/~kennedy/elen5007/coursepack/paper/ict2005cv.htm]

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. [http://dept.ee.wits.ac.za/~kennedy/elen5007/coursepack/paper/ict2005cv.htm]

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. [http://www.cs.bu.edu/brite/user_manual/node42.html]

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. Additionally, aggregating streams of self-similar traffic typically intensifies the self-similarity ("burstiness") rather than smoothing it, compounding the problem. [http://citeseer.ist.psu.edu/438672.html]

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 smooths 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. [http://dept.ee.wits.ac.za/~kennedy/elen5007/coursepack/course/selfsim.htm]

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 e.g. 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. [http://www.cs.kent.ac.uk/people/staff/pfl/presentations/longrange/]

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

ee also

*Long-tail traffic

External links

* [http://www.columbia.edu/~ww2040/A12.html A site offering numerous links to articles] written on the effect of self-similar traffic on network performance.

* [http://www.ie.tsinghua.edu.cn/~Liql/talks/hs.pdf A detailed mathematical treatment] of long-range dependent processes and heavy-tail distributions.

* [http://www.ap.univie.ac.at/users/Franz.Vesely/sp_english/sp/node4.html A (fairly comprehensive) overview] of elementary statistics, probability theory, and distribution functions.

* [http://www.glossarist.com/glossaries/science/physical-sciences/statistics.asp Glossarist.com] , a dictionary defining technical statistical words and concepts.

* [http://planetmath.org/encyclopedia Planet Math] , an online mathematics encyclopaedia.

References

:*Beran, J. (1994) "Statistics for Long-Memory Processes", Chapman & Hall. ISBN 0-412-04901-5.