[erlang-questions] IP search optimization

[Michael Truog]

Comment below:

On 11/20/2015 03:52 PM, Geoff Cant wrote:
> 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).
If you used https://github.com/okeuday/trie with an Erlang string (list of integers) it would be faster than the ets usage, though it can consume more memory if it needs to be replicated in many Erlang processes.  The basic way would be with a decimal number in each element, so [192,168,0,0] with the range expanded (as described above) to store everything.  You could also use the trie:find_match/2 function with the IP address stored as a boolean string with a wildcard character to represent the range, e.g.:

lists:sublist(lists:flatten(io_lib:format("~8.2.0B~8.2.0B~8.2.0B~8.2.0B", [192, 168, 0, 0])), 16) ++ "*". % is 192.168.0.0/16 in a format to use with trie:store/3 as the key argument

then just use find_match/2 to match the IP patterns (the most specific match would be found)

Best Regards,
Michael

>
>> 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
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions