Agree on the workings of Round-Robin

[polybeandip]

There's some ambiguity in the glossary's definition of round-robin: namely, what do we when a class falls silent?

Let's focus on the policy rr[A, B]. Consider the following scenario:

• Suppose we receive the packet sequence B_1, B_2, B_3 before any pops
• Then, we perform one pop
• Then, we receive a single packet A_1

Would flushing our associated PIFO tree result in

flush-1: A_1, B_2, B_3

or

flush-2: B_2, A_1, B_3

In other words, do skipped classes get to save their turn? This is the crux of this discussion.

According to @csziklai's n-flow, RR-PIFOs in Calyx, skipped classes lose their turn: i.e. flushing yields flush-2. However, @anshumanmohan's 2-flow, RR-PIFO in Calyx and ternary tree, RR-control in pifo-tree-artifact disagree: flushing on his implementations give flush-1.

Is everyone is in favor of shifting all our round-robin implementations to @csziklai's approach? Stealing @anshumanmohan's comment, this would mean our policy is:

• Start with some hot pointer.
• In an infinite loop:
  • If our tree is non-empty, pop from the flow pointed to by hot.
    • If it succeeds, increment hot and return the result.
    • If it fails, increment hot and continue.

[anshumanmohan]

Thanks for staging this, let’s hash it out at tomorrow’s meeting

[polybeandip]

Updates from Monday's meeting (7/29)

We'll move forward with hot pointer approach above as our definition of round-robin: i.e. skipped classes don't save their turn and flushing in the scenario above yields flush-2. Note that this is different from our algorithm for WFQ with equal weights.

To-do: make a scheduling transaction (i.e. an Alg_t module) and graph for this policy in schedulers-in-ocaml.