Hi
> I'm still not convinced by your approach. :-/
You really should have a closer look at nf-HiPAC so that you know what you are
talking about!
Your Compact Filter takes a completely different approach than nf-HiPAC to
build the data structure used in the kernel for the packet classification
lookup.
Your Compact Filter uses a static compiler in user space. That compiler
transforms the rule set into boolean expressions and than uses operations
from predicate logic to optimize the rule set.
This has the big drawback that whenever only a single rule changes you have to
recompile the complete lookup data structure. So this approach is clearly not
suitable for scenarios depending on dynamic rule sets.
nf-HiPAC uses a completely different approach to build the lookup data
structure in the kernel. It is based on geometry.
This approach allows completely dynamic updates. During an update of the rules
only the required changes of the lookup data structure are made. The data
structure is NOT rebuild from scratch. This guarantees that the packet
processing is only affected to the least possible amount during updates.
Although nf-HiPAC and Compact Filter use completely different approaches and
algorithms to build the lookup data structure it is important that you
understand the following:
nf-HiPAC and Compact filter end up with a very very similar lookup data
structure in the kernel.
> These experiments have to be updated but can you comment on this:
> http://www.cs.aau.dk/~mixxel/cf/experiments.html
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.
This explains your test results.
Compact Filter and nf-HiPAC perform the same when they are both able to keep
their lookup data structure in the CPU caches and when they are both not able
to do so anymore.
Compact Filter is currently able to perform better in the area where it is
able to keep its data structure still in the caches while nf-HiPAC is not
able to do so anymore.
Most aspects of your performance tests are quite nice (e.g. the generating the
traffic by replaying a packet header trace).
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.
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.
-----------------
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.
Regards,
+---------------------------+
| Michael Bellion |
| <[email protected]> |
+---------------------------+
-
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]
| |
 |