Glossary of Scheduling Policies

[anshumanmohan]

This is a running list of scheduling policies, both work-conserving and non-work-conserving of which we are aware. It would be great if our DSL could easily express a large number of these. The list is currently in roughly increasing order of complexity, and probably makes for a good ordered hitlist for our project.

Warning, WIP: I am surfacing this early so people can look at it and comment on it as I improve it.

Work-Conserving Policies

1. FCFS/FIFO order. First come, first served.
   • fcfs(A) just sends packets of class A in the order that they arrive.
   • fcfs(A, B) emits a mix of packets from classes A and B, again following the order that packets from these classes arrive.
2. Round-robin.
   • Agnostic to any other feature of packets, such as size.
   • rr(A, B) sends one packet from A, one from B, and so on. If one class is silent and the other is active, it allows the active class to send packets in FIFO order until the silent class starts up again. The erstwhile silent class does not get any form of "credit" for the time it was silent.
   • rr(A, B, C) behaves as you would expect from the above. A subtlety of this policy is that if, say, A fell silent, the policy would need to temporarily become equivalent to rr(B, C).
   • See Agree on the workings of Round-Robin  #48 for a more precise description of the policy.
3. Strict priority.
   • Again agnostic to other features.
   • strict(A, B) emits packets from class A so long as as class A is active. If class A falls silent, it emits packets from B until such time as class A is active again.
4. Weighted Fair Queueing (WFQ), aka Weighted Round Robin (WRR). Demers et al, SIGCOMM '89.
   • Agnostic to packets' own features, but accepts user-set weights for prioritizing classes of packets.
   • wfq_2_3(A, B) emits packets from classes A and B, attempting to ensure that, for every five packets emitted, two come from A and three from B. If one class is silent, the other is temporarily allowed more than its stated share. When the silent class starts transmitting again, it does not get "credit" for the time it was silent. I can imagine denoting this differently, like wfq((2, 3), (A, B)) or something.
   • wfq_2_3_4(A, B, C) behaves as you would expect from the above. A subtlety of this policy is that if, say, A fell silent, the policy would need to temporarily become equivalent to wfq_3_4(B, C).
5. Least Slack-Time First (LSTF), aka Earliest Deadline First (EDF). Leung, Algorithmica '89.
   • Each packet comes in with some "slack", which is the time remaining until the packet is due to be released.
   • This is the first policy on this list that takes into account some inherent property of the packet being scheduled.
   • lstf(A) emits packets from A in increasing order of packet slack.
   • lstf(A, B) generalizes straightforwardly: mix A and B freely, paying attention to the slacks and not the classes.
   • Mittal et al., NSDI '16 find this to be the closest thing to a universal packet scheduling policy.
6. Shortest Job Next (SJN).
   • The packet that needs the least processing time is scheduled first.
   • Requires some way to accurately predict the time required. Perhaps based on size?
   • This is a non-premptive version of this policy. That is, say the shortest job A would take 10 seconds and gets scheduled at time 0. Then, five seconds later, a job B that would take 2 seconds is enqueued. This policy does not let the quick new job B overtake the running job A, even though B needs 2 seconds and A needs 5 more seconds.
7. Shortest Remaining Time First (SRTF).
   • This is the preemptive version of SJN. In the example above, A would be paused and added back to the queue, and B would be started in its stead.

Non-Work-Conserving Policies

1. Rate-controlled Static-Priority (RCSP)

   • For any flow, all elements within it are assigned 'readiness times' determining at what time they will be ready to be processed.
   • The next packet to be processed will be determined as follows:
     • All flows will be queried to find the highest-priority element which is eligible given the current time and its readiness time.
     • Out of these packets, the lowest-ranking one is processed.
   • rcsp(A, B) will emit a series of elements from both A and B, based on the rules that are described above. If neither one has an eligible element, our scheduler will fall silent as time passes until an element becomes eligible (its readiness time passes).

2. Leaky Bucket Filter

   • The first of our traffic control policies. The main objective is to ensure that 'bursty' flows don't create unbalanced traffic (hence the 'traffic control').
   • The Leaky Bucket algorithm functions similarly to a FIFO, except that it has a constant (parameterized) 'output rate' which determines how many packets it may emit over a given time interval, and a maximum 'backlog buffer size' or number of packets that it may hold at once.
   • It is analogous to a bucket from which we carve a small hole in the bottom – water may enter it at any speed or amount, but water drains from the hole at the base at a constant speed. Once full, we cannot fill it anymore.
   • leaky(A, B, n, m) functions like fifo(A, B) would, except for the fact that it processes elements at specified time rates & capacities as described above.

3. Token Bucket Filter

   • Also a traffic control policy, similar to a leaky bucket filter.
   • "TB schedules packets from eligible flows, i.e., flows with enough tokens, or else defers the scheduling of the flow to some future time by when the flow has gathered enough tokens." (Shrivastav.).
   • Effectively, the underlying queue is a 'bucket' which is assigned a fixed token capacity and refill time.
   • In order to be eligible for a transaction, a bucket needs to have available tokens in it.
     • Emitting a packet costs the bucket a token.
     • After each refill interval passes, the bucket's tokens refill.
   • Functions similarly to a FIFO. token(A, B, n, m) functions likefifo(A, B) would, except that it now handles elements with the capacity and time constraints described above.

4. Stop-And-Go Filter

   • A third traffic-control filter. See here and here for in-depth discussions.
   • Packets are partitioned into 'windows' based on their enqueue time, which have a specified 'start time' and 'end time'.
     • Functions like a FIFO, but takes in an additional parameter for window time length.
     • All packets within a window are dequeued (in FIFO order by arrival time) at the exact moment their window ends.
     • The result is a policy with a highly controlled and restricted series of bursty transactions.
   • stopandgo(A, B, n) functions like fifo(A, B) would, but elements are only accessed after each interval of time length n.

Size-aware
Intuition: if flow A's packets are 3x longer than flow B's, then we should behave as though there were a 1:3 weight from the user.

• Fair Sojourn Protocol (FSP)

Unclassified

• Deficit Round Robin
• Start Time Fair Queueing (STFQ).
  • Siv et al present it as an approximation of WFQ, saying that WFQ is too hard to implement as originally proposed in Demers et al. Need to read more to understand the issue and the fix.

Tabled For Now

1. Jitter-EDD
2. Class-Based Queueing

[sampsyo]

Awesome! Just wanted to say this is really helpful; especially for the most "basic" policies, it's clarifying to see everything written out explicitly.

[KabirSamsi]

I'm adding a handful of non-work-conserving pollicies (and updating this discussion to reflect that we now support both WC & NWC). Also adding a few policies that I think are interesting and worth exploring later, albeit not at the risk of overwhelming ourselves currently!

[KabirSamsi]

Putting a little note here on #46, a new discussion I'm opening up – one where we can store a glossary of 'algorithms' to translate policies we express here into queue representations!

[KabirSamsi]

lstf(A, B) generalizes straightforwardly: mix A and B freely, paying attention to the slacks and not the classes.

@anshumanmohan This can now be more formally stated – $lstf(A, B) \rightarrow lstf(Union(A, B))$!

Same comment for the FIFO and SJN notes.