Hierarchical Policies People are Interested In

[csziklai]

Some compositions of policies simply do not make sense, or behave in unintuitive ways when composed in a hierarchical manner. Once such is the EDF example given in #51. The question that this discussion will explore is what parent-child policies make sense? Unfortunately there did not seem to be much literature available on the subject, so it was hard to get a good idea of what policies people in the field are interested in composing as trees. Nevertheless, I found relevant research and the following example policy from Zhang et. al. in vPIFO: Virtualized Packet Scheduler for Programmable Hierarchical Scheduling in High-speed Networks.

At the root is a strict queue with two WFQ children, one of which has a strict queue for one of its children. Drawn more abstractly, it is

Intuitively, this policy makes sense. We want to strictly prefer one of the WFQs (labeled X and Y in Figure 1) over the other. WFQ Y in turn manages packets from A while it still has flow (if not then B) and C.

As I mentioned in meeting, this paper does closely related work to us. It defines a scheduler description language (SDL) to specify the policies a user wants to compose. They draw from Sivaraman et al.’s idea of orchestrating multiple connected PIFO queues to form a tree, but instead opt for a single physical PIFO that is virtualized.

Another example, that looks a bit funky compared to what we have been considering more abstractly, comes from the LOOM paper Stephens et. al. The WFQ in (1) handles the competing flows from Big Data and SQL Analytics. These are the leaves, equivalent to classes like A, B, C in Rio. In this paper, Pri is equivalent to Strict. There is a FIFO that orchestrates N Dst Rate-Limits. This hierarchy generalizes to N VMs which are each a child of WFQ (4). For more details, see (§)2.1. As we can see, real life policies can be quite complex and large.

Another paper I mentioned was Hierarchical Policies for Software Defined Networks, Ferguson et. al. While specifying how to resolve conflicts in hierarchical policies, I believe they imagine policy trees at the level of those who manage networks such as network administrators and their deputies. So perhaps the delegation of a hierarchy of authority in decision-making. And of course, our research is not involved with match action tables but I thought I’d include some findings from the paper that may be of interest. “When independent parts of the tree arrive at conflicting decisions, HFT resolves conflicts with user-defined conflict-resolution operators, which exist at each node of the tree.” HFT, or Hierarchical Flow Tables, is the framework they present for specifying hierarchical policies.

They translate policy tables to network flow tables (match action table essentially?). Still the discussion of what counts as a “policy” is kept vague/not specified, so maybe the idea can be transferable to our context? Anyways, they define conflict-resolution operators that resolve conflicts, such as those between parent and child. For example, a conflict resolution could be “child overrides parent”. The operator (+) is a function from action -> action -> action.

Thus, based on this research, it would seem that WFQ and Strict are popular policies to be composed together hierarchically. I regret not being able to find more information on this topic. In regards to the problem of how to handle hierarchical policies that have conflicting parents/children, I think it should be based on the way the compiler naturally reads the policy and have it be on the user for specifying a nonsensical policy. Or at least that might be the easiest way to deal with it.