name-prefix-table.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
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 
37  std::unique_ptr<AfterRoutingChange>& afterRoutingChangeSignal)
38  : m_fib(fib)
39  , m_routingTable(routingTable)
40 {
41  m_afterRoutingChangeConnection = afterRoutingChangeSignal->connect(
42  [this] (const std::list<RoutingTableEntry>& entries) {
43  updateWithNewRoute(entries);
44  });
45 }
46 
48 {
49  m_afterRoutingChangeConnection.disconnect();
50 }
51 
52 void
53 NamePrefixTable::addEntry(const ndn::Name& name, const ndn::Name& destRouter)
54 {
55 
56  // Check if the advertised name prefix is in the table already.
57  NptEntryList::iterator nameItr =
58  std::find_if(m_table.begin(),
59  m_table.end(),
60  [&] (const std::shared_ptr<NamePrefixTableEntry>& entry) {
61  return name == entry->getNamePrefix();
62  });
63 
64  // Attempt to find a routing table pool entry (RTPE) we can use.
65  RoutingTableEntryPool::iterator rtpeItr = m_rtpool.find(destRouter);
66 
67  // These declarations just to make the compiler happy...
69  std::shared_ptr<RoutingTablePoolEntry> rtpePtr(nullptr);
70 
71  // There isn't currently a routing table entry in the pool for this name
72  if (rtpeItr == m_rtpool.end()) {
73  // See if there is a routing table entry available we could use
74  RoutingTableEntry* routeEntryPtr = m_routingTable.findRoutingTableEntry(destRouter);
75 
76  // We have to create a new routing table entry
77  if (routeEntryPtr == nullptr) {
78  rtpe = RoutingTablePoolEntry(destRouter, 0);
79  }
80  // There was already a usable one in the routing table
81  else {
82  rtpe = RoutingTablePoolEntry(*routeEntryPtr, 0);
83  }
84 
85  // Add the new pool object to the pool.
86  rtpePtr = addRtpeToPool(rtpe);
87  }
88  // There was one already, so just fetch that one.
89  else {
90  rtpePtr = (*rtpeItr).second;
91  }
92 
93  std::shared_ptr<NamePrefixTableEntry> npte;
94  // Either we have to make a new NPT entry or there already was one.
95  if (nameItr == m_table.end()) {
96  NLSR_LOG_DEBUG("Adding origin: " << rtpePtr->getDestination()
97  << " to a new name prefix: " << name);
98  npte = make_shared<NamePrefixTableEntry>(name);
99  npte->addRoutingTableEntry(rtpePtr);
100  npte->generateNhlfromRteList();
101  m_table.push_back(npte);
102  // If this entry has next hops, we need to inform the FIB
103  if (npte->getNexthopList().size() > 0) {
104  NLSR_LOG_TRACE("Updating FIB with next hops for " << npte->getNamePrefix());
105  m_fib.update(name, npte->getNexthopList());
106  }
107  // The routing table may recalculate and add a routing table entry
108  // with no next hops to replace an existing routing table entry. In
109  // this case, the name prefix is no longer reachable through a next
110  // hop and should be removed from the FIB. But, the prefix should
111  // remain in the Name Prefix Table as a future routing table
112  // calculation may add next hops.
113  else {
114  NLSR_LOG_TRACE(npte->getNamePrefix() << " has no next hops; removing from FIB");
115  m_fib.remove(name);
116  }
117  }
118  else {
119  npte = *nameItr;
120  NLSR_LOG_TRACE("Adding origin: " << rtpePtr->getDestination() <<
121  " to existing prefix: " << **nameItr);
122  (*nameItr)->addRoutingTableEntry(rtpePtr);
123  (*nameItr)->generateNhlfromRteList();
124 
125  if ((*nameItr)->getNexthopList().size() > 0) {
126  NLSR_LOG_TRACE("Updating FIB with next hops for " << (**nameItr));
127  m_fib.update(name, (*nameItr)->getNexthopList());
128  }
129  else {
130  NLSR_LOG_TRACE(npte->getNamePrefix() << " has no next hops; removing from FIB");
131  m_fib.remove(name);
132  }
133  }
134  // Add the reference to this NPT to the RTPE.
135  rtpePtr->namePrefixTableEntries.emplace(
136  std::make_pair(npte->getNamePrefix(), std::weak_ptr<NamePrefixTableEntry>(npte)));
137 }
138 
139 void
140 NamePrefixTable::removeEntry(const ndn::Name& name, const ndn::Name& destRouter)
141 {
142  NLSR_LOG_DEBUG("Removing origin: " << destRouter << " from " << name);
143 
144  // Fetch an iterator to the appropriate pair object in the pool.
145  RoutingTableEntryPool::iterator rtpeItr = m_rtpool.find(destRouter);
146 
147  // Simple error checking to prevent any unusual behavior in the case
148  // that we try to remove an entry that isn't there.
149  if (rtpeItr == m_rtpool.end()) {
150  NLSR_LOG_DEBUG("No entry for origin: " << destRouter
151  << " found, so it cannot be removed from prefix: "
152  << name);
153  return;
154  }
155  std::shared_ptr<RoutingTablePoolEntry> rtpePtr = rtpeItr->second;
156 
157  // Ensure that the entry exists
158  NptEntryList::iterator nameItr =
159  std::find_if(m_table.begin(), m_table.end(),
160  [&] (const std::shared_ptr<NamePrefixTableEntry>& entry) {
161  return entry->getNamePrefix() == name;
162  });
163  if (nameItr != m_table.end()) {
164  NLSR_LOG_TRACE("Removing origin: " << rtpePtr->getDestination()
165  << " from prefix: " << **nameItr);
166 
167  // Rather than iterating through the whole list periodically, just
168  // delete them here if they have no references.
169  if ((*nameItr)->removeRoutingTableEntry(rtpePtr) == 0) {
170  deleteRtpeFromPool(rtpePtr);
171  }
172 
173  // If the prefix is a router prefix and it does not have any other
174  // routing table entries, the Adjacency/Coordinate LSA associated
175  // with that origin router has been removed from the LSDB and so
176  // the router prefix should be removed from the Name Prefix Table.
177  //
178  // If the prefix is an advertised name prefix: If another router
179  // advertises this name prefix, the RteList should have another
180  // entry for that router; the next hops should be recalculated
181  // and installed in the FIB.
182  //
183  // If no other router advertises this name prefix, the RteList
184  // should be empty and the prefix can be removed from the Name
185  // Prefix Table. Once a new Name LSA advertises this prefix, a
186  // new entry for the prefix will be created.
187  //
188  if ((*nameItr)->getRteListSize() == 0) {
189  NLSR_LOG_TRACE(**nameItr << " has no routing table entries;"
190  << " removing from table and FIB");
191  m_table.erase(nameItr);
192  m_fib.remove(name);
193  }
194  else {
195  NLSR_LOG_TRACE(**nameItr << " has other routing table entries;"
196  << " updating FIB with next hops");
197  (*nameItr)->generateNhlfromRteList();
198  m_fib.update(name, (*nameItr)->getNexthopList());
199  }
200  }
201  else {
202  NLSR_LOG_DEBUG("Attempted to remove origin: " << rtpePtr->getDestination()
203  << " from non-existent prefix: " << name);
204  }
205 }
206 
207 void
208 NamePrefixTable::updateWithNewRoute(const std::list<RoutingTableEntry>& entries)
209 {
210  NLSR_LOG_DEBUG("Updating table with newly calculated routes");
211 
212  // Iterate over each pool entry we have
213  for (auto&& poolEntryPair : m_rtpool) {
214  auto&& poolEntry = poolEntryPair.second;
215  auto sourceEntry = std::find_if(entries.begin(), entries.end(),
216  [&poolEntry] (const RoutingTableEntry& entry) {
217  return poolEntry->getDestination() == entry.getDestination();
218  });
219  // If this pool entry has a corresponding entry in the routing table now
220  if (sourceEntry != entries.end()
221  && poolEntry->getNexthopList() != sourceEntry->getNexthopList()) {
222  NLSR_LOG_DEBUG("Routing entry: " << poolEntry->getDestination() << " has changed next-hops.");
223  poolEntry->setNexthopList(sourceEntry->getNexthopList());
224  for (const auto& nameEntry : poolEntry->namePrefixTableEntries) {
225  auto nameEntryFullPtr = nameEntry.second.lock();
226  addEntry(nameEntryFullPtr->getNamePrefix(), poolEntry->getDestination());
227  }
228  }
229  else if (sourceEntry == entries.end()) {
230  NLSR_LOG_DEBUG("Routing entry: " << poolEntry->getDestination() << " now has no next-hops.");
231  poolEntry->getNexthopList().reset();
232  for (const auto& nameEntry : poolEntry->namePrefixTableEntries) {
233  auto nameEntryFullPtr = nameEntry.second.lock();
234  addEntry(nameEntryFullPtr->getNamePrefix(), poolEntry->getDestination());
235  }
236  }
237  else {
238  NLSR_LOG_TRACE("No change in routing entry:" << poolEntry->getDestination()
239  << ", no action necessary.");
240  }
241  }
242 }
243 
244  // Inserts the routing table pool entry into the NPT's RTE storage
245  // pool. This cannot fail, so the pool is guaranteed to contain the
246  // item after this occurs.
247 std::shared_ptr<RoutingTablePoolEntry>
249 {
250  RoutingTableEntryPool::iterator poolItr =
251  m_rtpool.insert(std::make_pair(rtpe.getDestination(),
252  std::make_shared<RoutingTablePoolEntry>
253  (rtpe)))
254  .first;
255  return poolItr->second;
256 }
257 
258  // Removes the routing table pool entry from the storage pool. The
259  // postconditions of this function are guaranteed to include that
260  // the storage pool does not contain such an item. Additionally,
261  // this function cannot fail, but nonetheless debug information is
262  // given in the case that this function is called with an entry that
263  // isn't in the pool.
264 void
265 NamePrefixTable::deleteRtpeFromPool(std::shared_ptr<RoutingTablePoolEntry> rtpePtr)
266 {
267  if (m_rtpool.erase(rtpePtr->getDestination()) != 1) {
268  NLSR_LOG_DEBUG("Attempted to delete non-existent origin: "
269  << rtpePtr->getDestination()
270  << " from NPT routing table entry storage pool.");
271  }
272 }
273 
274 void
276 {
277  NLSR_LOG_DEBUG(*this);
278 }
279 
280 std::ostream&
281 operator<<(std::ostream& os, const NamePrefixTable& table)
282 {
283  os << "----------------NPT----------------------\n";
284 
285  for (const auto& entryPtr : table) {
286  os << *entryPtr << std::endl;
287  }
288 
289  return os;
290 }
291 
292 } // namespace nlsr
void update(const ndn::Name &name, const NexthopList &allHops)
Set the nexthop list of a name.
Definition: fib.cpp:89
std::ostream & operator<<(std::ostream &os, const Adjacent &adjacent)
Definition: adjacent.cpp:99
NamePrefixTable(Fib &fib, RoutingTable &routingTable, std::unique_ptr< AfterRoutingChange > &afterRoutingChangeSignal)
std::shared_ptr< RoutingTablePoolEntry > addRtpeToPool(RoutingTablePoolEntry &rtpe)
Adds a pool entry to the pool.
void deleteRtpeFromPool(std::shared_ptr< RoutingTablePoolEntry > rtpePtr)
Removes a pool entry from the pool.
#define NLSR_LOG_DEBUG(x)
Definition: logger.hpp:38
void updateWithNewRoute(const std::list< RoutingTableEntry > &entries)
Updates all routing information in the NPT.
Copyright (c) 2014-2018, The University of Memphis, Regents of the University of California.
Maps names to lists of next hops, and exports this information to NFD.
Definition: fib.hpp:53
#define INIT_LOGGER(name)
Definition: logger.hpp:35
void removeEntry(const ndn::Name &name, const ndn::Name &destRouter)
Removes a destination from a name prefix table entry.
const ndn::Name & getDestination() const
Copyright (c) 2014-2018, The University of Memphis, Regents of the University of California, Arizona Board of Regents.
void remove(const ndn::Name &name)
Completely remove a name prefix from the FIB.
Definition: fib.cpp:51
RoutingTableEntry * findRoutingTableEntry(const ndn::Name &destRouter)
#define NLSR_LOG_TRACE(x)
Definition: logger.hpp:37
void addEntry(const ndn::Name &name, const ndn::Name &destRouter)
Adds a destination to the specified name prefix.