PaperlayerView exact revision on arXiv

Source-linked AI summary

pForest: In-Network Inference with Random Forests

Coralie Busse-Grawitz, Roland Meier, Alexander Dietmüller, Tobias Bühler, Laurent Vanbever

arXiv:1909.05680v2cs.NI

TL;DR

Network traffic classification must balance early decisions against having enough evidence, and the optimal timing varies across flows. pForest trains phase-specific random forests and applies them as flows progress, accepting a label when its certainty meets a threshold. Its evaluation reports line-rate classification for hundreds of thousands of flows, with scores on par with software-based solutions.

  • Problem

    In-network classifiers either wait until a flow ends or use a fixed packet count, although the best classification time varies by task, workload, and flow.

    Source: §1 · p. 1

  • Method

    pForest trains a sequence of random forests for different flow phases, optimizes models and features for data-plane constraints, and switches models as packets arrive.

    Source: §1 · p. 2, §4.2 · p. 5, §11 · p. 12

  • Results

    pForest classifies at line rate for hundreds of thousands of flows with scores on par with software-based solutions.

    Source: §1 · p. 2, §11 · p. 12

  • Takeaways & Limitations

    pForest applies classification after the smallest amount of packet evidence possible while maintaining a high score, using random forests adapted to programmable data-plane constraints.

    Source: §11 · p. 12

    pForest does not address constructing a representative training dataset, and poor input data can result in poor performance.

    Source: §1 · p. 2

Abstract

from arXiv · show

When classifying network traffic, a key challenge is deciding when to perform the classification, i.e., after how many packets. Too early, and the decision basis is too thin to classify a flow confidently; too late, and the tardy labeling delays crucial actions (e.g., shutting down an attack) and invests computational resources for too long (e.g., tracking and storing features). Moreover, the optimal decision timing varies across flows. We present pForest, a system for "As Soon As Possible" (ASAP) in-network classification according to supervised machine learning models on top of programmable data planes. pForest automatically classifies each flow as soon as its label is sufficiently established, not sooner, not later. A key challenge behind pForest is finding a strategy for dynamically adapting the features and the classification logic during the lifetime of a flow. pForest solves this problem by: (i) training random forest models tailored to different phases of a flow; and (ii) dynamically switching between these models in real time, on a per-packet basis. pForest models are tuned to fit the constraints of programmable switches (e.g., no floating points, no loops, and limited memory) while providing a high accuracy. We implemented a prototype of pForest in Python (training) and P4 (inference). Our evaluation shows that pForest can classify traffic ASAP for hundreds of thousands of flows, with a classification score that is on-par with software-based solutions.

1 INTRODUCTION

pForest targets per-flow, as-soon-as-possible traffic classification, where waiting too long delays action and wastes resources, while classifying too early can leave too little evidence. It trains phase-specific random forests and adapts them to programmable-switch constraints; its evaluation reports line-rate classification at scale with scores on par with software solutions.

1 INTRODUCTION

  • Because the optimal packet count varies by task, workload, and flow, existing in-network approaches that wait until flow end or classify at a fixed packet count are suboptimal.Classifying too early can leave an insufficient basis for a confident decision; classifying too late can delay action and waste resources.Source: §1 · p. 1
  • pForest trains a sequence of random forests for different flow phases and switches among them as packets arrive, deciding per flow when classification is possible.The selected features and useful classification rules can change over a flow’s lifetime.Source: §1 · p. 1
  • pForest performs ASAP traffic classification at line rate for hundreds of thousands of flows, with scores on par with software-based solutions.The evaluation also confirms that pForest’s basic operations are supported on Intel Tofino hardware.Source: §1 · p. 2
  • pForest does not provide representative training data; building such a dataset is outside the paper’s scope, and poor input data can yield poor performance.Source: §1 · p. 2
  • pForest optimizes random forests and feature sets for programmable data planes, compiles the models for network devices, and allocates memory for feature storage.The approach accounts for switch operation and memory constraints while aiming to preserve classification score.Source: §1 · p. 2
  • The prototype uses Python for training and P4 for inference, and the evaluation spans synthetic and real datasets.The contributions also include compilation and dynamic feature-memory allocation techniques.Source: §1 · p. 2

2 BACKGROUND

This background introduces programmable data-plane constraints, random-forest classification, and the notation and thresholds used by pForest.

2.1 Programmable data planes

  • Programmable data planes use parsers, match-and-action pipelines, and deparsers; their fixed pipeline stages limit sequential table applications, and P4 lacks floating-point computations and loops.P4 supports the basic operations pForest requires, including addition, subtraction, min, max, bit shifts, and bit slices.Source: §2.1 · p. 2

2.2 Random forest classifiers

  • A random forest classifies a sample by majority vote across decision trees and reports certainty as the mean of the trees’ certainty scores.Each tree’s certainty is based on the fraction of training samples in its leaf that share the predicted label.Source: §2.2 · p. 3

2.3 Notation

  • A flow is a packet sequence sharing a five-tuple, and a subflow F[i:j] denotes a packet range within that flow.The first n packets are denoted F[:n].Source: §2.3 · p. 3
  • pForest uses τ_s as the minimum acceptable model F1 score and τ_c as the minimum certainty required to accept a predicted label.Source: §2.3 · p. 3

3 PFOREST OVERVIEW

pForest defines ASAP inference as classifying a flow as soon as its prediction is sufficiently confident. It trains random forests for different packet-count contexts and applies them as flows progress, accepting a label when its certainty crosses the operator’s threshold.

3 PFOREST OVERVIEW

  • ASAP inference combines context-dependent random forests with certainty-based labeling: pForest applies models as a flow progresses and accepts a label once certainty exceeds τ_c.Each model must meet the required quality threshold τ_s.Source: §3 · p. 3
  • The offline workflow extracts feasible features, trains models that meet a minimum score while minimizing hardware memory, then compiles and deploys them for runtime inference.Training and compilation can be performed in the control plane.Source: §3 · p. 3
  • pForest trains context-dependent random forests from labeled packet-level data, using features that can be computed in programmable network devices.It can use up to 18 popular network-traffic features per subflow and adapts computation, for example by replacing averages with moving averages.Source: §3 · p. 4
  • pForest compiles decision trees as sequences of match-and-action tables, enabling parallel tree application and runtime model updates through table entries.Source: §3 · p. 4
  • To handle the lack of dynamic memory management, pForest encodes multiple feature values in a register by reducing their bit-width and concatenating them.It dynamically allocates memory for features needed during inference.Source: §3 · p. 4
  • A higher τ_c requires waiting for greater prediction certainty, trading classification speed for confidence; pForest continues tracking a flow until certainty crosses the threshold.After accepting the label, it frees memory and stops tracking the flow.Source: §3 · p. 4

4 CONTEXT-DEPENDENT RANDOM FORESTS

pForest formulates ASAP classification as a hardware-feasible search for classifiers that meet an F1 threshold while balancing early decisions against per-flow memory. It approximates the search with context-specific random forests, selects features and models under device constraints, and combines the forests into a classifier that exceeds the threshold in evaluation.

4.1 Optimization problem

  • pForest seeks a hardware-feasible classifier with F1 at least τs while minimizing per-flow memory and classifying flows as early as possible.Waiting for another packet can permit fewer features and improve memory efficiency, trading off classification speed.Source: §4.1 · pp. 4–5

4.2 pForest greedy algorithm

  • Because exhaustive search over flows, flow lengths, and features is infeasible, pForest combines locally optimal RFs, reducing the search space from exponential to linear.A context is the first x packets of a flow; its RF must meet τs while minimizing memory and maximizing classification speed.Source: §4.1 · p. 5, §4.2 · p. 5
  • Each context-dependent RF meets τs using only the features needed to reach it, and the combined classifier exceeds τs in evaluation.When the first RF's label is accepted regardless of certainty, the overall score equals that model's score and is at least τs.Source: §4.2 · p. 5

4.3 Training context-dependent RFs

  • pForest extracts 18 traffic features per subflow and uses mutual-information distances with DBSCAN to cluster features.The feature extraction also splits data into training and test sets in a 9:1 proportion.Source: §4.3 · p. 5
  • For each redundant-feature group, pForest selects a representative using weighted memory, convergence-speed, and reuse costs; reuse matters more in later RFs.Memory cost reflects feature size, convergence cost the packets needed to compute a feature, and reuse cost whether an earlier model used it.Source: §4.3 · p. 5
  • Model search tunes tree depth, tree count, and class weights by six-fold cross-validation on macro F1, with device fit and class imbalance in view.The folds preserve class proportions, while macro F1 weights classes equally.Source: §4.3 · p. 6
  • After choosing a model, pForest retrains it on the full training set and selects it only if its test score exceeds τs.It incrementally adds features ranked by mean decrease in impurity until the score reaches τs, then reuses the most recent or a previously extracted RF while its score remains above τs.Source: §4.3 · p. 6

5 COMPILING RANDOM FORESTS TO THE DATA PLANE

pForest compiles context-dependent random forests into P4 code and configuration for programmable devices. It represents tree decisions in match&action tables and packs per-flow feature values into memory sized to support the models' threshold comparisons.

5.1 Compiler output

  • pForest compiles context-dependent RFs into program code and configuration, placing runtime-changeable model parts in configuration and hardware-fixed parts in code.Changing code requires a device restart, while configuration can be changed on the fly.Source: §5.1 · p. 6

5.2 Random forests in match&action tables

  • Each decision-tree level maps to a match&action stage that compares a feature with a threshold and routes to the next node; leaves assign labels and certainty.The RF's trees use separate tables, allowing parallel application, and their outputs are combined into a final label and certainty.Source: §5.2 · p. 6
  • For context-dependent RFs, a table maps the flow's packet count to the single RF applied to that packet's phase.Encoding these multiple RFs does not require additional tables beyond the encoding approach for one RF.Source: §5.2 · p. 7

5.3 Allocating feature memory

  • pForest reduces each feature's stored precision while preserving comparisons with model thresholds, then concatenates feature values into one bitstring for per-flow memory allocation.The precision calculation considers the threshold range across models using a feature; stored start and end indices locate each feature in the bitstring.Source: §5.3 · p. 7

6 ASAP INFERENCE IN THE DATA PLANE

The data-plane runtime parses packets, maintains per-flow features, applies the currently applicable forest, and labels flows when certainty exceeds a threshold.

6.1 Pipeline overview

6.2 Feature extraction

  • Because P4 lacks division and floating-point operations, pForest approximates averages with an EWMA and uses α = 0.5 so multiplications can become bit shifts.The EWMA combines the current value with the previous EWMA; α controls how strongly current values influence it.Source: §6.2 · p. 8

6.3 Feature memory management

  • Per-flow memory is a fixed-size bitstring divided into dynamically sized feature blocks, with each block sized to the precision its feature requires.The compiler defines feature locations in the bitstring, and pForest can deploy a new RF using different features without recompiling the P4 program.Source: §6.3 · p. 8, §6.3.2 · p. 8

6.3.1 Per-flow memory management.

  • Multiple hashes probe candidate registers for a flow; on CAIDA traces, hash-collision probability was ≈3.085 · 10−5, and no usable slot means forwarding without classification.A slot is usable when empty or when its previous flow packet is older than a predefined timeout.Source: §6.3.1 · p. 8

6.3.2 Per-feature memory management.

  • The compiler assigns each feature a location in the concatenated bitstring, which P4 extracts using bit slices or bit shifts.This layout supports feature blocks sized according to the precision required by each feature.Source: §6.3.2 · p. 8, §6.3 · p. 8

6.4 Certainty-based labeling

  • Each arriving packet triggers a classification attempt when an RF applies; pForest trusts labels above τc and then frees that flow’s allocated space.The RF is encoded as match&action tables specifying each node’s feature, threshold, and next node.Source: §6.4 · p. 8

7 IMPLEMENTATION

The implementation combines Python-based feature extraction, training, and compilation with P4 inference in a behavioral model and a Tofino hardware prototype.

Feature extraction and training

  • Feature extraction, training context-dependent RFs, and compiling them to P4 use about 17,000 lines of Python, with dpkt and scikit-learn.dpkt parses traffic and extracts features; scikit-learn computes RF models.Source: §7 · p. 8

Inference in the data plane

  • The behavioral-model inference program uses about 1,500 lines of P4_16 for an RF with 32 trees and maximum depth 10.The implementation was tested using Mininet; bmv2 does not support classification for offline flows after timeout.Source: §7 · p. 8

Hardware prototype

  • The Tofino hardware prototype supports counter and max/min features and RFs up to depth 4.The authors verified that pForest’s basic operations run on real hardware.Source: §7 · p. 9

8 EVALUATION

Across synthetic and real datasets, pForest’s evaluation tests context-dependent model training, per-flow classification timing, score, and memory use. Its reported scores are close to software baselines, while its training and runtime mechanisms adapt forest use and classification timing to each flow.

8 EVALUATION

  • The evaluation reports high scores in software and hardware and low memory use, and confirms that pForest’s required basic operations are supported on Intel Tofino.Source: §8 · p. 9

8.1 Datasets and methodology

  • Evaluation used one synthetic dataset and two public datasets, with Python runtime simulations comparing full-accuracy and hardware-style inference.The synthetic data contained 100,000 nine-packet flows with features designed to vary in relevance by flow phase; the models used at most 32 trees and depth 20.Source: §8.1 · p. 9

8.2 Context-dependent random forests

  • Training selected its first random forest at packet count 2, reused forests when their scores stayed above τs, and selected only necessary relevant features.The results link early forest use, reuse, and feature selection to lower memory consumption.Source: §8.2 · pp. 9–10

8.3 Speed of ASAP inference at runtime

  • After only three packets, pForest classified at least 82.5% of CICIDS flows across all four days, reaching 99.3% on Fri 1; rates were 99.1% Tue, 89.3% Fri 2, and 82.5% Fri 3.Source: §8.3 · p. 10

8.4 Score of ASAP inference at runtime

  • F1 macro score: pForest was never more than 0.03% below the online baseline or 7.9% below the offline baseline, and exceeded τs in all cases.For CICIDS, the reported gap from the offline baseline ranged from 0.2% (Fri 2) to 2% (Fri 3).Source: §8.4 · pp. 10–11
  • The certainty threshold allowed pForest to exceed τs by 14% for UNIBS Day 3 at packet count 7, while also enabling tuning of the percentage of classified flows.Varying τc over time is analogous to a control system on memory usage; τc is adaptable at runtime via controller communication, while implementing that broader system lies beyond the scope of the paper.Source: §8.4 · p. 11

8.5 Memory consumption of ASAP inference

  • Higher τs did not always mean greater memory use: for UNIBS Day 3, τs=0.6 yielded eight applicable forests, while τs=0.8 yielded four.The paper attributes this pattern to the higher threshold leaving fewer forests that satisfy the score requirement.Source: §8.5 · p. 11
  • Feature selection and optimization allow pForest to track hundreds of thousands of flows per 10MB of available memory.Per-flow memory includes a 49-bit model-independent part for the flow ID and timestamp, plus model-dependent feature storage.Source: Figure 8 · p. 11, §8.5 · p. 11

9 DISCUSSION

The discussion identifies extensions and operational constraints for pForest, including its memory-bounded flow tracking and current packet-sampling strategy.

Classifying other entities

  • The current system classifies flows, but the same approach also works for individual packets or hosts.Source: §9 · p. 11

Resource exhaustion attacks

  • Limited memory caps the number of concurrent flows pForest can track, although it can reclaim cells from idle flows using their last-packet timestamps.A malicious actor could initiate many flows to exhaust available memory.Source: §9 · p. 11

Distributing the classification

  • pForest uses a simple best-effort strategy to flag classified flows; actively routing flows to devices with classification capacity is described as a feasible, more sophisticated alternative.Source: §9 · p. 11

Other datasets

  • Absolute score and memory performance depend on the training dataset, while pForest optimizes models and feature sets for score and memory requirements.Datasets may come from third parties or be recorded from the operator’s network with automated labeling.Source: §9 · p. 11

Different packet sampling strategies

  • pForest’s current training algorithm builds its random-forest sequence over sampled packet counts such as 1, 3, 5, ... .The optimal sampling strategy depends on memory, classification-speed priority, feature-value variation, training-time constraints, and when relevant patterns appear.Source: §9 · p. 11

10 RELATED WORK

Related systems translate trees, forests, or other machine-learning models into network devices, but the cited approaches differ from pForest in early classification, training, and resource trade-offs.

RFs and DTs on network switches

  • Ilsy and Planter translate trained forests or trees to switches but do not optimize for early classification; their table strategies trade feature-range support against table-resource constraints.Ilsy uses exact-match tables, which can grow large for wide-ranging features; Planter uses range-match tables in more limited TCAM, and pForest instead stores and explicitly compares thresholds.Source: §10 · p. 12

Model compression and feature representations

  • Mousika and compress trained models without optimizing for early classification, while FlowLens bins features in power-of-two ranges that may mismatch pForest’s forest thresholds and reduce accuracy.The passage notes that ’s loss-free compression might work on pForest models, while Mousika does not support stateful features.Source: §10 · p. 12

Homunculus, pHeavy, and SwitchTree

  • Homunculus, pHeavy, and SwitchTree propose data-plane tree or forest methods, while SwitchTree and do not support early classification; SwitchTree also lacks automatic parameter tuning.Source: §10 · p. 12
  • Homunculus trains models under hardware constraints but does not generate a sequence of models; pForest searches a non-sampled grid of eligible parameters for each forest.The passage says Homunculus-style search could speed pForest training in future work.Source: §10 · p. 12
  • pHeavy spreads heavy-flow detection across models that must all be applied to confirm a flow is heavy, whereas pForest attempts all labels at each forest and defers only when uncertain.Source: §10 · p. 12

Other in-network machine learning

  • Other work implements neural networks, clustering, or reinforcement learning in network devices, and NetPixel uses an in-switch decision tree to classify images rather than flows.The paper characterizes these machine-learning approaches as complementary because the best choice depends on the task.Source: §10 · p. 12

11 CONCLUSION

pForest performs ASAP in-network inference with random forests by switching among models as flows progress. Its prototype evaluates accurate classification at scale.

11 CONCLUSION

  • pForest applies classification after the smallest possible number of packets while maintaining a high score, using a sequence of random forests switched as a flow progresses.The models are optimized during training for programmable-data-plane constraints, and the passage says this does not lower the achieved score.Source: §11 · p. 12
  • The prototype performs accurate ASAP classification for hundreds of thousands of flows.Source: §11 · p. 12

A TRAINING ALGORITHM

The appendix presents pForest’s greedy training algorithm, which searches packet counts and feature sets to produce a list of models and their use points.

A TRAINING ALGORITHM

  • The pseudocode describes the greedy algorithm; the training implementation is approximately 17,000 lines of Python and inference is approximately 1,500 lines of P4.Source: A TRAINING ALGORITHM · p. 15
  • The algorithm takes packet counts, features available up to those counts, completed-flow features, a confidence threshold, labels, and trade-off parameters, and outputs packet-count/model/feature assignments.Source: A TRAINING ALGORITHM · p. 15
  • Training first computes information distances among features and uses DBSCAN to find redundant feature groups.Source: A TRAINING ALGORITHM · p. 15
  • For successive packet counts, the algorithm updates trade-off parameters, selects representative features, and grid-searches for a random forest and score.Source: A TRAINING ALGORITHM · p. 15
  • It selects a minimal feature set with score meeting the threshold, retrains the forest, updates feature utility, and appends the model and feature names.Source: A TRAINING ALGORITHM · p. 15
  • When a model’s score exceeds the threshold, the greedy procedure can reuse the previous forest and feature names at the next packet count.Source: A TRAINING ALGORITHM · p. 15
Loading 1909.05680v2…