Traffic-adaptive Field Ordering for Improving Tree-rule Firewall Performance

Abstract

—Firewall performance depends heavily on the order in which packet fields are examined during rule matching. The Tree-Rule Firewall (TRF) organizes rules as a hierarchical tree whose levels correspond to packet fields, but existing designs fix the field-to-level assignment staticaly at compile time, which is suboptimal under non-stationary traffic. This paper proposes Automatic Field-Level Positioning (AFLP), a lightweight mechanism that monitors per-field elimination rates online and repositions field levels so that the most discriminating field always occupies the root. Three trigger strategies are evaluated: Periodic, Threshold-based Exponential Moving Average (EMA), and On-demand. Under a 90% skewed two-phase traffic model (10–200 rules, up to 100,000 packets, 30 repetitions per scenario), AFLP-Periodic reduces average comparisons per packet by up to 68.77% and total processing time by up to 51.60% relative to a static TRF, while AFLP-On-demand achieves 44.77% and 29.19% with a single repositioning event. Analysis of the Threshold-based strategy reveals a sensitivity trade-off between thrashing and under-triggering; an extended 378-configuration sweep locates a narrow workable regime at percent-level thresholds ( δ ≤ 0.02), motivating future work on adaptive trigger design. These results establish AFLP as a fully online mechanism that discovers a near-optimal field order—with an average optimality gap of 6.57% (maximum 8.72%) relative to the brute-force optimum—without offline search or prior traffic knowledge. This study is a proof of concept based entirely on software simulation with synthetic rule sets and traffic; the reported gains cannot be assumed to transfer directly to production environments without validation on real traffic traces