[erlang-questions] IP search optimization

[Alexandre Snarskii]

On Thu, Nov 19, 2015 at 05:17:21PM +0100, Sid Muller wrote:
> Hi,
> 
> I was wondering if someone knowledgeable in IP/CIDR and bitstrings 
> could give me some advice on how to proceed?
> 
> I'm storing network address in an ets table, for example:
> 77.242.16.0/20
> 31.24.168.0/21
> 
> And then I want to check if an IP (31.24.171.44) belongs to any 
> network address in the ets table (the table can get pretty large).

Looks more like a task for radix trees...

The best you can achieve with ets is:
on insert: make sure that inserted networks are normalized (do not have
any bits set after prefix length).
on lookup:
1. start with masklen of 32
2. normalize address to current masklen
3. lookup for address/masklen record, return if found
4. if current masklen is zero - return 'not_found'
5. decrease masklen and repeat from step two. 


> The crux of the matter is that I am not sure which of the following 
> routes to pursue because I only get the IP but CIDR is stored in 
> ets with each network:
> 
> 1. Should I store the network/CIDR in ets as tuples:
> {{77, 42, 6, 0}, 20}
> {{31, 24, 168, 0}, 21}
> and search for the IP as a tuple ({31, 24, 171, 44}) byte by byte?
> 
> 2. Should I store the Network as a bitstring:
> <<77,242,1:4>>
> <<31,24,21:5>>
> And then search for the IP as a bitstring match?
> 
> 3. Should I store the network/CIDR as binary:
> <<"77.242.16.0/20">>
> <<"31.24.168.0/21">>
> 
> I think the best solution would be the #2 but this one, just like 
> the others I don't know the CIDR ahead of time to be able to trim 
> the CIDR off the IP and then do a simple key based match from ets.
> 
> Any thoughts?
> 
> Thank you
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions