Priority and Fair Queueing for Mixed Traffic

A single FIFO queue gives every packet the same delay distribution, which means a bulk transfer and a voice call sharing a link receive the same treatment. When the link is idle that is harmless; when it is loaded, the voice call’s packets sit behind whatever the transfer has queued, and the call degrades for reasons that have nothing to do with the link’s capacity. Scheduling is the set of mechanisms that break the shared distribution into separate ones, and the mechanisms differ mainly in how they handle a class that is not using its share.

The problem is not only about prioritising latency-sensitive traffic. It is also about preventing any one class from consuming the link, and about what happens to unused capacity when a class has nothing to send. Every scheduler has to answer both questions, and the answers interact.

Strict priority and the starvation it permits

The simplest scheduler maintains a queue per class and always serves the highest non-empty class. A voice packet is transmitted before any bulk packet that is waiting, regardless of how long the bulk packet has been there.

The latency benefit is exact. If the highest class is shaped to a rate well below the link rate, its queue is short and its packets wait at most for the one packet in service plus whatever is queued ahead of them within the class. The bulk class is irrelevant to it. This is the mechanism that makes a real-time class usable on an otherwise saturated link.

The failure mode is equally exact. Strict priority offers no guarantee to lower classes. If the high class misbehaves, or is configured with too generous a rate, or is flooded by traffic that has been marked as high class without authorisation, the lower classes receive nothing. A bulk transfer on a link whose high class is unshaped will starve completely, and the starvation is invisible in the high class’s own measurements.

There is a subtler issue: strict priority also starves the lower classes during the high class’s bursts. A high class that is normally light but occasionally sends a large burst delays everything behind it for the burst’s duration. If the burst is a hundred full-size packets, the lower classes wait for the time it takes to transmit them, which on a 10 Mbit/s link is over a tenth of a second.

The practical rule is that a strict priority class should be shaped to a fraction of the link and should carry traffic that is genuinely small and genuinely latency-sensitive. Both conditions are about the traffic’s aggregate rate, not about individual packets, and neither is enforced by the scheduler itself.

Fair queueing and the max-min objective

Fair queueing replaces priority with an allocation rule. The classical formulation, generalised processor sharing, imagines the link as a fluid server that divides its rate among the backlogged flows in proportion to weights, and the packet-level algorithms approximate that fluid behaviour by tracking, for each packet, the time at which it would have completed service under the fluid model, then transmitting in order of that virtual finish time.

The property that makes this attractive is max-min fairness: a flow that is not using its full share leaves capacity available to others, and the allocation is the one that maximises the minimum rate any flow receives. A class with weight 1 and a class with weight 3 share the link 1:3 when both are backlogged, and the light class gets everything it needs when the heavy class is idle. No class can be starved by another class’s excess, because the excess is exactly what the fair allocation denies it.

The cost is complexity and state. Tracking virtual finish times requires a per-flow or per-class timestamp, a sort or a priority structure to select the next packet, and careful handling of flows that become active and idle. On a core router with a million flows that state is prohibitive, which is why fair queueing appears most often at the edge, where the number of classes is small and known.

Deficit round robin and the packet-size problem

Round robin over queues has a defect that shows up with variable packet sizes. A simple round robin that serves one packet per queue per turn gives a queue sending maximum-size packets far more bytes than a queue sending small packets, because the byte count per turn differs by a factor of twenty or more. Byte-counting fair queueing avoids that but requires the scheduler to know each packet’s size before selecting it, which complicates the implementation.

Deficit round robin solves it with a per-queue credit. Each queue has a deficit counter. On each visit, the counter is increased by a quantum proportional to the queue’s weight, and then packets are served from that queue while the counter is at least the size of the next packet, subtracting each packet’s size. If the queue’s next packet is larger than the remaining credit, the visit ends and the credit carries over to the next visit.

The carry-over is the essential detail. Without it, a queue whose packets are consistently larger than the quantum would never be served, because it would never accumulate enough credit within one visit. With it, a queue sending large packets is served one packet every few turns, and its average byte rate matches its weight over time. The credit is bounded, so a queue that has been idle cannot bank unlimited credit and then send a huge burst.

/* One turn of a deficit round robin scheduler over n queues.
   q[i].deficit carries over between turns; q[i].head is the next packet. */
static int drr_serve(struct queue q[], int n, int quantum,
                     struct packet **out, int max_out)
{
    int produced = 0;
    for (int i = 0; i < n && produced < max_out; i++) {
        if (!q[i].head) {               /* idle queue banks no credit */
            q[i].deficit = 0;
            continue;
        }
        q[i].deficit += quantum;
        while (q[i].head && q[i].head->len <= q[i].deficit) {
            struct packet *p = q[i].head;
            q[i].deficit -= p->len;     /* charge the whole packet */
            q[i].head = p->next;
            out[produced++] = p;
            if (produced == max_out)
                break;
        }
        /* If the next packet is larger than the remaining credit it stays
           queued, and the leftover credit is kept for the next turn. */
    }
    return produced;
}

Resetting the credit of an idle queue is the detail that matters most in practice. A queue that has been empty for many turns would otherwise accumulate credit proportional to the time it was idle, and its first burst after becoming active would be served far above its share. Resetting to zero bounds the deficit of an active queue at less than two quanta, so no queue can be more than one packet ahead of its allocation.

A representative configuration uses a quantum of a few hundred bytes to a few kilobytes per queue. A quantum of 1,500 bytes means a queue with maximum-size packets gets one packet per turn and a queue with 500-byte packets gets three, which equalises bytes per turn. Larger quanta reduce the number of turns and the scheduler’s overhead but increase the burstiness of each queue’s output, which matters if the output feeds a latency-sensitive downstream.

Deficit round robin’s fairness is approximate and long-term. It does not provide the bounded delay guarantee that a fluid model gives, because a queue can accumulate credit and then send a burst. For the purpose of separating bulk from interactive traffic, the approximation is usually sufficient; for a hard latency guarantee, the scheduler needs shaping in addition.

Shaping, policing, and where the queue lives

A scheduler decides which queue to serve next. A shaper decides when a queue may be served at all, by enforcing a rate on the class’s output. The distinction matters because a scheduler without a shaper cannot bound a class’s rate: strict priority with an unshaped high class starves everything, and fair queueing with an unshaped class merely divides the excess among classes rather than preventing it.

Shaping requires a queue to hold packets that are waiting for their permitted transmission time, and that queue is where latency accumulates. A shaper configured at the link rate with a small burst allowance holds almost nothing; a shaper configured well below the link rate holds whatever arrives faster than the permitted rate, and that backlog’s drain time is the delay the class experiences. This is the same standing-queue mechanism described in standing queues and buffer sizing, applied deliberately rather than accidentally.

Policing is the alternative: instead of delaying packets over the permitted rate, it discards them. Policing adds no delay but converts excess into loss, which a bulk flow handles by reducing its rate and a real-time flow handles badly. The choice between the two is a choice about which failure mode the traffic tolerates.

On an access link the useful arrangement is usually a shaper at slightly below the subscribed rate, so that the queue forms in the subscriber’s own device rather than in the upstream network where it cannot be managed, combined with a scheduler that gives the interactive class priority within the shaped rate. The shaper’s queue is then the only queue, and it is under local control. This is the standard structure behind the latency improvements attributed to smart queue management on home gateways, and its effect is measurable with the delay-under-load methodology in measuring latency under load.

What classification costs and where it goes wrong

Every scheduler needs a classifier to assign packets to classes, and the classifier is where most deployments fail. Classification by port number is defeated by encryption and by protocols that multiplex over one port. Classification by address is defeated by any traffic the operator did not anticipate. Classification by a field the endpoint sets is defeated by endpoints that set it dishonestly.

The practical option is to classify at the first device the traffic crosses, which is usually the endpoint or the access device, and to mark the result in a field that downstream devices trust. The differentiated services architecture defines such a field and a per-hop behaviour for each class, and its design assumes that trust boundary explicitly: marking is done at an edge the operator controls, and interior devices act on the marking without re-deriving it.

Where that trust boundary does not exist, a scheduler that honours endpoint markings becomes a way for any endpoint to obtain priority. The consequence is that unmarked bulk traffic is starved by marked bulk traffic, and the scheduler’s benefit disappears. The design has to include a policy that limits the rate of the high class regardless of marking, which returns to shaping, and the two mechanisms are only useful together.