38 , m_measurements(getMeasurements())
39 , m_probing(m_measurements)
43 NDN_THROW(std::invalid_argument(
44 "AsfStrategy does not support version " + to_string(*parsed.
version)));
49 auto probingInterval = params.
getOrDefault<time::milliseconds::rep>(
"probing-interval",
52 m_nMaxTimeouts = params.
getOrDefault<
size_t>(
"max-timeouts", m_nMaxTimeouts);
56 NDN_LOG_DEBUG(*m_retxSuppression);
58 <<
" max-timeouts=" << m_nMaxTimeouts);
64 static const auto strategyName = Name(
"/localhost/nfd/strategy/asf").appendVersion(4);
70 const shared_ptr<pit::Entry>& pitEntry)
72 const auto& fibEntry = this->
lookupFib(*pitEntry);
76 auto* faceToUse = getBestFaceForForwarding(interest, ingress.
face, fibEntry, pitEntry);
77 if (faceToUse ==
nullptr) {
78 NFD_LOG_DEBUG(interest <<
" new-interest from=" << ingress <<
" no-nexthop");
79 sendNoRouteNack(ingress.
face, pitEntry);
82 NFD_LOG_DEBUG(interest <<
" new-interest from=" << ingress <<
" forward-to=" << faceToUse->getId());
83 forwardInterest(interest, *faceToUse, fibEntry, pitEntry);
84 sendProbe(interest, ingress, *faceToUse, fibEntry, pitEntry);
89 auto* faceToUse = getBestFaceForForwarding(interest, ingress.
face, fibEntry, pitEntry,
false);
90 if (faceToUse !=
nullptr) {
91 auto suppressResult = m_retxSuppression->decidePerUpstream(*pitEntry, *faceToUse);
95 <<
" forward-to=" << faceToUse->getId() <<
" suppressed");
100 NFD_LOG_DEBUG(interest <<
" retx-interest from=" << ingress <<
" forward-to=" << faceToUse->getId());
101 auto* outRecord = forwardInterest(interest, *faceToUse, fibEntry, pitEntry);
103 m_retxSuppression->incrementIntervalForOutRecord(*outRecord);
111 const auto& nexthops = fibEntry.getNextHops();
113 if (it == nexthops.end()) {
114 NFD_LOG_DEBUG(interest <<
" retx-interest from=" << ingress <<
" no eligible nexthop");
117 auto& outFace = it->getFace();
118 auto suppressResult = m_retxSuppression->decidePerUpstream(*pitEntry, outFace);
121 <<
" retry-to=" << outFace.getId() <<
" suppressed");
124 NFD_LOG_DEBUG(interest <<
" retx-interest from=" << ingress <<
" retry-to=" << outFace.getId());
127 auto* outRecord =
sendInterest(interest, outFace, pitEntry);
129 m_retxSuppression->incrementIntervalForOutRecord(*outRecord);
136 const shared_ptr<pit::Entry>& pitEntry)
139 if (namespaceInfo ==
nullptr) {
140 NFD_LOG_DEBUG(pitEntry->getName() <<
" data from=" << ingress <<
" no-measurements");
146 if (faceInfo ==
nullptr) {
147 NFD_LOG_DEBUG(pitEntry->getName() <<
" data from=" << ingress <<
" no-face-info");
151 auto outRecord = pitEntry->getOutRecord(ingress.
face);
152 if (outRecord == pitEntry->out_end()) {
153 NFD_LOG_DEBUG(pitEntry->getName() <<
" data from=" << ingress <<
" no-out-record");
156 faceInfo->
recordRtt(time::steady_clock::now() - outRecord->getLastRenewed());
157 NFD_LOG_DEBUG(pitEntry->getName() <<
" data from=" << ingress
170 const shared_ptr<pit::Entry>& pitEntry)
172 NFD_LOG_DEBUG(nack.getInterest() <<
" nack from=" << ingress <<
" reason=" << nack.getReason());
173 onTimeoutOrNack(pitEntry->getName(), ingress.
face.
getId(),
true);
177 AsfStrategy::forwardInterest(
const Interest& interest,
Face& outFace,
const fib::Entry& fibEntry,
178 const shared_ptr<pit::Entry>& pitEntry)
180 const auto& interestName = interest.getName();
181 auto faceId = outFace.
getId();
183 auto* outRecord =
sendInterest(interest, outFace, pitEntry);
193 [
this, name = interestName, faceId] {
194 onTimeoutOrNack(name, faceId,
false);
197 <<
" in " << time::duration_cast<time::milliseconds>(timeout));
204 AsfStrategy::sendProbe(
const Interest& interest,
const FaceEndpoint& ingress,
const Face& faceToUse,
205 const fib::Entry& fibEntry,
const shared_ptr<pit::Entry>& pitEntry)
210 Face* faceToProbe = m_probing.
getFaceToProbe(ingress.face, interest, fibEntry, faceToUse);
211 if (faceToProbe ==
nullptr)
214 Interest probeInterest(interest);
215 probeInterest.refreshNonce();
216 NFD_LOG_TRACE(
"Sending probe " << probeInterest <<
" to=" << faceToProbe->getId());
217 forwardInterest(probeInterest, *faceToProbe, fibEntry, pitEntry);
225 time::nanoseconds rtt;
226 time::nanoseconds srtt;
230 struct FaceStatsCompare
233 operator()(
const FaceStats& lhs,
const FaceStats& rhs)
const
235 time::nanoseconds lhsValue = getValueForSorting(lhs);
236 time::nanoseconds rhsValue = getValueForSorting(rhs);
239 return std::tie(lhsValue, lhs.cost) < std::tie(rhsValue, rhs.cost);
243 static time::nanoseconds
244 getValueForSorting(
const FaceStats& stats)
249 return time::nanoseconds::max();
252 return time::nanoseconds::max() / 2;
261 AsfStrategy::getBestFaceForForwarding(
const Interest& interest,
const Face& inFace,
262 const fib::Entry& fibEntry,
const shared_ptr<pit::Entry>& pitEntry,
265 std::set<FaceStats, FaceStatsCompare> rankedFaces;
267 auto now = time::steady_clock::now();
268 for (
const auto& nh : fibEntry.getNextHops()) {
273 const FaceInfo* info = m_measurements.
getFaceInfo(fibEntry, interest.getName(), nh.getFace().getId());
274 if (info ==
nullptr) {
279 rankedFaces.insert({&nh.getFace(), info->getLastRtt(), info->getSrtt(), nh.getCost()});
283 auto it = rankedFaces.begin();
284 return it != rankedFaces.end() ? it->face :
nullptr;
288 AsfStrategy::onTimeoutOrNack(
const Name& interestName,
FaceId faceId,
bool isNack)
290 NamespaceInfo* namespaceInfo = m_measurements.
getNamespaceInfo(interestName);
291 if (namespaceInfo ==
nullptr) {
292 NFD_LOG_TRACE(interestName <<
" FibEntry has been removed since timeout scheduling");
296 FaceInfo* fiPtr = namespaceInfo->getFaceInfo(faceId);
297 if (fiPtr ==
nullptr) {
298 NFD_LOG_TRACE(interestName <<
" FaceInfo id=" << faceId <<
" has been removed since timeout scheduling");
302 auto& faceInfo = *fiPtr;
306 if (nTimeouts < m_nMaxTimeouts && !isNack) {
307 NFD_LOG_TRACE(interestName <<
" face=" << faceId <<
" timeout-count=" << nTimeouts <<
" ignoring");
309 namespaceInfo->extendFaceInfoLifetime(faceInfo, faceId);
313 NFD_LOG_TRACE(interestName <<
" face=" << faceId <<
" timeout-count=" << nTimeouts);
319 AsfStrategy::sendNoRouteNack(Face& face,
const shared_ptr<pit::Entry>& pitEntry)
321 lp::NackHeader nackHeader;
322 nackHeader.setReason(lp::NackReason::NO_ROUTE);
323 this->
sendNack(nackHeader, face, pitEntry);
This file contains common algorithms used by forwarding strategies.
Represents a face-endpoint pair in the forwarder.
Main class of NFD's forwarding engine.
Generalization of a network interface.
FaceId getId() const noexcept
Returns the face ID.
Represents an entry in the FIB.
const Name & getPrefix() const
static std::unique_ptr< RetxSuppressionExponential > construct(const StrategyParameters ¶ms)
Base class of all forwarding strategies.
void rejectPendingInterest(const shared_ptr< pit::Entry > &pitEntry)
Schedule the PIT entry for immediate deletion.
const fib::Entry & lookupFib(const pit::Entry &pitEntry) const
Performs a FIB lookup, considering Link object if present.
bool sendNack(const lp::NackHeader &header, Face &egress, const shared_ptr< pit::Entry > &pitEntry)
Send a Nack packet.
pit::OutRecord * sendInterest(const Interest &interest, Face &egress, const shared_ptr< pit::Entry > &pitEntry)
Send an Interest packet.
static ParsedInstanceName parseInstanceName(const Name &input)
Parse a strategy instance name.
void setExpiryTimer(const shared_ptr< pit::Entry > &pitEntry, time::milliseconds duration)
Schedule the PIT entry to be erased after duration.
void setInstanceName(const Name &name) noexcept
Set strategy instance name.
static StrategyParameters parseParameters(const PartialName ¶ms)
Parse strategy parameters encoded in a strategy instance name.
static Name makeInstanceName(const Name &input, const Name &strategyName)
Construct a strategy instance name.
std::enable_if_t< std::is_signed_v< T >, T > getOrDefault(const key_type &key, const T &defaultVal) const
NamespaceInfo & getOrCreateNamespaceInfo(const fib::Entry &fibEntry, const Name &prefix)
FaceInfo & getOrCreateFaceInfo(const fib::Entry &fibEntry, const Name &interestName, FaceId faceId)
FaceInfo * getFaceInfo(const fib::Entry &fibEntry, const Name &interestName, FaceId faceId)
NamespaceInfo * getNamespaceInfo(const Name &prefix)
Adaptive SRTT-based forwarding strategy.
static const Name & getStrategyName()
void afterReceiveNack(const lp::Nack &nack, const FaceEndpoint &ingress, const shared_ptr< pit::Entry > &pitEntry) override
Trigger after a Nack is received.
AsfStrategy(Forwarder &forwarder, const Name &name=getStrategyName())
void afterReceiveInterest(const Interest &interest, const FaceEndpoint &ingress, const shared_ptr< pit::Entry > &pitEntry) override
Trigger after an Interest is received.
void beforeSatisfyInterest(const Data &data, const FaceEndpoint &ingress, const shared_ptr< pit::Entry > &pitEntry) override
Trigger before a PIT entry is satisfied.
Strategy information for each face in a namespace.
static constexpr time::nanoseconds RTT_TIMEOUT
void cancelTimeout(const Name &prefix)
bool isTimeoutScheduled() const
size_t getNTimeouts() const
static constexpr time::nanoseconds RTT_NO_MEASUREMENT
time::nanoseconds getSrtt() const
void setNTimeouts(size_t nTimeouts)
time::nanoseconds getLastRtt() const
void recordTimeout(const Name &interestName)
void recordRtt(time::nanoseconds rtt)
time::nanoseconds scheduleTimeout(const Name &interestName, scheduler::EventCallback cb)
Stores strategy information about each face in this namespace.
FaceInfo * getFaceInfo(FaceId faceId)
void extendFaceInfoLifetime(FaceInfo &info, FaceId faceId)
Face * getFaceToProbe(const Face &inFace, const Interest &interest, const fib::Entry &fibEntry, const Face &faceUsed)
bool isProbingNeeded(const fib::Entry &fibEntry, const Name &interestName)
time::milliseconds getProbingInterval() const
void afterForwardingProbe(const fib::Entry &fibEntry, const Name &interestName)
void setProbingInterval(time::milliseconds probingInterval)
Contains information about an Interest toward an outgoing face.
#define NFD_LOG_INIT(name)
uint64_t FaceId
Identifies a face.
@ SUPPRESS
Interest is retransmission and should be suppressed.
@ FORWARD
Interest is retransmission and should be forwarded.
bool isNextHopEligible(const Face &inFace, const Interest &interest, const fib::NextHop &nexthop, const shared_ptr< pit::Entry > &pitEntry, bool wantUnused, time::steady_clock::time_point now)
Determines whether a NextHop is eligible, i.e., not the same inFace.
fib::NextHopList::const_iterator findEligibleNextHopWithEarliestOutRecord(const Face &inFace, const Interest &interest, const fib::NextHopList &nexthops, const shared_ptr< pit::Entry > &pitEntry)
Pick an eligible NextHop with earliest out-record.
NFD_REGISTER_STRATEGY(SelfLearningStrategy)
bool hasPendingOutRecords(const pit::Entry &pitEntry)
Determine whether pitEntry has any pending out-records.
std::optional< uint64_t > version
The strategy version number, if present.
PartialName parameters
Parameter components, may be empty.