nanog mailing list archives
Re: Partial vs Full tables
From: William Herrin <bill () herrin us>
Date: Mon, 8 Jun 2020 11:44:27 -0700
On Mon, Jun 8, 2020 at 10:52 AM <ljwobker () 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 () herrin us https://bill.herrin.us/
Current thread:
- Re: Partial vs Full tables, (continued)
- Re: Partial vs Full tables Yang Yu (Jun 05)
- Re: Partial vs Full tables William Herrin (Jun 05)
- Re: Partial vs Full tables Ryan Woolley (Jun 07)
- Re: Partial vs Full tables Saku Ytti (Jun 07)
- Re: Partial vs Full tables Baldur Norddahl (Jun 08)
- Re: Partial vs Full tables William Herrin (Jun 08)
- Re: Partial vs Full tables Nick Hilliard (Jun 08)
- Re: Partial vs Full tables Joe Greco (Jun 08)
- Re: Partial vs Full tables William Herrin (Jun 08)
- Re: Partial vs Full tables Mike Hammett (Jun 08)
- Message not available
- Re: Partial vs Full tables William Herrin (Jun 08)
- Re: Partial vs Full tables Josh Hoppes (Jun 08)
- Re: Partial vs Full tables Anoop Ghanwani (Jun 08)
- Re: Partial vs Full tables Saku Ytti (Jun 08)
- Re: Partial vs Full tables Mike Hammett (Jun 06)
- Re: Partial vs Full tables Mark Tinka (Jun 09)
- Re: Partial vs Full tables Tom Beecher (Jun 05)
- Re: Partial vs Full tables Baldur Norddahl (Jun 05)