catchunks: Implement CUBIC window adaptation
Also increase the RTT estimator multiplier k to 8.
Change-Id: I68c5096ac0da854f071bab5f7519b1c144f20ca1
refs: #4861
diff --git a/tools/chunks/catchunks/main.cpp b/tools/chunks/catchunks/main.cpp
index 737f2aa..718fb49 100644
--- a/tools/chunks/catchunks/main.cpp
+++ b/tools/chunks/catchunks/main.cpp
@@ -33,7 +33,8 @@
#include "discover-version-fixed.hpp"
#include "discover-version-realtime.hpp"
#include "options.hpp"
-#include "pipeline-interests-adaptive.hpp"
+#include "pipeline-interests-aimd.hpp"
+#include "pipeline-interests-cubic.hpp"
#include "pipeline-interests-fixed.hpp"
#include "rtt-estimator.hpp"
#include "statistics-collector.hpp"
@@ -51,17 +52,18 @@
std::string programName(argv[0]);
Options options;
std::string discoverType("realtime");
- std::string pipelineType("aimd");
+ std::string pipelineType("cubic");
size_t maxPipelineSize(1);
int64_t discoveryTimeoutMs(DEFAULT_INTEREST_LIFETIME.count());
std::string uri;
// congestion control parameters, CWA refers to conservative window adaptation,
// i.e. only reduce window size at most once per RTT
- bool disableCwa(false), resetCwndToInit(false), ignoreCongMarks(false);
- double aiStep(1.0), mdCoef(0.5), alpha(0.125), beta(0.25),
- minRto(200.0), maxRto(4000.0);
- int initCwnd(1), initSsthresh(std::numeric_limits<int>::max()), k(4);
+ bool disableCwa(false), resetCwndToInit(false),
+ ignoreCongMarks(false), enableFastConv(false);
+ double aiStep(1.0), rtoAlpha(0.125), rtoBeta(0.25), minRto(200.0), maxRto(4000.0),
+ aimdBeta(0.5), cubicBeta(0.7);
+ int initCwnd(1), initSsthresh(std::numeric_limits<int>::max()), k(8);
std::string cwndPath, rttPath;
namespace po = boost::program_options;
@@ -71,7 +73,7 @@
("discover-version,d", po::value<std::string>(&discoverType)->default_value(discoverType),
"version discovery algorithm to use; valid values are: 'fixed', 'realtime'")
("pipeline-type,p", po::value<std::string>(&pipelineType)->default_value(pipelineType),
- "type of Interest pipeline to use; valid values are: 'fixed', 'aimd'")
+ "type of Interest pipeline to use; valid values are: 'fixed', 'aimd', 'cubic'")
("fresh,f", po::bool_switch(&options.mustBeFresh), "only return fresh content")
("lifetime,l", po::value<int64_t>()->default_value(options.interestLifetime.count()),
"lifetime of expressed Interests, in milliseconds")
@@ -93,30 +95,27 @@
"size of the Interest pipeline")
;
- po::options_description adaptivePipeDesc("Adaptive pipeline options (AIMD)");
+ po::options_description adaptivePipeDesc("Adaptive pipeline options (AIMD & CUBIC)");
adaptivePipeDesc.add_options()
- ("log-cwnd", po::value<std::string>(&cwndPath), "log file for cwnd statistics")
- ("log-rtt", po::value<std::string>(&rttPath), "log file for rtt statistics")
- ("disable-cwa", po::bool_switch(&disableCwa),
- "disable Conservative Window Adaptation, "
- "i.e. reduce window on each congestion event (timeout or congestion mark) "
- "instead of at most once per RTT")
("ignore-marks", po::bool_switch(&ignoreCongMarks),
- "ignore congestion marks, "
- "the default is to decrease the window after receiving a congestion mark")
+ "do not decrease the window after receiving a congestion mark")
+ ("disable-cwa", po::bool_switch(&disableCwa),
+ "disable Conservative Window Adaptation, i.e., reduce the window on "
+ "each timeout or congestion mark instead of at most once per RTT")
("reset-cwnd-to-init", po::bool_switch(&resetCwndToInit),
- "reset cwnd to initial value after loss/mark, default is "
- "resetting to ssthresh")
- ("init-cwnd", po::value<int>(&initCwnd)->default_value(initCwnd), "initial cwnd")
- ("init-ssthresh", po::value<int>(&initSsthresh),
- "initial slow start threshold (defaults to infinity)")
- ("aistep", po::value<double>(&aiStep)->default_value(aiStep),
+ "after a timeout or congestion mark, reset the window "
+ "to the initial value instead of resetting to ssthresh")
+ ("init-cwnd", po::value<int>(&initCwnd)->default_value(initCwnd),
+ "initial congestion window in segments")
+ ("init-ssthresh", po::value<int>(&initSsthresh),
+ "initial slow start threshold in segments (defaults to infinity)")
+ ("aimd-step", po::value<double>(&aiStep)->default_value(aiStep),
"additive-increase step")
- ("mdcoef", po::value<double>(&mdCoef)->default_value(mdCoef),
- "multiplicative-decrease coefficient")
- ("rto-alpha", po::value<double>(&alpha)->default_value(alpha),
+ ("aimd-beta", po::value<double>(&aimdBeta)->default_value(aimdBeta),
+ "multiplicative decrease factor (AIMD)")
+ ("rto-alpha", po::value<double>(&rtoAlpha)->default_value(rtoAlpha),
"alpha value for rto calculation")
- ("rto-beta", po::value<double>(&beta)->default_value(beta),
+ ("rto-beta", po::value<double>(&rtoBeta)->default_value(rtoBeta),
"beta value for rto calculation")
("rto-k", po::value<int>(&k)->default_value(k),
"k value for rto calculation")
@@ -124,10 +123,23 @@
"minimum rto value in milliseconds")
("max-rto", po::value<double>(&maxRto)->default_value(maxRto),
"maximum rto value in milliseconds")
+ ("log-cwnd", po::value<std::string>(&cwndPath), "log file for congestion window stats")
+ ("log-rtt", po::value<std::string>(&rttPath), "log file for round-trip time stats")
+ ;
+
+ po::options_description cubicPipeDesc("CUBIC pipeline options");
+ cubicPipeDesc.add_options()
+ ("fast-conv", po::bool_switch(&enableFastConv), "enable cubic fast convergence")
+ ("cubic-beta", po::value<double>(&cubicBeta),
+ "window decrease factor for CUBIC (defaults to 0.7)")
;
po::options_description visibleDesc;
- visibleDesc.add(basicDesc).add(realDiscoveryDesc).add(fixedPipeDesc).add(adaptivePipeDesc);
+ visibleDesc.add(basicDesc)
+ .add(realDiscoveryDesc)
+ .add(fixedPipeDesc)
+ .add(adaptivePipeDesc)
+ .add(cubicPipeDesc);
po::options_description hiddenDesc;
hiddenDesc.add_options()
@@ -231,11 +243,11 @@
optionsPipeline.maxPipelineSize = maxPipelineSize;
pipeline = make_unique<PipelineInterestsFixed>(face, optionsPipeline);
}
- else if (pipelineType == "aimd") {
+ else if (pipelineType == "aimd" || pipelineType == "cubic") {
RttEstimator::Options optionsRttEst;
optionsRttEst.isVerbose = options.isVerbose;
- optionsRttEst.alpha = alpha;
- optionsRttEst.beta = beta;
+ optionsRttEst.alpha = rtoAlpha;
+ optionsRttEst.beta = rtoBeta;
optionsRttEst.k = k;
optionsRttEst.minRto = Milliseconds(minRto);
optionsRttEst.maxRto = Milliseconds(maxRto);
@@ -248,10 +260,19 @@
optionsPipeline.initCwnd = static_cast<double>(initCwnd);
optionsPipeline.initSsthresh = static_cast<double>(initSsthresh);
optionsPipeline.aiStep = aiStep;
- optionsPipeline.mdCoef = mdCoef;
+ optionsPipeline.mdCoef = aimdBeta;
optionsPipeline.ignoreCongMarks = ignoreCongMarks;
- auto adaptivePipeline = make_unique<PipelineInterestsAdaptive>(face, *rttEstimator, optionsPipeline);
+ unique_ptr<PipelineInterestsAdaptive> adaptivePipeline;
+ if (pipelineType == "aimd") {
+ adaptivePipeline = make_unique<PipelineInterestsAimd>(face, *rttEstimator, optionsPipeline);
+ }
+ else {
+ PipelineInterestsCubic::Options optionsCubic(optionsPipeline);
+ optionsCubic.enableFastConv = enableFastConv;
+ optionsCubic.cubicBeta = cubicBeta;
+ adaptivePipeline = make_unique<PipelineInterestsCubic>(face, *rttEstimator, optionsCubic);
+ }
if (!cwndPath.empty() || !rttPath.empty()) {
if (!cwndPath.empty()) {
diff --git a/tools/chunks/catchunks/pipeline-interests-adaptive.cpp b/tools/chunks/catchunks/pipeline-interests-adaptive.cpp
index 4ce277d..03a842f 100644
--- a/tools/chunks/catchunks/pipeline-interests-adaptive.cpp
+++ b/tools/chunks/catchunks/pipeline-interests-adaptive.cpp
@@ -32,7 +32,6 @@
#include <cmath>
#include <iomanip>
-
namespace ndn {
namespace chunks {
@@ -42,6 +41,8 @@
const Options& options)
: PipelineInterests(face)
, m_options(options)
+ , m_cwnd(m_options.initCwnd)
+ , m_ssthresh(m_options.initSsthresh)
, m_rttEstimator(rttEstimator)
, m_scheduler(m_face.getIoService())
, m_highData(0)
@@ -55,14 +56,9 @@
, m_nRetransmitted(0)
, m_nCongMarks(0)
, m_nSent(0)
- , m_cwnd(m_options.initCwnd)
- , m_ssthresh(m_options.initSsthresh)
, m_hasFailure(false)
, m_failedSegNo(0)
{
- if (m_options.isVerbose) {
- std::cerr << m_options;
- }
}
PipelineInterestsAdaptive::~PipelineInterestsAdaptive()
@@ -400,29 +396,6 @@
}
void
-PipelineInterestsAdaptive::increaseWindow()
-{
- if (m_cwnd < m_ssthresh) {
- m_cwnd += m_options.aiStep; // additive increase
- }
- else {
- m_cwnd += m_options.aiStep / std::floor(m_cwnd); // congestion avoidance
- }
-
- afterCwndChange(time::steady_clock::now() - getStartTime(), m_cwnd);
-}
-
-void
-PipelineInterestsAdaptive::decreaseWindow()
-{
- // please refer to RFC 5681, Section 3.1 for the rationale behind it
- m_ssthresh = std::max(MIN_SSTHRESH, m_cwnd * m_options.mdCoef); // multiplicative decrease
- m_cwnd = m_options.resetCwndToInit ? m_options.initCwnd : m_ssthresh;
-
- afterCwndChange(time::steady_clock::now() - getStartTime(), m_cwnd);
-}
-
-void
PipelineInterestsAdaptive::cancelInFlightSegmentsGreaterThan(uint64_t segNo)
{
for (auto it = m_segmentInfo.begin(); it != m_segmentInfo.end();) {
@@ -488,9 +461,9 @@
<< "\tRTO check interval = " << options.rtoCheckInterval << "\n"
<< "\tMax retries on timeout or Nack = " << (options.maxRetriesOnTimeoutOrNack == DataFetcher::MAX_RETRIES_INFINITE ?
"infinite" : to_string(options.maxRetriesOnTimeoutOrNack)) << "\n"
- << "\tReaction to congestion marks " << (options.ignoreCongMarks ? "disabled" : "enabled") << "\n"
- << "\tConservative window adaptation " << (options.disableCwa ? "disabled" : "enabled") << "\n"
- << "\tResetting cwnd to " << (options.resetCwndToInit ? "initCwnd" : "ssthresh") << " upon loss event\n";
+ << "\tReact to congestion marks = " << (options.ignoreCongMarks ? "no" : "yes") << "\n"
+ << "\tConservative window adaptation = " << (options.disableCwa ? "no" : "yes") << "\n"
+ << "\tResetting window to " << (options.resetCwndToInit ? "initCwnd" : "ssthresh") << " upon loss event\n";
return os;
}
diff --git a/tools/chunks/catchunks/pipeline-interests-adaptive.hpp b/tools/chunks/catchunks/pipeline-interests-adaptive.hpp
index b65a2c3..0c4f889 100644
--- a/tools/chunks/catchunks/pipeline-interests-adaptive.hpp
+++ b/tools/chunks/catchunks/pipeline-interests-adaptive.hpp
@@ -59,6 +59,9 @@
bool ignoreCongMarks = false; ///< disable window decrease after congestion marks
};
+std::ostream&
+operator<<(std::ostream& os, const PipelineInterestsAdaptiveOptions& options);
+
/**
* @brief indicates the state of the segment
*/
@@ -96,11 +99,11 @@
class PipelineInterestsAdaptive : public PipelineInterests
{
public:
- typedef PipelineInterestsAdaptiveOptions Options;
+ using Options = PipelineInterestsAdaptiveOptions;
public:
/**
- * @brief create a PipelineInterestsAdaptive service
+ * @brief Constructor.
*
* Configures the pipelining service without specifying the retrieval namespace. After this
* configuration the method run must be called to start the Pipeline.
@@ -108,19 +111,35 @@
PipelineInterestsAdaptive(Face& face, RttEstimator& rttEstimator,
const Options& options = Options());
- ~PipelineInterestsAdaptive() final;
+ ~PipelineInterestsAdaptive() override;
/**
- * @brief Signals when cwnd changes
+ * @brief Signals when the congestion window changes.
*
* The callback function should be: void(Milliseconds age, double cwnd) where age is the
* duration since pipeline starts, and cwnd is the new congestion window size (in segments).
*/
signal::Signal<PipelineInterestsAdaptive, Milliseconds, double> afterCwndChange;
+protected:
+ DECLARE_SIGNAL_EMIT(afterCwndChange)
+
private:
/**
- * @brief fetch all the segments between 0 and lastSegment of the specified prefix
+ * @brief Increase congestion window.
+ */
+ virtual void
+ increaseWindow() = 0;
+
+ /**
+ * @brief Decrease congestion window.
+ */
+ virtual void
+ decreaseWindow() = 0;
+
+private:
+ /**
+ * @brief Fetch all the segments between 0 and lastSegment of the specified prefix.
*
* Starts the pipeline with an adaptive window algorithm to control the window size.
* The pipeline will fetch every segment until the last segment is successfully received
@@ -130,13 +149,13 @@
doRun() final;
/**
- * @brief stop all fetch operations
+ * @brief Stop all fetch operations.
*/
void
doCancel() final;
/**
- * @brief check RTO for all sent-but-not-acked segments.
+ * @brief Check RTO for all sent-but-not-acked segments.
*/
void
checkRto();
@@ -169,18 +188,6 @@
void
handleFail(uint64_t segNo, const std::string& reason);
- /**
- * @brief increase congestion window size
- */
- void
- increaseWindow();
-
- /**
- * @brief decrease congestion window size
- */
- void
- decreaseWindow();
-
void
cancelInFlightSegmentsGreaterThan(uint64_t segNo);
@@ -188,9 +195,14 @@
void
printSummary() const final;
-PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+PUBLIC_WITH_TESTS_ELSE_PROTECTED:
static constexpr double MIN_SSTHRESH = 2.0;
const Options m_options;
+
+ double m_cwnd; ///< current congestion window size (in segments)
+ double m_ssthresh; ///< current slow start threshold
+
+PUBLIC_WITH_TESTS_ELSE_PRIVATE:
RttEstimator& m_rttEstimator;
Scheduler m_scheduler;
scheduler::ScopedEventId m_checkRtoEvent;
@@ -210,9 +222,6 @@
int64_t m_nCongMarks; ///< # of data packets with congestion mark
int64_t m_nSent; ///< # of interest packets sent out (including retransmissions)
- double m_cwnd; ///< current congestion window size (in segments)
- double m_ssthresh; ///< current slow start threshold
-
std::unordered_map<uint64_t, SegmentInfo> m_segmentInfo; ///< keeps all the internal information
///< on sent but not acked segments
std::unordered_map<uint64_t, int> m_retxCount; ///< maps segment number to its retransmission count;
@@ -225,10 +234,6 @@
std::string m_failureReason;
};
-std::ostream&
-operator<<(std::ostream& os, const PipelineInterestsAdaptiveOptions& options);
-
-
} // namespace chunks
} // namespace ndn
diff --git a/tools/chunks/catchunks/pipeline-interests-aimd.cpp b/tools/chunks/catchunks/pipeline-interests-aimd.cpp
new file mode 100644
index 0000000..0292714
--- /dev/null
+++ b/tools/chunks/catchunks/pipeline-interests-aimd.cpp
@@ -0,0 +1,69 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2016-2019, Regents of the University of California,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University.
+ *
+ * This file is part of ndn-tools (Named Data Networking Essential Tools).
+ * See AUTHORS.md for complete list of ndn-tools authors and contributors.
+ *
+ * ndn-tools is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * ndn-tools is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * ndn-tools, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * See AUTHORS.md for complete list of ndn-cxx authors and contributors.
+ *
+ * @author Shuo Yang
+ * @author Weiwei Liu
+ * @author Chavoosh Ghasemi
+ * @author Klaus Schneider
+ */
+
+#include "pipeline-interests-aimd.hpp"
+
+#include <cmath>
+
+namespace ndn {
+namespace chunks {
+
+PipelineInterestsAimd::PipelineInterestsAimd(Face& face, RttEstimator& rttEstimator,
+ const Options& options)
+ : PipelineInterestsAdaptive(face, rttEstimator, options)
+{
+ if (options.isVerbose) {
+ std::cerr << options;
+ }
+}
+
+void
+PipelineInterestsAimd::increaseWindow()
+{
+ if (m_cwnd < m_ssthresh) {
+ m_cwnd += m_options.aiStep; // additive increase
+ }
+ else {
+ m_cwnd += m_options.aiStep / std::floor(m_cwnd); // congestion avoidance
+ }
+
+ emitSignal(afterCwndChange, time::steady_clock::now() - getStartTime(), m_cwnd);
+}
+
+void
+PipelineInterestsAimd::decreaseWindow()
+{
+ // please refer to RFC 5681, Section 3.1 for the rationale behind it
+ m_ssthresh = std::max(MIN_SSTHRESH, m_cwnd * m_options.mdCoef); // multiplicative decrease
+ m_cwnd = m_options.resetCwndToInit ? m_options.initCwnd : m_ssthresh;
+
+ emitSignal(afterCwndChange, time::steady_clock::now() - getStartTime(), m_cwnd);
+}
+
+} // namespace chunks
+} // namespace ndn
diff --git a/tools/chunks/catchunks/pipeline-interests-aimd.hpp b/tools/chunks/catchunks/pipeline-interests-aimd.hpp
new file mode 100644
index 0000000..ccaf08b
--- /dev/null
+++ b/tools/chunks/catchunks/pipeline-interests-aimd.hpp
@@ -0,0 +1,57 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2016-2019, Regents of the University of California,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University.
+ *
+ * This file is part of ndn-tools (Named Data Networking Essential Tools).
+ * See AUTHORS.md for complete list of ndn-tools authors and contributors.
+ *
+ * ndn-tools is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * ndn-tools is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * ndn-tools, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * See AUTHORS.md for complete list of ndn-cxx authors and contributors.
+ *
+ * @author Shuo Yang
+ * @author Weiwei Liu
+ * @author Chavoosh Ghasemi
+ * @author Klaus Schneider
+ */
+
+#ifndef NDN_TOOLS_CHUNKS_CATCHUNKS_PIPELINE_INTERESTS_AIMD_HPP
+#define NDN_TOOLS_CHUNKS_CATCHUNKS_PIPELINE_INTERESTS_AIMD_HPP
+
+#include "pipeline-interests-adaptive.hpp"
+
+namespace ndn {
+namespace chunks {
+
+/**
+ * @brief Implements AIMD window increase and decrease.
+ */
+class PipelineInterestsAimd : public PipelineInterestsAdaptive
+{
+public:
+ PipelineInterestsAimd(Face& face, RttEstimator& rttEstimator,
+ const Options& options = Options());
+
+private:
+ void
+ increaseWindow() final;
+
+ void
+ decreaseWindow() final;
+};
+
+} // namespace chunks
+} // namespace ndn
+
+#endif // NDN_TOOLS_CHUNKS_CATCHUNKS_PIPELINE_INTERESTS_AIMD_HPP
diff --git a/tools/chunks/catchunks/pipeline-interests-cubic.cpp b/tools/chunks/catchunks/pipeline-interests-cubic.cpp
new file mode 100644
index 0000000..414cc8a
--- /dev/null
+++ b/tools/chunks/catchunks/pipeline-interests-cubic.cpp
@@ -0,0 +1,124 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2016-2019, Regents of the University of California,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University.
+ *
+ * This file is part of ndn-tools (Named Data Networking Essential Tools).
+ * See AUTHORS.md for complete list of ndn-tools authors and contributors.
+ *
+ * ndn-tools is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * ndn-tools is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * ndn-tools, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * See AUTHORS.md for complete list of ndn-cxx authors and contributors.
+ *
+ * @author Klaus Schneider
+ */
+
+#include "pipeline-interests-cubic.hpp"
+
+#include <cmath>
+
+namespace ndn {
+namespace chunks {
+
+constexpr double CUBIC_C = 0.4;
+
+PipelineInterestsCubic::PipelineInterestsCubic(Face& face, RttEstimator& rttEstimator,
+ const Options& options)
+ : PipelineInterestsAdaptive(face, rttEstimator, options)
+ , m_cubicOptions(options)
+ , m_lastDecrease(time::steady_clock::now())
+{
+ if (options.isVerbose) {
+ std::cerr << options;
+ }
+}
+
+void
+PipelineInterestsCubic::increaseWindow()
+{
+ // Slow start phase
+ if (m_cwnd < m_ssthresh) {
+ m_cwnd += 1.0;
+ }
+ // Congestion avoidance phase
+ else {
+ // If wmax is still 0, set it to the current cwnd. Usually unnecessary,
+ // if m_ssthresh is large enough.
+ if (m_wmax < m_options.initCwnd) {
+ m_wmax = m_cwnd;
+ }
+
+ // 1. Time since last congestion event in seconds
+ const double t = (time::steady_clock::now() - m_lastDecrease).count() / 1e9;
+
+ // 2. Time it takes to increase the window to m_wmax = the cwnd right before the last
+ // window decrease.
+ // K = cubic_root(wmax*(1-beta_cubic)/C) (Eq. 2)
+ const double k = std::cbrt(m_wmax * (1 - m_cubicOptions.cubicBeta) / CUBIC_C);
+
+ // 3. Target: W_cubic(t) = C*(t-K)^3 + wmax (Eq. 1)
+ const double wCubic = CUBIC_C * std::pow(t - k, 3) + m_wmax;
+
+ // 4. Estimate of Reno Increase (Currently Disabled)
+ // const double rtt = m_rtt->GetCurrentEstimate().GetSeconds();
+ // const double w_est = wmax*m_beta + (3*(1-m_beta)/(1+m_beta)) * (t/rtt);
+ const double wEst = 0.0;
+
+ // Actual adaptation
+ double cubicIncrement = std::max(wCubic, wEst) - m_cwnd;
+ // Cubic increment must be positive
+ // Note: This change is not part of the RFC, but I added it to improve performance.
+ cubicIncrement = std::max(0.0, cubicIncrement);
+
+ m_cwnd += cubicIncrement / m_cwnd;
+ }
+
+ emitSignal(afterCwndChange, time::steady_clock::now() - getStartTime(), m_cwnd);
+}
+
+void
+PipelineInterestsCubic::decreaseWindow()
+{
+ // A flow remembers the last value of wmax,
+ // before it updates wmax for the current congestion event.
+
+ // Current wmax < last_wmax
+ if (m_cubicOptions.enableFastConv && m_cwnd < m_lastWmax) {
+ m_lastWmax = m_cwnd;
+ m_wmax = m_cwnd * (1.0 + m_cubicOptions.cubicBeta) / 2.0;
+ }
+ else {
+ // Save old cwnd as wmax
+ m_lastWmax = m_cwnd;
+ m_wmax = m_cwnd;
+ }
+
+ m_ssthresh = std::max(m_options.initCwnd, m_cwnd * m_cubicOptions.cubicBeta);
+ m_cwnd = m_ssthresh;
+ m_lastDecrease = time::steady_clock::now();
+
+ emitSignal(afterCwndChange, time::steady_clock::now() - getStartTime(), m_cwnd);
+}
+
+std::ostream&
+operator<<(std::ostream& os, const PipelineInterestsCubicOptions& options)
+{
+ os << static_cast<const PipelineInterestsAdaptiveOptions&>(options)
+ << "Cubic pipeline parameters:\n"
+ << "\tFast convergence = " << (options.enableFastConv ? "yes" : "no") << "\n"
+ << "\tCubic beta = " << options.cubicBeta << "\n";
+ return os;
+}
+
+} // namespace chunks
+} // namespace ndn
diff --git a/tools/chunks/catchunks/pipeline-interests-cubic.hpp b/tools/chunks/catchunks/pipeline-interests-cubic.hpp
new file mode 100644
index 0000000..11d3100
--- /dev/null
+++ b/tools/chunks/catchunks/pipeline-interests-cubic.hpp
@@ -0,0 +1,85 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2016-2019, Regents of the University of California,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University.
+ *
+ * This file is part of ndn-tools (Named Data Networking Essential Tools).
+ * See AUTHORS.md for complete list of ndn-tools authors and contributors.
+ *
+ * ndn-tools is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * ndn-tools is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * ndn-tools, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * See AUTHORS.md for complete list of ndn-cxx authors and contributors.
+ *
+ * @author Klaus Schneider
+ */
+
+#ifndef NDN_TOOLS_CHUNKS_CATCHUNKS_PIPELINE_INTERESTS_CUBIC_HPP
+#define NDN_TOOLS_CHUNKS_CATCHUNKS_PIPELINE_INTERESTS_CUBIC_HPP
+
+#include "pipeline-interests-adaptive.hpp"
+
+namespace ndn {
+namespace chunks {
+
+class PipelineInterestsCubicOptions : public PipelineInterestsAdaptiveOptions
+{
+public:
+ explicit
+ PipelineInterestsCubicOptions(const PipelineInterestsAdaptiveOptions& options =
+ PipelineInterestsAdaptiveOptions())
+ : PipelineInterestsAdaptiveOptions(options)
+ {
+ }
+
+public:
+ bool enableFastConv = false; ///< use cubic fast convergence
+ double cubicBeta = 0.7; ///< multiplicative decrease factor (from Linux kernel: 717/1024)
+};
+
+std::ostream&
+operator<<(std::ostream& os, const PipelineInterestsCubicOptions& options);
+
+/**
+ * @brief Implements Cubic window increase and decrease.
+ *
+ * This implementation follows the RFC8312 https://tools.ietf.org/html/rfc8312
+ * and the Linux kernel implementation https://github.com/torvalds/linux/blob/master/net/ipv4/tcp_cubic.c
+ */
+class PipelineInterestsCubic : public PipelineInterestsAdaptive
+{
+public:
+ using Options = PipelineInterestsCubicOptions;
+
+public:
+ PipelineInterestsCubic(Face& face, RttEstimator& rttEstimator,
+ const Options& options = Options());
+
+private:
+ void
+ increaseWindow() final;
+
+ void
+ decreaseWindow() final;
+
+private:
+ const Options m_cubicOptions;
+
+ double m_wmax = 0.0; ///< window size before last window decrease
+ double m_lastWmax = 0.0; ///< last wmax
+ time::steady_clock::TimePoint m_lastDecrease; ///< time of last window decrease
+};
+
+} // namespace chunks
+} // namespace ndn
+
+#endif // NDN_TOOLS_CHUNKS_CATCHUNKS_PIPELINE_INTERESTS_CUBIC_HPP
diff --git a/tools/chunks/catchunks/rtt-estimator.hpp b/tools/chunks/catchunks/rtt-estimator.hpp
index 6f10326..47f2ac8 100644
--- a/tools/chunks/catchunks/rtt-estimator.hpp
+++ b/tools/chunks/catchunks/rtt-estimator.hpp
@@ -57,7 +57,7 @@
: isVerbose(false)
, alpha(0.125)
, beta(0.25)
- , k(4)
+ , k(8)
, initialRto(1000.0)
, minRto(200.0)
, maxRto(20000.0)