So Philip Smith / Geoff Huston's CIDR report becomes worth a good hard look today

Thu Aug 14 03:09:53 UTC 2014

Once upon a time, Brett Frankenberger <rbf+nanog at panix.com> said:
> -- This isn't that hard to implement.  Once you have a FIB and
> primitives for manipulating it, it's not especially difficult to extend
> them to also maintain a minimal-size-FIB.

I would say it is hard to implement, or at least non-trivial.  Building
a reduced FIB from a given RIB is not hard, but then RIB changes become
more complex (possibly significantly so) to process into FIB updates.

For example, the control plane receives a BGP update that removes a
route from the RIB.  Right now, the check is simply "was this the best
path" (and if so, "was it in the FIB" for systems with RIB->FIB
filtering methods).  If so, remove it from the FIB.  If there's a
next-best path in the RIB, add it to the FIB.

With a compacted FIB, a RIB update has to check a bunch of different
things to see what (if any) FIB updates are required.  This could also
require other RIB updates (to mark other RIB entries as now in or out of
the FIB).

The lowest-overhead method would probably be for the control plane to
keep a separate (non-compacted) copy of the FIB, with all the pointers
to how things were compacted before sending to the forwarding plane
compacted FIB.  That would take up more control plane RAM (and still add
CPU overhead to every RIB change).

If you thought things like rpd stalls on JUNOS were fun before, imagine
the excitement you could have with FIB compacting!
-- 
Chris Adams <cma at cmadams.net>