Calendar Queues - Overview & Analysis

[KabirSamsi]

Calendar Queues – Overview & Analysis

This serves to discuss the implementation of the Programmable Calendar Queue (PCQ), its relevance against PIFOs and potential drawbacks.

Papers

1. https://www.usenix.org/system/files/nsdi20-paper-sharma.pdf
2. https://dl.acm.org/doi/pdf/10.1145/63039.63045

Summary

A Calendar Queue's functionality is analogous to that of a desk calendar. We have a tracker pointing to the 'current day' in a year, which represents a single bucket in an array of buckets.

That bucket holds a series of values/packets, etc.

• The order of those values represents their respective priority.
• The bucket which is currently pointed to has the highest priority.
• The successive buckets in the queue have decreasing priority.
• We then wrap around, such that the buckets leading up to our current bucket have decreasing priority, until bucket k-1.

So priority ordering would go something like follows:

$$b_k \geq b_{k+1} \geq b_{k+2} + \dots \geq b_n \geq b_0 \geq b_1 \geq b_{k-1}$$

One big advantage that this gives, as we'll discuss in the Advantages section, is an ability for dynamic and implicit escalation of priority. If we wish to 'advance time', we rotate the queue. This way, elements that have been in the queue longer end up receiving a higher overall priority, which proves practical for a variety of policies.

For elements which we wish to effectively 'schedule for close to a year later', we insert them at the front of the queue. Since our pointer is further down, that will be the effective behavior.

Structure and Functionality

Calendar Queues have a structure similar to that of hashtables that employ chaining. One common representation is an array of buckets – which can be stored as lists, linked lists, etc.

For a Calyx representation, a 2D memory cell might be the most pragmatic for the overall representation.

Three Major Operations

1. push/enqueue: Takes in a value and a priority and accordingly pushes it into the Calendar Queue
2. pop/dequeue: Takes no arguments. Dequeues the lowest priority element from the queue
3. rotate: Takes no arguments. Shifts the current day pointer, such that we can 'advance in time'.

The signature here is very similar to that of a PIFO, with that added functionality of rotation.

Presented Advantages Of Calendar Queues

• Calendar queues enable us to create Priority Queues with two major advantages:

  • Prioritization of packets with higher priority
  • Implicit and Mass Escalation of Priority With Time, As We Move Elements

• We can now enable policies such as Earliest Deadline First and Weighted Fair Queueing. At a general level, we achieve a PIFO-esque optimization which enables us to not only enqueue elements by priority, but also factors in time as a variable.

• Speed and general hardware compatibility.

A Visual OCaml Representation

As with PIEO queues, I've explored a potential OCaml implementation that may develop as we further our understanding of the structure (note that as with earlier structures, we add peek functionality, which functions like pop without mutating the structure):

module type CalendarQueue = sig
	type rank
	type 'a t
	val push: 'a t -> 'a -> rank -> 'a t
	val pop: 'a t -> 'a option
	val peek: 'a t -> 'a option
	val rotate: 'a t -> 'a t
end