route: Prevent incomplete removal of NPT entry
refs: #2785
Change-Id: Ic8ff955236784db76c55b94bf9300fb21ea9beae
diff --git a/src/route/name-prefix-table.cpp b/src/route/name-prefix-table.cpp
index ba7dd75..56bea2d 100644
--- a/src/route/name-prefix-table.cpp
+++ b/src/route/name-prefix-table.cpp
@@ -19,56 +19,68 @@
* NLSR, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
**/
+#include "name-prefix-table.hpp"
+
+#include "logger.hpp"
+#include "nlsr.hpp"
+#include "routing-table.hpp"
+
+#include <algorithm>
#include <list>
#include <utility>
-#include <algorithm>
-
-#include "nlsr.hpp"
-#include "name-prefix-table.hpp"
-#include "name-prefix-table-entry.hpp"
-#include "routing-table.hpp"
-#include "logger.hpp"
namespace nlsr {
INIT_LOGGER("NamePrefixTable");
-using namespace std;
-
static bool
npteCompare(NamePrefixTableEntry& npte, const ndn::Name& name)
{
return npte.getNamePrefix() == name;
}
-
-
void
NamePrefixTable::addEntry(const ndn::Name& name, RoutingTableEntry& rte)
{
- std::list<NamePrefixTableEntry>::iterator it = std::find_if(m_table.begin(),
- m_table.end(),
- ndn::bind(&npteCompare, _1, name));
+ NptEntryList::iterator it = std::find_if(m_table.begin(),
+ m_table.end(),
+ bind(&npteCompare, _1, name));
if (it == m_table.end()) {
- NamePrefixTableEntry newEntry(name);
- newEntry.addRoutingTableEntry(rte);
- newEntry.generateNhlfromRteList();
- newEntry.getNexthopList().sort();
- m_table.push_back(newEntry);
+ _LOG_TRACE("Adding origin: " << rte.getDestination() << " to new name prefix: " << name);
+
+ NamePrefixTableEntry entry(name);
+
+ entry.addRoutingTableEntry(rte);
+
+ entry.generateNhlfromRteList();
+ entry.getNexthopList().sort();
+
+ m_table.push_back(entry);
+
if (rte.getNexthopList().getSize() > 0) {
- m_nlsr.getFib().update(name, newEntry.getNexthopList());
+ _LOG_TRACE("Updating FIB with next hops for " << entry);
+ m_nlsr.getFib().update(name, entry.getNexthopList());
}
}
else {
- if (rte.getNexthopList().getSize() > 0) {
- (*it).addRoutingTableEntry(rte);
- (*it).generateNhlfromRteList();
- (*it).getNexthopList().sort();
- m_nlsr.getFib().update(name, (*it).getNexthopList());
+ _LOG_TRACE("Adding origin: " << rte.getDestination() << " to existing prefix: " << *it);
+
+ it->addRoutingTableEntry(rte);
+
+ it->generateNhlfromRteList();
+ it->getNexthopList().sort();
+
+ if (it->getNexthopList().getSize() > 0) {
+ _LOG_TRACE("Updating FIB with next hops for " << *it);
+ m_nlsr.getFib().update(name, it->getNexthopList());
}
else {
- (*it).resetRteListNextHop();
- (*it).getNexthopList().reset();
+ // The routing table may recalculate and add a routing table entry with no next hops to
+ // replace an existing routing table entry. In this case, the name prefix is no longer
+ // reachable through a next hop and should be removed from the FIB. But, the prefix
+ // should remain in the Name Prefix Table as a future routing table calculation may
+ // add next hops.
+ _LOG_TRACE(*it << " has no next hops; removing from FIB");
m_nlsr.getFib().remove(name);
}
}
@@ -77,40 +89,50 @@
void
NamePrefixTable::removeEntry(const ndn::Name& name, RoutingTableEntry& rte)
{
- std::list<NamePrefixTableEntry>::iterator it = std::find_if(m_table.begin(),
- m_table.end(),
- ndn::bind(&npteCompare, _1, name));
+ NptEntryList::iterator it = std::find_if(m_table.begin(),
+ m_table.end(),
+ bind(&npteCompare, _1, name));
if (it != m_table.end()) {
- const ndn::Name destRouter = rte.getDestination();
+ _LOG_TRACE("Removing origin: " << rte.getDestination() << " from prefix: " << *it);
+
it->removeRoutingTableEntry(rte);
- if (it->getRteListSize() == 0 &&
- !m_nlsr.getLsdb().doesLsaExist(ndn::Name(destRouter).append(NameLsa::TYPE_STRING),
- NameLsa::TYPE_STRING) &&
- !m_nlsr.getLsdb().doesLsaExist(ndn::Name(destRouter).append(AdjLsa::TYPE_STRING),
- AdjLsa::TYPE_STRING) &&
- !m_nlsr.getLsdb().doesLsaExist(ndn::Name(destRouter).append(CoordinateLsa::TYPE_STRING),
- CoordinateLsa::TYPE_STRING))
- {
+ // If the prefix is a router prefix and it does not have any other routing table entries,
+ // the Adjacency/Coordinate LSA associated with that origin router has been removed from
+ // the LSDB and so the router prefix should be removed from the Name Prefix Table.
+ //
+ // If the prefix is an advertised name prefix:
+ // If another router advertises this name prefix, the RteList should have another entry
+ // for that router; the next hops should be recalculated and installed in the FIB.
+ //
+ // If no other router advertises this name prefix, the RteList should be empty and the
+ // prefix can be removed from the Name Prefix Table. Once a new Name LSA advertises this
+ // prefix, a new entry for the prefix will be created.
+ //
+ if (it->getRteListSize() == 0) {
+ _LOG_TRACE(*it << " has no routing table entries; removing from table and FIB");
m_table.erase(it);
m_nlsr.getFib().remove(name);
}
else {
- (*it).generateNhlfromRteList();
- m_nlsr.getFib().update(name, (*it).getNexthopList());
+ _LOG_TRACE(*it << " has other routing table entries; updating FIB with next hops");
+ it->generateNhlfromRteList();
+ it->getNexthopList().sort();
+
+ m_nlsr.getFib().update(name, it->getNexthopList());
}
}
}
-
void
NamePrefixTable::addEntry(const ndn::Name& name, const ndn::Name& destRouter)
{
- //
- RoutingTableEntry* rteCheck =
- m_nlsr.getRoutingTable().findRoutingTableEntry(destRouter);
- if (rteCheck != 0) {
- addEntry(name, *(rteCheck));
+ _LOG_DEBUG("Adding origin: " << destRouter << " to " << name);
+
+ RoutingTableEntry* rteCheck = m_nlsr.getRoutingTable().findRoutingTableEntry(destRouter);
+
+ if (rteCheck != nullptr) {
+ addEntry(name, *rteCheck);
}
else {
RoutingTableEntry rte(destRouter);
@@ -121,11 +143,12 @@
void
NamePrefixTable::removeEntry(const ndn::Name& name, const ndn::Name& destRouter)
{
- //
- RoutingTableEntry* rteCheck =
- m_nlsr.getRoutingTable().findRoutingTableEntry(destRouter);
- if (rteCheck != 0) {
- removeEntry(name, *(rteCheck));
+ _LOG_DEBUG("Removing origin: " << destRouter << " from " << name);
+
+ RoutingTableEntry* rteCheck = m_nlsr.getRoutingTable().findRoutingTableEntry(destRouter);
+
+ if (rteCheck != nullptr) {
+ removeEntry(name, *rteCheck);
}
else {
RoutingTableEntry rte(destRouter);
@@ -136,19 +159,23 @@
void
NamePrefixTable::updateWithNewRoute()
{
- for (std::list<NamePrefixTableEntry>::iterator it = m_table.begin();
- it != m_table.end(); ++it) {
- std::list<RoutingTableEntry> rteList = (*it).getRteList();
- for (std::list<RoutingTableEntry>::iterator rteit = rteList.begin();
- rteit != rteList.end(); ++rteit) {
+ _LOG_DEBUG("Updating table with newly calculated routes");
+
+ // Update each name prefix entry in the Name Prefix Table with newly calculated next hops
+ for (const NamePrefixTableEntry& prefixEntry : m_table) {
+ for (const RoutingTableEntry& routingEntry : prefixEntry.getRteList()) {
+ _LOG_TRACE("Updating next hops to origin: " << routingEntry.getDestination()
+ << " for prefix: " << prefixEntry);
+
RoutingTableEntry* rteCheck =
- m_nlsr.getRoutingTable().findRoutingTableEntry((*rteit).getDestination());
- if (rteCheck != 0) {
- addEntry((*it).getNamePrefix(), *(rteCheck));
+ m_nlsr.getRoutingTable().findRoutingTableEntry(routingEntry.getDestination());
+
+ if (rteCheck != nullptr) {
+ addEntry(prefixEntry.getNamePrefix(), *rteCheck);
}
else {
- RoutingTableEntry rte((*rteit).getDestination());
- addEntry((*it).getNamePrefix(), rte);
+ RoutingTableEntry rte(routingEntry.getDestination());
+ addEntry(prefixEntry.getNamePrefix(), rte);
}
}
}
@@ -157,12 +184,19 @@
void
NamePrefixTable::writeLog()
{
- _LOG_DEBUG("----------------NPT----------------------");
- for (std::list<NamePrefixTableEntry>::iterator it = m_table.begin();
- it != m_table.end();
- ++it) {
- (*it).writeLog();
- }
+ _LOG_DEBUG(*this);
}
-} //namespace nlsr
+std::ostream&
+operator<<(std::ostream& os, const NamePrefixTable& table)
+{
+ os << "----------------NPT----------------------\n";
+
+ for (const NamePrefixTableEntry& entry : table) {
+ os << entry << std::endl;
+ }
+
+ return os;
+}
+
+} // namespace nlsr