Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Congestion control and QoS

Congestion control and Quality of Service (QoS) cover how networks avoid and manage overload (congestion) and how they guarantee or differentiate traffic performance (delay, throughput, jitter, loss).

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Congestion control and QoS are used by engineers when designing and operating networks so that many users can share links without the network slowing to a crawl, and so that delay-sensitive applications (VoIP, video) get predictable service. Routers, switches and transport protocols (TCP, RSVP, DiffServ) implement these controls in data centres, ISPs and campus networks.

Key ideas

Start from first principles and definitions (I define each term the first time I use it):

  • Congestion — the condition in a network when the offered load (total incoming packet rate) approaches or exceeds the capacity of some network resource (link or router), causing packet queues to grow and performance (throughput, delay, loss) to degrade.
  • Quality of Service (QoS) — any set of techniques that control traffic forwarding or resource allocation so that different traffic flows receive different performance (latency, jitter, loss, throughput) according to policy.
  • Throughput — the rate (bits per second or packets per second) at which useful data is delivered to the receiver.
  • Delay (latency) — the time for a packet to traverse the network (seconds); includes transmission, propagation, processing and queueing delays.
  • Jitter — variation in packet delay.
  • Packet loss — fraction of packets dropped; often caused by queue overflow in routers during congestion.
  • RTT (Round-Trip Time) — time for a packet to go from sender to receiver and for an acknowledgement to return.
  • Window (congestion window, cwnd) — sender-side control limiting the number of unacknowledged bytes in flight; used by TCP congestion control.

Why congestion happens: queues build at routers when arrival rate λ exceeds service capacity μ (or momentarily exceeds it). When queues fill, packets are dropped; persistent overload can lead to congestion collapse (throughput falls dramatically while load remains high).

Basic router-side controls:

  • Drop-tail: simplest queue; drop arriving packets when buffer full. Easy but causes global synchronization and unfairness.
  • RED (Random Early Detection): probabilistically drop or mark packets before buffer is full to signal senders and avoid synchronization, based on average queue length; can mark ECN instead of dropping when enabled. Configure min-threshold, max-threshold, and max-drop-probability.
  • Fair queuing (FQ) and Weighted Fair Queuing (WFQ): approximate fair sharing of link capacity between flows; WFQ gives flows weights to enforce proportional bandwidth.
  • Priority Queuing / Class-based Queuing: put packets into classes with strict or weighted priority scheduling. Strict priority risks starvation of low-priority traffic; practical weighted schedulers like WRR/DRR approximate WFQ.

Traffic conditioning at boundary and edge:

  • Policing: drop or mark packets that exceed a configured rate (enforces contract); no buffering to absorb bursts.
  • Shaping: buffer and delay excess packets to smooth bursts (uses token-bucket or leaky-bucket mechanisms).

Token bucket (define): Token bucket — tokens arrive at a constant rate r into a bucket of capacity B tokens; to send a packet of size s you must remove s tokens. This enforces long-term rate r but allows bursts up to B.

Leaky bucket (define): Leaky bucket — a queue with constant-rate output; arrivals above output rate are queued up to buffer capacity and excess are dropped (used for shaping).

Transport-side congestion control (TCP family):

  • AIMD (Additive Increase Multiplicative Decrease) — increase cwnd by a constant (additive) each RTT (probing for extra bandwidth), decrease cwnd multiplicatively when loss or congestion is detected. This gives stability and fairness.
  • TCP Reno behaviours: Slow start (exponential growth of cwnd until first loss or threshold), Congestion avoidance (linear increase), Fast retransmit and Fast recovery (respond to duplicate ACKs without returning to slow start). On retransmission timeout (RTO), cwnd is reset to 1 MSS and ssthresh is set to half the flight size.
  • Important qualitative result: AIMD converges to a fair sharing among flows that see similar RTTs and loss conditions; if RTTs differ, short RTT flows get more bandwidth.

QoS architectures:

  • Integrated Services (IntServ) — per-flow resource reservation (RSVP) to guarantee bandwidth/latency; high overhead in core routers. Defines Guaranteed Service (strict delay/loss bounds) and Controlled Load (service approximating a lightly loaded best-effort network).
  • Differentiated Services (DiffServ) — class-based marking (DSCP) at the edge and per-class forwarding behaviour in the core (scalable). DSCP is a 6-bit field in the IP header; common PHBs include EF (expedited forwarding, low loss/latency) and AF classes with different drop precedences.
  • Admission control — accept or reject new flows based on available resources (used with IntServ and in some QoS policies).

Simple queueing theory applied to congestion:

  • For a single server router with Poisson arrivals and exponential service (M/M/1), utilization ρ = λ/μ. Average queue length Lq = ρ^2/(1-ρ), average waiting time Wq = ρ/(μ−λ), and average delay in system W = 1/(μ-λ) (including service). Average number in system L = ρ/(1−ρ). When ρ → 1, delays explode and congestion occurs.

Exact steps universities often ask to derive or draw:

  • Draw a sawtooth plot of TCP cwnd (y-axis = cwnd in segments, x-axis = time). Label slow start exponential rise region, linear increase in congestion avoidance, point of loss, and multiplicative drop to half.
  • For RED, draw queue length on x-axis and packet drop probability on y-axis showing min-threshold, max-threshold and linear increase region up to p_max.

Assumptions to state in exam answers: traffic models (Poisson, fluid), per-packet vs per-byte fairness, that packet loss signals congestion for TCP (not only link errors), and that QoS guarantees require admission control plus isolation (scheduling/policing).

Formulas

ρ = λ / μ — ρ is utilization (dimensionless); λ is arrival rate (packets/s); μ is service rate (packets/s); applies to single-server queueing.

W = 1 / (μ - λ) — W is mean time in system for M/M/1 (s); applies when arrivals are Poisson and service times exponential; μ>λ required.

L = λ·W — Little's law; L is average number of items in system (packets), λ arrival rate (packets/s), W average time (s); model-independent. BDP = bandwidth · RTT — Bandwidth–Delay Product; bytes or bits in flight needed to fully utilize a path; cwnd should be at least BDP.

For TCP Reno (approximate average throughput; Mathis et al. model): Throughput ≈ 1.22 · MSS / (RTT · sqrt(p)) — Throughput in bytes/s; MSS is maximum segment size (bytes); RTT (s); p loss probability (fraction of packets lost); applies under assumptions of long-lived TCP flow, steady state, and loss as congestion signal.

Relation between loss p and window W (segments) for sawtooth AIMD: p ≈ 8 / (3 · W^2) — p dimensionless; W is peak cwnd in segments; used in derivation of the Mathis formula.

Token bucket constraints: Maximum burst bytes = B; Maximum burst duration = B / r — B tokens (bytes) is bucket capacity; token arrival rate r (bytes/s) is sustained rate.

Scheduling service share in GPS (fluid model): Rate_i = (w_i / Σ w_j) · C — flow i receives instantaneous service rate proportional to its weight w_i of link capacity C (bps).

Worked examples

  1. TCP throughput numeric (use Mathis formula) Given: MSS = 1460 bytes, RTT = 50 ms = 0.05 s, measured packet loss p = 0.001 (0.1%). Compute average throughput. Step 1: Write formula: Throughput ≈ 1.22 · MSS / (RTT · sqrt(p)). Step 2: Insert numbers: Throughput ≈ 1.22 · 1460 bytes / (0.05 s · sqrt(0.001)). Step 3: sqrt(0.001) = 0.0316228. Numerator = 1.22 × 1460 = 1781.2 bytes. Denominator = 0.05 × 0.0316228 = 0.00158114 s. Step 4: Throughput = 1781.2 / 0.00158114 ≈ 1,126,900 bytes/s ≈ 9,015,200 bits/s ≈ 9.02 Mbps. (Answer rounded; show units: bytes → bits).

  2. Token-bucket shaping example Edge device enforces token bucket with rate r = 512 kbps and bucket size B = 64 kB. Sender wants to send a burst of 100 kB instantly. How much of the burst can be sent immediately and how long to drain remainder at rate r? Step 1: Max immediate bytes = B = 64 kB can be sent at once. Step 2: Remaining = 100 kB − 64 kB = 36 kB. Step 3: Token refill rate r = 512 kbps = 64 kB/s (using decimal units: k=1000; 512,000 b/s ÷ 8 = 64,000 B/s). Time to send remaining 36 kB at sustained rate = 36 kB / 64 kB/s = 0.5625 s. Answer: 64 kB sent instantly; remaining 36 kB takes 0.5625 s to be transmitted at shaped rate.

  3. M/M/1 queue numeric Router processes packets at μ = 10,000 packets/s. Average arrival λ = 9,000 packets/s. Compute utilization ρ, average time in system W, and average queue length L. Step 1: ρ = λ/μ = 9000/10000 = 0.9. Step 2: W = 1/(μ − λ) = 1/(10000 − 9000) = 1/1000 s = 0.001 s (this is mean time in system including service). Step 3: L = λ·W = 9000 × 0.001 = 9 packets on average in system. Answer: ρ = 0.9, W = 1 ms, L = 9 packets.

Common mistakes

  • Thinking RED always reduces loss: wrong parameter choices (min/max thresholds, p_max) make it act like drop-tail.
  • Mixing up policing and shaping: policing drops/exceeds immediately; shaping buffers to smooth bursts.
  • Ignoring RTT dependence: AIMD gives advantage to short-RTT flows; many students forget to mention this in fairness discussions.
  • Using bytes and segments interchangeably without converting MSS when applying throughput formulas.

For your exam

Typical question types: definitions (define congestion, QoS, RED, AIMD), short notes (TCP congestion control steps, token bucket vs leaky bucket), derivations (derive Mathis throughput approx from sawtooth model), numericals (compute throughput given MSS, RTT, loss; compute queue delay given λ, μ), and diagrams (draw TCP cwnd sawtooth; RED drop-probability graph).

What a full-marks answer includes:

  • Clear definitions of terms used, explicit assumptions, labelled diagrams where asked, step-by-step algebra (show units), and final numeric answers with correct units.
  • For protocols, state the sequence of events (e.g., slow start doubles cwnd each RTT until ssthresh; on triple duplicate ACK do fast retransmit and halve cwnd) and the reason (avoid collapse, probe for bandwidth).

Quick check

  1. What does AIMD stand for and why is it used?
  2. In token bucket, what two parameters control the traffic profile?
  3. For an M/M/1 queue, what happens to average delay as utilization ρ → 1? Answers: AIMD = Additive Increase Multiplicative Decrease; it probes for bandwidth and responds to congestion while converging to fairness. Token bucket parameters: token rate r and bucket capacity B. As ρ → 1, average delay → ∞ (grows without bound).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?