This discussion draws on https://github.com/orgs/calyxir/discussions/1818, but attempts to stand on its own. Feel free to refer to 1818 if you want further context!

Background

Programmable Packet Scheduling

The application we're interested in is efficiently scheduling flows of packets through networking hardware to prioritize different kinds of traffic. This is important in general because naively forwarding whatever traffic you receive indiscriminately – FIFO (first in, first out) – will inevitably lead to some kind of "unfairness" among different users of the network. For example, if one client is sending a lot of traffic and another is sending only a little, then a simplistic policy for balancing them would squeeze out the "light" client. It's possible to make better scheduling policies, but making these decisions fast enough requires custom hardware support: a CPU probably can't do this efficiently enough.

One important detail here is that there is no "one-size-fits-all" packet scheduling policy. Fairly balancing the traffic 50/50 between two clients is one thing, but you might want to change the ratio you allocate (maybe one person pays for better bandwidth, maybe you know something about the global network that informs your decision at a particular switch...), and other parameters are possible too. And importantly, you generally want to nest these policies into a hierarchy. Like, if you have 4 different flows A, B, C, and D that you want to balance between, you might want a "flat" policy that says:

divide_4_ways_fairly(A, B, C, D)

Or, you might want a "nested" policy built out of smaller policy-building pieces:

divide_2_ways_fairly(
  left_priority(A, B),
  divide_2_ways_fairly(C, D)
)

Here, imagine that left_priority(x, y) is a policy that always gives priority to x traffic and always de-prioritizes y traffic.

Anyway, this is all just to say that packet scheduling policies need to be programmable, and when they are programmable, it makes sense for that programming model to be hierarchal. That's why there are trees involved in the discussion below: trees express the hierarchy of different policies and the way they compose. This is also why there tree-shaped structures show up in the hardware we're building, to support those tree-shaped policies.

The PIFO Tree Data Structure

Sivaraman et al. have presented a new queueing data structure, the PIFO tree, which is a useful way to model hierarchical scheduling policies. In particular, PIFO trees allow the efficient reordering of previously buffered items in response to the entry of new items. Sivaraman et al. show that it is useful in a switch context, and we are exploring its applicability in the NIC context.

There exists no hardware implementation of PIFO trees on real switches. In fact, no switch even supports PIFOs (priority queues)! For an example of what is commercially deployed: Intel Tofino supports a bank of FIFOs along with logic to orchestrate which FIFO gets pushed into and which FIFO gets popped from.

In research-land, the closest proposals we have to hardware implementations are:

• Alcoz et al.: Orchestrate a bank of FIFOs to approximate a PIFO (just a PIFO, not a PIFO tree).
• Kim, Li, et al.: A Calyx implementation of a binary-branching PIFO tree of any height. This PIFO tree only supports one policy: fairness among siblings.

A large part of what makes this hard is speed: we need to operate "at line rate", which loosely means that our efforts at scheduling are not allowed to slow down the flow of traffic.

A Single Tree is Good Enough

It probably feels like we're really far away from real implementations! Thankfully Mohan et al. have shown that PIFO trees can be compiled from one shape to another. That is:

1. A user writes their scheduling policy using a PIFO tree of whatever shape they want.
2. We provision some single shape of PIFO tree on hardware.
3. We can compile the user's policy such that it runs on the tree available on hardware.

In the sketch below, the domain is the set of policies that users can define, and the codomain is the set of policies that we need to support.

Let's revisit the PIFO tree in Calyx. Suddenly, the fact that it is only binary-branching is totally okay. What is not okay is that we can only support a single simple policy, fairness. If we could provision a binary-branching PIFO tree with an arbitrarily programmable policy, we would be in a really good place: users would be able to write arbitrary policies against trees of arbitrary shape, and we would be able to handle them all.

Going back to the figure above, the present Calyx implementation occupies a tiny point in the codomain. We would like to extend the implementation so that it occupies more of the codomain.

An Arbitrary Policy is Probably Too Hard

We can try to expand the Calyx implementation to be more general, but truly arbitrary policies are probably going to impossible to support. Say we manage to expand our Calyx implementation some, represented by the blue subset in the codomain. Clearly the blue subset cannot support all user-written policies. Now an interesting question is, what kinds of policies in the domain can we support? What is the preimage of the blue oval, shown as a red oval?

A DSL For Programmable Scheduling

Eventually we would like to expose little to none of this to end-users. We would like a DSL that lets users express their scheduling policies, while limiting them to the set of shapes and policies that we can support (the red oval). We will then compile their policy down to our hardware implementation, where we will run it.