Support ECMP fanout equal to the number of front facing ports #91
Description
Right now ECMP fanout for IPv4 is limited to a factor of 8. Part of the reason for this is we use a static lookup table. That approach works, but it does not scale well and takes up a lot of resources. For large scale environments it's important to be able to fan out ECMP up to the number of external ports on a rack switch, this means supporting a fan out factor of up to 32.
I spent a bit of time looking into this, and it looks like there are a few promising options.
Lemire's Method
Using Lemire's Method we can select a random index in a range of [0, s] from a power of two hash value without using mod or division. It's essentially slot = (bit<16>)(((bit<32>)idx * (bit<32>)slots) >> 16). While Tofino does not support multiplication as an operation on bit<N> values, there is the MathUnit extern that supports multiplication. We also need to understand the input bias for this approach and how it effects ECMP. It's not clear to me that the bias rejection mechanism will work as described on the Tofino even with MathUnit, so we need to a) understand the statistical properties of the bias introduced and see if they are acceptable (ECMP is non-uniform for many traffic patterns to begin with) or b) come up with a rejection method suitable for implementation on the Tofino.
Action Selectors
The Tofino Native Architecture (TNA) document describes Action Selectors in section 7.4 and shows how they can be used for ECMP in section 7.4.1.
Whatever we end up going with, we'll also want to do for IPv6 as well, see #84.