[erlang-questions] IP search optimization

[Jacob]

Hi Alexandre,

>    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.
>

That is why I wrote

On 22.11.2015 18:11, Alexandre Snarskii wrote:
> On Sat, Nov 21, 2015 at 09:16:36AM +0100, Jacob wrote:
>>
>> 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>>}).
>>

That is crucial here:

>> and a check whether IP <= High holds.

Since {239,0,0,1} > {192,168,1,255} we are not done yet.

>> 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.

And further more:

>> If you have
>> nested routes, you will have to call ets:prev({Low,High}) again until IP
>> <= High or $end_of_table is returned.

Which tells how to get the correct result:

3> ets:prev(E, {{192,168,1,0},{192,168,1,255},eth3}).
{{192,168,0,0},{192,168,255,255},eth1}
4> ets:prev(E, {{192,168,0,0},{192,168,255,255},eth1}).
{{172,16,0,0},{172,31,255,255},eth2}
5> ets:prev(E, {{172,16,0,0},{172,31,255,255},eth2}).
{{0,0,0,0},{255,255,255,255},eth0}

which is exactly what you want.

Of course, this need four calls to ets:prev/2, which (if time critical)
could be avoided by using a flattened table (without holes) instead. In
that case,
only a single ets:prev/2 call (and nothing else from ets) would be
necessary for all lookups.

BTW, the example implementation I have given also returns (let's name
the module 'iproute').

1> R=iproute:new().
28688
2> iproute:addroute(R,{0,0,0,0},{255,255,255,255},eth0).
true
3> iproute:addroute(R,{192,168,0,0},{192,168,255,255},eth1).
true
4> iproute:addroute(R,{172,16,0,0},{172,31,255,255},eth2).
true
5> iproute:addroute(R,{192,168,1,0},{192,168,1,255},eth3).
true
6> iproute:getroute(R,{239,0,0,1}).
eth0

Jacob


>>
>> 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.
> 
>