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 <b...@herrin.us> wrote: > > On Mon, Jun 8, 2020 at 10:52 AM <ljwob...@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 > b...@herrin.us > https://bill.herrin.us/
