algorithm.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2014-2024, Regents of the University of California,
4  * Arizona Board of Regents,
5  * Colorado State University,
6  * University Pierre & Marie Curie, Sorbonne University,
7  * Washington University in St. Louis,
8  * Beijing Institute of Technology,
9  * The University of Memphis.
10  *
11  * This file is part of NFD (Named Data Networking Forwarding Daemon).
12  * See AUTHORS.md for complete list of NFD authors and contributors.
13  *
14  * NFD is free software: you can redistribute it and/or modify it under the terms
15  * of the GNU General Public License as published by the Free Software Foundation,
16  * either version 3 of the License, or (at your option) any later version.
17  *
18  * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
19  * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
20  * PURPOSE. See the GNU General Public License for more details.
21  *
22  * You should have received a copy of the GNU General Public License along with
23  * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
24  */
25 
26 #include "algorithm.hpp"
27 #include "scope-prefix.hpp"
28 #include "face/face.hpp"
29 
30 namespace nfd::fw {
31 
32 bool
33 wouldViolateScope(const Face& inFace, const Interest& interest, const Face& outFace)
34 {
35  if (outFace.getScope() == ndn::nfd::FACE_SCOPE_LOCAL) {
36  // forwarding to a local face is always allowed
37  return false;
38  }
39 
40  if (scope_prefix::LOCALHOST.isPrefixOf(interest.getName())) {
41  // localhost Interests cannot be forwarded to a non-local face
42  return true;
43  }
44 
45  if (scope_prefix::LOCALHOP.isPrefixOf(interest.getName())) {
46  // localhop Interests can be forwarded to a non-local face only if it comes from a local face
47  return inFace.getScope() != ndn::nfd::FACE_SCOPE_LOCAL;
48  }
49 
50  // Interest name is not subject to scope control
51  return false;
52 }
53 
54 int
55 findDuplicateNonce(const pit::Entry& pitEntry, Interest::Nonce nonce, const Face& face)
56 {
57  int dnw = DUPLICATE_NONCE_NONE;
58 
59  for (const pit::InRecord& inRecord : pitEntry.getInRecords()) {
60  if (inRecord.getLastNonce() == nonce) {
61  if (&inRecord.getFace() == &face) {
63  }
64  else {
66  }
67  }
68  }
69 
70  for (const pit::OutRecord& outRecord : pitEntry.getOutRecords()) {
71  if (outRecord.getLastNonce() == nonce) {
72  if (&outRecord.getFace() == &face) {
74  }
75  else {
77  }
78  }
79  }
80 
81  return dnw;
82 }
83 
84 bool
86 {
87  auto now = time::steady_clock::now();
88  return std::any_of(pitEntry.out_begin(), pitEntry.out_end(),
89  [&now] (const pit::OutRecord& outRecord) {
90  return outRecord.getExpiry() >= now &&
91  outRecord.getIncomingNack() == nullptr;
92  });
93 }
94 
95 time::steady_clock::time_point
96 getLastOutgoing(const pit::Entry& pitEntry)
97 {
98  pit::OutRecordCollection::const_iterator lastOutgoing = std::max_element(
99  pitEntry.out_begin(), pitEntry.out_end(),
100  [] (const pit::OutRecord& a, const pit::OutRecord& b) {
101  return a.getLastRenewed() < b.getLastRenewed();
102  });
103  BOOST_ASSERT(lastOutgoing != pitEntry.out_end());
104 
105  return lastOutgoing->getLastRenewed();
106 }
107 
108 fib::NextHopList::const_iterator
109 findEligibleNextHopWithEarliestOutRecord(const Face& inFace, const Interest& interest,
110  const fib::NextHopList& nexthops,
111  const shared_ptr<pit::Entry>& pitEntry)
112 {
113  auto found = nexthops.end();
114  auto earliestRenewed = time::steady_clock::time_point::max();
115 
116  for (auto it = nexthops.begin(); it != nexthops.end(); ++it) {
117  if (!isNextHopEligible(inFace, interest, *it, pitEntry))
118  continue;
119 
120  auto outRecord = pitEntry->findOutRecord(it->getFace());
121  BOOST_ASSERT(outRecord != pitEntry->out_end());
122  if (outRecord->getLastRenewed() < earliestRenewed) {
123  found = it;
124  earliestRenewed = outRecord->getLastRenewed();
125  }
126  }
127  return found;
128 }
129 
130 bool
131 isNextHopEligible(const Face& inFace, const Interest& interest,
132  const fib::NextHop& nexthop,
133  const shared_ptr<pit::Entry>& pitEntry,
134  bool wantUnused,
135  time::steady_clock::time_point now)
136 {
137  const Face& outFace = nexthop.getFace();
138 
139  // do not forward back to the same face, unless it is ad hoc
140  if ((outFace.getId() == inFace.getId() && outFace.getLinkType() != ndn::nfd::LINK_TYPE_AD_HOC) ||
141  (wouldViolateScope(inFace, interest, outFace)))
142  return false;
143 
144  if (wantUnused) {
145  // nexthop must not have unexpired out-record
146  auto outRecord = pitEntry->findOutRecord(outFace);
147  if (outRecord != pitEntry->out_end() && outRecord->getExpiry() > now) {
148  return false;
149  }
150  }
151  return true;
152 }
153 
154 } // namespace nfd::fw
This file contains common algorithms used by forwarding strategies.
Generalization of a network interface.
Definition: face.hpp:118
ndn::nfd::FaceScope getScope() const noexcept
Returns whether the face is local or non-local for scope control purposes.
Definition: face.hpp:232
ndn::nfd::LinkType getLinkType() const noexcept
Returns the link type of the face (point-to-point, multi-access, ...).
Definition: face.hpp:259
FaceId getId() const noexcept
Returns the face ID.
Definition: face.hpp:195
Represents a nexthop record in a FIB entry.
Definition: fib-entry.hpp:50
Face & getFace() const noexcept
Definition: fib-entry.hpp:59
Represents an entry in the Interest table (PIT).
Definition: pit-entry.hpp:197
const OutRecordCollection & getOutRecords() const noexcept
Returns the collection of out-records.
Definition: pit-entry.hpp:311
OutRecordCollection::iterator out_begin() noexcept
Definition: pit-entry.hpp:329
OutRecordCollection::iterator out_end() noexcept
Definition: pit-entry.hpp:341
const InRecordCollection & getInRecords() const noexcept
Returns the collection of in-records.
Definition: pit-entry.hpp:233
Contains information about an Interest from an incoming face.
Definition: pit-entry.hpp:107
Contains information about an Interest toward an outgoing face.
Definition: pit-entry.hpp:129
std::vector< NextHop > NextHopList
A collection of nexthops in a FIB entry.
Definition: fib-entry.hpp:84
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.
Definition: algorithm.cpp:131
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.
Definition: algorithm.cpp:109
@ DUPLICATE_NONCE_OUT_SAME
out-record of same face
Definition: algorithm.hpp:50
@ DUPLICATE_NONCE_NONE
no duplicate Nonce is found
Definition: algorithm.hpp:47
@ DUPLICATE_NONCE_IN_SAME
in-record of same face
Definition: algorithm.hpp:48
@ DUPLICATE_NONCE_OUT_OTHER
out-record of other face
Definition: algorithm.hpp:51
@ DUPLICATE_NONCE_IN_OTHER
in-record of other face
Definition: algorithm.hpp:49
int findDuplicateNonce(const pit::Entry &pitEntry, Interest::Nonce nonce, const Face &face)
Determine whether pitEntry has duplicate Nonce nonce.
Definition: algorithm.cpp:55
bool hasPendingOutRecords(const pit::Entry &pitEntry)
Determine whether pitEntry has any pending out-records.
Definition: algorithm.cpp:85
time::steady_clock::time_point getLastOutgoing(const pit::Entry &pitEntry)
Definition: algorithm.cpp:96
bool wouldViolateScope(const Face &inFace, const Interest &interest, const Face &outFace)
Determine whether forwarding the Interest in pitEntry to outFace would violate scope.
Definition: algorithm.cpp:33
const Name LOCALHOST
The localhost scope ndn:/localhost.
const Name LOCALHOP
The localhop scope ndn:/localhop.