long ruleset perfomance issue

long ruleset perfomance issue

[anton]

Hello,
I need to mark packets going through a linux router with iptables for some 4500 ip addresses(to use with tc bandwidth shaping filters).
This list needs to be updated every 10 minutes.
So i made a shell script file looking like:

/usr/local/sbin/iptables -F 
/usr/local/sbin/iptables -A FORWARD -t mangle -d 1.1.1.1 -j MARK --set-mark 1
/usr/local/sbin/iptables -A FORWARD -t mangle -d 1.1.1.3 -j MARK --set-mark 2
/usr/local/sbin/iptables -A FORWARD -t mangle -d 1.1.1.2 -j MARK --set-mark 1
and so on for 4500 times.

When i run this script on Xeon 2.4ghz cpu it takes 2-3 minutes real time with 100% cpu load to process.
During this time server becomes unusable. 
Is there any way to make it run faster, like optimizing ruleset or trying a different approach?
I have tried to search on this issue but was not successful.

Any input is greatly appreciatred.

Thank you,
Anton

Re: long ruleset perfomance issue

[John A. Sullivan III]

On Mon, 2005-04-04 at 12:44 +0100, anton@web-sat.com wrote:
> Hello,
> I need to mark packets going through a linux router with iptables for some 4500 ip addresses(to use with tc bandwidth shaping filters).
> This list needs to be updated every 10 minutes.
> So i made a shell script file looking like:
> 
> /usr/local/sbin/iptables -F 
> /usr/local/sbin/iptables -A FORWARD -t mangle -d 1.1.1.1 -j MARK --set-mark 1
> /usr/local/sbin/iptables -A FORWARD -t mangle -d 1.1.1.3 -j MARK --set-mark 2
> /usr/local/sbin/iptables -A FORWARD -t mangle -d 1.1.1.2 -j MARK --set-mark 1
> and so on for 4500 times.
> 
> When i run this script on Xeon 2.4ghz cpu it takes 2-3 minutes real time with 100% cpu load to process.
> During this time server becomes unusable. 
> Is there any way to make it run faster, like optimizing ruleset or trying a different approach?
> I have tried to search on this issue but was not successful.
> 
> Any input is greatly appreciatred.
> 
> Thank you,
> Anton
Absolutely.  Use iptables-restore (be careful with the command line
parameters, you may want iptables-restore -n).  You feed iptables-
restore a file with the rules in a slightly different syntax than
iptables.  The difference in load time is dramatic.

The ISCS network security management project that I maintain is designed
for large, enterprise or carrier class, multi-layered security and can
thus generate enormous rule sets (http://iscs.sourceforge.net).  We thus
always use iptables-restore in our work.  We also have moved away from
the creation of monolithic rule sets (from this source addr on this sort
port going to that dest addr on that dest port take this action) to
modular rules which evaluate source separately from access type
separately from destination.  This produces a much smaller rule set
which is traversed much more efficiently for large environments.  A
little off your question but also an important issue for minimizing rule
sets, load times and traversal speed.

For your immediate question, iptables-restore is your answer - John
-- 
John A. Sullivan III
Open Source Development Corporation
+1 207-985-7880
jsullivan@opensourcedevel.com

If you would like to participate in the development of an open source
enterprise class network security management system, please visit
http://iscs.sourceforge.net

Re: long ruleset perfomance issue

[Grant Taylor]

Based on the fact that you are wanting to mark traffic for 4500 IPs means to me that you are dealing with approximately 18 class C networks.  Thus I'd be tempted to do some of the following:

iptables -t mangle -N FORWARD_1_1_1_0
iptables -t mangle -N FORWARD_1_1_2_0
iptables -t mangle -N FORWARD_1_1_3_0
iptables -t mangle -A FORWARD -d 1.1.1.0/24 -j FORWARD_1_1_1_0
iptables -t mangle -A FORWARD -d 1.1.2.0/24 -j FORWARD_1_1_2_0
iptables -t mangle -A FORWARD -d 1.1.3.0/24 -j FORWARD_1_1_3_0
iptables -t mangle -A FORWARD_1_1_1_0 -d 1.1.1.1 -j MARK --set-mark 1
iptables -t mangle -A FORWARD_1_1_1_0 -d 1.1.1.2 -j MARK --set-mark 2
iptables -t mangle -A FORWARD_1_1_1_0 -d 1.1.1.3 -j MARK --set-mark 1
...
iptables -t mangle -A FORWARD_1_1_2_0 -d 1.1.2.1 -j MARK --set-mark 1
iptables -t mangle -A FORWARD_1_1_2_0 -d 1.1.2.2 -j MARK --set-mark 2
iptables -t mangle -A FORWARD_1_1_2_0 -d 1.1.2.3 -j MARK --set-mark 1
...
iptables -t mangle -A FORWARD_1_1_3_0 -d 1.1.3.1 -j MARK --set-mark 1
iptables -t mangle -A FORWARD_1_1_3_0 -d 1.1.3.2 -j MARK --set-mark 2
iptables -t mangle -A FORWARD_1_1_3_0 -d 1.1.3.3 -j MARK --set-mark 1

This will make is such that your packets don't have to traverse as many rules in the FORWARD chain directly.  In fact there would only be 18 conditional JUMP to sub chain rules in the main FORWARD chain.  In this situation there would be 255 entries in the sub chains.  You end up with a pseudo tree structure like this

FORWARD
   |
   <sbunet 1.1.1.0/24 -j FORWARD_1_1_1_0
      |
      <ip 1.1.1.1 -j MARK>
      <ip 1.1.1.2 -j MARK>
      <ip 1.1.1.3 -j MARK>
   <sbunet 1.1.2.0/24 -j FORWARD_1_1_2_0
      |
      <ip 1.1.2.1 -j MARK>
      <ip 1.1.2.2 -j MARK>
      <ip 1.1.2.3 -j MARK>
   <sbunet 1.1.3.0/24 -j FORWARD_1_1_3_0
      |
      <ip 1.1.3.1 -j MARK>
      <ip 1.1.3.2 -j MARK>
      <ip 1.1.3.3 -j MARK>

Yielding 18 conditionals in your first level and 255 conditionals in your 2nd level with 2 decisions having to be made.  Something you could do to possibly speed this up would be to play with the tree structure.  I.e. you could build something where you had 36 conditionals in your first level based on 128 subnets and then only 128 conditionals in your 2nd level, though this is more comparisons that would have to be done.  I have a feeling that the math will work out the best if you end up with something along the lines of 18 conditionals on the first level and 2, 4, 8, or 16 conditionals on the 2nd level with sub levels below that.  Assuming that we are only working with one class C for the moment you could build a structure like this with 16 items to choose from and 2 decisions that would have to be made.

iptables -t mangle -A FORWARD -d 1.1.1.0/28 -j FORWARD_1_1_1_0
iptables -t mangle -A FORWARD -d 1.1.1.16/28 -j FORWARD_1_1_1_16
iptables -t mangle -A FORWARD -d 1.1.1.32/28 -j FORWARD_1_1_1_32
iptables -t mangle -A FORWARD -d 1.1.1.48/28 -j FORWARD_1_1_1_48
iptables -t mangle -A FORWARD -d 1.1.1.64/28 -j FORWARD_1_1_1_64
iptables -t mangle -A FORWARD -d 1.1.1.80/28 -j FORWARD_1_1_1_80
iptables -t mangle -A FORWARD -d 1.1.1.96/28 -j FORWARD_1_1_1_96
iptables -t mangle -A FORWARD -d 1.1.1.112/28 -j FORWARD_1_1_1_112
iptables -t mangle -A FORWARD -d 1.1.1.128/28 -j FORWARD_1_1_1_128
iptables -t mangle -A FORWARD -d 1.1.1.144/28 -j FORWARD_1_1_1_144
iptables -t mangle -A FORWARD -d 1.1.1.160/28 -j FORWARD_1_1_1_160
iptables -t mangle -A FORWARD -d 1.1.1.176/28 -j FORWARD_1_1_1_176
iptables -t mangle -A FORWARD -d 1.1.1.192/28 -j FORWARD_1_1_1_192
iptables -t mangle -A FORWARD -d 1.1.1.208/28 -j FORWARD_1_1_1_208
iptables -t mangle -A FORWARD -d 1.1.1.224/28 -j FORWARD_1_1_1_224
iptables -t mangle -A FORWARD -d 1.1.1.240/28 -j FORWARD_1_1_1_240
#iptables -t mangle -A FORWARD_1_1_1_0 -d 1.1.1.0 -j MARK --set-mark 2 #We shouldn't really need this line.
iptables -t mangle -A FORWARD_1_1_1_0 -d 1.1.1.1 -j MARK --set-mark 1
iptables -t mangle -A FORWARD_1_1_1_0 -d 1.1.1.2 -j MARK --set-mark 2
iptables -t mangle -A FORWARD_1_1_1_0 -d 1.1.1.3 -j MARK --set-mark 1
iptables -t mangle -A FORWARD_1_1_1_0 -d 1.1.1.4 -j MARK --set-mark 2
iptables -t mangle -A FORWARD_1_1_1_0 -d 1.1.1.5 -j MARK --set-mark 1
iptables -t mangle -A FORWARD_1_1_1_0 -d 1.1.1.6 -j MARK --set-mark 2
iptables -t mangle -A FORWARD_1_1_1_0 -d 1.1.1.7 -j MARK --set-mark 1
iptables -t mangle -A FORWARD_1_1_1_0 -d 1.1.1.8 -j MARK --set-mark 2
iptables -t mangle -A FORWARD_1_1_1_0 -d 1.1.1.9 -j MARK --set-mark 1
iptables -t mangle -A FORWARD_1_1_1_0 -d 1.1.1.10 -j MARK --set-mark 2
iptables -t mangle -A FORWARD_1_1_1_0 -d 1.1.1.11 -j MARK --set-mark 1
iptables -t mangle -A FORWARD_1_1_1_0 -d 1.1.1.12 -j MARK --set-mark 2
iptables -t mangle -A FORWARD_1_1_1_0 -d 1.1.1.13 -j MARK --set-mark 1
iptables -t mangle -A FORWARD_1_1_1_0 -d 1.1.1.14 -j MARK --set-mark 2
iptables -t mangle -A FORWARD_1_1_1_0 -d 1.1.1.15 -j MARK --set-mark 1
iptables -t mangle -A FORWARD_1_1_1_16 -d 1.1.1.16 -j MARK --set-mark 2
iptables -t mangle -A FORWARD_1_1_1_16 -d 1.1.1.17 -j MARK --set-mark 1
iptables -t mangle -A FORWARD_1_1_1_16 -d 1.1.1.18 -j MARK --set-mark 2
iptables -t mangle -A FORWARD_1_1_1_16 -d 1.1.1.19 -j MARK --set-mark 1
iptables -t mangle -A FORWARD_1_1_1_16 -d 1.1.1.20 -j MARK --set-mark 2
iptables -t mangle -A FORWARD_1_1_1_16 -d 1.1.1.21 -j MARK --set-mark 1
iptables -t mangle -A FORWARD_1_1_1_16 -d 1.1.1.22 -j MARK --set-mark 2
iptables -t mangle -A FORWARD_1_1_1_16 -d 1.1.1.23 -j MARK --set-mark 1
iptables -t mangle -A FORWARD_1_1_1_16 -d 1.1.1.24 -j MARK --set-mark 2
iptables -t mangle -A FORWARD_1_1_1_16 -d 1.1.1.25 -j MARK --set-mark 1
iptables -t mangle -A FORWARD_1_1_1_16 -d 1.1.1.26 -j MARK --set-mark 2
iptables -t mangle -A FORWARD_1_1_1_16 -d 1.1.1.27 -j MARK --set-mark 1
iptables -t mangle -A FORWARD_1_1_1_16 -d 1.1.1.28 -j MARK --set-mark 2
iptables -t mangle -A FORWARD_1_1_1_16 -d 1.1.1.29 -j MARK --set-mark 1
iptables -t mangle -A FORWARD_1_1_1_16 -d 1.1.1.30 -j MARK --set-mark 2
iptables -t mangle -A FORWARD_1_1_1_16 -d 1.1.1.31 -j MARK --set-mark 1

And so on and so forth.  The problem that you start to run in to is really how do you create the tree properly so that it can be traversed quickly and efficiently.  Take the worst case example, where the IP is the last possible IP to choose from where it would have to traverse 16 conditionals to decide to jump to the next chain and then 16 more conditionals to decide what to mark the packet as.  That is a total of 32 conditionals (plus the one to get in to the class C structure) and 2 actions.  Would it be more efficient to brake the tree down to levels of 4 conditionals so that there would be a total of 16 conditionals (worst case) and 4 jumps?  If you are really paranoid you could brake it down to 2 conditionals and 8 jumps.  It's all in playing with the numbers and where the performance break is at and if you want to go through the trouble or not.  Of course a quick dirty Perl script 
 would make this a LOT easier.  If you want a related topic to see what is going on here r
ead up on B-Trees and the likes for databases.  B/c after all iptables is a small database in the kernel's memory of what to do with various packets that you are trying to efficiently and quickly search and traverse.

As an aside that has already ben mentioned you could use the iptables-save and iptables-restore commands as these make bulk changes to the tables / chains at one time (one invocation of the iptables binary) vs calling iptables for each and every line.

I hope this helps you some and does not confuse you.  If you need any more help or would like help writing a Perl script to do the layout for you I'd be glad to help with that (with and honorable mention ;) too.



Grant. . . .




anton@web-sat.com wrote:

> Hello,
> I need to mark packets going through a linux router with iptables for some 4500 ip addresses(to use with tc bandwidth shaping filters).
> This list needs to be updated every 10 minutes.
> So i made a shell script file looking like:
> 
> /usr/local/sbin/iptables -F 
> /usr/local/sbin/iptables -A FORWARD -t mangle -d 1.1.1.1 -j MARK --set-mark 1
> /usr/local/sbin/iptables -A FORWARD -t mangle -d 1.1.1.3 -j MARK --set-mark 2
> /usr/local/sbin/iptables -A FORWARD -t mangle -d 1.1.1.2 -j MARK --set-mark 1
> and so on for 4500 times.
> 
> When i run this script on Xeon 2.4ghz cpu it takes 2-3 minutes real time with 100% cpu load to process.
> During this time server becomes unusable. 
> Is there any way to make it run faster, like optimizing ruleset or trying a different approach?
> I have tried to search on this issue but was not successful.
> 
> Any input is greatly appreciatred.
> 
> Thank you,
> Anton
> 
> 

Re: long ruleset perfomance issue

[Jozsef Kadlecsik]

On Mon, 4 Apr 2005, Grant Taylor wrote:

> This will make is such that your packets don't have to traverse as many
> rules in the FORWARD chain directly.  In fact there would only be 18
> conditional JUMP to sub chain rules in the main FORWARD chain.  In this
> situation there would be 255 entries in the sub chains.  You end up with
> a pseudo tree structure like this
>
> FORWARD
>    |
>    <sbunet 1.1.1.0/24 -j FORWARD_1_1_1_0
>       |
>       <ip 1.1.1.1 -j MARK>
>       <ip 1.1.1.2 -j MARK>
>       <ip 1.1.1.3 -j MARK>
>    <sbunet 1.1.2.0/24 -j FORWARD_1_1_2_0
>       |
>       <ip 1.1.2.1 -j MARK>
>       <ip 1.1.2.2 -j MARK>
>       <ip 1.1.2.3 -j MARK>
>    <sbunet 1.1.3.0/24 -j FORWARD_1_1_3_0
>       |
>       <ip 1.1.3.1 -j MARK>
>       <ip 1.1.3.2 -j MARK>
>       <ip 1.1.3.3 -j MARK>

If the possible mark values are small, then ipset is a much more efficient
solution for the problem. You can even build up similar tree structure
with bindings in ipset. Actually, one can collapse the corresponding
iptables rules to the number of distinct mark values.

Best regards,
Jozsef
-
E-mail  : kadlec@blackhole.kfki.hu, kadlec@sunserv.kfki.hu
PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics
          H-1525 Budapest 114, POB. 49, Hungary