4 ms·

Can someone explain why loading a 1MM-route BGP table onto a network switch is a "hard problem" that requires fancy hardware to solve, rather than something tha

by derefr 3y ago

Can someone explain why loading a 1MM-route BGP table onto a network switch is a "hard problem" that requires fancy hardware to solve, rather than something that even commodity hardware today is capable of? Presuming you do your IPv4 and IPv6 routing separately... For IPv4, an interval-treemap from uint32-pair intervals to uint8 output ports fits into the default memory config of a PC from 1994; and each lookup into said tree resolves in nanoseconds, even on a machine of the era — esp. for tree-node pages that are hot in CPU cache. And for IPv6, the tree could grow a lot larger, since the intervals are, per se, "uint128"-pairs... but there just aren't that many extant IPv6 routes yet, so the table is actually small in practice. What are the constraints on the problem that I'm missing?

phirephly 3y ago
When you want line rate forwarding across several Tbps of front panel ports, you need the packet pipeline to be able to make all the routing decisions without involvement from the OS. 8Bpps just doesn't give you time to be able to walk any kind of data structure in memory. Running full internet tables on a x86 server where you can only get a few Gbps up to maybe a few dozen Gbps is much easier.
- cookiengineer 3y ago
  Isn't this what BPF and XDP try to target with their SmartNIC offloading, like the ones supported from Metronome?
  - phirephly 3y ago
    Sure. And switch ASICs hang off a CPU as a PCIe device, so the line between smartNICs and low end ASICs start to blur. The key is hardware acceleration of some sort.
alfons_foobar 3y ago
Speed. If your want to forward traffic at line rate (think 10/40/100 gbps per port), having the OS handle packets becomes a bottleneck.
crote 3y ago
A Cisco Catalyst 6506 can handle 330 Mpps, so you need to have a guaranteed lookup time of about 3ns. This router was released in 2005, back when a CPU was lucky to have 2MB of L2 cache which had a 10ns access time. So no, you can't just have the routing table in cache. Considering a random read from memory takes in the order of 200 nanoseconds, you're not going to be able to handle that with commodity hardware. It might be doable in 2023 - but 2023 routers are able to handle way more packages too.
- dfox 3y ago
  Cisco specifies Sup720 as being capable of “up to 400Mpps*” routed IPv4 with the footnote implying that this is in dCEF mode. With dCEF, each linecard has its own forwarding logic, so the lookup time deadline has to be multiplied by number of linecards (ie. 4 for 6506 chassis). One implication of dCEF is that you end up replicating somewhat expensive ASICs across the system to gain more performance, which gets real expensive real fast. Not that it changes much about your point.
dfox 3y ago
6500/7600 is weird beast where the same HW architecture (and well 4 generations of it that are to some extent compatible although internally very different) are used as both high port density ethernet switch (6500) and as an router (7600, the only meaningful difference in the HW is that 7600 is painted white). In almost all configurations all the forwarding decisions are done in hardware, which involves somewhat expensive memory chip that Cisco calls TCAM (Ternary Content Addressable Memory), essentially an SRAM array interspersed with comparators that can find a FIB record matching the destination address with most specific mask in one cycle. In the actual implementation it is not a full TCAM and involves some kind of hashing and lookup takes multiple cycles, to make it not ridiculously expensive, but still it is not priced like your typical off the shelf 6T-SRAM (which by itself is orders of magnitude more expensive than random high volume DDRx SDRAM). Another thing is that the thing is somewhat old and designed by Cisco who will not go out of their way to produce something that makes it obvious that their product can be replaced by a x86 box running Linux And good luck making a x86 box that has 720Gbps bandwidth and 144 ethernet ports. There is a question of exactly what is the real world practical application for 48 port gigabit linecard (there even is a PoE option, 6500 in right config can prowide kilowatts of PoE) in a router that can speak BGP, but well, you can build such a thing from 6500.
- derefr 3y ago
  The thing I was imagining replacing here is the supervision card alone (the sup720-XL), not the entire box. The supervision card doesn't need 720Gbps bandwidth; it's just spitting routing decisions, not entire packets. (And I would bet that established L3 flows cache their routing decisions in per-ASIC channel descriptors for short TTLs; so it's probably not even being prompted for a routing decision for every single packet, either.) I assume the supervision card is prompted over some wire protocol by the ASICs in the switches for routing decisions, and responds back to them with a predictable delay. To achieve parity with the existing supervision card, it "only" needs to emit 30MM one-byte(!) decisions per second. I.e. a top-line input rate of 3840Mbps (for IPv6), and a top-line output rate of 240Mbps. Basically, it confuses me why you can't slap such a "supervision card" together by taking a modern 8-core single-board computer that can fit the entire routing table into L2 cache on each core, and has a PCI-e socket; plugging an Infiniband card or whatever into it; and then running an RTOS on it. Heck, when you think about it, SBCs are so cheap compared to a single used sup720-XL, that you could cluster them inside your router, with each supervision shard taking routing-decision load from 1/Nth of the ASICs.

by derefr 3y ago

phirephly 3y ago

When you want line rate forwarding across several Tbps of front panel ports, you need the packet pipeline to be able to make all the routing decisions without involvement from the OS. 8Bpps just doesn't give you time to be able to walk any kind of data structure in memory. Running full internet tables on a x86 server where you can only get a few Gbps up to maybe a few dozen Gbps is much easier.

cookiengineer 3y ago
Isn't this what BPF and XDP try to target with their SmartNIC offloading, like the ones supported from Metronome?
- phirephly 3y ago
  Sure. And switch ASICs hang off a CPU as a PCIe device, so the line between smartNICs and low end ASICs start to blur. The key is hardware acceleration of some sort.

alfons_foobar 3y ago

Speed. If your want to forward traffic at line rate (think 10/40/100 gbps per port), having the OS handle packets becomes a bottleneck.

crote 3y ago

A Cisco Catalyst 6506 can handle 330 Mpps, so you need to have a guaranteed lookup time of about 3ns. This router was released in 2005, back when a CPU was lucky to have 2MB of L2 cache which had a 10ns access time. So no, you can't just have the routing table in cache. Considering a random read from memory takes in the order of 200 nanoseconds, you're not going to be able to handle that with commodity hardware. It might be doable in 2023 - but 2023 routers are able to handle way more packages too.

dfox 3y ago
Cisco specifies Sup720 as being capable of “up to 400Mpps*” routed IPv4 with the footnote implying that this is in dCEF mode. With dCEF, each linecard has its own forwarding logic, so the lookup time deadline has to be multiplied by number of linecards (ie. 4 for 6506 chassis). One implication of dCEF is that you end up replicating somewhat expensive ASICs across the system to gain more performance, which gets real expensive real fast. Not that it changes much about your point.

dfox 3y ago

6500/7600 is weird beast where the same HW architecture (and well 4 generations of it that are to some extent compatible although internally very different) are used as both high port density ethernet switch (6500) and as an router (7600, the only meaningful difference in the HW is that 7600 is painted white). In almost all configurations all the forwarding decisions are done in hardware, which involves somewhat expensive memory chip that Cisco calls TCAM (Ternary Content Addressable Memory), essentially an SRAM array interspersed with comparators that can find a FIB record matching the destination address with most specific mask in one cycle. In the actual implementation it is not a full TCAM and involves some kind of hashing and lookup takes multiple cycles, to make it not ridiculously expensive, but still it is not priced like your typical off the shelf 6T-SRAM (which by itself is orders of magnitude more expensive than random high volume DDRx SDRAM). Another thing is that the thing is somewhat old and designed by Cisco who will not go out of their way to produce something that makes it obvious that their product can be replaced by a x86 box running Linux And good luck making a x86 box that has 720Gbps bandwidth and 144 ethernet ports. There is a question of exactly what is the real world practical application for 48 port gigabit linecard (there even is a PoE option, 6500 in right config can prowide kilowatts of PoE) in a router that can speak BGP, but well, you can build such a thing from 6500.

derefr 3y ago
The thing I was imagining replacing here is the supervision card alone (the sup720-XL), not the entire box. The supervision card doesn't need 720Gbps bandwidth; it's just spitting routing decisions, not entire packets. (And I would bet that established L3 flows cache their routing decisions in per-ASIC channel descriptors for short TTLs; so it's probably not even being prompted for a routing decision for every single packet, either.) I assume the supervision card is prompted over some wire protocol by the ASICs in the switches for routing decisions, and responds back to them with a predictable delay. To achieve parity with the existing supervision card, it "only" needs to emit 30MM one-byte(!) decisions per second. I.e. a top-line input rate of 3840Mbps (for IPv6), and a top-line output rate of 240Mbps. Basically, it confuses me why you can't slap such a "supervision card" together by taking a modern 8-core single-board computer that can fit the entire routing table into L2 cache on each core, and has a PCI-e socket; plugging an Infiniband card or whatever into it; and then running an RTOS on it. Heck, when you think about it, SBCs are so cheap compared to a single used sup720-XL, that you could cluster them inside your router, with each supervision shard taking routing-decision load from 1/Nth of the ASICs.