fw: ASF: Fix implementation not matching technical report
This commit resolves several issues. First, a bug was discovered
regarding the usage of std::set objects when ranking faces for
forwarding and probing purposes. These objects enforce uniqueness;
however, this is defined based on the comparison function provided.
As no fields that were inherently unique were used to rank faces, this
would mean that a face with matching ranking information as one
inserted previously would be blocked from being inserted into face
ranking for forwarding and probing. We add faceId as a tiebreaker to
ensure deterministic behavior in these cases. We also fix an issue
where the count of consecutive silent timeouts was not properly cleared
upon the receipt of data or when a timeout was marked.
Additionally, this commit replaces previous implementations of the
ranking code for forwarding and probing. This is partially in order
to eliminate bugs introduced by incorrect implementations of the ranking
for probing and forwarding, as well as trying to make the code easier
to understand and maintain. This included removing a specific
optimization in probing by including unmeasured faces in the
ranking rather than have probes to unmeasured faces be ordered
based on undefined metrics (in practice, tied faces were inserted
in route creation order). However, we did make the choice to add
cost as a tiebreaker for working measured faces, as was the case
with the initial implementation for forwarding.
Refs #5310
Change-Id: Iabfdafea764fe24fe6c478a6073734e51aaf9fa1
diff --git a/daemon/fw/asf-measurements.hpp b/daemon/fw/asf-measurements.hpp
index 4883315..10c081c 100644
--- a/daemon/fw/asf-measurements.hpp
+++ b/daemon/fw/asf-measurements.hpp
@@ -35,8 +35,9 @@
namespace nfd::fw::asf {
-/** \brief Strategy information for each face in a namespace
-*/
+/**
+ * \brief Strategy information for each face in a namespace.
+ */
class FaceInfo
{
public:
@@ -72,12 +73,6 @@
cancelTimeout(interestName);
}
- bool
- hasTimeout() const
- {
- return getLastRtt() == RTT_TIMEOUT;
- }
-
time::nanoseconds
getLastRtt() const
{
@@ -123,7 +118,8 @@
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
-/** \brief Stores strategy information about each face in this namespace
+/**
+ * \brief Stores strategy information about each face in this namespace.
*/
class NamespaceInfo final : public StrategyInfo
{
@@ -183,7 +179,8 @@
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
-/** \brief Helper class to retrieve and create strategy measurements
+/**
+ * \brief Helper class to retrieve and create strategy measurements.
*/
class AsfMeasurements : noncopyable
{
diff --git a/daemon/fw/asf-probing-module.cpp b/daemon/fw/asf-probing-module.cpp
index fb07db2..d186d22 100644
--- a/daemon/fw/asf-probing-module.cpp
+++ b/daemon/fw/asf-probing-module.cpp
@@ -57,14 +57,94 @@
});
}
+static auto
+getFaceRankForProbing(const FaceStats& fs) noexcept
+{
+ // The RTT is used to store the status of the face:
+ // - A positive value indicates data was received and is assumed to indicate a working face (group 1),
+ // - RTT_NO_MEASUREMENT indicates a face is unmeasured (group 2),
+ // - RTT_TIMEOUT indicates a face is timed out (group 3).
+ // These groups are defined in the technical report.
+ //
+ // Unlike during forwarding, we adjust the ranking such that unmeasured faces (group 2)
+ // are prioritized before working faces (group 1), and working faces are prioritized
+ // before timed out faces (group 3). We assign each group a priority value from 1-3
+ // to ensure lowest-to-highest ordering consistent with this logic.
+ // Additionally, unmeasured faces will always be chosen to probe if they exist.
+
+ // Working faces are ranked second in priority; if RTT is not
+ // a special value, we assume the face to be in this group.
+ int priority = 2;
+ if (fs.rtt == FaceInfo::RTT_NO_MEASUREMENT) {
+ priority = 1;
+ }
+ else if (fs.rtt == FaceInfo::RTT_TIMEOUT) {
+ priority = 3;
+ }
+
+ // We set SRTT by default to the max value; if a face is working, we instead set it to the actual value.
+ // Unmeasured and timed out faces are not sorted by SRTT.
+ auto srtt = priority == 2 ? fs.srtt : time::nanoseconds::max();
+
+ // For ranking, group takes the priority over SRTT (if present) or cost, SRTT (if present)
+ // takes priority over cost, and cost takes priority over FaceId.
+ // FaceId is included to ensure all unique entries are included in the ranking (see #5310).
+ return std::tuple(priority, srtt, fs.cost, fs.face->getId());
+}
+
+bool
+ProbingModule::FaceStatsProbingCompare::operator()(const FaceStats& lhs, const FaceStats& rhs) const noexcept
+{
+ return getFaceRankForProbing(lhs) < getFaceRankForProbing(rhs);
+}
+
+static Face*
+chooseFace(const ProbingModule::FaceStatsProbingSet& rankedFaces)
+{
+ static std::uniform_real_distribution<> randDist;
+ static auto& rng = ndn::random::getRandomNumberEngine();
+ const double randomNumber = randDist(rng);
+
+ const auto nFaces = rankedFaces.size();
+ const double rankSum = (nFaces + 1) * nFaces / 2;
+ size_t rank = 1;
+ double offset = 0.0;
+
+ for (const auto& faceStat : rankedFaces) {
+ // n + 1 - j
+ // p = ---------
+ // sum(ranks)
+ double probability = static_cast<double>(nFaces + 1 - rank) / rankSum;
+ rank++;
+
+ // Is the random number within the bounds of this face's probability + the previous faces'
+ // probability?
+ //
+ // e.g. (FaceId: 1, p=0.5), (FaceId: 2, p=0.33), (FaceId: 3, p=0.17)
+ // randomNumber = 0.92
+ //
+ // The face with FaceId: 3 should be picked
+ // (0.68 < 0.5 + 0.33 + 0.17) == true
+ //
+ offset += probability;
+ if (randomNumber <= offset) {
+ // Found face to probe
+ return faceStat.face;
+ }
+ }
+
+ // Given a set of Faces, this method should always select a Face to probe
+ NDN_CXX_UNREACHABLE;
+}
+
Face*
ProbingModule::getFaceToProbe(const Face& inFace, const Interest& interest,
const fib::Entry& fibEntry, const Face& faceUsed)
{
- FaceInfoFacePairSet rankedFaces;
+ FaceStatsProbingSet rankedFaces;
- // Put eligible faces into rankedFaces. If a face does not have an RTT measurement,
- // immediately pick the face for probing
+ // Put eligible faces into rankedFaces. If one or more faces do not have an RTT measurement,
+ // the lowest ranked one will always be returned.
for (const auto& hop : fibEntry.getNextHops()) {
Face& hopFace = hop.getFace();
@@ -76,13 +156,13 @@
}
FaceInfo* info = m_measurements.getFaceInfo(fibEntry, interest.getName(), hopFace.getId());
- // If no RTT has been recorded, probe this face
if (info == nullptr || info->getLastRtt() == FaceInfo::RTT_NO_MEASUREMENT) {
- return &hopFace;
+ rankedFaces.insert({&hopFace, FaceInfo::RTT_NO_MEASUREMENT,
+ FaceInfo::RTT_NO_MEASUREMENT, hop.getCost()});
}
-
- // Add FaceInfo to container sorted by RTT
- rankedFaces.insert({info, &hopFace});
+ else {
+ rankedFaces.insert({&hopFace, info->getLastRtt(), info->getSrtt(), hop.getCost()});
+ }
}
if (rankedFaces.empty()) {
@@ -90,6 +170,11 @@
return nullptr;
}
+ // If the top face is unmeasured, immediately return it.
+ if (rankedFaces.begin()->rtt == FaceInfo::RTT_NO_MEASUREMENT) {
+ return rankedFaces.begin()->face;
+ }
+
return chooseFace(rankedFaces);
}
@@ -103,7 +188,8 @@
if (!info.isFirstProbeScheduled()) {
// Schedule first probe between 0 and 5 seconds
static std::uniform_int_distribution<> randDist(0, 5000);
- auto interval = randDist(ndn::random::getRandomNumberEngine());
+ static auto& rng = ndn::random::getRandomNumberEngine();
+ auto interval = randDist(rng);
scheduleProbe(fibEntry, time::milliseconds(interval));
info.setIsFirstProbeScheduled(true);
}
@@ -122,48 +208,6 @@
scheduleProbe(fibEntry, m_probingInterval);
}
-Face*
-ProbingModule::chooseFace(const FaceInfoFacePairSet& rankedFaces)
-{
- static std::uniform_real_distribution<> randDist;
- double randomNumber = randDist(ndn::random::getRandomNumberEngine());
- uint64_t rankSum = (rankedFaces.size() + 1) * rankedFaces.size() / 2;
-
- uint64_t rank = 1;
- double offset = 0.0;
-
- for (const auto& pair : rankedFaces) {
- double probability = getProbingProbability(rank++, rankSum, rankedFaces.size());
-
- // Is the random number within the bounds of this face's probability + the previous faces'
- // probability?
- //
- // e.g. (FaceId: 1, p=0.5), (FaceId: 2, p=0.33), (FaceId: 3, p=0.17)
- // randomNumber = 0.92
- //
- // The face with FaceId: 3 should be picked
- // (0.68 < 0.5 + 0.33 + 0.17) == true
- //
- if (randomNumber <= offset + probability) {
- // Found face to probe
- return pair.second;
- }
- offset += probability;
- }
-
- // Given a set of Faces, this method should always select a Face to probe
- NDN_CXX_UNREACHABLE;
-}
-
-double
-ProbingModule::getProbingProbability(uint64_t rank, uint64_t rankSum, uint64_t nFaces)
-{
- // p = n + 1 - j ; n: # faces
- // ---------
- // sum(ranks)
- return static_cast<double>(nFaces + 1 - rank) / rankSum;
-}
-
void
ProbingModule::setProbingInterval(time::milliseconds probingInterval)
{
diff --git a/daemon/fw/asf-probing-module.hpp b/daemon/fw/asf-probing-module.hpp
index 0d6b212..173f21a 100644
--- a/daemon/fw/asf-probing-module.hpp
+++ b/daemon/fw/asf-probing-module.hpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
- * Copyright (c) 2014-2022, Regents of the University of California,
+ * Copyright (c) 2014-2024, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -30,7 +30,19 @@
namespace nfd::fw::asf {
-/** \brief ASF Probing Module
+/**
+ * \brief Container for ranking-related values.
+ */
+struct FaceStats
+{
+ Face* face = nullptr;
+ time::nanoseconds rtt = 0_ns;
+ time::nanoseconds srtt = 0_ns;
+ uint64_t cost = 0;
+};
+
+/**
+ * \brief ASF Probing Module.
*/
class ProbingModule
{
@@ -60,36 +72,17 @@
return m_probingInterval;
}
-private:
- // Used to associate FaceInfo with the face in a NextHop
- using FaceInfoFacePair = std::pair<FaceInfo*, Face*>;
-
- struct FaceInfoCompare
- {
- bool
- operator()(const FaceInfoFacePair& leftPair, const FaceInfoFacePair& rightPair) const
- {
- const FaceInfo& lhs = *leftPair.first;
- const FaceInfo& rhs = *rightPair.first;
-
- // Sort by RTT: if a face has timed-out, rank it behind non-timed-out faces
- return (!lhs.hasTimeout() && rhs.hasTimeout()) ||
- (lhs.hasTimeout() == rhs.hasTimeout() && lhs.getSrtt() < rhs.getSrtt());
- }
- };
-
- using FaceInfoFacePairSet = std::set<FaceInfoFacePair, FaceInfoCompare>;
-
- static Face*
- chooseFace(const FaceInfoFacePairSet& rankedFaces);
-
- static double
- getProbingProbability(uint64_t rank, uint64_t rankSum, uint64_t nFaces);
-
public:
static constexpr time::milliseconds DEFAULT_PROBING_INTERVAL = 1_min;
static constexpr time::milliseconds MIN_PROBING_INTERVAL = 1_s;
+ struct FaceStatsProbingCompare
+ {
+ bool
+ operator()(const FaceStats& lhs, const FaceStats& rhs) const noexcept;
+ };
+ using FaceStatsProbingSet = std::set<FaceStats, FaceStatsProbingCompare>;
+
private:
time::milliseconds m_probingInterval;
AsfMeasurements& m_measurements;
diff --git a/daemon/fw/asf-strategy.cpp b/daemon/fw/asf-strategy.cpp
index 2373c69..24aa9d7 100644
--- a/daemon/fw/asf-strategy.cpp
+++ b/daemon/fw/asf-strategy.cpp
@@ -35,8 +35,6 @@
AsfStrategy::AsfStrategy(Forwarder& forwarder, const Name& name)
: Strategy(forwarder)
, ProcessNackTraits(this)
- , m_measurements(getMeasurements())
- , m_probing(m_measurements)
{
ParsedInstanceName parsed = parseInstanceName(name);
if (parsed.version && *parsed.version != getStrategyName()[-1].toVersion()) {
@@ -73,7 +71,7 @@
// Check if the interest is new and, if so, skip the retx suppression check
if (!hasPendingOutRecords(*pitEntry)) {
- auto* faceToUse = getBestFaceForForwarding(interest, ingress.face, fibEntry, pitEntry);
+ auto faceToUse = getBestFaceForForwarding(interest, ingress.face, fibEntry, pitEntry);
if (faceToUse == nullptr) {
NFD_LOG_INTEREST_FROM(interest, ingress, "new no-nexthop");
sendNoRouteNack(ingress.face, pitEntry);
@@ -86,7 +84,7 @@
return;
}
- auto* faceToUse = getBestFaceForForwarding(interest, ingress.face, fibEntry, pitEntry, false);
+ auto faceToUse = getBestFaceForForwarding(interest, ingress.face, fibEntry, pitEntry, false);
if (faceToUse != nullptr) {
auto suppressResult = m_retxSuppression->decidePerUpstream(*pitEntry, *faceToUse);
if (suppressResult == RetxSuppressionResult::SUPPRESS) {
@@ -160,6 +158,7 @@
// Extend PIT entry timer to allow slower probes to arrive
this->setExpiryTimer(pitEntry, 50_ms);
faceInfo->cancelTimeout(data.getName());
+ faceInfo->setNTimeouts(0);
}
void
@@ -218,50 +217,52 @@
m_probing.afterForwardingProbe(fibEntry, interest.getName());
}
-struct FaceStats
+static auto
+getFaceRankForForwarding(const FaceStats& fs) noexcept
{
- Face* face;
- time::nanoseconds rtt;
- time::nanoseconds srtt;
- uint64_t cost;
-};
+ // The RTT is used to store the status of the face:
+ // - A positive value indicates data was received and is assumed to indicate a working face (group 1),
+ // - RTT_NO_MEASUREMENT indicates a face is unmeasured (group 2),
+ // - RTT_TIMEOUT indicates a face is timed out (group 3).
+ // These groups are defined in the technical report.
+ //
+ // When forwarding, we assume an order where working faces (group 1) are ranked
+ // higher than unmeasured faces (group 2), and unmeasured faces are ranked higher
+ // than timed out faces (group 3). We assign each group a priority value from 1-3
+ // to ensure lowest-to-highest ordering consistent with this logic.
-struct FaceStatsCompare
-{
- bool
- operator()(const FaceStats& lhs, const FaceStats& rhs) const
- {
- time::nanoseconds lhsValue = getValueForSorting(lhs);
- time::nanoseconds rhsValue = getValueForSorting(rhs);
-
- // Sort by RTT and then by cost
- return std::tie(lhsValue, lhs.cost) < std::tie(rhsValue, rhs.cost);
+ // Working faces are ranked first in priority; if RTT is not
+ // a special value, we assume the face to be in this group.
+ int priority = 1;
+ if (fs.rtt == FaceInfo::RTT_NO_MEASUREMENT) {
+ priority = 2;
+ }
+ else if (fs.rtt == FaceInfo::RTT_TIMEOUT) {
+ priority = 3;
}
-private:
- static time::nanoseconds
- getValueForSorting(const FaceStats& stats)
- {
- // These values allow faces with no measurements to be ranked better than timeouts
- // srtt < RTT_NO_MEASUREMENT < RTT_TIMEOUT
- if (stats.rtt == FaceInfo::RTT_TIMEOUT) {
- return time::nanoseconds::max();
- }
- else if (stats.rtt == FaceInfo::RTT_NO_MEASUREMENT) {
- return time::nanoseconds::max() / 2;
- }
- else {
- return stats.srtt;
- }
- }
-};
+ // We set SRTT by default to the max value; if a face is working, we instead set it to the actual value.
+ // Unmeasured and timed out faces are not sorted by SRTT.
+ auto srtt = priority == 1 ? fs.srtt : time::nanoseconds::max();
+
+ // For ranking, group takes the priority over SRTT (if present) or cost, SRTT (if present)
+ // takes priority over cost, and cost takes priority over FaceId.
+ // FaceId is included to ensure all unique entries are included in the ranking (see #5310)
+ return std::tuple(priority, srtt, fs.cost, fs.face->getId());
+}
+
+bool
+AsfStrategy::FaceStatsForwardingCompare::operator()(const FaceStats& lhs, const FaceStats& rhs) const noexcept
+{
+ return getFaceRankForForwarding(lhs) < getFaceRankForForwarding(rhs);
+}
Face*
AsfStrategy::getBestFaceForForwarding(const Interest& interest, const Face& inFace,
const fib::Entry& fibEntry, const shared_ptr<pit::Entry>& pitEntry,
bool isInterestNew)
{
- std::set<FaceStats, FaceStatsCompare> rankedFaces;
+ FaceStatsForwardingSet rankedFaces;
auto now = time::steady_clock::now();
for (const auto& nh : fibEntry.getNextHops()) {
@@ -311,6 +312,7 @@
else {
NFD_LOG_TRACE(interestName << " face=" << faceId << " timeout-count=" << nTimeouts);
faceInfo.recordTimeout(interestName);
+ faceInfo.setNTimeouts(0);
}
}
diff --git a/daemon/fw/asf-strategy.hpp b/daemon/fw/asf-strategy.hpp
index 4607d4e..83bff13 100644
--- a/daemon/fw/asf-strategy.hpp
+++ b/daemon/fw/asf-strategy.hpp
@@ -86,11 +86,18 @@
sendNoRouteNack(Face& face, const shared_ptr<pit::Entry>& pitEntry);
private:
- AsfMeasurements m_measurements;
+ AsfMeasurements m_measurements{getMeasurements()};
NFD_PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+ struct FaceStatsForwardingCompare
+ {
+ bool
+ operator()(const FaceStats& lhs, const FaceStats& rhs) const noexcept;
+ };
+ using FaceStatsForwardingSet = std::set<FaceStats, FaceStatsForwardingCompare>;
+
std::unique_ptr<RetxSuppressionExponential> m_retxSuppression;
- ProbingModule m_probing;
+ ProbingModule m_probing{m_measurements};
size_t m_nMaxTimeouts = 3;
friend ProcessNackTraits<AsfStrategy>;