catchunks: Implement CUBIC window adaptation
Also increase the RTT estimator multiplier k to 8.
Change-Id: I68c5096ac0da854f071bab5f7519b1c144f20ca1
refs: #4861
diff --git a/tools/chunks/README.md b/tools/chunks/README.md
index 0c76fe8..f1cf967 100644
--- a/tools/chunks/README.md
+++ b/tools/chunks/README.md
@@ -13,11 +13,11 @@
## Version discovery methods in ndncatchunks
-* `fixed` : sends an interest attempting to find a data packet with the
+* `fixed` : sends an Interest attempting to find a data packet with the
specified prefix and version number. A version component must be present at the
end of the user-specified NDN name.
-* `realtime` : sends discovery interests to fetch metadata of the solicited content from which
+* `realtime` : sends discovery Interests to fetch metadata of the solicited content from which
the data version will be resolved.
The version number of the solicited content is included in the name of returned
metadata data packet.
@@ -32,14 +32,16 @@
* `fixed`: maintains a fixed-size window of Interests in flight; the window size is configurable
via a command line option and defaults to 1.
-* `aimd` : sends Interests using an additive-increase/multiplicative-decrease (AIMD) algorithm to
- control the window size. By default, a Conservative Loss Adaptation algorithm is adopted
- combining with the AIMD algorithm, that is, at most one window decrease will be
- performed per round-trip-time. For details please refer to:
- [A Practical Congestion Control Scheme for Named Data
- Networking](https://www.researchgate.net/publication/306259672_A_Practical_Congestion_Control_Scheme_for_Named_Data_Networking)
+* `aimd` : adjusts the window size via additive-increase/multiplicative-decrease (AIMD).
+ By default, it uses a Conservative Window Adaptation, that is, the congestion window
+ will be decreased at most once per round-trip-time.
-The default Interest pipeline type is `aimd`.
+* `cubic`: adjusts the window size similar to the TCP CUBIC algorithm.
+ For details about both aimd and cubic please refer to:
+ [A Practical Congestion Control Scheme for Named Data
+ Networking](https://conferences2.sigcomm.org/acm-icn/2016/proceedings/p21-schneider.pdf)
+
+The default Interest pipeline type is `cubic`.
## Usage examples
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)