PIEO Queues – Overview & Analysis

[KabirSamsi]

PIEO Queues – Overview & Analysis

This issue discuss the implementation of the PIEO (Push-In-Extract-Out) Queue, its relevance against PIFOs and potential drawbacks. See #9 for details on the task!

Papers

1) DR-PIFO: A Dynamic Ranking Packet Scheduler Using a Push-In-First-Out Queue – Elbediwy et al 2024, IEEE 2) Discussion on Push-In-Extract-Out Scheduler in Hardware – McLaughlin, University of Hawaii

Summary

Fundamentally, a PIEO (Push-In Extract Out) Queue is a generalization of the PIFO (Push-In First Out) Queue which we have already studied. The main difference lies in how a queue is queried.

Functionality and Relevant Operations

PIFOs contain two key functions – enqueue(f) and dequeue(f) (or, push and pop), alongside the query method peek. These require f to be some element containing a value and a rank.

With PIFOs, enqueueing pushes a new packet p into a queue such that the rank ordering is preserved. Dequeueing pops the head of the queue.

PIEOs embody all of this functionality, but with an added eligibility predicate. This takes on the form of a partial function mapping PIEO nodes to true or false. (See McLaughlin).

enqueue functions the same way. The dequeue function can take in an optional parameter p representing a specific packet to be dequeued.

If such a parameter is provided and and p occurs within PIEO, then the packet p is dequeued and returned, regardless of rank and eligibility. Otherwise, None is returned.

Notably, in the case that one wishes to update the value or rank of a packet p, this can be performed by dequeueing p, updating it, and then enqueueing it again.

If no parameter is provided, then the PIEO filters all packets such that the eligibility predicate returns true. It the returns the element with the lowest rank. In the case of a tie, the earliest element to be enqueued is returned.

A Side Note/Question On Peeking

While both papers have only explicitly discussed the enqueue and dequeue functions (with no mention of peeking), our PIFOs account for peeking as well.

I propose that for PIEOs, we generalize the function peek in the same way we will pop – that is to say, we run dequeue with optional parameter p, but do not modify the PIEO in question.

Pros and Cons of PIEOs (Against PIFOs)

There are a few drawbacks of using a PIFO for packets, which PIEO queues can address (See in particular Section 2E of Elbediwy et al.)

Inability to Re-Rank Enqueued Packets

• Once a packet has been enqueued in a PIFO, it cannot have its rank modified, as there is no way to re-access it through the PIFO's interface.
• This is easily achievable with a PIEO, as described above. By dequeueing a specific packet p, modifying it as desired and then enqueueing it again, we're able to bypass this issue.

Scalability

• A major issue with PIFOs is that it is unable to handle high numbers of flows in a reasonable timeframe (Elbediwy et al upper bounds this at around 1000).
• PIEOs can instead handle up to 30,000 simultaneous flows by optimizing its register usage.

A Potential Downside – Speed

• PIEOs require a four-step non-pipelined system, which is slower than the standard PIFO architecture.
• Enqueueing and dequeueing achieve a throughput of 1 packet per 4 cycles, while updating a rank can lead to an 8-cycle break from the norm.

A Visual OCaml Representation

For the sake of argument and a visual aid, I've explored a functional PIEO module type implementation in OCaml:

module type PIEO = sig
    type rank
    type 'a t
    val eligibile: 'a -> bool
    val enqueue: 'a t -> 'a -> rank -> 'a t
    val dequeue: 'a t -> 'a option -> ('a option * 'a t)
    val peek: 'a t -> 'a option -> ('a option * 'a t)
end

In which eligible maps any element to true or false, enqueue takes in a PIEO, element and rank and returns a PIEO, and both dequeue and peek take in a PIEO and an optional element, and either return the element (if found) and a PIEO queue.

[anshumanmohan]

Super cool, thanks for this research!

• Re: peek: I wouldn't worry too much about it! It's not necessarily a standard method anyway; our queues just support it because it is easy and may see some use. We may even remove it if we find we're never using it.

• The dequeue function can take in an optional parameter p representing a specific packet to be dequeued.

  Nice, and I imagine that if multiple copies of p exist, there is some straightforward rule to pick one.

• The scalability/speed trade-off is interesting, and I'll read the papers to learn more.

• Your OCaml signature is a helpful way to crisp this up. I have a question for you: are you sure eligible is "baked in" when defining the PIEO?

  For example, let's say I define a PIEO using your signature above. For ’a I pass integers and for eligible I pass is_even. Going by your description and signature, this notion of eligibility is baked right in, and so odd integers pushed into this PIEO will never be popped. If were thinking like a super thrifty implementer of such a queue, I would actually run the eligibility check at enqueue, and simply save myself the trouble of ever enqueuing items that fail eligibility. Then there would be no need to run the eligibility check at dequeue, since the PIEO would be full of eligible elements.

  I think you may have wanted something like this:

  module type PIEO = sig
    type rank
    type 'a t
    val enqueue: 'a t -> 'a -> rank -> 'a t
    val dequeue: 'a t -> ('a -> bool) -> 'a option -> ('a option * 'a t)
    val peek: 'a t -> ('a -> bool) -> 'a option -> ('a option * 'a t)
  end

  Now dequeue (and peek) take a new second argument, ('a -> bool), a predicate on packets. So the eligibility is no longer baked into the very definition of the queue. You can dequeue the queue once with is_even and get the best-ranked even number, and you can dequeue the same queue later on with is_odd to get the best-ranked odd number. I have retained the 'a option, now the third argument. So you're allowed to filter by eligibility and then hunt for a specific packet. If you don't want to filter by eligibility, just pass a predicate that always returns true: fun _ -> true.

[anshumanmohan]

See also:

• https://dl.acm.org/doi/10.1145/3341302.3342090
• https://ieeexplore.ieee.org/document/9651944

[anshumanmohan]

Also: a big use of the eligibility check in PIEOs is probably non work-conserving algorithms, sometimes also known as shaping algorithms.

From Formal Abstractions:

The focus of our study has been work-conserving scheduling: a pushed packet can immediately be popped. Non work-conserving algorithms, also known as shaping algorithms, say that a packet cannot be popped until some time that is computed, specifically for that packet, at push. This means that a less favorably ranked packet may be released before a more favorably ranked one if the former is ready and the latter is not, and the link may go idle if no packets are ready.

To achieve this using a PIFO is tricky and requires various tricks. With a PIEO, I can imagine carefully crafting the time-aware eligibility check packet_is_ready and using that in a straightforward way to dequeue packets. It's not actually clear if we will support non work-conserving policies in our project. Anyway, just something to keep an eye out for when you read, slash context for you if you have already seen the term and been confused!

[KabirSamsi]

Replying to the earlier thread:

• Nice, and I imagine that if multiple copies of p exist, there is some straightforward rule to pick one.

The policy I believe here is to return whichever copy was inserted first.

• are you sure eligible is "baked in" when defining the PIEO?

Unfortunately my interpretation seems to have been wrong – the papers were both a little bit vague on how the eligibility predicate is actually defined.

My interpretation was that it would be nice to have a one-for-all predicate given a PIEO that could operate on all incoming packets. Your suggestion makes a lot more sense though – popping then kind of integrates the filter function and it makes sense that we'd want it to be dynamic!

[KabirSamsi]

Updates on using PIEOs for this project:

I definitely believe that implementing these would be a worthwhile task. They provide a fairly significant advantage over PIFOs, and we can rely on existing implementations already.

@polybeandip and I were discussing potential implementations. I think we might try to begin with the binary heap structure, which should already support enqueueing in the way we desire. We can then add functionality specific for dequeueing specific elements.

[KabirSamsi]

Note on predicates:

Fortunately, for most packet scheduling algorithms, the predicate usually takes the form ($t{currrent} \geq t{eligible}$), where t could be any monotonic increasing function of time, and $t{eligible}$ is when the element becomes eligible for scheduling and can be calculated at enqueue into the ordered list (§4). This allows for a fast and parallel evaluation of predicates at dequeue. Further, one only needs to encode $t{eligible}$ for each element as the predicate, thus also ensuring a small storage footprint, important for scalability.

[anshumanmohan]

Just to summarize, I think we have agreed that the eligibility predicate is neither as baked-in as was originally suggested, not as free-wheeling as I then proposed. It will be relatively baked in, but will crucially have some kind of time input. As this time passes, different things (in our case, more things) will answer positively to the eligibility question.