Cheap Nasty Queueing

3.1. Overview

Unlike conventional fair queueing, with Cheap Nasty Queueing, packets are not distributed to queues by a flow mapping, but by a sparseness metric associated with that mapping. Thus, the number of queues is reduced to two.¶

The number of flows which can be handled is far greater, however, being limited by the number of flow buckets indexed by the flow hash. An implementation might define a flow as traffic to one subscriber, and provide a perfect mapping between subscribers and buckets. Alternatively it might provide a stochastic mapping based on the traditional 5-tuple of addresses, port numbers, and protocol number. The latter would be appropriate for low-cost consumer hardware, in which the notion of a "subscriber" is neither well-defined nor useful.¶

The per-flow state is just one unsigned integer, in contrast to DRR++ which requires a whole queue and a set of AQM state per flow. This integer is B, tracking the backlog of the flow in packets. This small per-flow state makes tracking a large number of flows practical.¶

The two queues provided are SQ and BQ:¶

SQ is the "sparse queue" which handles flows classed as sparse, including the first packets in newly active flows. This queue tends to remain short and drain quickly, which are ideal characteristics for latency-sensitive traffic, and young flows still establishing connections or probing for capacity. This queue does not maintain AQM state nor apply AQM signals.¶

BQ is the "bulk queue" which handles all traffic not classed as sparse, including at least the second and subsequent packets in a burst. An AQM algorithm is applied to all traffic delivered from it.¶

To prevent well-paced traffic from dominating the queue by keeping exactly one packet in SQ at all times, a dummy packet is sent into BQ in parallel with every packet enqueued in SQ, and the B value for the flow is double-incremented to match. A flow is therefore considered sparse IFF the interval between its packets is longer than the sojourn time of packets in BQ. This can be a much stricter criterion than for true derivatives of DRR++ such as LFQ.¶

In case of queue overflow, packets are removed from the "head" of BQ to make room for the new arrivals; this head-dropping behaviour minimises the delay before the lost packets can be retransmitted.¶

This simplification of state and algorithm has some drawbacks in terms of resultant behaviour. The sharing of link capacity between flows is dependent mainly on the RTT-fair properties of the flows' own congestion control, in response to congestion signalling from the single AQM.¶

3.2. Declarations

The following queues are defined:¶

 -------------------------------
-->                  | | | |  -->
 -------------------------------
 SQ: the Sparse Queue, containing packets from flows with no more
 than one packet in the queue at a time (no AQM for this queue).

 -------------------------------
-->    | | | | | | | | | | |  -->
 -------------------------------
 BQ: the Bulk Queue, containing packets from flows that build up a
 multi-packet backlog (AQM managed queue).

The following constants and variables are defined:¶

• B: the flow backlog, in packets¶

• N: the number of flow buckets (each bucket containing a value of B)¶

• S: the size of a packet¶

• T: the packet's timestamp, for later use by AQM¶

• H: the packet's flow hash, cached¶

• MAXSIZE: the maximum size for all packets in the queue¶

• NOW: the current timestamp¶

Finally, the hash function FH() maps a packet to a flow bucket:¶

                                     +---+
                                /--- | B |
                               /     +---+
                              /
                    +------+ /       +---+
----- Packet -----> | FH() | ------- | B |
                    +------+ \       +---+
                              \
                               \
                                \--- ... N

3.3. Pseudo-code

In the following pseudo-code:¶

• Lowercase is used for internal variables, and uppercase for constants, variables and queues defined in Section 3.2.¶

• The send() function transmits the packet.¶

• The aqm_action() function updates the AQM state (if any) based on the current sojourn time, and returns an action code indicating whether a CE or SCE mark (or no mark) should be applied. This function may be stateless and merely return results from a threshold function or probability ramp, or it may implement Codel or similar stateful AQMs, or a hybrid of the two for separate CE and SCE marking strategies.¶

The following functions and variables are defined for both the sparse and bulk queues:¶

• The push() function adds a packet to the tail of the specified queue.¶

• The pop() function removes and returns the packet from the head of the specified queue.¶

• The .size variable (BQ.size and SQ.size) refers to the sum of the sizes of all packets in the queue, and may be maintained during push(), pop().¶

• The .head variable is the current head pointer for the queue.¶

The logic for the enqueue operation is as follows:¶

enqueue(packet p) {
    while (SQ.size + BQ.size + S > MAXSIZE) {
        ; Queue overflow - drop from BQ head, then from SQ
        dp := pop(BQ)
        if (!dp)
            dp := pop(SQ)
        bkt := dp.H
        bkt.B -= 1
    }

    bkt := FH(p)
    p.T = NOW
    p.H = bkt
    if (bkt.B == 0) {
        push(SQ, p)
        dp := zero-length dummy packet
        dp.T = NOW
        dp.H = bkt
        push(BQ, dp)
        bkt.B += 2
    } else {
        push(BQ, p)
        bkt.B += 1
    }
}

The logic for the dequeue operation is as follows:¶

dequeue() {
    ; SQ gets strict priority
    p := pop(SQ)
    if (p) {
        send(p)
        bkt := p.H
        bkt.B -= 1
        return
    }

    ; Process BQ if SQ was empty
    repeat {
        p := pop(BQ)
        if (!p) {
            ; Queue is empty
            return
        }

        bkt := p.H
        bkt.B -= 1

        if (p.S == 0) {
            ; Dummy packet for sparseness metric - drop
            continue
        }

        ; Apply AQM logic based on sojourn time
        t := NOW - p.T

        ; drop unresponsive traffic
        if (t > 500ms)
            continue

        switch(aqm_action(t)) {
        case MARK_CE:
            ; legacy congestion signalling
            if (t.ECN == Not-ECT)
                continue
            ; RFC-3168
            if (t.ECN == ECT || t.ECN == SCE)
                t.ECN = CE  ; and update IP header checksum
            break

        case MARK_SCE:
            ; Some Congestion Experienced
            if (t.ECN == ECT)
                t.ECN = SCE ; and update IP header checksum
            break

        default:
            ; no marking request
            break
        }

        send(p)
        return
    }
}