<div dir="ltr">Hi Andy,<div><br></div><div>I totally agree that the practical ATCAM capacity from the control plane point of view (e.g. how many routes you can put into a ATCAM with N entries divided into M partitions) is difficult to predict, but "up to N" statement can still be holding some water :) I think that this is an inherent ATCAM property, much like the fact that you can't generally guarantee any specific occupancy for a hashed table (as you clearly outlined in the article).</div><div><br></div><div>Thanks,</div><div>Vladmir</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Mar 24, 2018 at 10:40 AM, Andy Fingerhut (jafinger) <span dir="ltr"><<a href="mailto:jafinger@cisco.com" target="_blank">jafinger@cisco.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">





<div lang="EN-US" link="blue" vlink="purple">
<div class="m_-6344401123669537100WordSection1">
<p class="MsoNormal"><span style="font-size:12.0pt">Thanks for the comments, Vladimir.  I agree with just about every word, and would be happy to incorporate your comments into it, perhaps in another week or so after I get some other things done.<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt">One quick response here.  The article does not say that algorithmic TCAMs are not “fast”.  It says: ‘All techniques I am aware of here either cannot go "fast" as defined above, or have capacity that is dependent
 upon the contents of the table entries.’.  If you know of an algorithmic TCAM method that is both fast _and_ has capacity independent of the contents of the table entries, then I really want to hear about it.  I’ve spent way too much of my life dealing with
 the non-deterministic capacity of algorithmic TCAMs, for Cisco platforms where they wish they could claim the capacity was a fixed number N.<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt">Thanks,<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt">Andy<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt"><u></u> <u></u></span></p>
<div style="border:none;border-top:solid #b5c4df 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b><span style="font-size:12.0pt;color:black">From: </span></b><span style="font-size:12.0pt;color:black">Vladimir Gurevich <<a href="mailto:vag@barefootnetworks.com" target="_blank">vag@barefootnetworks.com</a>><br>
<b>Date: </b>Saturday, March 24, 2018 at 9:06 AM<br>
<b>To: </b>"Andy Fingerhut (jafinger)" <<a href="mailto:jafinger@cisco.com" target="_blank">jafinger@cisco.com</a>><br>
<b>Cc: </b>p4-design <<a href="mailto:p4-design@lists.p4.org" target="_blank">p4-design@lists.p4.org</a>><br>
<b>Subject: </b>Re: [P4-design] Maybe too much text describing issues around P4 table and parser value set sizes<u></u><u></u></span></p>
</div><div><div class="h5">
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal"><a name="m_-6344401123669537100__MailOriginalBody">Hi Andy, <u></u><u></u></a></p>
<div>
<p class="MsoNormal"><span><u></u> <u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span>Great stuff, worthy of a book chapter or an encyclopedia article.<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span><u></u> <u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span>If anything, I'd just say that some of the assumptions are a little "rosy" meaning that they cover the "classic" behaviors, but do not account for a variety of idiosyncratic behaviors that are
 often encountered in real life. Call them bugs, features or both, but they do have an effect on table capacity. One big topic you sort of omitted is the question of how to count default actions: are they entries or not? do they need to be included in total
 entry count or not (i.e. should the "natural" size be 2^N, 2^N-1 or 2^N+1)? Even in "good" cases, such as TCAMs or indexed tables, I am sure that different implementations will answer this question differently. In other cases control plane might need to reserve
 additional entries for a variety of technical/efficiency reasons (faster entry moves in TCAMs, atomic updates, garbage collection (in action profiles), etc.). <u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span><u></u> <u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span>Therefore, people usually advertise their table capacities as being "up to N entries", with that "up to" being the key, that allows customers to reasonably judge the device capacity, while freeing
 the vendors from frivolous lawsuits :)<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span><u></u> <u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span>I know, there are different opinions in this area (mostly guided by (a) the n-to-1 case you described and (b) the fact that SW implementations might not need size indication at all), but coming
 from the ASIC background, I firmly believe that the basic "up to" size attribute is vital for both tables and value_sets and is preferred to an annotation, because it expresses a basic intent of the data plane program designer that the compiler cannot reasonably
 guess (as opposed to many technical allocation parameters (e.g. the number of ways in a hash table) that the compilers can determine automatically, often even better than humans). P4_14 even has min_size and max_size attributes in addition to size and I think
 that was not a bad idea (although I am not sure if they were implemented anywhere). <u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span><u></u> <u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span>Last, but not least, I am not quite sure what to make of the comment at the end of the article that assert that ATCAMs are not "fast". I think everything depends on the implementation, but if
 you can implement a multi-way hash table with O(1) lookup performance, there is no reason why you can't implement an ATCAM with the same performance either. <u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span><u></u> <u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span>Happy hacking,<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span>Vladimir<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span><u></u> <u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span><u></u> <u></u></span></p>
</div>
</div>
<div>
<p class="MsoNormal"><span><u></u> <u></u></span></p>
<div>
<p class="MsoNormal"><span>On Fri, Mar 23, 2018 at 9:49 PM, Andy Fingerhut (jafinger) <</span><a href="mailto:jafinger@cisco.com" target="_blank"><span>jafinger@cisco.com</span><span></span></a><span>>
 wrote:<u></u><u></u></span></p>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<div>
<p class="MsoNormal"><span>In the last P4 language design WG meeting, I volunteered to write up some notes on P4 table sizes, and what “size” might mean.<u></u><u></u></span></p>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
<p class="MsoNormal"><span>I have written up a discussion of the issues around P4 table and parser value set sizes here.  It is more a tutorial style directed
 at people who might be unfamiliar with issues around high speed implementations of P4-style matching, and what their consequences are for specifying table sizes, especially ones where the actual capacity of a table is not really predictable.<u></u><u></u></span></p>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
<p class="MsoNormal"><span></span><a href="https://github.com/jafingerhut/p4-guide/blob/master/docs/p4-table-and-parser-value-set-sizes.md" target="_blank"><span>https://github.com/<wbr>jafingerhut/p4-guide/blob/<wbr>master/docs/p4-table-and-<wbr>parser-value-set-sizes.md</span><span></span></a><span><u></u><u></u></span></p>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
<p class="MsoNormal"><span>Corrections/questions/comments welcome.<u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="color:#888888"> <u></u><u></u></span></span></p>
<p class="MsoNormal"><span><span style="color:#888888">Andy<u></u><u></u></span></span></p>
<p class="MsoNormal"><span><span style="color:#888888"> <u></u><u></u></span></span></p>
</div>
</div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><span><br>
______________________________<wbr>_________________<br>
P4-design mailing list<br>
</span><a href="mailto:P4-design@lists.p4.org" target="_blank"><span>P4-design@lists.p4.org</span><span></span></a><span><br>
</span><a href="http://lists.p4.org/mailman/listinfo/p4-design_lists.p4.org" target="_blank"><span>http://lists.p4.org/mailman/<wbr>listinfo/p4-design_lists.p4.<wbr>org</span><span></span></a><span><br>
<br>
<u></u><u></u></span></p>
</blockquote>
</div>
<p class="MsoNormal"><span><u></u> <u></u></span></p>
</div>
</div></div></div>
</div>

</blockquote></div><br></div>