PIFO Trees for real

[anshumanmohan]

Lay of the land

1. Mittal et al. at NSDI '16: There is no universal scheduling algorithm.
2. Sivaraman et al. at SIGCOMM '16: For hierarchical policies, a PIFO is not good enough. Build a PIFO tree instead.
3. Mohan et al. at OOPSLA '23: Building a $d$-ary branching PIFO tree is good enough. Make it as expressive as you can afford to: taller trees are more expressive and wider trees are more expressive, but it's not clear how best to spend your budget.
4. What's actually on Tofino: A set of $n$ FIFOs that we can orchestrate.

TODO: look into what basic building blocks other programmable switches have.

5. Alcoz et al. at NSDI '20: Orchestrate those $n$ FIFOs to approximate a PIFO (just a PIFO queue, not a PIFO tree).
6. Kim, Li, et al.: A Calyx implementation of a binary-branching PIFO tree of any height, but one that is only able to do fairness.

Room for improvement

1. No one since Sivaraman et al. has proposed custom hardware. Sivaraman et al. sketch a fully-connected mesh of PIFOs that can then be marshaled into trees. There is no implementation.
2. Alcoz et al. have a throwaway line about PIFO trees, but that involves recirculating packets.
3. Given a realistic treatment of hardware resources, there isn't one single PIFO tree to put on all switches; there's a spectrum of trees that are incomparable in terms of expressivity.

A PIFO primitive

• The main issue with Kim, Li, et al.'s PIFO tree is not that it's binary, but that its only policy is fairness. This limitation comes from its PIFO.
• We need a true PIFO with state, an arbitrary ranking function, and possibly an arbitrary popping function.

This need is really crucial. Say we limit our goal to "fair policies of one shape being run against a tree of another shape". This allows us to use our baby Calyx tree as the source tree. However, this isn't really a win: we still need a general PIFO with state for the tree that's actually in the hardware. This is because the compiled version of the tree may need a true PIFO with state in order to simulate the user's fair policy; c.f. my ternary-to-binary compilation "fail" example.

• Can we build a perfect PIFO as a Calyx primitive?
  • What makes us think we can do better than Alcoz et al.?
  • While we won't literally be orchestrating the FIFOs exposed by Tofino, we will be orchestrating some simple things in Calyx.
  • Speaking of that simple thing, maybe a warm-up can be to have a Calyx FIFO primitive instead of doing it the way Kim, Li, et al. do it right now.
• Can we build an imperfect PIFO as a Calyx primitive?
  • Will we be any "less imperfect" than Alcoz et al. because we will have only two children?
  • Will we be "more imperfect" because of the magnifications of our tree structure?

Marshaling $n$ PIFOs

• Say the above works out, and we know we have $7$ PIFOs in our budget.
• It is unclear what "most expressive" tree to put on our hardware!
• Draw inspiration from Sivaraman et al.'s mesh, so that the best-possible tree can quickly be fashioned from a set of $n$ PIFOs?

More penny-pinching

• The observation is that every tier of the tree actually has the same number of items: $|t|$, the number of packets in the tree.
• Can we exploit this somehow? Can the root be a true PIFO with the luxury of its own memory, but then the next tier be two PIFOs that are sharing the same memory? Is this too wild?

[sampsyo]

We need a true PIFO with state, an arbitrary ranking function, and possibly an arbitrary popping function.

Just to record one notion from the synchronous discussion: it seems important to decouple two pieces of the generalized hardware.

1. The core structure, whose interface just consists of push-with-priority and pop.
2. The logic that chooses priorities. Maybe this involves looking at some packet fields and doing some computations on them to produce a priority number.

It's important to decouple of them because part 2 is so much less well defined. In the limit, it needs to be a tiny RISC-V core that does arbitrary computations to produce a number. So we just have to come up with something balancing generality with compactness. But part 1 is much better defined, and we can/should make it fully general with no compromises.

[anshumanmohan]

Surfacing a couple other things from our synchronous discussion!

Possible Outcome

Packet scheduling on SmartNICs. It has a single host with several VMs, so you need packet scheduling to manage the VMs' traffic. Now we can do this for real!

• The paper will be pretty low on novelty, but will actually build it out.
  • One piece of novelty would come from the software-hardware interplay: "We tried out x different PIFO trees given some resource constraint, and heuristically this is what we found."
• Keep the hardware and the compiler as simple as possible. Our wins will be more imperative. What is fast enough? What workloads do we need to support? What is sacred in the domain, and what is expendable? What policies do people care about? What are the performance objectives?
  • Questions about adding programmability would come later, guided by these lessons.
• To convince the community that we have built a solid system, we will need to interface with the AXI folks.
  • Study Praveen, Nate, et al.'s Neptune work.
  • What does the Alveo card have? Is it a serious piece of networking hardware? Looks like yes.
  • We could take some preliminary implementation, show it to Nate etc, and then ask them what they think. Are those numbers competitive in SIGCOMM etc?

Immediate next steps

• Without worrying about streaming packets to the FPGA one by one, just try to port over the present "batch mode" hack as it is. Look at the Calyx docs and talk to @nathanielnrn.
• Look at tutorials etc and learn how to stream on Alveo. At present we don't think anyone on the team is an expert.
• Instead of writing Verilog, use the P4 compiler to generate Verilog. This will just be a no-op program but it will be exactly the Verilog boilerplate that I will need to build atop of.
• Investigate what Sivaraman et al. do for the PIFOs in their implementation.