Re: Help with a tough question. RE: Firewall rule inspection overhead.

thanks for the thorough reply :). i'm still a bit lost though. i did
a bit of reading from the IEEE website that shows the average number of
rules in a firewall is 144 based on one research. so does that mean
that S = 72 (half of 144, since 50% is accepted)? How would I go about
determining the cost to evaluate one rule? I'm sorry, I'm very

On Oct 14, 11:43 pm, rober...@xxxxxxxxxxxx (Walter Roberson) wrote:
In article <1160879734.071268.254...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,

abstractclass <mea...@xxxxxxxxx> wrote:
I have no idea how to approach this question. Can anybody help? I'm
lost. Thx!
A firewall has S accept rules and receives R (packet/sec) traffic rate.
What is the total matching overhead in seconds if the cost of
evaluating one rule is X seconds and 50% is accepted (uniformly
distributed over rules). (Hint: firewalls are filtering devices that
inspecting incoming packets against policy rules sequentially till one
rule is matched)To answer the question, we have to make an assumption about the way the
firewall works, based upon hints in the way the question is phrased.

A normal firewall would have a mix of "accept" and "reject" rules, and
it would have a policy as to whether "running off the end of the rules"
meant to accept or to reject. In the question, we are not told whether
the policies being matched against are only "accept" or only "reject"
or are a mix of both, and we aren't told about what to do at the end of
the rules.

It makes a difference because we must know, "In order to accept a
packet, does that mean that S 'reject' rules were scanned and none
found applicable and so the packet was accepted by default, after X*S
seconds of work?" versus "In order to accept a packet, does that mean
that from 1 to S 'accept' rules were searched and one was found
applicable and so the packet was accepted explicitly after R * X
seconds of work (R being the rule number of the accepting rule)?"

It turns out that in this question, if we suppose -either- of those
models, then the answer will be the same -- the same because we are
told that exactly 1/2 are accepted and 1/2 rejected; if we were given
-any- other ratio, we would have to know the innards. But if it were a
mixed model, we'd need to know that as it would affect the

The phrase about 50% accepted "uniformly distributed over the rules"
hints that the model we are to use is "acceptance rules only, reject if
not accepted"; a filtering model of that style is quite poor at
expressing some common configurations.

Anyhow, if we do decide that we don't have a mixed accept/deny model,
then what you need to do to arrive at the calculation is to ask
yourself, "What is the -average- number of rules that are examined to
permit (deny) a packet?". Once that number is known, multiply that
average by the cost of processing that number of rules. Then calculate
the cost of the opposite way -- e.g., if the previous calculation was
for acceptance, then that would mean rejecting always required that all
S rules be examined; if the previous calculation was for rejection,
that that would mean -accepting always required examining all S rules.
Multiply that S rules by the cost per second per rule. You now have an
average cost to do it one one, and an average (fixed) cost to do it the
other way; multiply each of those costs by the relative probabilities
that that was the outcome, and add those two weighted costs together to
find the total average weighted cost.