Re: how many bits of entropy do we need for load balancing?

[Masataka Ohta <mohta () necom830 hpcl titech ac jp>]

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 <ljwobker () gmail com>
> Sent: Monday, December 14, 2020 12:33:07 PM
> To: Pascal Thubert (pthubert) <pthubert () cisco com>; NANOG <nanog () nanog org>
> 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 <nanog-bounces+ljwobker=pobox.com () nanog org> on behalf of Pascal Thubert (pthubert) via NANOG <nanog () 
> nanog org>
> Sent: Monday, December 14, 2020 9:44:05 AM
> To: NANOG <nanog () nanog org>
> 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