Jawaharlal Nehru University
Since firewalls need to filter all the traffic crossing the network perimeter, they should be able to sustain a very high throughput, or risk becoming a bottleneck. 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. Thus, algorithms from computational geometry can be applied. In this paper, the authors consider a classical algorithm that they adapted to the firewall domain. They call the resulting algorithm "Geometric Efficient Matching" (GEM). The GEM algorithm enjoys a logarithmic matching time performance.