Name prefix table entries keep pointers instead of keeping a copy of the object for routing table entries.
refs: #2863
Change-Id: I3271c9f96dfc8721a0ca7c900542c6ddb0b321ac
diff --git a/src/lsdb.hpp b/src/lsdb.hpp
index 6666558..acd030d 100644
--- a/src/lsdb.hpp
+++ b/src/lsdb.hpp
@@ -344,7 +344,7 @@
/*!
\brief Success callback when SegmentFetcher returns a valid LSA
- \param The base Interest used to fetch the LSA in the format:
+ \param interestName The base Interest used to fetch the LSA in the format:
/<network>/NLSR/LSA/<site>/%C1.Router/<router>/<lsa-type>/<seqNo>
*/
void
diff --git a/src/route/name-prefix-table-entry.cpp b/src/route/name-prefix-table-entry.cpp
index 0306911..5bd6a4c 100644
--- a/src/route/name-prefix-table-entry.cpp
+++ b/src/route/name-prefix-table-entry.cpp
@@ -33,81 +33,80 @@
NamePrefixTableEntry::generateNhlfromRteList()
{
m_nexthopList.reset();
- // For every routing table entry associated with this name prefix
- for (std::list<RoutingTableEntry>::iterator it = m_rteList.begin();
- it != m_rteList.end(); ++it)
- {
- // Add every next hop from each routing table entry to this entry's NHL.
- for (std::set<NextHop, NextHopComparator>::iterator nhit =
- (*it).getNexthopList().getNextHops().begin();
- nhit != (*it).getNexthopList().getNextHops().end(); ++nhit)
- {
- m_nexthopList.addNextHop((*nhit));
+ for (auto rtpeItr = m_rteList.begin(); rtpeItr != m_rteList.end(); ++rtpeItr) {
+ for (auto nhItr = (*rtpeItr)->getNexthopList().getNextHops().begin();
+ nhItr != (*rtpeItr)->getNexthopList().getNextHops().end();
+ ++nhItr) {
+ m_nexthopList.addNextHop((*nhItr));
}
}
}
-
-
-static bool
-rteCompare(RoutingTableEntry& rte, ndn::Name& destRouter)
+uint64_t
+NamePrefixTableEntry::removeRoutingTableEntry(shared_ptr<RoutingTablePoolEntry>
+ rtpePtr)
{
- return rte.getDestination() == destRouter;
+ auto rtpeItr = std::find(m_rteList.begin(), m_rteList.end(), rtpePtr);
+
+ if (rtpeItr != m_rteList.end()) {
+ (*rtpeItr)->decrementUseCount();
+ m_rteList.erase(rtpeItr);
+ }
+ else {
+ _LOG_ERROR("Routing entry for: " << rtpePtr->getDestination()
+ << " not found in NPT entry: " << getNamePrefix());
+ }
+ return (*rtpeItr)->getUseCount();
}
void
-NamePrefixTableEntry::removeRoutingTableEntry(RoutingTableEntry& rte)
+NamePrefixTableEntry::addRoutingTableEntry(shared_ptr<RoutingTablePoolEntry>
+ rtpePtr)
{
- std::list<RoutingTableEntry>::iterator it = std::find_if(m_rteList.begin(),
- m_rteList.end(),
- bind(&rteCompare, _1, rte.getDestination()));
- if (it != m_rteList.end())
- {
- m_rteList.erase(it);
- }
-}
+ auto rtpeItr = std::find(m_rteList.begin(), m_rteList.end(), rtpePtr);
-void
-NamePrefixTableEntry::addRoutingTableEntry(RoutingTableEntry& rte)
-{
- std::list<RoutingTableEntry>::iterator it = std::find_if(m_rteList.begin(),
- m_rteList.end(),
- bind(&rteCompare, _1, rte.getDestination()));
- if (it == m_rteList.end())
- {
- m_rteList.push_back(rte);
+ // Ensure that this is a new entry
+ if (rtpeItr == m_rteList.end()) {
+ // Adding a new routing entry to the NPT entry
+ rtpePtr->incrementUseCount();
+ m_rteList.push_back(rtpePtr);
}
- else
- {
- (*it).getNexthopList().reset(); // reseting existing routing table's next hop
- for (std::set<NextHop, NextHopComparator>::iterator nhit =
- rte.getNexthopList().getNextHops().begin();
- nhit != rte.getNexthopList().getNextHops().end(); ++nhit) {
- (*it).getNexthopList().addNextHop((*nhit));
- }
- }
+ // Note: we don't need to update in the else case because these are
+ // pointers, and they are centrally-located in the NPT and will all
+ // be updated there.
}
void
NamePrefixTableEntry::writeLog()
{
_LOG_DEBUG("Name: " << m_namePrefix);
- for (std::list<RoutingTableEntry>::iterator it = m_rteList.begin();
- it != m_rteList.end(); ++it) {
- _LOG_DEBUG("Destination: " << (*it).getDestination());
+ for (auto it = m_rteList.begin(); it != m_rteList.end(); ++it) {
+ _LOG_DEBUG("Destination: " << (*it)->getDestination());
_LOG_DEBUG("Nexthops: ");
- (*it).getNexthopList().writeLog();
+ (*it)->getNexthopList().writeLog();
}
m_nexthopList.writeLog();
}
+bool
+operator==(const NamePrefixTableEntry& lhs, const NamePrefixTableEntry& rhs)
+{
+ return (lhs.getNamePrefix() == rhs.getNamePrefix());
+}
+
+bool
+operator==(const NamePrefixTableEntry& lhs, const ndn::Name& rhs)
+{
+ return (lhs.getNamePrefix() == rhs);
+}
+
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";
+ for (const shared_ptr<RoutingTablePoolEntry> rtpePtr : entry.getRteList()) {
+ os << "Destination: " << rtpePtr->getDestination() << "\n";
}
return os;
diff --git a/src/route/name-prefix-table-entry.hpp b/src/route/name-prefix-table-entry.hpp
index ddae8ce..bb9c383 100644
--- a/src/route/name-prefix-table-entry.hpp
+++ b/src/route/name-prefix-table-entry.hpp
@@ -22,7 +22,9 @@
#ifndef NLSR_NAME_PREFIX_TABLE_ENTRY_HPP
#define NLSR_NAME_PREFIX_TABLE_ENTRY_HPP
-#include "routing-table-entry.hpp"
+#include "routing-table-pool-entry.hpp"
+
+#include "test-access-control.hpp"
#include <list>
#include <utility>
@@ -48,7 +50,7 @@
return m_namePrefix;
}
- const std::list<RoutingTableEntry>&
+ const std::list<std::shared_ptr<RoutingTablePoolEntry>>&
getRteList() const
{
return m_rteList;
@@ -58,9 +60,8 @@
resetRteListNextHop()
{
if (m_rteList.size() > 0) {
- for (std::list<RoutingTableEntry>::iterator it = m_rteList.begin();
- it != m_rteList.end(); ++it) {
- (*it).getNexthopList().reset();
+ for (auto it = m_rteList.begin(); it != m_rteList.end(); ++it) {
+ (*it)->getNexthopList().reset();
}
}
}
@@ -81,28 +82,41 @@
void
generateNhlfromRteList();
- void
- removeRoutingTableEntry(RoutingTableEntry& rte);
+ /*! \brief Removes a routing entry from this NPT entry.
+ \param rtpePtr The routing entry
+ \return The remaining number of other NPTs using the removed routing entry.
+ */
+ uint64_t
+ removeRoutingTableEntry(std::shared_ptr<RoutingTablePoolEntry> rtpePtr);
- /*! \brief Adds a routing table entry to this object's list.
- \param rte The routing table entry.
+ /*! \brief Adds a routing entry to this NPT entry.
+ \param rtpePtr The routing entry.
- Adds a routing table entry to this NPT entry's list. (reminder:
- each RTE has a next-hop list) They are used to calculate this
- entry's next-hop list.
+ Adds a routing table pool entry to this NPT entry's list
+ (reminder: each RTPE has a next-hop list). They are used to
+ calculate this entry's overall next-hop list.
*/
void
- addRoutingTableEntry(RoutingTableEntry& rte);
+ addRoutingTableEntry(std::shared_ptr<RoutingTablePoolEntry> rtpePtr);
void
writeLog();
private:
ndn::Name m_namePrefix;
- std::list<RoutingTableEntry> m_rteList;
+
+PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+ std::list<std::shared_ptr<RoutingTablePoolEntry>> m_rteList;
NexthopList m_nexthopList;
+
};
+bool
+operator==(const NamePrefixTableEntry& lhs, const NamePrefixTableEntry& rhs);
+
+bool
+operator==(const NamePrefixTableEntry& lhs, const ndn::Name& rhs);
+
std::ostream&
operator<<(std::ostream& os, const NamePrefixTableEntry& entry);
diff --git a/src/route/name-prefix-table.cpp b/src/route/name-prefix-table.cpp
index 5c18b77..e743276 100644
--- a/src/route/name-prefix-table.cpp
+++ b/src/route/name-prefix-table.cpp
@@ -33,112 +33,90 @@
INIT_LOGGER("NamePrefixTable");
-static bool
+bool
npteCompare(NamePrefixTableEntry& npte, const ndn::Name& name)
{
return npte.getNamePrefix() == name;
}
void
-NamePrefixTable::addEntry(const ndn::Name& name, RoutingTableEntry& rte)
-{
- // Check if the advertised name prefix is in the table already.
- NptEntryList::iterator it = std::find_if(m_table.begin(),
- m_table.end(),
- bind(&npteCompare, _1, name));
- // If not, create a new entry and add it.
- if (it == m_table.end()) {
- _LOG_TRACE("Adding origin: " << rte.getDestination() << " to new name prefix: " << name);
-
- NamePrefixTableEntry entry(name);
- entry.addRoutingTableEntry(rte); // Add this RTE to this new NPT entry.
- entry.generateNhlfromRteList(); // Generate a list of next-hops from the RTE.
-
- m_table.push_back(entry); // Add the new, completed entry into the main table.
-
- // If the RTE we added has any next hops, we inform the FIB of this.
- if (rte.getNexthopList().getSize() > 0) {
- _LOG_TRACE("Updating FIB with next hops for " << entry);
- m_nlsr.getFib().update(name, entry.getNexthopList());
- }
- }
- else {
- _LOG_TRACE("Adding origin: " << rte.getDestination() << " to existing prefix: " << *it);
- // Update the existing entry with the new RTE.
- it->addRoutingTableEntry(rte);
-
- it->generateNhlfromRteList();
-
- // As above, inform the FIB of this fact.
- // We may possibly have a new best next-hop for this name prefix
- // So this is a necessary step.
- if (it->getNexthopList().getSize() > 0) {
- _LOG_TRACE("Updating FIB with next hops for " << *it);
- m_nlsr.getFib().update(name, it->getNexthopList());
- }
- else {
- // 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);
- }
- }
-}
-
-void
-NamePrefixTable::removeEntry(const ndn::Name& name, RoutingTableEntry& rte)
-{
- NptEntryList::iterator it = std::find_if(m_table.begin(),
- m_table.end(),
- bind(&npteCompare, _1, name));
- if (it != m_table.end()) {
- _LOG_TRACE("Removing origin: " << rte.getDestination() << " from prefix: " << *it);
-
- it->removeRoutingTableEntry(rte);
-
- // 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 {
- _LOG_TRACE(*it << " has other routing table entries; updating FIB with next hops");
- it->generateNhlfromRteList();
-
- m_nlsr.getFib().update(name, it->getNexthopList());
- }
- }
-}
-
-void
NamePrefixTable::addEntry(const ndn::Name& name, const ndn::Name& destRouter)
{
- _LOG_DEBUG("Adding origin: " << destRouter << " to " << name);
- RoutingTableEntry* rteCheck = m_nlsr.getRoutingTable().findRoutingTableEntry(destRouter);
+ // Check if the advertised name prefix is in the table already.
+ NptEntryList::iterator nameItr = std::find(m_table.begin(),
+ m_table.end(),
+ name);
- if (rteCheck != nullptr) {
- addEntry(name, *rteCheck);
+ // Attempt to find a routing table pool entry (RTPE) we can use.
+ RtpEntryMap::iterator rtpeItr = m_rtpool.find(destRouter);
+
+ // These declarations just to make the compiler happy...
+ RoutingTablePoolEntry rtpe;
+ std::shared_ptr<RoutingTablePoolEntry> rtpePtr(nullptr);
+
+ // There isn't currently a routing table entry in the pool for this name
+ if (rtpeItr == m_rtpool.end()) {
+ // See if there is a routing table entry available we could use
+ RoutingTableEntry* routeEntryPtr = m_nlsr.getRoutingTable()
+ .findRoutingTableEntry(destRouter);
+
+ // We have to create a new routing table entry
+ if (routeEntryPtr == nullptr) {
+ rtpe = RoutingTablePoolEntry(destRouter, 0);
+ }
+ // There was already a usable one in the routing table
+ else {
+ rtpe = RoutingTablePoolEntry(*routeEntryPtr, 0);
+ }
+
+ // Add the new pool object to the pool.
+ rtpePtr = addRtpeToPool(rtpe);
+ }
+ // There was one already, so just fetch that one.
+ else {
+ rtpePtr = (*rtpeItr).second;
+ }
+
+ // Either we have to make a new NPT entry or there already was one.
+ if (nameItr == m_table.end()) {
+ _LOG_DEBUG("Adding origin: " << rtpePtr->getDestination()
+ << " to a new name prefix: " << name);
+ NamePrefixTableEntry npte(name);
+ npte.addRoutingTableEntry(rtpePtr);
+ npte.generateNhlfromRteList();
+ m_table.push_back(npte);
+
+ // If this entry has next hops, we need to inform the FIB
+ if (npte.getNexthopList().getSize() > 0) {
+ _LOG_TRACE("Updating FIB with next hops for " << npte);
+ m_nlsr.getFib().update(name, npte.getNexthopList());
+ }
+ // 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.
+ else {
+ _LOG_TRACE(npte << " has no next hops; removing from FIB");
+ m_nlsr.getFib().remove(name);
+ }
}
else {
- RoutingTableEntry rte(destRouter);
- addEntry(name, rte);
+ _LOG_TRACE("Adding origin: " << rtpePtr->getDestination()
+ << " to existing prefix: " << *nameItr);
+ nameItr->addRoutingTableEntry(rtpePtr);
+ nameItr->generateNhlfromRteList();
+
+ if (nameItr->getNexthopList().getSize() > 0) {
+ _LOG_TRACE("Updating FIB with next hops for " << (*nameItr));
+ m_nlsr.getFib().update(name, nameItr->getNexthopList());
+ }
+ else {
+ _LOG_TRACE((*nameItr) << " has no next hops; removing from FIB");
+ m_nlsr.getFib().remove(name);
+ }
}
}
@@ -147,14 +125,64 @@
{
_LOG_DEBUG("Removing origin: " << destRouter << " from " << name);
- RoutingTableEntry* rteCheck = m_nlsr.getRoutingTable().findRoutingTableEntry(destRouter);
+ // Fetch an iterator to the appropriate pair object in the pool.
+ RtpEntryMap::iterator rtpeItr = m_rtpool.find(destRouter);
- if (rteCheck != nullptr) {
- removeEntry(name, *rteCheck);
+ // Simple error checking to prevent any unusual behavior in the case
+ // that we try to remove an entry that isn't there.
+ if (rtpeItr == m_rtpool.end()) {
+ _LOG_DEBUG("No entry for origin: " << destRouter
+ << " found, so it cannot be removed from prefix: "
+ << name);
+ return;
+ }
+ std::shared_ptr<RoutingTablePoolEntry> rtpePtr = rtpeItr->second;
+
+ // Ensure that the entry exists
+ NptEntryList::iterator nameItr = std::find_if(m_table.begin(),
+ m_table.end(),
+ bind(&npteCompare, _1, name));
+ if (nameItr != m_table.end()) {
+ _LOG_TRACE("Removing origin: " << rtpePtr->getDestination()
+ << " from prefix: " << *nameItr);
+
+ // Rather than iterating through the whole list periodically, just
+ // delete them here if they have no references.
+ if ((*nameItr).removeRoutingTableEntry(rtpePtr) == 0) {
+ deleteRtpeFromPool(rtpePtr);
+ }
+
+ // 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 ((*nameItr).getRteListSize() == 0) {
+ _LOG_TRACE(*nameItr << " has no routing table entries;"
+ << " removing from table and FIB");
+ m_table.erase(nameItr);
+ m_nlsr.getFib().remove(name);
+ }
+ else {
+ _LOG_TRACE(*nameItr << " has other routing table entries;"
+ << " updating FIB with next hops");
+ (*nameItr).generateNhlfromRteList();
+ m_nlsr.getFib().update(name, (*nameItr).getNexthopList());
+ }
}
else {
- RoutingTableEntry rte(destRouter);
- removeEntry(name, rte);
+ _LOG_DEBUG("Attempted to remove origin: " << rtpePtr->getDestination()
+ << " from non-existant prefix: " << name);
}
}
@@ -163,29 +191,60 @@
{
_LOG_DEBUG("Updating table with newly calculated routes");
- // Update each name prefix entry in the Name Prefix Table with newly calculated next hops
- // For each entry in the NPT
- for (const NamePrefixTableEntry& prefixEntry : m_table) {
- // For each routing table entry
- for (const RoutingTableEntry& routingEntry : prefixEntry.getRteList()) {
- _LOG_TRACE("Updating next hops to origin: " << routingEntry.getDestination()
- << " for prefix: " << prefixEntry);
-
+ // Update each name prefix table entry in the NPT with the
+ // newly calculated next hops.
+ for (auto&& npte : m_table) {
+ // For each routing table pool entry in this NPT entry.
+ for (auto&& rtpe : npte.getRteList()) {
+ _LOG_TRACE("Updating next hops to origin: " << rtpe->getDestination()
+ << " for prefix: " << npte);
RoutingTableEntry* rteCheck =
- m_nlsr.getRoutingTable().findRoutingTableEntry(routingEntry.getDestination());
+ m_nlsr.getRoutingTable().findRoutingTableEntry(rtpe->getDestination());
// If there is a routing table entry for this prefix, update the NPT with it.
if (rteCheck != nullptr) {
- addEntry(prefixEntry.getNamePrefix(), *rteCheck);
+ rtpe->setNexthopList(rteCheck->getNexthopList());
}
else {
- RoutingTableEntry rte(routingEntry.getDestination());
- addEntry(prefixEntry.getNamePrefix(), rte);
+ rtpe->getNexthopList().reset();
}
+ addEntry(npte.getNamePrefix(), rtpe->getDestination());
}
}
}
+ // Inserts the routing table pool entry into the NPT's RTE storage
+ // pool. This cannot fail, so the pool is guaranteed to contain the
+ // item after this occurs.
+std::shared_ptr<RoutingTablePoolEntry>
+NamePrefixTable::addRtpeToPool(RoutingTablePoolEntry& rtpe)
+{
+ RtpEntryMap::iterator poolItr =
+ m_rtpool.insert(std::make_pair(rtpe.getDestination(),
+ std::make_shared<RoutingTablePoolEntry>
+ (rtpe)))
+ .first;
+ //| There's gotta be a more efficient way to do this
+ //std::shared_ptr<RoutingTablePoolEntry> poolPtr = &(poolItr->second);
+ return poolItr->second;
+}
+
+ // Removes the routing table pool entry from the storage pool. The
+ // postconditions of this function are guaranteed to include that
+ // the storage pool does not contain such an item. Additionally,
+ // this function cannot fail, but nonetheless debug information is
+ // given in the case that this function is called with an entry that
+ // isn't in the pool.
+void
+NamePrefixTable::deleteRtpeFromPool(std::shared_ptr<RoutingTablePoolEntry> rtpePtr)
+{
+ if (m_rtpool.erase(rtpePtr->getDestination()) != 1) {
+ _LOG_DEBUG("Attempted to delete non-existant origin: "
+ << rtpePtr->getDestination()
+ << " from NPT routing table entry storage pool.");
+ }
+}
+
void
NamePrefixTable::writeLog()
{
diff --git a/src/route/name-prefix-table.hpp b/src/route/name-prefix-table.hpp
index d8a3bc1..3443d7e 100644
--- a/src/route/name-prefix-table.hpp
+++ b/src/route/name-prefix-table.hpp
@@ -23,9 +23,12 @@
#define NLSR_NAME_PREFIX_TABLE_HPP
#include "name-prefix-table-entry.hpp"
-#include "routing-table-entry.hpp"
+#include "routing-table-pool-entry.hpp"
+
+#include "test-access-control.hpp"
#include <list>
+#include <unordered_map>
namespace nlsr {
class Nlsr;
@@ -37,34 +40,78 @@
typedef std::list<NamePrefixTableEntry> NptEntryList;
typedef NptEntryList::const_iterator const_iterator;
+ typedef std::unordered_map<ndn::Name, std::shared_ptr<RoutingTablePoolEntry>>
+ RtpEntryMap;
+
NamePrefixTable(Nlsr& nlsr)
: m_nlsr(nlsr)
{
}
- /*! \brief Adds an entry to the NPT.
- \param name The name prefix that is being advertised.
- \param destRouter The destination router that is advertising the prefix.
+ /*! \brief Adds a destination to the specified name prefix.
+ \param name The name prefix
+ \param destRouter The destination router prefix
- Adds a destination router to the name prefix. If there isn't
- currently an entry present for the prefix, one is made and
- added. If there is no routing table entry available for the
- destination router, a placeholder routing table entry without next
- hops will be made. Since this function can be called when a
- routing table entry has been updated to have no hops (i.e. is
- unreachable), this function will check for the number of next hops
- an entry has. If it is found to have no next hops, the NPT will
- inform the FIB to remove that prefix.
- */
+ This method adds a router to a name prefix table entry. If the
+ name prefix table entry does not exist, it is created. The method
+ will first look through its local pool of cached entries to find
+ the routing information for destRouter. If it is not found there,
+ it will construct one and fill it with information from an
+ appropriate RoutingTableEntry in the routing table. If there isn't
+ a match, it will instantiate it with no next hops. The FIB will be
+ notified of the change to the NPT entry, too.
+ */
void
addEntry(const ndn::Name& name, const ndn::Name& destRouter);
+ /*! \brief Removes a destination from a name prefix table entry.
+ \param name The name prefix
+ \param destRouter The destination.
+
+ This method removes a destination from an entry. It will not fail
+ if an invalid name/destination pair are passed. After removal, if
+ the RoutingTablePoolEntry has a use count of 0, it is deleted from
+ the table. Additionally, if the name prefix has no routing table
+ entries associated with it, it is deleted from the NPT. In any
+ case, the FIB is informed of the changes.
+ */
void
removeEntry(const ndn::Name& name, const ndn::Name& destRouter);
+ /*! \brief Updates all routing information in the NPT.
+
+ Naively iterates over all the NPT entries, then over each of their
+ RoutingTablePoolEntries, passing the name/destination pair back to
+ addEntry after updating the pool entry with new information. This
+ ensures that the FIB is appropriately apprised of any changes to a
+ prefix's preferred next hops.
+ */
void
updateWithNewRoute();
+ /*! \brief Adds a pool entry to the pool.
+ \param rtpe The entry.
+
+ \return A shared_ptr to the entry, now in the pool.
+
+ Adds a RoutingTablePoolEntry to the NPT's local pool. Shared
+ pointers are used because it eliminates complicated hacks to deal
+ with lifetime issues, and to simplify memory management.
+ */
+ std::shared_ptr<RoutingTablePoolEntry>
+ addRtpeToPool(RoutingTablePoolEntry& rtpe);
+
+ /*! \brief Removes a pool entry from the pool.
+ \param rtpePtr The shared_ptr to the entry.
+
+ Removes a pool entry from the pool. Comparing these shared_ptrs
+ should not be a problem, because the same pointer is moved around,
+ all sourced from this central location. A more robust solution is
+ certainly possible, though.
+ */
+ void
+ deleteRtpeFromPool(std::shared_ptr<RoutingTablePoolEntry> rtpePtr);
+
void
writeLog();
@@ -74,21 +121,13 @@
const_iterator
end() const;
-private:
- /*! \brief Adds an entry to the NPT table.
- \param name The name prefix to add to the table.
- \param rte The routing table entry with the next hop information to
- reach the prefix.
- */
- void
- addEntry(const ndn::Name& name, RoutingTableEntry& rte);
-
- void
- removeEntry(const ndn::Name& name, RoutingTableEntry& rte);
+PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+ RtpEntryMap m_rtpool;
+ NptEntryList m_table;
private:
Nlsr& m_nlsr;
- std::list<NamePrefixTableEntry> m_table;
+
};
inline NamePrefixTable::const_iterator
@@ -103,6 +142,9 @@
return m_table.end();
}
+bool
+npteCompare(NamePrefixTableEntry& npte, const ndn::Name& name);
+
std::ostream&
operator<<(std::ostream& os, const NamePrefixTable& table);
diff --git a/src/route/nexthop-list.cpp b/src/route/nexthop-list.cpp
index 22046fd..c5010ec 100644
--- a/src/route/nexthop-list.cpp
+++ b/src/route/nexthop-list.cpp
@@ -43,6 +43,39 @@
nh1.getRouteCostAsAdjustedInteger() == nh2.getRouteCostAsAdjustedInteger()) ;
}
+bool
+operator==(const NexthopList& lhs, const NexthopList& rhs)
+{
+ if (lhs.getSize() != rhs.getSize()) {
+ return false;
+ }
+
+ NexthopList slhs = lhs;
+ NexthopList srhs = rhs;
+
+ for (struct {std::set<NextHop>::iterator lItr;
+ std::set<NextHop>::iterator rItr;} pair = {slhs.begin(), srhs.begin()};
+ (pair.lItr != slhs.end() || pair.rItr != srhs.end());
+ pair.rItr++, pair.lItr++) {
+ if (!((*pair.lItr) == (*pair.rItr))) {
+ return false;
+ }
+ }
+ return true;
+}
+
+std::ostream&
+operator<<(std::ostream& os, const NexthopList& nhl)
+{
+ NexthopList& ucnhl = const_cast<NexthopList&>(nhl);
+ os << "NexthopList(\nNext hops: ";
+ for (auto&& nh : ucnhl.getNextHops()) {
+ os << nh;
+ }
+ os << ")";
+ return os;
+}
+
void
NexthopList::addNextHop(const NextHop& nh)
{
diff --git a/src/route/nexthop-list.hpp b/src/route/nexthop-list.hpp
index 77bd4e7..2f7c6f4 100644
--- a/src/route/nexthop-list.hpp
+++ b/src/route/nexthop-list.hpp
@@ -60,9 +60,9 @@
/*! \brief Adds a next hop to the list.
\param nh The next hop.
- Add next hop to the Next Hop list If next hop is new it is added
- If next hop already exists in next hop list then updates the route
- cost with new next hop's route cost
+ Adds a next hop to this object. If the next hop is new it is
+ added. If the next hop already exists in the list then that next
+ hop's route cost is updated.
*/
void
addNextHop(const NextHop& nh);
@@ -72,7 +72,6 @@
The next hop gets removed only if both next hop face and route cost are same.
*/
-
void
removeNextHop(const NextHop& nh);
@@ -82,6 +81,12 @@
return m_nexthopList.size();
}
+ size_t
+ getSize() const
+ {
+ return m_nexthopList.size();
+ }
+
void
reset()
{
@@ -128,6 +133,15 @@
std::set<NextHop, NextHopComparator> m_nexthopList;
};
+bool
+operator==(NexthopList& lhs, NexthopList& rhs);
+
+bool
+operator==(const NexthopList& lhs, const NexthopList& rhs);
+
+std::ostream&
+operator<<(std::ostream& os, const NexthopList& nhl);
+
} // namespace nlsr
#endif //NLSR_NEXTHOP_LIST_HPP
diff --git a/src/route/nexthop.cpp b/src/route/nexthop.cpp
index 0274b9d..8de2f27 100644
--- a/src/route/nexthop.cpp
+++ b/src/route/nexthop.cpp
@@ -24,6 +24,14 @@
namespace nlsr {
+bool
+operator==(const NextHop& lhs, const NextHop& rhs)
+{
+ return ((lhs.getRouteCostAsAdjustedInteger() == rhs.getRouteCostAsAdjustedInteger())
+ &&
+ (lhs.getConnectingFaceUri() == rhs.getConnectingFaceUri()));
+}
+
std::ostream&
operator<<(std::ostream& os, const NextHop& hop)
{
diff --git a/src/route/nexthop.hpp b/src/route/nexthop.hpp
index 0aa5640..265b151 100644
--- a/src/route/nexthop.hpp
+++ b/src/route/nexthop.hpp
@@ -113,6 +113,9 @@
static const uint64_t HYPERBOLIC_COST_ADJUSTMENT_FACTOR = 1000;
};
+bool
+operator==(const NextHop& lhs, const NextHop& rhs);
+
std::ostream&
operator<<(std::ostream& os, const NextHop& hop);
diff --git a/src/route/routing-table-entry.cpp b/src/route/routing-table-entry.cpp
new file mode 100644
index 0000000..8a35c5e
--- /dev/null
+++ b/src/route/routing-table-entry.cpp
@@ -0,0 +1,36 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2016, The University of Memphis,
+ * Regents of the University of California
+ *
+ * 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 "routing-table-entry.hpp"
+#include "nexthop-list.hpp"
+
+namespace nlsr {
+
+std::ostream&
+operator<<(std::ostream& os, const RoutingTableEntry& rte)
+{
+ os << "RoutingTableEntry("
+ << "Destination: " << rte.getDestination()
+ << "Next hop list: " << rte.getNexthopList() << ")";
+
+ return os;
+}
+
+} // namespace nlsr
diff --git a/src/route/routing-table-entry.hpp b/src/route/routing-table-entry.hpp
index 626caf3..c8e1304 100644
--- a/src/route/routing-table-entry.hpp
+++ b/src/route/routing-table-entry.hpp
@@ -57,11 +57,28 @@
return m_nexthopList;
}
-private:
+ const NexthopList&
+ getNexthopList() const
+ {
+ return m_nexthopList;
+ }
+
+ inline bool
+ operator==(RoutingTableEntry& rhs)
+ {
+ return ((*this).getDestination() == rhs.getDestination()
+ &&
+ (*this).getNexthopList() == rhs.getNexthopList());
+ }
+
+protected:
ndn::Name m_destination;
NexthopList m_nexthopList;
};
+std::ostream&
+operator<<(std::ostream& os, const RoutingTableEntry& rte);
+
} // namespace nlsr
#endif //NLSR_ROUTING_TABLE_ENTRY_HPP
diff --git a/src/route/routing-table-pool-entry.cpp b/src/route/routing-table-pool-entry.cpp
new file mode 100644
index 0000000..dd6b07b
--- /dev/null
+++ b/src/route/routing-table-pool-entry.cpp
@@ -0,0 +1,46 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2016, The University of Memphis,
+ * Regents of the University of California
+ *
+ * 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 "routing-table-pool-entry.hpp"
+
+namespace nlsr {
+
+std::ostream&
+operator<<(std::ostream& os, RoutingTablePoolEntry& rtpe)
+{
+ os << "RoutingTablePoolEntry("
+ << "Destination router: " << rtpe.getDestination()
+ << "Next hop list: ";
+ for (auto && nh : rtpe.getNexthopList()) {
+ os << nh;
+ }
+
+ return os;
+}
+
+bool
+operator==(const RoutingTablePoolEntry& lhs, const RoutingTablePoolEntry& rhs)
+{
+ return (lhs.getDestination() == rhs.getDestination()
+ &&
+ lhs.getNexthopList() == rhs.getNexthopList());
+}
+
+} // namespace nlsr
diff --git a/src/route/routing-table-pool-entry.hpp b/src/route/routing-table-pool-entry.hpp
new file mode 100644
index 0000000..c81daef
--- /dev/null
+++ b/src/route/routing-table-pool-entry.hpp
@@ -0,0 +1,103 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2016, The University of Memphis,
+ * Regents of the University of California
+ *
+ * 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/>.
+ *
+ * \author Nicholas Gordon <nmgordon@memphis.edu>
+ *
+ **/
+
+#ifndef NLSR_ROUTING_TABLE_POOL_ENTRY_HPP
+#define NLSR_ROUTING_TABLE_POOL_ENTRY_HPP
+
+#include <iostream>
+#include <ndn-cxx/name.hpp>
+#include "nexthop-list.hpp"
+#include "routing-table-entry.hpp"
+
+namespace nlsr {
+class RoutingTablePoolEntry : public RoutingTableEntry
+{
+public:
+ RoutingTablePoolEntry()
+ {
+ }
+
+ ~RoutingTablePoolEntry()
+ {
+ }
+
+ RoutingTablePoolEntry(const ndn::Name& dest)
+ {
+ m_destination = dest;
+ m_useCount = 1;
+ }
+
+ RoutingTablePoolEntry(RoutingTableEntry& rte, uint64_t useCount)
+ {
+ m_destination = rte.getDestination();
+ m_nexthopList = rte.getNexthopList();
+ m_useCount = useCount;
+ }
+
+ RoutingTablePoolEntry(const ndn::Name& dest, uint64_t useCount)
+ {
+ m_destination = dest;
+ m_useCount = useCount;
+ }
+
+ uint64_t
+ getUseCount()
+ {
+ return m_useCount;
+ }
+
+ uint64_t
+ incrementUseCount()
+ {
+ return ++m_useCount;
+ }
+
+ uint64_t
+ decrementUseCount()
+ {
+ if (m_useCount != 0) {
+ return --m_useCount;
+ }
+ return 0;
+ }
+
+ void
+ setNexthopList(NexthopList nhl)
+ {
+ m_nexthopList = nhl;
+ }
+
+private:
+ uint64_t m_useCount;
+
+};
+
+bool
+operator==(const RoutingTablePoolEntry& lhs, const RoutingTablePoolEntry& rhs);
+
+std::ostream&
+operator<<(std::ostream& os, RoutingTablePoolEntry& rtpe);
+
+} // namespace nlsr
+
+#endif // NLSR_ROUTING_TABLE_POOL_ENTRY_HPP