On Fri, Jun 5, 2020 at 6:08 PM Yang Yu <yang.yu.list@gmail.com> wrote:
On Fri, Jun 5, 2020 at 10:39 AM William Herrin <bill@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@herrin.us https://bill.herrin.us/