Partial vs Full tables

Mon Jun 8 23:19:34 UTC 2020

Juniper Networks has also tried using Bloom filters.

https://patents.google.com/patent/US20170187624

I think the QFX10002 was the first product they made which used this approach.

https://forums.juniper.net/t5/Archive/Juniper-QFX10002-Technical-Overview/ba-p/270358

On Mon, Jun 8, 2020 at 1:45 PM William Herrin <bill at herrin.us> wrote:
>
> On Mon, Jun 8, 2020 at 10:52 AM <ljwobker at gmail.com> wrote:
> > 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.
>
> Howdy,
>
> AFAIK, there are two basic approaches: TCAM and Trie.  You can get off
> in to the weeds fast dealing with how you manage that TCAM or Trie and
> the Trie-based implementations have all manner of caching strategies
> to speed them up but the basics go back to TCAM and Trie.
>
> TCAM (ternary content addressable memory) is a sort of tri-state SRAM
> with a special read function. It's organized in rows and each bit in a
> row is set to 0, 1 or Don't-Care. You organize the routes in that
> memory in order from most to least specific with the netmask expressed
> as don't-care bits. You feed the address you want to match in to the
> TCAM. It's evaluated against every row in parallel during that clock
> cycle. The TCAM spits out the first matching row.
>
> A Trie is a tree data structure organized by bits in the address.
> Ordinary memory and CPU. Log-nish traversal down to the most specific
> route. What you expect from a tree.
>
> Or have I missed one?
>
> Regards,
> Bill Herrin
>
>
> --
> William Herrin
> bill at herrin.us
> https://bill.herrin.us/