The Wavelet IDR Center Research Subteam

[ Top | Vision | Technology | Recent Work | Problems ]

Modern communication networks are becoming more and more heterogeneous, not only with respect to the available link speeds (ranging from modem links running at speeds of up to 30Kbps to optical fiber connections capable of sending data at speeds of 155-620 Mbps and beyond), but also with respect to the user behavior, available services and applications, and underlying networking technologies. The implied changes in networking conditions are often so rapid that they challenge conventional approaches to network and performance engineering. 

As a viable alternative to conventional network engineering, network measurements of all different kinds are beginning to play an increasingly important role in trying to gain a fundamental and qualitative understanding of the dynamic nature of modern high-speed networks and of the traffic that they carry. Examples of such measurements range from coarse time scale, per router based, network management measurements (providing network-wide information about the quantity of the carried traffic), to high time resolution packet-level traces collected from individual network links running at speeds of 1.5-155 Mbps (giving link-specific information about the quality of the traffic), to measurements that actively probe the network and provide sufficient coverage for adequate inference about various aspects related to user-perceived end-to-end performance. Analyzing, understanding and visualizing these high-quality and high-volume data sets of various network measurements is rapidly becoming an integral part of the study of a wide range of topics related to the design, control and management of the next-generation communication networks. 

Our aim is to demonstrate how ideas from a multiresolution analysis can give rise to novel, practically useful and theoretically challenging approaches for effectively and efficiently measuring network-specific problems; for analyzing, understanding, and visualizing the temporal, spatial, or hierarchical structure of the resulting data; and for exploiting the ensuing new insights and qualitative understanding for developing a ubiquitous, stable, robust, and high-performance networking infrastructure of the future. 

[ Top | Vision | Technology | Recent Work | Problems ]

Wavelet-based techniques have recently been applied to the analysis of single-link, high time resolution packet-level traces and have contributed significantly to an improved understanding of the temporal dynamics of today's network traffic as observed on a single link. For example, the time-frequency localization ability of wavelets has been exploited to overcome practical obstacles (e.g., size of the data) and theoretical problems (e.g., stationarity issues) related to the study of self-similarity or large-time scaling. More recently, their time-localization capability has cleared the way for a new direction in traffic analysis: assessing the nature of local irregularities in measured network traffic over fine time scales and detecting and identifying structural properties that are localized in time and are consistent with multifractal scaling. The latter ability is expected to be crucial for future network engineering because local irregularities in a given set of network measurements are likely to point to "interesting" events that may contain valuable information about the state in which the network operated at that particular point in time. 

We expect multiresolution analysis techniques and their generalizations to play a major role in moving beyond the study of temporal phenomena in measured traffic traces, toward an analysis that incorporates the temporal and spatial aspects of future high-resolution and network-wide measurements, as well as a third aspect associated with the hierarchical structure of modern communication networks. In this sense, the nature of the measurements and the context in which they arise promise to be a constant source for new problems and unexpected scientific discoveries and can be expected to influence, in turn, theoretical developments in the area of multiscale analysis. 

[ Top | Vision | Technology | Recent Work | Problems ]

Recently, Abry and Veitch suggested and developed a wavelet-based technique for analyzing self-similar network traffic and for estimating the associated scaling parameter H, also known as the Hurst parameter (in the context of long-range dependent processes). Their original paper plus subsequent articles that provide a more detailed discussion of the use of wavelets for the analysis, estimation, and synthesis of scaling phenomena can be found at Darryl Veitch's webpage.

Emphasizing the wavelets' natural ability for investigating scaling properties that may be present in a given large data set, Feldmann et al. in [1] examine packet-level traffic measurements, collected over the past 6-7 years from a number of different wide-area networks (WANs), and show how the popularity of the Web has (has not) affected certain aspects of measured Internet traffic. Our findings point to scaling phenomena in Internet traffic wherever you look.

Figure 1: Time series plot of the number of TCP connections per second in one hour of aggregate traffic (top), textured plot of TCP connection arrivals within a single WWW session (middle) and augmented with their corresponding durations (bottom).  For more information about this picture, see [1] .

 

In particular, in [2] we present a detailed investigation into the observed multifractal scaling behavior of measured Internet traffic and relate it to the protocol dynamics and end-to-end congestion control mechanisms that operate over small time scales and determine the flow of packets at the different layers in the TCP/IP protocol hierarchy. We validate empirically that over small time scales networks act as conservative cascades, thereby contributing a multiplicative component to network traffic that has remained inaccessible to date.

Figure 2: Steps 0, 1, 2, 3, 4, and 10 of a conservative cascade construction, starting with a constant bit-rate source.  After only 10 steps of construction, the synthetic TCP connection resembles the distribution of packets within a measured TCP connection not only visually but also in other statistically sophisticated ways.  For more information about this picture, see  [2]

In a technical counterpart to their ACM/SIGCOMM'98 paper, we present in [3] a wavelet-based time/scale analysis of conservative cascade processes, determine rigorously their scaling properties, and prove that they obey the multifractal formalism. For related work and the original paper on the observed multifractal nature of wide-area network traffic, see Rolf Riedi's current work. For an example of how the measurements at hand generate new problems for wavelet analysis, Gilbert et al. develop and present in [4] a simple coloring heuristic that attempts to visualize multifractal scaling behavior in the time domain and that also gives rise to interesting theoretical problems associated with estimating the multifractal spectrum.

Figure 3: Local area network (left) and wide area network (right) traces colored according to their local irregularity; different colors indicate different magnitudes of the local scaling exponents at the different points in the traffic trace (black for large scaling exponents or spikes in the traffic rate and yellow for small scaling exponents or lulls in the traffic rate).  For more information about this picture, see [4]

[ Top | Vision | Technology | Recent Work | Problems ]

The current trend toward ever-more massive data sets of network measurements from an ever-increasing number of locations within a network poses numerous technical challenges.

• First there is the problem of finding optimal representations of the data that take into account network-specific features (e.g., existing hierarchical structures in the network architectures, topological properties) and scale with the number of nodes at which high time resolution measurements are collected.
• A related problem is that of characterizing the order of approximation of the system at hand. On the one hand, the order of approximation has to be fine enough to detect and identify details that are potentially relevant for network engineering; on the other hand, for routine network operations, the order has to be sufficiently coarse so that standard networking equipment will not be overwhelmed by the volume of collected or transferred data.
• Time-frequency localization techniques need to be extended to incorporate the spatial dimension of the data at hand as well as the additional dimension of the different layers in the networking hierarchy, and fast and efficient algorithms are needed for exploiting the potential in singularity detection and feature extraction for network engineering purposes.
• One of our main objectives is to develop effective methods for visualizing the various types of network measurements that can account for the temporal, spatial and hierarchical aspects of the data at hand.