Overview
Data traffic: a macroscopic network wide view
Data traffic: a microscopic view
Data traffic: interaction with applications
Data traffic: characteristics
Flow classfication
Data traffic: a macroscopic network wide view
Myself and Jennifer Rexford, Carsten Lund, Nick Reingold, Albert Greenberg, Fred True, in collaboration with WorldNet, are developing a tool NetScope to study and visualize the flow of traffic in the backbone. (An overview article of NetScope will appear in an IEEE Network Magazine special issue on traffice engineering.) Based on the configuration information we construct a network wide view of the configuration of the network and the customer addresses. NetScope then allows network operators and designers to zoom in on the measured traffic between pairs of nodes as well as on the components of load on individual links. This is useful to diagnose performance problems or experiment with alternate routing and peering configurations. In addition, NetScope can correlate traffic flows with other network measurements, such as active measurements and utilization. On a longer timescale we are working on understanding the dynamics of the traffic matrix and its influence on routing and network design. The need to understand the configuration and topology of IP networks motivated me to develop a network debugger, Netdb. Netdb checks for correctness as well as for compliance with network provider policies.
Data traffic: a microscopic view
Dynamics of IP traffic: variability and control
Myself, A. Gilbert, and W. Willinger are investigating how the state of the network is influencing the spacing of packets and thus leaves a signature on small time scale network measurements. We have empirically established the presence of complex scaling phenomena (i.e., multifractal scaling) in data traffic over small time scales and identified its main cause -- networking mechanisms such as TCP and end-to-end congestion controls. We have provided a mathematical framework (wavelets, cascades, and multifractals) for analyzing and describing the observed small-time scaling properties of the measured traffic. We have demonstrate that the new mathematical framework is capable of detecting and identifying local irregularities in a given set of network measurements ( SIGCOMM'98, Special Issue of IEEE Information Theory on Multiscale Statistical Signal Analysis and its Applications'99 , Asilomar'98, CCR'98 ). We are, together with P. Huang (USC), using simulations to correlate the local irregularities in measurements with specific network behavior ( SIGCOMM'99). The goal is to exploit the presence of local irregularities in network measurements to infer user-perceived performance and to relate it to network performance. This work has lead to our participation in the Wavelet Ideal Data Representation Center an NSF KDI initiative. Together with Youngmi Joo (Stanford) and Vinay Ribeiro (Rice) we demonstrate in the context of a simple TCP/IP-based network that depending on the underlying assumptions about the inherent nature of the variability of network traffic, very different conclusions can be derived for a number of well-studied and apparently well-understood problems in the areas of traffic engineering and management ( Allerton'99).
The Changing Nature of Network Traffic: Scaling Phenomena
Relying on a unique set of high-quality, packet-level WAN traffic measurements and using a wavelet-based technique recently suggested and developed by Abry and Veitch we (together with A. Gilbert, and W. Willinger ) are investigating scaling properties that may be present in a large data set. Information at all levels of the user-network interaction hierarchy: session level data; TCP connection, IP flow, and packet level data. The analysis of the scaling behavior of a process helps to characterize the way the process will aggregate over different time intervals, as well as over different-sized groups of hosts. We have identify distinct scaling regions, one for small time scales (a few hundreds of milliseconds and below) and one for large time scales (beyond a few hundreds of milliseconds).
The results of our analysis (Allerton'97, CCR) illustrate that the large-time scaling property of measured WAN traffic has not changed during the last 6-7 years, despite the drastic changes that working WANs such as the Internet have experienced over this time period. In contrast, using the same scaling analysis, we demonstrate that the WAN traffic characteristics at the transport level (i.e., TCP/IP) have changed significantly during the past 6-7 years. While in the early days of the Internet, TCP connection arrivals (representing mostly FTP and TELNET sessions) were consistent with Poisson arrivals, the emergence of WWW as killer application has resulted in TCP connection arrivals that themselves scale over a wide range of time scales and are fully consistent with self-similar behavior. At the same time, we recover the pre-Web TCP connection arrival behavior in today's WAN traffic at the session layer, where modem calls (substitutes for user sessions) are found to be consistent with Poisson arrivals. We are currently investigating the feasibility of a structural modeling approach for WAN traffic that is capable of (i) capturing the large-time as well as small-time scaling properties of measured WAN traces at the different levels of the networking hierarchy in a compact and parsimonious manner, and (ii) accounting for the relevant changes in observed WAN traffic dynamics.
Data traffic: interaction with applications
Web characterization
I am a member of the W3C Web Characterization Activity. Recently I gave a talk on Web Performance Characterization ( Powerpoint, Postscript) at the Nov'99 IETF plenary presenting an overview of how the Web as the dominant application interacts with other network protocols and traffic engineering.
Live Study of the World Wide Web
To gain a better understanding of the World Wide Web, the dominating application on the Internet, it is important to study how a group of people use the Web as well as the characteristics of the accessed Web pages. There are three places where live data can be gathered: the browser, the proxy, or the network. Since most people (e.g., AT&T; employees at Florham Park/Murray Hill) use commercial software and no one is requiring them to use a proxy its impossible to gather data on the browser or at the proxy. I augmented the passive monitoring software to allow the extraction of HTTP packet header information and even the reconstruction of the accessed Web pages if desired ( Paper). This software was used to collect trace data at AT&T; Labs--Research in Florham Park, Murray Hill, and within AT&T; WorldNet. For example this methodology has been used to study the usage of HTTP header fields.
Together with Gideon Glass, Ramon Caceres, Fred Douglis, Misha Rabinovich, we are using this data to evaluate the performance of WWW Proxy Caching. The traces are used as input to a simulator ( INFOCOM'99). We simulate a proxy cache, its cache contents, and its network state with respect to its set of clients and to the content servers to which it connects. We find that a proxy cache, if installed for use by our clients, would under optimistic conditions, reduce client-perceived latency by about 25%. Surprisingly, we also find that the presence of the proxy cache can increase the network bandwidth consumed by our clients.
We, F. Douglis, B. Krishnamurty, and myself, then analyzed the data according to several metrics, including rate of change and compressibility. We are collaborating on this project with Jeffrey Mogul from DEC-WRL, who address the same questions using traces obtained at the DEC's Internet proxy, a proxy everyone at DEC has to use. A paper on potential benefits of delta-encodign and data compression of HTTP appeared in Sigcomm'97 and a paper analyzing the rate of change and other metrics appears in USITS 97.
Reducing Overhead in Flow-Switched Networks
Tother with Jennifer Rexford and Ramon Caceres in AT&T; Research, we are studing ( TON'98, INFOCOM'98) how to efficiently transfer large amounts of diverse traffic over high-speed links, modern integrated networks require more efficient packet-switching techniques that can capitalize on recent advances in switch hardware. Several promising approaches attempt to improve performance by creating dedicated ``shortcut'' connections for long-lived traffic flows, at the expense of the network overhead for establishing and maintaining these shortcuts. The network can balance these cost-performance tradeoffs through three tunable parameters: the granularity of flow end-point addresses, the timeout for grouping related packets into flows, and the trigger for migrating a long-lived flow to a shortcut connection.
Drawing on a continuous one-week trace of Internet traffic, we evaluate the processor and switch overheads for transferring HTTP server traffic through a flow-switched network. In contrast to previous work, we focus on the full probability distributions of flow sizes and cost-performance metrics to highlight the subtle influence of the HTTP protocol and user behavior on the performance of flow switching. We find that moderate levels of aggregation and triggering yield significant reductions in overhead with a negligible reduction in performance. The traffic characterization results further suggest schemes for limiting the shortcut setup rate and the number of simultaneous shortcuts by temporarily delaying the creation of shortcuts during peak load, and by aggregating related packets that share a portion of their routes through the network.
Data traffic: characteristics
TCP connection characteristics
Based on traces collected early via passive traffic monitor I have shown that the connection behavior of current TCP traffic is statistically better modeled by distributions with heavy tails, especially the Weibull distribution, than traditional models. Combined with the observation that the connection arrival process shows self-similar behavior, this implies that the burstiness of current Internet traffic, and most likely future multi-media traffic, is substantially higher than expected. Since a bursty arrival process can substantially degrade the performance of network management algorithms we suggest the Weibull distribution as an alternative model for the analysis and simulations of such algorithms. In a paper in GLOBECOM'96 I show that bursty traffic together with high bandwidth requirements poses a significant challenge to existing call admission algorithms. To cope with bursty traffic and high bandwidth demands I suggest algorithms that may delay calls.
Fitting Mixtures of Exponentials to Long-Tail Distributions
Given that my traffic measurements confirm other studies that show that many quantities characterizing network performance have long-tail probability distributions. Long-tail distributions can have a dramatic effect upon performance, but it is often difficult to describe this effect in detail, because performance models with component long-tail distributions tend to be difficult to analyze. We, joined work with W. Whitt, address this problem by developing an algorithm for approximating a long-tail distribution by a finite mixture of exponentials. Even though a mixture of exponentials has an exponential tail, it can match a long-tail distribution in the regions of primary interest when there are enough exponential components. Approximating long-tail distributions by hyperexponential distributions allows one to apply well known analytical models to analyze and bound the performance degradation that long-tail distributions may or may not impose for some applications. This work has appeared in INFOCOM'97 and in Performance Evaluation'98.
Flow classification
Together with Muthu Muthukrishnan we have proposed ( INFOCOM'00) an algorithmic framework for solving the packet classification problem that allows various access time vs. memory tradeoffs. It reduces the multi-dimensional packet classification problem to solving a few instances of the one-dimensional IP lookup problem. It gives the best known lookup performance with moderately large memory space. Furthermore, it efficiently supports a reasonable number of additions and deletions to the rulesets without degrading the lookup performance. We perform a thorough experimental study of the tradeoffs for the two-dimensional packet classification problem on rulesets derived from datasets collected from AT&T; WorldNet, an Internet Service Provider.