On Mon, Oct 2, 2023 at 12:27 PM Matthew Petach <mpet...@netflight.com> wrote: > There is a difference between what the papers William cited are doing, which > is finding more optimal ways of storing the full structure in memory with > what I think the general thread here is talking about, which is > 'proxy-aggregation' of a form--reducing the actual number of entries in the > forwarding table, regardless of the *method* of storage. > > "FIB compression" of the form talked about in the papers William cited is > already being done; we don't store whole string representations of the > routing table in memory, and look them up sequentially, we store them in > binary tries, which are faster and take up less space (e, compressed), but > they still encode and represent the *whole* set of prefixes in the forwarding > table.
Hi Matthew, Either you're misreading the papers or I quoted the wrong ones. Apologies if it's the latter. The RIB is stored in a trie (a radix tree) in essentially all router implementations. From there it's processed into a FIB whose design depends on the hardware implementing it. For a software implementation that's another trie, sometimes with hash-based cache of current activity. For a TCAM, it's an array ordered from most specific to least specific. (TCAMs are special hardware that processes every array element simultaneously instead of linearly.) These structures don't change with FIB compression. What changes is the number of routes stored in them and the complexity of the software that translates the RIB into a FIB. > As Mark just said--sane ISPs push their vendor for a knob to disable it, so > that they can return back the land of deterministic lookups for the sanity of > their engineers. ;) Just so it doesn't get lost - I endorse that idea as well. With a very few exceptions, I think the operator should have sufficient knobs to control how their equipment does its work. The developer doesn't (and can't) know all of the situations the operator will encounter, so can't plan his software to be smart enough to always do the right thing on its own. The exceptions deal with knobs where the operator is not just likely shoot themselves in the foot but likely shoot other people too. That doesn't apply here. Regards, Bill Herrin -- William Herrin b...@herrin.us https://bill.herrin.us/
