Internet Flow Characterization -- Adaptive Timeout and Statistical Modeling

Bo Ryu (contact author)
HRL Laboratories

David Cheney and Hans-Warner Braun
National Laboratories for Advanced Networking Research (NLANR), UC San Diego

There is a growing effort on understanding Internet traffic dynamics via the abstraction of flows from packets. We first present an adaptive flow timeout strategy, called Measurement-based Binary Exponential Timeout (MBET), for identifying and maintaining flow state information. In this study, we establish an urgent need for, and investigate the feasibility of adopting an adaptive flow timeout strategy that combines fixed and dynamic timeout values based on observed dynamics of intra-flow packet interarrival times. Applying fixed, identical timeout value across all flows, which is a common practice in several recent studies, makes it difficult to find an optimal timeout value, given that Internet flows show an extreme variability in flow statistics such as flow duration and volume. We demonstrate that, via an extensive analysis of a large number of traces collected at three different sites, the MBET achieves significant performance advantages over widely used fixed flow timeout scheme. This is possible since we find that there is a fair amount of flows exhibiting persistency in intra-flow packet arrivals dynamics and the MBET exploits it whenever possible. By persistency we mean that when a large (small) interarrival time is detected, it is more likely that future interarrival times are large (small) as well. If such persistency does exists in the majority of flows, it can serve as quite an effective means for detecting whether a flow will have a high throughput or not based on observing the packet dynamics during the initial period of the flow. For example, if a flow appears to exhibit high throughput in the beginning, a smaller timeout is likely to be sufficient to determine its end. Consequently, the advantages gained by MBET translate to faster detection of the end of flow, more accurate recognition of long-lived flows and substantial reduction in hardware resources.

Second, we present a highly versatile and parameterized statistical modeling framework for characterizing a broad spectrum of flow dynamics. With the growing interest in understanding and characterizing flow dynamics, it has become necessary and crucial to have a set of parameterized statistical modeling tools so that broadly different and yet faithfully realistic flow characteristics can be repeatedly generated. Such tools are essential for evaluating a number of new flow-based traffic engineering tasks such as dynamic routing. This flow characterization framework identifies several components key to the faithful description of flow dynamics in a statistical sense. Based on the analysis of a couple of very large traces, we find that the proposed modeling framework are capable of capturing some of the essential characteristics of flow dynamics. We also identify that some of the widely used assumptions about flow modeling, such as Poisson flow arrivals and uniform/Poisson packet arrivals within flows underestimate the burstiness of flow dynamics. Instead, we find that flow arrivals appear to follow mono-fractal characteristics over time scales greater than 100 msec, and intra-flow packet dynamics exhibit an array of different statistical behaviors, including non-fractal, mono-fractal, and multi-fractal patterns. While these deviations from common modeling assumptions make faithful flow dynamics modeling a challenge, the proposed modeling framework paves the way for accurate flow simulation and provides plausible causes for complex packet-level dynamics such as multi-fractals.