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