Understanding HFSC Scheduling in Linux/BSD: Implementation Differences, Curve Mechanics, and Practical Configuration

The original HFSC paper proposed a revolutionary approach to packet scheduling by using non-linear service curves to decouple bandwidth allocation from latency control. Unlike traditional schedulers that rely on linear service curves, HFSC allowed network administrators to specify convex or concave curves that could simultaneously guarantee:

Minimum bandwidth (link-sharing)
Bounded delay (real-time requirements)

Current BSD and Linux implementations have extended the original specification in ways that create confusion:

Original HFSC:
- Single service curve per class
- Two scheduling algorithms (real-time & link-share) operating on same curve

Modern Implementations:
+ Real-time curve (rt)
+ Link-share curve (ls)
+ Upper-limit curve (ul)
+ Priority levels (in some BSD variants)

Let's examine a basic setup with two parent classes (A, B) each containing two leaf classes (A1,A2 and B1,B2):

# Linux tc configuration example
tc qdisc add dev eth0 root handle 1: hfsc
tc class add dev eth0 parent 1: classid 1:1 hfsc rt rate 512kbit

# Class A (256kbit total)
tc class add dev eth0 parent 1:1 classid 1:10 hfsc rt rate 256kbit
tc class add dev eth0 parent 1:10 classid 1:11 hfsc rt m1 256kbit d 20ms m2 128kbit ls rate 128kbit
tc class add dev eth0 parent 1:10 classid 1:12 hfsc ls rate 128kbit

# Class B (256kbit total)
tc class add dev eth0 parent 1:1 classid 1:20 hfsc rt rate 256kbit
tc class add dev eth0 parent 1:20 classid 1:21 hfsc rt m1 256kbit d 20ms m2 128kbit ls rate 128kbit
tc class add dev eth0 parent 1:20 classid 1:22 hfsc ls rate 128kbit

Real-time vs Link-share Bandwidth Relationship

The real-time bandwidth does count toward the link-share allocation. If a class receives 64kbit/s via its real-time curve, that counts as satisfying 64kbit/s of its link-share requirement. Excess bandwidth distribution would only consider the remaining (link-share - real-time) portion.

Upper Limit Application Scope

The upper limit curve acts as a hard ceiling for total bandwidth consumption (real-time + link-share + any excess bandwidth). This is confirmed in both the FreeBSD and Linux kernel source implementations.

Priority Handling in Extended Implementations

Modern implementations use a hybrid approach:

Real-time curve parameters determine strict prioritization
Link-share curves handle fairness during congestion
The steeper initial slope in real-time curves gives priority to latency-sensitive traffic

Based on kernel source analysis and practical testing:

Keep real-time allocations below 75% of total bandwidth
Use real-time curves only for latency-sensitive leaf classes
Set upper limits 10-15% above expected maximum usage
For priority differentiation, adjust the m1 parameter in real-time curves

# Recommended priority differentiation
# High priority service (voice)
tc class add dev eth0 parent 1:1 classid 1:100 hfsc \
    rt m1 512kbit d 10ms m2 128kbit \
    ls rate 256kbit \
    ul rate 384kbit

# Standard service (web)
tc class add dev eth0 parent 1:1 classid 1:200 hfsc \
    rt m1 256kbit d 30ms m2 128kbit \
    ls rate 256kbit \
    ul rate 320kbit

Use these commands to verify scheduler operation:

# Linux
tc -s class show dev eth0
tc -d qdisc show dev eth0

# FreeBSD
altqstat -v -i em0
sysctl net.inet.ip.dummynet.hfsc_debug=1

The original SIGCOMM '97 paper presented HFSC (Hierarchical Fair Service Curve) as an elegant solution using single service curves to decouple bandwidth and delay. However, modern implementations in BSD (via ALTQ) and Linux (via TC) introduced two additional curves:


# Linux TC example showing all three curves
tc qdisc add dev eth0 root handle 1: hfsc
tc class add dev eth0 parent 1: classid 1:1 hfsc \
    rt m1 256kbit d 10ms m2 128kbit \  # Real-time
    ls m2 256kbit \                    # Link-share
    ul m2 512kbit                      # Upper-limit

The paper's single-curve approach allowed prioritization through curve shaping alone. For example:


# Original HFSC concept (single curve)
curve = [256kbit/s 20ms 128kbit/s]

Modern implementations break this into:

Real-time (rt): Guarantees minimum bandwidth with strict timing
Link-share (ls): Ensures fair bandwidth distribution
Upper-limit (ul): Prevents bandwidth starvation

For your specific scenario with A1/A2/B1/B2 classes:


# BSD ALTQ configuration example
altq on eth0 hfsc bandwidth 512kbit queue { A, B }
queue A hfsc ( pshare 256kbit grate 256kbit ) 
queue A1 hfsc ( pshare 128kbit grate 128kbit )
queue A2 hfsc ( pshare 128kbit )

Real-time Curve Purpose

The real-time curve provides deterministic latency for time-sensitive traffic. Even with equal link-share values, real-time curves ensure:

Guaranteed minimum bandwidth allocation
Strictly enforced service deadlines
Priority in packet scheduling

Bandwidth Accounting Mechanics

In modern implementations:

Real-time bandwidth does count toward link-share requirements
Upper-limit applies to combined real-time + link-share traffic
The hierarchy follows: rt ≤ ls ≤ ul

Inner Class Configuration Reality

Despite documentation claims, setting real-time curves on inner classes does affect aggregate bandwidth guarantees:


# This actually works in practice
queue A hfsc ( grate 256kbit )  # Sets minimum for entire branch

For optimal results:

Keep real-time allocations below 75% of total bandwidth

Shape curves differently for real-time vs link-share:


# Different slopes for rt vs ls
rt m1 512kbit d 5ms m2 256kbit
ls m2 384kbit

Use upper-limits to prevent starvation:


ul m2 640kbit  # Caps at 125% of nominal rate

The original HFSC achieves prioritization through:

Steeper real-time curve slopes for higher priority classes
Earlier intercept points in concave curves
Careful m1/d/m2 parameter selection

Example priority differentiation:


# High priority service
queue VoIP hfsc ( grate 64kbit rt m1 128kbit d 2ms m2 64kbit )

# Normal priority
queue http hfsc ( grate 128kbit rt m1 128kbit d 20ms m2 128kbit )