Project 3: Network Packet Buffer / Traffic Shaper

Build a userspace packet buffer with backpressure, priority queues, and rate limits.

Quick Reference

Attribute Value
Difficulty Advanced
Time Estimate 1-2 weeks
Language C
Prerequisites C, basic networking concepts
Key Topics ring buffers, backpressure, priority queues

1. Learning Objectives

By completing this project, you will:

  1. Implement a lock-free ring buffer with wrap-around arithmetic.
  2. Apply backpressure when the buffer is full.
  3. Add priority queues for traffic classes.
  4. Implement rate limiting and basic metrics.

2. Theoretical Foundation

2.1 Core Concepts

  • Ring buffers: Fixed-size circular arrays with O(1) enqueue/dequeue.
  • Backpressure: Feedback that slows producers to prevent overflow.
  • Priority queues: Heaps allow higher-priority traffic to jump ahead.

2.2 Why This Matters

Buffers decide whether systems are stable or collapse under load. Understanding them is core to networking.

2.3 Historical Context / Background

Most network stacks use ring buffers in NIC drivers and kernel queues for their speed and cache locality.

2.4 Common Misconceptions

  • “Bigger buffers solve everything”: They increase latency and hide problems.
  • “Linked lists are fine”: They are slower and less cache-friendly than arrays.

3. Project Specification

3.1 What You Will Build

A userspace traffic shaper that accepts packet-like inputs, buffers them, and outputs at a controlled rate with priority handling.

3.2 Functional Requirements

  1. Implement a ring buffer for packets.
  2. Apply backpressure when full (drop or block).
  3. Support at least two priority classes.
  4. Rate limit output using a token bucket or fixed interval.

3.3 Non-Functional Requirements

  • Performance: O(1) enqueue/dequeue.
  • Reliability: No buffer overrun.
  • Usability: Metrics for drops and throughput.

3.4 Example Usage / Output

$ ./traffic_shaper --rate 1000 --buffer 4096
Packets in: 10000
Packets out: 9500
Drops: 500

3.5 Real World Outcome

You will inject bursts and observe smoothing and drops based on buffer capacity:

$ ./traffic_shaper --rate 1000 --buffer 4096
Packets in: 10000
Packets out: 9500
Drops: 500

4. Solution Architecture

4.1 High-Level Design

input -> enqueue ring -> scheduler -> dequeue -> rate limit -> output

4.2 Key Components

Component Responsibility Key Decisions
Ring buffer Store packets Fixed-size array
Priority queue Pick next packet Heap per class
Rate limiter Control output rate Token bucket
Metrics Track drops and latency Counters

4.3 Data Structures

typedef struct {
    uint8_t *data;
    size_t len;
    int priority;
} packet_t;

4.4 Algorithm Overview

Key Algorithm: Enqueue/Dequeue

  1. If buffer full, apply backpressure policy.
  2. Enqueue packet with wrap-around index.
  3. Dequeue in priority order.

Complexity Analysis:

  • Time: O(1) enqueue, O(log n) for priority selection
  • Space: O(n) buffer

5. Implementation Guide

5.1 Development Environment Setup

gcc --version

5.2 Project Structure

project-root/
├── src/
│   ├── ring.c
│   ├── shaper.c
│   └── main.c
└── README.md

5.3 The Core Question You’re Answering

“How do you keep traffic stable when bursts exceed output capacity?”

5.4 Concepts You Must Understand First

Stop and research these before coding:

  1. Ring buffer arithmetic
  2. Priority queue basics
  3. Backpressure vs dropping

5.5 Questions to Guide Your Design

Before implementing, think through these:

  1. Should you drop new packets or oldest packets when full?
  2. How do you avoid starvation of low-priority traffic?
  3. How will you simulate packets for testing?

5.6 Thinking Exercise

Buffer overflow scenario

If input rate is 10x output, what should happen over 60 seconds? Sketch drop rates and latency.

5.7 The Interview Questions They’ll Ask

Prepare to answer these:

  1. “What is backpressure and why is it important?”
  2. “Why are ring buffers popular in systems code?”
  3. “How do you avoid starvation in priority queues?”

5.8 Hints in Layers

Hint 1: Use power-of-two sizes It simplifies modulo with bit masks.

Hint 2: Start without priority Implement FIFO first, then add priority.

Hint 3: Use token bucket Tokens accumulate at rate and allow bursts.

5.9 Books That Will Help

Topic Book Chapter
Ring buffers “The Linux Programming Interface” Ch. 44
Priority queues “Algorithms” Ch. 2.4
Backpressure “Designing Data-Intensive Applications” Ch. 11

5.10 Implementation Phases

Phase 1: Foundation (3-4 days)

Goals:

  • Ring buffer working for FIFO.

Tasks:

  1. Implement enqueue/dequeue.
  2. Add overflow policy.

Checkpoint: FIFO works under load.

Phase 2: Core Functionality (4-5 days)

Goals:

  • Add priority queues and rate limiting.

Tasks:

  1. Implement priority selection.
  2. Add token bucket.

Checkpoint: High priority traffic passes first.

Phase 3: Polish & Edge Cases (2-3 days)

Goals:

  • Add metrics and fairness tweaks.

Tasks:

  1. Track drops, latency, throughput.
  2. Add weighted priorities.

Checkpoint: Output stable across bursts.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Buffer overflow drop-new vs drop-old drop-new Preserves FIFO order
Rate limit fixed interval vs token bucket token bucket Handles bursts

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Ring buffer Wrap-around Fill and drain
Priority Order correctness Mixed priorities
Backpressure Full buffer Drop counts

6.2 Critical Test Cases

  1. Buffer wrap-around preserves order.
  2. High-priority packets are sent first.
  3. Drops occur when buffer full.

6.3 Test Data

Packets: 1000, priority mix

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
Off-by-one in ring Data corruption Use head/tail invariants
Priority starvation Low-priority never sent Add weights
Time drift Rate unstable Use monotonic clock

7.2 Debugging Strategies

  • Log head/tail indices on overflow.
  • Add assertions for buffer size invariants.

7.3 Performance Traps

Using malloc per packet adds overhead; use a fixed pool.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add CLI to switch drop policy.
  • Add a stats-only mode.

8.2 Intermediate Extensions

  • Add fairness (weighted round-robin).
  • Add latency histogram.

8.3 Advanced Extensions

  • Implement lock-free multi-producer/consumer.
  • Integrate with real UDP sockets.

9. Real-World Connections

9.1 Industry Applications

  • Traffic shaping in routers, proxies, and message queues.
  • tc (Linux traffic control): https://man7.org/linux/man-pages/man8/tc.8.html
  • DPDK: https://www.dpdk.org

9.3 Interview Relevance

  • Backpressure and ring buffers are common systems topics.

10. Resources

10.1 Essential Reading

  • Ring buffer notes in TLPI Ch. 44
  • token bucket algorithm references

10.2 Video Resources

  • Networking buffering talks (search “ring buffer network”)

10.3 Tools & Documentation

  • clock_gettime(2) - man 2 clock_gettime

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain ring buffer wrap-around.
  • I can explain backpressure.
  • I can describe priority queue behavior.

11.2 Implementation

  • Ring buffer is correct under load.
  • Priority scheduling works.
  • Rate limiting behaves as expected.

11.3 Growth

  • I can extend to real sockets.
  • I can tune for fairness and latency.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Ring buffer with backpressure and FIFO output.

Full Completion:

  • Priority classes and rate limiting.

Excellence (Going Above & Beyond):

  • Real network integration and weighted scheduling.

This guide was generated from SPRINT_4_5_REAL_WORLD_PROJECTS.md. For the complete learning path, see the parent directory.