Tuple Space Search implementation for BMv2

[jafingerhut]

Motivation: There are some people using BMv2 for executing a P4-based reference model for packet processing behavior for the DASH project. Some of them have experienced issues where tables with ternary keys cause the packet processing rate to go very low when the table has tens of thousands of entries, because BMv2 currently performs a linear search for every packet through all entries, in priority order.

Tuple Space Search is implemented in OVS, and for the common case when the number of unique masks in the set of all table entries of a ternary table is much smaller than the number of entries, it can provide very good matching performance. More details in this BMv2 issue:

• Consider implementing something like Tuple Space Search for ternary table lookups p4lang/behavioral-model#1260

As of 2024-Sep-16, Davide Scano indicated an interest in working on this enhancement, so please talk to him if you are interested.

[jafingerhut]

Closing since all issues have been copied to this repo: https://github.com/p4lang/project-ideas/issues