Queue Management

1. Buffers and queues in congestion handling

Network devices that forward traffic, from home routers to carrier switches, use buffers divided into one or more queues. A queuestores packets when their arrival rate exceeds the interface's current transmission rate. The buffer separates packet arrival from service by the interface and absorbs short periods in which several inputs compete for one output.

Consider a router with multiple input ports and a single output port. If packets from several inputs are sent to the same output link and their combined arrival rate exceeds the link's capacity, a bottleneck is created. The router cannot transmit data faster than the physical link allows. Packets that are waiting are placed in the queue associated with the output port. The buffer capacity limits how many packets can be held before transmission. Once the buffer is full, the device needs a discard rule unless an AQM mechanism has already dropped or marked a packet.

Queues show where congestion affects packet forwarding. Queue management covers the packets stored in a buffer and the rules for dropping or marking them. A scheduler determines transmission order and the bandwidth share of each class. Both mechanisms affect delay, delay variation, and packet loss, so they are basic elements of Quality of Service (QoS). Their configuration must account for buffer capacity and output bandwidth.

2. FIFO (First-In, First-Out) Queueing

FIFO is a simple queueing discipline. A device handling best-effort traffic may use it when no explicit QoS policy is configured. It assigns no classes or weights, so the scheduler uses arrival order. When the queue is full, new packets are normally subject to the device's discard policy.

How FIFO Works

A router using FIFO has a single queue for a given output interface. Packets arriving at the interface are placed at the back of the queue, and the scheduler takes them from the front in arrival order. With multiple flows, the same rule applies to all traffic sent through that interface.

Strengths of FIFO

• Simplicity: It requires little processing overhead and simple memory management, so it is easy to implement.
• Order Preservation: For a single flow of data, FIFO guarantees that packets will be transmitted in the same order they were received, preventing out-of-order delivery by that router.

FIFO limitation: no differentiation

FIFO serves packets in one order and does not account for priority or application requirements. This can cause head-of-line blocking. If a large lower-priority packet, such as a segment of a file download, reaches the front of the queue, it is transmitted before small latency-sensitive packets such as VoIP or DNS request packets. Those packets wait until the large packet has been transmitted, increasing delay and potentially delay variation for real-time traffic.

3. Priority queueing (PQ)

Priority Queueing (PQ) extends FIFO by classifying traffic into multiple priority levels. It is a classic QoS mechanism in which an administrator defines classes and their service order.

How Priority Queueing Works

With PQ, a router uses multiple queues for a single output interface. One implementation can define four levels: High, Medium, Normal, and Low. A classifier at the input assigns each arriving packet to one of these queues based on a predefined policy (e.g., based on protocol, port number, or DSCP marking). The scheduler then follows a very strict rule:

1. It always checks the High-priority queue first. If there are any packets in the High queue, it will transmit them until that queue is completely empty.
2. Only when the High queue is empty will the scheduler even look at the Medium queue.
3. Only when both the High and Medium queues are empty will it service the Normal queue, and so on.

Strengths of Priority Queueing

PQ serves a small amount of high-priority, low-latency traffic ahead of lower-priority classes. Placing VoIP packets in the High-priority queue makes the scheduler serve them before packets in lower-priority queues while the High queue contains packets. This preference reduces waiting for that class while the scheduler can serve it first. A particular delay guarantee requires analysis of the load and configuration.

The Risk of Starvation

PQ can prevent lower classes from being served when high-priority traffic keeps the High queue occupied. This phenomenon is called starvation. Packets in lower-priority queues can wait for an unbounded time and be dropped when the buffer fills. PQ is therefore used with a limited, controlled share and a known profile of high-priority traffic.

4. Weighted fair queueing (WFQ)

Weighted Fair Queueing (WFQ) provides a more balanced allocation than a strict priority queue by dividing bandwidth among traffic flows or classes. Queue weights determine their shares, while packet size and virtual finish time can affect service order. When one queue has no data, its unused share can be assigned to other queues according to the implementation.

How Weighted Fair Queueing Works

WFQ classifies traffic into flows, often using source and destination IP addresses, ports, and interfaces, and assigns logical queues. The scheduler compares virtual packet finish times and applies queue weights. Its behavior can be described through two aspects:

• Bandwidth sharing: With equal weights and 10 continuously backlogged flows on a 10 Mbps link, the simplified example gives each flow approximately 1 Mbps. This limits the share of a single intensive flow, such as a large FTP download, among the remaining flows.
• Serving small packets:WFQ orders packets by a virtual "finish time," the moment at which they would finish under simultaneous bit-by-bit service. In this model, smaller packets receive an earlier finish time, which can shorten response times for interactive traffic.

Class-Based Weighted Fair Queueing (CBWFQ)

Class-Based WFQ (CBWFQ) extends WFQ with explicitly defined traffic classes. The administrator assigns each class to a queue and specifies a weight or guaranteed minimum bandwidth. An example policy might have the following form, and its guarantee depends on the implementation and configuration:

• The "Voice" class is guaranteed 2 Mbps.
• The "Database" class is guaranteed 3 Mbps.
• The "Web" class is guaranteed 4 Mbps.
• All other traffic goes into a default class.

During congestion, the scheduler assigns each class at least its configured share when the implementation and configuration provide that guarantee. Extra bandwidth can be shared among the classes.

CBWFQ can be used with one strict-priority queue. This arrangement is known as Low Latency Queueing (LLQ). The real-time queue, such as a VoIP queue, is served before the other classes, and the remaining bandwidth is assigned by CBWFQ. A bandwidth limit on the priority queue protects the other classes from starvation.

5. Active queue management (AQM)

The earlier mechanisms mainly describe the order of transmission from non-empty queues. Active Queue Management (AQM) controls queue length or packet waiting time by dropping or marking packets before the buffer overflows. ECN marking requires support along the path and at the sender; otherwise AQM signals congestion through loss.

Tail drop and synchronization of TCP flows

When a queue reaches its limit, a common discipline is tail drop. The router then drops subsequent packets. If packets from several TCP flows are dropped at similar times, TCP global synchronization can occur. Flows react according to the congestion-control variant in use. In TCP Reno, after the third duplicate acknowledgment, RFC 5681 sets ssthresh to no more than max(FlightSize / 2, 2 * SMSS); after a retransmission timeout, cwnd is set to no more than one full-sized segment. Synchronized reactions can lower link utilization before traffic rises again.

Random Early Detection (RED)

Random Early Detection (RED) is a classic AQM algorithm. It spreads drop or marking decisions over time to limit synchronized flow reactions. Its average queue depth is smoothed, so a short burst does not necessarily trigger an immediate decision.

• RED monitors the average queue depth, which smooths out short-term bursts.
• It uses two thresholds: a minimum threshold ($min_{th}$) and a maximum threshold ($max_{th}$).
• When the average queue depth is below $min_{th}$, the basic model drops no packets.
• When the average queue depth is between $min_{th}$ and $max_{th}$, packets are dropped or marked with a probability that rises linearly from 0 to a configured maximum as the average approaches $max_{th}$.
• When the average queue depth exceeds $max_{th}$, packets are dropped under heavy congestion.

Applying decisions to packets from different flows at different times can make TCP sessions react asynchronously and limit global synchronization. RED thresholds describe the average queue and are not a direct equivalent of the buffer's physical capacity. Weighted RED (WRED) is a variant that considers packet priority, such as a DSCP value, so lower-priority packets can receive a higher drop probability. Thresholds and probabilities must be tuned to the offered load and traffic mix.