[erlang-questions] IP search optimization

[Jacob]

Hi,

On 21.11.2015 00:52, 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.
> 
> [...]
>
> 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).

In that case you can just use ets:prev to get the network, as in

  {Low, High} = ets:prev(E, {IP, <<255,255,255,255,1>>}).

and a check whether IP <= High holds. The <<255,255,255,255,1>> is an
arbitrary value that just needs to be larger than any valid IP address,
to make lookups like for IP = <<192,168,0,0>> reliable. If you have
nested routes, you will have to call ets:prev({Low,High}) again until IP
<= High or $end_of_table is returned.

This can also be done without converting the IP adresses to binaries.
The route specific data can also be put into the key to avoid an
additional lookup as in

  E = ets:new(ip, [ordered_set]).
  ets:insert(E, {{{0,0,0,0},{255,255,255,255},eth0},1}).
  ets:insert(E, {{{192,168,0,0},{192,168,255,255},eth1},1}).
  ets:insert(E, {{{172,16,0,0},{172,31,255,255},eth2},1}).

  {Low, High, If} = ets:prev(E, {{172,25,4,3},{256,256,256,256}, '_'}).
  -> {{172,16,0,0},{172,31,255,255},eth2}

So a possible implementation is

-define(LARGER_THAN_ANY_VALID_IP, <<-1:256>>).

new() ->
  ets:new(?MODULE, [ordered_set]).

addroute(E, Low, High, If) ->
  ets:insert(E, {{Low, High, If},1}).

getroute(E, Ip) ->
  getroute(E, Ip, ets:prev(E, {Ip, ?LARGER_THAN_ANY_VALID_IP, '_'})).

getroute(_E, Ip, {_Low, High, If}) when Ip =< High ->
  If;
getroute(E, Ip, Key = {_Low, _High, _If}) ->
  getroute(E, Ip, ets:prev(E, Key)).


which supports nested routes and would work with any kind of address
encoding as long as the length is the same for all entries. Note that
this will crash if there is no matching route, which can easily be
avoided by adding a default route like in the example above.

HTH,

Jacob