QoS, queues and traffic shaping

Quality of service (QoS) means giving some traffic better treatment than other traffic where they compete for the same link. It matters only where packets wait, so QoS is about queues: they form at the slowest link of a path, such as a home uplink or a busy office circuit. Three tools do the work. Marking labels each packet with a class in a 6-bit field of the IP header, the DSCP of the Differentiated Services (DiffServ) architecture. Metering with a token bucket checks a class against its rate: policing drops or re-marks the excess, and traffic shaping delays it until it fits. Scheduling decides which of several queues sends the next packet. This lesson shows where queues form, what the marks mean, runs one token bucket in both of its modes, and names the schedulers and queue managers that keep a call clear while a large upload runs.

Where queues form

A router can send only as fast as its output link. When packets arrive faster, they wait in a buffer, and the delay is simply the bytes waiting divided by the link’s rate. A home router with a 20 Mbit/s uplink and room for 500 full-size packets holds 500 × 1,500 = 750,000 bytes, or 6 megabits: a packet at the back waits 6 ÷ 20 = 0.3 seconds. A call’s packet stuck behind an upload’s full queue arrives a third of a second late, although the call needs a tiny share of the link.

Queues form only where traffic slows down. Gigabit switches in front of that uplink rarely queue at all, so a QoS policy on them changes nothing; the policy must sit where the queue builds. Buffers that are large and stay full are called bufferbloat, and the cure is to keep queues short rather than to make them longer.

Marking: one byte in the IP header

DiffServ redefines the byte that IPv4 calls the TOS octet and IPv6 the Traffic Class: its first six bits carry the DSCP (RFC 2474) and the last two the ECN field, which routers use to signal congestion without dropping (RFC 3168). A DSCP selects a per-hop behaviour (PHB), the treatment each router gives the packet:

• Default forwarding (DF), DSCP 0, is ordinary best effort.
• Expedited Forwarding (EF), DSCP 46, asks for low delay and low loss, such as for voice (RFC 3246).
• Assured Forwarding has four classes with three drop levels each, AF11 to AF43 (RFC 2597).
• Class Selectors CS0 to CS7 keep the old IP precedence values working.
• Lower Effort (LE), DSCP 1, is for traffic that should only use spare capacity (RFC 8622).

A mark is a request, not a guarantee. Each network decides whether to trust it, and many re-mark what they do not recognise to zero at their border (RFC 8100).

One token bucket, two jobs

A token bucket earns tokens at a rate r, holds at most b of them, and lets a packet pass when it can pay its size in tokens. Policing drops or re-marks a packet that finds too few tokens, so it adds no delay but loses data. Traffic shaping holds such a packet in a queue until the tokens arrive, so it loses nothing but adds delay. The program sends bursts of 30 packets every 100 ms, 3.6 Mbit/s on average, against a contract of 8 Mbit/s:

"""One token bucket, two jobs: policing drops the excess, shaping delays it.

A video encoder sends a burst of 30 packets of 1,500 bytes every 100 ms, back to back at
1 Gbit/s. On average that is 3.6 Mbit/s. The contract allows 8 Mbit/s with a bucket of
15,000 bytes (10 packets). Tokens are bytes; times are whole microseconds, so the
arithmetic is exact.
"""

PACKET = 1_500
RATE = 1_000_000  # 8 Mbit/s = 1,000,000 bytes a second, so one byte of credit per microsecond
BURSTS, PER_BURST, GAP_US = 5, 30, 100_000
WIRE_US = 12  # one 1,500-byte packet at 1 Gbit/s


def arrivals():
    return [b * GAP_US + i * WIRE_US for b in range(BURSTS) for i in range(PER_BURST)]


def police(times, depth):
    """Send a packet if the bucket holds enough tokens, else drop it."""
    tokens, last, sent, dropped = depth, 0, [], 0
    for t in times:
        tokens = min(depth, tokens + (t - last) * RATE // 1_000_000)
        last = t
        if tokens >= PACKET:
            tokens -= PACKET
            sent.append(t)
        else:
            dropped += 1
    return sent, dropped


def shape(times, depth):
    """Hold each packet in a queue until the bucket holds enough tokens: nothing is dropped."""
    tokens, last, out = depth, 0, []
    for t in times:
        t = max(t, out[-1] if out else 0)  # packets leave in order
        tokens = min(depth, tokens + (t - last) * RATE // 1_000_000)
        last = t
        if tokens < PACKET:  # wait for the missing tokens
            wait = -(-(PACKET - tokens) * 1_000_000 // RATE)
            t, tokens, last = t + wait, tokens + wait * RATE // 1_000_000, t + wait
        tokens -= PACKET
        out.append(t)
    return out


def mbit(nbytes, seconds):
    return nbytes * 8 / seconds / 1e6


times = arrivals()
span = BURSTS * GAP_US / 1e6
print(f"offered: {len(times)} packets, {mbit(len(times) * PACKET, span):.1f} Mbit/s on average, "
      f"in bursts of {PER_BURST} at 1 Gbit/s")
for depth in (15_000, 45_000):
    sent, dropped = police(times, depth)
    out = shape(times, depth)
    delays = [o - t for o, t in zip(out, times)]
    print(f"bucket {depth:,} bytes ({depth // PACKET} packets), rate 8 Mbit/s:")
    print(f"  policed: {len(sent)} sent, {dropped} dropped ({dropped / len(times):.0%}), "
          f"{mbit(len(sent) * PACKET, span):.1f} Mbit/s delivered")
    print(f"  shaped:  {len(out)} sent, 0 dropped, largest delay {max(delays) / 1000:.1f} ms, "
          f"last packet of a burst leaves {(out[PER_BURST - 1] - times[0]) / 1000:.1f} ms after the first arrived")

offered: 150 packets, 3.6 Mbit/s on average, in bursts of 30 at 1 Gbit/s
bucket 15,000 bytes (10 packets), rate 8 Mbit/s:
  policed: 50 sent, 100 dropped (67%), 1.2 Mbit/s delivered
  shaped:  150 sent, 0 dropped, largest delay 29.7 ms, last packet of a burst leaves 30.0 ms after the first arrived
bucket 45,000 bytes (30 packets), rate 8 Mbit/s:
  policed: 150 sent, 0 dropped (0%), 3.6 Mbit/s delivered
  shaped:  150 sent, 0 dropped, largest delay 0.0 ms, last packet of a burst leaves 0.3 ms after the first arrived

With a 15,000-byte bucket, the policer dropped 67 % of a stream whose average was under half the contracted rate: each burst found only ten packets’ worth of tokens. Traffic shaping delivered every packet, the last one of each burst 29.7 ms late. A bucket as large as one burst let both pass everything at once. Size the bucket for the burst, not only the rate.

def token_bucket(arrivals, rate, depth, mode):
    """Police (a list of True/False) or shape (departure times) packets with one token bucket.

    arrivals: (time_us, size_bytes) pairs in time order; rate: bytes a second; depth: bytes.
    """
    scale = 1_000_000              # tokens are kept in micro-bytes: whole numbers, exact arithmetic
    tokens = depth * scale         # the bucket starts full
    last = 0
    out = []
    for time_us, size in arrivals:
        # Replace these lines: add the tokens earned since `last`, then send, drop or delay the packet.
        out.append(True if mode == "police" else time_us)
    return out

from bucket import token_bucket

R = 1_000_000  # bytes a second: one byte of tokens per microsecond


def test_police_a_burst():
    """sends what the full bucket covers and drops the rest of a burst"""
    burst = [(0, 1_500)] * 5
    assert token_bucket(burst, R, 3_000, "police") == [True, True, False, False, False]
    assert token_bucket(burst, R, 7_500, "police") == [True] * 5


def test_police_refills_over_time():
    """earns rate bytes a second, never more than the depth"""
    pkts = [(0, 1_500), (0, 1_500), (1_499, 1_500), (1_500, 1_500), (100_000, 1_500), (100_000, 1_500), (100_000, 1_500)]
    assert token_bucket(pkts, R, 3_000, "police") == [True, True, False, True, True, True, False]


def test_police_spends_nothing_on_a_drop():
    """a dropped packet leaves the tokens for the next one"""
    pkts = [(0, 1_000), (0, 1_500), (0, 1_000)]
    assert token_bucket(pkts, R, 2_000, "police") == [True, False, True]


def test_shape_delays_instead_of_dropping():
    """holds packets until the tokens are there, in order, rounding waits up"""
    burst = [(0, 1_500)] * 4
    assert token_bucket(burst, R, 3_000, "shape") == [0, 0, 1_500, 3_000]
    slow = [(0, 1_000), (0, 1_000), (10, 1_000)]
    assert token_bucket(slow, 3_000, 1_000, "shape") == [0, 333_334, 666_668]
    small_behind_big = [(0, 1_500), (0, 1_500), (100, 100)]  # the small packet must wait its turn
    assert token_bucket(small_behind_big, R, 1_500, "shape") == [0, 1_500, 1_600]


def test_shape_conforming_traffic_and_oversized_packets():
    """does not delay traffic within the rate, and refuses a packet larger than the bucket"""
    steady = [(i * 2_000, 1_500) for i in range(5)]
    assert token_bucket(steady, R, 1_500, "shape") == [0, 2_000, 4_000, 6_000, 8_000]
    try:
        token_bucket([(0, 9_000)], R, 1_500, "shape")
    except ValueError:
        pass
    else:
        raise AssertionError("a 9,000-byte packet can never fit a 1,500-byte bucket")

Schedulers and queue managers, by name

• FIFO keeps one queue and sends packets in the order they arrived.
• Strict priority always empties the higher-priority queues first.
• Round robin lets the queues take turns; deficit round robin (DRR) counts bytes, so large packets earn no extra share.
• Weighted fair queueing (WFQ) sends packets in the order a bit-by-bit weighted share of the link would finish them.
• RED drops packets at random as the average queue length grows, before the buffer is full.
• CoDel drops when packets have waited longer than a target time for a while.
• FQ-CoDel gives each flow a queue of its own, served by DRR, and runs CoDel in each (RFC 8290).

Four schedulers on one link, run and measured Pro: opens with a Pro, Premium or Ultimate pass

Marks that survive the path: DSCP plans, trust and Wi-Fi Pro: opens with a Pro, Premium or Ultimate pass

Owning the queue: shaping below the bottleneck and AQM, measured Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• QoS only acts where a queue forms, usually at the slowest link; the delay there is the bytes waiting divided by the link’s rate.
• DiffServ marks packets with a 6-bit DSCP: DF 0 for best effort, EF 46 for low delay, AF11 to AF43 for assured classes, LE 1 for spare capacity. Each network decides whether to trust a mark.
• A token bucket with rate r and depth b polices by dropping or re-marking the excess and shapes by delaying it; a bucket smaller than the bursts drops traffic even when the average rate is low.
• Schedulers decide who waits: FIFO, strict priority, round robin and DRR, and WFQ; queue managers such as RED, CoDel and FQ-CoDel keep the queue itself short.