[erlang-questions] IP search optimization

[Sid Muller]

> Sent: Thursday, November 19, 2015 at 9:05 AM
> From: "Alexandre Snarskii" <snar@REDACTED>
> To: "Sid Muller" <sid5@REDACTED>
> Cc: erlang-questions <erlang-questions@REDACTED>
> Subject: Re: [erlang-questions] IP search optimization
> > And then I want to check if an IP (31.24.171.44) belongs to any 
> > network address in the ets table (the table can get pretty large).
> 
> Looks more like a task for radix trees...

Hmm, good point although with ets if my owner process gets killed I inherit the ets and no data is lost. Not sure how that cold be done with a radix tree.


> The best you can achieve with ets is:
> on insert: make sure that inserted networks are normalized (do not have
> any bits set after prefix length).
> on lookup:
> 1. start with masklen of 32
> 2. normalize address to current masklen
> 3. lookup for address/masklen record, return if found
> 4. if current masklen is zero - return 'not_found'
> 5. decrease masklen and repeat from step two. 

There are a few faster methods:
1. Have a pre-scanned list of /CIDR [21, 20...], there are usually about 10. But this still traverses the table 10 times in worst case.

2. Traverse the table with ets:lookup(ets:next(), this has the advantage over #1 as it's much faster in most cases.

3. ets:select(MatchSpec), this is probably the fastest solution because it should traverse the table only once. But right now I'm having a bit of a problem with my select statement... see other email [bitstring select]