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
^^^^^^^^^^^^