On 2020/12/15 3:16, Lawrence Wobker wrote:
So I’d argue that the pedantic answer is “you need only as many bits of entropy
as your largest fan out” — meaning that 10 bits would allow 1024-way ECMP. But
I don’t think that’s what you were actually after...
Most of the challenges I’ve seen are not around how many bits you end up with,
but rather how you get to those bits. There are lots of different ways to
compute the hash values, but if you want to be “fast” you’re unlikely to also
get “good” and “cheap”.... generally to select a path, we run a hash function
against some set of packet fields, then map that hash to one of the member
links. A “perfect” balancing algorithm would be crypto grade hash generation
with a large output, and a true modulo operation to select which member we use.
The reality is that both crypto hash functions and modulo operations are more
expensive than lots of other ways to compute it, so vendors (disclaimer, I work
for Cisco) have lots and lots of combinations for how it’s actually done.
And then you still have the flow issue: since the vast majority of
implementation are hashing flows regardless of their actual bandwidth, if you
hash even a few ‘elephants’ onto the same link, you’re not going to get good
distribution no matter how good your hashing/selection mechanism is. With
respect to your comment about standardization, I doubt you’ll ever be able to
get a broad consensus on the combination of “how many bits we need given the
others constraints for a spec” and “how much we want to assume about the
goodness of the hash generator” and “how much I’m willing to just throw bits at
the problem” ...
—lj
—lj
________________________________
From: Lawrence Wobker <[email protected]>
Sent: Monday, December 14, 2020 12:33:07 PM
To: Pascal Thubert (pthubert) <[email protected]>; NANOG <[email protected]>
Subject: Re: how many bits of entropy do we need for load balancing?
So I’d argue that the pedantic answer is “you need only as many bits of entropy
as your largest fan out” — meaning that 10 bits would allow 1024-way ECMP.
Most of the challenges I’ve seen are not around how many bits you end up with,
but rather how you get to that state. There are lots of different ways to
compute the hash values, but if you want to be “fast” you’re unlikely to also
get “good” and “cheap”.... generally to select a path, we run a hash function
against some set of packet fields, then map that hash to one of the member
links. A “perfect” balancing algorithm would be crypto grade hash generation
with a large output, and a true modulo operation to select which member we use.
The reality is that both crypto hash functions and modulo operations are more
expensive than lots of other ways to compute it, so vendors (disclaimer, I work
for Cisco) have lots and lots of combinations for how it’s actually done.
And then you still have the flow issue: since the vast majority of
implementation are hashing flows regardless of their actual bandwidth, if you
hash even a few ‘elephants’ onto the same link, you’re not going to get good
distribution no matter how good your hashing/selection mechanism is.
—lj
________________________________
From: NANOG <[email protected]> on behalf of Pascal Thubert
(pthubert) via NANOG <[email protected]>
Sent: Monday, December 14, 2020 9:44:05 AM
To: NANOG <[email protected]>
Subject: how many bits of entropy do we need for load balancing?
Dear all:
How many bits of entropy do we need for (ECMP) load balancing in the core?
This question has kept coming up regularly in many discussions and drafts at
the IETF.
The IPv6 flow label is 20 bits but hardware implementations do their balancing
only on a subset of that, e.g. 12 or 16 bits.
There are drafts for MPLS, BIER etc.. that provide their own entropy bit fields
of various sizes.
I traced to a 6MAN discussion at IETF 78 a claim that 10 or 11 bits were enough.
Did someone do the actual exercise? It would be neat to align the IETF specs in
the making to whatever truth may be established in the core.
Keep safe,
Pascal
