On Thu, 31 Oct 2002 17:59:31 +0100, Daniel Hartmeier wrote: > On Fri, Nov 01, 2002 at 02:14:58AM +1000, loki wrote: > > having such a rule (or rules) has several other advantages, you could > > create several trees, one for each proxy that requires it (include a > > mechanism for the proxy to talk to its own tree). you could specify which > > field of the state entry is variable (id still say that remote src port > > would be th only one, but its nice to be flexible). you could specify tcp > > flags and state modulation. whatever is needed for connections created by > > the proxy. > > I can't think of a case where anything but the source port is missing, > actually.
I just did, but in a way this is entirely unrelated to the proposed idea. Filter rules are, in their own way, a lot like embryonic states. They contain some information that a state does, but not all. Their other significant difference is that matching a non-quick rule does not determine whether the packet matches. To me this suggests creating embryonic states corresponding to filter rules and arranging them in trees; it feels like it would simplest to have the trees rooted by interface, but that may not be true in practice. At each node of the tree would be an embryonic state. For a packet to progress through the tree, it must be compared to the embryonic states of the children of the node it is currently in. If it matches none of them, the block/pass rule of its current node applies. If it matches one of them, that node becomes the packet's current node. Processing ends when the packet reaches a terminal node or no child of the current node matches the packet. Quick rules would always be terminal nodes. The major difficulty, as far as I can tell, is in creating the tree. No two children of the same node could ever match the same packet or else the ruleset becomes ambiguous. Furthermore, the "most efficient" tree is probably difficult to determine. Even an inefficient tree would likely take a while to create with a large ruleset, and I don't have any idea how one would insert or delete rules into an existing tree. The advantage, however, is that ruleset evaluation becomes very fast. If the tree is balanced, evaluation should be O(log n). The worst case should be a tree with a root and only terminal children, but that should still be O(n). You lose skip steps with such a case, though, so performance would be worse than it is now. But it feels to me like it should be possible to avoid such a pathological case with good tree construction. -- Kyle R. Hofmann <[EMAIL PROTECTED]>
