iptables performance and alternatives

iptables performance and alternatives

[Anton]

Regarding the performance of the lookup of the iptables 
rules for match inside the kernel, is there any plans to 
improve the behaviour or no plans in this area yet?

For example on the transit gateway I have ~500 rules which 
mark the packet, according to the client source IP - with 
unique mark per client IP - so I have 500 unique marks 
there, and so cannot use IPSET, and only IPTABLES - but 
it's known that iptables insert/lookup is very slow on huge 
rulesets (atleat with iptables 1.3.x) and slowness 
progresses approximatelly exponentially on growth of rules 
number.

Do I miss anything?

Re: iptables performance and alternatives

[Jan Engelhardt]

On Thursday 2008-05-15 11:21, Anton wrote:

>Regarding the performance of the lookup of the iptables 
>rules for match inside the kernel, is there any plans to 
>improve the behaviour or no plans in this area yet?
>
>For example on the transit gateway I have ~500 rules which 
>mark the packet, according to the client source IP - with 
>unique mark per client IP - so I have 500 unique marks 
>there, and so cannot use IPSET, and only IPTABLES - but 
>it's known that iptables insert/lookup is very slow on huge 
>rulesets (atleat with iptables 1.3.x) and slowness 
>progresses approximatelly exponentially on growth of rules 
>number.
>
>Do I miss anything?

You missed IPMARK from Xtables-addons which does the marking
in O(1) instead of O(n).

Re: iptables performance and alternatives

[Anton]

On Thursday 15 May 2008 14:26, Jan Engelhardt wrote:
> On Thursday 2008-05-15 11:21, Anton wrote:
> > IPTABLES - but it's known that iptables insert/lookup
> > is very slow on huge rulesets (atleat with iptables
> > 1.3.x) and slowness progresses approximatelly
> > exponentially on growth of rules number.
> >
> >Do I miss anything?
>
> You missed IPMARK from Xtables-addons which does the
> marking in O(1) instead of O(n).

Great! This partially solves problem with marking while used 
with shaper, but in global scope - iptables remains slow?

Re: iptables performance and alternatives

[Jan Engelhardt]

On Thursday 2008-05-15 12:35, Anton wrote:
>> You missed IPMARK from Xtables-addons which does the
>> marking in O(1) instead of O(n).
>
>Great! This partially solves problem with marking while used 
>with shaper, but in global scope - iptables remains slow?

Slow, where?

Re: iptables performance and alternatives

[Anton]

Definitelly what my test shows - while rule-inserts - if you 
try to insert 10000 rules - after a several hundreds - it 
will be inserting like a 1 rule in 1 second and slowness 
will progress :)

regarding the further slowness inside the kernel - i'm 
reffering to the following tests, since did not do mine

http://people.netfilter.org/kadlec/nftest.pdf

and

http://www.hipac.org/performance_tests/independent.html

On Thursday 15 May 2008 15:43, Jan Engelhardt wrote:
> On Thursday 2008-05-15 12:35, Anton wrote:
> >> You missed IPMARK from Xtables-addons which does the
> >> marking in O(1) instead of O(n).
> >
> >Great! This partially solves problem with marking while
> > used with shaper, but in global scope - iptables
> > remains slow?
>
> Slow, where?

Re: iptables performance and alternatives

[Jan Engelhardt]

On Thursday 2008-05-15 12:57, Anton wrote:

>Definitelly what my test shows - while rule-inserts - if you 
>try to insert 10000 rules - after a several hundreds - it 
>will be inserting like a 1 rule in 1 second and slowness 
>will progress :)

Your insertion slowness is probably due to incorrect use of iptables.

Re: iptables performance and alternatives

[Anton]

On Thursday 15 May 2008 16:18, Jan Engelhardt wrote:
> On Thursday 2008-05-15 12:57, Anton wrote:
> >Definitelly what my test shows - while rule-inserts - if
> > you try to insert 10000 rules - after a several
> > hundreds - it will be inserting like a 1 rule in 1
> > second and slowness will progress :)
>
> Your insertion slowness is probably due to incorrect use
> of iptables.

Possible too. 

But aside of use of IPMARK from xtables, if I have to match 
80  (prio traffic)  22(realtime) port for every customer IP 
and customer's ip too (bulk traffic) for another mark set 
and all with different htb queues - IPMARK will not help 
and in case of, say, 1000 matching IP's, it comes to 4 
queues per , with 3 to use with lending/borrowing (main, 
80, and 22) and 3000 queuses in total, plus POSTROUTING 
mangle rule per park (3000 rules) + 3000 return rules 
(6000) rules and so on. If this PC also do NAT for 
matches - it will come with extra 1000 rules (or single 
IPSET :)

If there is a better approach to this in relation to 
IPTABLES - this would be just great...

Re: iptables performance and alternatives

[Jan Engelhardt]

On Thursday 2008-05-15 13:29, Anton wrote:
>On Thursday 15 May 2008 16:18, Jan Engelhardt wrote:
>> On Thursday 2008-05-15 12:57, Anton wrote:
>> >Definitelly what my test shows - while rule-inserts - if
>> > you try to insert 10000 rules - after a several
>> > hundreds - it will be inserting like a 1 rule in 1
>> > second and slowness will progress :)
>>
>> Your insertion slowness is probably due to incorrect use
>> of iptables.
>
>Possible too. 
>
>But aside of use of IPMARK from xtables, if I have to match 
>80  (prio traffic)  22(realtime) port for every customer IP 

prio and realtime sound quite the same :p

>and customer's ip too (bulk traffic) for another mark set 
>and all with different htb queues - IPMARK will not help 
>and in case of, say, 1000 matching IP's, it comes to 4 
>queues per , with 3 to use with lending/borrowing (main, 
>80, and 22) and 3000 queuses in total, plus POSTROUTING 
>mangle rule per park (3000 rules) + 3000 return rules 
>(6000) rules and so on. If this PC also do NAT for 
>matches - it will come with extra 1000 rules (or single 
>IPSET :)
>
>If there is a better approach to this in relation to 
>IPTABLES - this would be just great...

Write your own module that sets the mark according to your taste, it is not
that hard. I have a semibook ("big pdf") on that entitled "Writing your own
Netfilter modules" on http://jengelh.medozas.de/. You can easily use IPMARK
as a base.

Re: iptables performance and alternatives

[Anton VG]

2008/5/15 Jan Engelhardt <jengelh@medozas.de>:
>
> On Thursday 2008-05-15 13:29, Anton wrote:
>
> prio and realtime sound quite the same :p
>

:) yea, just realtime has a little more prio than prio is :-D
i filed that you will note it :)

>>queues per , with 3 to use with lending/borrowing (main,
>
> Write your own module that sets the mark according to your taste, it is not
> that hard. I have a semibook ("big pdf") on that entitled "Writing your own
> Netfilter modules" on http://jengelh.medozas.de/. You can easily use IPMARK
> as a base.
>

I've looked at it few days ago, just feel that I have to be more brave
to touch kernel from inside :) Will get there sometime.
You are right from one side, the module with exactly fits to a need is
the best way,
But for the universal approach, in the ideal case, some changes in the
iptables storage and matching scheme
makes sense too... but having lots of matching targets and so on makes
question not so simple I feel...

Re: iptables performance and alternatives

[Thomas Jacob]

On Thu, 2008-05-15 at 13:18 +0200, Jan Engelhardt wrote:
> On Thursday 2008-05-15 12:57, Anton wrote:
> 
> >Definitelly what my test shows - while rule-inserts - if you 
> >try to insert 10000 rules - after a several hundreds - it 
> >will be inserting like a 1 rule in 1 second and slowness 
> >will progress :)
> 
> Your insertion slowness is probably due to incorrect use of iptables.

What do you mean by that? Isn't it a fact, that the iptables command
utility and to a  lesser extent also iptables-restore  is pretty slow in
updating the ruleset when you have a large number of rules, simply
because it copies the entire ruleset to userspace, modifies it there,
and then copies the resulting rule set back to the kernel? 

Curious...
    
    Thomas

Re: iptables performance and alternatives

[Jesper Dangaard Brouer]

On Thu, 15 May 2008, Thomas Jacob wrote:

> On Thu, 2008-05-15 at 13:18 +0200, Jan Engelhardt wrote:
>> On Thursday 2008-05-15 12:57, Anton wrote:
>>
>>> Definitelly what my test shows - while rule-inserts - if you
>>> try to insert 10000 rules - after a several hundreds - it
>>> will be inserting like a 1 rule in 1 second and slowness
>>> will progress :)
>>
>> Your insertion slowness is probably due to incorrect use of iptables.
>
> What do you mean by that? Isn't it a fact, that the iptables command
> utility and to a  lesser extent also iptables-restore  is pretty slow in
> updating the ruleset when you have a large number of rules, simply
> because it copies the entire ruleset to userspace, modifies it there,
> and then copies the resulting rule set back to the kernel?

Yes, its true that iptables is slow with large rule sets (even when using 
iptables-restore).  It does copy the entire ruleset everytime, but the 
copy process (between userspace and kernel) is not the slow part, its the 
parsing the ruleset (libiptc).

I have fixed some of the ruleset parsing issues in libiptc. (50k chains 
ruleset listing reduced from 5 minuts to 0.5 sec).

(Already accepted in latest SVN/git:)
  http://git.netfilter.org/cgi-bin/gitweb.cgi?p=iptables.git;a=commit;h=73ff92a2b0f338374a1f9830009d38b1f0ccaf42

There are still some libiptc scalability issues left... That I promised 
Patrick I would solve... Lets hope I'll fix them before the workshop ;-)

If doing a lot of rule changes, you should definitly use iptables-restore 
or CPAN perl module IPTables::libiptc.

Hilsen
   Jesper Brouer

--
-------------------------------------------------------------------
MSc. Master of Computer Science
Dept. of Computer Science, University of Copenhagen
Author of http://www.adsl-optimizer.dk
-------------------------------------------------------------------

Re: iptables performance and alternatives

[Thomas Jacob]

[..
> I have fixed some of the ruleset parsing issues in libiptc. (50k chains 
> ruleset listing reduced from 5 minuts to 0.5 sec).
> 
[..]
> There are still some libiptc scalability issues left... That I promised 
> Patrick I would solve... Lets hope I'll fix them before the workshop ;-)

That's great news, hopefully those changes will end up in the mainline
releases pretty soon ;-)

> If doing a lot of rule changes, you should definitly use iptables-restore 
> or CPAN perl module IPTables::libiptc.

Incidentally, what happens during the time changes are being processed
by iptables-restore/the kernel. More specifically, do I need to
worry about packets being blocked/dropped when I would do a lot of
rule updates?

    Regards,
           Thomas

Re: iptables performance and alternatives

[Jesper Dangaard Brouer]

On Mon, 19 May 2008, Thomas Jacob wrote:

>> If doing a lot of rule changes, you should definitly use iptables-restore
>> or CPAN perl module IPTables::libiptc.
>
> Incidentally, what happens during the time changes are being processed
> by iptables-restore/the kernel. More specifically, do I need to
> worry about packets being blocked/dropped when I would do a lot of
> rule updates?

Packet will not get dropped while userspace (iptables/libiptc) is making 
changes to the ruleset. Its allowed to make many many changes in userspace 
before commiting it to the kernel.

When commiting the ruleset to the kernel, the kernel will have both the 
old and new ruleset before it swaps the two.  I have not measured the 
performance hit of swaping the rulesets, but it should be insignificant.

Cheers,
   Jesper Brouer

--
-------------------------------------------------------------------
MSc. Master of Computer Science
Dept. of Computer Science, University of Copenhagen
Author of http://www.adsl-optimizer.dk
-------------------------------------------------------------------

Re: iptables performance and alternatives

[Henrik Nordstrom]

On tor, 2008-05-15 at 15:57 +0500, Anton wrote:
> Definitelly what my test shows - while rule-inserts - if you 
> try to insert 10000 rules - after a several hundreds - it 
> will be inserting like a 1 rule in 1 second and slowness 
> will progress :)

If you need to change add many rules then iptables-restore is the tool
to use. Batches the updates in a single transaction, instead of one
transaction per rule...

Regards
Henrik

Re: iptables performance and alternatives

[Anton VG]

Hm... I feel I've tried iptables-restore, but speed was about the same.

2008/5/15 Henrik Nordstrom <henrik@henriknordstrom.net>:
> On tor, 2008-05-15 at 15:57 +0500, Anton wrote:
>> Definitelly what my test shows - while rule-inserts - if you
>> try to insert 10000 rules - after a several hundreds - it
>> will be inserting like a 1 rule in 1 second and slowness
>> will progress :)
>
> If you need to change add many rules then iptables-restore is the tool
> to use. Batches the updates in a single transaction, instead of one
> transaction per rule...
>
> Regards
> Henrik
>
>

Re: iptables performance and alternatives

[Eric Leblond]

[-- Attachment #1: Type: text/plain, Size: 1073 bytes --]

Hello,

On Thursday, 2008 May 15 at 14:21:23 +0500, Anton wrote:
> Regarding the performance of the lookup of the iptables 
> rules for match inside the kernel, is there any plans to 
> improve the behaviour or no plans in this area yet?

Nf hipac is an alternative: http://www.hipac.org/

> For example on the transit gateway I have ~500 rules which 
> mark the packet, according to the client source IP - with 
> unique mark per client IP - so I have 500 unique marks 
> there, and so cannot use IPSET, and only IPTABLES - but 
> it's known that iptables insert/lookup is very slow on huge 
> rulesets (atleat with iptables 1.3.x) and slowness 
> progresses approximatelly exponentially on growth of rules 
> number.
> 
> Do I miss anything?

If you plan to use mark for QOS or routing why not simply use native
classifier of tc or "ip rule" ?

One other thing to look at may be :
http://www.netfilter.org/projects/patch-o-matic/pom-external.html#pom-external-IPMARK

BR,
-- 
Eric Leblond
INL: http://www.inl.fr/
NuFW: http://www.nufw.org/

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: iptables performance and alternatives

[Jan Engelhardt]

On Thursday 2008-05-15 11:34, Eric Leblond wrote:
>
>One other thing to look at may be :
>http://www.netfilter.org/projects/patch-o-matic/pom-external.html#pom-external-IPMARK

That variant is as old as POM and broken.

Re: iptables performance and alternatives

[Krzysztof Oledzki]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 447 bytes --]



On Thu, 15 May 2008, Jan Engelhardt wrote:

>
> On Thursday 2008-05-15 11:34, Eric Leblond wrote:
>>
>> One other thing to look at may be :
>> http://www.netfilter.org/projects/patch-o-matic/pom-external.html#pom-external-IPMARK
>
> That variant is as old as POM and broken.

The second statement is not true as it shoudl work with all 2.6.x kernels 
and both iptables-1.3 and iptables-1.4.

Best regards,

 			Krzysztof Olędzki

Re: iptables performance and alternatives

[Jan Engelhardt]

On Thursday 2008-05-15 13:18, Krzysztof Oledzki wrote:

>
>
> On Thu, 15 May 2008, Jan Engelhardt wrote:
>
>>
>> On Thursday 2008-05-15 11:34, Eric Leblond wrote:
>> >
>> > One other thing to look at may be :
>> > http://www.netfilter.org/projects/patch-o-matic/pom-external.html#pom-external-IPMARK
>>
>> That variant is as old as POM and broken.
>
> The second statement is not true as it shoudl work with all 2.6.x kernels and
> both iptables-1.3 and iptables-1.4.

It will definitely not work for 32-bit userland+64-bit kernel due to a size
mismatch. But since it is fixed in Xtables-addons, no further action is needed.

Re: iptables performance and alternatives

[Anton]

On Thursday 15 May 2008 14:34, Eric Leblond wrote:
> Hello,
>
> On Thursday, 2008 May 15 at 14:21:23 +0500, Anton wrote:
> > Regarding the performance of the lookup of the iptables
> > rules for match inside the kernel, is there any plans
> > to improve the behaviour or no plans in this area yet?
>
> Nf hipac is an alternative: http://www.hipac.org/

It looks like there is almost no development, but It would 
be good if i'm wrong 

>
> >
> > Do I miss anything?
>
> If you plan to use mark for QOS or routing why not simply
> use native classifier of tc or "ip rule" ?

Jan meant the exact case, I'm using this for shaper, so I 
would need to remake scripts to use IPMARK... hopefully it 
can also match networks... but this will give inflexibility 
in many cases, like ports

>
> One other thing to look at may be :
> http://www.netfilter.org/projects/patch-o-matic/pom-exter
>nal.html#pom-external-IPMARK
>
> BR,

Re: iptables performance and alternatives

[Jan Engelhardt]

On Thursday 2008-05-15 13:04, Anton wrote:
>>
>> If you plan to use mark for QOS or routing why not simply
>> use native classifier of tc or "ip rule" ?
>
>Jan meant the exact case, I'm using this for shaper, so I 
>would need to remake scripts to use IPMARK... hopefully it 
>can also match networks... but this will give inflexibility 
>in many cases, like ports

IPMARK is a target so it itself does not deal with matching;
but if you meant marking network, well than nothing easier than that:
(pick one)

(a) -j IPMARK --and-mask 0xffffff00  (for a /24)
(b) -j IPMARK; -j MARK --and-mark 0xffffff00;

Now since you are concerned about speed I guess the former is what you want.
Perhaps varying (a) to not leave the 8 null bits:

(c) -j IPMARK --shift 8

Re: iptables performance and alternatives

[Henrik Nordstrom]

On tor, 2008-05-15 at 11:34 +0200, Eric Leblond wrote:

> On Thursday, 2008 May 15 at 14:21:23 +0500, Anton wrote:
> > Regarding the performance of the lookup of the iptables 
> > rules for match inside the kernel, is there any plans to 
> > improve the behaviour or no plans in this area yet?
> 
> Nf hipac is an alternative: http://www.hipac.org/

Unfortunately a somewhat dead one as MARA Systems after all has selected
to develop this privately in future, so it's quite unlikely NF-HiPAC
will see any significant updates unless someone else picks up the
project.

Also it's insert performance is not the best in all cases (depends on
the structure of your ruleset and what kind of rule you insert). But
lookup speeds is always great.

Regards
Henrik

Re: iptables performance and alternatives

[KOVACS Krisztian]

Hi Henrik,

On Thu, May 15, 2008 at 02:28:54PM +0200, Henrik Nordstrom wrote:
> > On Thursday, 2008 May 15 at 14:21:23 +0500, Anton wrote:
> > > Regarding the performance of the lookup of the iptables 
> > > rules for match inside the kernel, is there any plans to 
> > > improve the behaviour or no plans in this area yet?
> > 
> > Nf hipac is an alternative: http://www.hipac.org/
> 
> Unfortunately a somewhat dead one as MARA Systems after all has selected
> to develop this privately in future, so it's quite unlikely NF-HiPAC
> will see any significant updates unless someone else picks up the
> project.

Really sad - although I can understand why they did this.

BTW, would there be any interest in at least getting the last published
version compile and work on recent kernels?

-- 
KOVACS Krisztian

Re: iptables performance and alternatives

[Henrik Nordstrom]

[-- Attachment #1: Type: text/plain, Size: 445 bytes --]

On tis, 2008-05-20 at 09:42 +0200, KOVACS Krisztian wrote:

> Really sad - although I can understand why they did this.
> 
> BTW, would there be any interest in at least getting the last published
> version compile and work on recent kernels?

I attempted doing so at the last workshop, but ran into some strange
issues. May try again.

The interface between hipac and netfilter/iptables is pretty simple
however.

Regards
Henrik

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 307 bytes --]

Re: iptables performance and alternatives

[Patrick McHardy]

Anton wrote:
> Regarding the performance of the lookup of the iptables 
> rules for match inside the kernel, is there any plans to 
> improve the behaviour or no plans in this area yet?
>
> For example on the transit gateway I have ~500 rules which 
> mark the packet, according to the client source IP - with 
> unique mark per client IP - so I have 500 unique marks 
> there, and so cannot use IPSET, and only IPTABLES - but 
> it's known that iptables insert/lookup is very slow on huge 
> rulesets (atleat with iptables 1.3.x) and slowness 
> progresses approximatelly exponentially on growth of rules 
> number.
>
> Do I miss anything?

Use conntrack to avoid doing the full lookup for every packet.

I'm working on improving things, its slowly progressing.
The successor of iptablse will use netlink, so it will be
able to insert and delete single rules without having to
transfer the entire ruleset again and again. Additionally
it natively supports sets, bitmaps and hashes, so your
500 source IP rules can be represented as a single rule
with, depending on how the IPs are distributed, either
O(1) or O(n) lookup time.

Its unfortunately still not in a publishable state, my
current plan is to have something for other people to
play with and work on by the next workshop. Maybe even
sooner.