The geometric efficient matching algorithm for firewalls

Abstract

Firewall packet matching can be viewed as a point location problem: each packet (point) has 5 fields (dimensions) which need to be checked against every firewall rule in order to find the first matching rule. We consider a packet matching algorithm, which we call the geometric efficient matching (GEM) algorithm. The GEM algorithm enjoys a logarithmic matching time performance, easily beating the linear time required by the naive matching algorithm. However, the algorithm's theoretical worst-case space complexity is O(n/sup 4/) for a rule-base with n rules. Based on statistics from real firewall rule-bases, we created a model that generates random, but non-uniform, rule-bases. We evaluated GEM via extensive simulation using this rule-base generator. Subsequently, we integrated GEM into the code of the Linux "iptables" open-source firewall. Our GEM-iptables implementation supports a throughput which is at least 5-10 times higher than that of the unoptimized iptables. Our implementation was able to match over 30,000 packets-per-second even with 10 thousand rules.