Multifractal Processes
R. H. Riedi,
in Long range dependence : theory and applications,
eds. Doukhan, Oppenheim and Taqqu (to appear 2000).
While in the progress of publication see also:
Technical Report, ECE Dept., Rice University, TR 99-06;
12 page summary, lite version: (text only)

Multifractal theory up to date has been concerned mostly with random and deterministic singular measures, with the notable exception of fractional Brownian motion and Lévy motion. Real world problems involved with the estimation of the singularity structure of both, measures and processes, has revealed the need to broaden the known `multifractal formalism' to include more sophisticated tools such as wavelets. Moreover, the pool of models available at present shows a gap between `classical' multifractal measures, i.e.\ cascades in all variations with rich scaling properties, and stochastic processes with nice statistical properties such as stationarity of increments, Gaussian marginals, and long-range dependence but with degenerate scaling characteristics.
This paper has two objectives, then. For one it develops the multifractal formalism in a context suitable for functions and processes. Second, it introduces truly multifractal processes, building a bridge between multifractal cascades and self-similar processes.
Keywords: Multifractal analysis, self-similar processes, fractional Brownian motion, Lévy flights, stable motion, wavelets, long-range dependence, multifractal subordinator.

Long-Range Dependence and Data Network Traffic
W. Willinger, R. H. Riedi and M. S. Taqqu,
in Long range dependence : theory and applications,
eds. Doukhan, Oppenheim and Taqqu (2000).
 

The objective of this article is twofold.  First, we provide an overview of an exciting and relatively recent application of the concept of long-range dependence (LRD) to the area of communication networks, in particular to problems concerned with the dynamic nature of packet flows in high-speed data networks such as the Internet.  Second and more importantly, we demonstrate that this new application area offers unique opportunities for significantly advancing our understanding of LRD nd related phenomena. These advances are made possible by moving beyond the conventional approaches associated with the wide-spread ``black-box'' perspective of traditional time series analysis and exploiting instead the physical mechanisms that exist in the networking context and are intimately tied to the observed characteristics of measured network traffic.  Clearly, succeeding in this endeavor requires a willingness to acquire a familiarity with networking-related concepts, starting with a basic understanding of the design, architecture, and operations of data networks.  While the  popular ``black-box'' approaches have their merits, especially in areas of applications where the available measurements are limited in scope, we argue in this article that for highly engineered complex systems such as the Internet, they are of little or no value, because ignoring the rich semantic context of the available data sets of traffic measurements means missing out on new discoveries and unexpected but relevant findings.
Keywords: Long-range dependence, network traffic, self-similar processes, fractional Brownian motion, multifractal analysis, cascades.

Multiscale Modeling and Queuing Analysis of Long-Range-Dependent Network Traffic
V. J. Ribeiro, R. H. Riedi, M. S. Crouse and R. G. Baraniuk
IEEE Trans. on Networking, submitted
see also: Technical Report 99-08, ECE Dept., Rice University;
as well as: Proceedings of IEEE INFOCOM 2000, Tel Aviv, Israel, March 2000.
 

There is an urgent need for accurate models of traffic loads seen on high-speed data networks for both, practical applications as well as towards a deeper understanding of the complex dynamics governing the high variability and burstiness observed. The importance of capturing scaling properties when modeling traffic loads is undisputed; a crucial lesson to learn from fractal, long-range dependent (LRD) models was the overly optimistic prediction of loss and delay on links provided by classical models.  However, the influence of (LRD) and marginal statistics still remains on unsure footing.
In this paper, we study these two issues by introducing a multiscale traffic model and a novel multiscale approach to queuing analysis. The multifractal wavelet model (MWM) is a multiplicative, wavelet-based model that captures the positivity, LRD, and ``spikiness'' of non-Gaussian traffic. It is set in the framework of {\em multifractals} which provide the appropriate statistical tools to address the multiscale properties of traffic loads, in particular its burstiness. Using a binary tree, the model synthesizes an $N$-point data set with only $O(N)$ computations.  Leveraging the tree structure of the model, we derive a {\em multiscale queuing analysis} that provides a simple closed form approximation to the tail queue probability, valid for any given buffer size.
Our results clearly indicate that the marginal distribution of traffic at different time-resolutions affects queuing and that a Gaussian assumption can lead to over-optimistic predictions of tail queue probability even when taking LRD into account.

Toward an Improved Understanding of Network Traffic Dynamics
R. H. Riedi and W. Willinger
in: Self-similar Network Traffic and Performance Evaluation to appear with Wiley, June 1999

Since the discovery of long range dependence in Ethernet LAN traces there has been significant progress in developing appropriate mathematical and statistical techniques that provide a physical-based, networking-related understanding of the observed fractal-like or self-similar scaling behavior of measured data traffic over time scales ranging from hundreds of milliseconds to seconds and beyond. These developments have helped immensely in demystifying fractal-based traffic modeling and have given rise to new insights and physical understanding of the effects of large-time scaling properties in measured network traffic on the design, management and performance of high-speed networks.
However, to provide a complete description of data network traffic, the same kind of understanding is necessary with respect to the dynamic nature of traffic over small time scales, from a few hundreds of milliseconds downwards. Because of the predominant protocols and end-to-end congestion control mechanisms that determine the flow of packets, studying the fine-time scale behavior or local characteristics of data traffic is intimately related to understanding the complex interactions that exist in data networks.
In this chapter, we first summarize the results that provide a unifying and consistent picture of the large-time scaling behavior of data traffic. We then report on recent progress in studying the small-time scaling behavior in data network traffic and outline a number of challenging open problems that stand in the way of providing an understanding of the local traffic characteristics that is as plausible, intuitive, appealing and relevant as the one that has been found for the global or large-time scaling properties of data traffic.

L'attracteur d'un systeme de fonctions itéré est le support d'une mesure dite invariante, ou auto-similaire: c'est le point fixe de l'opérateur de Markov dans l'espace métrique des mesures de probabilité a support compact. Un algorithme aléatoire permet la contruction de l'attracteur, qui est presque surement l'ensemble des points limites d'une orbite. Un théoreme ergodique permet de prouver que la fréquence de visite d'un ensemble par cette orbite est presque surement égale a la mesure invariante de cet ensemble. Nous donnons ici une démonstration simple de ce résultat connu.
Abstract in English:
The attractor of an iterated function system (IFS) is the support of a so-called invariant or self-similar measure: this measure is, more precisely, the unique fixed point of the Markov (or Hutchinson) operator which acts in the metric space of all compactly supported probability measures and is associated with the IFS. A simple iterative algorithm allows to produce a random orbit the limit points of which are almost surely the attractor of the IFS. This fact is an essential ingredient in fractal image compression. Moreover, an ergodic theorem states that the frequency of visits of a set by such a random orbit is almost surely equal to the probability assigned to that set by the invariant measure. Thus, the random orbit actually samples the self-similar measure almost surely. We give here a simple proof of this known result.

Wavelet Analysis of Fractional Brownian Motion in Multifractal Time
P. Goncalves and R. H. Riedi
Proceedings of the 17th Colloquium GRETSI, Vannes, France, Sept 1999.

We study fractional Brownian motions in multifractal time, a model for multifractal processes proposed recently in the context of economics. Our interest focuses on the statistical properties of the wavelet decomposition of these processes, such as residual correlations (LRD) and stationarity, which are instrumental towards computing the statistics of wavelet-based estimators of the multifractal spectrum.

Multifractal products of stochastic processes: A Preview
P. Mannersalo, I. Norros and R. Riedi
COST257 (1999) 31.
 

Motivated by the need for multifractal processes with stationary increments we introduce a construction of random multifractal measures based on iterative multiplication of stationary stochastic processes. We establish conditions for the L2-convergence and non-degeneracy of the limit process in a general setting. Proceeding then to multiplying piecewise constant processes we proof continuity of the limit and show some other interesting properties.

Simulation of Non-Gaussian Long-Range-Dependent Traffic using Wavelets
V. J. Ribeiro, R. H. Riedi, M. S. Crouse and R. G. Baraniuk
Proc. ACM SigMetrics'99 (May 1999), 1-12

In this paper, we develop a simple and powerful multiscale model for the synthesis of nonGaussian, long-range dependent (LRD) network traffic. Although wavelets effectively decorrelate LRD data, wavelet-based models have generally been restricted by a Gaussianity assumption that can be unrealistic for traffic. Using a multiplicative superstructure on top of the Haar wavelet transform, we exploit the decorrelating properties of wavelets while simultaneously capturing the positivity and ``spikiness'' of nonGaussian traffic. This leads to a swift O(N) algorithm for fitting and synthesizing N-point data sets. The resulting model belongs to the class of multifractal cascades, a set of processes with rich statistical properties. We elucidate our model's ability to capture the covariance structure of real data and then fit it to real traffic traces. Queueing experiments demonstrate the accuracy of the model for matching real data. Our results indicate that the nonGaussian nature of traffic has a significant effect on queuing.

In this paper, we develop a new multiscale modeling framework for characterizing positive-valued data with long-range-dependent correlations (1/f noise). Using the Haar wavelet transform and a special multiplicative structure on the wavelet and scaling coefficients to ensure positive results, the model provides a rapid O(N) cascade algorithm for synthesizing N-point data sets. We study both the second-order and multifractal properties of the model, the latter after a tutorial overview of multifractal analysis. We derive a scheme for matching the model to real data observations and, to demonstrate its effectiveness, apply the model to network traffic synthesis. The flexibility and accuracy of the model and fitting procedure result in a close fit to the real data statistics (variance-time plots and moment scaling) and queuing behavior. Although for illustrative purposes we focus on applications in network traffic modeling, the multifractal wavelet model could be useful in a number of other areas involving positive data, including image processing, finance, and geophysics.
Keywords: Multifractals, long-range dependence, positive 1/f noise, wavelets, network traffic

The multifractal spectrum characterizes the scaling and singularity structures of signals and proves useful in numerous applications, from network traffic analysis to turbulence. Of great concern is the estimation of the spectrum from a finite data record. In this paper, we derive asymptotic expressions for the bias and variance of a wavelet-based estimator for a fractional Brownian motion (fBm) process. Numerous numerical simulations demonstrate the accuracy and utility of our results.

The apparent `fractal' properties of TCP data traffic have recently attracted considerable interest. Most prominently, fractional Brownian motion (FBM) has been used to model the long range dependence of traffic traces through self-similarity. Traffic being by nature a process of positive increments, though, a multifractal approach appears more natural. In this study, various traces of TCP traffic have been analyzed from both points of view. Though evidence for statistical self-similarity is present in certain `aspects' of the traffic, the multifractal scaling behavior is much more convincing. Furthermore, crucial LAN specific characteristics of data traffic are revealed by the multifractal analysis (MA) only. TCP traffic at Berkeley and at CNET, e.g., looks entirely different from a multifractal point of view while showing about the same self-similarity parameter H. As a further example, MA suggests that Lévy stable motion is in certain situations a more accurate model than FBM. In conclusion, to consider traffic traces as multifractal random measures rather than as (monofractal) self-similar processes is not only more natural but has also various numerical advantages. A novel approach to queueing supports this conclusion.

We analyze the fractal behavior of the high frequency part of the Fourier spectrum of fBm using multifractal analysis and show that it is not consistent with what is measured on real traffic traces. We propose two extensions of fBm which come closer to actual traffic traces multifractal properties.
Keywords: fractional Brownian motion, Multifractal analysis, TCP

In an earlier paper (Adv. Appl. Math. 18 (1997), 50--58) the authors introduced the inverse measure m' of a given measure m on [0,1] and presented the inversion formula f(a) = a f(1/a) which was argued to link the respective multifractal spectra of m and m'. A second paper (Adv. Appl. Math. 19 (1997), 332--354) established the formula under the assumption that m and m' are continuous measures.
Here, we investigate the general case which reveals telling details of interest to the full understanding of multifractals. Subjecting self-similar measures to the operation m->m' creates a new class of discontinuous multifractals. Calculating explicitly we find that the inversion formula holds only for the `fine' multifractal spectra and not for the `coarse' ones. As a consequence, the multifractal formalism fails for this class of measures. A natural explanation is found when drawing parallels to equilibrium measures of dynamical systems. In the context of our work it becomes natural to consider the degenerate Hölder exponents 0 and infinity.

In a previous paper (Adv. Appl. Math. 18 (1997), 50--58) the authors introduced the inverse measure m' of a probability measure m on [0,1]. It was argued that the respective multifractal spectra are linked by the inversion formula f'(a) = a f(1/a). Here, the statements of Part I are put in more mathematical terms and proofs are given for the inversion formula in the case of continuous measures. Thereby, f may stand for the Hausdorff spectrum, the pacing spectrum, or the coarse grained spectrum. With a closer look at the special case of self-similar measures we offer a motivation of the inversion formula as well as a discussion of possible generalizations. Doing so we find a natural extension of the scope of the notion `self-similar' and a failure of the usual multifractal formalism.

The present paper is part I of a series of three closely related papers in which the inverse measure m' of a given measure m on [0,1] is introduced. In the first case discussed in detail, both these measures are multifractal in the usual sense, that is, both are linearly self-similar and continuous but not differentiable and both are non--zero for every interval of [0,1]. Under these assumptions the Hölder multifractal spectra of the two measures are shown to be linked by the inversion formula f'(a) = a f(1/a) .
The inversion formula is then subjected to several diverse variations, which reveal telling details of interest to the full understanding of multifractals. The inverse of the uniform measure on a Cantor dust leads us to argue that this inversion formula applies to the Hausdorff spectrum even if the measures m and m' are not continuous while it may fail for the spectrum obtained by the Legendre path. This phenomenon goes along with a loss of concavity in the spectrum. Moreover, with the examples discussed it becomes natural to include the degenerate Hölder exponents 0 and infty in the Hölder spectra.
This present paper is the first of three closely related papers on inverse measures, introducing the new notion in a language adopted for the physicist. Parts II and III make rigorous what is argued with intuitive arguments here. Part II extends the common scope of the notion of self-similar measures. With this broader class of invariant measures part III shows that the multifractal formalism may fail.

The study of fractal quantities and structures exhibiting highly erratic features on all scales has proved to be of outstanding significance in various disciplines. While scaling phenomena are pervasive in natural and man-made constructs, such objects are less fractal than multifractal. In most simple terms this means that moments of different orders scale differently with increasing resolution.
This paper should be understood as a tutorial in multifractals and their analysis via wavelets, in view of possible applications in geophysics. It is elaborated how a description of the well log measurement through wavelets provides a new way of modeling reflection of waves in a material which is dependent on frequency. The wavelet analysis has the potential to provide an explanation for the inconsistencies that are observed when comparing subsurface models that have been constructed from measurements with different resolutions, such as surface seismic, vertical seismic profiles and well logs.

In the study of the involved geometry of singular distributions the use of fractal and multifractal analysis has shown results of outstanding significance. So far, the investigation has focused on structures produced by one single mechanism which were analyzed with respect to the ordinary metric or volume. Most prominent examples include self-similar measures and attractors of dynamical systems. In certain cases, the multifractal spectrum is known explicitly, providing a characterization in terms of the geometrical properties of the singularities of a distribution. Unfortunately, strikingly different measures may possess identical spectra. To overcome this drawback we propose two novel methods, the conditional and the relative multifractal spectrum, which allow for a direct comparison of two distributions. These notions measure the extent to which the singularities of two distributions `correlate'. Being based on multifractal concepts, however, they go beyond calculating correlations. As a particularly useful tool we develop the multifractal formalism and establish some basic properties of the new notions. With the simple example of Binomial multifractals we demonstrate how in the novel approach a distribution mimics a metric different from the usual one. Finally, the provided applications to real data show how to interpret the spectra in terms of mutual influence of dense and sparse parts of the distributions.

Usual fixed-size box-counting algorithms are inefficient for computing generalized fractal dimensions in the range of q<0. In this Letter we describe a new numerical algorithm specifically devised to estimate generalized dimensions for large negative q, providing evidence of its better performance. We compute the complete spectrum of the Hénon attractor, and interpret our results in terms of a ``phase transition'' between different multiplicative laws.

There are strong reasons to believe that the multifractal spectrum of DLA shows anomalies which have been termed left sided. In order to show that this is compatible with strictly multiplicative structures Mandelbrot et al. introduced a one parameter family of multifractal measures invariant under infinitely many linear maps on the real line. Under the assumption that the usual multifractal formalism holds, the authors showed that the multifractal spectrum of these measure is indeed left sided, i.e. they possess arbitrarily large Hölder exponents and the spectrum is increasing over the whole range of these values. Here, it is shown that the multifractal formalism for self-similar measures does indeed hold also in the infinite case, in particular that the singularity exponents D(q) satisfy the usual equation of self-similar measures and that the multifractal spectrum f(a) is the Legendre transform of (q-1)D(q).

To characterize the geometry of a measure, its so-called generalized dimensions D(q) have been introduced recently. The mathematically precise definition given by Falconer turns out to be unsatisfactory for reasons of convergence as well as of undesired sensitivity to the particular choice of coordinates in the negative q range. A new definition is introduced, which is based on box-counting too, but which carries relevant information also for negative q. In particular, rigorous proofs are provided for the Legendre connection between generalized dimensions and the so-called multifractal spectrum and for the implicit formula giving the generalized dimensions of self-similar measures, which was until now known only for positive q.

A lower bound of the Hausdorff dimension of certain self-affine sets is given. Moreover, this and other known bounds such as the box dimension are expressed in terms of solutions of simple equations involving the singular values of the affinities.

This document is a six page summary of my Ph.D. thesis in which multifractal formalism based on counting on coarse levels (as opposed to a dimensional approach) is developed (see also J. Math. Anal. Appl. 16 (1995) 132--150). This formalism is then applied to self-affine measures discovering phase transitions which are not present with self-similar measures.

This is an easy read introduction to multifractals. We start with a thorough study of the Binomial measure from a multifractal point of view, introducing the main multifractal tools. We then continue by showing how to generate more general multiplicative measures and close by presenting an extensive set of examples on which we elaborate how to `read' a multifractal spectrum.