apps: Implement BIC and CUBIC congestion control in ConsumerPcon

Also fix some bugs in the current version.

refs: #4672

Change-Id: Ibbada2c808945f144d7dd9bd6fb9e779ce16aea9
diff --git a/apps/ndn-consumer-pcon.cpp b/apps/ndn-consumer-pcon.cpp
index 3add082..9fbc55c 100644
--- a/apps/ndn-consumer-pcon.cpp
+++ b/apps/ndn-consumer-pcon.cpp
@@ -26,6 +26,10 @@
 
 NS_OBJECT_ENSURE_REGISTERED(ConsumerPcon);
 
+constexpr double ConsumerPcon::CUBIC_C;
+constexpr uint32_t ConsumerPcon::BIC_MAX_INCREMENT;
+constexpr uint32_t ConsumerPcon::BIC_LOW_WINDOW;
+
 TypeId
 ConsumerPcon::GetTypeId()
 {
@@ -35,24 +39,47 @@
       .SetParent<ConsumerWindow>()
       .AddConstructor<ConsumerPcon>()
 
-      .AddAttribute("Beta", "TCP Multiplicative Decrease factor",
+      .AddAttribute("CcAlgorithm",
+                    "Specify which window adaptation algorithm to use (AIMD, BIC, or CUBIC)",
+                    EnumValue(CC_ALGORITHM::AIMD),
+                    MakeEnumAccessor(&ConsumerPcon::m_ccAlgorithm),
+                    MakeEnumChecker(CC_ALGORITHM::AIMD, "AIMD", CC_ALGORITHM::BIC, "BIC",
+                                    CC_ALGORITHM::CUBIC, "CUBIC"))
+
+      .AddAttribute("Beta",
+                    "TCP Multiplicative Decrease factor",
                     DoubleValue(0.5),
                     MakeDoubleAccessor(&ConsumerPcon::m_beta),
                     MakeDoubleChecker<double>())
 
-      .AddAttribute("AddRttSupress", "Minimum number of RTTs (1 + this factor) between window decreases",
-                    DoubleValue(0.5), // This default value was chosen after manual testing
-                    MakeDoubleAccessor(&ConsumerPcon::m_addRttSupress),
+      .AddAttribute("CubicBeta",
+                    "TCP CUBIC Multiplicative Decrease factor",
+                    DoubleValue(0.8),
+                    MakeDoubleAccessor(&ConsumerPcon::m_cubicBeta),
                     MakeDoubleChecker<double>())
 
-      .AddAttribute("ShouldReactToCongestionMarks", "If true, process received congestion marks",
+      .AddAttribute("AddRttSuppress",
+                    "Minimum number of RTTs (1 + this factor) between window decreases",
+                    DoubleValue(0.5), // This default value was chosen after manual testing
+                    MakeDoubleAccessor(&ConsumerPcon::m_addRttSuppress),
+                    MakeDoubleChecker<double>())
+
+      .AddAttribute("ReactToCongestionMarks",
+                    "If true, process received congestion marks",
                     BooleanValue(true),
-                    MakeBooleanAccessor(&ConsumerPcon::m_shouldReactToCongestionMarks),
+                    MakeBooleanAccessor(&ConsumerPcon::m_reactToCongestionMarks),
                     MakeBooleanChecker())
 
-      .AddAttribute("ShouldUseCwa", "If true, use Conservative Window Adaptation",
+      .AddAttribute("UseCwa",
+                    "If true, use Conservative Window Adaptation",
                     BooleanValue(true),
-                    MakeBooleanAccessor(&ConsumerPcon::m_shouldUseCwa),
+                    MakeBooleanAccessor(&ConsumerPcon::m_useCwa),
+                    MakeBooleanChecker())
+
+      .AddAttribute("UseCubicFastConvergence",
+                    "If true, use TCP CUBIC Fast Convergence",
+                    BooleanValue(false),
+                    MakeBooleanAccessor(&ConsumerPcon::m_useCubicFastConv),
                     MakeBooleanChecker());
 
   return tid;
@@ -62,6 +89,15 @@
   : m_ssthresh(std::numeric_limits<double>::max())
   , m_highData(0)
   , m_recPoint(0.0)
+  , m_cubicWmax(0)
+  , m_cubicLastWmax(0)
+  , m_cubicLastDecrease(time::steady_clock::now())
+  , m_bicMinWin(0)
+  , m_bicMaxWin(std::numeric_limits<double>::max())
+  , m_bicTargetWin(0)
+  , m_bicSsCwnd(0)
+  , m_bicSsTarget(0)
+  , m_isBicSs(false)
 {
 }
 
@@ -70,7 +106,7 @@
 {
   Consumer::OnData(data);
 
-  uint64_t sequenceNum = data->getName().get(-1).toSegment();
+  uint64_t sequenceNum = data->getName().get(-1).toSequenceNumber();
 
   // Set highest received Data to sequence number
   if (m_highData < sequenceNum) {
@@ -78,7 +114,7 @@
   }
 
   if (data->getCongestionMark() > 0) {
-    if (m_shouldReactToCongestionMarks) {
+    if (m_reactToCongestionMarks) {
       NS_LOG_DEBUG("Received congestion mark: " << data->getCongestionMark());
       WindowDecrease();
     }
@@ -116,27 +152,49 @@
 void
 ConsumerPcon::WindowIncrease()
 {
-  if (m_window < m_ssthresh) {
-    m_window += 1.0;
+  if (m_ccAlgorithm == CC_ALGORITHM::AIMD) {
+    if (m_window < m_ssthresh) {
+      m_window += 1.0;
+    }
+    else {
+      m_window += (1.0 / m_window);
+    }
+  }
+  else if (m_ccAlgorithm == CC_ALGORITHM::CUBIC) {
+    CubicIncrease();
+  }
+  else if (m_ccAlgorithm == CC_ALGORITHM::BIC) {
+    BicIncrease();
   }
   else {
-    m_window += (1.0 / m_window);
+    BOOST_ASSERT_MSG(false, "Unknown CC Algorithm");
   }
-
   NS_LOG_DEBUG("Window size increased to " << m_window);
 }
 
 void
 ConsumerPcon::WindowDecrease()
 {
-  if (m_shouldUseCwa || m_highData > m_recPoint) {
+  if (!m_useCwa || m_highData > m_recPoint) {
     const double diff = m_seq - m_highData;
-    assert(diff > 0);
+    BOOST_ASSERT(diff > 0);
 
-    m_recPoint = m_seq + (m_addRttSupress * diff);
+    m_recPoint = m_seq + (m_addRttSuppress * diff);
 
-    m_ssthresh = m_window * m_beta;
-    m_window = m_ssthresh;
+    if (m_ccAlgorithm == CC_ALGORITHM::AIMD) {
+      // Normal TCP Decrease:
+      m_ssthresh = m_window * m_beta;
+      m_window = m_ssthresh;
+    }
+    else if (m_ccAlgorithm == CC_ALGORITHM::CUBIC) {
+      CubicDecrease();
+    }
+    else if (m_ccAlgorithm == CC_ALGORITHM::BIC) {
+      BicDecrease();
+    }
+    else {
+      BOOST_ASSERT_MSG(false, "Unknown CC Algorithm");
+    }
 
     // Window size cannot be reduced below initial size
     if (m_window < m_initialWindow) {
@@ -150,5 +208,139 @@
   }
 }
 
+
+void
+ConsumerPcon::BicIncrease()
+{
+  if (m_window < BIC_LOW_WINDOW) {
+    // Normal TCP AIMD behavior
+    if (m_window < m_ssthresh) {
+      m_window = m_window + 1;
+    }
+    else {
+      m_window = m_window + 1.0 / m_window;
+    }
+  }
+  else if (!m_isBicSs) {
+    // Binary increase
+    if (m_bicTargetWin - m_window < BIC_MAX_INCREMENT) { // Binary search
+      m_window += (m_bicTargetWin - m_window) / m_window;
+    }
+    else {
+      m_window += BIC_MAX_INCREMENT / m_window; // Additive increase
+    }
+    // FIX for equal double values.
+    if (m_window + 0.00001 < m_bicMaxWin) {
+      m_bicMinWin = m_window;
+      m_bicTargetWin = (m_bicMaxWin + m_bicMinWin) / 2;
+    }
+    else {
+      m_isBicSs = true;
+      m_bicSsCwnd = 1;
+      m_bicSsTarget = m_window + 1.0;
+      m_bicMaxWin = std::numeric_limits<double>::max();
+    }
+  }
+  else {
+    // BIC slow start
+    m_window += m_bicSsCwnd / m_window;
+    if (m_window >= m_bicSsTarget) {
+      m_bicSsCwnd = 2 * m_bicSsCwnd;
+      m_bicSsTarget = m_window + m_bicSsCwnd;
+    }
+    if (m_bicSsCwnd >= BIC_MAX_INCREMENT) {
+      m_isBicSs = false;
+    }
+  }
+}
+
+void
+ConsumerPcon::BicDecrease()
+{
+  // BIC Decrease
+  if (m_window >= BIC_LOW_WINDOW) {
+    auto prev_max = m_bicMaxWin;
+    m_bicMaxWin = m_window;
+    m_window = m_window * m_cubicBeta;
+    m_bicMinWin = m_window;
+    if (prev_max > m_bicMaxWin) {
+      // Fast Convergence
+      m_bicMaxWin = (m_bicMaxWin + m_bicMinWin) / 2;
+    }
+    m_bicTargetWin = (m_bicMaxWin + m_bicMinWin) / 2;
+  }
+  else {
+    // Normal TCP Decrease:
+    m_ssthresh = m_window * m_cubicBeta;
+    m_window = m_ssthresh;
+  }
+}
+
+
+void
+ConsumerPcon::CubicIncrease()
+{
+  // 1. Time since last congestion event in Seconds
+  const double t = time::duration_cast<time::microseconds>(
+                     time::steady_clock::now() - m_cubicLastDecrease).count() / 1e6;
+
+  // 2. Time it takes to increase the window to cubic_wmax
+  // K = cubic_root(W_max*(1-beta_cubic)/C) (Eq. 2)
+  const double k = std::cbrt(m_cubicWmax * (1 - m_cubicBeta) / CUBIC_C);
+
+  // 3. Target: W_cubic(t) = C*(t-K)^3 + W_max (Eq. 1)
+  const double w_cubic = CUBIC_C * std::pow(t - k, 3) + m_cubicWmax;
+
+  // 4. Estimate of Reno Increase (Currently Disabled)
+  //  const double rtt = m_rtt->GetCurrentEstimate().GetSeconds();
+  //  const double w_est = m_cubic_wmax*m_beta + (3*(1-m_beta)/(1+m_beta)) * (t/rtt);
+  constexpr double w_est = 0.0;
+
+  // Actual adaptation
+  if (m_window < m_ssthresh) {
+    m_window += 1.0;
+  }
+  else {
+    BOOST_ASSERT(m_cubicWmax > 0);
+
+    double cubic_increment = std::max(w_cubic, w_est) - m_window;
+    // Cubic increment must be positive:
+    // Note: This change is not part of the RFC, but I added it to improve performance.
+    if (cubic_increment < 0) {
+      cubic_increment = 0.0;
+    }
+    m_window += cubic_increment / m_window;
+  }
+}
+
+
+void
+ConsumerPcon::CubicDecrease()
+{
+  // This implementation is ported from https://datatracker.ietf.org/doc/rfc8312/
+
+  const double FAST_CONV_DIFF = 1.0; // In percent
+
+  // A flow remembers the last value of W_max,
+  // before it updates W_max for the current congestion event.
+
+  // Current w_max < last_wmax
+  if (m_useCubicFastConv && m_window < m_cubicLastWmax * (1 - FAST_CONV_DIFF / 100)) {
+    m_cubicLastWmax = m_window;
+    m_cubicWmax = m_window * (1.0 + m_cubicBeta) / 2.0;
+  }
+  else {
+    // Save old cwnd as w_max:
+    m_cubicLastWmax = m_window;
+    m_cubicWmax = m_window;
+  }
+
+  m_ssthresh = m_window * m_cubicBeta;
+  m_ssthresh = std::max<double>(m_ssthresh, m_initialWindow);
+  m_window = m_ssthresh;
+
+  m_cubicLastDecrease = time::steady_clock::now();
+}
+
 } // namespace ndn
 } // namespace ns3
diff --git a/apps/ndn-consumer-pcon.hpp b/apps/ndn-consumer-pcon.hpp
index 9600829..080e675 100644
--- a/apps/ndn-consumer-pcon.hpp
+++ b/apps/ndn-consumer-pcon.hpp
@@ -27,11 +27,21 @@
 namespace ns3 {
 namespace ndn {
 
+enum CcAlgorithm {
+  AIMD,
+  BIC,
+  CUBIC
+};
+
 /**
  * @ingroup ndn-apps
- * \brief NDN consumer application (uses a PCON congestion window)
+ * \brief NDN consumer application with more advanced congestion control options
  *
- * Please refer to ConsumerWindow for further documentation on how to use this consumer.
+ * This app uses the algorithms from "A Practical Congestion Control Scheme for Named
+ * Data Networking" (https://dl.acm.org/citation.cfm?id=2984369).
+ *
+ * It implements slow start, conservative window adaptation (RFC 6675),
+ * and 3 different TCP algorithms: AIMD, BIC, and CUBIC (RFC 8312).
  */
 class ConsumerPcon : public ConsumerWindow {
 public:
@@ -53,15 +63,52 @@
   void
   WindowDecrease();
 
+  void
+  CubicIncrease();
+
+  void
+  CubicDecrease();
+
+  void
+  BicIncrease();
+
+  void
+  BicDecrease();
+
 private:
+  CcAlgorithm m_ccAlgorithm;
   double m_beta;
-  double m_addRttSupress;
-  bool m_shouldReactToCongestionMarks;
-  bool m_shouldUseCwa;
+  double m_addRttSuppress;
+  bool m_reactToCongestionMarks;
+  bool m_useCwa;
 
   double m_ssthresh;
   uint32_t m_highData;
   double m_recPoint;
+
+  // TCP CUBIC Parameters //
+  static constexpr double CUBIC_C = 0.4;
+  bool m_useCubicFastConv;
+  double m_cubicBeta;
+
+  double m_cubicWmax;
+  double m_cubicLastWmax;
+  time::steady_clock::TimePoint m_cubicLastDecrease;
+
+  // TCP BIC Parameters //
+  //! Regular TCP behavior (including slow start) until this window size
+  static constexpr uint32_t BIC_LOW_WINDOW = 14;
+
+  //! Sets the maximum (linear) increase of TCP BIC. Should be between 8 and 64.
+  static constexpr uint32_t BIC_MAX_INCREMENT = 16;
+
+  // BIC variables:
+  double m_bicMinWin; //!< last minimum cwnd
+  double m_bicMaxWin; //!< last maximum cwnd
+  double m_bicTargetWin;
+  double m_bicSsCwnd;
+  double m_bicSsTarget;
+  bool m_isBicSs; //!< whether we are currently in the BIC slow start phase
 };
 
 } // namespace ndn
diff --git a/docs/source/applications.rst b/docs/source/applications.rst
index c35440e..5191146 100644
--- a/docs/source/applications.rst
+++ b/docs/source/applications.rst
@@ -130,7 +130,7 @@
 ConsumerWindow
 ^^^^^^^^^^^^^^^^^^
 
-:ndnsim:`ConsumerWindow` is an application generating a variable rate Interest traffic. It implements a simple sliding-window-based Interest generation mechanism.
+:ndnsim:`ConsumerWindow` is an application generating a variable-rate Interest traffic. It implements a simple sliding-window-based Interest generation mechanism.
 
 .. code-block:: c++
 
@@ -166,7 +166,7 @@
 ConsumerPcon
 ^^^^^^^^^^^^^^^^
 
-:ndnsim:`ConsumerPcon` is an application generating variable rate Interest traffic. It implements a sliding-window-based Interest generation mechanism that adjusts window size using the PCON congestion control mechanism developed by K. Schneider et al. (https://named-data.net/publications/practical_congestion_control_scheme/). It is derived from :ndnsim:`ConsumerWindow`.
+:ndnsim:`ConsumerPcon` is an application generating variable-rate Interest traffic. It implements a window-based rate control that adjusts window size using the PCON congestion control mechanism developed by K. Schneider et al. (https://named-data.net/publications/practical_congestion_control_scheme/). It is derived from :ndnsim:`ConsumerWindow`.
 
 .. code-block:: c++
 
@@ -175,6 +175,13 @@
 
 The application has the same attributes as :ndnsim:`ConsumerWindow`, in addition to the following:
 
+* ``CcAlgorithm``
+
+  .. note::
+     default: ``AIMD``
+
+  Which window adaptation algorithm to use (AIMD, BIC, or CUBIC)
+
 * ``Beta``
 
   .. note::
@@ -182,6 +189,13 @@
 
   TCP Multiplicative Decrease factor
 
+* ``CubicBeta``
+
+  .. note::
+     default: ``0.8``
+
+  TCP CUBIC Multiplicative Decrease factor
+
 * ``AddRttSupress``
 
   .. note::
@@ -189,20 +203,27 @@
 
   Minimum number of RTTs (1 + this factor) between window decreases
 
-* ``ShouldReactToCongestionMarks``
+* ``ReactToCongestionMarks``
 
   .. note::
      default: ``true``
 
   If true, process received congestion marks; otherwise, ignore them
 
-* ``ShouldUseCwa``
+* ``UseCwa``
 
   .. note::
      default: ``true``
 
   If true, use Conservative Window Adaptation
 
+* ``UseCubicFastConvergence``
+
+  .. note::
+     default: ``true``
+
+  If true, use TCP CUBIC Fast Convergence
+
 Producer
 ^^^^^^^^^^^^