NF-HIPAC: High Performance Packet Classification for Netfilter

NF-HIPAC: High Performance Packet Classification for Netfilter

Post by n.. » Fri, 27 Sep 2002 00:50:09



Hi,

nf-hipac aims to become a drop-in replacement for the iptables packet
filtering module. It implements a novel framework for packet classification
which uses an advanced algorithm to reduce the number of memory lookups per
packet. The module is ideal for environments where large rulesets and/or
high bandwidth networks are involved.

The algorithm code is designed in a way that it can be verified in userspace,
so the algorithm code itself can be considered correct. We are not able to
really verify the remaining files nfhp_mod.[ch] and the userspace tool
(nf-hipac.[ch]), but they are tested in depth and shouldn't contain any
critical bugs.

We have the results of some basic performance tests available on our web page.
The test compares the performance of the iptables filter table to the
performance of nf-hipac. Results are pretty impressive :-)

You can find the performance test results on our web page http://www.hipac.org
The releases can be downloaded from http://sourceforge.net/projects/nf-hipac/

Features:
    - optimized for high performance packet classification
      with moderate memory usage
    - completely dynamic:
        data structure isn't rebuild from scratch when inserting or
        deleting rules, so fast updates are possible
    - userspace tool syntax is very similar to the iptables syntax
    - kernel does not need to be patched
    - compatible to iptables: you can use iptables and nf-hipac at
      the same time:
        for example you could use the connection tracking module from
        iptables and match the states with nf-hipac
    - match support for:
        + source/destination ip
        + in/out interface
        + protocol (udp, tcp, icmp)
        + source/destination ports (udp, tcp)
        + icmp type
        + tcp flags
        + ttl
        + state match (conntrack module must be loaded)
   - /proc/net/nf-hipac:
        + algorithm statistics available via
            # cat /proc/net/nf-hipac
        + allows to dynamically limit the maximum memory usage
            # echo   >  /proc/net/nf-hipac

Enjoy,

+-----------------------+----------------------+
|   Michael Bellion     |     Thomas Heinz     |

+-----------------------+----------------------+

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

 
 
 

NF-HIPAC: High Performance Packet Classification for Netfilter

Post by David S. Mille » Fri, 27 Sep 2002 01:10:04



   Date: Thu, 26 Sep 2002 00:41:56 +0200

   We have the results of some basic performance tests available on our web page.
   The test compares the performance of the iptables filter table to the
   performance of nf-hipac. Results are pretty impressive :-)

You missed the real trick, extending the routing tables to
do packet filter rule lookup.  That's where the real
performance gains can be found, and how we intend to eventually
make all firewalling/encapsulation/et al. work.

Such a scheme can even obviate socket lookup if implemented properly.
It'd basically be a flow cache, much like route lookups but with an
expanded key set and the capability to stack routes.  Such a flow
cache could even be two level, with the top level being %100 cpu local
on SMP (ie. no shared cache lines).

We have to do the route lookup anyways, if it got you to the packet
filtering tables (or ipsec encap information, or TCP socket, etc etc)
as a side effect, lots of netfilter becomes superfluous because all it
is doing is maintaining these lookup tables etc. which is what you are
optimizing.

Everyone looks to optimize these things on such a local level, and
that's not where the real improvements live.  Think globally, and the
more powerful solutions are much more evident.

Everything, from packet forwarding, to firewalling, to TCP socket
packet receive, can be described with routes.  It doesn't make sense
for forwarding, TCP, netfilter, and encapsulation schemes to duplicate
all of this table lookup logic and in fact it's entirely superfluous.

This stackable routes idea being worked on, watch this space over the
next couple of weeks :-)
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

 
 
 

NF-HIPAC: High Performance Packet Classification for Netfilter

Post by Rik van Rie » Fri, 27 Sep 2002 02:20:05



> Everything, from packet forwarding, to firewalling, to TCP socket
> packet receive, can be described with routes.

QoS stuff too ?

Rik
--
Bravely reimplemented by the knights who say "NIH".

http://www.surriel.com/             http://distro.conectiva.com/


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

 
 
 

NF-HIPAC: High Performance Packet Classification for Netfilter

Post by David S. Mille » Fri, 27 Sep 2002 02:40:06



   Date: Wed, 25 Sep 2002 21:10:02 -0300 (BRT)


   > Everything, from packet forwarding, to firewalling, to TCP socket
   > packet receive, can be described with routes.

   QoS stuff too ?

It is definitely possible.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

 
 
 

NF-HIPAC: High Performance Packet Classification for Netfilter

Post by n.. » Fri, 27 Sep 2002 02:50:05


Hi,

Quote:> You missed the real trick, extending the routing tables to
> do packet filter rule lookup.  That's where the real
> performance gains can be found, ...

Yes, that's certainly true. But we have to take step by step.
We started our project in August 2001 and up to now almost all our work went
into developing and optimizing the algorithm and not into an optimal
integration into the linux kernel. We chose the netfilter integration as a
first step, because it was easy and fast to do. It doesn't break anything in
the kernel, no kernel patch is needed, it can be used together with other
existing netfilter/iptables modules and switching from the iptables filter
module to nf-hipac is really easy.

We have now basically finished the work on the algorithm itself. We can now
concentrate on porting the algorithm to other fields and on a better
integration into the kernel. We designed the algorithm code in a way that
allows to port it to other fields than packetfiltering without much work.  
We were aware from the beginning that combining several fields (e.g. routing
and filtering) is THE way to go and it is no problem to support this with our
algorithm.
Our algorithm is already fast with a small number of rules, but what makes it
really interesting is, that it is possible to use huge rulesets/routing
tables/qos ... without much slowing down performance. In practical use people
won't notice much of a difference between using 25 or 25000 rules.  

The nf-hipac team
        Michael Bellion, Thomas Heinz

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

 
 
 

NF-HIPAC: High Performance Packet Classification for Netfilter

Post by David S. Mille » Fri, 27 Sep 2002 02:50:06



   Date: Thu, 26 Sep 2002 02:38:06 +0200

   > You missed the real trick, extending the routing tables to
   > do packet filter rule lookup.  That's where the real
   > performance gains can be found, ...

   Yes, that's certainly true. But we have to take step by step.

All the work you will spend to validate all the converted modules
will be equal if not greater to doing the algorithm correctly.

So why not do it correctly from the start? :-)

Seriously, just sit tight with your work, and once the stackable
route stuff is done, you can look into applying your algorithms
to the new flow cache.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

 
 
 

NF-HIPAC: High Performance Packet Classification for Netfilter

Post by n.. » Fri, 27 Sep 2002 03:50:04


Quote:> Seriously, just sit tight with your work, and once the stackable
> route stuff is done, you can look into applying your algorithms
> to the new flow cache.

Sorry, we are a bit confused of the formulation "adding the algorithmus to the
new flow cache"
Why to the flow cache? What exaclty is the job of this flow cache?
Does the job go beyond caching recently "lookup results"?
What happens if the flow cache doesn't have a certain lookup result in the
cache yet?
We mean, how is the packet classification solved then?
Is it right, that the code will then use a linear search algorithm and compare
the packet with each rule sequentially until a rule is found that matches all
relevant fields?

Our algorithm does not implement some kind of cache. Our algorithm is actually
a replacement for that linear search algorithm. Our algorithm implements an
advanced approach to the packet classification problem itself.

the nf-hipac team
        Michael Bellion, Thomas Heinz

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

 
 
 

NF-HIPAC: High Performance Packet Classification for Netfilter

Post by David S. Mille » Fri, 27 Sep 2002 05:40:05



   Date: Thu, 26 Sep 2002 03:44:26 +0200

   Sorry, we are a bit confused of the formulation "adding the
   algorithmus to the new flow cache"
   Why to the flow cache? What exaclty is the job of this flow cache?
   Does the job go beyond caching recently "lookup results"?

It is just a lookup function, keyed on whatever we'd like to take
from the incoming packet.

I mean that if you find a stronger hash/lookup architecture that
is faster for this purpose, we can integrate into _whatever_
scheme we end up using.

   What happens if the flow cache doesn't have a certain lookup result
   in the cache yet?

It goes to the level 2 lookup tables, which are slightly more complex
yet are still reasonably fast for lookups.

   Is it right, that the code will then use a linear search algorithm and compare
   the packet with each rule sequentially until a rule is found that matches all
   relevant fields?

No linear search, but because we'll be doing masked/prefix lookups
on the various keys the lookup table will be different than the one
at the top level which uses perfect comparison results.

Just look at how the routing code works now, the final result will
be architected not much differently.

Franks a lot,
David S. Miller

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

 
 
 

NF-HIPAC: High Performance Packet Classification for Netfilter

Post by David S. Mille » Fri, 27 Sep 2002 07:50:05



   Date: Thu, 26 Sep 2002 15:19:33 +1000

   3) If you want to keep counters in the subsystems (eg. iptables keeps packet
      and byte counters at the moment for every rule because it's easy). You
      need to keep this info in your route cache, then call the subsystems when
      you evict something from the cache.

The flow cache, routing table, whatever you want to call it, doesn't
care what your info looks like, that will be totally private.

Actually the idea is that skb tagging would not be needed, the
skb->dst would _BE_ the tag.  From it you could get at all the
info you needed.

Draw a picture in your head as you read this.

The private information could be a socket, a fast forwarding path, a
stack of IPSEC decapsulation operations, netfilter connection tracking
info, anything.

So skb->dst could point to something like:

        struct socket_dst {
                struct dst_entry dst;
                enum dst_type dst_type;
                struct sock *sk;
        }

Here dst->input() would be tcp_ipv4_rcv().

It could just as easily be:

        struct nf_conntrack_dst {
                struct dst_entry dst;
                enum dst_type dst_type;
                struct nf_conntrack_info *ct;
        }

And dst->input() would be nf_conntrack_input(), or actually something
more specific.

See?

And when you have the "drop packet" firewall rule, the skb->dst then
points to nf_blackhole() (which perhaps logs the event if you need to
do that).

If you have things that must happen in a sequence to flow through
your path properly, that's where the "stackable" bit comes in.  You
do that one bit, skb->dst = dst_pop(skb->dst), then your caller
will pass the packet on to skb->dst->{output,input}().

Is it clearer now the kind of things you'll be able to do?

Stackable entries also allow encapsulation situations to propagate
precisely calculated PMTU information back to the transports.

Cached entries are created by demand, the level 2 lookup area is
where long term information sits.  The top level lookup engine
carries cached entries of whatever is active at a given moment,
that is why I refer to it as a flow cache sometimes.

All of this was concocted to do IPSEC in a reasonable way, but as a
nice side effect it ends up solving a ton of other problems too.  I
think some guy named Linus once told me that's the indication of a
clean design. :-)

...

Let me give another example of how netfilter could use this.  Consider
FTP nat stuff, you'd start with the "from TCP, any address/anyport, to
any address/ FTP port" DST.  This watches for new FTP connections, so
you can track them properly and do NAT or whatever else.  This
destination would drop anything other only than SYN packets.  It's
dst->input() would point to something like ftp_new_connection_input().

When you get a new connection, you create a destination which handles
the translation of specifically THAT ftp connection (ie. specific
instead of "any" addr/port pairs are used for the key).  Here,
dst->input() would point to ftp_existing_connection_input().
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

 
 
 

NF-HIPAC: High Performance Packet Classification for Netfilter

Post by James Morri » Fri, 27 Sep 2002 17:30:12



> If you have things that must happen in a sequence to flow through
> your path properly, that's where the "stackable" bit comes in.  You
> do that one bit, skb->dst = dst_pop(skb->dst), then your caller
> will pass the packet on to skb->dst->{output,input}().

> Is it clearer now the kind of things you'll be able to do?

So, this could be used for generic network layer encapsulation, and be
used for GRE tunnels, SIT etc. without the kinds of kludges currently in
use?  Sounds nice.

- James
--
James Morris

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

 
 
 

NF-HIPAC: High Performance Packet Classification for Netfilter

Post by David S. Mille » Fri, 27 Sep 2002 23:10:04



   Date: Fri, 27 Sep 2002 01:27:41 +1000 (EST)

   So, this could be used for generic network layer encapsulation, and be
   used for GRE tunnels, SIT etc. without the kinds of kludges currently in
   use?  Sounds nice.

Such IPIP tunnels have very real problems though, since only 64-bits
of packet quoting are required in ICMP errors, it is often impossible
to deal with PMTU requests properly, see "#ifndef
I_WISH_WORLD_WERE_PERFECT" in net/ipv4/ip_gre.c
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

 
 
 

NF-HIPAC: High Performance Packet Classification for Netfilter

Post by jama » Sat, 28 Sep 2002 16:30:05


Dave,

now that i followed the thread on lk (slrn is great; thanks Jason);
I am actually interested to find out how you are going to pull what
you propose ;-> There are not that many things that will work well
with a dst-cache like idea. I actually considered the stacking idea
when i first was trying to prototype code that i posted. It is much harder
to make use of in practise. At least this is my experience.
If you look at the scheme i posted, youll see that the policy
could be to direct the packets to a IPV4-forwarding block or
totaly bypass it etc (i just didnt wanna jump into that step yet sicne it
is quiet involved architecturaly)
In any case we need to encourage people like the hipac authors to be
putting out things (i only wish theyd incorporate it into the tc
framework!); whatever changes made should consider that there is
more than one way to do things and people will always come with better
ways to do certain portions of the packet path.

cheers,
jamal



>    Date: Fri, 27 Sep 2002 01:27:41 +1000 (EST)

>    So, this could be used for generic network layer encapsulation, and be
>    used for GRE tunnels, SIT etc. without the kinds of kludges currently in
>    use?  Sounds nice.

> Such IPIP tunnels have very real problems though, since only 64-bits
> of packet quoting are required in ICMP errors, it is often impossible
> to deal with PMTU requests properly, see "#ifndef
> I_WISH_WORLD_WERE_PERFECT" in net/ipv4/ip_gre.c

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
 
 
 

NF-HIPAC: High Performance Packet Classification for Netfilter

Post by David S. Mille » Sun, 29 Sep 2002 03:40:05



   Date: Fri, 27 Sep 2002 10:12:26 -0400 (EDT)

   whatever changes made should consider that there is more than one
   way to do things and people will always come with better ways to do
   certain portions of the packet path.

Of course.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/