Michael Bellion wrote: >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. > > It would seem, looking at the provided results and author's comments, that the following are true: - for small static rulesets there is little difference, my 200-600 rules run fine in either - for very large rulesets cf will currently perform better (if this is due to cache effects, may be less evident, since the server runs an application rather than being a dedicated network device). - cf can't do large dynamic rulesets, compile time > change interval - the iptables results don't represent server use with persistent sockets, like mail/usenet, in which most (~95%) packets match the first rule in INPUT (ESTABLISHED -> ACCEPT) and the complexity is in processing TCP/SYN packets and forwarding rules. Also: none of the results I've seen show the effect of many tracked sockets, the performance of one stream pushing a lot of packets is not the same as the same bitrate coming from 500-5k source IPs, at least if you use the INPUT rule noted above. >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. > The nf-HiPAC advantage seems to be in applications with moderate to large dynamic rulesets, in that it allows a lot of changes quickly. Don't give that up for throughput, the idea of being able to do 5-7 changes/sec on a 500-2k ruleset is exciting, and in some cases vital. Thanks to everyone working on improvements. -- bill davidsen CTO TMR Associates, Inc Doing interesting things with small computers since 1979