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 be
> 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 packet
> 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
implementations.
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 computed
> 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. :)
Regards
--
Emmanuel Fleury
Ideals are dangerous things. Realities are better.
They wound but they are better.
-- Oscar Wilde
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[Index of Archives]
[Kernel Newbies]
[Netfilter]
[Bugtraq]
[Photo]
[Gimp]
[Yosemite News]
[MIPS Linux]
[ARM Linux]
[Linux Security]
[Linux RAID]
[Video 4 Linux]
[Linux for the blind]
| |
 |