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