While I did allude to some of the complexity, my main point is that FIB compression does not allow you to install a FIB with less memory. Because you must be prepared for transients during which the FIB needs to store mostly uncompressed anyway. All it does is to increase convergence time. Kind Regards, Jakob From: William Herrin <bill@herrin.us> Date: Sunday, October 1, 2023 at 6:32 PM To: Jakob Heitz (jheitz) <jheitz@cisco.com> Cc: nanog@nanog.org <nanog@nanog.org> Subject: Re: maximum ipv4 bgp prefix length of /24 ? On Sun, Oct 1, 2023 at 5:40 PM Jakob Heitz (jheitz) via NANOG <nanog@nanog.org> wrote:

Among the issues: Suppose the FIB has all the /24 components to make a /20, so it programs a /20. Then one of the /24's changes nexthop. It now has to undo all that compression

Yeah... all this stuff is on the same level of complexity as implementing a B-Tree. Standard task on the road to an undergraduate computer science degree. Compared to decoding a BGP update message, where nearly everything is variable length and you have to nibble away at the current field to find the start of the next field, this is a cakewalk. It doesn't actually get complicated until you want to do more than just joining adjacent address blocks. Regards, Bill Herrin -- William Herrin bill@herrin.us https://bill.herrin.us/

William Herrin wrote on 02/10/2023 08:56:

All it means is that you have to keep an eye on your FIB size as well, since it's no longer the same as your RIB size.

the point Jacob is making is is that when using FIB compression, the FIB size depends on both RIB size and RIB complexity. I.e. what was previously a deterministic 1:1 ratio between RIB and FIB - which is straightforward to handle from an operational point of view - becomes non-deterministic. The difficulty with this is that if you end up with a FIB overflow, your router will no longer route. That said, there are cases where FIB compression makes a lot of sense, e.g. leaf sites, etc. Conversely, it's not a generally appropriate technology for a dense dfz core device. It's a tool in the toolbox, one of many. Nick

That depends. When the FIB gets too big, routers don't immediately die. Instead, their performance degrades. Just like what happens with oversubscription elsewhere in the system.

If you consider blackholing traffic because the relevant next-hops aren't present in the FIB to be looked up as "degradation".... I guess? If you keep a 10%

slack for transients, you still have a 20% net gain in your equipment's capability versus no compression.

This ignores whatever % of something else you have up to get effective compression. On Mon, Oct 2, 2023 at 4:41 AM William Herrin <bill@herrin.us> wrote:

On Mon, Oct 2, 2023 at 1:18 AM Nick Hilliard <nick@foobar.org> wrote:

...

The difficulty with this is that if you end up with a FIB overflow, your router will no longer route.

Hi Nick,

That depends. When the FIB gets too big, routers don't immediately die. Instead, their performance degrades. Just like what happens with oversubscription elsewhere in the system.

With a TCAM-based router, the least specific routes get pushed off the TCAM (out of the fast path) up to the main CPU. As a result, the PPS (packets per second) degrades really fast.

With a DRAM+SRAM cache system, the least used routes fall out of the cache. They haven't actually been pushed out of the fast path, but the fast path gets a little bit slower. The PPS degrades, but not as sharply as with a TCAM-based router.

...

That said, there are cases where FIB compression makes a lot of sense, e.g. leaf sites, etc. Conversely, it's not a generally appropriate technology for a dense dfz core device. It's a tool in the toolbox, one of many.

The case for FIB compression deep in the core is... not as obvious as the case near the edge for sure. But I wouldn't discount it on any installation that has a reasonably defined notion of "upstream," as opposed to installations where the only sorts of interfaces are either lateral or downstream.

Look at it this way: here are some numbers from last Friday's BGP report:

BGP routing table entries examined: 930281 Prefixes after maximum aggregation (per Origin AS): 353509 Deaggregation factor: 2.63 Unique aggregates announced (without unneeded subnets): 453312

Obviously adjacent routes to the same AS aren't always going to have the same next hop. But I'll bet you that they do more often than not, even deep in the core. Even if only half the adjacent routes from the same AS have the same next hop when found deep in the core, according to these numbers that's still a 30% compression. If you keep a 10% slack for transients, you still have a 20% net gain in your equipment's capability versus no compression.

Regards, Bill Herrin

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

Come on man, go re-read the post. The two paragraphs you cut literally explained what happens -instead of- routes dropping out of the FIB or being black holed.

Ok On Mon, Oct 2, 2023 at 2:03 PM William Herrin <bill@herrin.us> wrote:

On Mon, Oct 2, 2023 at 6:05 AM Tom Beecher <beecher@beecher.cc> wrote:

...

...

That depends. When the FIB gets too big, routers don't immediately die. Instead, their performance degrades. Just like what happens with oversubscription elsewhere in the system.

If you consider blackholing traffic because the relevant next-hops aren't present in the FIB to be looked up as "degradation".... I guess?

Come on man, go re-read the post. The two paragraphs you cut literally explained what happens -instead of- routes dropping out of the FIB or being black holed.

Regards, Bill Herrin

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

Seems like we've reached the limits of apriori speculation. At this point I'd like to see data demonstrating that it's at least viable from a statistical perspective. If someone is motivated to demonstrate this, a "backtest" against historical data would be the next step. Later, one could design the study to reveal "transient degradation" (loops, drops, etc.) and their probability, though the duration would be more a function of the implementation. It would be best to "backtest" the status quo as a control because it too has transient degradation, for a more apples-to-apples comparison. I'm not sufficiently motivated (nor knowledgeable in statistics) to take this on. I see this more in the domain of vendors to determine the best approach for their implementation. On Mon, Oct 2, 2023 at 9:21 AM tim@pelican.org <tim@pelican.org> wrote:

On Monday, 2 October, 2023 09:39, "William Herrin" <bill@herrin.us> said:

...

That depends. When the FIB gets too big, routers don't immediately die. Instead, their performance degrades. Just like what happens with oversubscription elsewhere in the system.

With a TCAM-based router, the least specific routes get pushed off the TCAM (out of the fast path) up to the main CPU. As a result, the PPS (packets per second) degrades really fast.

With a DRAM+SRAM cache system, the least used routes fall out of the cache. They haven't actually been pushed out of the fast path, but the fast path gets a little bit slower. The PPS degrades, but not as sharply as with a TCAM-based router.

Spit-balling here, is there a possible design for not-Tier-1 providers where routing optimality (which is probably not a word) degrades rather than packet-shifting performance?

If the FIB is full, can we start making controlled and/or smart decisions about what to install, rather than either of the simple overflow conditions?

For starters, as long as you have *somewhere* you can point a default at in the worst case, even if it's far from the *best* route, you make damn sure you always install a default.

Then you could have knobs for what other routes you discard when you run out of space. Receiving a covering /16? Maybe you can drop the /24s, even if they have a different next hop - routing will be sub-optimal, but it will work. (I know, previous discussions around traffic engineering and whether the originating network must / does do that in practice...)

Understand which routes your customers care about / where most of your traffic goes? Set the "FIB-preference" on those routes as you receive them, to give them the greatest chance of getting installed.

Not a hardware designer, I have little idea as to how feasible this is - I suspect it depends on the rate of churn, complexity of FIB updates, etc. But it feels like there could be a way to build something other than "shortest -> punt to CPU" or "LRU -> punt to CPU".

Or is everyone who could make use of this already doing the same filtering at the RIB level, and not trying to fit a quart RIB into a pint FIB in the first place?

Thanks, Tim.

On Mon, Oct 2, 2023 at 6:40 AM Joshua Miller <contemno@gmail.com> wrote:

At this point I'd like to see data demonstrating that it's at least viable from a statistical perspective.

https://conferences.sigcomm.org/sigcomm/2013/papers/sigcomm/p111.pdf https://yangtonghome.github.io/uploads/MAoFIBC.pdf More where those came from if you google "BGP FIB compression paper." Regards, Bill Herrin -- William Herrin bill@herrin.us https://bill.herrin.us/

On Mon, Oct 2, 2023 at 6:21 AM tim@pelican.org <tim@pelican.org> wrote:

On Monday, 2 October, 2023 09:39, "William Herrin" <bill@herrin.us> said:

...

That depends. When the FIB gets too big, routers don't immediately die. Instead, their performance degrades. Just like what happens with oversubscription elsewhere in the system.

With a TCAM-based router, the least specific routes get pushed off the TCAM (out of the fast path) up to the main CPU. As a result, the PPS (packets per second) degrades really fast.

With a DRAM+SRAM cache system, the least used routes fall out of the cache. They haven't actually been pushed out of the fast path, but the fast path gets a little bit slower. The PPS degrades, but not as sharply as with a TCAM-based router.

Spit-balling here, is there a possible design for not-Tier-1 providers where routing optimality (which is probably not a word) degrades rather than packet-shifting performance?

If the FIB is full, can we start making controlled and/or smart decisions about what to install, rather than either of the simple overflow conditions?

For starters, as long as you have *somewhere* you can point a default at in the worst case, even if it's far from the *best* route, you make damn sure you always install a default.

Then you could have knobs for what other routes you discard when you run out of space. Receiving a covering /16? Maybe you can drop the /24s, even if they have a different next hop - routing will be sub-optimal, but it will work. (I know, previous discussions around traffic engineering and whether the originating network must / does do that in practice...)

The problem with this approach is you now have non-deterministic routing. Depending on the state of FIB compression, packets *may* flow out interfaces that are not what the RIB thinks they will be. This can be a good recipe for routing micro-loops that come and go as your FIB compression size ebbs and flows. Taking your example: RTR-A----------RTR-B---------RTR-C RTR-A is announcing a /16 to RTR-B RTR-C is announcing a /24 from within the /16 to RTR-B, which is passing it along to RTR-A If RTR-B's FIB compression fills up, and falls back to "drop the /24, since I see a /16", packets destined to the /24 arriving from RTR-A will reach RTR-B, which will check its FIB, and send them back towards RTR-A....which will send them back to RTR-B, until TTL is exceeded. BTW, this scenario holds true even when it's a default route coming from RTR-A, so saying "well, OK, but we can do FIB compression easily as long as we have a default route to fall back on" still leads to packet-ping-ponging on your upstream interface towards your default if you ever drop a more specific from your FIB that is destined downstream of you. You're better off doing the filtering at the RIB end of things, so that RTR-B no longer passes the /24 to RTR-A; sure, routing breaks at that point, but at least you haven't filled up the RTR-A to RTR-B link with packets ping-ponging back and forth. Your routing protocols *depend* on packets being forwarded along the interfaces the RIB thinks they'll be going out in order for loop-free routing to occur. If the FIB decisions are made independent of the RIB state, your routing protocols might as well just give up and go home, because no matter how many times they run Dijkstra, the path to the destination isn't going to match where the packets ultimately end up going. You could of course fix this issue by propagating the decisions made by the FIB compression algorithm back up into the RIB; at least then, the network engineer being paged at 3am to figure out why a link is full will instead be paged to figure out why routes aren't showing up in the routing table that policy *says* should be showing up. Understand which routes your customers care about / where most of your

traffic goes? Set the "FIB-preference" on those routes as you receive them, to give them the greatest chance of getting installed.

Not a hardware designer, I have little idea as to how feasible this is - I suspect it depends on the rate of churn, complexity of FIB updates, etc. But it feels like there could be a way to build something other than "shortest -> punt to CPU" or "LRU -> punt to CPU".

Or is everyone who could make use of this already doing the same filtering at the RIB level, and not trying to fit a quart RIB into a pint FIB in the first place?

The sane ones who care about the sanity of their network engineers certainly do. ^_^;

Thanks, Tim.

Thanks! Matt

On 10/2/23 20:44, Tim Franklin wrote:

Had NOT considered the looping - that's what you get for writing in public without thinking it all the way through *blush*.

Thanks for poking holes appropriately,

Like I said, it's going to be a messy experiment - for probably a decade, at least. As Saku has highlighted as well, vendors are likely to find a lot of sludge in this experiment that they will never be able to share with us... likely because it will be too complicated for us to understand in a coherent way, or likely because the experiment changes so rapidly it makes no sense to tell us about issues which will quickly become obsolete. Many lessons will be learned, but ultimately, one would be naive to think this black box will just work. All I want is a "set routing-options fib-compression disable" present for Christmas. Mark.

On Mon, Oct 2, 2023 at 11:46 AM Tim Franklin <tim@pelican.org> wrote:

On 02/10/2023 19:24, Matthew Petach wrote:

The problem with this approach is you now have non-deterministic routing.

Depending on the state of FIB compression, packets *may* flow out interfaces that are not what the RIB thinks they will be. This can be a good recipe for routing micro-loops that come and go as your FIB compression size ebbs and flows.

Had NOT considered the looping - that's what you get for writing in public without thinking it all the way through *blush*.

Thanks for poking holes appropriately, Tim.

No worries--if this were easy, we would have been doing it decades ago without thinking twice. To William's point to Tom--we are perhaps using the term "compression" in incompatible ways at times during this conversation. There is a difference between what the papers Williams 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. "FIB-count-reduction" would be a more accurate term for what we're tossing about here, and that's where dragons lie, because that's where your FIB and RIB no longer represent the same set of information. And while Jon is right, it can help struggling ISPs stave off expensive upgrades, it does so at the cost of potentially increased troubleshooting nightmares when packets stop going where the RIB expects them to go, and network engineers are left scratching their heads trying to figure out why. ^_^; 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. ;) Thanks! Matt

On 02/10/2023 14:19, tim@pelican.org wrote:

If the FIB is full, can we start making controlled and/or smart decisions about what to install, rather than either of the simple overflow conditions?

There is a project [1] that make use of sflow to install the top n prefixes by traffic, presuming there is a default route for the remainder. Chris [1] https://github.com/sflow-rt/active-routes

On a related note, I'm working on a project to handle FIB overflow in such a way as to cause the least disruption in the network. I welcome suggestions either on or off list. Kind Regards, Jakob

First, no, a transient where all route disaggregating disappears from the global table is extraordinarily unlikely. Second, as I understand it, each update cycle results in rebuilding the fib from scratch rather than figuring out how to splice and dice it, so the computation required to cope with that single /24 change isn’t exactly as described. Finally, unless that /24 change ends up changing the exit interface or next-hop on the exit interface (which decreases in probability with topological distance), it wouldn’t actually change the fib content. The process of downloading a new fib to line cards from the RE is very fast. Break before make may be tolerable risk. It won’t lose a statistically significant number of packets in a single event. If events are occurring frequently enough to be an issue, then I think the route flapping is a bigger problem than the lost packets. YMMV Owen

On Oct 1, 2023, at 21:55, Jakob Heitz (jheitz) via NANOG <nanog@nanog.org> wrote:

 While I did allude to some of the complexity, my main point is that FIB compression does not allow you to install a FIB with less memory. Because you must be prepared for transients during which the FIB needs to store mostly uncompressed anyway. All it does is to increase convergence time.

Kind Regards, Jakob

From: William Herrin <bill@herrin.us> Date: Sunday, October 1, 2023 at 6:32 PM To: Jakob Heitz (jheitz) <jheitz@cisco.com> Cc: nanog@nanog.org <nanog@nanog.org> Subject: Re: maximum ipv4 bgp prefix length of /24 ?

On Sun, Oct 1, 2023 at 5:40 PM Jakob Heitz (jheitz) via NANOG <nanog@nanog.org> wrote:

...

Among the issues: Suppose the FIB has all the /24 components to make a /20, so it programs a /20. Then one of the /24's changes nexthop. It now has to undo all that compression

Yeah... all this stuff is on the same level of complexity as implementing a B-Tree. Standard task on the road to an undergraduate computer science degree. Compared to decoding a BGP update message, where nearly everything is variable length and you have to nibble away at the current field to find the start of the next field, this is a cakewalk.

It doesn't actually get complicated until you want to do more than just joining adjacent address blocks.

Regards, Bill Herrin

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