cubic: fast convergence from the rfc8312bis draft

Update based on https://github.com/NTAP/rfc8312bis/pull/35

- remove w_last_max
- update the logic of fast convergence
- fix the bug where fast convergence is not applied

1 files changed, 69 insertions, 12 deletions

diff --git a/src/recovery/cubic.rs b/src/recovery/cubic.rs
index 8f843ecf..f3d58aba 100644
--- a/src/recovery/cubic.rs
+++ b/src/recovery/cubic.rs
@@ -70,15 +70,13 @@ 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.
-/// k, w_max, w_last_max is described in the RFC.
+/// k, w_max, w_est are described in the RFC.
 #[derive(Debug, Default)]
 pub struct State {
     k: f64,
 
     w_max: f64,
 
-    w_last_max: f64,
-
     w_est: f64,
 
     alpha_aimd: f64,
@@ -148,8 +146,7 @@ fn collapse_cwnd(r: &mut Recovery) {
 
     r.congestion_recovery_start_time = None;
 
-    cubic.w_last_max = r.congestion_window as f64;
-    cubic.w_max = cubic.w_last_max;
+    cubic.w_max = r.congestion_window as f64;
 
     // 4.7 Timeout - reduce ssthresh based on BETA_CUBIC
     r.ssthresh = (r.congestion_window as f64 * BETA_CUBIC) as usize;
@@ -357,15 +354,13 @@ fn congestion_event(
         r.congestion_recovery_start_time = Some(now);
 
         // Fast convergence
-        if r.cubic_state.w_max < r.cubic_state.w_last_max {
-            r.cubic_state.w_last_max = r.cubic_state.w_max;
+        if (r.congestion_window as f64) < r.cubic_state.w_max {
             r.cubic_state.w_max =
-                r.cubic_state.w_max as f64 * (1.0 + BETA_CUBIC) / 2.0;
+                r.congestion_window as f64 * (1.0 + BETA_CUBIC) / 2.0;
         } else {
-            r.cubic_state.w_last_max = r.cubic_state.w_max;
+            r.cubic_state.w_max = r.congestion_window as f64;
         }
 
-        r.cubic_state.w_max = r.congestion_window as f64;
         r.ssthresh = (r.congestion_window as f64 * BETA_CUBIC) as usize;
         r.ssthresh = cmp::max(
             r.ssthresh,
@@ -396,7 +391,6 @@ fn checkpoint(r: &mut Recovery) {
     r.cubic_state.prior.congestion_window = r.congestion_window;
     r.cubic_state.prior.ssthresh = r.ssthresh;
     r.cubic_state.prior.w_max = r.cubic_state.w_max;
-    r.cubic_state.prior.w_last_max = r.cubic_state.w_last_max;
     r.cubic_state.prior.k = r.cubic_state.k;
     r.cubic_state.prior.epoch_start = r.congestion_recovery_start_time;
     r.cubic_state.prior.lost_count = r.lost_count;
@@ -406,7 +400,6 @@ fn rollback(r: &mut Recovery) {
     r.congestion_window = r.cubic_state.prior.congestion_window;
     r.ssthresh = r.cubic_state.prior.ssthresh;
     r.cubic_state.w_max = r.cubic_state.prior.w_max;
-    r.cubic_state.w_last_max = r.cubic_state.prior.w_last_max;
     r.cubic_state.k = r.cubic_state.prior.k;
     r.congestion_recovery_start_time = r.cubic_state.prior.epoch_start;
 }
@@ -798,4 +791,68 @@ mod tests {
         // cwnd is restored to the previous one.
         assert_eq!(r.cwnd(), prev_cwnd);
     }
+
+    #[test]
+    fn cubic_fast_convergence() {
+        let mut cfg = crate::Config::new(crate::PROTOCOL_VERSION).unwrap();
+        cfg.set_cc_algorithm(recovery::CongestionControlAlgorithm::CUBIC);
+
+        let mut r = Recovery::new(&cfg);
+        let mut now = Instant::now();
+        let prev_cwnd = r.cwnd();
+
+        // Send initcwnd full MSS packets to become no longer app limited
+        for _ in 0..recovery::INITIAL_WINDOW_PACKETS {
+            r.on_packet_sent_cc(r.max_datagram_size, now);
+        }
+
+        // Trigger congestion event to update ssthresh
+        r.congestion_event(now, packet::EPOCH_APPLICATION, now);
+
+        // After 1st congestion event, cwnd will be reduced.
+        let cur_cwnd = (prev_cwnd as f64 * BETA_CUBIC) as usize;
+        assert_eq!(r.cwnd(), cur_cwnd);
+
+        // Shift current time by 1 RTT.
+        let rtt = Duration::from_millis(100);
+        r.update_rtt(rtt, Duration::from_millis(0), now);
+
+        // Exit from the recovery.
+        now += rtt;
+
+        // To avoid rollback
+        r.lost_count += RESTORE_COUNT_THRESHOLD;
+
+        // 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;
+        }
+
+        assert_eq!(r.cwnd(), cur_cwnd + r.max_datagram_size);
+
+        let prev_cwnd = r.cwnd();
+
+        // Fast convergence: now there is 2nd congestion event and
+        // cwnd is not fully recovered to w_max, w_max will be
+        // further reduced.
+        r.congestion_event(now, packet::EPOCH_APPLICATION, now);
+
+        // After 2nd congestion event, cwnd will be reduced.
+        let cur_cwnd = (prev_cwnd as f64 * BETA_CUBIC) as usize;
+        assert_eq!(r.cwnd(), cur_cwnd);
+
+        // w_max will be further reduced, not prev_cwnd
+        assert_eq!(
+            r.cubic_state.w_max,
+            prev_cwnd as f64 * (1.0 + BETA_CUBIC) / 2.0
+        );
+    }
 }