[erlang-questions] IP search optimization

[Geoff Cant]

Hi Sid, are you writing an open source library for this functionality? I need exactly the same thing and was going to sit down to write it.

With CIDR blocks, you can always calculate the lower and upper address in a range.

> -type ip4() :: <<_:32/bits>>.
> -type ip4_mask() :: 0..32.
> -type ip4_cidr() :: {ip4(), ip4_mask()}.
> -spec to_range(ip4_cidr()) -> {Low::ip4(), High::ip4()}.
> to_range({<<CIDR:4/binary>>, Mask})
>   when 0 =< Mask,
>        Mask =< 32 ->
>     HostBits = 32 - Mask,
>     {<<CIDR:Mask/bits, 0:HostBits/integer>>,
>      <<CIDR:Mask/bits, 16#FFFFFFFF:HostBits/integer>>}.

If you pre-convert your CIDR list into a range list, you can then select all the matching cidrs by comparing Low =< IP, IP =< High, and returning the CIDR with the largest mask (if you do longest-prefix wins), or the first in order if you’re doing an ordered CIDR match.

Pre-converting CIDR -> Range will let you use ets:select - and might be reasonably efficient in an ordered_set table if you’ve got large numbers of CIDRs. I think if your ets key is {Low, High}, and it’s an ordered_set table, the first result from a matching select will be the one with the longest Mask anyway (as {<<192,168,0,0>>, <<192,168,0,255>>} <  {<<192,168,0,0>>, <<192,168,255,255>>} — i.e. 192.168.0.0/24 < 192.168.0.0/16 when converted to a range tuple).

> IP = something,
> Matching = ets:select(cidr_table, ets:fun2ms(fun (#record{range={Low, High}}) when Low =< IP, IP =< High) -> object() end)).


Anyway - I’m either going to write something like this in the next couple of weeks, or use yours if it’s public and suitable :)

Cheers,
-Geoff


> On 19 Nov, 2015, at 08:17, Sid Muller <sid5@REDACTED> 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).
> 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