[LARTC] Massive filtering

[LARTC] Massive filtering

[ericr]

I am trying to build a trafic control rule set for a huge NATed network, and I have it working for single known addresses but I need to scale it to 16M potential client addresses.  I'm using iptables for NAT.  Incoming traffic is simple because I can match destination address, outgoing traffic I use iptables IPMARK then tc match mark and it works perfectly if I build rules for each client individually. I am worried about performance as the client list increases.

I need to place client IPs into classes like routers, freeloaders, lite-access, premium-access, etc. I have no problem with rewriting rules on the fly.  It is easy to pop in a rule change any time a user authenticates or is disconnected for inactivity.

My first thought for scaling up was to use the hash tables, and I am feeling that the last line in lartc's document page "12.4. Hashing filters for very fast massive filtering" which says "Note that this example could be improved to the ideal case where each chain contains 1 filter!" is a little misleading since no divisor above 256 works.  On first reading, I 'm thinking, yeh, I'll just put a divisor of 16777216 and my problems are solved... nope.. wrong answer.  I haven't even gotten to the point where I issue 32 million filter rules to tc and see if it chokes.

I hate to have to ask, I am gratefull for all the work you have done just to get me here, I'm probably missing something important, but I'm trying to scale to 16 million potential clients and the only practical documentation I can find says thinking large is 200 clients.


thoughts, comments, ideas? solutions are best.
Thanks in advance,
Eric.


 




________________________________________________________________
Sent via the WebMail system at ipro.net


 
                   
_______________________________________________
LARTC mailing list
LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc

Re: [LARTC] Massive filtering

[Vladimir Vitkov]

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

Hi,

personally i've never tried so huge thing but ... a guy whom i know
has writen 2 papers on this.
1) optimizing iptables and tc rules:
http://www.linux-bg.org/cgi-bin/y/index.pl?page=article&id=advices&key=380752598
2) usage of ipset, iptables, ipmark:
http://www.linux-bg.org/cgi-bin/y/index.pl?page=article&id=advices&key=386924398

they are in bulgarian but hopefully the code will help. IF you have a
problem with understanding them, write me in private so i can make a
translation.

On 05/05/07, ericr <ericr@ipro.net> wrote:
> I am trying to build a trafic control rule set for a huge NATed network, and I have it working for single known addresses but I need to scale it to 16M potential client addresses.  I'm using iptables for NAT.  Incoming traffic is simple because I can match destination address, outgoing traffic I use iptables IPMARK then tc match mark and it works perfectly if I build rules for each client individually. I am worried about performance as the client list increases.
>
> I need to place client IPs into classes like routers, freeloaders, lite-access, premium-access, etc. I have no problem with rewriting rules on the fly.  It is easy to pop in a rule change any time a user authenticates or is disconnected for inactivity.
>
> My first thought for scaling up was to use the hash tables, and I am feeling that the last line in lartc's document page "12.4. Hashing filters for very fast massive filtering" which says "Note that this example could be improved to the ideal case where each chain contains 1 filter!" is a little misleading since no divisor above 256 works.  On first reading, I 'm thinking, yeh, I'll just put a divisor of 16777216 and my problems are solved... nope.. wrong answer.  I haven't even gotten to the point where I issue 32 million filter rules to tc and see if it chokes.
>
> I hate to have to ask, I am gratefull for all the work you have done just to get me here, I'm probably missing something important, but I'm trying to scale to 16 million potential clients and the only practical documentation I can find says thinking large is 200 clients.
>
>
> thoughts, comments, ideas? solutions are best.
> Thanks in advance,
> Eric.
>
>
>
>
>
>
>
> ________________________________________________________________
> Sent via the WebMail system at ipro.net
>
>
>
>
> _______________________________________________
> LARTC mailing list
> LARTC@mailman.ds9a.nl
> http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc
>


-- 
С уважение,
Владимир Витков

http://www.netsecad.com
http://www.supportbg.com

[-- Attachment #2: Type: text/plain, Size: 143 bytes --]

_______________________________________________
LARTC mailing list
LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc

Re: [LARTC] Massive filtering

[Stanislav Kruchinin]

ericr wrote:

> My first thought for scaling up was to use the hash tables, and I am
> feeling that the last line in lartc's document page "12.4. Hashing filters
> for very fast massive filtering" which says "Note that this example could
> be improved to the ideal case where each chain contains 1 filter!" is a
> little misleading since no divisor above 256 works.  On first reading, I 'm
> thinking, yeh, I'll just put a divisor of 16777216 and my problems are
> solved... nope.. wrong answer.  I haven't even gotten to the point where I
> issue 32 million filter rules to tc and see if it chokes.

The only solution in the case of thousands of rules is the u32 classifier with 
hashing filters. Unfortunately, divisor's upper limit is 256, and it's not 
appropriate for the practical tasks. From the other side, hashes with very 
large number of buckets (like 16777216, you said) can't be implemented, 
because they will require much more RAM than you can address.

I have similar task and some days ago started to work on patches for tc and 
u32 classifier that will allow to use large hashes (see my recent messages at 
linux-net@ mailing list archive). I'm a newbie in a Linux kernel and I can't 
complete this task fast. I think we should ask for help from experienced 
developers.
_______________________________________________
LARTC mailing list
LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc

Re: [LARTC] Massive filtering

[Corey Hickey]

ericr wrote:
> I am trying to build a trafic control rule set for a huge NATed
> network, and I have it working for single known addresses but I need
> to scale it to 16M potential client addresses.  I'm using iptables
> for NAT.  Incoming traffic is simple because I can match destination
> address, outgoing traffic I use iptables IPMARK then tc match mark
> and it works perfectly if I build rules for each client individually.
> I am worried about performance as the client list increases.
> 
> I need to place client IPs into classes like routers, freeloaders,
> lite-access, premium-access, etc. I have no problem with rewriting
> rules on the fly.  It is easy to pop in a rule change any time a user
> authenticates or is disconnected for inactivity.

I don't know what exactly it is you're doing, but here's a thought.

Do you control the allocation of addresses via DHCP? If so, it might be
faster/easier to simply set up IP ranges for your separate classes of user.

10.1.0.0/16        routers
10.2.0.0/16        freeloaders
10.3.0.0/16        ...etc...

Then you can use single matches in iptables/tc to identify packets
to/from each class.

-Corey
_______________________________________________
LARTC mailing list
LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc