Obtain all possible outputs generated by ActionSelector group members with single input packet

[Hoooao]

ActionSelector helps to define a mapping from table keys to action groups, and uses a designated hash algorithm to choose one action member from the matched group.

This issue tries to propose a way to have all the members of a matched group be applied and obtain the set of output results for analysis.

Having all members in a matched group applied is beneficial for several reasons. One of them is diff testing, where we use BMv2 to check the validity of the deployed ActionSelector behaviors.

There are 2 approaches:

• Concolic Testing: use constraint solvers to generate concrete test cases that go through all the paths created by selectors.
• A new replication engine: for a given selector, replicate N packet headers where N is the number of members of the matched group. Reassemble the headers and "resubmit" them to the gress that the selector resides in, but we have them starting from the control flow node (table) they get replicated.

We choose the second one by instrumenting the BMv2 source code instead of making an automated tool following the first approach for 3 reasons:

• Instrumenting the code is much simpler and localized to a few components of BMv2.
• Hash introduces challenges to solvers: solving for an input is non-trivial when the hash algorithm is complex.
• Performance could be an issue for the solver as the number of possible outputs grows exponentially as the number of selectors increases.

Here is an overview of how it works (we focus on ingress for now):

1. When a header reaches a selector, it will be replicated N times, where N is (the number of members in the matched group - 1).
2. The original header will be processed as usual. For each replicated header, the next_table after applying its specific action will be associated with it. They will be stored in a singleton vector.
3. Then the replicated headers will be reassembled using deparser and pushed to the ingress buffer with the highest priority.
4. One by one, they are pushed to the parser as if they are new input headers.
5. Upon getting processed by the pipeline, the next_table will be used as the starting control flow node(table), instead of starting from the initial table defined in the program.

[jafingerhut]

I may be misunderstanding something, but you need to replicate not only the headers, but also the state of all metadata variables, too, yes? That should certainly be possible with appropriate modifications to BMv2 code, of course.

Also, I am fairly sure it would be best to skip the parsing for replicated packets, because by the time the packet reaches an ActionSelector that causes it to be replicated, an arbitrary subset of its header field values may have been modified, new headers may have been setValid(), parsed headers may have been setInvalid(), etc. Any such changes should be captured by making copies of all metadata variables, mentioned above, but repeating parsing could undo those changes. I think you really want the packet to jump straight to the next node, without parsing again.

[jafingerhut]

Also, looking at your figure, the replicated packets should not execute the deparser, either, in addition to not executing the parser.

In general, you want a "snapshot" of what the current packet processing state looks like at the time the table with the action selector is applied (before executing the action that the action selector refers to), and to continue the processing of each replicated "snapshot" at the same point where it left off, with the only difference between them being which group member was selected.

[Hoooao]

Also, looking at your figure, the replicated packets should not execute the deparser, either, in addition to not executing the parser.

In general, you want a "snapshot" of what the current packet processing state looks like at the time the table with the action selector is applied (before executing the action that the action selector refers to), and to continue the processing of each replicated "snapshot" at the same point where it left off, with the only difference between them being which group member was selected.

Thanks for the suggestions. You are absolutely correct.
The use of parser/deparser was for maintainability, where I did not want to modify the existing processing logic in the "ingress_thread" as it is hard to take care of all the states that get manipulated. Yet I did not notice, and thanks for pointing out, that the pardes also have side effects on states.
And yes, I will add a snapshot mechanism to take care of the states.

[Hoooao]

Updated diagram

[qobilidop]

CC @matthewtlam @jonathan-dilorenzo for this discussion.

[github-actions]

This issue is stale because it has been open 180 days with no activity. Remove stale label or comment, or this will be closed in 180 days

[fruffy]

@Hoooao What's the status here?