[P4-dev] table questions

Mihai Budiu mbudiu at barefootnetworks.com
Tue Jul 28 13:48:08 EDT 2015

I believe that Chang's answer summarizes the current P4 view of tables very

Let me elaborate a little on this.

In P4 tables are abstract finite maps from keys (i.e., tuples of type K) to
actions of type A (each table only allows
a specific set of actions; you can think of A as being a "union" of all
allowed actions). Such a map supports a single operation from the P4
data-plane point of view, which is lookup(K) -> A?, where given a key of
type K you return an action from A or "miss". There can be many
IMPLEMENTATIONS of such maps (more on this below).

Given this view of the world, for your 4 questions, the answers are the
* there is no way you can insert an entry in a table in P4. This is a
control-plane-only operation. I will discuss this more thoroughly below.
* same observation applies; see below about table sizes.
* a default-action is not in the table at all; it is "next" to the table,
and is executed if "lookup" returns "miss". The default action is part of
the match-action computation specification.
* in the P4 spec the values in a table are all actions from the set of
allowed actions A. Actions can contain some "parameters". P4 has no real
support for variable-length datatypes (e.g. lists). So the state in a table
value is whatever can be stored in the action parameters - or, more
precisely, a union of all action parameters. Since it's a union, you do
have a choice from multiple sets of parameters, but all such choices have
fixed compile-time known sizes.

Now, talking about table implementations, P4 supports many types of table
implementations: hash tables, ternary tables, LPM tables (which are special
cases of ternary tables), and it should also support other table types that
are used in the industry, such as arrays (direct maps), tries, etc. The
nice thing about all these tables is that they all provide a "lookup"
functionality. The way you manage entries in all these tables depends on
the table implementation. This is today only exposed to the control-plane,
so it is not part of the P4 specification.

For example, if your table is an array, it's capacity is fixed. But if your
table is a hash-table, then the number of entries that can fit in the table
is not even a fixed quantity: your hash will be full when you have
collisions that you cannot resolve. You may have a hash table with room for
50 entries, but you may be unable to fit more than 40, for example,
depending on actual keys that you are using.

Insertion in an array is just "overwriting" an entry. There you cannot have
two entries with the same key. However, in certain ternary table you MIGHT
have entries with the same "key", or with overlapping "keys", if they have
different priorities. (E.g., you can have both 1.0.0.* and In
fact, the entries in a ternary table are not described by keys from the set
K - the one used for lookup, they are described by "cubes" that are
subspaces of K (e.g., 10.0.0.* represents 255 different keys).

This is the core reason why P4 separates table lookup (which can be done in
the same way for all tables, no matter what the implementation), and the
table management (which is done in the control-plane, and is
implementation-dependent). The benefit is that P4 programs should be able
to run even on architectures that have some exotic table types that no-one
has thought about when writing the P4 spec (such as tries, for example).
This should also allow a wide variety of control-plane implementations,
including open-flow-based.


On Mon, Jul 27, 2015 at 6:15 PM, Changhoon Kim <chang at barefootnetworks.com>

> In general, the semantics of table add and update operations, including
> the exception semantics of those operations, are relevant to the network
> control plane, but not to data plane. Hence, P4 -- as a network data-plane
> description language -- doesn't really dictate table update behaviors.
> Various control-plane protocols and approaches (including OpenFlow) can
> employ their own best table-management designs, and P4 remains neutral to
> those differences.
> -- Chang
> On Mon, Jul 27, 2015 at 12:41 PM, Ben Mack-Crane <ben.mackcrane at corsa.com>
> wrote:
>> In OpenFlow (which might be used as the run-time control protocol for a
>> P4-defined pipeline) there are a few options:
>> A flow_mod message can request to *add* or *modify* a table entry.If the
>> request is to add an entry and an entry with the same key (match condition)
>> already exists in the table the add fails and an error is returned.  If a
>> modify is requested and an entry with the same key is found in the table
>> that entry's action is replaced.  If a modify is requested and no matching
>> entry exists the request is silently ignored.
>> As LJ notes, there are other behaviors possible as well.  I am just
>> mentioning those currently defined in OpenFlow (looking at OF1.5).
>> As for adding the N+1st entry in an N entry table, in OpenFlow the
>> default is to fail the add request and return an error.  There is an option
>> to allow the switch to evict an entry of lower importance to make room for
>> the new entry.  Along with the eviction option bounds on available space in
>> the table can be set to generate notifications to the Controller when the
>> free space crosses a threshold (either getting smaller or larger).
>> Regards,
>> Ben
>> On Sun, Jul 26, 2015 at 11:32 AM, LJ Wobker <ljw at barefootnetworks.com>
>> wrote:
>>> Generally if you insert a new key it overwrites the existing one.  Keys
>>> are assumed to be unique.  I suppose you could design your target/API to
>>> have a different behavior, but I think the majority of use cases (think
>>> “updating routing information in the FIB”) are best served by the
>>> overwrite-if-exists semantic.
>>> The API will (or at least “should”) throw an error if you try to insert
>>> N+1 elements into a table of size N.  Again, I suppose you COULD write a
>>> target/API that behaves differently…
>>> The way the language is structured is that if you need to add headers to
>>> a packet, you need to have those headers represented in the parse graph, so
>>> that when the packet is deparsed to the wire you have that path in the
>>> parse tree.  So while you have have “different headers with varying
>>> lengths” you can’t really have “variable length headers”.  The parse tree
>>> must land on a node that has a fixed length.
>>> To do TLV type processing, you’d have to represent the length (generally
>>> by a branch based on the type) somewhere in the parse greph.
>>> --lj
>>> *From:* P4-dev [mailto:p4-dev-bounces at p4.org] *On Behalf Of *brian
>>> fiegen
>>> *Sent:* Sunday, July 26, 2015 4:48 AM
>>> *To:* p4-dev at p4.org
>>> *Subject:* [P4-dev] table questions
>>> I have a few questions about tables:
>>>    - suppose one inserts a <key1, value1> into a table and then at some
>>>    point in the future inserts a <key1, value2> into the table.  Does this
>>>    operation result in both entries in the table?  Or the most recent one?  Or
>>>    is the result of these operations unknown?
>>>    - if one defines a table to be of size 50 and there are 50 elements
>>>    in the table and 51st unique element is added to the table, what
>>>    happens?Does an error get returned and the 51st element isn’t inserted?
>>>    Does one of the existing elements get randomly picked and removed to make
>>>    room?
>>>    - Does a default table action consume a spot in the table?
>>>    - Is it possible to insert into a table a “value" which has variable
>>>    length?   Basically I’m thinking of this “value” as being a sequence of
>>>    bytes that are a header to be inserted into the packet.    What would be
>>>    the mechanism to reference and process this variable length byte sequence
>>>    on the action side?
>>> Thanks
>>> _______________________________________________
>>> P4-dev mailing list
>>> P4-dev at p4.org
>>> Listinfo - http://mail.p4.org/mailman/listinfo/p4-dev_p4.org
>>> Archives - http://mail.p4.org/pipermail/p4-dev_p4.org/
>> _______________________________________________
>> P4-dev mailing list
>> P4-dev at p4.org
>> Listinfo - http://mail.p4.org/mailman/listinfo/p4-dev_p4.org
>> Archives - http://mail.p4.org/pipermail/p4-dev_p4.org/
> _______________________________________________
> P4-dev mailing list
> P4-dev at p4.org
> Listinfo - http://mail.p4.org/mailman/listinfo/p4-dev_p4.org
> Archives - http://mail.p4.org/pipermail/p4-dev_p4.org/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.p4.org/pipermail/p4-dev_lists.p4.org/attachments/20150728/55c85f3f/attachment-0001.html>

More information about the P4-dev mailing list