<div dir="ltr"><div>I think routers generally use radix trees, and it's certainly important for them to be able to do lookups quickly. Some also have specialised hardware to assist, but I guess you can't have everything!<br><br>Regarding your desire to use an ETS table for the inheritance, I obviously don't know your exact use case, but I personally feel it's more important to use the correct/optimal storage solution. My reasoning is:<br><br> 1. Obviously it will perform best.<br> 2. If then you crash, well, fail early is the Erlang way, and hopefully this would lead to a more rapid development of a relatively stable solution.<br> 3. If there is a flaw in your persistent data that caused the crash, you won't persist the flaw and crash again.<br> 4. If it's worth it, you could back up your prefixes in a separate process (or ETS table) anyway.<br><br>If you backed up your prefixes (point 4) you can reconstruct your radix tree from the backup in the event of a failure. Not perhaps as quick as not having to... but probably not really very expensive unless you really crash very often. Typically routers would do this anyway because they learn routes from various sources and maintain databases for each of those sources and/or each protocol, and then the actual routing table used to make routing decisions is essentially separate, and can be optimised separately. Your use case might be quite different but you could still adopt the idea artificially.<br><br>Another thing to consider is that you could implement a 'route cache' on top of whatever solution you choose (every time you have to search your radix/ETS stuff the result in a cache, the cache being a map of IP to prefix). This will make most of your lookup speeds very quick and largely constant because they'll be a hash lookup, ASSUMING your use case is such that you get a good cache hit rate. There is additional work to be done of course, you have to garbage collect your cache, you have to invalidate all or some of it when you update your prefix list (unless the lag is acceptable in which case just wait for garbage collection), and you must give very careful consideration to the possibility of dos attacks causing you to build huge caches. This obviously depends on the details of your use case, as does the likelihood of a good cache hit rate.<br><br></div>M.<br></div><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Nov 20, 2015 at 5:01 PM, Sid Muller <span dir="ltr"><<a href="mailto:sid5@gmx.us" target="_blank">sid5@gmx.us</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">> Sent: Thursday, November 19, 2015 at 9:05 AM<br>
> From: "Alexandre Snarskii" <<a href="mailto:snar@snar.spb.ru">snar@snar.spb.ru</a>><br>
> To: "Sid Muller" <<a href="mailto:sid5@gmx.us">sid5@gmx.us</a>><br>
> Cc: erlang-questions <<a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a>><br>
> Subject: Re: [erlang-questions] IP search optimization<br>
<span class="">> > And then I want to check if an IP (31.24.171.44) belongs to any<br>
> > network address in the ets table (the table can get pretty large).<br>
><br>
> Looks more like a task for radix trees...<br>
<br>
</span>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.<br>
<span class=""><br>
<br>
> The best you can achieve with ets is:<br>
> on insert: make sure that inserted networks are normalized (do not have<br>
> any bits set after prefix length).<br>
> on lookup:<br>
> 1. start with masklen of 32<br>
> 2. normalize address to current masklen<br>
> 3. lookup for address/masklen record, return if found<br>
> 4. if current masklen is zero - return 'not_found'<br>
> 5. decrease masklen and repeat from step two.<br>
<br>
</span>There are a few faster methods:<br>
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.<br>
<br>
2. Traverse the table with ets:lookup(ets:next(), this has the advantage over #1 as it's much faster in most cases.<br>
<br>
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]<br>
<div class="HOEnZb"><div class="h5">_______________________________________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><br>
<a href="http://erlang.org/mailman/listinfo/erlang-questions" rel="noreferrer" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
</div></div></blockquote></div><br></div>