[P4-dev] search in p4 tables

Antonin Bas antonin at barefootnetworks.com
Mon Jul 17 17:16:48 EDT 2017

As Nate wrote, if you only have one or two tables in your P4 program, they
will probably not be the bottleneck.

To answer your question though:
1) exact match tables are implemented using hash tables and the lookup time
doesn't depend on the number of entries N
2) LPM tables are implemented using some kind of trie and lookup time also
should be mostly independent of N
3) ternary and range tables are implemented using a linear search and
lookup time is in O(N). However, I use a hash table cache ahead of the
lookup table, which means that packets belonging to the same "flow" will be
processed in constant time, only the first packet of the flow will incur a
linear search through the table. By "flow" I mean all the packets for which
the header fields used in the table match key have the same value.

On Mon, Jul 17, 2017 at 12:40 PM, Nate Foster <jnfoster at cs.cornell.edu>

> Use the source, Luke :-)
> https://github.com/p4lang/behavioral-model/blob/master/
> src/bm_sim/lookup_structures.cpp
> It's hard to say why without knowing more about the setup used to drive
> your experiments, but it may well be that table lookup time is negligible
> compared to all the other overheads inherent in processing packets using a
> (largely unoptimized) software switch.
> -N
> On Mon, Jul 17, 2017 at 12:18 PM, Wallas Fróes <wallasync at gmail.com>
> wrote:
>> Hi
>> Someone know to informe me what is the search algorith used for the
>> simple_switch?
>> I am realizy some tests and when I use few rules the rtt time is equal
>> when I use the table full.
>> Someone know the why of that it?
>> --
>> Att,
>> Wallas Fróes
>> Student of master degree in the PGCOMP (UFBA)
>> Information Security in Computer Networks
>> Computer Engineer
>> Cel: (77) 98841-0762
>> _______________________________________________
>> P4-dev mailing list
>> P4-dev at lists.p4.org
>> http://lists.p4.org/mailman/listinfo/p4-dev_lists.p4.org
> _______________________________________________
> P4-dev mailing list
> P4-dev at lists.p4.org
> http://lists.p4.org/mailman/listinfo/p4-dev_lists.p4.org

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.p4.org/pipermail/p4-dev_lists.p4.org/attachments/20170717/181ad16b/attachment-0002.html>

More information about the P4-dev mailing list