route: Allow 0 cost in hyperbolic calculation
refs: #1982
Change-Id: I6ffe677d59dcb559f344b7d648600e9537d9c4f5
diff --git a/src/lsa.cpp b/src/lsa.cpp
index 9fa7421..99b69a8 100644
--- a/src/lsa.cpp
+++ b/src/lsa.cpp
@@ -204,7 +204,7 @@
_LOG_DEBUG(" Ls Seq No: " << m_lsSeqNo);
_LOG_DEBUG(" Ls Lifetime: " << m_expirationTimePoint);
_LOG_DEBUG(" Hyperbolic Radius: " << m_corRad);
- _LOG_DEBUG(" Hyperbolic Theta: " << m_corRad);
+ _LOG_DEBUG(" Hyperbolic Theta: " << m_corTheta);
}
AdjLsa::AdjLsa(const ndn::Name& origR, const string& lst, uint32_t lsn,
diff --git a/src/route/nexthop.cpp b/src/route/nexthop.cpp
new file mode 100644
index 0000000..b60e740
--- /dev/null
+++ b/src/route/nexthop.cpp
@@ -0,0 +1,37 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014 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 "nexthop.hpp"
+
+namespace nlsr {
+
+std::ostream&
+operator<<(std::ostream& os, const NextHop& hop)
+{
+ os << "Nexthop("
+ << "face-uri: " << hop.getConnectingFaceUri()
+ << ", cost: " << hop.getRouteCost() << ")";
+
+ return os;
+}
+
+}//namespace nlsr
diff --git a/src/route/nexthop.hpp b/src/route/nexthop.hpp
index a4feec2..26bebd5 100644
--- a/src/route/nexthop.hpp
+++ b/src/route/nexthop.hpp
@@ -79,6 +79,9 @@
static const uint64_t HYPERBOLIC_COST_ADJUSTMENT_FACTOR = 100;
};
+std::ostream&
+operator<<(std::ostream& os, const NextHop& hop);
+
}//namespace nlsr
#endif //NLSR_NEXTHOP_HPP
diff --git a/src/route/routing-table-calculator.cpp b/src/route/routing-table-calculator.cpp
index 00db7b7..dffe4a3 100644
--- a/src/route/routing-table-calculator.cpp
+++ b/src/route/routing-table-calculator.cpp
@@ -30,6 +30,8 @@
#include "nlsr.hpp"
#include "logger.hpp"
+#include <boost/math/constants/constants.hpp>
+
namespace nlsr {
INIT_LOGGER("RoutingTableCalculator");
@@ -38,17 +40,18 @@
void
RoutingTableCalculator::allocateAdjMatrix()
{
- adjMatrix = new double*[numOfRouter];
- for (int i = 0; i < numOfRouter; ++i) {
- adjMatrix[i] = new double[numOfRouter];
+ adjMatrix = new double*[m_nRouters];
+
+ for (size_t i = 0; i < m_nRouters; ++i) {
+ adjMatrix[i] = new double[m_nRouters];
}
}
void
RoutingTableCalculator::initMatrix()
{
- for (int i = 0; i < numOfRouter; i++) {
- for (int j = 0; j < numOfRouter; j++) {
+ for (size_t i = 0; i < m_nRouters; i++) {
+ for (size_t j = 0; j < m_nRouters; j++) {
adjMatrix[i][j] = 0;
}
}
@@ -58,15 +61,19 @@
RoutingTableCalculator::makeAdjMatrix(Nlsr& pnlsr, Map pMap)
{
std::list<AdjLsa> adjLsdb = pnlsr.getLsdb().getAdjLsdb();
- for (std::list<AdjLsa>::iterator it = adjLsdb.begin();
- it != adjLsdb.end() ; it++) {
- int row = pMap.getMappingNoByRouterName((*it).getOrigRouter());
+ for (std::list<AdjLsa>::iterator it = adjLsdb.begin(); it != adjLsdb.end() ; it++) {
+
+ int32_t row = pMap.getMappingNoByRouterName((*it).getOrigRouter());
+
std::list<Adjacent> adl = (*it).getAdl().getAdjList();
- for (std::list<Adjacent>::iterator itAdl = adl.begin();
- itAdl != adl.end() ; itAdl++) {
- int col = pMap.getMappingNoByRouterName((*itAdl).getName());
+ for (std::list<Adjacent>::iterator itAdl = adl.begin(); itAdl != adl.end() ; itAdl++) {
+
+ int32_t col = pMap.getMappingNoByRouterName((*itAdl).getName());
double cost = (*itAdl).getLinkCost();
- if ((row >= 0 && row < numOfRouter) && (col >= 0 && col < numOfRouter)) {
+
+ if ((row >= 0 && row < static_cast<int32_t>(m_nRouters)) &&
+ (col >= 0 && col < static_cast<int32_t>(m_nRouters)))
+ {
adjMatrix[row][col] = cost;
}
}
@@ -76,9 +83,9 @@
void
RoutingTableCalculator::writeAdjMatrixLog()
{
- for (int i = 0; i < numOfRouter; i++) {
+ for (size_t i = 0; i < m_nRouters; i++) {
string line="";
- for (int j = 0; j < numOfRouter; j++) {
+ for (size_t j = 0; j < m_nRouters; j++) {
line += boost::lexical_cast<std::string>(adjMatrix[i][j]);
line += " ";
}
@@ -89,7 +96,7 @@
void
RoutingTableCalculator::adjustAdMatrix(int source, int link, double linkCost)
{
- for (int i = 0; i < numOfRouter; i++) {
+ for (int i = 0; i < static_cast<int>(m_nRouters); i++) {
if (i == link) {
adjMatrix[source][i] = linkCost;
}
@@ -103,7 +110,8 @@
RoutingTableCalculator::getNumOfLinkfromAdjMatrix(int sRouter)
{
int noLink = 0;
- for (int i = 0; i < numOfRouter; i++) {
+
+ for (size_t i = 0; i < m_nRouters; i++) {
if (adjMatrix[sRouter][i] > 0) {
noLink++;
}
@@ -116,7 +124,8 @@
double* linkCosts, int source)
{
int j = 0;
- for (int i = 0; i < numOfRouter; i++) {
+
+ for (size_t i = 0; i < m_nRouters; i++) {
if (adjMatrix[source][i] > 0) {
links[j] = i;
linkCosts[j] = adjMatrix[source][i];
@@ -128,7 +137,7 @@
void
RoutingTableCalculator::freeAdjMatrix()
{
- for (int i = 0; i < numOfRouter; ++i) {
+ for (size_t i = 0; i < m_nRouters; ++i) {
delete [] adjMatrix[i];
}
delete [] adjMatrix;
@@ -203,25 +212,25 @@
{
int i;
int v, u;
- int* Q = new int[numOfRouter];
+ int* Q = new int[m_nRouters];
int head = 0;
/* Initiate the Parent */
- for (i = 0 ; i < numOfRouter; i++) {
+ for (i = 0 ; i < static_cast<int>(m_nRouters); i++) {
m_parent[i] = EMPTY_PARENT;
m_distance[i] = INF_DISTANCE;
Q[i] = i;
}
if (sourceRouter != NO_MAPPING_NUM) {
m_distance[sourceRouter] = 0;
- sortQueueByDistance(Q, m_distance, head, numOfRouter);
- while (head < numOfRouter) {
+ sortQueueByDistance(Q, m_distance, head, m_nRouters);
+ while (head < static_cast<int>(m_nRouters)) {
u = Q[head];
if (m_distance[u] == INF_DISTANCE) {
break;
}
- for (v = 0 ; v < numOfRouter; v++) {
+ for (v = 0 ; v < static_cast<int>(m_nRouters); v++) {
if (adjMatrix[u][v] > 0) {
- if (isNotExplored(Q, v, head + 1, numOfRouter)) {
+ if (isNotExplored(Q, v, head + 1, m_nRouters)) {
if (m_distance[u] + adjMatrix[u][v] < m_distance[v]) {
m_distance[v] = m_distance[u] + adjMatrix[u][v] ;
m_parent[v] = u;
@@ -230,22 +239,27 @@
}
}
head++;
- sortQueueByDistance(Q, m_distance, head, numOfRouter);
+ sortQueueByDistance(Q, m_distance, head, m_nRouters);
}
}
delete [] Q;
}
void
-LinkStateRoutingTableCalculator::addAllLsNextHopsToRoutingTable(Nlsr& pnlsr,
- RoutingTable& rt, Map& pMap, int sourceRouter)
+LinkStateRoutingTableCalculator::addAllLsNextHopsToRoutingTable(Nlsr& pnlsr, RoutingTable& rt,
+ Map& pMap, uint32_t sourceRouter)
{
_LOG_DEBUG("LinkStateRoutingTableCalculator::addAllNextHopsToRoutingTable Called");
+
int nextHopRouter = 0;
- for (int i = 0; i < numOfRouter ; i++) {
+
+ for (size_t i = 0; i < m_nRouters ; i++) {
if (i != sourceRouter) {
+
nextHopRouter = getLsNextHop(i, sourceRouter);
+
if (nextHopRouter != NO_NEXT_HOP) {
+
double routeCost = m_distance[i];
ndn::Name nextHopRouterName = pMap.getRouterNameByMappingNo(nextHopRouter);
std::string nextHopFace =
@@ -305,13 +319,13 @@
void
LinkStateRoutingTableCalculator::allocateParent()
{
- m_parent = new int[numOfRouter];
+ m_parent = new int[m_nRouters];
}
void
LinkStateRoutingTableCalculator::allocateDistance()
{
- m_distance = new double[numOfRouter];
+ m_distance = new double[m_nRouters];
}
void
@@ -325,144 +339,137 @@
delete [] m_distance;
}
+const double HyperbolicRoutingCalculator::MATH_PI = boost::math::constants::pi<double>();
+const double HyperbolicRoutingCalculator::UNKNOWN_DISTANCE = -1.0;
+const double HyperbolicRoutingCalculator::UNKNOWN_RADIUS = -1.0;
+
+const int32_t HyperbolicRoutingCalculator::ROUTER_NOT_FOUND = -1.0;
void
-HypRoutingTableCalculator::calculatePath(Map& pMap,
- RoutingTable& rt, Nlsr& pnlsr)
+HyperbolicRoutingCalculator::calculatePaths(Map& map, RoutingTable& rt,
+ Lsdb& lsdb, AdjacencyList& adjacencies)
{
- allocateAdjMatrix();
- initMatrix();
- makeAdjMatrix(pnlsr, pMap);
- ndn::Name routerName = pnlsr.getConfParameter().getRouterPrefix();
- int sourceRouter = pMap.getMappingNoByRouterName(routerName);
- int noLink = getNumOfLinkfromAdjMatrix(sourceRouter);
- setNoLink(noLink);
- allocateLinks();
- allocateLinkCosts();
- getLinksFromAdjMatrix(links, linkCosts, sourceRouter);
- for (int i = 0 ; i < numOfRouter ; ++i) {
- int k = 0;
- if (i != sourceRouter) {
- allocateNexthopRouters();
- allocateDistanceToNeighbor();
- allocateDistFromNbrToDest();
- for (int j = 0; j < vNoLink; j++) {
- double distToNbr = getHyperbolicDistance(pnlsr, pMap,
- sourceRouter, links[j]);
- double distToDestFromNbr = getHyperbolicDistance(pnlsr,
- pMap, links[j], i);
- if (distToDestFromNbr >= 0) {
- m_nexthopRouters[k] = links[j];
- m_distanceToNeighbor[k] = distToNbr;
- m_distFromNbrToDest[k] = distToDestFromNbr;
- k++;
+ _LOG_TRACE("Calculating hyperbolic paths");
+
+ int thisRouter = map.getMappingNoByRouterName(m_thisRouterName);
+
+ // Iterate over directly connected neighbors
+ std::list<Adjacent> neighbors = adjacencies.getAdjList();
+ for (std::list<Adjacent>::iterator adj = neighbors.begin(); adj != neighbors.end(); ++adj) {
+
+ // Don't calculate nexthops using an inactive router
+ if (adj->getStatus() == Adjacent::STATUS_INACTIVE) {
+ _LOG_TRACE(adj->getName() << " is inactive; not using it as a nexthop");
+ continue;
+ }
+
+ ndn::Name srcRouterName = adj->getName();
+
+ // Don't calculate nexthops for this router to other routers
+ if (srcRouterName == m_thisRouterName) {
+ continue;
+ }
+
+ std::string srcFaceUri = adj->getConnectingFaceUri();
+
+ // 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);
+
+ if (src == ROUTER_NOT_FOUND) {
+ _LOG_WARN(adj->getName() << " does not exist in the router map!");
+ continue;
+ }
+
+ // 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) {
+
+ ndn::Name destRouterName = map.getRouterNameByMappingNo(dest);
+
+ 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;
}
- }
- addHypNextHopsToRoutingTable(pnlsr, pMap, rt, k, i);
- freeNexthopRouters();
- freeDistanceToNeighbor();
- freeDistFromNbrToDest();
- }
- }
- freeLinks();
- freeLinksCosts();
- freeAdjMatrix();
-}
-void
-HypRoutingTableCalculator::addHypNextHopsToRoutingTable(Nlsr& pnlsr, Map& pMap,
- RoutingTable& rt, int noFaces, int dest)
-{
- ndn::Name destRouter = pMap.getRouterNameByMappingNo(dest);
- for (int i = 0 ; i < noFaces ; ++i) {
- ndn::Name nextHopRouterName = pMap.getRouterNameByMappingNo(m_nexthopRouters[i]);
- std::string nextHopFaceUri =
- pnlsr.getAdjacencyList().getAdjacent(nextHopRouterName).getConnectingFaceUri();
- NextHop nh(nextHopFaceUri, m_distFromNbrToDest[i]);
- if (m_isDryRun) {
- rt.addNextHopToDryTable(destRouter, nh);
- }
- else {
- rt.addNextHop(destRouter, nh);
+ addNextHop(destRouterName, srcFaceUri, distance, rt);
+ }
}
}
}
double
-HypRoutingTableCalculator::getHyperbolicDistance(Nlsr& pnlsr,
- Map& pMap, int src, int dest)
+HyperbolicRoutingCalculator::getHyperbolicDistance(Map& map, Lsdb& lsdb,
+ ndn::Name src, ndn::Name dest)
{
- double distance = 0.0;
- ndn::Name srcRouterKey = pMap.getRouterNameByMappingNo(src);
- srcRouterKey.append("coordinate");
- ndn::Name destRouterKey = pMap.getRouterNameByMappingNo(dest);
- destRouterKey.append("coordinate");
- CoordinateLsa* srcLsa = pnlsr.getLsdb().findCoordinateLsa(srcRouterKey);
- CoordinateLsa* destLsa = pnlsr.getLsdb().findCoordinateLsa(destRouterKey);
+ _LOG_TRACE("Calculating hyperbolic distance from " << src << " to " << dest);
- if ((srcLsa == 0) || (destLsa == 0)) {
- return -1;
+ double distance = UNKNOWN_DISTANCE;
+
+ ndn::Name srcLsaKey = src;
+ srcLsaKey.append("coordinate");
+
+ CoordinateLsa* srcLsa = lsdb.findCoordinateLsa(srcLsaKey);
+
+ ndn::Name destLsaKey = dest;
+ destLsaKey.append("coordinate");
+
+ CoordinateLsa* destLsa = lsdb.findCoordinateLsa(destLsaKey);
+
+ // Coordinate LSAs do not exist for these routers
+ if (srcLsa == NULL || destLsa == NULL) {
+ return UNKNOWN_DISTANCE;
}
- double srcRadius = srcLsa->getCorRadius();
double srcTheta = srcLsa->getCorTheta();
- double destRadius = destLsa->getCorRadius();
double destTheta = destLsa->getCorTheta();
double diffTheta = fabs(srcTheta - destTheta);
+
if (diffTheta > MATH_PI) {
diffTheta = 2 * MATH_PI - diffTheta;
}
- if (srcRadius != -1 && destRadius != -1) {
- if (diffTheta == 0) {
- distance = fabs(srcRadius - destRadius);
- }
- else {
- distance = acosh((cosh(srcRadius) * cosh(destRadius)) -
- (sinh(srcRadius) * sinh(destRadius) * cos(diffTheta)));
- }
+
+ double srcRadius = srcLsa->getCorRadius();
+ double destRadius = destLsa->getCorRadius();
+
+ if (srcRadius == UNKNOWN_RADIUS && destRadius == UNKNOWN_RADIUS) {
+ return UNKNOWN_DISTANCE;
+ }
+
+ if (diffTheta == 0) {
+ distance = fabs(srcRadius - destRadius);
}
else {
- distance = -1;
+ distance = acosh((cosh(srcRadius) * cosh(destRadius)) -
+ (sinh(srcRadius) * sinh(destRadius) * cos(diffTheta)));
}
+
+ _LOG_TRACE("Distance from " << src << " to " << dest << " is " << distance);
+
return distance;
}
-void
-HypRoutingTableCalculator::allocateNexthopRouters()
+void HyperbolicRoutingCalculator::addNextHop(ndn::Name dest, std::string faceUri,
+ double cost, RoutingTable& rt)
{
- m_nexthopRouters = new uint32_t[vNoLink];
-}
+ NextHop hop(faceUri, cost);
-void
-HypRoutingTableCalculator::allocateDistanceToNeighbor()
-{
- m_distanceToNeighbor = new double[vNoLink];
-}
+ _LOG_TRACE("Calculated " << hop << " for destination: " << dest);
-void
-HypRoutingTableCalculator::allocateDistFromNbrToDest()
-{
- m_distFromNbrToDest = new double[vNoLink];
-}
-
-void
-HypRoutingTableCalculator::freeNexthopRouters()
-{
- delete [] m_nexthopRouters;
-}
-
-void
-HypRoutingTableCalculator::freeDistanceToNeighbor()
-{
- delete [] m_distanceToNeighbor;
-}
-
-void
-HypRoutingTableCalculator::freeDistFromNbrToDest()
-{
- delete [] m_distFromNbrToDest;
+ if (m_isDryRun) {
+ rt.addNextHopToDryTable(dest, hop);
+ }
+ else {
+ rt.addNextHop(dest, hop);
+ }
}
}//namespace nlsr
diff --git a/src/route/routing-table-calculator.hpp b/src/route/routing-table-calculator.hpp
index a56fed3..a2295b5 100644
--- a/src/route/routing-table-calculator.hpp
+++ b/src/route/routing-table-calculator.hpp
@@ -27,6 +27,8 @@
#include <iostream>
#include <boost/cstdint.hpp>
+#include <ndn-cxx/name.hpp>
+
namespace nlsr {
class Map;
@@ -39,9 +41,9 @@
RoutingTableCalculator()
{
}
- RoutingTableCalculator(int rn)
+ RoutingTableCalculator(size_t nRouters)
{
- numOfRouter = rn;
+ m_nRouters = nRouters;
}
protected:
void
@@ -52,10 +54,7 @@
void
makeAdjMatrix(Nlsr& pnlsr, Map pMap);
-/*
- void
- printAdjMatrix();
-*/
+
void
writeAdjMatrixLog();
@@ -91,7 +90,7 @@
protected:
double** adjMatrix;
- int numOfRouter;
+ size_t m_nRouters;
int vNoLink;
int* links;
@@ -101,20 +100,18 @@
class LinkStateRoutingTableCalculator: public RoutingTableCalculator
{
public:
- LinkStateRoutingTableCalculator(int rn)
- : EMPTY_PARENT(-12345)
+ LinkStateRoutingTableCalculator(size_t nRouters)
+ : RoutingTableCalculator(nRouters)
+ , EMPTY_PARENT(-12345)
, INF_DISTANCE(2147483647)
, NO_MAPPING_NUM(-1)
, NO_NEXT_HOP(-12345)
{
- numOfRouter = rn;
}
-
void
calculatePath(Map& pMap, RoutingTable& rt, Nlsr& pnlsr);
-
private:
void
doDijkstraPathCalculation(int sourceRouter);
@@ -127,7 +124,7 @@
void
addAllLsNextHopsToRoutingTable(Nlsr& pnlsr, RoutingTable& rt,
- Map& pMap, int sourceRouter);
+ Map& pMap, uint32_t sourceRouter);
int
getLsNextHop(int dest, int source);
@@ -144,14 +141,10 @@
void
freeDistance();
-
-
-
private:
int* m_parent;
double* m_distance;
-
const int EMPTY_PARENT;
const double INF_DISTANCE;
const int NO_MAPPING_NUM;
@@ -159,61 +152,38 @@
};
-class HypRoutingTableCalculator: public RoutingTableCalculator
+class AdjacencyList;
+class Lsdb;
+
+class HyperbolicRoutingCalculator
{
public:
- HypRoutingTableCalculator(int rn)
- : MATH_PI(3.141592654)
+ HyperbolicRoutingCalculator(size_t nRouters, bool isDryRun, ndn::Name thisRouterName)
+ : m_nRouters(nRouters)
+ , m_isDryRun(isDryRun)
+ , m_thisRouterName(thisRouterName)
{
- numOfRouter = rn;
- m_isDryRun = 0;
- }
-
- HypRoutingTableCalculator(int rn, int idr)
- : MATH_PI(3.141592654)
- {
- numOfRouter = rn;
- m_isDryRun = idr;
}
void
- calculatePath(Map& pMap, RoutingTable& rt, Nlsr& pnlsr);
+ calculatePaths(Map& map, RoutingTable& rt, Lsdb& lsdb, AdjacencyList& adjacencies);
private:
- void
- allocateNexthopRouters();
-
- void
- allocateDistanceToNeighbor();
-
- void
- allocateDistFromNbrToDest();
-
- void
- freeNexthopRouters();
-
- void
- freeDistanceToNeighbor();
-
- void
- freeDistFromNbrToDest();
-
double
- getHyperbolicDistance(Nlsr& pnlsr, Map& pMap, int src, int dest);
+ getHyperbolicDistance(Map& map, Lsdb& lsdb, ndn::Name src, ndn::Name dest);
void
- addHypNextHopsToRoutingTable(Nlsr& pnlsr, Map& pMap,
- RoutingTable& rt, int noFaces, int dest);
+ addNextHop(ndn::Name destinationRouter, std::string faceUri, double cost, RoutingTable& rt);
private:
- bool m_isDryRun;
+ const size_t m_nRouters;
+ const bool m_isDryRun;
+ const ndn::Name m_thisRouterName;
- uint32_t* m_nexthopRouters;
- double* m_distanceToNeighbor;
- double* m_distFromNbrToDest;
-
- const double MATH_PI;
-
+ static const double MATH_PI;
+ static const double UNKNOWN_DISTANCE;
+ static const double UNKNOWN_RADIUS;
+ static const int32_t ROUTER_NOT_FOUND;
};
}//namespace nlsr
diff --git a/src/route/routing-table.cpp b/src/route/routing-table.cpp
index e05db49..09b9430 100644
--- a/src/route/routing-table.cpp
+++ b/src/route/routing-table.cpp
@@ -105,37 +105,51 @@
void
-RoutingTable::calculateLsRoutingTable(Nlsr& pnlsr)
+RoutingTable::calculateLsRoutingTable(Nlsr& nlsr)
{
_LOG_DEBUG("RoutingTable::calculateLsRoutingTable Called");
- Map vMap;
- vMap.createFromAdjLsdb(pnlsr);
- vMap.writeLog();
- int numOfRouter = vMap.getMapSize();
- LinkStateRoutingTableCalculator lsrtc(numOfRouter);
- lsrtc.calculatePath(vMap, ndn::ref(*this), pnlsr);
+
+ Map map;
+ map.createFromAdjLsdb(nlsr);
+ map.writeLog();
+
+ size_t nRouters = map.getMapSize();
+
+ LinkStateRoutingTableCalculator calculator(nRouters);
+
+ calculator.calculatePath(map, ndn::ref(*this), nlsr);
}
void
-RoutingTable::calculateHypRoutingTable(Nlsr& pnlsr)
+RoutingTable::calculateHypRoutingTable(Nlsr& nlsr)
{
- Map vMap;
- vMap.createFromAdjLsdb(pnlsr);
- vMap.writeLog();
- int numOfRouter = vMap.getMapSize();
- HypRoutingTableCalculator hrtc(numOfRouter, 0);
- hrtc.calculatePath(vMap, ndn::ref(*this), pnlsr);
+ Map map;
+ map.createFromAdjLsdb(nlsr);
+ map.writeLog();
+
+ size_t nRouters = map.getMapSize();
+
+ HyperbolicRoutingCalculator calculator(nRouters, false,
+ nlsr.getConfParameter().getRouterPrefix());
+
+ calculator.calculatePaths(map, ndn::ref(*this),
+ nlsr.getLsdb(), nlsr.getAdjacencyList());
}
void
-RoutingTable::calculateHypDryRoutingTable(Nlsr& pnlsr)
+RoutingTable::calculateHypDryRoutingTable(Nlsr& nlsr)
{
- Map vMap;
- vMap.createFromAdjLsdb(pnlsr);
- vMap.writeLog();
- int numOfRouter = vMap.getMapSize();
- HypRoutingTableCalculator hrtc(numOfRouter, 1);
- hrtc.calculatePath(vMap, ndn::ref(*this), pnlsr);
+ Map map;
+ map.createFromAdjLsdb(nlsr);
+ map.writeLog();
+
+ size_t nRouters = map.getMapSize();
+
+ HyperbolicRoutingCalculator calculator(nRouters, true,
+ nlsr.getConfParameter().getRouterPrefix());
+
+ calculator.calculatePaths(map, ndn::ref(*this),
+ nlsr.getLsdb(), nlsr.getAdjacencyList());
}
void
@@ -159,6 +173,8 @@
void
RoutingTable::addNextHop(const ndn::Name& destRouter, NextHop& nh)
{
+ _LOG_DEBUG("Adding " << nh << " for destination: " << destRouter);
+
RoutingTableEntry* rteChk = findRoutingTableEntry(destRouter);
if (rteChk == 0) {
RoutingTableEntry rte(destRouter);
@@ -209,6 +225,8 @@
void
RoutingTable::addNextHopToDryTable(const ndn::Name& destRouter, NextHop& nh)
{
+ _LOG_DEBUG("Adding " << nh << " to dry table for destination: " << destRouter);
+
std::list<RoutingTableEntry>::iterator it = std::find_if(m_dryTable.begin(),
m_dryTable.end(),
ndn::bind(&routingTableEntryCompare,
diff --git a/tests/test-hyperbolic-calculator.cpp b/tests/test-hyperbolic-calculator.cpp
new file mode 100644
index 0000000..eaf1f1a
--- /dev/null
+++ b/tests/test-hyperbolic-calculator.cpp
@@ -0,0 +1,175 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014 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 "test-common.hpp"
+#include "dummy-face.hpp"
+
+#include "route/routing-table-calculator.hpp"
+
+#include "adjacency-list.hpp"
+#include "lsa.hpp"
+#include "lsdb.hpp"
+#include "nlsr.hpp"
+#include "route/map.hpp"
+#include "route/routing-table.hpp"
+
+#include <boost/test/unit_test.hpp>
+
+namespace nlsr {
+namespace test {
+
+using ndn::DummyFace;
+using ndn::shared_ptr;
+using ndn::time::system_clock;
+static const system_clock::TimePoint MAX_TIME = system_clock::TimePoint::max();
+
+class HyperbolicCalculatorFixture : public BaseFixture
+{
+public:
+ HyperbolicCalculatorFixture()
+ : face(ndn::makeDummyFace())
+ , nlsr(g_ioService, g_scheduler, ndn::ref(*face))
+ , routingTable(nlsr.getRoutingTable())
+ , adjacencies(nlsr.getAdjacencyList())
+ , lsdb(nlsr.getLsdb())
+ {
+ setUpTopology();
+ }
+
+ // Triangle topology with routers A, B, C connected
+ void setUpTopology()
+ {
+ INIT_LOGGERS("/tmp", "TRACE");
+
+ Adjacent a(ROUTER_A_NAME, ROUTER_A_FACE, 0, Adjacent::STATUS_ACTIVE, 0, 0);
+ Adjacent b(ROUTER_B_NAME, ROUTER_B_FACE, 0, Adjacent::STATUS_ACTIVE, 0, 0);
+ Adjacent c(ROUTER_C_NAME, ROUTER_C_FACE, 0, Adjacent::STATUS_ACTIVE, 0, 0);
+
+ // Router A
+ adjacencies.insert(b);
+ adjacencies.insert(c);
+
+ AdjLsa adjA(a.getName(), "adjacency", 1, MAX_TIME, 2, adjacencies);
+ lsdb.installAdjLsa(adjA);
+
+ CoordinateLsa coordA(adjA.getOrigRouter(), "coordinate", 1, MAX_TIME, 16.23, 2.97);
+ lsdb.installCoordinateLsa(coordA);
+
+ // Router B
+ a.setFaceId(1);
+ c.setFaceId(2);
+
+ AdjacencyList adjacencyListB;
+ adjacencyListB.insert(a);
+ adjacencyListB.insert(c);
+
+ AdjLsa adjB(b.getName(), "adjacency", 1, MAX_TIME, 2, adjacencyListB);
+ lsdb.installAdjLsa(adjB);
+
+ CoordinateLsa coordB(adjB.getOrigRouter(), "coordinate", 1, MAX_TIME, 16.59, 3.0);
+ lsdb.installCoordinateLsa(coordB);
+
+ // Router C
+ a.setFaceId(1);
+ b.setFaceId(2);
+
+ AdjacencyList adjacencyListC;
+ adjacencyListC.insert(a);
+ adjacencyListC.insert(b);
+
+ AdjLsa adjC(c.getName(), "adjacency", 1, MAX_TIME, 2, adjacencyListC);
+ lsdb.installAdjLsa(adjC);
+
+ CoordinateLsa coordC(adjC.getOrigRouter(), "coordinate", 1, MAX_TIME, 14.11, 2.99);
+ lsdb.installCoordinateLsa(coordC);
+
+ map.createFromAdjLsdb(nlsr);
+ }
+
+public:
+ shared_ptr<DummyFace> face;
+ Nlsr nlsr;
+ Map map;
+
+ RoutingTable& routingTable;
+ AdjacencyList& adjacencies;
+ Lsdb& lsdb;
+
+ static const ndn::Name ROUTER_A_NAME;
+ static const ndn::Name ROUTER_B_NAME;
+ static const ndn::Name ROUTER_C_NAME;
+
+ static const std::string ROUTER_A_FACE;
+ static const std::string ROUTER_B_FACE;
+ static const std::string ROUTER_C_FACE;
+};
+
+const ndn::Name HyperbolicCalculatorFixture::ROUTER_A_NAME = "/ndn/router/a";
+const ndn::Name HyperbolicCalculatorFixture::ROUTER_B_NAME = "/ndn/router/b";
+const ndn::Name HyperbolicCalculatorFixture::ROUTER_C_NAME = "/ndn/router/c";
+
+const std::string HyperbolicCalculatorFixture::ROUTER_A_FACE = "face-a";
+const std::string HyperbolicCalculatorFixture::ROUTER_B_FACE = "face-b";
+const std::string HyperbolicCalculatorFixture::ROUTER_C_FACE = "face-c";
+
+BOOST_FIXTURE_TEST_SUITE(TestHyperbolicRoutingCalculator, HyperbolicCalculatorFixture)
+
+BOOST_AUTO_TEST_CASE(Basic)
+{
+ HyperbolicRoutingCalculator calculator(map.getMapSize(), false, ROUTER_A_NAME);
+ calculator.calculatePaths(map, routingTable, lsdb, adjacencies);
+
+ RoutingTableEntry* entryB = routingTable.findRoutingTableEntry(ROUTER_B_NAME);
+
+ // Router A should be able to get to B through B with cost 0 and to B through
+ // C with cost 2010
+ NexthopList& bHopList = entryB->getNexthopList();
+ BOOST_REQUIRE_EQUAL(bHopList.getNextHops().size(), 2);
+
+ for (std::list<NextHop>::iterator it = bHopList.begin(); it != bHopList.end(); ++it) {
+ std::string faceUri = it->getConnectingFaceUri();
+ uint64_t cost = it->getRouteCostAsAdjustedInteger();
+
+ BOOST_CHECK((faceUri == ROUTER_B_FACE && cost == 0) ||
+ (faceUri == ROUTER_C_FACE && cost == 2010));
+ }
+
+ RoutingTableEntry* entryC = routingTable.findRoutingTableEntry(ROUTER_C_NAME);
+
+ // Router A should be able to get to C through C with cost 0 and to C through
+ // B with cost 2010
+ NexthopList& cHopList = entryC->getNexthopList();
+ BOOST_REQUIRE_EQUAL(cHopList.getNextHops().size(), 2);
+
+ for (std::list<NextHop>::iterator it = cHopList.begin(); it != cHopList.end(); ++it) {
+ std::string faceUri = it->getConnectingFaceUri();
+ uint64_t cost = it->getRouteCostAsAdjustedInteger();
+
+ BOOST_CHECK((faceUri == ROUTER_B_FACE && cost == 2010) ||
+ (faceUri == ROUTER_C_FACE && cost == 0));
+ }
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} //namespace test
+} //namespace nlsr