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-2019, 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 
28 namespace nfd {
29 namespace fw {
30 
31 bool
32 wouldViolateScope(const Face& inFace, const Interest& interest, const Face& outFace)
33 {
34  if (outFace.getScope() == ndn::nfd::FACE_SCOPE_LOCAL) {
35  // forwarding to a local face is always allowed
36  return false;
37  }
38 
39  if (scope_prefix::LOCALHOST.isPrefixOf(interest.getName())) {
40  // localhost Interests cannot be forwarded to a non-local face
41  return true;
42  }
43 
44  if (scope_prefix::LOCALHOP.isPrefixOf(interest.getName())) {
45  // localhop Interests can be forwarded to a non-local face only if it comes from a local face
46  return inFace.getScope() != ndn::nfd::FACE_SCOPE_LOCAL;
47  }
48 
49  // Interest name is not subject to scope control
50  return false;
51 }
52 
53 bool
54 canForwardToLegacy(const pit::Entry& pitEntry, const Face& face)
55 {
56  time::steady_clock::TimePoint now = time::steady_clock::now();
57 
58  bool hasUnexpiredOutRecord = std::any_of(pitEntry.out_begin(), pitEntry.out_end(),
59  [&face, &now] (const pit::OutRecord& outRecord) {
60  return &outRecord.getFace() == &face && outRecord.getExpiry() >= now;
61  });
62  if (hasUnexpiredOutRecord) {
63  return false;
64  }
65 
66  bool hasUnexpiredOtherInRecord = std::any_of(pitEntry.in_begin(), pitEntry.in_end(),
67  [&face, &now] (const pit::InRecord& inRecord) {
68  return &inRecord.getFace() != &face && inRecord.getExpiry() >= now;
69  });
70  if (!hasUnexpiredOtherInRecord) {
71  return false;
72  }
73 
74  return true;
75 }
76 
77 int
78 findDuplicateNonce(const pit::Entry& pitEntry, uint32_t nonce, const Face& face)
79 {
80  int dnw = DUPLICATE_NONCE_NONE;
81 
82  for (const pit::InRecord& inRecord : pitEntry.getInRecords()) {
83  if (inRecord.getLastNonce() == nonce) {
84  if (&inRecord.getFace() == &face) {
86  }
87  else {
89  }
90  }
91  }
92 
93  for (const pit::OutRecord& outRecord : pitEntry.getOutRecords()) {
94  if (outRecord.getLastNonce() == nonce) {
95  if (&outRecord.getFace() == &face) {
97  }
98  else {
100  }
101  }
102  }
103 
104  return dnw;
105 }
106 
107 bool
109 {
110  time::steady_clock::TimePoint now = time::steady_clock::now();
111  return std::any_of(pitEntry.out_begin(), pitEntry.out_end(),
112  [&now] (const pit::OutRecord& outRecord) {
113  return outRecord.getExpiry() >= now &&
114  outRecord.getIncomingNack() == nullptr;
115  });
116 }
117 
118 time::steady_clock::TimePoint
119 getLastOutgoing(const pit::Entry& pitEntry)
120 {
121  pit::OutRecordCollection::const_iterator lastOutgoing = std::max_element(
122  pitEntry.out_begin(), pitEntry.out_end(),
123  [] (const pit::OutRecord& a, const pit::OutRecord& b) {
124  return a.getLastRenewed() < b.getLastRenewed();
125  });
126  BOOST_ASSERT(lastOutgoing != pitEntry.out_end());
127 
128  return lastOutgoing->getLastRenewed();
129 }
130 
131 fib::NextHopList::const_iterator
132 findEligibleNextHopWithEarliestOutRecord(const Face& inFace, const Interest& interest,
133  const fib::NextHopList& nexthops,
134  const shared_ptr<pit::Entry>& pitEntry)
135 {
136  auto found = nexthops.end();
137  auto earliestRenewed = time::steady_clock::TimePoint::max();
138 
139  for (auto it = nexthops.begin(); it != nexthops.end(); ++it) {
140  if (!isNextHopEligible(inFace, interest, *it, pitEntry))
141  continue;
142 
143  auto outRecord = pitEntry->getOutRecord(it->getFace());
144  BOOST_ASSERT(outRecord != pitEntry->out_end());
145  if (outRecord->getLastRenewed() < earliestRenewed) {
146  found = it;
147  earliestRenewed = outRecord->getLastRenewed();
148  }
149  }
150  return found;
151 }
152 
153 bool
154 isNextHopEligible(const Face& inFace, const Interest& interest,
155  const fib::NextHop& nexthop,
156  const shared_ptr<pit::Entry>& pitEntry,
157  bool wantUnused,
158  time::steady_clock::TimePoint now)
159 {
160  const Face& outFace = nexthop.getFace();
161 
162  // do not forward back to the same face, unless it is ad hoc
163  if ((outFace.getId() == inFace.getId() && outFace.getLinkType() != ndn::nfd::LINK_TYPE_AD_HOC) ||
164  (wouldViolateScope(inFace, interest, outFace)))
165  return false;
166 
167  if (wantUnused) {
168  // nexthop must not have unexpired out-record
169  auto outRecord = pitEntry->getOutRecord(outFace);
170  if (outRecord != pitEntry->out_end() && outRecord->getExpiry() > now) {
171  return false;
172  }
173  }
174  return true;
175 }
176 
177 } // namespace fw
178 } // namespace nfd
bool canForwardToLegacy(const pit::Entry &pitEntry, const Face &face)
decide whether Interest can be forwarded to face
Definition: algorithm.cpp:54
time::steady_clock::TimePoint getLastRenewed() const
const InRecordCollection & getInRecords() const
Definition: pit-entry.hpp:94
Contains information about an Interest toward an outgoing face.
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:132
in-record of same face
Definition: algorithm.hpp:63
An Interest table entry.
Definition: pit-entry.hpp:58
Copyright (c) 2014-2015, Regents of the University of California, Arizona Board of Regents...
Definition: algorithm.hpp:32
Contains information about an Interest from an incoming face.
Face & getFace() const
Definition: fib-nexthop.hpp:47
bool isNextHopEligible(const Face &inFace, const Interest &interest, const fib::NextHop &nexthop, const shared_ptr< pit::Entry > &pitEntry, bool wantUnused, time::steady_clock::TimePoint now)
determines whether a NextHop is eligible i.e.
Definition: algorithm.cpp:154
const Name LOCALHOP
ndn:/localhop
InRecordCollection::iterator in_end()
Definition: pit-entry.hpp:123
Represents a collection of nexthops.
Definition: fib-entry.hpp:39
bool hasPendingOutRecords(const pit::Entry &pitEntry)
determine whether pitEntry has any pending out-records
Definition: algorithm.cpp:108
const Name LOCALHOST
ndn:/localhost
no duplicate Nonce is found
Definition: algorithm.hpp:62
time::steady_clock::TimePoint getLastOutgoing(const pit::Entry &pitEntry)
Definition: algorithm.cpp:119
int findDuplicateNonce(const pit::Entry &pitEntry, uint32_t nonce, const Face &face)
determine whether pitEntry has duplicate Nonce nonce
Definition: algorithm.cpp:78
OutRecordCollection::iterator out_begin()
Definition: pit-entry.hpp:178
This file contains common algorithms used by forwarding strategies.
in-record of other face
Definition: algorithm.hpp:64
out-record of other face
Definition: algorithm.hpp:66
OutRecordCollection::iterator out_end()
Definition: pit-entry.hpp:190
const OutRecordCollection & getOutRecords() const
Definition: pit-entry.hpp:160
Represents a nexthop record in a FIB entry.
Definition: fib-nexthop.hpp:37
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:32
InRecordCollection::iterator in_begin()
Definition: pit-entry.hpp:111
out-record of same face
Definition: algorithm.hpp:65