[erlang-questions] IP search optimization

[Sergej Jurečko]

Excuse me if this is a stupid comment. But why use ETS and cidr format at all if your goal is to find an IP that fits into one of your ranges.

You can expand every range into {IpFrom,IpTo}. Sort them and create a binary tree by recursively half-ing it.
Every element would be: {IPFrom, IPTo, LeftSubtree,RightSubtree}. 
Then it is a very simple matter of looking up your IP by traversing the tree.


Sergej

> On 22 Nov 2015, at 19:02, Jacob <jacob01@REDACTED> wrote:
> 
> 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.
>> 
>> 
> 
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions