Lightweight Internet Bandwidth Allocation and Isolation with Fractional Fair Shares

Lightweight Internet Bandwidth Allocation and Isolation with Fractional Fair Shares

Speakers: Marc Wyss

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=_bgSkkfpE7k

Overview

Today's internet has no mechanism to enforce fair bandwidth allocation -- aggressive congestion control algorithms dominate quieter ones, and volumetric DDoS attackers disregard all congestion signals entirely. While enforcing fairness directly in network routers has been a long-standing vision, existing systems either provide modest security with easy deployment or strong security with complex deployment. This talk presents Fractional Fair Shares (FFS), a cryptography-free algorithm that enforces fair bandwidth allocations directly in the network, providing communication guarantees even under volumetric DDoS attacks and address spoofing attacks.

FFS achieves this through probabilistic forwarding using two packet labels (sending rate R and fair share F), a fairness matrix for local configuration, and label normalization to handle untrusted nodes. The system requires only constant memory, constant queue count, constant packet header size, and constant processing time, achieving up to 160 Gbps on commodity hardware using DPDK and scaling linearly with CPU cores.

Background

▶ Watch: The problem: bandwidth allocation is not fair in today's internet (0:00)

In the current internet, bandwidth allocation is fundamentally unfair. End hosts employ various congestion control algorithms with different aggression levels, and DDoS attackers completely ignore congestion feedback. The vision of enforcing fairness at the network level has persisted for decades but faces a fundamental deployability-security tradeoff.

The researchers analyzed existing systems across two dimensions: deployability (implementation simplicity, performance, lack of setup phases, no external dependencies) and security (traffic stream isolation, spoofing resilience, minimal assumptions). Systems fell into two categories: simple but insecure, or complex but secure. Some systems assume a single bandwidth bottleneck, some assume congestion only at the last mile, some require trust between ISPs, and some track only the K largest flows. On the security side, per-IP-address bandwidth allocation is vulnerable to spoofing, and systems using cryptographic source authentication (symmetric keys exchanged in setup phases) add router complexity and performance overhead.

FFS aims to achieve both strong security and simple deployment simultaneously.

Key Findings

▶ Watch: FFS design: fairness matrix, packet labels, probabilistic forwarding (4:00)

• Constant overhead in all dimensions: FFS provides constant memory, constant number of queues, constant packet header size, and constant packet processing time -- enabling massive scalability
• 160 Gbps on commodity hardware: The DPDK implementation scales linearly with CPU cores, achieving production-viable throughput
• No cryptographic primitives required: FFS is entirely cryptography-free, unlike the most secure prior systems that require MAC-based source authentication
• Spoofing-resistant without source authentication: Because forwarding probability depends on packet labels (rate and fair share) rather than IP addresses, address spoofing provides no advantage to attackers
• Multi-flow attacks have no advantage: An attacker creating many flows gets no more bandwidth than an attacker with one large flow, eliminating a common DDoS amplification technique
• Formal security proofs: Mathematical proofs show that traffic from any ingress to any egress is guaranteed forwarding up to the rate defined by the fairness matrix, regardless of other traffic
• Lower latency and jitter than FIFO: Probabilistic forwarding (immediate forward or drop) avoids the queue buildup that causes high latency and jitter in traditional FIFO routers
• Higher network utilization than the most recent and secure comparable systems

Technical Deep Dive

▶ Watch: Label normalization: handling untrusted nodes without cryptography (8:00)

FFS operates through four core mechanisms:

Fairness Matrix Configuration: Each FFS node defines a fairness matrix specifying how egress bandwidth should be allocated among ingress interfaces during congestion. For example, a node with ingresses A and B and egress C might allocate 3 Gbps to A-to-C traffic and 1 Gbps to B-to-C traffic. Each node defines its own matrix independently.

Packet Labels: Two labels travel with each packet:

• R (Rate): The packet stream's current sending rate
• F (Fair Share): The packet stream's fair share allocation

These labels make local fairness definitions global by propagating allocation information along the forwarding path.

Probabilistic Forwarding: At each ingress, FFS either forwards or drops each packet based on the relationship between R and F. If the stream's rate R is less than or equal to its fair share F, the packet is forwarded with probability 1. If R exceeds F, the packet is dropped with probability (R-F)/R, reducing the expected throughput to F. This eliminates the need for per-flow queues (constant queue count), avoids queue buildup (lower latency), and scales to arbitrary numbers of flows.

Label Normalization: Since any node (including attackers) can set arbitrary packet labels, FFS normalizes fair shares at each ingress so their sum corresponds to the traffic matrix entry. The normalization formula divides each packet's fair share by the estimated sum of all fair shares, multiplied by the traffic matrix entry. Critically, estimating the sum of fair shares doesn't require per-stream state: it reduces to measuring the total arrival rate (a simple counter) and dividing by the rate-over-fair-share ratio from the packet labels. Every node treats all other nodes (including direct neighbors) as untrusted.

Rate Feedback (Optional): When a packet traverses the forwarding path and arrives at the destination, the destination can read the fair share label and communicate it back to the source. This allows the source to immediately jump to its fair share without probing, avoiding the traditional slow-start discovery process.

Demo / Proof of Concept

▶ Watch: Evaluation: fairer than FIFO with lower latency and jitter (10:00)

The evaluation covers fairness, quality of service, network utilization, security, and high-speed implementation.

Fairness and QoS: Compared against FIFO queuing (the predominant internet deployment model), FFS dramatically improves bandwidth allocation balance between competing congestion control algorithms. Where FIFO allows aggressive algorithms to dominate, FFS enforces balanced allocations. Latency and jitter are also significantly lower because probabilistic forwarding avoids queue saturation.

Network Utilization: FFS achieves higher network utilization than the most recent secure systems, meaning less bandwidth is wasted on enforcement overhead.

Security Analysis: Formal mathematical proofs demonstrate: (1) local guarantees -- traffic from ingress to egress is forwarded up to the fairness matrix rate regardless of other traffic; (2) global guarantees -- every stream over a forwarding path gets a worst-case minimum guaranteed allocation determined by the fairness matrix entries along the path.

DPDK Implementation: The high-speed implementation demonstrates constant overhead across all metrics, with throughput scaling linearly to 160 Gbps by adding CPU cores on commodity hardware.

Defensive Implications

▶ Watch: DPDK implementation: 160 Gbps on commodity hardware (14:00)

FFS represents a fundamental architectural approach to DDoS mitigation:

• Guaranteed minimum bandwidth under attack: Rather than trying to detect and filter attack traffic, FFS guarantees that legitimate traffic receives its fair share regardless of volumetric attack intensity
• Eliminates address spoofing advantage: Since forwarding decisions are based on packet labels rather than IP addresses, attackers gain nothing from spoofing source addresses -- a significant departure from IP-based rate limiting
• No setup phase vulnerability: Systems requiring key exchange setup phases are vulnerable to attacks during setup. FFS requires no setup, making it immediately effective
• ISP-level deployment: FFS can be deployed at ISP routers without requiring coordination or trust between providers, enabling incremental adoption
• Complements existing defenses: FFS provides a network-layer fairness guarantee that complements application-layer DDoS defenses, creating defense in depth

Key Takeaways

• FFS enforces fair bandwidth allocation directly in the network using a simple, cryptography-free algorithm
• Probabilistic forwarding based on rate/fair-share packet labels provides spoofing resistance without source authentication
• Constant overhead (memory, queues, headers, processing time) enables linear throughput scaling to 160 Gbps on commodity hardware
• Formal security proofs guarantee minimum bandwidth allocation under volumetric DDoS and address spoofing attacks
• Multi-flow DDoS attacks gain no advantage over single-flow attacks, eliminating a common amplification vector
• The system treats all nodes (including direct neighbors) as untrusted, requiring no inter-ISP trust assumptions

About the Speaker(s)

Marc Wyss is a postdoctoral researcher at ETH Zurich. The presentation was exceptionally clear and well-structured, demonstrating deep understanding of both the theoretical properties and practical deployment considerations. Wyss engaged thoughtfully with technical questions about label normalization, fairness matrix dynamics, and botnet resilience.