Target switching in hierarchical `LSTF`/`EDF` and `SJN`

[polybeandip]

Before reading this issue, it would be helpful to familiaize yourself with the EDF in our glossary of scheduling policies.

Consider the following DSL program; while it's specific to EDF, the same discussion can be had about SJN.

classes A, B, C;

rr_A_B = rr[A, B];

policy = edf[rr_A_B, C];

return policy

Question 1: when pushing a packet, what rank do we give it's associated pointer in the root PIFO?

Perhaps using the packet's "slack" is a good choice? let's go with that for now!

Suppose we encounter the following sequence of packets (before performing any pops)

# Notation: (X_i, j) is the ith packet from flow X, with slack j
(A_1, 1), (A_2, 2), (A_3, 3), (B_1, 1000), (C_1, 4)

Flushing our PIFO tree yields

A_1, B_1, A_2, C_1, A_3

Question 2: is this right?

Notice how packet B_1 was popped before every packet other than A_1 despite having a drastically larger slack than them.

Question 3: is this strange or a problem? I think B_1 could maybe overtake A_2 and A_3 but passing C_1 feels wrong. Similarly, A_3 losing to C_1 seems odd.

In general, it seems policies that use properties inherent to packets have confusing behavior when realized on trees, similar to our previous discussion on PIEO trees. There, we got away with this because target switching would only happen between ripe packets (which we deemed okay); here, all packets and internal references are always visible.

[anshumanmohan]

Happy to go some other way of course, but I kinda think that a policy like edf should totally smother any sub-policies and just enforce slack-based prioritization.

So, your policy above is the same as:

edf[A, B, C]

Your problem is very interesting, but, like it sorta reads like the user didn't really know what they wanted! In general I do think it's okay if certain hierarchical compositions cancel each other out, or smother a child, or whatever.

[KabirSamsi]

Discussing our attempts to resolve this in #55.

[anshumanmohan]

Hi Nate,

Thanks again for chatting. In this email I'm hoping to crisp up the main issue in writing.

Consider the policy:

classes A, B, C;
rr_A_B = rr[A, B];
policy = edf[rr_A_B, C];
return policy

Where, morally, the policies are:

• rr is Round Robin.
• edf is Earliest Deadline First, aka Least Slack Time First. It reads a packet's header to determine its slack, and dispatches a packet with lower slack before one with higher slack. See Leung, Algorithmica '89 §2.

In moving to PIFO tree implementations, we need to think of scheduling transactions that will grant ranks in accordance with those policies:

• Round-robin is straightforward.
• For EDF, Sivaraman et al. give us the scheduling transaction. It's a one-liner: p.rank = p.slack + p.arrival_time. See Sivaraman et al., SIGCOMM '16 §3.1. At first glance I buy this: packets with less slack get serviced first; packets with the same slack get FIFO service. One can imagine small tweaks to the formula, but the point remains that some header field greatly influences the rank.

Now back to our example. Let's say that packets arrive like so:

Arrival time	Name	Flow	Slack	Rank given from edf's PoV
1	a1	A	1	2
2	a2	A	2	4
3	a3	A	3	6
4	b1	B	1000	1004
5	c1	C	4	9

Let's visualize the tree at every point in time. The tree is:

       edf
      /   \
     rr    C
    /  \
   A    B

where edf and rr are PIFOs and A, B, and C are FIFOs.

I'll write out the contents of all internal PIFOs in a table indexed by time.

• In PIFO edf, an entry (v, r) means value v with rank r. Note that we're in a tree setting, so the values v will be the integers 1 or 2, representing an opportunity for the PIFO's left or right child to nominate the next packet. The ranks will be what we would have given a packet, were there just a FIFO under us. These are actually the only interesting ranks in the tree, and they are granted in accordance with the table above.
• In PIFO rr, an entry (v, ?) means value v with an uninteresting rank (because it's just round robin doing its thing). Again, the values v will be 1 or 2.
• The three FIFOs will just have values. These values will be actual packets.

Recall that we read queues from right to left, so the most favorably ranked entry is the rightmost one.

Time	PIFO edf	PIFO rr	FIFO A	FIFO B	FIFO C
0 + ε	Empty	Empty	Empty	Empty	Empty
1 + ε	[(1, 2)]	[(1, ?)]	[a1]	Empty	Empty
2 + ε	[(1, 4); (1, 2)]	[(1, ?); (1, ?)]	[a2; a1]	Empty	Empty
3 + ε	[(1, 6); (1, 4); (1, 2)]	[(1, ?); (1, ?); (1, ?)]	[a3; a2; a1]	Empty	Empty
4 + ε	[(1, 1004); (1, 6); (1, 4); (1, 2)]	[(1, ?); (1, ?); (2, ?); (1, ?)]	[a3; a2; a1]	[b1]	Empty
5 + ε	[(1, 1004); (2, 9); (1, 6); (1, 4); (1, 2)]	[(1, ?); (1, ?); (2, ?); (1, ?)]	[a3; a2; a1]	[b1]	[c1]

Now, let's say starting at time 6, we pop this tree repeatedly.

• First pop: (1, 2) comes out of PIFO edf. This triggers the popping of edf's first child, PIFO rr. The rightmost (1, ?) comes out. This triggers the popping of rr's first child, FIFO A. Packet a1 comes out.
• Second pop: (1, 4) comes out of PIFO edf. This again triggers the popping of edf's first child, PIFO rr. The (2, ?) comes out. This triggers the popping of rr's second child, FIFO B. Packet b1 comes out.
• I will skip the rest, but then a2 comes out, then c1, then a3.

The overall order is a1, then b1, then a2, then c1, then a3. The Round Robin goal was met, but it feels like a massive failure of EDF. The reason is now clear too: although b1 had a terrible slack, it got to jump the line! The distinction in slack-based ranks between the a? packets and the packet b1 was blurred because they both lived under some intermediary PIFO, in this case the round-robin PIFO. In particular:

• When pushing b1 into the tree, we correctly enqueued (1, 1004) into the PIFO edf.
• However, b1 was popped by the popping of (1, 4), which itself was put into the PIFO edf because of a2, a packet having low slack.

We of course know that such target switching needs to be allowed. As we have been telling people during talks and such, this is exactly the power of PIFO trees. This case is particularly interesting because a child got to mess so badly with a parent. If a parent (having an "overarching" policy, vaguely speaking), were to dominate a child, I guess I'd understand. But this current situation feels very mind-bendy and un-compositional!