routing: improved routing map data structure.
Change-Id: I1cde5b2b9cffcec5cbfd78c5dd4262b5fb919a73
refs: #4240
diff --git a/src/route/map-entry.hpp b/src/route/map-entry.hpp
index 84f3dd1..e4c998c 100644
--- a/src/route/map-entry.hpp
+++ b/src/route/map-entry.hpp
@@ -58,6 +58,9 @@
return m_mappingNumber;
}
+ void
+ reset();
+
private:
ndn::Name m_router;
int32_t m_mappingNumber;
diff --git a/src/route/map.cpp b/src/route/map.cpp
index 5596a05..d43e058 100644
--- a/src/route/map.cpp
+++ b/src/route/map.cpp
@@ -32,18 +32,6 @@
INIT_LOGGER("Map");
-static bool
-mapEntryCompareByRouter(MapEntry& mpe1, const ndn::Name& rtrName)
-{
- return mpe1.getRouter() == rtrName;
-}
-
-static bool
-mapEntryCompareByMappingNo(MapEntry& mpe1, int32_t mappingNo)
-{
- return mpe1.getMappingNumber() == mappingNo;
-}
-
void
Map::addEntry(const ndn::Name& rtrName)
{
@@ -56,48 +44,39 @@
bool
Map::addEntry(MapEntry& mpe)
{
- //cout << mpe;
- std::list<MapEntry>::iterator it = std::find_if(m_table.begin(),
- m_table.end(),
- std::bind(&mapEntryCompareByRouter,
- _1, mpe.getRouter()));
- if (it == m_table.end()) {
- m_table.push_back(mpe);
- return true;
- }
- return false;
+ return m_entries.insert(mpe).second;
}
-const ndn::Name
+ndn::optional<ndn::Name>
Map::getRouterNameByMappingNo(int32_t mn)
{
- std::list<MapEntry>::iterator it = std::find_if(m_table.begin(),
- m_table.end(),
- std::bind(&mapEntryCompareByMappingNo,
- _1, mn));
- if (it != m_table.end()) {
- return (*it).getRouter();
+ auto&& mappingNumberView = m_entries.get<detail::byMappingNumber>();
+ auto iterator = mappingNumberView.find(mn);
+ if (iterator == mappingNumberView.end()) {
+ return {};
}
- return ndn::Name();
+ else {
+ return {iterator->getRouter()};
+ }
}
-int32_t
+ndn::optional<int32_t>
Map::getMappingNoByRouterName(const ndn::Name& rName)
{
- std::list<MapEntry>::iterator it = std::find_if(m_table.begin(),
- m_table.end(),
- std::bind(&mapEntryCompareByRouter,
- _1, rName));
- if (it != m_table.end()) {
- return (*it).getMappingNumber();
+ auto&& routerNameView = m_entries.get<detail::byRouterName>();
+ auto iterator = routerNameView.find(rName);
+ if (iterator == routerNameView.end()) {
+ return {};
}
- return -1;
+ else {
+ return {iterator->getMappingNumber()};
+ }
}
void
Map::reset()
{
- m_table.clear();
+ m_entries = detail::entryContainer{};
m_mappingIndex = 0;
}
@@ -105,9 +84,10 @@
Map::writeLog()
{
_LOG_DEBUG("---------------Map----------------------");
- for (std::list<MapEntry>::iterator it = m_table.begin(); it != m_table.end() ; it++) {
- _LOG_DEBUG("MapEntry: ( Router: " << (*it).getRouter() << " Mapping No: "
- << (*it).getMappingNumber() << " )");
+ auto&& routerNameView = m_entries.get<detail::byRouterName>();
+ for (auto entry = routerNameView.begin(); entry != routerNameView.end(); entry++) {
+ _LOG_DEBUG("MapEntry: ( Router: " << entry->getRouter() << " Mapping No: "
+ << entry->getMappingNumber() << " )");
}
}
diff --git a/src/route/map.hpp b/src/route/map.hpp
index 262fe52..04cf0e4 100644
--- a/src/route/map.hpp
+++ b/src/route/map.hpp
@@ -28,8 +28,32 @@
#include <list>
#include <boost/cstdint.hpp>
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/mem_fun.hpp>
+#include <boost/multi_index/tag.hpp>
+
namespace nlsr {
+namespace detail {
+
+ using namespace boost::multi_index;
+ // Define tags so that we can search by different indices.
+ struct byRouterName {};
+ struct byMappingNumber{};
+ using entryContainer = multi_index_container<
+ MapEntry,
+ indexed_by<
+ hashed_unique<tag<byRouterName>,
+ const_mem_fun<MapEntry, const ndn::Name&, &MapEntry::getRouter>,
+ std::hash<ndn::Name>>,
+ hashed_unique<tag<byMappingNumber>,
+ const_mem_fun<MapEntry, int32_t, &MapEntry::getMappingNumber>>
+ >
+ >;
+
+} // namespace detail
+
class Nlsr;
class Map
@@ -80,25 +104,19 @@
}
}
- const ndn::Name
+ ndn::optional<ndn::Name>
getRouterNameByMappingNo(int32_t mn);
- int32_t
+ ndn::optional<int32_t>
getMappingNoByRouterName(const ndn::Name& rName);
void
reset();
- std::list<MapEntry>&
- getMapList()
- {
- return m_table;
- }
-
size_t
getMapSize() const
{
- return m_table.size();
+ return m_entries.size();
}
void
@@ -109,7 +127,7 @@
addEntry(MapEntry& mpe);
int32_t m_mappingIndex;
- std::list<MapEntry> m_table;
+ detail::entryContainer m_entries;
};
} // namespace nlsr
diff --git a/src/route/routing-table-calculator.cpp b/src/route/routing-table-calculator.cpp
index f4442f5..318ec64 100644
--- a/src/route/routing-table-calculator.cpp
+++ b/src/route/routing-table-calculator.cpp
@@ -18,6 +18,7 @@
* 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-calculator.hpp"
#include "lsdb.hpp"
#include "map.hpp"
@@ -62,19 +63,19 @@
for (std::list<AdjLsa>::iterator it = adjLsdb.begin(); it != adjLsdb.end() ; it++) {
- int32_t row = pMap.getMappingNoByRouterName((*it).getOrigRouter());
+ ndn::optional<int32_t> row = pMap.getMappingNoByRouterName((*it).getOrigRouter());
std::list<Adjacent> adl = (*it).getAdl().getAdjList();
// For each adjacency represented in the LSA
for (std::list<Adjacent>::iterator itAdl = adl.begin(); itAdl != adl.end() ; itAdl++) {
- int32_t col = pMap.getMappingNoByRouterName((*itAdl).getName());
+ ndn::optional<int32_t> col = pMap.getMappingNoByRouterName((*itAdl).getName());
double cost = (*itAdl).getLinkCost();
- if ((row >= 0 && row < static_cast<int32_t>(m_nRouters)) &&
- (col >= 0 && col < static_cast<int32_t>(m_nRouters)))
+ if (row && col && *row < static_cast<int32_t>(m_nRouters)
+ && *col < static_cast<int32_t>(m_nRouters))
{
- adjMatrix[row][col] = cost;
+ adjMatrix[*row][*col] = cost;
}
}
}
@@ -210,30 +211,32 @@
initMatrix();
makeAdjMatrix(pnlsr, pMap);
writeAdjMatrixLog();
- int sourceRouter = pMap.getMappingNoByRouterName(pnlsr.getConfParameter().getRouterPrefix());
+ ndn::optional<int32_t> sourceRouter =
+ pMap.getMappingNoByRouterName(pnlsr.getConfParameter().getRouterPrefix());
allocateParent(); // These two matrices are used in Dijkstra's algorithm.
allocateDistance(); //
- if (pnlsr.getConfParameter().getMaxFacesPerPrefix() == 1) {
+ // We only bother to do the calculation if we have a router by that name.
+ if (sourceRouter && pnlsr.getConfParameter().getMaxFacesPerPrefix() == 1) {
// In the single path case we can simply run Dijkstra's algorithm.
- doDijkstraPathCalculation(sourceRouter);
+ doDijkstraPathCalculation(*sourceRouter);
// Inform the routing table of the new next hops.
- addAllLsNextHopsToRoutingTable(pnlsr, rt, pMap, sourceRouter);
+ addAllLsNextHopsToRoutingTable(pnlsr, rt, pMap, *sourceRouter);
}
else {
// Multi Path
- setNoLink(getNumOfLinkfromAdjMatrix(sourceRouter));
+ setNoLink(getNumOfLinkfromAdjMatrix(*sourceRouter));
allocateLinks();
allocateLinkCosts();
// Gets a sparse listing of adjacencies for path calculation
- getLinksFromAdjMatrix(links, linkCosts, sourceRouter);
+ getLinksFromAdjMatrix(links, linkCosts, *sourceRouter);
for (int i = 0 ; i < vNoLink; i++) {
// Simulate that only the current neighbor is accessible
- adjustAdMatrix(sourceRouter, links[i], linkCosts[i]);
+ adjustAdMatrix(*sourceRouter, links[i], linkCosts[i]);
writeAdjMatrixLog();
// Do Dijkstra's algorithm using the current neighbor as your start.
- doDijkstraPathCalculation(sourceRouter);
+ doDijkstraPathCalculation(*sourceRouter);
// Update the routing table with the calculations.
- addAllLsNextHopsToRoutingTable(pnlsr, rt, pMap, sourceRouter);
+ addAllLsNextHopsToRoutingTable(pnlsr, rt, pMap, *sourceRouter);
}
freeLinks();
freeLinksCosts();
@@ -314,12 +317,15 @@
// Fetch its distance
double routeCost = m_distance[i];
// Fetch its actual name
- ndn::Name nextHopRouterName = pMap.getRouterNameByMappingNo(nextHopRouter);
- std::string nextHopFace =
- pnlsr.getAdjacencyList().getAdjacent(nextHopRouterName).getFaceUri().toString();
- // Add next hop to routing table
- NextHop nh(nextHopFace, routeCost);
- rt.addNextHop(pMap.getRouterNameByMappingNo(i), nh);
+ ndn::optional<ndn::Name> nextHopRouterName= pMap.getRouterNameByMappingNo(nextHopRouter);
+ if (nextHopRouterName) {
+ std::string nextHopFace =
+ pnlsr.getAdjacencyList().getAdjacent(*nextHopRouterName).getFaceUri().toString();
+ // Add next hop to routing table
+ NextHop nh(nextHopFace, routeCost);
+ rt.addNextHop(*(pMap.getRouterNameByMappingNo(i)), nh);
+
+ }
}
}
}
@@ -397,15 +403,13 @@
const double HyperbolicRoutingCalculator::UNKNOWN_DISTANCE = -1.0;
const double HyperbolicRoutingCalculator::UNKNOWN_RADIUS = -1.0;
-const int32_t HyperbolicRoutingCalculator::ROUTER_NOT_FOUND = -1.0;
-
void
HyperbolicRoutingCalculator::calculatePaths(Map& map, RoutingTable& rt,
Lsdb& lsdb, AdjacencyList& adjacencies)
{
_LOG_TRACE("Calculating hyperbolic paths");
- int thisRouter = map.getMappingNoByRouterName(m_thisRouterName);
+ ndn::optional<int32_t> thisRouter = map.getMappingNoByRouterName(m_thisRouterName);
// Iterate over directly connected neighbors
std::list<Adjacent> neighbors = adjacencies.getAdjList();
@@ -429,9 +433,9 @@
// Install nexthops for this router to the neighbor; direct neighbors have a 0 cost link
addNextHop(srcRouterName, srcFaceUri, 0, rt);
- int src = map.getMappingNoByRouterName(srcRouterName);
+ ndn::optional<int32_t> src = map.getMappingNoByRouterName(srcRouterName);
- if (src == ROUTER_NOT_FOUND) {
+ if (!src) {
_LOG_WARN(adj->getName() << " does not exist in the router map!");
continue;
}
@@ -439,20 +443,21 @@
// Get hyperbolic distance from direct neighbor to every other router
for (int dest = 0; dest < static_cast<int>(m_nRouters); ++dest) {
// Don't calculate nexthops to this router or from a router to itself
- if (dest != thisRouter && dest != src) {
+ if (thisRouter && dest != *thisRouter && dest != *src) {
- ndn::Name destRouterName = map.getRouterNameByMappingNo(dest);
+ ndn::optional<ndn::Name> destRouterName = map.getRouterNameByMappingNo(dest);
+ if (destRouterName) {
+ double distance = getHyperbolicDistance(map, lsdb, srcRouterName, *destRouterName);
- double distance = getHyperbolicDistance(map, lsdb, srcRouterName, destRouterName);
+ // Could not compute distance
+ if (distance == UNKNOWN_DISTANCE) {
+ _LOG_WARN("Could not calculate hyperbolic distance from " << srcRouterName << " to " <<
+ *destRouterName);
+ continue;
+ }
- // Could not compute distance
- if (distance == UNKNOWN_DISTANCE) {
- _LOG_WARN("Could not calculate hyperbolic distance from " << srcRouterName << " to " <<
- destRouterName);
- continue;
+ addNextHop(*destRouterName, srcFaceUri, distance, rt);
}
-
- addNextHop(destRouterName, srcFaceUri, distance, rt);
}
}
}
diff --git a/src/route/routing-table-calculator.hpp b/src/route/routing-table-calculator.hpp
index 6c6ab18..7158fd6 100644
--- a/src/route/routing-table-calculator.hpp
+++ b/src/route/routing-table-calculator.hpp
@@ -17,12 +17,13 @@
* 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_ROUTING_TABLE_CALCULATOR_HPP
#define NLSR_ROUTING_TABLE_CALCULATOR_HPP
+#include "common.hpp"
+
#include <list>
#include <iostream>
#include <boost/cstdint.hpp>
@@ -238,7 +239,6 @@
static const double MATH_PI;
static const double UNKNOWN_DISTANCE;
static const double UNKNOWN_RADIUS;
- static const int32_t ROUTER_NOT_FOUND;
};
} // namespace nlsr