Likelihood-based inference for modelling packet transit from thinned\n flow summaries

Prosha A. Rahman, Boris Béranger, Matthew Roughan, Scott A. Sisson

TL;DR

This paper introduces a new likelihood-based framework to model individual network packet behavior using only "thinned" and summarized data (like NetFlow). By mathematically accounting for the data loss caused by sampling and aggregation, the authors provide a way to achieve high-accuracy statistical inference on massive network streams without needing to store every single packet.

What Problem Does This Paper Address?

Modern internet traffic is too fast and voluminous to record packet-by-packet. To manage this, network engineers use two "accounting compromises":

  1. Flow-level aggregation (NetFlow): Instead of recording every packet, they record a summary of a "flow" (e.g., start time, duration, and total packet count).
  2. Packet thinning: Only a small fraction of packets (e.g., 1 in 1,000) are actually inspected; the rest are discarded.

While these techniques save storage, they create a "statistical fog." Standard methods like the "method-of-moments" often fail or produce biased results because they don't explicitly account for the packets that were never recorded. This makes it incredibly difficult for researchers to build accurate models of traffic propagation or detect anomalies at the packet level.

Methods

The authors bridge this gap using Symbolic Data Analysis (SDA). Instead of treating a flow summary as a single point, they treat it as a "symbol" that represents an underlying distribution of latent (unobserved) packets.

Key components include:

  • The NetFlow Likelihood: A novel mathematical function that "integrates out" the missing information. It calculates the probability of seeing a specific flow summary given a packet-level model (like the Bartlett-Lewis renewal process).
  • Sub-sampled Likelihood: An extension that specifically models Bernoulli sampling (where each packet is kept with probability $q$).
  • Theoretical Proofs: The authors prove that their Maximum Likelihood Estimator (MLE) is consistent (it converges to the truth as you get more data) and asymptotically normal.
  • The "Ideal" Family: They identify that the Natural Exponential Family (NEF) of distributions is mathematically "perfect" for this task because its properties align naturally with the way flows are aggregated.

Datasets

The researchers evaluated their method using two primary sources:

  1. Synthetic Simulations: They generated artificial networks using a Zeta distribution for flow sizes (to mimic the "mice and elephants" nature of the web) and a Gamma distribution for packet inter-arrival times.
  2. Real-World Trace: A publicly available CAIDA (Center for Applied Internet Data Analysis) dataset from 2019, containing over 36 million packets captured over a one-minute period.

Key Insights and Ideas

  • Recovering the Latent: The most striking insight is that you can accurately estimate the parameters of individual packet arrivals even when you only observe a tiny fraction of the traffic and only in summarized form.
  • Data Efficiency vs. Storage: While the proposed MLE is computationally more "expensive" than simple arithmetic averages, it is far more data-efficient. It requires significantly fewer flows to reach a target accuracy compared to traditional methods.
  • The Failure of Moments: The paper demonstrates that traditional "method-of-moments" estimators often fail to converge, especially when dealing with "mouse flows" (very small flows), which make up the vast majority of internet traffic.
  • The NEF Advantage: If your packet-level model belongs to the Natural Exponential Family, the inference from summarized data is mathematically identical to having the full, un-summarized data.

Key Results

  • Accuracy: In simulations, the NetFlow MLE successfully converged to true values ($\alpha=0.6, \beta=526.32$) as the number of flows increased, even with sampling rates as low as $q=0.0001$.
  • Robustness: On real CAIDA data, the model (using a Log-Normal approximation) provided a satisfactory fit for packet inter-renewals, whereas naive models that ignored the sampling process failed completely.
  • Computational Trade-off: Computing the MLE on 4,553 thinned flows took about 3.8 hours, but the resulting dataset was 26 times smaller than the raw packet trace, representing a massive saving in data retention costs.

Limitations and Future Work

  • Computational Overhead: The primary bottleneck is the need to calculate "convolutions" (complex mathematical combinations) of probability densities. This becomes very slow if the model isn't "closed under convolution" (like the Gamma or Normal distributions are).
  • Flow Size Knowledge: The method currently requires either prior knowledge or a good empirical estimate of the distribution of flow sizes ($p_M$) to work effectively.
  • Future Directions: The authors suggest exploring closed-form approximations for more complex models (like Log-Normal) to speed up the optimization process for real-time network monitoring.

Summary updated

Abstract

The substantial growth of network traffic speed and volume presents practical\nchallenges to network data analysis. Packet thinning and flow aggregation\nprotocols such as NetFlow reduce the size of datasets by providing structured\ndata summaries, but conversely this impedes statistical inference. Methods\nwhich aim to model patterns of traffic propagation typically do not account for\nthe packet thinning and summarisation process into the analysis, and are often\nsimplistic, e.g.~method-of-moments. As a result, they can be of limited\npractical use.\n We introduce a likelihood-based analysis which fully incorporates packet\nthinning and NetFlow summarisation into the analysis. As a result, inferences\ncan be made for models on the level of individual packets while only observing\nthinned flow summary information. We establish consistency of the resulting\nmaximum likelihood estimator, derive bounds on the volume of traffic which\nshould be observed to achieve required levels of estimator accuracy, and\nidentify an ideal family of models. The robust performance of the estimator is\nexamined through simulated analyses and an application on a publicly available\ntrace dataset containing over 36m packets over a 1 minute period.\n
BibTeX
@article{rahman2022likelihood,
  author = {Prosha A. Rahman and Boris Béranger and Matthew Roughan and Scott A. Sisson},
  title = {{Likelihood-based inference for modelling packet transit from thinned\textbackslash\{\}n flow summaries}},
  journal = {IEEE Trans. Signal Inf. Process. Over Networks},
  year = {2022},
  doi = {10.1109/tsipn.2022.3188457},
}
Figure