Partial vs Full tables

Sat Jun 6 01:48:11 UTC 2020

On Fri, Jun 5, 2020 at 6:08 PM Yang Yu <yang.yu.list at gmail.com> wrote:
> On Fri, Jun 5, 2020 at 10:39 AM William Herrin <bill at herrin.us> wrote:
> > Speak of which, did anyone ever implement FIB compression? I seem to
> > remember the calculations looked really favorable for the leaf node
> > use case (like James') where the router sits at the edge with a small
> > number of more or less equivalent upstream transits. The FIB is the
> > expensive memory. The RIB sits in the cheap part of the hardware.
>
> fib optimize => using LPM table for LEM
> https://www.arista.com/en/um-eos/eos-section-28-11-ipv4-commands#ww1173031

Cool. So for folks who want a nutshell version about FIB compression,
here it is:

Your router has routing information bases (RIB) and a forwarding
information base (FIB). The FIB is what picks where to move the
packet. For each packet you look up the destination address in the FIB
and then send the packet to the next hop that you found in the FIB.
This is the expensive part of the router hardware because it has to do
this for every packet at line speed.

When we talk about the BGP table, we're talking about the RIB. That's
what has AS paths, communities, distances, etc. It's stored in
ordinary DRAM and computed by an ordinary CPU. Before the router can
route packets, the data in the RIB is reduced to a forwarding table
that's stored in the FIB. Normally, this means you take every route in
the RIB, pick the "best" one, figure out the next hop and then store
the result in the FIB.

FIB compression replaces that process with one that's more selective
about which RIB routes get installed in the FIB. The simplest version
works like this:

1. Figure out which next hop has the most routes pointing to it.
2. Add a default route to that next hop
3. Remove all the now-unnecessary more specific routes that go to the
same next hop.

If you have two upstream transit services, you've probably just cut
your FIB table size by more than half. Which means you don't need as
much of the pricey part of the router.

The actual algorithm gets more complex, the computational cost goes up
and the reduction in fib routes improves.

The down side is something you don't usually think about: default is
implicitly routed to reject (respond with icmp unreachable). 0.0.0.0/0
-> reject. You don't see it in your configuration but it's there all
the same. FIB compression eliminates the implicit reject and instead
routes the unroutable packets to a more or less random next hop. If
that next hop is also using FIB compression, it may route them right
back to you, creating a routing loop until the packet's TTL expires.

Happy weekend everybody,
Bill Herrin

-- 
William Herrin
bill at herrin.us
https://bill.herrin.us/