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

Vladimir Gurevich vag at barefootnetworks.com
Sat Mar 24 12:06:28 EDT 2018

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> 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.
> https://github.com/jafingerhut/p4-guide/blob/master/docs/p4-table-and-
> parser-value-set-sizes.md
> Corrections/questions/comments welcome.
> Andy
> _______________________________________________
> P4-design mailing list
> P4-design at lists.p4.org
> http://lists.p4.org/mailman/listinfo/p4-design_lists.p4.org
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.p4.org/pipermail/p4-design_lists.p4.org/attachments/20180324/ff9ed8c5/attachment.html>

More information about the P4-design mailing list