<div dir="ltr"><div dir="ltr">There are many different tries -- see here for some examples.<div><a href="https://www.drdobbs.com/cpp/fast-ip-routing-with-lc-tries/184410638">https://www.drdobbs.com/cpp/fast-ip-routing-with-lc-tries/184410638</a><br></div><div><br></div><div>And an enhancement to LC-tries</div><div><a href="http://www.diva-portal.org/smash/record.jsf?pid=diva2%3A469814&dswid=-2401">http://www.diva-portal.org/smash/record.jsf?pid=diva2%3A469814&dswid=-2401</a><br></div><div><br></div><div>Then there are radix-n (n-ary trie) lookups, e.g. radix-4 would look up 4-bits at a time and branch 16 ways.</div><div><br></div><div>Here's a good tutorial, and I don't think even this is exhaustive.</div><div><a href="http://klamath.stanford.edu/~pankaj/talks/hoti_tutorial.ppt">http://klamath.stanford.edu/~pankaj/talks/hoti_tutorial.ppt</a><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Jun 8, 2020 at 4:19 PM Josh Hoppes <<a href="mailto:josh.hoppes@gmail.com">josh.hoppes@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Juniper Networks has also tried using Bloom filters.<br>
<br>
<a href="https://patents.google.com/patent/US20170187624" rel="noreferrer" target="_blank">https://patents.google.com/patent/US20170187624</a><br>
<br>
I think the QFX10002 was the first product they made which used this approach.<br>
<br>
<a href="https://forums.juniper.net/t5/Archive/Juniper-QFX10002-Technical-Overview/ba-p/270358" rel="noreferrer" target="_blank">https://forums.juniper.net/t5/Archive/Juniper-QFX10002-Technical-Overview/ba-p/270358</a><br>
<br>
On Mon, Jun 8, 2020 at 1:45 PM William Herrin <<a href="mailto:bill@herrin.us" target="_blank">bill@herrin.us</a>> wrote:<br>
><br>
> On Mon, Jun 8, 2020 at 10:52 AM <<a href="mailto:ljwobker@gmail.com" target="_blank">ljwobker@gmail.com</a>> wrote:<br>
> > Every "fast" FIB implementation I'm aware of takes a set of prefixes, stores them in some sort of data structure, which can perform a longest-prefix lookup on the destination address and eventually get to an actual physical interface for forwarding that packet.  Exactly how those prefixes are stored and exactly how load-balancing is performed is *very* platform specific, and has tons of variability.  I've worked on at least a dozen different hardware based forwarding planes, and not a single pair of them used the same set of data structures and design tradeoffs.<br>
><br>
> Howdy,<br>
><br>
> AFAIK, there are two basic approaches: TCAM and Trie.  You can get off<br>
> in to the weeds fast dealing with how you manage that TCAM or Trie and<br>
> the Trie-based implementations have all manner of caching strategies<br>
> to speed them up but the basics go back to TCAM and Trie.<br>
><br>
> TCAM (ternary content addressable memory) is a sort of tri-state SRAM<br>
> with a special read function. It's organized in rows and each bit in a<br>
> row is set to 0, 1 or Don't-Care. You organize the routes in that<br>
> memory in order from most to least specific with the netmask expressed<br>
> as don't-care bits. You feed the address you want to match in to the<br>
> TCAM. It's evaluated against every row in parallel during that clock<br>
> cycle. The TCAM spits out the first matching row.<br>
><br>
> A Trie is a tree data structure organized by bits in the address.<br>
> Ordinary memory and CPU. Log-nish traversal down to the most specific<br>
> route. What you expect from a tree.<br>
><br>
> Or have I missed one?<br>
><br>
> Regards,<br>
> Bill Herrin<br>
><br>
><br>
> --<br>
> William Herrin<br>
> <a href="mailto:bill@herrin.us" target="_blank">bill@herrin.us</a><br>
> <a href="https://bill.herrin.us/" rel="noreferrer" target="_blank">https://bill.herrin.us/</a><br>
</blockquote></div></div>