DSL: Allow custom scheduling policies

[anshumanmohan]

Low on the list of priorities, but it would be nice to allow users to write down policies of their own so that they don't just need to mix and match from a limited menu of policies.

I am totally comfortable with this roll-your-own-policy mechanism being ergonomically gross/unwieldy! It's sorta the "advanced mode" choice that a user could make. In effect the user is directly writing the scheduling policy for a particular node.

We may need to set up some state for the node, and then this scheduling policy may need to maintain that state and assign ranks to packets. Yet another advanced move would be supporting NWC algorithms. And in the end, the user-created policies would be intermixable with the other "library" policies that we provide.

I suggest we start quite small and then ramp up. I imagine we'll want some kinda of meta DSL that is just used for policy-definition. Let's see if we can write really simple things like FIFO or RR using that meta language; the benefit is that we can compare the two implementations to see if we got it right. Then we can get into WC algorithms that are not strictly from the library, and finally we can explore NWC algorithms.

[anshumanmohan]

Just jotting down some thoughts from an IRL chat with @csziklai.

I am pretty sure the user wants to write a Sivaraman-style scheduling policy that grants a packet a rank, not a Formal Abstractions-style scheduling policy that grants a packet a path. The user is, after all, just trying to describe one node, not a whole (sub)tree.

So the meta-DSL needs to help the user define a function having the signature:

$$state \rightarrow pkt \rightarrow rank * state$$

The need for $state$ is relatively clear; for more sophisticated policies the user will want to maintain some notion of memory. The user will also need to update the state while granting the present rank, which is why there is a state in the output too. Also, as I alluded to in the post above, the user will probably want a chance to set up the state with some values as a one-time startup thing. I have left $rank$ opaque but think of it as float if you want.

We can study the examples currently in alg.ml to see what kinds of hijinks people usually get up to when defining policies. This is useful because, in a manner of speaking, the role of our meta-DSL is to ease the life of any user who is trying to write new policies in that style. For a taste of something familiar, you can see scheduling transactions for simple things like FIFO, RR, Strict, etc., being defined near the top of that file. A caveat there is that those scheduling transactions are in the Formal Abstractions style, so they are obeying the signature $state \rightarrow pkt \rightarrow path * state$.

A bit of a mind-bender here is that the scheduling transaction that our user writes will need to deal in packets, which our DSL has so far swept under the rug.