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-2019, 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 <map>
28 #include <cmath>
29 #include <algorithm>
30 #include <iterator>
31 
32 namespace nlsr {
33 
34 INIT_LOGGER(route.Fib);
35 
36 const uint64_t Fib::GRACE_PERIOD = 10;
37 const std::string Fib::MULTICAST_STRATEGY("ndn:/localhost/nfd/strategy/multicast");
38 const std::string Fib::BEST_ROUTE_V2_STRATEGY("ndn:/localhost/nfd/strategy/best-route");
39 
40 Fib::Fib(ndn::Face& face, ndn::Scheduler& scheduler, AdjacencyList& adjacencyList,
41  ConfParameter& conf, ndn::security::v2::KeyChain& keyChain)
42  : m_scheduler(scheduler)
43  , m_refreshTime(2 * conf.getLsaRefreshTime())
44  , m_controller(face, keyChain)
45  , m_adjacencyList(adjacencyList)
46  , m_confParameter(conf)
47 {
48 }
49 
50 void
51 Fib::remove(const ndn::Name& name)
52 {
53  NLSR_LOG_DEBUG("Fib::remove called");
54  auto it = m_table.find(name);
55 
56  // Only unregister the prefix if it ISN'T a neighbor.
57  if (it != m_table.end() && isNotNeighbor((it->second).getName())) {
58  for (const auto& nexthop : (it->second).getNexthopList().getNextHops()) {
59  unregisterPrefix((it->second).getName(), nexthop.getConnectingFaceUri());
60  }
61  cancelEntryRefresh(it->second);
62  m_table.erase(it);
63  }
64 }
65 
66 void
67 Fib::addNextHopsToFibEntryAndNfd(FibEntry& entry, const NexthopList& hopsToAdd)
68 {
69  const ndn::Name& name = entry.getName();
70 
71  bool shouldRegister = isNotNeighbor(name);
72 
73  for (const auto& hop : hopsToAdd.getNextHops())
74  {
75  // Add nexthop to FIB entry
76  entry.getNexthopList().addNextHop(hop);
77 
78  if (shouldRegister) {
79  // Add nexthop to NDN-FIB
80  registerPrefix(name, ndn::FaceUri(hop.getConnectingFaceUri()),
81  hop.getRouteCostAsAdjustedInteger(),
82  ndn::time::seconds(m_refreshTime + GRACE_PERIOD),
83  ndn::nfd::ROUTE_FLAG_CAPTURE, 0);
84  }
85  }
86 }
87 
88 void
89 Fib::update(const ndn::Name& name, const NexthopList& allHops)
90 {
91  NLSR_LOG_DEBUG("Fib::update called");
92 
93  // Get the max possible faces which is the minimum of the configuration setting and
94  // the length of the list of all next hops.
95  unsigned int maxFaces = getNumberOfFacesForName(allHops);
96 
97  NexthopList hopsToAdd;
98  unsigned int nFaces = 0;
99 
100  // Create a list of next hops to be installed with length == maxFaces
101  for (auto it = allHops.cbegin(); it != allHops.cend() && nFaces < maxFaces; ++it, ++nFaces) {
102  hopsToAdd.addNextHop(*it);
103  }
104 
105  auto entryIt = m_table.find(name);
106 
107  // New FIB entry that has nextHops
108  if (entryIt == m_table.end() && hopsToAdd.size() != 0) {
109  NLSR_LOG_DEBUG("New FIB Entry");
110 
111  FibEntry entry(name);
112 
113  addNextHopsToFibEntryAndNfd(entry, hopsToAdd);
114 
115  m_table.emplace(name, entry);
116 
117  entryIt = m_table.find(name);
118  }
119  // Existing FIB entry that may or may not have nextHops
120  else {
121  // Existing FIB entry
122  NLSR_LOG_DEBUG("Existing FIB Entry");
123 
124  // Remove empty FIB entry
125  if (hopsToAdd.size() == 0) {
126  remove(name);
127  return;
128  }
129 
130  FibEntry& entry = (entryIt->second);
131  addNextHopsToFibEntryAndNfd(entry, hopsToAdd);
132 
133  std::set<NextHop, NextHopComparator> hopsToRemove;
134  std::set_difference(entry.getNexthopList().begin(), entry.getNexthopList().end(),
135  hopsToAdd.begin(), hopsToAdd.end(),
136  std::inserter(hopsToRemove, hopsToRemove.end()), NextHopComparator());
137 
138  bool isUpdatable = isNotNeighbor(entry.getName());
139  // Remove the uninstalled next hops from NFD and FIB entry
140  for (const auto& hop : hopsToRemove){
141  if (isUpdatable) {
142  unregisterPrefix(entry.getName(), hop.getConnectingFaceUri());
143  }
144  NLSR_LOG_DEBUG("Removing " << hop.getConnectingFaceUri() << " from " << entry.getName());
145  entry.getNexthopList().removeNextHop(hop);
146  }
147 
148  // Increment sequence number
149  entry.setSeqNo(entry.getSeqNo() + 1);
150 
151  entryIt = m_table.find(name);
152 
153  }
154  if (entryIt != m_table.end() &&
155  !entryIt->second.getRefreshEventId() &&
156  isNotNeighbor(entryIt->second.getName())) {
157  scheduleEntryRefresh(entryIt->second,
158  [this] (FibEntry& entry) {
159  scheduleLoop(entry);
160  });
161  }
162 }
163 
164 void
166 {
167  NLSR_LOG_DEBUG("Fib::clean called");
168  // can't use const ref here as getNexthopList can't be marked const
169  for (auto&& it : m_table) {
170  NLSR_LOG_DEBUG("Canceling Scheduled event. Name: " << it.second.getName());
171  cancelEntryRefresh(it.second);
172 
173  for (const auto& hop : it.second.getNexthopList().getNextHops()) {
174  unregisterPrefix(it.second.getName(), hop.getConnectingFaceUri());
175  }
176  }
177 }
178 
179 unsigned int
180 Fib::getNumberOfFacesForName(const NexthopList& nextHopList)
181 {
182  uint32_t nNextHops = static_cast<uint32_t>(nextHopList.getNextHops().size());
183  uint32_t nMaxFaces = m_confParameter.getMaxFacesPerPrefix();
184 
185  // Allow all faces
186  if (nMaxFaces == 0) {
187  return nNextHops;
188  }
189  else {
190  return std::min(nNextHops, nMaxFaces);
191  }
192 }
193 
194 bool
195 Fib::isNotNeighbor(const ndn::Name& name)
196 {
197  return !m_adjacencyList.isNeighbor(name);
198 }
199 
200 void
201 Fib::registerPrefix(const ndn::Name& namePrefix, const ndn::FaceUri& faceUri,
202  uint64_t faceCost, const ndn::time::milliseconds& timeout,
203  uint64_t flags, uint8_t times)
204 {
205  uint64_t faceId = m_adjacencyList.getFaceId(faceUri);
206 
207  if (faceId > 0) {
208  ndn::nfd::ControlParameters faceParameters;
209  faceParameters
210  .setName(namePrefix)
211  .setFaceId(faceId)
212  .setFlags(flags)
213  .setCost(faceCost)
214  .setExpirationPeriod(timeout)
215  .setOrigin(ndn::nfd::ROUTE_ORIGIN_NLSR);
216 
217  NLSR_LOG_DEBUG("Registering prefix: " << faceParameters.getName() << " faceUri: " << faceUri);
218  m_controller.start<ndn::nfd::RibRegisterCommand>(faceParameters,
219  std::bind(&Fib::onRegistrationSuccess, this, _1, faceUri),
220  std::bind(&Fib::onRegistrationFailure, this, _1,
221  faceParameters, faceUri, times));
222  }
223  else {
224  NLSR_LOG_WARN("Error: No Face Id for face uri: " << faceUri);
225  }
226 }
227 
228 void
229 Fib::onRegistrationSuccess(const ndn::nfd::ControlParameters& param,
230  const ndn::FaceUri& faceUri)
231 {
232  NLSR_LOG_DEBUG("Successful in name registration: " << param.getName() <<
233  " Face Uri: " << faceUri << " faceId: " << param.getFaceId());
234 
235  auto adjacent = m_adjacencyList.findAdjacent(faceUri);
236  if (adjacent != m_adjacencyList.end()) {
237  adjacent->setFaceId(param.getFaceId());
238  }
239  onPrefixRegistrationSuccess(param.getName());
240 }
241 
242 void
243 Fib::onRegistrationFailure(const ndn::nfd::ControlResponse& response,
244  const ndn::nfd::ControlParameters& parameters,
245  const ndn::FaceUri& faceUri,
246  uint8_t times)
247 {
248  NLSR_LOG_DEBUG("Failed in name registration: " << response.getText() <<
249  " (code: " << response.getCode() << ")");
250  NLSR_LOG_DEBUG("Prefix: " << parameters.getName() << " failed for: " << +times);
251  if (times < 3) {
252  NLSR_LOG_DEBUG("Trying to register again...");
253  registerPrefix(parameters.getName(), faceUri,
254  parameters.getCost(),
255  parameters.getExpirationPeriod(),
256  parameters.getFlags(), times+1);
257  }
258  else {
259  NLSR_LOG_DEBUG("Registration trial given up");
260  }
261 }
262 
263 void
264 Fib::unregisterPrefix(const ndn::Name& namePrefix, const std::string& faceUri)
265 {
266  uint64_t faceId = 0;
267  auto adjacent = m_adjacencyList.findAdjacent(ndn::FaceUri(faceUri));
268  if (adjacent != m_adjacencyList.end()) {
269  faceId = adjacent->getFaceId();
270  }
271 
272  NLSR_LOG_DEBUG("Unregister prefix: " << namePrefix << " Face Uri: " << faceUri);
273  if (faceId > 0) {
274  ndn::nfd::ControlParameters controlParameters;
275  controlParameters
276  .setName(namePrefix)
277  .setFaceId(faceId)
278  .setOrigin(ndn::nfd::ROUTE_ORIGIN_NLSR);
279 
280  m_controller.start<ndn::nfd::RibUnregisterCommand>(controlParameters,
281  [] (const ndn::nfd::ControlParameters& commandSuccessResult) {
282  NLSR_LOG_DEBUG("Unregister successful Prefix: " << commandSuccessResult.getName() <<
283  " Face Id: " << commandSuccessResult.getFaceId());
284  },
285  [] (const ndn::nfd::ControlResponse& response) {
286  NLSR_LOG_DEBUG("Failed in unregistering name" << ": " << response.getText() <<
287  " (code: " << response.getCode() << ")");
288  });
289  }
290 }
291 
292 void
293 Fib::setStrategy(const ndn::Name& name, const std::string& strategy, uint32_t count)
294 {
295  ndn::nfd::ControlParameters parameters;
296  parameters
297  .setName(name)
298  .setStrategy(strategy);
299 
300  m_controller.start<ndn::nfd::StrategyChoiceSetCommand>(parameters,
301  std::bind(&Fib::onSetStrategySuccess, this, _1),
302  std::bind(&Fib::onSetStrategyFailure, this, _1,
303  parameters, count));
304 }
305 
306 void
307 Fib::onSetStrategySuccess(const ndn::nfd::ControlParameters& commandSuccessResult)
308 {
309  NLSR_LOG_DEBUG("Successfully set strategy choice: " << commandSuccessResult.getStrategy() <<
310  " for name: " << commandSuccessResult.getName());
311 }
312 
313 void
314 Fib::onSetStrategyFailure(const ndn::nfd::ControlResponse& response,
315  const ndn::nfd::ControlParameters& parameters,
316  uint32_t count)
317 {
318  NLSR_LOG_DEBUG("Failed to set strategy choice: " << parameters.getStrategy() <<
319  " for name: " << parameters.getName());
320  if (count < 3) {
321  setStrategy(parameters.getName(), parameters.getStrategy().toUri(), count + 1);
322  }
323 }
324 
325 void
326 Fib::scheduleEntryRefresh(FibEntry& entry, const afterRefreshCallback& refreshCallback)
327 {
328  NLSR_LOG_DEBUG("Scheduling refresh for " << entry.getName() <<
329  " Seq Num: " << entry.getSeqNo() <<
330  " in " << m_refreshTime << " seconds");
331 
332  entry.setRefreshEventId(m_scheduler.schedule(ndn::time::seconds(m_refreshTime),
333  std::bind(&Fib::refreshEntry, this,
334  entry.getName(), refreshCallback)));
335 }
336 
337 void
338 Fib::scheduleLoop(FibEntry& entry)
339 {
340  scheduleEntryRefresh(entry, std::bind(&Fib::scheduleLoop, this, _1));
341 }
342 
343 void
344 Fib::cancelEntryRefresh(const FibEntry& entry)
345 {
346  NLSR_LOG_DEBUG("Canceling refresh for " << entry.getName() << " Seq Num: " << entry.getSeqNo());
347  entry.getRefreshEventId().cancel();
348 }
349 
350 void
351 Fib::refreshEntry(const ndn::Name& name, afterRefreshCallback refreshCb)
352 {
353  auto it = m_table.find(name);
354  if (it == m_table.end()) {
355  return;
356  }
357 
358  FibEntry& entry = it->second;
359  NLSR_LOG_DEBUG("Refreshing " << entry.getName() << " Seq Num: " << entry.getSeqNo());
360 
361  // Increment sequence number
362  entry.setSeqNo(entry.getSeqNo() + 1);
363 
364  for (const NextHop& hop : entry) {
365  registerPrefix(entry.getName(),
366  ndn::FaceUri(hop.getConnectingFaceUri()),
367  hop.getRouteCostAsAdjustedInteger(),
368  ndn::time::seconds(m_refreshTime + GRACE_PERIOD),
369  ndn::nfd::ROUTE_FLAG_CAPTURE, 0);
370  }
371 
372  refreshCb(entry);
373 }
374 
375 void
377 {
378  NLSR_LOG_DEBUG("-------------------FIB-----------------------------");
379  for (const auto& entry : m_table) {
380  entry.second.writeLog();
381  }
382 }
383 
384 } // namespace nlsr
void writeLog()
Definition: fib.cpp:376
void setRefreshEventId(ndn::scheduler::EventId id)
Definition: fib-entry.hpp:53
#define NLSR_LOG_WARN(x)
Definition: logger.hpp:40
A class to house all the configuration parameters for NLSR.
const std::set< NextHop, NextHopComparator > & getNextHops() const
void update(const ndn::Name &name, const NexthopList &allHops)
Set the nexthop list of a name.
Definition: fib.cpp:89
static const std::string MULTICAST_STRATEGY
Definition: fib.hpp:227
size_t size() const
const_iterator cend() const
bool isNeighbor(const ndn::Name &adjName) const
#define NLSR_LOG_DEBUG(x)
Definition: logger.hpp:38
void setStrategy(const ndn::Name &name, const std::string &strategy, uint32_t count)
Definition: fib.cpp:293
static const std::string BEST_ROUTE_V2_STRATEGY
Definition: fib.hpp:228
const_iterator cbegin() const
Copyright (c) 2014-2018, The University of Memphis, Regents of the University of California.
#define INIT_LOGGER(name)
Definition: logger.hpp:35
uint32_t getMaxFacesPerPrefix() const
NexthopList & getNexthopList()
Definition: fib-entry.hpp:47
void setSeqNo(int32_t fsn)
Definition: fib-entry.hpp:65
ndn::scheduler::EventId getRefreshEventId() const
Definition: fib-entry.hpp:59
void clean()
Remove all entries from the FIB.
Definition: fib.cpp:165
int32_t getSeqNo() const
Definition: fib-entry.hpp:71
Fib(ndn::Face &face, ndn::Scheduler &scheduler, AdjacencyList &adjacencyList, ConfParameter &conf, ndn::security::v2::KeyChain &keyChain)
Definition: fib.cpp:40
void writeLog() const
Definition: fib-entry.cpp:29
Copyright (c) 2014-2019, The University of Memphis, Regents of the University of California, Arizona Board of Regents.
const ndn::Name & getName() const
Definition: fib-entry.hpp:41
AdjacencyList::iterator findAdjacent(const ndn::Name &adjName)
void addNextHop(const NextHop &nh)
Adds a next hop to the list.
void remove(const ndn::Name &name)
Completely remove a name prefix from the FIB.
Definition: fib.cpp:51
ndn::util::Signal< Fib, const ndn::Name & > onPrefixRegistrationSuccess
Definition: fib.hpp:229
uint64_t getFaceId(const ndn::FaceUri &faceUri)
void removeNextHop(const NextHop &nh)
Remove a next hop from the Next Hop list.
std::function< void(FibEntry &)> afterRefreshCallback
Definition: fib.hpp:33
const_iterator end() const
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:201