[P4-design] Maybe too much text describing issues around P4 table and parser value set sizes

Andy Fingerhut (jafinger) jafinger at cisco.com
Sat Mar 24 20:10:23 EDT 2018

If by “up to N” you mean “up to N with high probability”, or “up to N for most practical sets of keys you probably want to install”, yes that is what I was trying to convey in the article for hash tables.  I wasn’t trying to say that ATCAMs are any worse than hash tables in that regard (although some variations I have worked with _are_), just that they are no better in them, either.


From: Vladimir Gurevich <vag at barefootnetworks.com>
Date: Saturday, March 24, 2018 at 4:36 PM
To: "Andy Fingerhut (jafinger)" <jafinger at cisco.com>
Cc: p4-design <p4-design at lists.p4.org>
Subject: Re: [P4-design] Maybe too much text describing issues around P4 table and parser value set sizes

Hi Andy,

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).


On Sat, Mar 24, 2018 at 10:40 AM, Andy Fingerhut (jafinger) <jafinger at cisco.com<mailto:jafinger at cisco.com>> wrote:
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.

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.


From: Vladimir Gurevich <vag at barefootnetworks.com<mailto:vag at barefootnetworks.com>>
Date: Saturday, March 24, 2018 at 9:06 AM
To: "Andy Fingerhut (jafinger)" <jafinger at cisco.com<mailto:jafinger at cisco.com>>
Cc: p4-design <p4-design at lists.p4.org<mailto:p4-design at lists.p4.org>>
Subject: Re: [P4-design] Maybe too much text describing issues around P4 table and parser value set sizes

Hi Andy,

Great stuff, worthy of a book chapter or an encyclopedia article.

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.).

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 :)

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).

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.

Happy hacking,

On Fri, Mar 23, 2018 at 9:49 PM, Andy Fingerhut (jafinger) <jafinger at cisco.com<mailto:jafinger at cisco.com>> wrote:
In the last P4 language design WG meeting, I volunteered to write up some notes on P4 table sizes, and what “size” might mean.

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.


Corrections/questions/comments welcome.


P4-design mailing list
P4-design at lists.p4.org<mailto:P4-design at lists.p4.org>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.p4.org/pipermail/p4-design_lists.p4.org/attachments/20180325/cafc88bd/attachment-0001.html>

More information about the P4-design mailing list