In source IP address filtering, a common data structure is the lookup tree, also known as a trie (up to 32 levels), which is easily implemented on software switches.
However, it seems that there is no similar structure in the P4 language, with tables being the most frequently used construct.
I have the following questions:
How can a trie be implemented in P4?
Is it possible to use devices like SRAM or registers to store the trie and then implement the trie lookup logic in the ingress control?
If the second question is feasible, does every lookup operation in the trie consume a processing stage (given my understanding that there is a limit to the number of processing stages)?
If you mean “how can I implement a longest-prefix match table in P4”, then the answer is to use a table where the match_kind of the relevant field, e.g. IPv4 destination address, is lpm. The implementation should pick whatever implementation it has that is appropriate, which could be any of dozens of longest-prefix match algorithms, implemented in hardware and/or software. A trie is just one of those dozens of ways.
Thank you for your response. In fact, I am considering reproducing a filtering scheme that vertically distributes the lookup tree nodes to different switches. In simpler terms, each switch is responsible for a certain portion of the IP address’s bits. In this scenario, the ingress filter switch can use LPM, but a combination of ternary and LPM might be more suitable for subsequent switches. So, how can this lookup tree structure be implemented using P4? Alternatively, if P4’s match type can be defined as a combination of ternary and LPM, that would also work，I think.
It is not clear to me how there is any benefit you can achieve from having a single table with both ternary and lpm fields in the key. Feel free to describe the kind of match behavior you hope to achieve with such an approach, but pretty much in the definition of ‘lpm’ is LONGEST prefix match, i.e. the longer the prefix, the higher its match priority. Ternary requires that the control plane software that adds the entries must specify a numeric relative priority for every entry installed, with no notion of a prefix length involved. Those cannot be mixed in any P4 implementation that I know about.
You could certainly have on P4 program running in one switch that does a single lpm lookup, or a single ternary lookup, with the IP dest address as the key, and the result tells you which of several next switches to go to that can “finish the lookup”, if I understand correctly what you are hoping to do. That final lookup seems most appropriate to be ‘lpm’ to me, but you may be thinking of partitioning the prefixes in a different way between switches than I am imagining.
Thank you! The priority you mentioned has given me some insights. LPM indeed is the most suitable approach, so I’ve come up with the idea of combining ternary and priorities to achieve LPM’s effect.