New match kind: set

[stefanheule]

Personnel

• Owner: @stefanheule
• Supporters: @jafingerhut

Design

• Document: See below; also https://github.com/jafingerhut/p4-guide/tree/master/match-kinds

Implementation

• p4-spec:
• p4c:

Process

• LDWG discussed:
• LDWG approved:
• Merged into p4-spec:
• Merged into p4c:

I would like to propose set as a new match kind. It matches exactly against a set of values.

A common example I envision set to be used for is to match on a set of ports, for instance to drop all traffic from a given set of ports. Because the total number of ports is usually relatively small, this match can be implemented efficiently as a bitmap. This allows the control plane to use a single table entry to match on n ports, instead of having to use n exact matches, which means less resource usage.

[jnfoster]

Hi @stefanheule. Nice addition! However, in P4_16, architectures are free to define their own match-kinds. Is the proposal to add this to core.p4?

[cc10512]

I'm not sure that the "less resource usage" is a valid argument. Just as range, implementing set may require the compiler to insert table entries for each of the set values. I can see the convenience from the P4 perspective, certainly, so I am not arguing against the proposal, especially because, as @jnfoster pointed out, match kinds are extendable even outside the core language.

[stefanheule]

Some compiler backends might choose to implement it that way, in which case there really is no benefit. However, a more sophisticated backend could implement it using a bitmask. For my port example, the TCAM would match on a bitmask where every port gets one bit. So if you wanted to match on any packet coming in on ports 1, 3 and 17, you would match on a value that has the 1st, 3rd and 17th bit set. This means you can reduce the number of TCAM rows you need by a factor of n when you match on n items. A single row will be a little wider (since you need a bit per port), but for values with not too many distinct values (e.g. 32 different ports), that's not so bad, and overall definitely a win.

[cc10512]

@stefanheule are you expecting the compiler to generate the encode/decode tables that map the set values to bits and the ternary match table? If so, what are the limitations of such an approach? Do you need to know all the values of the set at compile time? Can you support dynamic sets with a bound on the range of values? If the latter, how are the entries in the ternary table inserted?

It might be best to discuss the proposal in the language design group, however, it seems there are enough questions (and interest) that you may want to provide experimental evidence on how realizable this is in practice under the hood vs. having the P4 programmer do it explicitly.

[jafingerhut]

For anyone considering implementing the set match_kind in the open source P4 development tools and v1model architecture, I have collected together a list of pull requests that implement the simpler optional match kind here: https://github.com/jafingerhut/p4-guide/tree/master/match-kinds

I would expect the changes to implement set to be more complex than those, as described briefly at the end of that article.

[stefanheule]

To say a little more, in yesterdays LDWG we decided to move forward with this proposal and add it to v1model for now, and in the future consider promotion to the standard library once it has proven itself and people agree this would be good to have in the language.

As Andy points out, there are going to be a number of projects that require changes, if someone would like to tackle any of them please let me know. Otherwise I will try to find someone to take on these changes.

Concretely set will be available for any field of type bit<w> (or a type type, which is declared as a bit<w>), and different backends will likely implement this differently. A common implementation will be as a bitmask with one bit per possible element in the set, i.e. a bitmask of width 2^w. As with other aspects in the language, this won't work for types that are too large, and given the exponential, w has to be quite small in practice for this to work. For instance for ports one might use w=8, which is doable on many hardware platforms.

[jnfoster]

This proposal seems interesting but has stalled for now. Feel fee to resurrect if someone wants to drive it!