[erlang-questions] IP search optimization

[Adam Cammack]

On Sun, Nov 22, 2015 at 07:53:45PM +0300, Alexandre Snarskii wrote:
> This algorithm is good for your test set of non-overlapping networks,
> but not in general. Let's assume we add entry {0, 0} (default route)
> to your set and try to lookup some non-existant route. In case we look
> for 244.42.192.0/20 - ets:prev returns 244.42.64.0/20 (last entry in 
> your set, which does not match), ets:prev for 244.42.64.0/20 returns 
> 244.42.48.0/20 (does not match again), then .32.0/20 and only after 
> ONE MILLION lookups you get matching 0.0.0.0/0 which is the right answer. 
> 
> With decrementing masklen you will get the same result in 32 lookups.

My apologies, I forgot to mention successive calls to ets:prev/2 should
done with the common prefix of the target IP and the non-matching block:

{Common_Prefix, Common_Len + 1}

common_prefix32(A, A) ->
  {A, 32};
common_prefix32(A, B) ->
  % Select the bits that are set in one, but not both
  Delta = (A bor B) bxor (A band B),
  % Most Significant Bit (first different) + 1
  Last_Common = trunc(math:log2(Delta)) + 1,
  Prefix = (A bsr Last_Common) bsl Last_Common,
  {Prefix, 32 - Last_Common}.

You could modify the algorithm to return all matching IP blocks by
shifting out an additional bit of the match and continuing to search.

In your case, the default rule would be found after 10 calls to
ets:prev/2, being slightly slower in the worst case due to the extra
math (same number of ETS operations).

With nested blocks, the simplicity of naively searching for the mask is
attractive. It would be interesting to see how the two methods scale
with IPv6 addresses. I'll try to work up a benchmark later.

--
Adam Cammack