[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 19:36:54 EDT 2018


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

Thanks,
Vladmir

On Sat, Mar 24, 2018 at 10:40 AM, Andy Fingerhut (jafinger) <
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.
>
>
>
> Thanks,
>
> Andy
>
>
>
> *From: *Vladimir Gurevich <vag at barefootnetworks.com>
> *Date: *Saturday, March 24, 2018 at 9:06 AM
> *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,
>
>
>
> 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,
>
> Vladimir
>
>
>
>
>
>
>
> 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/72eae036/attachment.html>


More information about the P4-design mailing list