Long-tail traffic
Encyclopedia
This article covers a range of tools from different disciplines that may be used in the important science of determining the probability of rare events.
The terms long-range dependent, self-similar and heavy-tailed are very close in meaning. Differences in nomenclature hint at the origins and application fields of the terms. These are somewhat different but closely related phenomena.
A long-tailed or heavy-tailed probability distribution
is one that assigns relatively high probabilities to regions far from the mean or median. A more formal mathematical definition is given below. In the context of teletraffic engineering
a number of quantities of interest have been shown to have a long-tailed distribution. For example, if we consider the sizes of files transferred from a web-server, then, to a good degree of accuracy, the distribution is heavy-tailed, that is, there are a large number of small files transferred but, crucially, the number of very large files transferred remains a major component of the volume downloaded.
Many processes are technically long-range dependent but not self-similar. The differences between these two phenomena are subtle. Heavy-tailed refers to a probability distribution, and long-range dependent refers to a property of a time series and so these should be used with care and a distinction should be made. The terms are distinct although superpositions of samples from heavy-tailed distributions aggregate to form long-range dependent time series.
Additionally there is Brownian motion
which is self-similar but not long-range dependent.
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].
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].
With many time-series if the series is averaged then the data begins to look smoother. However, with self-similar data, one is confronted with traces which are spiky and bursty, even at large scales. Such behaviour is caused by strong dependence in the data: large values tend to come in clusters, and clusters of clusters, etc. This can have far-reaching consequences for network performance
[5].
Heavy-tail distributions have been observed in many natural phenomena including both physical and sociological phenomena. Mandelbrot
established the use of heavy-tail distributions to model real-world fractal
phenomena, e.g. Stock markets, earthquakes, and the weather [3].
Ethernet, WWW
, SS7
, TCP
, FTP
, TELNET
and VBR
video (digitised video of the type that is transmitted over ATM
networks) traffic is self-similar [1].
Self-similarity in packetised data networks can be caused by the distribution of file sizes, human interactions and/or Ethernet dynamics [6]. 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 [7].
functions.
In short-range dependent processes, the coupling between values at different times decreases rapidly as the time difference increases.
In long-range processes, the correlations at longer time scales are more significant.
where ρ(k) is the autocorrelation function at a lag k, α is a parameter in the interval (0,1) and the ~ means asymptotically proportional to as k approaches infinity.
.
Assuming pure-chance arrivals and pure-chance terminations leads to the following:
where a is the number of call arrivals and
is the mean number of call arrivals in time T. For this reason, pure-chance traffic is also known as Poisson traffic.
where d is the number of call departures and
is the mean number of call departures in time T.
where h is the Mean Holding Time (MHT) [1].
Information on the fundamentals of statistics and probability theory can be found in the external links section.
The Hurst parameter H is a measure of the level of self-similarity of a time series that exhibits long-range dependence, to which the heavy-tail distribution can be applied. H takes on values from 0.5 to 1. A value of 0.5 indicates the data is uncorrelated or has only short-range correlations. The closer H is to 1, the greater the degree of persistence or long-range dependence [1].
Typical values of the Hurst parameter, H:
A distribution is said to be heavy-tailed 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-tail 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, spanning a large domain [9]. To its right is a graph of the complementary distribution functions over a smaller domain, and with a logarithmic range [6].
If the logarithm of the range of an exponential distribution is taken, the resulting plot is linear. In contrast, that of the heavy-tail distribution is still curvilinear. These characteristics can be clearly seen on the graph above to the right. A characteristic of long-tail distributions is that if the logarithm of both the range and the domain is taken, the tail of the long-tail distribution is approximately linear over many orders of magnitude [10]. 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-tail distribution is given by:
and its cumulative distribution function
is given by:
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.
and buffer
capacity) and network topology
[11]. This is currently the most popular explanation in the engineering literature and the one with the most empirical evidence through observed file size distributions.
Second, is a transport layer cause which theorizes that the feedback between multiple TCP streams due to TCP's congestion avoidance algorithm in moderate to high packet loss situations causes self-similar traffic or at least allows it to propagate. However, this is believed only to be a significant factor at relatively short timescales and not the long-term cause of self-similar traffic.
Finally, is a theorized link layer cause which is predicated based on physics simulations of packet switching networks on simulated topologies. At a critical packet creation rate, the flow in a network becomes congested and exhibits 1/f noise and long-tail traffic characteristics. There have been criticisms on these sorts of models though as being unrealistic in that network traffic is long-tailed even in non-congested regions [24] and at all levels of traffic.
[12] showed in simulation that long-range dependence could arise in the queue
length dynamics at a given node (an entity which transfers traffic) within a communications network even when the traffic sources are free of long-range dependence. The mechanism for this is believed to relate to feedback from routing effects in the simulation.
based on accurate assumptions of the traffic that they carry. The dimensioning and provisioning of networks that carry long-tail traffic is discussed in the next section.
Since (unlike traditional telephony traffic) packetised traffic exhibits self-similar or fractal characteristics, conventional traffic models do not apply to networks which carry long-tail traffic [1]. 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 [3].
It has for long been realised that efficient and accurate modelling of various real world phenomena needs to incorporate the fact that observations made on different scales each carry essential information. In most simple terms, representing data on large scales by its mean is often useful (such as an average income or an average number of clients per day) but can be inappropriate (e.g. in the context of buffering or waiting queues) [5].
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 long-tail traffic will be required to develop, design and dimension future multi-service networks [1]. We seek an equivalent to the Erlang
model for circuit switched networks [6].
There is not an abundance of heavy-tailed models with rich sets of accompanying data fitting techniques [13]. A clear model for fractal traffic has not yet emerged, nor is there any definite direction towards a clear model [1]. Deriving mathematical models which accurately represent long-tail traffic is a fertile area of research.
Gaussian models
, even long-range dependent Gaussian models, are unable to accurately model current Internet traffic [14]. Classical models of time series
such as Poisson and finite Markov processes
rely heavily on the assumption of independence
, or at least weak dependence [5]. Poisson and Markov related processes have, however, been used with some success. Nonlinear
methods are used for producing packet traffic models which can replicate both short-range and long-range dependent streams [12].
A number of models have been proposed for the task of modelling long-tail traffic. These include the following:
No unanimity exists about which of the competing models is appropriate [1], but the Poisson Pareto Burst Process (PPBP), which is an M/G/
process, is perhaps the most successful model to date. It is demonstrated to satisfy the basic requirements of a simple, but accurate, model of long-tail traffic [14].
Finally, results from simulations (taken from [1]) using
-stable stochastic processes for modelling traffic in broadband networks are presented. The simulations are compared to a variety of empirical data (Ethernet, WWW, VBR Video).
The graph on the left shows the model's simulation results for Ethernet traffic. On its right is shown measured Ethernet traffic. The model appears to appear to represent the empirical traffic well.
The graph on the left shows the model's simulation results for WWW traffic. On its right is shown measured WWW traffic. Here, too, the model appears to appear to represent the empirical traffic well.
control is able to shape source traffic into an on-average constant output stream while conserving information [15]. Congestion control of heavy-tailed traffic is discussed in the following section.
Traffic self-similarity negatively affects primary performance measures such as queue size and packet-loss rate. The queue length distribution of long-tail 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 [4].
For heavy-tailed traffic, extremely large bursts occur more frequently than with light-tailed traffic [16]. Additionally, aggregating streams of long-tail traffic typically intensifies the self-similarity ("burstiness") rather than smoothing it, compounding the problem [2].
The graph above right, taken from [1], presents a queueing performance comparison between traffic streams 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.
In the modern network environment with multimedia
and other QoS
sensitive traffic streams comprising a growing fraction of network traffic, second order performance measures in the form of “jitter
” such as delay variation and packet loss
variation are of import to provisioning user specified QoS. Self-similar burstiness is expected to exert a negative influence on second order performance measures [17].
Packet switching based services, such as the Internet (and other networks that employ IP
) are best-effort services, so degraded performance, although undesirable, can be tolerated. However, since the connection is contracted, ATM networks need to keep delays and jitter within negotiated limits [18].
Self-similar traffic exhibits the persistence of clustering which has a negative impact on network performance.
Many aspects of network quality of service depend on coping with traffic peaks that might cause network failures, such as
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 [8].
Due to the increased demands that long-tail traffic places on networks resources, networks need to be carefully provisioned to ensure that quality of service
and service level agreement
s are met. The following subsection deals with the provisioning of standard network resources, and the subsection after that looks at provisioning web servers which carry a significant amount of long-tail traffic.
While throughput
declines gradually as self-similarity increases, queuing delay increases more drastically. When traffic is self-similar, we find that queuing delay grows proportionally to the buffer capacity present in the system. Taken together, these two observations have potentially dire implications for QoS provisions in networks. To achieve a constant level of throughput or packet loss as self-similarity is increased, extremely large buffer capacity is needed. However, increased buffering leads to large queuing delays and thus self-similarity significantly steepens the trade-off curve between throughput/ packet loss and delay [15].
ATM can be employed in telecommunications networks to overcome second order performance measure problems. The short fixed length cell used in ATM reduces the delay and most significantly the jitter for delay-sensitive services such as voice and video [20].
encountered by user requests, in terms of higher average response times and higher response time variance
. Without adaptive, optimal management and control of resources, SLAs based on response time are impossible. The capacity requirements on the site are increased while its ability to provide acceptable levels of performance and availability
diminishes [16]. Techniques to control and manage long-tail traffic are discussed in the following section.
The ability to accurately forecast request patterns is an important requirement of capacity planning. A practical consequence of burstiness and heavy-tailed and correlated arrivals is difficulty in capacity planning [16].
With respect to SLAs, the same level of service for heavy-tailed distributions requires a more powerful set of servers, compared with the case of independent light-tailed request traffic. To guarantee good performance, focus needs to be given to peak traffic duration because it is the huge bursts of requests that most degrade performance. That is why some busy sites require more head room (spare capacity) to handle the volumes; for example, a high-volume online trading site reserves spare capacity with a ratio of three to one [16].
Reference to additional information on the effect of long-range dependency on network performance can be found in the external links section.
Traffic control for self-similar traffic has been explored on two fronts: Firstly, as an extension of performance analysis in the resource provisioning context, and secondly, from the multiple time scale traffic control perspective where the correlation structure at large time scales is actively exploited to improve network performance [22].
The resource provisioning approach seeks to identify the relative utility of the two principal network resource types - bandwidth and buffer capacity - with respect to their curtailing effects on self-similarity, and advocates a small buffer/ large bandwidth resource dimensioning policy. Whereas resource provisioning is open-loop
in nature, multiple time scale traffic control exploits the long-range correlation structure present in self-similar traffic [22]. Congestion control can be exercised concurrently at multiple time scales, and by cooperatively engaging information extracted at different time scales, achieve significant performance gains [21].
Another approach adopted in controlling long-tail traffic makes traffic controls cognizant of workload properties. For example, when TCP is invoked in HTTP in the context of web client/ server interactions, the size of the file being transported (which is known at the server) is conveyed or made accessible to protocols in the transport layer
, including the selection of alternative protocols, for more effective data transport. For short files, which constitute the bulk of connection requests in heavy-tailed file size distributions of web servers, elaborate feedback control may be bypassed in favour of lightweight mechanisms in the spirit of optimistic control, which can result in improved bandwidth utilisation [17].
[12] found that the simplest way to control packet traffic is to limit the length of queues. Long queues in the network invariably occur at hosts (entities that can transmit and receive packets). Congestion control can therefore be achieved by reducing the rate of packet production at hosts with long queues.
It should be noted that long-range dependence and its exploitation for traffic control is best suited for flows or connections whose lifetime or connection duration is long lasting [17].
The terms long-range dependent, self-similar and heavy-tailed are very close in meaning. Differences in nomenclature hint at the origins and application fields of the terms. These are somewhat different but closely related phenomena.
A long-tailed or heavy-tailed probability distribution
Probability distribution
In probability theory, a probability mass, probability density, or probability distribution is a function that describes the probability of a random variable taking certain values....
is one that assigns relatively high probabilities to regions far from the mean or median. A more formal mathematical definition is given below. In the context of teletraffic engineering
Teletraffic engineering
Telecommunications traffic engineering, teletraffic engineering, or traffic engineering is the application of traffic engineering theory to telecommunications...
a number of quantities of interest have been shown to have a long-tailed distribution. For example, if we consider the sizes of files transferred from a web-server, then, to a good degree of accuracy, the distribution is heavy-tailed, that is, there are a large number of small files transferred but, crucially, the number of very large files transferred remains a major component of the volume downloaded.
Many processes are technically long-range dependent but not self-similar. The differences between these two phenomena are subtle. Heavy-tailed refers to a probability distribution, and long-range dependent refers to a property of a time series and so these should be used with care and a distinction should be made. The terms are distinct although superpositions of samples from heavy-tailed distributions aggregate to form long-range dependent time series.
Additionally there is Brownian motion
Brownian motion
Brownian motion or pedesis is the presumably random drifting of particles suspended in a fluid or the mathematical model used to describe such random movements, which is often called a particle theory.The mathematical model of Brownian motion has several real-world applications...
which is self-similar but not long-range dependent.
Overview
The design of robust and reliable networks and network services has become an increasingly challenging task in today's InternetInternet
The Internet is a global system of interconnected computer networks that use the standard Internet protocol suite to serve billions of users worldwide...
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].
Self-similar Ethernet
Ethernet
Ethernet is a family of computer networking technologies for local area networks commercially introduced in 1980. Standardized in IEEE 802.3, Ethernet has largely replaced competing wired LAN technologies....
traffic exhibits dependencies over a long range of time scales. This is to be contrasted with telephone traffic which is Poisson
Poisson distribution
In probability theory and statistics, the Poisson distribution is a discrete probability distribution that expresses the probability of a given number of events occurring in a fixed interval of time and/or space if these events occur with a known average rate and independently of the time since...
in its arrival and departure process [3].
With many time-series if the series is averaged then the data begins to look smoother. However, with self-similar data, one is confronted with traces which are spiky and bursty, even at large scales. Such behaviour is caused by strong dependence in the data: large values tend to come in clusters, and clusters of clusters, etc. This can have far-reaching consequences for network performance
Network performance
Network performance refers to the service quality of a telecommunications product as seen by the customer. It should not be seen merely as an attempt to get "more through" the network....
[5].
Heavy-tail distributions have been observed in many natural phenomena including both physical and sociological phenomena. Mandelbrot
Benoît Mandelbrot
Benoît B. Mandelbrot was a French American mathematician. Born in Poland, he moved to France with his family when he was a child...
established the use of heavy-tail distributions to model real-world fractal
Fractal
A fractal has been defined as "a rough or fragmented geometric shape that can be split into parts, each of which is a reduced-size copy of the whole," a property called self-similarity...
phenomena, e.g. Stock markets, earthquakes, and the weather [3].
Ethernet, WWW
World Wide Web
The World Wide Web is a system of interlinked hypertext documents accessed via the Internet...
, SS7
SS7
SS-7 can stand for:* Signaling System #7, a set of telephone signaling protocols.* The R-16 missile, with NATO reporting name SS-7 Saddler.* China Railways SS7, an electric locomotive model in China.* Super Socket 7, a chip socket introduced by AMD...
, TCP
Transmission Control Protocol
The Transmission Control Protocol is one of the core protocols of the Internet Protocol Suite. TCP is one of the two original components of the suite, complementing the Internet Protocol , and therefore the entire suite is commonly referred to as TCP/IP...
, FTP
File Transfer Protocol
File Transfer Protocol is a standard network protocol used to transfer files from one host to another host over a TCP-based network, such as the Internet. FTP is built on a client-server architecture and utilizes separate control and data connections between the client and server...
, TELNET
TELNET
Telnet is a network protocol used on the Internet or local area networks to provide a bidirectional interactive text-oriented communications facility using a virtual terminal connection...
and VBR
VBR
VBR may refer to:* Variable bitrate, in telecommunications and computing, when the bitrate used in sound or video encoding is not held constant* Volume Boot Record, in computer disks, a type of boot sector that contains code for bootstrapping programs...
video (digitised video of the type that is transmitted over ATM
Asynchronous Transfer Mode
Asynchronous Transfer Mode is a standard switching technique designed to unify telecommunication and computer networks. It uses asynchronous time-division multiplexing, and it encodes data into small, fixed-sized cells. This differs from approaches such as the Internet Protocol or Ethernet that...
networks) traffic is self-similar [1].
Self-similarity in packetised data networks can be caused by the distribution of file sizes, human interactions and/or Ethernet dynamics [6]. 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 [7].
Short-range dependence vs. long-range dependence
Long-range and short-range dependent processes are characterised by their autocovarianceAutocovariance
In statistics, given a real stochastic process X, the autocovariance is the covariance of the variable with itself, i.e. the variance of the variable against a time-shifted version of itself...
functions.
In short-range dependent processes, the coupling between values at different times decreases rapidly as the time difference increases.
- The sum of the autocorrelationAutocorrelationAutocorrelation is the cross-correlation of a signal with itself. Informally, it is the similarity between observations as a function of the time separation between them...
function over all lags is finite. - As the lag increases, the autocorrelationAutocorrelationAutocorrelation is the cross-correlation of a signal with itself. Informally, it is the similarity between observations as a function of the time separation between them...
function of short-range dependent processes decays quickly.
In long-range processes, the correlations at longer time scales are more significant.
- The area under the autocorrelationAutocorrelationAutocorrelation is the cross-correlation of a signal with itself. Informally, it is the similarity between observations as a function of the time separation between them...
function summed over all lags is infinite [8]. - The decay of the autocorrelationAutocorrelationAutocorrelation is the cross-correlation of a signal with itself. Informally, it is the similarity between observations as a function of the time separation between them...
function is often assumed to have the specific functional form,
where ρ(k) is the autocorrelation function at a lag k, α is a parameter in the interval (0,1) and the ~ means asymptotically proportional to as k approaches infinity.
The Poisson distribution and traffic
Before the heavy-tail distribution is introduced mathematically, the memoryless Poisson distribution, used to model traditional telephony networks, is briefly reviewed below. For more details, see the article on the Poisson distributionPoisson distribution
In probability theory and statistics, the Poisson distribution is a discrete probability distribution that expresses the probability of a given number of events occurring in a fixed interval of time and/or space if these events occur with a known average rate and independently of the time since...
.
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.:
where a is the number of call arrivals 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.:
where d is the number of call departures 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.:
where h is the Mean Holding Time (MHT) [1].
Information on the fundamentals of statistics and probability theory can be found in the external links section.
The heavy-tail distribution
Heavy-tail distributions have properties that are qualitatively different from 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, to which the heavy-tail distribution can be applied. H takes on values from 0.5 to 1. A value of 0.5 indicates the data is uncorrelated or has only short-range correlations. The closer H is to 1, the greater the degree of persistence or long-range dependence [1].
Typical values of the Hurst parameter, H:
- Any pure random process has H = 0.5
- Phenomena with H > 0.5 typically have a complex process structure. [8]
A distribution is said to be heavy-tailed 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-tail 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, spanning a large domain [9]. To its right is a graph of the complementary distribution functions over a smaller domain, and with a logarithmic range [6].
If the logarithm of the range of an exponential distribution is taken, the resulting plot is linear. In contrast, that of the heavy-tail distribution is still curvilinear. These characteristics can be clearly seen on the graph above to the right. A characteristic of long-tail distributions is that if the logarithm of both the range and the domain is taken, the tail of the long-tail distribution is approximately linear over many orders of magnitude [10]. 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
Probability mass function
In probability theory and statistics, a probability mass function is a function that gives the probability that a discrete random variable is exactly equal to some value...
of a heavy-tail distribution is given by:
and its cumulative distribution function
Cumulative distribution function
In probability theory and statistics, the cumulative distribution function , or just distribution function, describes the probability that a real-valued random variable X with a given probability distribution will be found at a value less than or equal to x. Intuitively, it is the "area so far"...
is given by:
where k represents the smallest value the random variable
Random variable
In probability and statistics, a random variable or stochastic variable is, roughly speaking, a variable whose value results from a measurement on some type of random process. Formally, it is a function from a probability space, typically to the real numbers, which is measurable functionmeasurable...
can take.
Readers interested in a more rigorous mathematical treatment of the subject are referred to the external links section.
What causes long-tail traffic?
In general, there are three main theories for the causes of long-tail traffic (see a review of all three causes in [23]). First, is a cause based in the application layer which theorizes that user session durations vary with a long-tail distribution due to the file size distribution. If the distribution of file sizes is heavy-tailed then the superposition of many file transfers in a client/server network environment will be long-range dependent. Additionally, this causal mechanism is robust with respect to changes in network resources (bandwidthBandwidth (computing)
In computer networking and computer science, bandwidth, network bandwidth, data bandwidth, or digital bandwidth is a measure of available or consumed data communication resources expressed in bits/second or multiples of it .Note that in textbooks on wireless communications, modem data transmission,...
and buffer
Buffer (computer science)
In computer science, a buffer is a region of a physical memory storage used to temporarily hold data while it is being moved from one place to another. Typically, the data is stored in a buffer as it is retrieved from an input device or just before it is sent to an output device...
capacity) and network topology
Network topology
Network topology is the layout pattern of interconnections of the various elements of a computer or biological network....
[11]. This is currently the most popular explanation in the engineering literature and the one with the most empirical evidence through observed file size distributions.
Second, is a transport layer cause which theorizes that the feedback between multiple TCP streams due to TCP's congestion avoidance algorithm in moderate to high packet loss situations causes self-similar traffic or at least allows it to propagate. However, this is believed only to be a significant factor at relatively short timescales and not the long-term cause of self-similar traffic.
Finally, is a theorized link layer cause which is predicated based on physics simulations of packet switching networks on simulated topologies. At a critical packet creation rate, the flow in a network becomes congested and exhibits 1/f noise and long-tail traffic characteristics. There have been criticisms on these sorts of models though as being unrealistic in that network traffic is long-tailed even in non-congested regions [24] and at all levels of traffic.
[12] showed in simulation that long-range dependence could arise in the queue
length dynamics at a given node (an entity which transfers traffic) within a communications network even when the traffic sources are free of long-range dependence. The mechanism for this is believed to relate to feedback from routing effects in the simulation.
Modelling long-tail traffic
Modelling of long-tail traffic is necessary so that networks can be provisionedProvisioning
In telecommunication, provisioning is the process of preparing and equipping a network to allow it to provide services to its users. In NS/EP telecommunications services, "provisioning" equates to "initiation" and includes altering the state of an existing priority service or capability.In a...
based on accurate assumptions of the traffic that they carry. The dimensioning and provisioning of networks that carry long-tail traffic is discussed in the next section.
Since (unlike traditional telephony traffic) packetised traffic exhibits self-similar or fractal characteristics, conventional traffic models do not apply to networks which carry long-tail traffic [1]. 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 [3].
It has for long been realised that efficient and accurate modelling of various real world phenomena needs to incorporate the fact that observations made on different scales each carry essential information. In most simple terms, representing data on large scales by its mean is often useful (such as an average income or an average number of clients per day) but can be inappropriate (e.g. in the context of buffering or waiting queues) [5].
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 long-tail traffic will be required to develop, design and dimension future multi-service networks [1]. We seek an equivalent to the Erlang
Agner Krarup Erlang
Agner Krarup Erlang was a Danish mathematician, statistician and engineer, who invented the fields of traffic engineering and queueing theory....
model for circuit switched networks [6].
There is not an abundance of heavy-tailed models with rich sets of accompanying data fitting techniques [13]. A clear model for fractal traffic has not yet emerged, nor is there any definite direction towards a clear model [1]. Deriving mathematical models which accurately represent long-tail traffic is a fertile area of research.
Gaussian models
Gaussian process
In probability theory and statistics, a Gaussian process is a stochastic process whose realisations consist of random values associated with every point in a range of times such that each such random variable has a normal distribution...
, even long-range dependent Gaussian models, are unable to accurately model current Internet traffic [14]. Classical models of time series
Time series
In statistics, signal processing, econometrics and mathematical finance, a time series is a sequence of data points, measured typically at successive times spaced at uniform time intervals. Examples of time series are the daily closing value of the Dow Jones index or the annual flow volume of the...
such as Poisson and finite Markov processes
Markov chain
A Markov chain, named after Andrey Markov, is a mathematical system that undergoes transitions from one state to another, between a finite or countable number of possible states. It is a random process characterized as memoryless: the next state depends only on the current state and not on the...
rely heavily on the assumption of independence
Statistical independence
In probability theory, to say that two events are independent intuitively means that the occurrence of one event makes it neither more nor less probable that the other occurs...
, or at least weak dependence [5]. Poisson and Markov related processes have, however, been used with some success. Nonlinear
Nonlinearity
In mathematics, a nonlinear system is one that does not satisfy the superposition principle, or one whose output is not directly proportional to its input; a linear system fulfills these conditions. In other words, a nonlinear system is any problem where the variable to be solved for cannot be...
methods are used for producing packet traffic models which can replicate both short-range and long-range dependent streams [12].
A number of models have been proposed for the task of modelling long-tail traffic. These include the following:
- Fractional ARIMAArimaThe Royal Borough of Arima is the fourth largest town in Trinidad and Tobago. Located east of the capital, Port of Spain, Arima supports the only organised indigenous community in the country, the Santa Rosa Carib Community and is the seat of the Carib Queen...
- Fractional Brownian motionBrownian motionBrownian motion or pedesis is the presumably random drifting of particles suspended in a fluid or the mathematical model used to describe such random movements, which is often called a particle theory.The mathematical model of Brownian motion has several real-world applications...
- Iterated Chaotic Maps
- Infinite Markov Modulated Processes
- Poisson Pareto Burst Processes (PPBP)
- Markov Modulated Poisson Processes (MMPP) [4]
- Multi-fractal models [5]
- Matrix models [1]
- Wavelet Modelling
No unanimity exists about which of the competing models is appropriate [1], but the Poisson Pareto Burst Process (PPBP), which is an M/G/
process, is perhaps the most successful model to date. It is demonstrated to satisfy the basic requirements of a simple, but accurate, model of long-tail traffic [14].Finally, results from simulations (taken from [1]) using
-stable stochastic processes for modelling traffic in broadband networks are presented. The simulations are compared to a variety of empirical data (Ethernet, WWW, VBR Video).The graph on the left shows the model's simulation results for Ethernet traffic. On its right is shown measured Ethernet traffic. The model appears to appear to represent the empirical traffic well.
The graph on the left shows the model's simulation results for WWW traffic. On its right is shown measured WWW traffic. Here, too, the model appears to appear to represent the empirical traffic well.
Network performance
In some cases an increase in the Hurst parameter can lead to a reduction in network performance. The extent to which heavy-tailedness degrades network performance is determined by how well congestionNetwork congestion
In data networking and queueing theory, network congestion occurs when a link or node is carrying so much data that its quality of service deteriorates. Typical effects include queueing delay, packet loss or the blocking of new connections...
control is able to shape source traffic into an on-average constant output stream while conserving information [15]. Congestion control of heavy-tailed traffic is discussed in the following section.
Traffic self-similarity negatively affects primary performance measures such as queue size and packet-loss rate. The queue length distribution of long-tail 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 [4].
For heavy-tailed traffic, extremely large bursts occur more frequently than with light-tailed traffic [16]. Additionally, aggregating streams of long-tail traffic typically intensifies the self-similarity ("burstiness") rather than smoothing it, compounding the problem [2].
The graph above right, taken from [1], presents a queueing performance comparison between traffic streams 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.
In the modern network environment with multimedia
Multimedia
Multimedia is media and content that uses a combination of different content forms. The term can be used as a noun or as an adjective describing a medium as having multiple content forms. The term is used in contrast to media which use only rudimentary computer display such as text-only, or...
and other QoS
Quality of service
The quality of service refers to several related aspects of telephony and computer networks that allow the transport of traffic with special requirements...
sensitive traffic streams comprising a growing fraction of network traffic, second order performance measures in the form of “jitter
Jitter
Jitter is the undesired deviation from true periodicity of an assumed periodic signal in electronics and telecommunications, often in relation to a reference clock source. Jitter may be observed in characteristics such as the frequency of successive pulses, the signal amplitude, or phase of...
” such as delay variation and packet loss
Packet loss
Packet loss occurs when one or more packets of data travelling across a computer network fail to reach their destination. Packet loss is distinguished as one of the three main error types encountered in digital communications; the other two being bit error and spurious packets caused due to noise.-...
variation are of import to provisioning user specified QoS. Self-similar burstiness is expected to exert a negative influence on second order performance measures [17].
Packet switching based services, such as the Internet (and other networks that employ IP
Internet Protocol
The Internet Protocol is the principal communications protocol used for relaying datagrams across an internetwork using the Internet Protocol Suite...
) are best-effort services, so degraded performance, although undesirable, can be tolerated. However, since the connection is contracted, ATM networks need to keep delays and jitter within negotiated limits [18].
Self-similar traffic exhibits the persistence of clustering which has a negative impact on network performance.
- With Poisson traffic (found in conventional telephonyTelephonyIn telecommunications, telephony encompasses the general use of equipment to provide communication over distances, specifically by connecting telephones to each other....
networks), clustering occurs in the short term but smooths out over the long term. - With long-tail traffic, the bursty behaviour may itself be bursty, which exacerbates the clustering phenomena, and degrades network performance [1].
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 multiplexingMultiplexingThe multiplexed signal is transmitted over a communication channel, which may be a physical transmission medium. The multiplexing divides the capacity of the low-level communication channel into several higher-level logical channels, one for each message signal or data stream to be transferred...
Poisson processes are well-behaved because they are stateless
Stateless server
In computing, a stateless protocol is a communications protocol that treats each request as an independent transaction that is unrelated to any previous request so that the communication consists of independent pairs of requests and responses...
, 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 [8].
Due to the increased demands that long-tail traffic places on networks resources, networks need to be carefully provisioned to ensure that quality of service
Quality of service
The quality of service refers to several related aspects of telephony and computer networks that allow the transport of traffic with special requirements...
and service level agreement
Service Level Agreement
A service-level agreement is a part of a service contract where the level of service is formally defined. In practice, the term SLA is sometimes used to refer to the contracted delivery time or performance...
s are met. The following subsection deals with the provisioning of standard network resources, and the subsection after that looks at provisioning web servers which carry a significant amount of long-tail traffic.
Network provisioning for long-tail traffic
For network queues with long-range dependent inputs, the sharp increase in queuing delays at fairly low levels of utilisation and slow decay of queue lengths implies that an incremental improvement in loss performance requires a significant increase in buffer size [19].While throughput
Throughput
In communication networks, such as Ethernet or packet radio, throughput or network throughput is the average rate of successful message delivery over a communication channel. This data may be delivered over a physical or logical link, or pass through a certain network node...
declines gradually as self-similarity increases, queuing delay increases more drastically. When traffic is self-similar, we find that queuing delay grows proportionally to the buffer capacity present in the system. Taken together, these two observations have potentially dire implications for QoS provisions in networks. To achieve a constant level of throughput or packet loss as self-similarity is increased, extremely large buffer capacity is needed. However, increased buffering leads to large queuing delays and thus self-similarity significantly steepens the trade-off curve between throughput/ packet loss and delay [15].
ATM can be employed in telecommunications networks to overcome second order performance measure problems. The short fixed length cell used in ATM reduces the delay and most significantly the jitter for delay-sensitive services such as voice and video [20].
Web site provisioning for long-tail traffic
Workload pattern complexities (for example, bursty arrival patterns) can significantly affect resource demands, throughput, and the latencyLatency (engineering)
Latency is a measure of time delay experienced in a system, the precise definition of which depends on the system and the time being measured. Latencies may have different meaning in different contexts.-Packet-switched networks:...
encountered by user requests, in terms of higher average response times and higher response time variance
Variance
In probability theory and statistics, the variance is a measure of how far a set of numbers is spread out. It is one of several descriptors of a probability distribution, describing how far the numbers lie from the mean . In particular, the variance is one of the moments of a distribution...
. Without adaptive, optimal management and control of resources, SLAs based on response time are impossible. The capacity requirements on the site are increased while its ability to provide acceptable levels of performance and availability
Availability
In telecommunications and reliability theory, the term availability has the following meanings:* The degree to which a system, subsystem, or equipment is in a specified operable and committable state at the start of a mission, when the mission is called for at an unknown, i.e., a random, time...
diminishes [16]. Techniques to control and manage long-tail traffic are discussed in the following section.
The ability to accurately forecast request patterns is an important requirement of capacity planning. A practical consequence of burstiness and heavy-tailed and correlated arrivals is difficulty in capacity planning [16].
With respect to SLAs, the same level of service for heavy-tailed distributions requires a more powerful set of servers, compared with the case of independent light-tailed request traffic. To guarantee good performance, focus needs to be given to peak traffic duration because it is the huge bursts of requests that most degrade performance. That is why some busy sites require more head room (spare capacity) to handle the volumes; for example, a high-volume online trading site reserves spare capacity with a ratio of three to one [16].
Reference to additional information on the effect of long-range dependency on network performance can be found in the external links section.
Controlling long-tail traffic
Given the ubiquity of scale-invariant burstiness observed across diverse networking contexts, finding an effective traffic control algorithm capable of detecting and managing self-similar traffic has become an important problem. The problem of controlling self-similar network traffic is still in its infancy [21].Traffic control for self-similar traffic has been explored on two fronts: Firstly, as an extension of performance analysis in the resource provisioning context, and secondly, from the multiple time scale traffic control perspective where the correlation structure at large time scales is actively exploited to improve network performance [22].
The resource provisioning approach seeks to identify the relative utility of the two principal network resource types - bandwidth and buffer capacity - with respect to their curtailing effects on self-similarity, and advocates a small buffer/ large bandwidth resource dimensioning policy. Whereas resource provisioning is open-loop
Open-loop controller
An open-loop controller, also called a non-feedback controller, is a type of controller that computes its input into a system using only the current state and its model of the system....
in nature, multiple time scale traffic control exploits the long-range correlation structure present in self-similar traffic [22]. Congestion control can be exercised concurrently at multiple time scales, and by cooperatively engaging information extracted at different time scales, achieve significant performance gains [21].
Another approach adopted in controlling long-tail traffic makes traffic controls cognizant of workload properties. For example, when TCP is invoked in HTTP in the context of web client/ server interactions, the size of the file being transported (which is known at the server) is conveyed or made accessible to protocols in the transport layer
Transport layer
In computer networking, the transport layer or layer 4 provides end-to-end communication services for applications within a layered architecture of network components and protocols...
, including the selection of alternative protocols, for more effective data transport. For short files, which constitute the bulk of connection requests in heavy-tailed file size distributions of web servers, elaborate feedback control may be bypassed in favour of lightweight mechanisms in the spirit of optimistic control, which can result in improved bandwidth utilisation [17].
[12] found that the simplest way to control packet traffic is to limit the length of queues. Long queues in the network invariably occur at hosts (entities that can transmit and receive packets). Congestion control can therefore be achieved by reducing the rate of packet production at hosts with long queues.
It should be noted that long-range dependence and its exploitation for traffic control is best suited for flows or connections whose lifetime or connection duration is long lasting [17].
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 This site provides 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 This site gives a (fairly comprehensive) overview of elementary statistics, probability theory and distribution functions.
- http://www.glossarist.com/glossaries/science/physical-sciences/statistics.asp A dictionary defining technical statistical words and concepts.
- http://planetmath.org Planet Math has an online mathematics encyclopaedia.