<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=Windows-1252">
</head>
<body>
<div>
<div>
<div style="direction: ltr;">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...</div>
<div><br>
</div>
<div style="direction: ltr;">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. </div>
<div><br>
</div>
<div style="direction: ltr;">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” ...<span id="ms-outlook-ios-cursor"></span></div>
<div><br>
</div>
<div style="direction: ltr;">—lj </div>
</div>
<div><br>
</div>
<div class="ms-outlook-ios-signature">
<div style="color: rgb(33, 33, 33); background-color: rgb(255, 255, 255); text-align: left;" dir="auto">
—lj </div>
</div>
</div>
<hr style="display:inline-block;width:98%" tabindex="-1">
<div id="divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" style="font-size:11pt" color="#000000"><b>From:</b> Lawrence Wobker <ljwobker@gmail.com><br>
<b>Sent:</b> Monday, December 14, 2020 12:33:07 PM<br>
<b>To:</b> Pascal Thubert (pthubert) <pthubert@cisco.com>; NANOG <nanog@nanog.org><br>
<b>Subject:</b> Re: how many bits of entropy do we need for load balancing?</font>
<div> </div>
</div>
<div>
<div>
<div>
<div style="direction:ltr">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.</div>
<div><br>
</div>
<div style="direction:ltr">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. </div>
<div><br>
</div>
<div style="direction:ltr">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. <span id="x_ms-outlook-ios-cursor"></span></div>
</div>
<div><br>
</div>
<div class="x_ms-outlook-ios-signature">
<div dir="auto" style="color:rgb(33,33,33); background-color:rgb(255,255,255); text-align:left">
—lj </div>
</div>
</div>
<hr tabindex="-1" style="display:inline-block; width:98%">
<div id="x_divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" color="#000000" style="font-size:11pt"><b>From:</b> NANOG <nanog-bounces+ljwobker=pobox.com@nanog.org> on behalf of Pascal Thubert (pthubert) via NANOG <nanog@nanog.org><br>
<b>Sent:</b> Monday, December 14, 2020 9:44:05 AM<br>
<b>To:</b> NANOG <nanog@nanog.org><br>
<b>Subject:</b> how many bits of entropy do we need for load balancing?</font>
<div> </div>
</div>
<style>
<!--
@font-face
{font-family:"Cambria Math"}
@font-face
{font-family:Calibri}
p.x_x_MsoNormal, li.x_x_MsoNormal, div.x_x_MsoNormal
{margin:0cm;
font-size:11.0pt;
font-family:"Calibri",sans-serif}
span.x_x_EmailStyle17
{font-family:"Calibri",sans-serif;
color:windowtext}
.x_x_MsoChpDefault
{font-family:"Calibri",sans-serif}
@page WordSection1
{margin:70.85pt 70.85pt 70.85pt 70.85pt}
-->
</style>
<div lang="EN-US" style="word-wrap:break-word">
<div class="x_x_WordSection1">
<p class="x_x_MsoNormal"><font size="2" face="Calibri"><span style="font-size:11.0pt">Dear all:</span></font></p>
<p class="x_x_MsoNormal"><font size="2" face="Calibri"><span style="font-size:11.0pt"> </span></font></p>
<p class="x_x_MsoNormal"><font size="2" face="Calibri"><span style="font-size:11.0pt">How many bits of entropy do we need for (ECMP) load balancing in the core?</span></font></p>
<p class="x_x_MsoNormal"><font size="2" face="Calibri"><span style="font-size:11.0pt">This question has kept coming up regularly in many discussions and drafts at the IETF.
</span></font></p>
<p class="x_x_MsoNormal"><font size="2" face="Calibri"><span style="font-size:11.0pt"> </span></font></p>
<p class="x_x_MsoNormal"><font size="2" face="Calibri"><span style="font-size:11.0pt">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.</span></font></p>
<p class="x_x_MsoNormal"><font size="2" face="Calibri"><span style="font-size:11.0pt"> </span></font></p>
<p class="x_x_MsoNormal"><font size="2" face="Calibri"><span style="font-size:11.0pt">There are drafts for MPLS, BIER etc.. that provide their own entropy bit fields of various sizes.</span></font></p>
<p class="x_x_MsoNormal"><font size="2" face="Calibri"><span style="font-size:11.0pt">I traced to a 6MAN discussion at IETF 78 a claim that 10 or 11 bits were enough.
</span></font></p>
<p class="x_x_MsoNormal"><font size="2" face="Calibri"><span style="font-size:11.0pt"> </span></font></p>
<p class="x_x_MsoNormal"><font size="2" face="Calibri"><span style="font-size:11.0pt">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.</span></font></p>
<p class="x_x_MsoNormal"><font size="2" face="Calibri"><span style="font-size:11.0pt"> </span></font></p>
<p class="x_x_MsoNormal"><font size="2" face="Calibri"><span style="font-size:11.0pt">Keep safe,</span></font></p>
<p class="x_x_MsoNormal"><font size="2" face="Calibri"><span style="font-size:11.0pt"> </span></font></p>
<p class="x_x_MsoNormal"><font size="2" face="Calibri"><span style="font-size:11.0pt">Pascal</span></font></p>
</div>
</div>
</div>
</body>
</html>