name-prefix-table.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2014-2022, The University of Memphis,
4  * Regents of the University of California,
5  * Arizona Board of Regents.
6  *
7  * This file is part of NLSR (Named-data Link State Routing).
8  * See AUTHORS.md for complete list of NLSR authors and contributors.
9  *
10  * NLSR is free software: you can redistribute it and/or modify it under the terms
11  * of the GNU General Public License as published by the Free Software Foundation,
12  * either version 3 of the License, or (at your option) any later version.
13  *
14  * NLSR is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
15  * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
16  * PURPOSE. See the GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License along with
19  * NLSR, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
20  */
21 
22 #include "name-prefix-table.hpp"
23 
24 #include "logger.hpp"
25 #include "nlsr.hpp"
26 #include "routing-table.hpp"
27 
28 #include <algorithm>
29 #include <list>
30 #include <utility>
31 
32 namespace nlsr {
33 
34 INIT_LOGGER(route.NamePrefixTable);
35 
36 NamePrefixTable::NamePrefixTable(const ndn::Name& ownRouterName, Fib& fib,
37  RoutingTable& routingTable,
38  AfterRoutingChange& afterRoutingChangeSignal,
39  Lsdb::AfterLsdbModified& afterLsdbModifiedSignal)
40  : m_ownRouterName(ownRouterName)
41  , m_fib(fib)
42  , m_routingTable(routingTable)
43 {
44  m_afterRoutingChangeConnection = afterRoutingChangeSignal.connect(
45  [this] (const std::list<RoutingTableEntry>& entries) {
46  updateWithNewRoute(entries);
47  });
48 
49  m_afterLsdbModified = afterLsdbModifiedSignal.connect(
50  [this] (std::shared_ptr<Lsa> lsa, LsdbUpdate updateType,
51  const auto& namesToAdd, const auto& namesToRemove) {
52  updateFromLsdb(lsa, updateType, namesToAdd, namesToRemove);
53  }
54  );
55 }
56 
58 {
59  m_afterRoutingChangeConnection.disconnect();
60  m_afterLsdbModified.disconnect();
61 }
62 
63 void
64 NamePrefixTable::updateFromLsdb(std::shared_ptr<Lsa> lsa, LsdbUpdate updateType,
65  const std::list<ndn::Name>& namesToAdd,
66  const std::list<ndn::Name>& namesToRemove)
67 {
68  if (m_ownRouterName == lsa->getOriginRouter()) {
69  return;
70  }
71  NLSR_LOG_TRACE("Got update from Lsdb for router: " << lsa->getOriginRouter());
72 
73  if (updateType == LsdbUpdate::INSTALLED) {
74  addEntry(lsa->getOriginRouter(), lsa->getOriginRouter());
75 
76  if (lsa->getType() == Lsa::Type::NAME) {
77  auto nlsa = std::static_pointer_cast<NameLsa>(lsa);
78  for (const auto& name : nlsa->getNpl().getNames()) {
79  if (name != m_ownRouterName) {
80  addEntry(name, lsa->getOriginRouter());
81  }
82  }
83  }
84  }
85  else if (updateType == LsdbUpdate::UPDATED) {
86  if (lsa->getType() != Lsa::Type::NAME) {
87  return;
88  }
89 
90  for (const auto& name : namesToAdd) {
91  if (name != m_ownRouterName) {
92  addEntry(name, lsa->getOriginRouter());
93  }
94  }
95 
96  for (const auto& name : namesToRemove) {
97  if (name != m_ownRouterName) {
98  removeEntry(name, lsa->getOriginRouter());
99  }
100  }
101  }
102  else {
103  removeEntry(lsa->getOriginRouter(), lsa->getOriginRouter());
104  if (lsa->getType() == Lsa::Type::NAME) {
105  auto nlsa = std::static_pointer_cast<NameLsa>(lsa);
106  for (const auto& name : nlsa->getNpl().getNames()) {
107  if (name != m_ownRouterName) {
108  removeEntry(name, lsa->getOriginRouter());
109  }
110  }
111  }
112  }
113 }
114 
115 void
116 NamePrefixTable::addEntry(const ndn::Name& name, const ndn::Name& destRouter)
117 {
118  // Check if the advertised name prefix is in the table already.
119  auto nameItr = std::find_if(m_table.begin(), m_table.end(),
120  [&] (const auto& entry) { return name == entry->getNamePrefix(); });
121 
122  // Attempt to find a routing table pool entry (RTPE) we can use.
123  auto rtpeItr = m_rtpool.find(destRouter);
124 
125  // These declarations just to make the compiler happy...
127  std::shared_ptr<RoutingTablePoolEntry> rtpePtr(nullptr);
128 
129  // There isn't currently a routing table entry in the pool for this name
130  if (rtpeItr == m_rtpool.end()) {
131  // See if there is a routing table entry available we could use
132  RoutingTableEntry* routeEntryPtr = m_routingTable.findRoutingTableEntry(destRouter);
133 
134  // We have to create a new routing table entry
135  if (routeEntryPtr == nullptr) {
136  rtpe = RoutingTablePoolEntry(destRouter, 0);
137  }
138  // There was already a usable one in the routing table
139  else {
140  rtpe = RoutingTablePoolEntry(*routeEntryPtr, 0);
141  }
142 
143  // Add the new pool object to the pool.
144  rtpePtr = addRtpeToPool(rtpe);
145  }
146  // There was one already, so just fetch that one.
147  else {
148  rtpePtr = (*rtpeItr).second;
149  }
150 
151  std::shared_ptr<NamePrefixTableEntry> npte;
152  // Either we have to make a new NPT entry or there already was one.
153  if (nameItr == m_table.end()) {
154  NLSR_LOG_DEBUG("Adding origin: " << rtpePtr->getDestination()
155  << " to a new name prefix: " << name);
156  npte = std::make_shared<NamePrefixTableEntry>(name);
157  npte->addRoutingTableEntry(rtpePtr);
158  npte->generateNhlfromRteList();
159  m_table.push_back(npte);
160 
161  // If this entry has next hops, we need to inform the FIB
162  if (npte->getNexthopList().size() > 0) {
163  NLSR_LOG_TRACE("Updating FIB with next hops for " << npte->getNamePrefix());
164  m_fib.update(name, npte->getNexthopList());
165  }
166  // The routing table may recalculate and add a routing table entry
167  // with no next hops to replace an existing routing table entry. In
168  // this case, the name prefix is no longer reachable through a next
169  // hop and should be removed from the FIB. But, the prefix should
170  // remain in the Name Prefix Table as a future routing table
171  // calculation may add next hops.
172  else {
173  NLSR_LOG_TRACE(npte->getNamePrefix() << " has no next hops; removing from FIB");
174  m_fib.remove(name);
175  }
176  }
177  else {
178  npte = *nameItr;
179  NLSR_LOG_TRACE("Adding origin: " << rtpePtr->getDestination() <<
180  " to existing prefix: " << **nameItr);
181  (*nameItr)->addRoutingTableEntry(rtpePtr);
182  (*nameItr)->generateNhlfromRteList();
183 
184  if ((*nameItr)->getNexthopList().size() > 0) {
185  NLSR_LOG_TRACE("Updating FIB with next hops for " << (**nameItr));
186  m_fib.update(name, (*nameItr)->getNexthopList());
187  }
188  else {
189  NLSR_LOG_TRACE(npte->getNamePrefix() << " has no next hops; removing from FIB");
190  m_fib.remove(name);
191  }
192  }
193 
194  // Add the reference to this NPT to the RTPE.
195  rtpePtr->namePrefixTableEntries.try_emplace(npte->getNamePrefix(),
196  std::weak_ptr<NamePrefixTableEntry>(npte));
197 }
198 
199 void
200 NamePrefixTable::removeEntry(const ndn::Name& name, const ndn::Name& destRouter)
201 {
202  NLSR_LOG_DEBUG("Removing origin: " << destRouter << " from " << name);
203 
204  // Fetch an iterator to the appropriate pair object in the pool.
205  auto rtpeItr = m_rtpool.find(destRouter);
206 
207  // Simple error checking to prevent any unusual behavior in the case
208  // that we try to remove an entry that isn't there.
209  if (rtpeItr == m_rtpool.end()) {
210  NLSR_LOG_DEBUG("No entry for origin: " << destRouter
211  << " found, so it cannot be removed from prefix: " << name);
212  return;
213  }
214  std::shared_ptr<RoutingTablePoolEntry> rtpePtr = rtpeItr->second;
215 
216  // Ensure that the entry exists
217  auto nameItr = std::find_if(m_table.begin(), m_table.end(),
218  [&] (const auto& entry) { return entry->getNamePrefix() == name; });
219  if (nameItr != m_table.end()) {
220  NLSR_LOG_TRACE("Removing origin: " << rtpePtr->getDestination()
221  << " from prefix: " << **nameItr);
222 
223  // Rather than iterating through the whole list periodically, just
224  // delete them here if they have no references.
225  if ((*nameItr)->removeRoutingTableEntry(rtpePtr) == 0) {
226  deleteRtpeFromPool(rtpePtr);
227  }
228 
229  // If the prefix is a router prefix and it does not have any other
230  // routing table entries, the Adjacency/Coordinate LSA associated
231  // with that origin router has been removed from the LSDB and so
232  // the router prefix should be removed from the Name Prefix Table.
233  //
234  // If the prefix is an advertised name prefix: If another router
235  // advertises this name prefix, the RteList should have another
236  // entry for that router; the next hops should be recalculated
237  // and installed in the FIB.
238  //
239  // If no other router advertises this name prefix, the RteList
240  // should be empty and the prefix can be removed from the Name
241  // Prefix Table. Once a new Name LSA advertises this prefix, a
242  // new entry for the prefix will be created.
243  //
244  if ((*nameItr)->getRteListSize() == 0) {
245  NLSR_LOG_TRACE(**nameItr << " has no routing table entries;"
246  << " removing from table and FIB");
247  m_table.erase(nameItr);
248  m_fib.remove(name);
249  }
250  else {
251  NLSR_LOG_TRACE(**nameItr << " has other routing table entries;"
252  << " updating FIB with next hops");
253  (*nameItr)->generateNhlfromRteList();
254  m_fib.update(name, (*nameItr)->getNexthopList());
255  }
256  }
257  else {
258  NLSR_LOG_DEBUG("Attempted to remove origin: " << rtpePtr->getDestination()
259  << " from non-existent prefix: " << name);
260  }
261 }
262 
263 void
264 NamePrefixTable::updateWithNewRoute(const std::list<RoutingTableEntry>& entries)
265 {
266  NLSR_LOG_DEBUG("Updating table with newly calculated routes");
267 
268  // Iterate over each pool entry we have
269  for (auto&& poolEntryPair : m_rtpool) {
270  auto&& poolEntry = poolEntryPair.second;
271  auto sourceEntry = std::find_if(entries.begin(), entries.end(),
272  [&poolEntry] (const RoutingTableEntry& entry) {
273  return poolEntry->getDestination() == entry.getDestination();
274  });
275  // If this pool entry has a corresponding entry in the routing table now
276  if (sourceEntry != entries.end()
277  && poolEntry->getNexthopList() != sourceEntry->getNexthopList()) {
278  NLSR_LOG_DEBUG("Routing entry: " << poolEntry->getDestination() << " has changed next-hops.");
279  poolEntry->setNexthopList(sourceEntry->getNexthopList());
280  for (const auto& nameEntry : poolEntry->namePrefixTableEntries) {
281  auto nameEntryFullPtr = nameEntry.second.lock();
282  addEntry(nameEntryFullPtr->getNamePrefix(), poolEntry->getDestination());
283  }
284  }
285  else if (sourceEntry == entries.end()) {
286  NLSR_LOG_DEBUG("Routing entry: " << poolEntry->getDestination() << " now has no next-hops.");
287  poolEntry->getNexthopList().clear();
288  for (const auto& nameEntry : poolEntry->namePrefixTableEntries) {
289  auto nameEntryFullPtr = nameEntry.second.lock();
290  addEntry(nameEntryFullPtr->getNamePrefix(), poolEntry->getDestination());
291  }
292  }
293  else {
294  NLSR_LOG_TRACE("No change in routing entry:" << poolEntry->getDestination()
295  << ", no action necessary.");
296  }
297  }
298 }
299 
300 // Inserts the routing table pool entry into the NPT's RTE storage
301 // pool. This cannot fail, so the pool is guaranteed to contain the
302 // item after this occurs.
303 std::shared_ptr<RoutingTablePoolEntry>
305 {
306  auto poolIt = m_rtpool.try_emplace(rtpe.getDestination(),
307  std::make_shared<RoutingTablePoolEntry>(rtpe)).first;
308  return poolIt->second;
309 }
310 
311 // Removes the routing table pool entry from the storage pool. The
312 // postconditions of this function are guaranteed to include that
313 // the storage pool does not contain such an item. Additionally,
314 // this function cannot fail, but nonetheless debug information is
315 // given in the case that this function is called with an entry that
316 // isn't in the pool.
317 void
318 NamePrefixTable::deleteRtpeFromPool(std::shared_ptr<RoutingTablePoolEntry> rtpePtr)
319 {
320  if (m_rtpool.erase(rtpePtr->getDestination()) != 1) {
321  NLSR_LOG_DEBUG("Attempted to delete non-existent origin: "
322  << rtpePtr->getDestination()
323  << " from NPT routing table entry storage pool.");
324  }
325 }
326 
327 void
329 {
330  NLSR_LOG_DEBUG(*this);
331 }
332 
333 std::ostream&
334 operator<<(std::ostream& os, const NamePrefixTable& table)
335 {
336  os << "----------------NPT----------------------\n";
337 
338  for (const auto& entryPtr : table) {
339  os << *entryPtr << std::endl;
340  }
341 
342  return os;
343 }
344 
345 } // namespace nlsr
Maps names to lists of next hops, and exports this information to NFD.
Definition: fib.hpp:63
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
ndn::signal::Signal< Lsdb, std::shared_ptr< Lsa >, LsdbUpdate, std::list< ndn::Name >, std::list< ndn::Name > > AfterLsdbModified
Definition: lsdb.hpp:338
std::shared_ptr< RoutingTablePoolEntry > addRtpeToPool(RoutingTablePoolEntry &rtpe)
Adds a pool entry to the pool.
void removeEntry(const ndn::Name &name, const ndn::Name &destRouter)
Removes a destination from a name prefix table entry.
void updateWithNewRoute(const std::list< RoutingTableEntry > &entries)
Updates all routing information in the NPT.
NamePrefixTable(const ndn::Name &ownRouterName, Fib &fib, RoutingTable &routingTable, AfterRoutingChange &afterRoutingChangeSignal, Lsdb::AfterLsdbModified &afterLsdbModifiedSignal)
void updateFromLsdb(std::shared_ptr< Lsa > lsa, LsdbUpdate updateType, const std::list< ndn::Name > &namesToAdd, const std::list< ndn::Name > &namesToRemove)
Add, update, or remove Names according to the Lsdb update.
void addEntry(const ndn::Name &name, const ndn::Name &destRouter)
Adds a destination to the specified name prefix.
void deleteRtpeFromPool(std::shared_ptr< RoutingTablePoolEntry > rtpePtr)
Removes a pool entry from the pool.
Data abstraction for RouteTableInfo.
const ndn::Name & getDestination() const
RoutingTableEntry * findRoutingTableEntry(const ndn::Name &destRouter)
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_TRACE(x)
Definition: logger.hpp:37
Copyright (c) 2014-2020, The University of Memphis, Regents of the University of California.
std::ostream & operator<<(std::ostream &os, const Adjacent &adjacent)
Definition: adjacent.cpp:176
ndn::signal::Signal< RoutingTable, std::list< RoutingTableEntry > > AfterRoutingChange
Definition: signals.hpp:35
LsdbUpdate
Definition: lsdb.hpp:53