- 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 usingheavy-tailed distribution s, also known aslong-tailed distribution s. 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-worldfractal 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 andVBR 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 anexponential decay .

*The area under it is finite.In long-range processes there is much stronger coupling.

*The decay of the autocovariance function ishyperbolic , 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

:$Pr\; [X>x]\; sim\; x^\{-\; alpha\},mbox\{\; as\; \}x\; o\; infty,qquad\; 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.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 conventionaltelephony 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 statisticalmultiplexing 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.

*Wikimedia Foundation.
2010.*