fib.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2014-2023, The University of Memphis,
4  * Regents of the University of California
5  *
6  * This file is part of NLSR (Named-data Link State Routing).
7  * See AUTHORS.md for complete list of NLSR authors and contributors.
8  *
9  * NLSR is free software: you can redistribute it and/or modify it under the terms
10  * of the GNU General Public License as published by the Free Software Foundation,
11  * either version 3 of the License, or (at your option) any later version.
12  *
13  * NLSR is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
14  * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
15  * PURPOSE. See the GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License along with
18  * NLSR, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
19  */
20 
21 #include "fib.hpp"
22 #include "adjacency-list.hpp"
23 #include "conf-parameter.hpp"
24 #include "logger.hpp"
25 #include "nexthop-list.hpp"
26 
27 #include <algorithm>
28 #include <cmath>
29 #include <map>
30 
31 namespace nlsr {
32 
33 INIT_LOGGER(route.Fib);
34 
35 Fib::Fib(ndn::Face& face, ndn::Scheduler& scheduler, AdjacencyList& adjacencyList,
36  ConfParameter& conf, ndn::security::KeyChain& keyChain)
37  : m_scheduler(scheduler)
38  , m_refreshTime(2 * conf.getLsaRefreshTime())
39  , m_controller(face, keyChain)
40  , m_adjacencyList(adjacencyList)
41  , m_confParameter(conf)
42 {
43 }
44 
45 void
46 Fib::remove(const ndn::Name& name)
47 {
48  NLSR_LOG_DEBUG("Fib::remove called");
49  auto it = m_table.find(name);
50 
51  // Only unregister the prefix if it ISN'T a neighbor.
52  if (it != m_table.end() && isNotNeighbor((it->second).name)) {
53  for (const auto& nexthop : (it->second).nexthopSet) {
54  unregisterPrefix((it->second).name, nexthop.getConnectingFaceUri());
55  }
56  m_table.erase(it);
57  }
58 }
59 
60 void
61 Fib::addNextHopsToFibEntryAndNfd(FibEntry& entry, const NextHopsUriSortedSet& hopsToAdd)
62 {
63  const ndn::Name& name = entry.name;
64 
65  bool shouldRegister = isNotNeighbor(name);
66 
67  for (const auto& hop : hopsToAdd)
68  {
69  // Add nexthop to FIB entry
70  NLSR_LOG_DEBUG("Adding " << hop.getConnectingFaceUri() << " to " << entry.name);
71  entry.nexthopSet.addNextHop(hop);
72 
73  if (shouldRegister) {
74  // Add nexthop to NDN-FIB
75  registerPrefix(name, ndn::FaceUri(hop.getConnectingFaceUri()),
76  hop.getRouteCostAsAdjustedInteger(),
77  ndn::time::seconds(m_refreshTime + GRACE_PERIOD),
78  ndn::nfd::ROUTE_FLAG_CAPTURE, 0);
79  }
80  }
81 }
82 
83 void
84 Fib::update(const ndn::Name& name, const NexthopList& allHops)
85 {
86  NLSR_LOG_DEBUG("Fib::update called");
87 
88  // Get the max possible faces which is the minimum of the configuration setting and
89  // the length of the list of all next hops.
90  unsigned int maxFaces = getNumberOfFacesForName(allHops);
91 
92  NextHopsUriSortedSet hopsToAdd;
93  unsigned int nFaces = 0;
94 
95  // Create a list of next hops to be installed with length == maxFaces
96  for (auto it = allHops.cbegin(); it != allHops.cend() && nFaces < maxFaces; ++it, ++nFaces) {
97  hopsToAdd.addNextHop(*it);
98  }
99 
100  auto entryIt = m_table.find(name);
101 
102  // New FIB entry that has nextHops
103  if (entryIt == m_table.end() && hopsToAdd.size() != 0) {
104  NLSR_LOG_DEBUG("New FIB Entry");
105 
106  FibEntry entry;
107  entry.name = name;
108  addNextHopsToFibEntryAndNfd(entry, hopsToAdd);
109 
110  entryIt = m_table.try_emplace(name, std::move(entry)).first;
111  }
112  // Existing FIB entry that may or may not have nextHops
113  else {
114  // Existing FIB entry
115  NLSR_LOG_DEBUG("Existing FIB Entry");
116 
117  // Remove empty FIB entry
118  if (hopsToAdd.size() == 0) {
119  remove(name);
120  return;
121  }
122 
123  FibEntry& entry = entryIt->second;
124  addNextHopsToFibEntryAndNfd(entry, hopsToAdd);
125 
126  std::set<NextHop, NextHopUriSortedComparator> hopsToRemove;
127  std::set_difference(entry.nexthopSet.begin(), entry.nexthopSet.end(),
128  hopsToAdd.begin(), hopsToAdd.end(),
129  std::inserter(hopsToRemove, hopsToRemove.begin()),
131 
132  bool isUpdatable = isNotNeighbor(entry.name);
133  // Remove the uninstalled next hops from NFD and FIB entry
134  for (const auto& hop : hopsToRemove){
135  if (isUpdatable) {
136  unregisterPrefix(entry.name, hop.getConnectingFaceUri());
137  }
138  NLSR_LOG_DEBUG("Removing " << hop.getConnectingFaceUri() << " from " << entry.name);
139  entry.nexthopSet.removeNextHop(hop);
140  }
141 
142  // Increment sequence number
143  entry.seqNo += 1;
144  entryIt = m_table.find(name);
145  }
146 
147  if (entryIt != m_table.end() &&
148  !entryIt->second.refreshEventId &&
149  isNotNeighbor(entryIt->second.name)) {
150  scheduleEntryRefresh(entryIt->second, [this] (FibEntry& entry) { scheduleLoop(entry); });
151  }
152 }
153 
154 void
156 {
157  NLSR_LOG_DEBUG("Clean called");
158  for (const auto& it : m_table) {
159  for (const auto& hop : it.second.nexthopSet) {
160  unregisterPrefix(it.second.name, hop.getConnectingFaceUri());
161  }
162  }
163 }
164 
165 unsigned int
166 Fib::getNumberOfFacesForName(const NexthopList& nextHopList)
167 {
168  uint32_t nNextHops = static_cast<uint32_t>(nextHopList.getNextHops().size());
169  uint32_t nMaxFaces = m_confParameter.getMaxFacesPerPrefix();
170 
171  // 0 == all faces
172  return nMaxFaces == 0 ? nNextHops : std::min(nNextHops, nMaxFaces);
173 }
174 
175 bool
176 Fib::isNotNeighbor(const ndn::Name& name)
177 {
178  return !m_adjacencyList.isNeighbor(name);
179 }
180 
181 void
182 Fib::registerPrefix(const ndn::Name& namePrefix, const ndn::FaceUri& faceUri,
183  uint64_t faceCost, const ndn::time::milliseconds& timeout,
184  uint64_t flags, uint8_t times)
185 {
186  uint64_t faceId = m_adjacencyList.getFaceId(faceUri);
187 
188  if (faceId > 0) {
189  ndn::nfd::ControlParameters faceParameters;
190  faceParameters
191  .setName(namePrefix)
192  .setFaceId(faceId)
193  .setFlags(flags)
194  .setCost(faceCost)
195  .setExpirationPeriod(timeout)
196  .setOrigin(ndn::nfd::ROUTE_ORIGIN_NLSR);
197 
198  NLSR_LOG_DEBUG("Registering prefix: " << faceParameters.getName() << " faceUri: " << faceUri);
199  m_controller.start<ndn::nfd::RibRegisterCommand>(faceParameters,
200  std::bind(&Fib::onRegistrationSuccess, this, _1, faceUri),
201  std::bind(&Fib::onRegistrationFailure, this, _1,
202  faceParameters, faceUri, times));
203  }
204  else {
205  NLSR_LOG_WARN("Error: No Face Id for face uri: " << faceUri);
206  }
207 }
208 
209 void
210 Fib::onRegistrationSuccess(const ndn::nfd::ControlParameters& param,
211  const ndn::FaceUri& faceUri)
212 {
213  NLSR_LOG_DEBUG("Successful in name registration: " << param.getName() <<
214  " Face Uri: " << faceUri << " faceId: " << param.getFaceId());
215 
216  auto adjacent = m_adjacencyList.findAdjacent(faceUri);
217  if (adjacent != m_adjacencyList.end()) {
218  adjacent->setFaceId(param.getFaceId());
219  }
220  onPrefixRegistrationSuccess(param.getName());
221 }
222 
223 void
224 Fib::onRegistrationFailure(const ndn::nfd::ControlResponse& response,
225  const ndn::nfd::ControlParameters& parameters,
226  const ndn::FaceUri& faceUri,
227  uint8_t times)
228 {
229  NLSR_LOG_DEBUG("Failed in name registration: " << response.getText() <<
230  " (code: " << response.getCode() << ")");
231  NLSR_LOG_DEBUG("Prefix: " << parameters.getName() << " failed for: " << +times);
232  if (times < 3) {
233  NLSR_LOG_DEBUG("Trying to register again...");
234  registerPrefix(parameters.getName(), faceUri,
235  parameters.getCost(),
236  parameters.getExpirationPeriod(),
237  parameters.getFlags(), times+1);
238  }
239  else {
240  NLSR_LOG_DEBUG("Registration trial given up");
241  }
242 }
243 
244 void
245 Fib::unregisterPrefix(const ndn::Name& namePrefix, const ndn::FaceUri& faceUri)
246 {
247  uint64_t faceId = 0;
248  auto adjacent = m_adjacencyList.findAdjacent(faceUri);
249  if (adjacent != m_adjacencyList.end()) {
250  faceId = adjacent->getFaceId();
251  }
252 
253  NLSR_LOG_DEBUG("Unregister prefix: " << namePrefix << " Face Uri: " << faceUri);
254  if (faceId > 0) {
255  ndn::nfd::ControlParameters controlParameters;
256  controlParameters
257  .setName(namePrefix)
258  .setFaceId(faceId)
259  .setOrigin(ndn::nfd::ROUTE_ORIGIN_NLSR);
260 
261  m_controller.start<ndn::nfd::RibUnregisterCommand>(controlParameters,
262  [] (const ndn::nfd::ControlParameters& commandSuccessResult) {
263  NLSR_LOG_DEBUG("Unregister successful Prefix: " << commandSuccessResult.getName() <<
264  " Face Id: " << commandSuccessResult.getFaceId());
265  },
266  [] (const ndn::nfd::ControlResponse& response) {
267  NLSR_LOG_DEBUG("Failed in unregistering name" << ": " << response.getText() <<
268  " (code: " << response.getCode() << ")");
269  });
270  }
271 }
272 
273 void
274 Fib::setStrategy(const ndn::Name& name, const ndn::Name& strategy, uint32_t count)
275 {
276  ndn::nfd::ControlParameters parameters;
277  parameters
278  .setName(name)
279  .setStrategy(strategy);
280 
281  m_controller.start<ndn::nfd::StrategyChoiceSetCommand>(parameters,
282  std::bind(&Fib::onSetStrategySuccess, this, _1),
283  std::bind(&Fib::onSetStrategyFailure, this, _1,
284  parameters, count));
285 }
286 
287 void
288 Fib::onSetStrategySuccess(const ndn::nfd::ControlParameters& commandSuccessResult)
289 {
290  NLSR_LOG_DEBUG("Successfully set strategy choice: " << commandSuccessResult.getStrategy() <<
291  " for name: " << commandSuccessResult.getName());
292 }
293 
294 void
295 Fib::onSetStrategyFailure(const ndn::nfd::ControlResponse& response,
296  const ndn::nfd::ControlParameters& parameters,
297  uint32_t count)
298 {
299  NLSR_LOG_DEBUG("Failed to set strategy choice: " << parameters.getStrategy() <<
300  " for name: " << parameters.getName());
301  if (count < 3) {
302  setStrategy(parameters.getName(), parameters.getStrategy().toUri(), count + 1);
303  }
304 }
305 
306 void
307 Fib::scheduleEntryRefresh(FibEntry& entry, const AfterRefreshCallback& refreshCallback)
308 {
309  NLSR_LOG_DEBUG("Scheduling refresh for " << entry.name <<
310  " Seq Num: " << entry.seqNo <<
311  " in " << m_refreshTime << " seconds");
312 
313  entry.refreshEventId = m_scheduler.schedule(ndn::time::seconds(m_refreshTime),
314  std::bind(&Fib::refreshEntry, this,
315  entry.name, refreshCallback));
316 }
317 
318 void
319 Fib::scheduleLoop(FibEntry& entry)
320 {
321  scheduleEntryRefresh(entry, std::bind(&Fib::scheduleLoop, this, _1));
322 }
323 
324 void
325 Fib::refreshEntry(const ndn::Name& name, AfterRefreshCallback refreshCb)
326 {
327  auto it = m_table.find(name);
328  if (it == m_table.end()) {
329  return;
330  }
331 
332  FibEntry& entry = it->second;
333  NLSR_LOG_DEBUG("Refreshing " << entry.name << " Seq Num: " << entry.seqNo);
334 
335  entry.seqNo += 1;
336 
337  for (const NextHop& hop : entry.nexthopSet) {
338  registerPrefix(entry.name,
339  ndn::FaceUri(hop.getConnectingFaceUri()),
340  hop.getRouteCostAsAdjustedInteger(),
341  ndn::time::seconds(m_refreshTime + GRACE_PERIOD),
342  ndn::nfd::ROUTE_FLAG_CAPTURE, 0);
343  }
344 
345  refreshCb(entry);
346 }
347 
348 void
350 {
351  NLSR_LOG_DEBUG("-------------------FIB-----------------------------");
352  for (const auto& entry : m_table) {
353  NLSR_LOG_DEBUG("Name prefix: " << entry.first);
354  NLSR_LOG_DEBUG("Seq No: " << entry.second.seqNo);
355  NLSR_LOG_DEBUG("Nexthop List: \n" << entry.second.nexthopSet);
356  }
357 }
358 
359 } // namespace nlsr
uint64_t getFaceId(const ndn::FaceUri &faceUri)
const_iterator end() const
bool isNeighbor(const ndn::Name &adjName) const
AdjacencyList::iterator findAdjacent(const ndn::Name &adjName)
A class to house all the configuration parameters for NLSR.
uint32_t getMaxFacesPerPrefix() const
void setStrategy(const ndn::Name &name, const ndn::Name &strategy, uint32_t count)
Definition: fib.cpp:274
void writeLog()
Definition: fib.cpp:349
void clean()
Remove all entries from the FIB.
Definition: fib.cpp:155
void remove(const ndn::Name &name)
Completely remove a name prefix from the FIB.
Definition: fib.cpp:46
void update(const ndn::Name &name, const NexthopList &allHops)
Set the nexthop list of a name.
Definition: fib.cpp:84
Fib(ndn::Face &face, ndn::Scheduler &scheduler, AdjacencyList &adjacencyList, ConfParameter &conf, ndn::security::KeyChain &keyChain)
Definition: fib.cpp:35
void registerPrefix(const ndn::Name &namePrefix, const ndn::FaceUri &faceUri, uint64_t faceCost, const ndn::time::milliseconds &timeout, uint64_t flags, uint8_t times)
Inform NFD of a next-hop.
Definition: fib.cpp:182
ndn::signal::Signal< Fib, ndn::Name > onPrefixRegistrationSuccess
Definition: fib.hpp:225
void removeNextHop(const NextHop &nh)
Remove a next hop from the Next Hop list.
iterator end() const
const_iterator cend() const
const_iterator cbegin() const
void addNextHop(const NextHop &nh)
Adds a next hop to the list.
iterator begin() const
const std::set< NextHop, T > & getNextHops() const
size_t size() const
Copyright (c) 2014-2018, The University of Memphis, Regents of the University of California.
#define NLSR_LOG_DEBUG(x)
Definition: logger.hpp:38
#define INIT_LOGGER(name)
Definition: logger.hpp:35
#define NLSR_LOG_WARN(x)
Definition: logger.hpp:40
Copyright (c) 2014-2020, The University of Memphis, Regents of the University of California.
std::function< void(FibEntry &)> AfterRefreshCallback
Definition: fib.hpp:44
Definition: fib.hpp:37
ndn::Name name
Definition: fib.hpp:38
NextHopsUriSortedSet nexthopSet
Definition: fib.hpp:41
int32_t seqNo
Definition: fib.hpp:40