route: Prevent incomplete removal of NPT entry
refs: #2785
Change-Id: Ic8ff955236784db76c55b94bf9300fb21ea9beae
diff --git a/src/route/name-prefix-table-entry.cpp b/src/route/name-prefix-table-entry.cpp
index 383a00c..a465f95 100644
--- a/src/route/name-prefix-table-entry.cpp
+++ b/src/route/name-prefix-table-entry.cpp
@@ -1,7 +1,8 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2014 University of Memphis,
- * Regents of the University of California
+ * Copyright (c) 2014-2015, The University of Memphis,
+ * Regents of the University of California,
+ * Arizona Board of Regents.
*
* This file is part of NLSR (Named-data Link State Routing).
* See AUTHORS.md for complete list of NLSR authors and contributors.
@@ -16,16 +17,11 @@
*
* You should have received a copy of the GNU General Public License along with
* NLSR, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
- *
- * \author A K M Mahmudul Hoque <ahoque1@memphis.edu>
- *
**/
-#include <list>
-#include <utility>
+
+#include "name-prefix-table-entry.hpp"
#include "common.hpp"
-#include "name-prefix-table-entry.hpp"
-#include "routing-table-entry.hpp"
#include "nexthop.hpp"
#include "logger.hpp"
@@ -33,8 +29,6 @@
INIT_LOGGER("NamePrefixTableEntry");
-using namespace std;
-
void
NamePrefixTableEntry::generateNhlfromRteList()
{
@@ -105,4 +99,16 @@
m_nexthopList.writeLog();
}
-}//namespace nlsr
+std::ostream&
+operator<<(std::ostream& os, const NamePrefixTableEntry& entry)
+{
+ os << "Name: " << entry.getNamePrefix() << "\n";
+
+ for (const RoutingTableEntry& rte : entry.getRteList()) {
+ os << "Destination: " << rte.getDestination() << "\n";
+ }
+
+ return os;
+}
+
+} // namespace nlsr
diff --git a/src/route/name-prefix-table-entry.hpp b/src/route/name-prefix-table-entry.hpp
index 9b25f5e..7b8ed5a 100644
--- a/src/route/name-prefix-table-entry.hpp
+++ b/src/route/name-prefix-table-entry.hpp
@@ -1,7 +1,8 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2014 University of Memphis,
- * Regents of the University of California
+ * Copyright (c) 2014-2015, The University of Memphis,
+ * Regents of the University of California,
+ * Arizona Board of Regents.
*
* This file is part of NLSR (Named-data Link State Routing).
* See AUTHORS.md for complete list of NLSR authors and contributors.
@@ -16,18 +17,15 @@
*
* You should have received a copy of the GNU General Public License along with
* NLSR, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
- *
- * \author A K M Mahmudul Hoque <ahoque1@memphis.edu>
- *
**/
+
#ifndef NLSR_NAME_PREFIX_TABLE_ENTRY_HPP
#define NLSR_NAME_PREFIX_TABLE_ENTRY_HPP
+#include "routing-table-entry.hpp"
+
#include <list>
#include <utility>
-#include <boost/cstdint.hpp>
-
-#include "routing-table-entry.hpp"
namespace nlsr {
@@ -50,8 +48,8 @@
return m_namePrefix;
}
- std::list<RoutingTableEntry>&
- getRteList()
+ const std::list<RoutingTableEntry>&
+ getRteList() const
{
return m_rteList;
}
@@ -97,6 +95,9 @@
NexthopList m_nexthopList;
};
-}//namespace nlsr
+std::ostream&
+operator<<(std::ostream& os, const NamePrefixTableEntry& entry);
-#endif //NLSR_NAME_PREFIX_TABLE_ENTRY_HPP
+} // namespace nlsr
+
+#endif // NLSR_NAME_PREFIX_TABLE_ENTRY_HPP
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
diff --git a/src/route/name-prefix-table.hpp b/src/route/name-prefix-table.hpp
index fb36ffb..0f6e94f 100644
--- a/src/route/name-prefix-table.hpp
+++ b/src/route/name-prefix-table.hpp
@@ -1,7 +1,8 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2014 University of Memphis,
- * Regents of the University of California
+ * Copyright (c) 2014-2015, The University of Memphis,
+ * Regents of the University of California,
+ * Arizona Board of Regents.
*
* This file is part of NLSR (Named-data Link State Routing).
* See AUTHORS.md for complete list of NLSR authors and contributors.
@@ -16,25 +17,26 @@
*
* You should have received a copy of the GNU General Public License along with
* NLSR, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
- *
- * \author A K M Mahmudul Hoque <ahoque1@memphis.edu>
- *
**/
+
#ifndef NLSR_NAME_PREFIX_TABLE_HPP
#define NLSR_NAME_PREFIX_TABLE_HPP
-#include <list>
-#include <boost/cstdint.hpp>
-
#include "name-prefix-table-entry.hpp"
#include "routing-table-entry.hpp"
+#include <list>
+
namespace nlsr {
class Nlsr;
class NamePrefixTable
{
public:
+
+ typedef std::list<NamePrefixTableEntry> NptEntryList;
+ typedef NptEntryList::const_iterator const_iterator;
+
NamePrefixTable(Nlsr& nlsr)
: m_nlsr(nlsr)
{
@@ -52,6 +54,12 @@
void
writeLog();
+ const_iterator
+ begin() const;
+
+ const_iterator
+ end() const;
+
private:
void
addEntry(const ndn::Name& name, RoutingTableEntry& rte);
@@ -64,6 +72,21 @@
std::list<NamePrefixTableEntry> m_table;
};
-}//namespace nlsr
+inline NamePrefixTable::const_iterator
+NamePrefixTable::begin() const
+{
+ return m_table.begin();
+}
-#endif //NLSR_NAME_PREFIX_TABLE_HPP
+inline NamePrefixTable::const_iterator
+NamePrefixTable::end() const
+{
+ return m_table.end();
+}
+
+std::ostream&
+operator<<(std::ostream& os, const NamePrefixTable& table);
+
+} // namespace nlsr
+
+#endif // NLSR_NAME_PREFIX_TABLE_HPP
diff --git a/tests/test-name-prefix-table.cpp b/tests/test-name-prefix-table.cpp
new file mode 100644
index 0000000..c7c64b7
--- /dev/null
+++ b/tests/test-name-prefix-table.cpp
@@ -0,0 +1,147 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015, The University of Memphis,
+ * Regents of the University of California,
+ * Arizona Board of Regents.
+ *
+ * This file is part of NLSR (Named-data Link State Routing).
+ * See AUTHORS.md for complete list of NLSR authors and contributors.
+ *
+ * NLSR is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NLSR is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NLSR, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ **/
+
+#include "nlsr.hpp"
+#include "test-common.hpp"
+
+#include <ndn-cxx/util/dummy-client-face.hpp>
+
+namespace nlsr {
+namespace test {
+
+class NamePrefixTableFixture : public UnitTestTimeFixture
+{
+public:
+ NamePrefixTableFixture()
+ : face(ndn::util::makeDummyClientFace(g_ioService))
+ , nlsr(g_ioService, g_scheduler, ndn::ref(*face))
+ , lsdb(nlsr.getLsdb())
+ , npt(nlsr.getNamePrefixTable())
+ {
+ INIT_LOGGERS("/tmp", "DEBUG");
+ }
+
+public:
+ shared_ptr<ndn::util::DummyClientFace> face;
+ Nlsr nlsr;
+
+ Lsdb& lsdb;
+ NamePrefixTable& npt;
+};
+
+BOOST_AUTO_TEST_SUITE(TestNamePrefixTable)
+
+BOOST_FIXTURE_TEST_CASE(Bupt, NamePrefixTableFixture)
+{
+ ConfParameter& conf = nlsr.getConfParameter();
+ conf.setNetwork("/ndn");
+ conf.setSiteName("/router");
+ conf.setRouterName("/a");
+ conf.buildRouterPrefix();
+
+ RoutingTable& routingTable = nlsr.getRoutingTable();
+ routingTable.setRoutingCalcInterval(0);
+
+ NamePrefixTable& npt = nlsr.getNamePrefixTable();
+
+ Adjacent thisRouter(conf.getRouterPrefix(), "udp://face", 0, Adjacent::STATUS_ACTIVE, 0, 0);
+
+ ndn::Name buptRouterName("/ndn/cn/edu/bupt/%C1.Router/bupthub");
+ Adjacent bupt(buptRouterName, "udp://bupt", 0, Adjacent::STATUS_ACTIVE, 0, 0);
+
+ // This router's Adjacency LSA
+ nlsr.getAdjacencyList().insert(bupt);
+ AdjLsa thisRouterAdjLsa(thisRouter.getName(),
+ AdjLsa::TYPE_STRING,
+ 1,
+ ndn::time::system_clock::now() + ndn::time::seconds::max(),
+ 2,
+ nlsr.getAdjacencyList());
+
+ lsdb.installAdjLsa(thisRouterAdjLsa);
+
+ // BUPT Adjacency LSA
+ AdjacencyList buptAdjacencies;
+ buptAdjacencies.insert(thisRouter);
+ AdjLsa buptAdjLsa(buptRouterName,
+ AdjLsa::TYPE_STRING,
+ 1,
+ ndn::time::system_clock::now() + ndn::time::seconds(5),
+ 0 , buptAdjacencies);
+
+ lsdb.installAdjLsa(buptAdjLsa);
+
+ // BUPT Name LSA
+ ndn::Name buptAdvertisedName("/ndn/cn/edu/bupt");
+
+ NamePrefixList buptNames;
+ buptNames.insert(buptAdvertisedName);
+
+ NameLsa buptNameLsa(buptRouterName,
+ NameLsa::TYPE_STRING,
+ 1,
+ ndn::time::system_clock::now(),
+ buptNames);
+
+ lsdb.installNameLsa(buptNameLsa);
+
+ // Advance clocks to expire LSAs
+ this->advanceClocks(ndn::time::seconds(15));
+
+ // LSA expirations should cause NPT entries to be completely removed
+ NamePrefixTable::const_iterator it = npt.begin();
+ BOOST_REQUIRE(it == npt.end());
+
+ // Install new name LSA
+ NameLsa buptNewNameLsa(buptRouterName, NameLsa::TYPE_STRING,
+ 12,
+ ndn::time::system_clock::now() + ndn::time::seconds(3600),
+ buptNames);
+
+ lsdb.installNameLsa(buptNewNameLsa);
+
+ this->advanceClocks(ndn::time::seconds(1));
+
+ // Install new adjacency LSA
+ AdjLsa buptNewAdjLsa(buptRouterName, AdjLsa::TYPE_STRING,
+ 12,
+ ndn::time::system_clock::now() + ndn::time::seconds(3600),
+ 0, buptAdjacencies);
+ lsdb.installAdjLsa(buptNewAdjLsa);
+
+ this->advanceClocks(ndn::time::seconds(1));
+
+ // Each NPT entry should have a destination router
+ it = npt.begin();
+ BOOST_REQUIRE_EQUAL(it->getNamePrefix(), buptRouterName);
+ BOOST_REQUIRE_EQUAL(it->getRteList().size(), 1);
+ BOOST_CHECK_EQUAL(it->getRteList().begin()->getDestination(), buptRouterName);
+
+ ++it;
+ BOOST_REQUIRE_EQUAL(it->getNamePrefix(), buptAdvertisedName);
+ BOOST_REQUIRE_EQUAL(it->getRteList().size(), 1);
+ BOOST_CHECK_EQUAL(it->getRteList().begin()->getDestination(), buptRouterName);
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace test
+} // namespace nlsr