Michael Bellion wrote:
> The current version of the algorithm used in nf-HiPAC does not optimize
> certain aspects of the lookup data structure in order to increase the speed
> of dynamic rule set updates.
> This means that the lookup data structure is larger than it really needs to
> because it contains some unnecessary redundancy.
Could you quantify how much this "unnecessary redundancy" does hit the
size of the filter. Because last time I looked it was quite huge (you
may have improve it). And having a fat kernel does not help in backbones.
> But your performance tests have a serious flaw:
> You construct your rule set by creating one rule for each entry in your
> header trace. This results in an completely artificial rule set that creates
> a lot of redundancy in the nf-HiPAC lookup data structure making it much
> larger than the Compact Filter data structure.
Yes, it was intended to be a worst case for our scheme (not realistic
but worst case). We were more interested in comparing the complexity of
the different algorithms better than the efficiency of several
I don't consider this as a flaw in our experiment because our goal was
different from having a real proof of concept (kind of having an
empirical evidence of a theoretical result).
> You have to understand that with real world rule sets the size of the
> lookup data structure will not be much different for Compact Filter and
> nf-HiPAC. This means that when you use real world rule sets there shouldn't
> be any noticeable difference in lookup performance betweeen Compact Filter
> and nf-HiPAC.
Might be right, but admit that the big problem of your algorithm is the
size of your data-structure in kernel-space. What you gain in speed, you
loose it in memory. And this IS an issue on routers (IMHO).
> I am currently working on a new improved version of the algorithm used in
> nf-HiPAC. The new algorithmic core will reduce memory usage while at the same
> time improving the running time of insert and delete operations. The lookup
> performance will be improved too, especially for bigger rulesets. The
> concepts and the design are already developed, but the implementation is
> still in its early stages.
> The new algorithmic core will make sure that the lookup data structure in the
> kernel is always fully optimized while at the same time allowing very fast
> dynamic updates.
> At that point Compact Filter will not be able to win in any performance test
> against nf-HiPAC anymore, simply because there is no way to optimize the
> lookup data structure any further.
Well, you already said this last time we had exchanged some mails
(it was more than one year ago if I count well).
Anyway, I doubt you can get something that you can update dynamically
AND small in size following your way of doing. But, prove me wrong and
I'll be happy. :)
Ideals are dangerous things. Realities are better.
They wound but they are better.
-- Oscar Wilde