previous page


Fractal Analysis and Wavelet transform:
Potential and Limitation for Traffic Models Design


Abstract

Traffic models have a wide potential use for design a modern heterogeneous application. In IP telephony and video streaming systems a packet-level process peculiarity is heavily depended on scheduling algorithms based on traffic models. The fundamental problem of design such models is finding out under what conditions different controlling policies guarantee required QoS parameters. The empirical studies of network traffic behaviors have shown that scale-invariant or fractal-like feature plays an important role in context of QoS analysis. In this paper we discuss potential and limitation of wavelet transform and fractal analysis methods to describe differential and integral properties of measured data traffic.

Keywords:
fractal analysis, wavelet transform, traffic models, self-similarity.

1. Introduction

This work belong to a line of research that attempts to develop new tools and models of the data traffic at the different layers of WAN/LAN protocol hierarchy. Such research have to become an important issue of empirical QoS analysis of traffic behaviour. Several studies reported that the packet traffic for diverse networking conditions indicates fractal behaviour [1,2]. Such peculiarities may be caused by several reasons: high variability of individual connections or heavy-tailed distributions of congested periods. In any case fractal behavior is a general phenomena. From the practical point of view fractal properties implies the existence of concentrated periods of high or low (ON/OFF) source activities at wide range of time scale (fig1).


Fig 1. Packets delays gain as s function of time in a WAN environment: the top diagram - absolute values of RTT parameter in virtual channel; the bottom diagram - fractal structure of packets flow that excessed 600 msec threshold.

As a result a correlation structure of packet streams in modern network stand in contrast with traditional models and Poisson models could not be used to explain the empirical observed a fractal-like behavior of aggregate traffic. All stream transmitted on high-speed packet-switched computer network will be statistically multiplexed with local irregularities at the virtual path nodes. Therefore each packets experiencing stochastic delays and exhibit the presence of non-trivial stochastic behavior as they path to target destination (Fig 1). The first-order statistics of packets delay provide information regarding the length of a burst and the second-order statistics information about neighbouring irregularities and its spectral density. In such packets flow negative difference between inter departure and inter arrival times of packets correspond to a clustering of packets; positive one to dispersion of packets and excessive delay. Either event increases the probability of packets loss and have an influence on the QoS parameters. To provide a complete description of such process it is necessary to get a handle of small and large time scaling features. In this case fractal models and wavelet transform of packet flow on different time scales allow us to refine the fractal nature of network traffic both qualitatively and quantitatively.

2. Fractal analysis.

Measured WAN traffic is consistent with large time scaling or asymptotic self-similarity and can be characterised by a simple model with single parameter. This feature of network traffic may holds globally both in time and scale and quite different from a properties observed over small time scales. Therefore for network design purpose we need a traffic model with built-in scale-localisation ability across wide range of time scales. The fractional measure of a network process can be written as:

      (1)

where D - fractional dimension; - the scaling parameter or chosen measuring element; a - factor describing a measure, which can be compared to the given process. Let f(t) some function used for the description of properties of a process. If the following equality

      (2)

is carried out, than the process is characterised by scale invariance property. The non-trivial decision of (2) is a of sedate function , that allows to define a class of models which help to characterise its self-similarity properties. For example, for a state loss model of dynamic system we have

where m=1,4,...2n, and the core of integrated transformation can be computed as

At n this expression results in convolution integral structure on Cantor set

      (3)

where - fractional dimension; - Gamma function; - a constant dependent on the characteristic of Cantor set.

The characteristics of scale property of network processes can be investigated with the help of generalised Brownian motion. Taking into account general properties of such process

it is possible to write down

Setting and k2H(t)=(22H-1-1)t2H the expression for such process can be written as a following convolution equation


where

It should be note that a core of all this integral equations is function that satisfying (2). Thus, the standard definition of scale invariant or fractal properties for continuous process is satisfy to the following equality

      (4)

which understood in the sense of equality of process probability distribution. If for all whole m we have Xk=Z(k+1)-Z(k), then

      (5)

It is necessary to make a several remarks. If X there is a positive value process and average value is not equal to zero, neither X nor X-M{X} can not be precisely self-similar processes in sense of definition (5). However sequence X-M{X} can be asymptotically self-similar.

To investigate a fractal-like of property and characteristics of the network traffic it is possible used a absolute statistical moments function defined by

      (6)

If the process X has of self-similarity property (5), then the value is proportional to value . Therefore for the fixed values q the following condition hold

      (7)

As, according to (5) it is possible to write down

      (8)

On can use (8) as a next definition of fractal properties. In this case a self-similarity feature can be formulated as a linear dependence of changes log at change of logm. So used an inclination of on the diagram in double logarithmic scale it is possible to define a value of fractal parameters. When process X(t) has non-liner depends from q, the concept multifractal is used. The process X(t) refers to as multifractal if the logarithm of its absolute moments changes linearly together with change of the logarithm of a aggregate level m, but non-liner depends from q. For the analysis of such properties it is not enough to use the information only about of the first or second absolute statistical moments. In this case we shall use of non-parametrical statistics for the aggregated series given by

      (9)

If changes linearly, it is possible to consider process X as a multifractal. Just such character of change is observed in Internet during connections (Fig.2)


Fig 2. A dependence of the statistical moments from first (a) till fourth (d) of the orders for the traffic in WAN virtual Internet connection.

3. Wavelet transform

Wavelet is an effective investigating tool which detecting global and local scaling traffic behavior as well as describe packet-switched process both in time and scale measure. For this purpose wavelet model use the notion of coarse and fine approximations which needed to pass from one level of approximation to another. The wavelet decomposition can be written as

      (10)

where - first level signal approximation, - wavelet functions, - scaling functions.

For investigating the nature of local and global singularities as a function we can used a set of wavelet coefficients across finer and finer scales (Fig 3).


a) network traffic

b) Wavelet coefficients

Fig.3. Wavelet traffic transform

While the classical methods results in scaling properties that hold across the whole signal the wavelet technique provides local information about the fine structure of network traffic at a given point in time. Therefore wavelets with their scale-localisation ability provide an useful tool for traffic models design.

Conclusion

To study the local and global scaling phenomena of measured network traffic fractal analysis and wavelet transform may be a useful tools. A next step is to find out how this new methods can be exploited for engineering traffic model and QoS management.

Reference

  1. Leland W.E., Taggu M.S., Willinger and Wilson D.V. On the Self-Similar Nature of Ethernet Traffic. Proceedings of ACM SIGCOMM'93, San Francisco, 1993, v 23, N 4.
  2. Klivansky S.M., Mukherjee A. and Song C. On Long-Range Dependence in NSFNET Traffic, Technical Report CIT-CC-94-61, 1994, 38p



Previous page Top