Partial vs Full tables
anoop at alumni.duke.edu
Tue Jun 9 00:12:39 UTC 2020
There are many different tries -- see here for some examples.
And an enhancement to LC-tries
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.
Here's a good tutorial, and I don't think even this is exhaustive.
On Mon, Jun 8, 2020 at 4:19 PM Josh Hoppes <josh.hoppes at gmail.com> wrote:
> Juniper Networks has also tried using Bloom filters.
> I think the QFX10002 was the first product they made which used this
> 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/
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the NANOG