Hi
I am happy to announce the release of nf-HiPAC version 0.9.0
During the development of version 0.9.0 everything was ported to Linux kernel
2.6 and large parts of the kernel code have been rewritten.
The kernel patch is now fairly non-intrusive: it only adds one simple function
to ip_tables.c. The rest of the patch introduces new files to the kernel.
The new release fixes all known bugs and also introduces some new features.
Since the last release I have become part of MARA Systems AB
( http://www.marasystems.com ). MARA Systems AB is now the commercial backer
of the HiPAC Project and finances it completely. Together MARA Systems and I
will make sure that HiPAC is actively maintained and further developed under
the GNU GPL.
For all of you who don't know nf-HiPAC yet, here is a short overview:
nf-HiPAC is a full featured packet filter for Linux which demonstrates the
power and flexibility of HiPAC. HiPAC is a novel framework for packet
classification which uses an advanced algorithm to reduce the number of
memory lookups per packet. It is ideal for environments involving large rule
sets and/or high bandwidth networks.
nf-HiPAC provides the same rich feature set as iptables, the popular Linux
packet filter. The complexity of the sophisticated HiPAC packet
classification algorithm is hidden behind an iptables compatible user
interface which renders nf-HiPAC a drop-in replacement for iptables. Thereby,
the iptables' semantics of the rules is preserved, i.e. you can construct your
rules like you are used to. From a user's point of view there is no need to
understand anything about the HiPAC algorithm.
The nf-hipac user space tool is designed to be as compatible as possible to
'iptables -t filter'. It even supports the full power of iptables targets,
matches and stateful packet filtering (connection tracking) besides the native
nf-HiPAC matches. This makes a switch from iptables to nf-HiPAC very easy.
Usually it is sufficient to replace the calls to iptables with calls to
nf-hipac for your filter rules.
Why another packet filter?
Performance:
iptables, like most packet filters, uses a simple packet classification
algorithm which traverses the rules in a chain linearly per packet until a
matching rule is found (or not). Clearly, this approach lacks efficiency.
As networks grow more and more complex and offer a wider bandwidth linear
packet filtering is no longer an option if many rules have to be matched
per packet. Higher bandwidth means more packets per second which leads to
shorter process times per packet. nf-HiPAC outperforms iptables regardless
of the number of rules, i.e. the HiPAC classification engine does not
impose any overhead even for very small rule sets.
Scalability to large rule sets:
The performance of nf-HiPAC is nearly independent of the number of rules.
nf-HiPAC with thousands of rules still outperforms iptables with 20 rules.
Dynamic rule sets:
nf-HiPAC offers fast dynamic rules et updates without stalling packet
classification in contrast to iptables which yields bad update performance
along with stalled packet processing during updates.
More information about the project can be found at: http://www.hipac.org
The releases are published on: http://sourceforge.net/projects/nf-hipac/
Enjoy,
+---------------------------+
| Michael Bellion |
| <[email protected]> |
+---------------------------+
On Mon, 2005-26-09 at 04:45 +0200, Michael Bellion wrote:
> Hi
>
> I am happy to announce the release of nf-HiPAC version 0.9.0
>
> During the development of version 0.9.0 everything was ported to Linux kernel
> 2.6 and large parts of the kernel code have been rewritten.
> The kernel patch is now fairly non-intrusive: it only adds one simple function
> to ip_tables.c. The rest of the patch introduces new files to the kernel.
> The new release fixes all known bugs and also introduces some new features.
>
> Since the last release I have become part of MARA Systems AB
> ( http://www.marasystems.com ). MARA Systems AB is now the commercial backer
> of the HiPAC Project and finances it completely. Together MARA Systems and I
> will make sure that HiPAC is actively maintained and further developed under
> the GNU GPL.
>
>
Congratulations to yourself as well as your sponsor. I think this is
useful.
The iptables wrapper is certainly valuable.
Can you post some numbers relative to iptables?
Some tests with the following parameters would be helpful:
- Variable incoming packet rate (in packets per second)
- Variable packet sizes
- Variable number of users/filters
- Effect of adding/removing/modifying policies while under different
incoming traffic rates.
Just even simple non-stateful comparisons like i did with tc over here:
http://www.suug.ch/sucon/04/slides/pkt_cls.pdf
Or even better when you do these tests also try out with tc filter.
cheers,
jamal
Hi,
Did you solved your "size" issues when entering long list of rules ???
I'm still not convinced by your approach. :-/
These experiments have to be updated but can you comment on this:
http://www.cs.aau.dk/~mixxel/cf/experiments.html
Regards
--
Emmanuel Fleury
Houston, we've had a problem here.
-- Jack Swigert (Appolo XIII, April 13, 1970)
On Mon, 2005-26-09 at 13:24 +0200, Emmanuel Fleury wrote:
> Hi,
>
> Did you solved your "size" issues when entering long list of rules ???
>
> I'm still not convinced by your approach. :-/
>
> These experiments have to be updated but can you comment on this:
> http://www.cs.aau.dk/~mixxel/cf/experiments.html
To repeat the tests i mentioned earlier for clarity:
a) Variable incoming packet rate (in packets per second)
b) Variable packet sizes
c) Variable number of users/filters
d) Effect of adding/removing/modifying policies while under different
incoming traffic rates.
You seem to have taken care of most of the variables involved except for
#d below. If you look at my slides you will see why #d is important to
have in modern firewalls. I think if you have to first compile rules
then you will have issues, but it remains to be seen.
Several comments:
- Am i mistaken that your source of data is from somewhere in the
backbone? Would it be fair to say that something in the edge would be
more appropriate?
- Your header extraction tool creates "10 sets of rules"; is there a
reason for the number 10?
- Is tcpreplay the right tool? What does it give you that you cant use a
better blaster like pktgen?
- I think the blackbox monitor looking at the input vs output tool is
good. It will be more complete if you can quantify the input rate then
you can easily quantify output rate.
- While your results were useful in showing Mbps; they are incomplete by
not mentioning the packet size. A better metric would have been pps. But
even then mentioning packet size is also useful.
If you are going to run these tests in stateless firewalling as you did,
please consider using tc filter as well.
cheers,
jamal
Hi,
jamal wrote:
>
> To repeat the tests i mentioned earlier for clarity:
> a) Variable incoming packet rate (in packets per second)
> b) Variable packet sizes
> c) Variable number of users/filters
> d) Effect of adding/removing/modifying policies while under different
> incoming traffic rates.
>
> You seem to have taken care of most of the variables involved except
> for #d below. If you look at my slides you will see why #d is
> important to have in modern firewalls. I think if you have to first
> compile rules then you will have issues, but it remains to be seen.
That is right, the add/remove/modifying policies was still an issue when
we stopped working on this. But, I think we can solve this problem by
working on an incremental compiler. I have to admit that this require a
proof of concept. This issue is quite critical on our method.
> Several comments:
> - Am i mistaken that your source of data is from somewhere in the
> backbone? Would it be fair to say that something in the edge would be
> more appropriate?
The source of the data has been recorded from a backbone but all the
clients in the experimental setting are replaying part of it and sending
it to the gigabit switch.
> - Your header extraction tool creates "10 sets of rules"; is there a
> reason for the number 10?
No particular reason.
> - Is tcpreplay the right tool? What does it give you that you cant use
> a better blaster like pktgen?
The idea was to replay a realistic traffic. So we used a slightly
modified version of the tcpreplay (I don't remember what modifications
have been done, my co-author did it). I should definitely take a look at
pktgen.
> - I think the blackbox monitor looking at the input vs output tool is
> good. It will be more complete if you can quantify the input rate then
> you can easily quantify output rate.
Interesting suggestion. Thanks.
> - While your results were useful in showing Mbps; they are incomplete
> by not mentioning the packet size. A better metric would have been
> pps. But even then mentioning packet size is also useful.
Right, the packet size was 300bytes (I think this is mentioned in the
text but not highlighted in the figures). I agree with you about pps (we
were young and innocent at the time).
> If you are going to run these tests in stateless firewalling as you
> did, please consider using tc filter as well.
The spirit was to test a totally new idea, the plan was not really to
get integrated (yet) into any tool, so we did it like this. We might
have been wrong.
Thanks for your comments.
Regards
--
Emmanuel Fleury
The highest goal of computer science is to automate that
which can be automated.
-- D. L. VerLee
On Mon, 2005-26-09 at 14:13 +0200, Emmanuel Fleury wrote:
> That is right, the add/remove/modifying policies was still an issue when
> we stopped working on this. But, I think we can solve this problem by
> working on an incremental compiler. I have to admit that this require a
> proof of concept. This issue is quite critical on our method.
>
I think if you solve the lookup issue (which you seem to have) and this
you will be in good shape.
> > Several comments:
> > - Am i mistaken that your source of data is from somewhere in the
> > backbone? Would it be fair to say that something in the edge would be
> > more appropriate?
>
> The source of the data has been recorded from a backbone but all the
> clients in the experimental setting are replaying part of it and sending
> it to the gigabit switch.
>
Ok, makes sense.
> > - Is tcpreplay the right tool? What does it give you that you cant use
> > a better blaster like pktgen?
>
> The idea was to replay a realistic traffic. So we used a slightly
> modified version of the tcpreplay (I don't remember what modifications
> have been done, my co-author did it). I should definitely take a look at
> pktgen.
>
Both are useful tests. Benchmarking typically doesnt factor in realistic
- the rule of thumb being if you can win a benchmark you can do better.
The exception is when you make complex changes to win a benchmark; there
has to be a balance.
> > If you are going to run these tests in stateless firewalling as you
> > did, please consider using tc filter as well.
>
> The spirit was to test a totally new idea, the plan was not really to
> get integrated (yet) into any tool, so we did it like this. We might
> have been wrong.
I think the methodology was fine enough for what you were doing then;
academic time constraints apply and you can be forgiven for that ;->
Now that you have gone beyond academia and have some company behind your
work, it is only fair to compare against tc filter because it is in the
kernel and being used by some people.
I am willing to help consult for the tc filter side if you need help.
cheers,
jamal
Hi,
> Can you post some numbers relative to iptables?
We have some performance tests available at:
http://www.hipac.org/performance_tests/overview.html
We also have a list of the independent performance tests we know of:
http://www.hipac.org/performance_tests/independent.html
> Some tests with the following parameters would be helpful:
> - Variable incoming packet rate (in packets per second)
> - Variable packet sizes
> - Variable number of users/filters
> - Effect of adding/removing/modifying policies while under different
> incoming traffic rates.
Most of this parameters are used in the performance tests above.
The effect of adding/removing/modifying policies while under different
incoming traffic rates has not been tested in the above tests.
nf-HiPAC is based on a completely dynamic approach.
This means that the algorithm used in HiPAC makes sure that the lookup data
structure is not rebuild from scratch again as soon as you make a update of
the data structure.
Instead during an update of the policies only the required changes of the
lookup data structure are made. This guaranties that the packet processing is
only affected to the least possible amount during updates.
It would certainly be nice to see some benchmark results for this case.
nf-HiPAC is expected to handle this very well, because it was designed with
this case in mind.
Regards
+---------------------------+
| Michael Bellion |
| <[email protected]> |
+---------------------------+
On Mon, 2005-26-09 at 15:16 +0200, Michael Bellion wrote:
> Hi,
>
> > Can you post some numbers relative to iptables?
>
> We have some performance tests available at:
> http://www.hipac.org/performance_tests/overview.html
>
> We also have a list of the independent performance tests we know of:
> http://www.hipac.org/performance_tests/independent.html
>
Can you please post something against new kernels you are patching
against _today_? I recall these same graphs from a few years back but
even iptables has improved since.
Any issues you may find can only help you improve.
BTW, your tests were unfair to iptables; you should have had optimized
the rules with the assumption that someone needing that many rules would
probably have needed to do some optimization even with iptables.
Yes, it would only have taken one year to load 256K rules, but it would
have loaded eventually.
> > Some tests with the following parameters would be helpful:
> > - Variable incoming packet rate (in packets per second)
> > - Variable packet sizes
> > - Variable number of users/filters
> > - Effect of adding/removing/modifying policies while under different
> > incoming traffic rates.
>
> Most of this parameters are used in the performance tests above.
>
> The effect of adding/removing/modifying policies while under different
> incoming traffic rates has not been tested in the above tests.
>
> nf-HiPAC is based on a completely dynamic approach.
Very good. Please do more up to date testing and try to include tc
filter as well.
cheers,
jamal
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]> |
+---------------------------+
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
Hi,
> > 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)..
Sorry, but this is far away from the worst case for your scheme. Actually it
is a quite good case for your compiler, because every rule is fully specified
(meaning there are no wildcards in any rule) and there are no ranges or masks
involved.
Try using a mixed rule set that contains rules that only specify certain
dimensions and have wildcards on the other dimensions. Try using rules with
ranges and masks.
Try using overlapping rules, meaning rules that completely or partly overlap
other rules in certain dimensions.
This will make your data structure grow!
> > 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).
Yes, you are right. The HiPAC project has gone through some tough times over
the last 2 years. With MARA Systems the HiPAC Project has finally found a
strong partner that is fully committed to the concept of Open Source
Software. This allows me to continue the development of HiPAC under the GNU
GPL license.
> 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. :)
Ok, I'll do that :)
Regards,
+---------------------------+
| Michael Bellion |
| <[email protected]> |
+---------------------------+
Michael Bellion wrote:
>
> Sorry, but this is far away from the worst case for your scheme. Actually it
> is a quite good case for your compiler, because every rule is fully specified
> (meaning there are no wildcards in any rule) and there are no ranges or masks
> involved.
> Try using a mixed rule set that contains rules that only specify certain
> dimensions and have wildcards on the other dimensions. Try using rules with
> ranges and masks.
> Try using overlapping rules, meaning rules that completely or partly overlap
> other rules in certain dimensions.
> This will make your data structure grow!
I think you misunderstood our experiment. In fact, we were trying to
generate as much possible different singletons on the domain (each of
our rule was the header of a packet which have not been seen before),
because if we can group these rules into intervals, then our scheme is
having some advantages.
We were using IDD (Interval Decision Diagrams) which is a kind of
extended BDD (Binary Decision Diagrams) where you take your decision by
looking at a partition of the possible values of the variable. For
example, looking at the value x in [0,1024] where [0,128] leads to one
node in the decision tree, [129,256] to another and [257,1024] to a last
one. More this partition is fragmented more you increase the size of the
structure. Having a lot of overlap does certainly increase the number of
partitions, but adding singletons is the simplest way to increase the
number of partitions.
Take a look at this paper, maybe you can get some idea for your scheme
(it might be that some hybrid between your ideas and ours can make it):
http://www.cs.aau.dk/~fleury/download/papers/tc04.pdf
> Yes, you are right. The HiPAC project has gone through some tough times over
> the last 2 years. With MARA Systems the HiPAC Project has finally found a
> strong partner that is fully committed to the concept of Open Source
> Software. This allows me to continue the development of HiPAC under the GNU
> GPL license.
I'm always happy to see a firm funding some Open Source project. So, I
can do anything else but wishing you good luck for the future. :)
> Ok, I'll do that :)
Good. :)
Regards
--
Emmanuel Fleury
As usual, goodness hardly puts up a fight.
-- Calvin & Hobbes (Bill Waterson)
On Mon, Sep 26, 2005 at 04:45:46AM +0200, Michael Bellion wrote:
> Hi
>
> I am happy to announce the release of nf-HiPAC version 0.9.0
I'm happy to hear this, especially in the advent of the netfilter
develpoer workshop next week, and after a very long period of silence
from the nf-hipac project.
I'll make sure to have read through your 0.9.0 version source code until
then, to be able to give some feedback asap.
Looking forward to talking to you about it next week!
--
- Harald Welte <[email protected]> http://gnumonks.org/
============================================================================
"Privacy in residential applications is a desirable marketing option."
(ETSI EN 300 175-7 Ch. A6)
Hi
> > I am happy to announce the release of nf-HiPAC version 0.9.0
>
> Looking forward to talking to you about it next week!
Yes, I am looking forward to meet you and the rest of the netfilter developers
again at the workshop next week too. The workshop has always been a lot of
fun with a lot of interesting discussions. With the 2 days of the workshop
and the 2 extra days of hacking on code there will probably be plenty of time
to talk about the current state and future directions of the HiPAC project.
See you next week
Michael Bellion