% firewall_optimization

Nowadays network links reach high speed transmission and this brings with it the requirement of high speed network devices, security ones are not excluded from it.

Firewalls need to perform optimized algorithms for the packet classification that is a critical component for performance evaluation, because a packet is considered correctly handled if an action is performed on it. This is done by ordered sliding the list of the rules until the matching one or till the end with the default action, so the search is proportional to the length of the rule list \textit{O}(N), where N is the number of the rules~\cite{firewall-02}.

Hardware-based solutions use specialized memory called Content Addressable Memory (CAM) or Ternary CAM (TCAM), because they take advantages of hardware parallelism to match more than one rule in parallel. This gets a high speed lookup, but those memory types are limited in the number of entries.

Other solution follows the \textit{Aggregated Bit Vector} (ABV) approach which is able to perform \textit{n} parallel and independent lookups on one dimension, or the \textit{geometric algorithm}.

The delay, or \textit{skew}, introduced by the middle-boxes, depends on the the searching time before a matching rule is found, so the ordering of these rules became important.
Besides the lookup algorithms, \textit{Dynamic Rule-Ordering Optimization technique}~\cite{firewall-03} improves firewalls performance.
This new approach is made up of two layers, the upper layer contains the \textit{active rules}, which means all the most frequently matching rules ordered on the matching rate base. The second layer has all the \textit{inactive rules}, the rules that has no matching or performs less matching.