1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

/* CUBIC Window Growth Function */
 
#include <math.h>
 
/* CUBIC parameters (from RFC 8312) */
#define CUBIC_C     0.4    /* Scaling constant */
#define CUBIC_BETA  0.7    /* Multiplicative decrease factor */
 
typedef struct {
    double wmax;           /* W_max: window before last loss */
    double cwnd;           /* Current congestion window */
    double ssthresh;       /* Slow start threshold */
    double K;              /* Time to reach W_max */
    double epoch_start;    /* Time when current epoch started */
    uint32_t mss;          /* Maximum segment size */
} CUBICState;
 
/*
 * Calculate target window size at time t since last loss
 */
double cubic_window(CUBICState* s, double t) {
    /*
     * W(t) = C * (t - K)^3 + W_max
     * 
     * This is a cubic function centered at (K, W_max)
     * - For t < K: window grows concavely toward W_max
     * - At t = K: window reaches W_max exactly
     * - For t > K: window grows convexly beyond W_max
     */
    double diff = t - s->K;
    double target = CUBIC_C * diff * diff * diff + s->wmax;
    
    return target;
}
 
/*
 * Calculate K: time to reach W_max
 */
double calculate_K(double wmax_segments) {
    /*
     * K = ∛(W_max * β / C)
     * 
     * After loss, cwnd becomes W_max * β.
     * K is the time for cubic function to return to W_max.
     */
    return cbrt(wmax_segments * (1 - CUBIC_BETA) / CUBIC_C);
}
 
/*
 * Enter congestion epoch (after loss detection)
 */
void cubic_enter_congestion(CUBICState* s, double current_time) {
    /* Record W_max as current window */
    s->wmax = s->cwnd;
    
    /* Calculate K for this epoch */
    s->K = calculate_K(s->wmax / s->mss);
    
    /* Multiplicative decrease */
    s->cwnd = s->wmax * CUBIC_BETA;
    s->ssthresh = s->cwnd;
    
    /* Mark epoch start time */
    s->epoch_start = current_time;
}
 
/*
 * Update cwnd on ACK
 */
void cubic_on_ack(CUBICState* s, double current_time) {
    /* Time since congestion event */
    double t = current_time - s->epoch_start;
    
    /* Calculate target window */
    double target = cubic_window(s, t);
    
    /* CUBIC growth: move toward target */
    if (target > s->cwnd) {
        /* Window should increase */
        double increase = (target - s->cwnd) / s->cwnd * s->mss;
        s->cwnd += increase;
    }
    
    /*
     * Note: In practice, there's also TCP-friendliness logic
     * to ensure CUBIC doesn't underperform compared to Reno.
     * See next section for details.
     */
}

Window
Size     ^
         |                                    .
         |                                . '  Convex
         |                            . '      (probing
W_max ---+- - - - - - - - - - - - -+          capacity)
         |      .  '  .  '  .  '   |
         |    .'      '      '     |
         |   .   Concave           | Plateau
         |  .    (recovering)      | (cautious)
         | .                       |
W_max*β -+------------------------'
         |
         +----------------------------> Time
               t=0              t=K
               (loss)           (reach W_max)
 
Phase 1: CONCAVE (t < K, W < W_max)
- Rapid growth toward W_max
- Shape: derivative decreasing (slowing as we approach W_max)  
- Goal: Quickly recover bandwidth after loss
 
Phase 2: PLATEAU (t ≈ K, W ≈ W_max)
- Very slow growth near W_max
- The cubic function has near-zero slope at this point
- Goal: Careful probing—we lost packets here before
 
Phase 3: CONVEX (t > K, W > W_max)
- Accelerating growth beyond W_max
- Shape: derivative increasing (faster as we move into new territory)
- Goal: Discover if more capacity has become available

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

/* CUBIC TCP-Friendliness Mechanism */
 
typedef struct {
    double cwnd;
    double wmax;
    double K;
    double epoch_start;
    double tcp_cwnd;      /* Simulated Reno window */
    double ack_count;     /* ACKs since epoch start */
    uint32_t mss;
} CUBICFriendly;
 
/*
 * Reno window growth simulation
 * 
 * Standard TCP: cwnd += MSS / cwnd per ACK
 * In Congestion Avoidance: ~1 MSS per RTT
 * 
 * We simulate this to ensure we're never slower than Reno.
 */
double compute_tcp_window(CUBICFriendly* s, double time_since_epoch) {
    /*
     * Reno after loss: cwnd = W_max * 0.5
     * Then linear growth: 1 MSS per RTT
     * 
     * If RTT = time_since_epoch / ACKs_received:
     *   RTTs elapsed ≈ time_since_epoch / RTT
     *   W_tcp = W_max * 0.5 + (time_since_epoch / RTT) * MSS
     * 
     * Simplified estimate:
     *   W_tcp = 3 * (1 - β) / (2 - β) * (t/RTT) + W_max * β
     * 
     * This creates a linear growth from the post-loss window.
     */
    double beta_factor = (3 * (1 - CUBIC_BETA)) / (2 - CUBIC_BETA);
    double rtt_estimate = get_smoothed_rtt();
    double elapsed_rtts = time_since_epoch / rtt_estimate;
    
    return s->wmax * CUBIC_BETA + beta_factor * elapsed_rtts * s->mss;
}
 
/*
 * Main CUBIC update: use maximum of cubic and Reno windows
 */
void cubic_friendly_on_ack(CUBICFriendly* s, double current_time) {
    double t = current_time - s->epoch_start;
    
    /* CUBIC's window calculation */
    double w_cubic = cubic_window(s, t);
    
    /* Simulated Reno's window */
    double w_tcp = compute_tcp_window(s, t);
    
    /* TCP-friendliness: use the larger window */
    double target = MAX(w_cubic, w_tcp);
    
    /*
     * If w_tcp > w_cubic, we're in "TCP mode"
     * This typically happens when:
     * 1. W_max is small (low-BDP path)
     * 2. Shortly after loss (Reno's linear growth beats concave)
     * 3. K is very large (slow cubic convergence)
     */
    if (target > s->cwnd) {
        /* Grow toward target */
        double segments_to_add = (target - s->cwnd) / s->cwnd;
        s->cwnd += MAX(1, segments_to_add) * s->mss;
    }
}
 
/*
 * Visualization of CUBIC vs TCP window growth
 *
 * Window
 *   ^          
 *   |                      . CUBIC
 *   |                    .'
 *   |                  .'
 * W_max-+- - - - - -.+- - - - - - 
 *   |            .'  '.
 *   |          .'      '.  <- Plateau region
 *   |        .'          '. 
 *   |      .' .-----------.-- Reno (linear)
 *   |    .'  /         
 *   |  .'   /  <- CUBIC concave
 *   | .    /             
 * W*β+---./
 *   +-------------------------------------> t
 *       0                K
 *
 * Below the intersection: TCP-friendly mode uses Reno growth
 * Above the intersection: CUBIC's cubic function takes over
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

/* CUBIC Parameter Impact Analysis */
 
/*
 * C = 0.4 (CUBIC scaling constant)
 * 
 * Higher C: More aggressive growth, especially in convex phase
 * Lower C:  More conservative, slower to probe beyond W_max
 * 
 * The value 0.4 was chosen empirically to balance aggressiveness
 * with network stability. Typical range: 0.2 - 0.8
 */
#define CUBIC_C 0.4
 
/*
 * β = 0.7 (Multiplicative decrease)
 * 
 * Compare to Reno's β = 0.5 (halving on loss)
 * 
 * CUBIC's gentler reduction (keeping 70% instead of 50%):
 * - Reduces window oscillation amplitude
 * - Faster recovery (less ground to make up)
 * - Potentially more packets in flight during congestion
 * 
 * Trade-off: More aggressive toward network, less backoff on loss
 */
#define CUBIC_BETA 0.7
 
/*
 * Fast Convergence
 * 
 * When a new flow joins a bottleneck, existing flows should
 * release bandwidth. Fast Convergence accelerates this.
 * 
 * Logic: If current W_max < previous W_max, assume new competition.
 *        Set W_max = current_cwnd * (1 + β) / 2
 *        This lowers K, speeding convergence to new equilibrium.
 */
void fast_convergence_check(CUBICState* s) {
    if (s->cwnd < s->wmax) {
        /* 
         * Lost at a window smaller than last W_max
         * Likely means more competition on the link
         */
        s->wmax = s->cwnd * (1 + CUBIC_BETA) / 2;
        /* Recalculate K for faster convergence */
        s->K = calculate_K(s->wmax / s->mss);
    } else {
        /* Normal case: W_max from current cwnd */
        s->wmax = s->cwnd;
    }
}
 
/*
 * HyStart: Hybrid Slow Start
 * 
 * Linux CUBIC includes HyStart to exit Slow Start before
 * massive loss. HyStart detects incipient congestion via:
 * 
 * 1. ACK Train: Monitor inter-ACK spacing. If ACKs slow down,
 *    queues are building → exit Slow Start early.
 * 
 * 2. Delay Increase: Monitor RTT samples. If current RTT 
 *    exceeds baseline by a threshold → exit early.
 * 
 * This avoids the Slow Start overshoot that causes burst losses.
 */
typedef struct {
    bool   hystart_enabled;
    double min_rtt;           /* Baseline RTT */
    double curr_rtt;          /* Current RTT sample */
    double delay_threshold;   /* Trigger threshold */
    int    sample_count;      /* RTT samples in this window */
} HyStartState;
 
void hystart_check(HyStartState* h, CUBICState* s) {
    if (!h->hystart_enabled) return;
    if (s->cwnd >= s->ssthresh) return;  /* Already in CA */
    
    h->sample_count++;
    
    /* Delay increase detection */
    if (h->curr_rtt > h->min_rtt + h->delay_threshold) {
        /* Exit Slow Start early */
        s->ssthresh = s->cwnd;
        /* Transition to CA */
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170

/* Complete TCP CUBIC Implementation */
 
#include <math.h>
#include <stdint.h>
#include <stdbool.h>
 
#define CUBIC_C    0.4
#define CUBIC_BETA 0.7
 
typedef struct {
    /* Core state */
    uint32_t cwnd;           /* Congestion window (bytes) */
    uint32_t ssthresh;       /* Slow start threshold */
    uint32_t mss;            /* Maximum segment size */
    
    /* CUBIC specific */
    double   wmax;           /* Window at last loss */
    double   K;              /* Time to reach W_max */
    double   epoch_start;    /* Time of last loss */
    double   tcp_cwnd;       /* TCP-friendly window estimate */
    
    /* For fast convergence */
    double   last_wmax;      /* Previous W_max (for fast convergence) */
    
    /* Timing */
    double   min_rtt;        /* Minimum observed RTT */
    
    /* Flags */
    bool     in_slow_start;
    uint8_t  dupacks;
} TCPCubic;
 
/* Initialize CUBIC state */
void cubic_init(TCPCubic* c, uint32_t mss) {
    c->cwnd = mss;           /* IW = 1 MSS (or 10 in modern impl) */
    c->ssthresh = UINT32_MAX;
    c->mss = mss;
    c->wmax = 0;
    c->K = 0;
    c->epoch_start = 0;
    c->tcp_cwnd = 0;
    c->last_wmax = 0;
    c->min_rtt = 0;
    c->in_slow_start = true;
    c->dupacks = 0;
}
 
/* Cubic function: W(t) = C*(t-K)³ + W_max */
double cubic_func(TCPCubic* c, double t) {
    double offset = t - c->K;
    return CUBIC_C * offset * offset * offset * c->mss + c->wmax;
}
 
/* Calculate TCP-friendly window estimate */
double tcp_friendly_window(TCPCubic* c, double t) {
    /* Simulate Reno: linear growth from β*W_max */
    double rtt = c->min_rtt > 0 ? c->min_rtt : 0.1;  /* Default 100ms */
    double elapsed_rtts = t / rtt;
    double alpha = 3 * (1 - CUBIC_BETA) / (2 - CUBIC_BETA);
    return c->wmax * CUBIC_BETA + alpha * elapsed_rtts * c->mss;
}
 
/* Enter loss recovery */
void cubic_on_loss(TCPCubic* c, double current_time) {
    c->dupacks = 0;
    
    /* Fast Convergence: if W_max decreasing, reduce further */
    if (c->cwnd < c->last_wmax) {
        /* New flow likely joined - converge faster */
        c->wmax = c->cwnd * (1 + CUBIC_BETA) / 2;
    } else {
        c->wmax = c->cwnd;
    }
    c->last_wmax = c->cwnd;
    
    /* Calculate K for this epoch */
    double wmax_segs = c->wmax / c->mss;
    c->K = cbrt(wmax_segs * (1 - CUBIC_BETA) / CUBIC_C);
    
    /* Multiplicative decrease */
    c->ssthresh = (uint32_t)(c->cwnd * CUBIC_BETA);
    if (c->ssthresh < 2 * c->mss) {
        c->ssthresh = 2 * c->mss;
    }
    c->cwnd = c->ssthresh;
    
    /* Mark epoch start */
    c->epoch_start = current_time;
    c->tcp_cwnd = c->cwnd;
    c->in_slow_start = false;
}
 
/* Handle ACK in Congestion Avoidance */
void cubic_on_ack_ca(TCPCubic* c, double current_time, double rtt_sample) {
    /* Update minimum RTT if needed */
    if (c->min_rtt == 0 || rtt_sample < c->min_rtt) {
        c->min_rtt = rtt_sample;
    }
    
    /* Time since epoch */
    double t = current_time - c->epoch_start;
    
    /* Calculate CUBIC target */
    double w_cubic = cubic_func(c, t);
    
    /* Calculate TCP-friendly target */
    double w_tcp = tcp_friendly_window(c, t);
    
    /* Use maximum (TCP-friendliness) */
    double target = (w_cubic > w_tcp) ? w_cubic : w_tcp;
    
    /* Calculate increment */
    if (target > c->cwnd) {
        /* cnt: how many ACKs to increase cwnd by 1 MSS */
        double cnt = c->cwnd / (target - c->cwnd);
        if (cnt < 1) cnt = 1;
        
        c->cwnd += c->mss / cnt;
    }
}
 
/* Handle ACK in Slow Start */
void cubic_on_ack_ss(TCPCubic* c) {
    /* Exponential growth: cwnd += MSS per ACK */
    c->cwnd += c->mss;
    
    /* Check for Slow Start exit */
    if (c->cwnd >= c->ssthresh) {
        c->in_slow_start = false;
        /* Note: HyStart may cause earlier exit */
    }
}
 
/* Main ACK handler */
void cubic_on_ack(TCPCubic* c, double current_time, double rtt_sample,
                  bool is_dup_ack) {
    if (is_dup_ack) {
        c->dupacks++;
        if (c->dupacks == 3) {
            /* Enter Fast Recovery (uses NewReno-style recovery) */
            cubic_on_loss(c, current_time);
            retransmit_first_unacked();
        }
        return;
    }
    
    /* New ACK */
    c->dupacks = 0;
    
    if (c->in_slow_start) {
        cubic_on_ack_ss(c);
    } else {
        cubic_on_ack_ca(c, current_time, rtt_sample);
    }
}
 
/* Timeout handler */
void cubic_on_timeout(TCPCubic* c, double current_time) {
    /* Severe congestion: full reset like Tahoe */
    c->ssthresh = (uint32_t)(c->cwnd * CUBIC_BETA);
    if (c->ssthresh < 2 * c->mss) {
        c->ssthresh = 2 * c->mss;
    }
    c->cwnd = c->mss;
    c->epoch_start = current_time;
    c->wmax = c->ssthresh;
    c->K = 0;
    c->in_slow_start = true;
    c->dupacks = 0;
}