Re: Handling a large number of IPs efficiently

From: Leon. (noemail_at_noemail.noemail.com)
Date: 12/28/03 

Date: Sun, 28 Dec 2003 18:19:33 +1100

"Bill Davidsen" <davidsen@tmr.com> wrote in message
news:RdadneK5x8hG23OiRVn-gQ@thebiz.net...
> jack wrote:
> > Bill Davidsen wrote:
> >
> >> I have a site which is going to want to allow access from certain site
> >> only. A large number of sites, and not neatly grouped in CIDR blocks.
> >> A few thousand IP addresses, in fact. Unfortunately iptables doesn't
> >> seem to do this well, using a linear progression rather than a hash or
> >> similar.
> >
> >
> > Not necessarily. In Your case, I'd simply add more chains like so:
> >
> > Create a chain for all "leftmost" network addresses that are in
> > question, e. g. one chain "D9" for all clients where the IP address is
> > in 217.0.0.0/8.
> >
> > In that chain "D9", create new chains the same way, e. g. a chain "D954"
> > for all clients from 217.84.0.0/16 and so on.
> >
> > I don't know whether this is practical to You or whether it is practical
> > at all, but this was my first idea when I read Your term "linear",
> > above.
>
> I looked at that, but I don't think it's going to be a solution. The IPs
> are moderately well split, so I have about 20-40 values for the first
> octet on a given day, same for 2nd octet, then up to 80 3rd octet values
> for some 1st+2nd combinations. A few thousand is typical, but it can hit
> 10k at times, and I need to process 30-100 packets/sec for validation.
> All-in-all I don't think the tree scales all that well.
>
> Of course I could do it a bit at a time, giving max 64 rules per packet,
> but I think that doesn't make it, either. Not to mention that adding and
> deleting rules can happen at a high rate.
>
> What I need is a fairly good hash or other database attack on the
> problem, I'm afraid.
>
> Thanks for the idea, but these IPs are being used for a DDoS and they
> are identified and blocked in large numbers at times.

Yes hashing just on the last 8 bits this would reduce the table rules to
search through from 10k does down to
10k/254 + 8 = 40 + 8 = 48 , at the worst. thats quite a saving.

If you make the hash structure bigger, then you could do it on the last 12
bits, reducing the worst case down to about 10k/1024 + 12 =22 As thats
about 50 % in the last table and 50% in the hash tables, theres no point in
going any further ?

Define a table called 'hash' (or use the main table) , and add the rules
like this
if matches 255.255.255.0/255.255.255.128 goto table a
if matches 255.255.255.128/255.255.255.128 goto table b

Table a
if matches 255.255.255.0/255.255.255.192 goto table c
if matches 2555.255.255.64/255.255.255.192 goto table d

table b
if matches 255.255.255.128/255.255.255.192 goto table g
if matches 255.255.255.192/255.255.255.192 goto table h

Table C
if matches 255.255.255.0/255.255.255.224 goto table e
if matches 255.255.255.32/255.255.255.224 goto table f

etc

Relevant Pages