[erlang-questions] IP search optimization

[Alexandre Snarskii]

On Sat, Nov 21, 2015 at 09:16:36AM +0100, Jacob wrote:
> 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}

   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}),
   ets:insert(E, {{{192,168,1,0},{192,168,1,255},eth3},1}),
 {Low, Hi, If} = ets:prev(E, {{192,168,10,11}, {256,256,256,256}, '_'}).
{{192,168,1,0},{192,168,1,255},eth3}

As you see, lookup for 192.168.10.11 returns incorrect network 192.168.1.0/24, 
not 192.168.0.0/16. Another example with the same setup:

ets:prev(E, {{239,0,0,1}, {256,256,256,256}, '_'}).                    
{{192,168,1,0},{192,168,1,255},eth3}

lookup for 239.0.0.1 returns 192.168.1.0/24, not 0.0.0.0/0 as it should.