Subject: [Policy] condition evaluation order

From: Mircea Pana <[email-masked]>
Date: Thu, 14 Feb 2002 16:09:42 -0500

PCIM and PCIMe do not provide a mechanism for ordering conditions in a
set (PolicyConditionStructure in PCIMe). This, mathematically speaking,
is correct because the boolean operators AND and OR are commutative
(E.g.: "a AND b" is equivalent to "b AND a").

However, in reality, the order of the operands (aggregated
PolicyConditions) may have an important impact on the performance of the
expression evaluation. This is true when shortcut evaluation is used
(evaluation stops as soon as the result is obvious) - and most compilers
support that.

Example 1: Among the two domain filters below, the evaluation of the
first one may be more efficient for packets coming from 10.x.x.x
sources. The evaluation of the second one may involve a DNS call for
every packet.
1. (SrcIP=10.x.x.x OR SrcIP=abc.bigco.com) AND DstIP=www.bigco.com
2. (SrcIP=abc.bigco.com OR SrcIP=10.x.x.x) AND DstIP=www.bigco.com

Example 2:
1. (Src=10.x.x.x OR Src=1.2.x.x OR Src=3.4.5.6) AND ...
2. (Src=3.4.5.6 OR Src=1.2.x.x OR Src=10.x.x.x) AND ...
Filter 1. may be more efficient than Filter 2. in an administrative
domain where the traffic has an equal distribution. However, in a domain
where Src=3.4.5.6 produces most of the traffic, Filter 2. may be more
efficient.

Has anybody encountered this issue yet? I would appreciate any
suggestions. I know that the PCIMe feature list is closed now, so I
guess that whatever I do to resolve this issue would be a non-standard
solution. Right?

Regards,
Mircea.

_______________________________________________
Policy mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/policy

---

From: Marcus Brunner <[email-masked]>
Date: Mon, 25 Feb 2002 16:57:13 +0100

Since this really implementation dependent I would like to stay out of it.
Additionally, I assume that PDPs/PEPs taking rules as input will convert 
them into an internal representation anyway. That step can be used to 
optimize for whatever execution engine you are running. And I think in most 
case you can define a heuristice to get good results.

Marcus

> guess that whatever I do to resolve this issue would be a non-standard

--------------------------------------
Dr. Marcus Brunner
Network Laboratories
NEC Europe Ltd.

E-Mail: [email-masked]
WWW:    http://www.ccrle.nec.de/
personal home page: http://www.brubers.org/marcus