cubic: AIMD approach for TCP friendly window

- Update based on https://github.com/NTAP/rfc8312bis/pull/24
- Fix congestion avoidance test

1 files changed, 47 insertions, 25 deletions

diff --git a/src/recovery/cubic.rs b/src/recovery/cubic.rs
index b9e8e454..8f843ecf 100644
--- a/src/recovery/cubic.rs
+++ b/src/recovery/cubic.rs
@@ -64,6 +64,9 @@ const C: f64 = 0.4;
 /// lost packet count since the last checkpoint is less than the threshold.
 const RESTORE_COUNT_THRESHOLD: usize = 10;
 
+/// Default value of alpha_aimd in the beginning of congestion avoidance.
+const ALPHA_AIMD: f64 = 3.0 * (1.0 - BETA_CUBIC) / (1.0 + BETA_CUBIC);
+
 /// CUBIC State Variables.
 ///
 /// We need to keep those variables across the connection.
@@ -76,6 +79,10 @@ pub struct State {
 
     w_last_max: f64,
 
+    w_est: f64,
+
+    alpha_aimd: f64,
+
     // Used in CUBIC fix (see on_packet_sent())
     last_sent_time: Option<Instant>,
 
@@ -128,14 +135,11 @@ impl State {
             max_datagram_size as f64
     }
 
-    // W_est(t) = w_max * beta_cubic + 3 * (1 - beta_cubic) / (1 + beta_cubic) *
-    // (t / RTT) (Eq. 4)
-    fn w_est(&self, t: Duration, rtt: Duration, max_datagram_size: usize) -> f64 {
-        let w_max = self.w_max / max_datagram_size as f64;
-        (w_max * BETA_CUBIC +
-            3.0 * (1.0 - BETA_CUBIC) / (1.0 + BETA_CUBIC) * t.as_secs_f64() /
-                rtt.as_secs_f64()) *
-            max_datagram_size as f64
+    // W_est = W_est + alpha_aimd * (segments_acked / cwnd)  (Eq. 4)
+    fn w_est_inc(
+        &self, acked: usize, cwnd: usize, max_datagram_size: usize,
+    ) -> f64 {
+        self.alpha_aimd * (acked as f64 / cwnd as f64) * max_datagram_size as f64
     }
 }
 
@@ -257,6 +261,9 @@ fn on_packet_acked(
             if r.cubic_state.w_max == 0.0 {
                 r.cubic_state.w_max = r.congestion_window as f64;
                 r.cubic_state.k = 0.0;
+
+                r.cubic_state.w_est = r.congestion_window as f64;
+                r.cubic_state.alpha_aimd = ALPHA_AIMD;
             }
         } else {
             match r.congestion_recovery_start_time {
@@ -269,6 +276,9 @@ fn on_packet_acked(
 
                     r.cubic_state.w_max = r.congestion_window as f64;
                     r.cubic_state.k = 0.0;
+
+                    r.cubic_state.w_est = r.congestion_window as f64;
+                    r.cubic_state.alpha_aimd = ALPHA_AIMD;
                 },
             }
         }
@@ -282,14 +292,23 @@ fn on_packet_acked(
         let target = f64::max(target, r.congestion_window as f64);
         let target = f64::min(target, r.congestion_window as f64 * 1.5);
 
-        // w_est(t)
-        let w_est = r.cubic_state.w_est(t, r.min_rtt, r.max_datagram_size);
+        // Update w_est.
+        let w_est_inc = r.cubic_state.w_est_inc(
+            packet.size,
+            r.congestion_window,
+            r.max_datagram_size,
+        );
+        r.cubic_state.w_est += w_est_inc;
+
+        if r.cubic_state.w_est >= r.cubic_state.w_max {
+            r.cubic_state.alpha_aimd = 1.0;
+        }
 
         let mut cubic_cwnd = r.congestion_window;
 
-        if r.cubic_state.w_cubic(t, r.max_datagram_size) < w_est {
-            // TCP friendly region.
-            cubic_cwnd = cmp::max(cubic_cwnd, w_est as usize);
+        if r.cubic_state.w_cubic(t, r.max_datagram_size) < r.cubic_state.w_est {
+            // AIMD friendly region (W_cubic(t) < W_est)
+            cubic_cwnd = cmp::max(cubic_cwnd, r.cubic_state.w_est as usize);
         } else {
             // Concave region or convex region use same increment.
             let cubic_inc =
@@ -364,6 +383,9 @@ fn congestion_event(
         r.cubic_state.cwnd_inc =
             (r.cubic_state.cwnd_inc as f64 * BETA_CUBIC) as usize;
 
+        r.cubic_state.w_est = r.congestion_window as f64;
+        r.cubic_state.alpha_aimd = ALPHA_AIMD;
+
         if r.hystart.in_lss(epoch) {
             r.hystart.congestion_event();
         }
@@ -555,27 +577,27 @@ mod tests {
         // Shift current time by 1 RTT.
         let rtt = Duration::from_millis(100);
 
-        let acked = vec![Acked {
-            pkt_num: 0,
-            // To exit from recovery
-            time_sent: now + rtt,
-            size: r.max_datagram_size,
-        }];
-
         r.update_rtt(rtt, Duration::from_millis(0), now);
 
         // Exit from the recovery.
         now += rtt;
 
-        // Ack more than cwnd bytes with rtt=100ms
-        r.update_rtt(rtt, Duration::from_millis(0), now);
-
         // To avoid rollback
         r.lost_count += RESTORE_COUNT_THRESHOLD;
 
-        r.on_packets_acked(acked, packet::EPOCH_APPLICATION, now + rtt * 3);
+        // During Congestion Avoidance, it will take
+        // 5 ACKs to increase cwnd by 1 MSS.
+        for _ in 0..5 {
+            let acked = vec![Acked {
+                pkt_num: 0,
+                time_sent: now,
+                size: r.max_datagram_size,
+            }];
+
+            r.on_packets_acked(acked, packet::EPOCH_APPLICATION, now);
+            now += rtt;
+        }
 
-        // After acking more than cwnd, expect cwnd increased by MSS
         assert_eq!(r.cwnd(), cur_cwnd + r.max_datagram_size);
     }