Project 3: Network Packet Buffer and Traffic Shaper

Build a userspace packet buffer with backpressure, priority scheduling, and rate shaping.

Quick Reference

Attribute	Value
Difficulty	Intermediate
Time Estimate	15-25 hours
Main Programming Language	C (Alternatives: Rust)
Alternative Programming Languages	Rust
Coolness Level	Level 3
Business Potential	Service and support
Prerequisites	C arrays, basic networking, queues
Key Topics	Ring buffers, backpressure, priority queues, shaping

1. Learning Objectives

By completing this project, you will:

Implement a lock-free ring buffer for packet storage.
Apply backpressure policies when buffers reach capacity.
Implement priority scheduling for mixed traffic classes.
Shape outgoing traffic with a token bucket rate limiter.
Measure latency and throughput under bursty load.

2. All Theory Needed (Per-Concept Breakdown)

Ring Buffers and Circular Indexing

Fundamentals

A ring buffer is a fixed-size array used as a queue with wrap-around indexing. It is ideal for streaming data because it avoids reallocations and provides O(1) enqueue and dequeue. The buffer uses two indices: head (read) and tail (write). When tail catches up to head, the buffer is full. When head equals tail, it is empty. To disambiguate full vs empty, you can reserve one slot or track a count. Ring buffers are common in networking because packets arrive in bursts and must be buffered quickly with minimal overhead. Understanding wrap-around arithmetic and the invariants that keep the buffer consistent is essential to implementing stable buffering and backpressure behavior.

Deep Dive into the concept

A ring buffer turns a linear array into a circular queue. The key invariant is that each index is always taken modulo the capacity. The buffer supports enqueue by writing at tail and advancing it, and dequeue by reading at head and advancing it. A simple implementation reserves one slot to distinguish full from empty: the buffer is full when (tail + 1) % capacity == head and empty when tail == head. This reduces effective capacity by one but simplifies logic and avoids tracking a separate count. Another approach uses a count variable that increments on enqueue and decrements on dequeue, which allows full use of all slots but requires careful updates under concurrency.

In networking, the ring buffer must be fast. It should avoid branches and keep data contiguous to improve cache locality. Because packets can be variable-length, you often store pointers to packet structures in the ring rather than the raw bytes. Each packet structure contains metadata like length, priority, and timestamp. This keeps the ring buffer lightweight while allowing packet data to live in separate memory pools. The ring buffer itself can be a simple array of packet_t*. When you enqueue, you check if the buffer is full; if so, you trigger backpressure or drop policies. When you dequeue, you return the packet pointer and let the scheduler decide which packet to send next.

If you want to make the buffer lock-free for single-producer/single-consumer, you can use atomic head/tail updates. For this project, a single-threaded design is acceptable, but you should still reason about memory ordering because network IO often involves concurrent producer/consumer patterns. In a single-threaded event loop, head and tail updates are deterministic, and you can avoid atomics. The main point is to understand the invariant and ensure you never overwrite unread data.

Ring buffers are used throughout networking stacks: NIC receive queues, kernel socket buffers, and user-level packet capture systems. They are chosen because they offer fixed memory usage and predictable performance. The drawback is that they cannot grow dynamically; when the buffer is full, you must choose a policy: drop, block, or apply backpressure. This is where the ring buffer connects directly to system stability. A buffer that silently overwrites old data might hide congestion but loses packets. A buffer that blocks too aggressively can stall the system. The correct policy depends on the traffic type and the service guarantees you want to provide. You will explore these tradeoffs in this project by implementing explicit backpressure and priority scheduling.

Another subtle point is index wrap-around and integer overflow. If you use unsigned integers and take modulo capacity, you are safe, but you must ensure capacity is a power of two if you plan to optimize modulo using bit masking. If you do this, you can compute idx = index & (capacity - 1), which is faster than modulo, but only if capacity is a power of two. You should document this in your implementation. If you choose not to enforce power-of-two, use % for correctness. The difference is small for this project but is a real performance decision in high-speed networking.

How this fit on projects

Ring buffers are the backbone of §3.2 Functional Requirements and §4.4 Data Structures. They are implemented in §5.10 Phase 1 and tested in §6.2. Ring buffers also appear in P01-in-memory-cache-lru.md for request buffering and in P04-memory-allocator-debugging.md for free list queues.

Definitions & key terms

ring buffer -> circular queue over a fixed array
head -> index of next element to read
tail -> index of next element to write
wrap-around -> modulo indexing when reaching capacity
single-producer/single-consumer -> concurrency model with one writer and one reader

Mental model diagram

capacity = 8
[0][1][2][3][4][5][6][7]
  ^head        ^tail
wrap-around -> (tail + 1) % 8

How it works (step-by-step, with invariants and failure modes)

Initialize head = 0, tail = 0.
On enqueue, check if full condition holds.
Write item at tail and advance tail.
On dequeue, check if empty condition holds.
Read item at head and advance head.

Invariants: head and tail are always in [0, capacity); buffer is full when next tail equals head; buffer is empty when head equals tail. Failure modes: overwrite unread data or mis-detect full/empty.

Minimal concrete example

bool full = ((tail + 1) % cap) == head;
if (!full) { buf[tail] = pkt; tail = (tail + 1) % cap; }

Common misconceptions

“Ring buffers can grow” -> they are fixed-size by design.
“Full vs empty is obvious” -> you need an explicit rule or count.
“Modulo is always cheap” -> power-of-two optimizations matter at scale.

Check-your-understanding questions

Why do many ring buffers reserve one empty slot?
What breaks if head and tail wrap incorrectly?
Why might you store packet pointers instead of raw bytes?

Check-your-understanding answers

It disambiguates full from empty without an extra counter.
You can overwrite unread packets or read invalid data.
Packet sizes vary; pointers keep the ring fixed-size and fast.

Real-world applications

NIC receive queues and kernel socket buffers.
High-performance logging pipelines.

Where you’ll apply it

This project: §3.2, §4.4, §5.10 Phase 1.
Also used in: P01-in-memory-cache-lru.md.

References

Computer Systems: A Programmer’s Perspective, Ch. 6
Linux kernel ring buffer implementations

Key insights

Ring buffers provide predictable, fixed-size buffering with O(1) operations, but require explicit policy when full.

Summary

The ring buffer is the core queue in your packet system. It is fast and memory-stable, but requires precise wrap-around logic and clear full/empty rules.

Homework/Exercises to practice the concept

Implement a ring buffer with power-of-two capacity and mask indexing.
Write tests for wrap-around behavior and full/empty detection.

Solutions to the homework/exercises

Use idx = index & (cap - 1) with cap as power-of-two.
Enqueue and dequeue around the boundary, verify correctness.

Backpressure and Congestion Control Policies

Fundamentals

Backpressure is a system’s way of signaling producers to slow down when buffers are full. In networking, if packets arrive faster than they can be transmitted, you must choose a policy: drop packets, block producers, or signal upstream. Backpressure prevents buffers from growing unbounded and keeps latency stable. In a user-space packet buffer, you can implement backpressure by returning a “buffer full” error to the producer, delaying acceptance, or dropping lower-priority packets. The goal is to protect the system from overload while preserving the most important traffic.

From a systems perspective, you should be able to explain the invariants this concept maintains, the resources it consumes (CPU, memory, IO), and the typical failure modes when it is misused. This basic framing will help you reason about correctness before you optimize or extend the design.

Deep Dive into the concept

Backpressure is not just a boolean; it is a strategy. In real systems, uncontrolled buffers create “bufferbloat,” where latency grows dramatically under load. A fixed-size ring buffer with a drop policy can avoid unbounded latency but may lose data. A blocking policy preserves data but may stall producers and create head-of-line blocking. A backpressure signal can be explicit (returning an error code) or implicit (slowing down reads so the producer blocks). In kernel networking, backpressure can be implemented with socket send buffers and TCP flow control. In user space, you must implement it yourself.

For this project, define a clear policy when the buffer is full. For example, when full, return a specific error code EAGAIN and increment a drop counter. This models “drop-tail” behavior. Alternatively, you can drop lower-priority packets first (priority-aware dropping). This requires scanning for a lower-priority packet and removing it, which is more expensive but provides better service for high-priority traffic. Another option is to block the producer by not reading from its socket until space becomes available. This is a form of pushback and can be implemented by removing the socket from the read set in your event loop.

Backpressure connects directly to system stability. If you always accept packets, you risk memory growth or high latency. If you always drop, you might lose critical traffic. The correct strategy depends on the service: for real-time audio, you might drop old packets; for file transfer, you might block. By implementing backpressure in this project, you will reason about these tradeoffs and see their impact on latency and throughput.

A good design includes metrics. Track how often backpressure is engaged, how many packets are dropped, and how long the buffer stays full. These metrics help you evaluate the policy. You can also implement hysteresis: only turn off backpressure when the buffer drops below a lower threshold, to prevent oscillation. For example, engage backpressure at 95% capacity and release at 80%. This mimics real congestion control systems and improves stability.

Backpressure also interacts with scheduling. If you prioritize certain traffic, you might apply backpressure only to low-priority producers. This can be done by maintaining per-priority queues or by tagging packets with priority and making drop decisions accordingly. The key is to make the policy explicit and deterministic so you can test it. Your deterministic golden path should include a known buffer fill pattern and a predictable drop decision.

You should also think about how backpressure propagates in a pipeline. In real systems, a downstream queue filling up causes upstream components to slow or drop, which prevents cascading overload. In your tool, you can model this by reducing the input rate or pausing reads when backpressure is active. Another practical approach is to implement a "soft" backpressure mode where you still accept packets but mark them as "late" and count them separately. This helps you analyze how often the system would have dropped packets if it were strict. The broader lesson is that backpressure is not just a local rule; it is a systemic mechanism that shapes end-to-end latency and loss.

How this fit on projects

Backpressure is required in §3.2 and demonstrated in §3.7. It is implemented in §5.10 Phase 2 and tested in §6.2. It is also relevant to P01-in-memory-cache-lru.md for request throttling.

Definitions & key terms

backpressure -> signal that slows producers when buffers are full
drop-tail -> drop newest packet when buffer is full
head-of-line blocking -> one slow producer stalls others
bufferbloat -> excessive buffering leading to high latency
hysteresis -> separate thresholds for engage/release

Mental model diagram

producer -> [buffer 95% full] -> backpressure ON -> producer slows
producer -> [buffer 80% full] -> backpressure OFF

How it works (step-by-step, with invariants and failure modes)

Measure buffer occupancy each enqueue.
If occupancy >= high watermark, signal backpressure.
Enqueue only if policy allows; otherwise drop or block.
When occupancy <= low watermark, release backpressure.

Invariants: occupancy never exceeds capacity; backpressure state transitions are deterministic. Failure modes: oscillation or starvation of low-priority traffic.

Minimal concrete example

if (count >= high_mark) backpressure = true;
if (count <= low_mark) backpressure = false;
if (backpressure) return EAGAIN;

Common misconceptions

“Backpressure is just dropping” -> it can be blocking or signaling too.
“More buffering is always good” -> it often increases latency.
“One policy fits all” -> policies depend on traffic type.

Check-your-understanding questions

Why can large buffers increase latency?
What is the difference between drop-tail and priority drop?
How does hysteresis improve stability?

Check-your-understanding answers

Packets wait longer in the queue, leading to queueing delay.
Drop-tail drops newest packets; priority drop preserves high-priority traffic.
It prevents rapid on/off toggling when occupancy hovers near threshold.

Real-world applications

TCP flow control and window management.
Router queue management (RED, CoDel).

Where you’ll apply it

This project: §3.2, §3.7, §5.10 Phase 2.
Also used in: P01-in-memory-cache-lru.md for request throttling.

References

Computer Networks (Tanenbaum), congestion control chapters
RFC 2309 (queue management)

Key insights

Backpressure is a stability mechanism that trades acceptance for bounded latency and controlled loss.

Summary

When buffers fill, you must push back. Backpressure policies are the difference between controlled overload and catastrophic latency.

Homework/Exercises to practice the concept

Implement a buffer with high/low watermarks and record backpressure toggles.
Simulate bursty traffic and measure drop counts.

Solutions to the homework/exercises

Track occupancy and log when state changes at thresholds.
Generate bursts exceeding capacity and verify deterministic drop behavior.

Priority Scheduling and Multi-Queue Dispatch

Fundamentals

Priority scheduling ensures that high-priority packets are transmitted before low-priority ones. This is crucial for latency-sensitive traffic like voice or control messages. A simple approach is to maintain separate queues per priority and always dequeue from the highest non-empty queue. Another approach is to use a priority queue (heap) keyed by packet priority. In network systems, strict priority can starve low-priority traffic, so you may need to implement a weighted or round-robin policy. For this project, you will implement strict priority to keep the model clear.

Deep Dive into the concept

Priority scheduling is about aligning transmission order with application requirements. In a packet buffer, you likely have multiple classes of traffic: control, interactive, bulk. If you treat them all equally, bursty bulk traffic can delay control packets and cause visible latency. The simplest fix is strict priority: always serve the highest priority queue first. This is easy to implement with a set of FIFO queues. Each queue can be a ring buffer or a linked list. The scheduler checks the highest priority queue; if it is empty, it checks the next, and so on. This gives predictable latency for high-priority traffic but can starve low-priority traffic under constant high load.

A more balanced approach is weighted round-robin (WRR) or deficit round-robin (DRR). These algorithms allocate a certain number of bytes or packets per class, ensuring fairness. For this project, strict priority is adequate, but you should understand its limitations. If you want to extend the project, you can add WRR as an advanced extension.

The scheduler must integrate with the buffer and backpressure. When the buffer is full, you may decide to drop low-priority packets first, preserving high-priority ones. This policy must be consistent with the scheduler to avoid surprising behavior. For example, if you use strict priority, you should also drop low-priority packets when full, otherwise high-priority packets might be dropped while low-priority packets remain in the buffer. This is a common design rule in networking: scheduling and drop policy should align.

Implementing priority scheduling requires a clear representation of packet priority. You can encode it as an integer (0 = low, 2 = high) and map it to a queue. Each packet struct should contain its priority. When you enqueue, you place it into the corresponding queue. When you dequeue, you check queues in priority order. The scheduler should be called when the transmit path is ready to send a packet. In a user-space simulation, you can model this with a timer or by simply dequeuing at a fixed rate.

An important measurement is per-priority latency. You should track the enqueue timestamp for each packet and compute the time until it is transmitted. This allows you to verify that high-priority traffic sees lower latency. To make this deterministic, you can use a simulated clock in your tests, or you can base it on a fixed tick counter. This aligns with the determinism requirement and ensures reproducible outputs.

Another practical consideration is priority inversion. If a low-priority packet holds a shared resource needed by a high-priority packet, strict priority alone cannot fix the delay. In your project, you can approximate this by treating the buffer itself as the shared resource and ensuring that dequeue does not block on lower-priority state. You can also add a small fairness window, such as "serve at most N high-priority packets in a row before considering medium." This is a light-weight way to avoid starvation without implementing a full weighted scheduler. Even if you do not implement fairness, documenting the tradeoff shows that you understand the limitations of strict priority.

How this fit on projects

Priority scheduling is required in §3.2 and shown in §3.7. It is implemented in §5.10 Phase 2 and tested in §6.2. It is also relevant to P06-capstone-simple-database-engine.md where query scheduling could prioritize transactions.

Definitions & key terms

strict priority -> always serve highest priority first
starvation -> low-priority traffic never gets served
weighted round-robin -> allocate service proportional to weights
deficit round-robin -> byte-based fair scheduling

Mental model diagram

High Q -> [pkt][pkt]
Med  Q -> [pkt]
Low  Q -> [pkt][pkt][pkt]
Scheduler: High -> Med -> Low

How it works (step-by-step, with invariants and failure modes)

Assign a priority to each incoming packet.
Enqueue into the corresponding priority queue.
On transmit, pick the highest non-empty queue.
Dequeue one packet and send it.
Repeat at configured rate.

Invariants: order within each queue is FIFO; higher priority always preempts lower. Failure modes: starvation or incorrect priority tagging.

Minimal concrete example

if (!q_high.empty()) return dequeue(q_high);
if (!q_med.empty()) return dequeue(q_med);
return dequeue(q_low);

Common misconceptions

“Priority scheduling is always fair” -> strict priority can starve.
“One queue is enough” -> mixing priorities defeats the purpose.
“Priority fixes congestion” -> it only orders service, not capacity.

Check-your-understanding questions

Why can strict priority starve low-priority traffic?
How does priority scheduling interact with drop policy?
What would a weighted policy add?

Check-your-understanding answers

If high-priority traffic is continuous, lower queues never drain.
You should drop low priority first to preserve high priority packets.
It guarantees a share of bandwidth for each class.

Real-world applications

QoS in routers and switches.
Audio/video streaming with control channels.

Where you’ll apply it

This project: §3.2, §3.7, §5.10 Phase 2.
Also used in: P06-capstone-simple-database-engine.md.

References

Computer Networks, QoS chapters
RFC 2597 (DiffServ)

Key insights

Priority scheduling improves latency for critical traffic but must be balanced against fairness.

Summary

Separate queues and a clear scheduler make priority behavior explicit and testable, and they integrate with backpressure policies.

Homework/Exercises to practice the concept

Implement strict priority scheduling with three queues.
Add counters for per-priority latency.

Solutions to the homework/exercises

Always check high queue first, then medium, then low.
Record enqueue tick and compute dequeue tick delta.

Token Bucket Rate Shaping

Fundamentals

A token bucket is a rate-limiting algorithm that allows bursts while enforcing an average rate. Tokens accumulate in a bucket at a fixed rate, and each packet consumes tokens proportional to its size. If there are not enough tokens, the packet must wait. This is a common traffic shaping mechanism in networks. By combining a token bucket with your scheduler, you can simulate a fixed transmit rate and observe how buffers behave under bursts.

Deep Dive into the concept

The token bucket algorithm maintains a bucket with a maximum capacity B tokens and a refill rate R tokens per second. Tokens represent permission to send bytes (or packets). When a packet of size S is ready to send, the scheduler checks if at least S tokens are available. If so, the packet is sent and S tokens are removed. If not, the packet waits until enough tokens accumulate. Because tokens accumulate over time, the system can send a burst of packets if it has accumulated tokens during idle periods. This is why token buckets allow bursts while enforcing average rate.

Implementing a token bucket requires a time source. In a deterministic simulation, you can model time as discrete ticks. Each tick adds a fixed number of tokens up to capacity. In a real system, you would use a high-resolution clock and compute elapsed time since the last update. For determinism, define a fixed tick interval and make the refill deterministic. This ensures reproducible results and aligns with the determinism requirement. The token bucket can be per-priority or global. A global bucket limits overall bandwidth, while per-priority buckets enforce class-based limits.

A key design choice is the unit of tokens. You can define one token as one byte, which makes the algorithm accurate for variable packet sizes. If you define one token per packet, you ignore size differences, which might be acceptable for this project if packets are uniform. A realistic system uses bytes. Another design choice is how to handle packets that are larger than the bucket capacity. The simplest approach is to allow them only when the bucket is full, but this can cause long delays. You can also cap packet size or split large packets, but that is out of scope. For this project, choose a max packet size that fits in the bucket.

The token bucket interacts with priority scheduling. You can allow high-priority packets to bypass the bucket (dangerous) or use separate buckets per priority. For simplicity, you can apply a single global bucket after scheduling. This means you pick the next packet based on priority, then check if tokens are available; if not, you wait. This preserves priority ordering while enforcing rate limits. The outcome is a predictable rate-limited flow with priority-aware ordering.

In terms of measurement, you should record the effective throughput and compare it to the configured rate. You should also measure queueing delay: when bursts arrive, the buffer fills, and packets wait until tokens are available. This demonstrates how rate limiting interacts with buffering and backpressure. The key insight is that shaping controls the output rate but can increase latency under load. This is a fundamental systems tradeoff.

Implementation details matter here. If you base the token bucket on real time, you must handle clock drift and the possibility of large jumps (for example, if the process is paused). A robust implementation clamps the added tokens to the maximum capacity and ensures that negative time deltas are ignored. In a deterministic test harness, you can avoid this by using a monotonic tick counter and fixed increments. This also makes throughput calculations exact and testable. By explicitly modeling time, you will see that shaping is about controlling time-based resource allocation, not just counting packets.

How this fit on projects

Token bucket shaping is required in §3.2 and shown in §3.7. It is implemented in §5.10 Phase 3 and tested in §6.2. It also appears in P02-log-structured-kv-store.md as an analogy to write throttling.

Definitions & key terms

token bucket -> rate limiter with burst allowance
refill rate -> tokens added per time unit
bucket capacity -> maximum tokens stored
shaping -> delaying packets to enforce rate

Mental model diagram

Tokens: [######] (capacity)
Packet size: 3 tokens
If tokens >= 3 -> send, else wait

How it works (step-by-step, with invariants and failure modes)

Initialize bucket with capacity B and rate R.
On each tick, add tokens up to capacity.
Pick next packet by priority.
If tokens >= size, send and subtract tokens.
If not, wait and accumulate tokens.

Invariants: tokens never exceed capacity; packets are sent only when tokens sufficient. Failure modes: time calculation errors or negative tokens.

Minimal concrete example

tokens = min(cap, tokens + rate * dt);
if (tokens >= pkt->size) { tokens -= pkt->size; send(pkt); }

Common misconceptions

“Rate limiting prevents bursts” -> token bucket allows bursts up to capacity.
“One token per packet is enough” -> ignores size differences.
“Shaping reduces latency” -> it usually increases latency under load.

Check-your-understanding questions

Why does a token bucket allow bursts?
What happens if packet size exceeds bucket capacity?
How does shaping interact with backpressure?

Check-your-understanding answers

Tokens accumulate during idle time, allowing a burst.
The packet may be delayed indefinitely unless you cap size or special-case it.
Shaping slows output, which can cause buffers to fill and trigger backpressure.

Real-world applications

ISP bandwidth shaping.
QoS rate limiting in routers and switches.

Where you’ll apply it

This project: §3.2, §3.7, §5.10 Phase 3.
Also used in: P02-log-structured-kv-store.md analogies.

References

RFC 2697 (Single Rate Three Color Marker)
Network traffic shaping literature

Key insights

Token buckets enforce average rate while allowing controlled bursts, which reveals how buffering and latency interact.

Summary

A token bucket is a deterministic way to shape traffic. It trades latency for predictable throughput and integrates naturally with priority scheduling.

Homework/Exercises to practice the concept

Implement a token bucket simulator with fixed ticks and verify throughput.
Vary bucket capacity and observe burst behavior.

Solutions to the homework/exercises

Use a loop that adds tokens per tick and sends when possible; compare sent bytes to rate.
Larger buckets allow bigger bursts before rate limiting dominates.

3. Project Specification

3.1 What You Will Build

A userspace packet buffering and shaping tool that accepts simulated packets, enqueues them into a ring buffer, applies backpressure when full, schedules packets by priority, and enforces an output rate with a token bucket. The tool prints deterministic logs showing enqueue, dequeue, drops, and rate limiting.

3.2 Functional Requirements

Enqueue packets into a fixed-size ring buffer.
Apply backpressure when buffer is full (drop or reject).
Support at least three priority levels.
Schedule transmission by strict priority.
Enforce an output rate using token bucket shaping.
Expose stats: drops, backpressure events, latency per priority.

3.3 Non-Functional Requirements

Performance: O(1) enqueue/dequeue, constant memory usage.
Reliability: no buffer corruption; deterministic behavior.
Usability: clear CLI output and reproducible demo.

3.4 Example Usage / Output

$ ./packet_buffer --rate 5mbps --buffer 1024 --drop drop-tail
[buf] capacity=1024 packets rate=5mbps
[buf] enqueue: 100 packets
[buf] enqueue: 500 packets
[buf] buffer full, backpressure ON
[buf] drop: priority=LOW packet_id=9
[buf] dequeue: priority=HIGH packet_id=42

3.5 Data Formats / Schemas / Protocols

Input format (simulated packet lines):

<id> <size_bytes> <priority>

Example: 42 512 HIGH

3.6 Edge Cases

Buffer full triggers deterministic drop or reject policy.
Packets larger than bucket capacity return error.
Priority mismatch returns ERR bad_priority.

3.7 Real World Outcome

3.7.1 How to Run (Copy/Paste)

cc -O2 -Wall -Wextra -o packet_buffer src/main.c src/ring.c src/scheduler.c src/shaper.c
./packet_buffer --rate 5mbps --buffer 8 --drop drop-tail --seed 1234

3.7.2 Golden Path Demo (Deterministic)

$ ./packet_buffer --rate 1mbps --buffer 4 --seed 1
[buf] capacity=4 packets rate=1mbps
[buf] enqueue: id=1 prio=HIGH size=256
[buf] enqueue: id=2 prio=LOW size=256
[buf] enqueue: id=3 prio=HIGH size=256
[buf] dequeue: id=1 prio=HIGH
[buf] dequeue: id=3 prio=HIGH
[buf] dequeue: id=2 prio=LOW

3.7.3 Failure Demo (Deterministic)

$ ./packet_buffer --rate 1mbps --buffer 2 --seed 1
[buf] enqueue: id=1 prio=LOW size=2048
ERR packet_too_large
[buf] enqueue: id=2 prio=LOW size=256
[buf] enqueue: id=3 prio=LOW size=256
ERR buffer_full

Exit codes:

0 on normal exit
2 on invalid arguments

4. Solution Architecture

4.1 High-Level Design

Input -> Ring Buffer -> Priority Scheduler -> Token Bucket -> Output

4.2 Key Components

4.4 Data Structures (No Full Code)

struct packet {
    uint64_t id;
    uint32_t size;
    uint8_t priority;
    uint64_t enqueue_tick;
};

4.4 Algorithm Overview

Key Algorithm: Priority dequeue with shaping

Select highest non-empty priority queue.
Check token bucket; if enough, dequeue and send.
Otherwise wait for tokens.

Complexity Analysis:

Time: O(1) enqueue/dequeue per queue
Space: O(N) buffer

5. Implementation Guide

5.1 Development Environment Setup

cc --version

5.2 Project Structure

packet_buffer/
├── src/
│   ├── main.c
│   ├── ring.c
│   ├── scheduler.c
│   └── shaper.c
└── README.md

5.3 The Core Question You’re Answering

“How do you keep a system stable under bursty input without dropping the wrong data?”

5.4 Concepts You Must Understand First

Ring buffers
Backpressure policies
Priority scheduling
Token bucket shaping

5.5 Questions to Guide Your Design

How will you detect full vs empty?
What drop policy best matches your traffic goals?
How will you measure per-priority latency?

5.6 Thinking Exercise

If packets arrive at 1000/s and you can transmit 600/s, how long until a 10,000-packet buffer fills? What should your backpressure policy do?

5.7 The Interview Questions They’ll Ask

Why are ring buffers common in network stacks?
What is backpressure and why does it matter?
How would you avoid starvation under strict priority?

5.8 Hints in Layers

Hint 1: Implement a simple single-queue buffer first. Hint 2: Add priorities as separate queues. Hint 3: Add token bucket shaping last.

5.9 Books That Will Help

| Topic | Book | Chapter | |——-|——|———| | Queues and scheduling | Computer Networks | Ch. 3 | | Data structures | Algorithms, Fourth Edition | Ch. 2.4 |

5.10 Implementation Phases

Phase 1: Foundation (4-6 hours)

Goals: ring buffer and enqueue/dequeue tests Tasks: implement head/tail logic, tests Checkpoint: wrap-around tests pass

Phase 2: Core Functionality (4-8 hours)

Goals: backpressure and priority queues Tasks: add drop policy, multiple queues Checkpoint: deterministic drop behavior

Phase 3: Polish & Edge Cases (4-8 hours)

Goals: token bucket shaping, stats Tasks: add rate limiter, latency stats Checkpoint: throughput matches configured rate

5.11 Key Implementation Decisions

6. Testing Strategy

6.1 Test Categories

6.2 Critical Test Cases

Enqueue/dequeue across wrap boundary.
Fill buffer and verify drop policy.
Rate limiting with fixed tick clock.

6.3 Test Data

128 HIGH
128 LOW
128 HIGH

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

7.2 Debugging Strategies

Print head/tail indices in debug builds.
Log enqueue/dequeue order and compare to expected trace.

7.3 Performance Traps

Excessive logging slows throughput and distorts measurements.

8. Extensions & Challenges

8.1 Beginner Extensions

Add medium priority class.
Add buffer occupancy visualization.

8.2 Intermediate Extensions

Implement weighted round-robin scheduling.
Add priority-aware drop policy.

8.3 Advanced Extensions

Use shared memory to feed packets from another process.
Implement lock-free SPSC ring buffer with atomics.

9. Real-World Connections

9.1 Industry Applications

Router queue management and QoS.
Video streaming traffic shaping.

Linux kernel traffic control (tc)
DPDK ring buffer examples

9.3 Interview Relevance

Buffering vs latency tradeoffs
Scheduling algorithms

10. Resources

10.1 Essential Reading

Computer Networks (Tanenbaum), congestion control
DPDK documentation (ring buffers)

10.2 Video Resources

Network QoS and traffic shaping talks

10.3 Tools & Documentation

tc (Linux traffic control) for reference

11. Self-Assessment Checklist

11.1 Understanding

I can explain ring buffer invariants.
I can explain backpressure policies.
I can explain token bucket shaping.

11.2 Implementation

All functional requirements are met.
Deterministic tests pass.
Stats match expected outputs.

11.3 Growth

I can reason about scheduling and latency tradeoffs.

12. Submission / Completion Criteria

Minimum Viable Completion:

Ring buffer with backpressure
Priority scheduling

Full Completion:

Token bucket shaping
Deterministic golden demo

Excellence (Going Above & Beyond):

Weighted scheduling and fairness metrics