route: reduce calculators to free functions
Link state and hyperbolic calculator implementations are split to
separate files.
Class structures are now internal to each calculator, so that they can
be refactored independently without affecting external callers.
The code within each class remains unchanged.
refs #5308
Change-Id: I14b126da3250bce9bc0488ae006629465f3ed328
diff --git a/src/route/routing-calculator-hyperbolic.cpp b/src/route/routing-calculator-hyperbolic.cpp
new file mode 100644
index 0000000..272779f
--- /dev/null
+++ b/src/route/routing-calculator-hyperbolic.cpp
@@ -0,0 +1,287 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2014-2024, 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 "routing-calculator.hpp"
+#include "name-map.hpp"
+#include "nexthop.hpp"
+
+#include "adjacent.hpp"
+#include "logger.hpp"
+#include "nlsr.hpp"
+
+#include <cmath>
+
+namespace nlsr {
+
+INIT_LOGGER(route.RoutingCalculatorHyperbolic);
+
+class HyperbolicRoutingCalculator
+{
+public:
+ HyperbolicRoutingCalculator(size_t nRouters, bool isDryRun, ndn::Name thisRouterName)
+ : m_nRouters(nRouters)
+ , m_isDryRun(isDryRun)
+ , m_thisRouterName(thisRouterName)
+ {
+ }
+
+ void
+ calculatePath(NameMap& map, RoutingTable& rt, Lsdb& lsdb, AdjacencyList& adjacencies);
+
+private:
+ double
+ getHyperbolicDistance(Lsdb& lsdb, ndn::Name src, ndn::Name dest);
+
+ void
+ addNextHop(const ndn::Name& destinationRouter, const ndn::FaceUri& faceUri, double cost, RoutingTable& rt);
+
+ double
+ calculateHyperbolicDistance(double rI, double rJ, double deltaTheta);
+
+ double
+ calculateAngularDistance(std::vector<double> angleVectorI,
+ std::vector<double> angleVectorJ);
+
+private:
+ const size_t m_nRouters;
+ const bool m_isDryRun;
+ const ndn::Name m_thisRouterName;
+};
+
+constexpr double UNKNOWN_DISTANCE = -1.0;
+constexpr double UNKNOWN_RADIUS = -1.0;
+
+void
+HyperbolicRoutingCalculator::calculatePath(NameMap& map, RoutingTable& rt,
+ Lsdb& lsdb, AdjacencyList& adjacencies)
+{
+ NLSR_LOG_TRACE("Calculating hyperbolic paths");
+
+ auto thisRouter = map.getMappingNoByRouterName(m_thisRouterName);
+
+ // Iterate over directly connected neighbors
+ std::list<Adjacent> neighbors = adjacencies.getAdjList();
+ for (auto adj = neighbors.begin(); adj != neighbors.end(); ++adj) {
+
+ // Don't calculate nexthops using an inactive router
+ if (adj->getStatus() == Adjacent::STATUS_INACTIVE) {
+ NLSR_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;
+ }
+
+ // Install nexthops for this router to the neighbor; direct neighbors have a 0 cost link
+ addNextHop(srcRouterName, adj->getFaceUri(), 0, rt);
+
+ auto src = map.getMappingNoByRouterName(srcRouterName);
+ if (!src) {
+ NLSR_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 (thisRouter && dest != *thisRouter && dest != *src) {
+
+ auto destRouterName = map.getRouterNameByMappingNo(dest);
+ if (destRouterName) {
+ double distance = getHyperbolicDistance(lsdb, srcRouterName, *destRouterName);
+
+ // Could not compute distance
+ if (distance == UNKNOWN_DISTANCE) {
+ NLSR_LOG_WARN("Could not calculate hyperbolic distance from " << srcRouterName
+ << " to " << *destRouterName);
+ continue;
+ }
+ addNextHop(*destRouterName, adj->getFaceUri(), distance, rt);
+ }
+ }
+ }
+ }
+}
+
+double
+HyperbolicRoutingCalculator::getHyperbolicDistance(Lsdb& lsdb, ndn::Name src, ndn::Name dest)
+{
+ NLSR_LOG_TRACE("Calculating hyperbolic distance from " << src << " to " << dest);
+
+ double distance = UNKNOWN_DISTANCE;
+
+ auto srcLsa = lsdb.findLsa<CoordinateLsa>(src);
+ auto destLsa = lsdb.findLsa<CoordinateLsa>(dest);
+
+ // Coordinate LSAs do not exist for these routers
+ if (srcLsa == nullptr || destLsa == nullptr) {
+ return UNKNOWN_DISTANCE;
+ }
+
+ std::vector<double> srcTheta = srcLsa->getTheta();
+ std::vector<double> destTheta = destLsa->getTheta();
+
+ double srcRadius = srcLsa->getRadius();
+ double destRadius = destLsa->getRadius();
+
+ double diffTheta = calculateAngularDistance(srcTheta, destTheta);
+
+ if (srcRadius == UNKNOWN_RADIUS || destRadius == UNKNOWN_RADIUS ||
+ diffTheta == UNKNOWN_DISTANCE) {
+ return UNKNOWN_DISTANCE;
+ }
+
+ // double r_i, double r_j, double delta_theta, double zeta = 1 (default)
+ distance = calculateHyperbolicDistance(srcRadius, destRadius, diffTheta);
+
+ NLSR_LOG_TRACE("Distance from " << src << " to " << dest << " is " << distance);
+
+ return distance;
+}
+
+double
+HyperbolicRoutingCalculator::calculateAngularDistance(std::vector<double> angleVectorI,
+ std::vector<double> angleVectorJ)
+{
+ // It is not possible for angle vector size to be zero as ensured by conf-file-processor
+
+ // https://en.wikipedia.org/wiki/N-sphere#Spherical_coordinates
+
+ // Check if two vector lengths are the same
+ if (angleVectorI.size() != angleVectorJ.size()) {
+ NLSR_LOG_ERROR("Angle vector sizes do not match");
+ return UNKNOWN_DISTANCE;
+ }
+
+ // Check if all angles are within the [0, PI] and [0, 2PI] ranges
+ if (angleVectorI.size() > 1) {
+ for (unsigned int k = 0; k < angleVectorI.size() - 1; k++) {
+ if ((angleVectorI[k] > M_PI && angleVectorI[k] < 0.0) ||
+ (angleVectorJ[k] > M_PI && angleVectorJ[k] < 0.0)) {
+ NLSR_LOG_ERROR("Angle outside [0, PI]");
+ return UNKNOWN_DISTANCE;
+ }
+ }
+ }
+
+ if (angleVectorI[angleVectorI.size()-1] > 2.*M_PI ||
+ angleVectorI[angleVectorI.size()-1] < 0.0) {
+ NLSR_LOG_ERROR("Angle not within [0, 2PI]");
+ return UNKNOWN_DISTANCE;
+ }
+
+ if (angleVectorI[angleVectorI.size()-1] > 2.*M_PI ||
+ angleVectorI[angleVectorI.size()-1] < 0.0) {
+ NLSR_LOG_ERROR("Angle not within [0, 2PI]");
+ return UNKNOWN_DISTANCE;
+ }
+
+ // deltaTheta = arccos(vectorI . vectorJ) -> do the inner product
+ double innerProduct = 0.0;
+
+ // Calculate x0 of the vectors
+ double x0i = std::cos(angleVectorI[0]);
+ double x0j = std::cos(angleVectorJ[0]);
+
+ // Calculate xn of the vectors
+ double xni = std::sin(angleVectorI[angleVectorI.size() - 1]);
+ double xnj = std::sin(angleVectorJ[angleVectorJ.size() - 1]);
+
+ // Do the aggregation of the (n-1) coordinates (if there is more than one angle)
+ // i.e contraction of all (n-1)-dimensional angular coordinates to one variable
+ for (unsigned int k = 0; k < angleVectorI.size() - 1; k++) {
+ xni *= std::sin(angleVectorI[k]);
+ xnj *= std::sin(angleVectorJ[k]);
+ }
+ innerProduct += (x0i * x0j) + (xni * xnj);
+
+ // If d > 1
+ if (angleVectorI.size() > 1) {
+ for (unsigned int m = 1; m < angleVectorI.size(); m++) {
+ // calculate euclidean coordinates given the angles and assuming R_sphere = 1
+ double xmi = std::cos(angleVectorI[m]);
+ double xmj = std::cos(angleVectorJ[m]);
+ for (unsigned int l = 0; l < m; l++) {
+ xmi *= std::sin(angleVectorI[l]);
+ xmj *= std::sin(angleVectorJ[l]);
+ }
+ innerProduct += xmi * xmj;
+ }
+ }
+
+ // ArcCos of the inner product gives the angular distance
+ // between two points on a d-dimensional sphere
+ return std::acos(innerProduct);
+}
+
+double
+HyperbolicRoutingCalculator::calculateHyperbolicDistance(double rI, double rJ,
+ double deltaTheta)
+{
+ if (deltaTheta == UNKNOWN_DISTANCE) {
+ return UNKNOWN_DISTANCE;
+ }
+
+ // Usually, we set zeta = 1 in all experiments
+ double zeta = 1;
+
+ if (deltaTheta <= 0.0 || rI <= 0.0 || rJ <= 0.0) {
+ NLSR_LOG_ERROR("Delta theta or rI or rJ is <= 0");
+ NLSR_LOG_ERROR("Please make sure that no two nodes have the exact same HR coordinates");
+ return UNKNOWN_DISTANCE;
+ }
+
+ double xij = (1. / zeta) * std::acosh(std::cosh(zeta*rI) * std::cosh(zeta*rJ) -
+ std::sinh(zeta*rI)*std::sinh(zeta*rJ)*std::cos(deltaTheta));
+ return xij;
+}
+
+void
+HyperbolicRoutingCalculator::addNextHop(const ndn::Name& dest, const ndn::FaceUri& faceUri,
+ double cost, RoutingTable& rt)
+{
+ NextHop hop(faceUri, cost);
+ hop.setHyperbolic(true);
+
+ NLSR_LOG_TRACE("Calculated " << hop << " for destination: " << dest);
+
+ if (m_isDryRun) {
+ rt.addNextHopToDryTable(dest, hop);
+ }
+ else {
+ rt.addNextHop(dest, hop);
+ }
+}
+
+void
+calculateHyperbolicRoutingPath(NameMap& map, RoutingTable& rt, Lsdb& lsdb,
+ AdjacencyList& adjacencies, ndn::Name thisRouterName,
+ bool isDryRun)
+{
+ HyperbolicRoutingCalculator calculator(map.size(), isDryRun, thisRouterName);
+ calculator.calculatePath(map, rt, lsdb, adjacencies);
+}
+
+} // namespace nlsr
diff --git a/src/route/routing-table-calculator.cpp b/src/route/routing-calculator-link-state.cpp
similarity index 64%
rename from src/route/routing-table-calculator.cpp
rename to src/route/routing-calculator-link-state.cpp
index 061e151..7d113ee 100644
--- a/src/route/routing-table-calculator.cpp
+++ b/src/route/routing-calculator-link-state.cpp
@@ -19,28 +19,185 @@
* NLSR, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
*/
-#include "routing-table-calculator.hpp"
-#include "lsdb.hpp"
+#include "routing-calculator.hpp"
#include "name-map.hpp"
#include "nexthop.hpp"
-#include "nlsr.hpp"
-#include "logger.hpp"
-#include "adjacent.hpp"
-#include <cmath>
+#include "adjacent.hpp"
+#include "logger.hpp"
+#include "nlsr.hpp"
+
#include <boost/lexical_cast.hpp>
-#include <ndn-cxx/util/logger.hpp>
namespace nlsr {
-INIT_LOGGER(route.RoutingTableCalculator);
+INIT_LOGGER(route.RoutingCalculatorLinkState);
+
+class RoutingTableCalculator
+{
+public:
+ RoutingTableCalculator(size_t nRouters)
+ {
+ m_nRouters = nRouters;
+ }
+
+protected:
+ /*! \brief Allocate the space needed for the adj. matrix. */
+ void
+ allocateAdjMatrix();
+
+ /*! \brief set NON_ADJACENT_COST i.e. -12345 to every cell of the matrix to
+ ensure that the memory is safe. This is also to incorporate zero cost links */
+ void
+ initMatrix();
+
+ /*! \brief Constructs an adj. matrix to calculate with.
+ \param lsdb Reference to the Lsdb
+ \param pMap The map to populate with the adj. data.
+ */
+ void
+ makeAdjMatrix(const Lsdb& lsdb, NameMap& pMap);
+
+ /*! \brief Writes a formated adjacent matrix to DEBUG log
+ \param map The map containing adjacent matrix data
+ */
+ void
+ writeAdjMatrixLog(const NameMap& map) const;
+
+ /*! \brief Returns how many links a router in the matrix has.
+ \param sRouter The router to count the links of.
+ */
+ int
+ getNumOfLinkfromAdjMatrix(int sRouter);
+
+ void
+ freeAdjMatrix();
+ /*! \brief Adjust a link cost in the adj. matrix
+ \param source The source router whose adjacency to adjust.
+ \param link The adjacency of the source to adjust.
+ \param linkCost The cost to change to.
+ */
+ void
+ adjustAdMatrix(int source, int link, double linkCost);
+
+ /*! \brief Populates temp. variables with the link costs for some router.
+ \param source The router whose values are to be adjusted.
+ \param links An integer pointer array for the link mappingNos.
+ \param linkCosts A double pointer array that stores the link costs.
+
+ Obtains a sparse list of adjacencies and link costs for some
+ router. Since this is sparse, that means while generating these
+ arrays, if there is no adjacency at i in the matrix, these
+ temporary variables will not contain a NON_ADJACENT_COST (-12345) at i,
+ but rather will contain the values for the next valid adjacency.
+ */
+ void
+ getLinksFromAdjMatrix(int* links, double* linkCosts, int source);
+
+ /*! Allocates an array large enough to hold multipath calculation temps. */
+ void
+ allocateLinks();
+
+ void
+ allocateLinkCosts();
+
+ void
+ freeLinks();
+
+ void
+ freeLinksCosts();
+
+ void
+ setNoLink(int nl)
+ {
+ vNoLink = nl;
+ }
+
+protected:
+ double** adjMatrix;
+ size_t m_nRouters;
+
+ int vNoLink;
+ int* links;
+ double* linkCosts;
+
+};
+
+class LinkStateRoutingTableCalculator: public RoutingTableCalculator
+{
+public:
+ LinkStateRoutingTableCalculator(size_t nRouters)
+ : RoutingTableCalculator(nRouters)
+ {
+ }
+
+ void
+ calculatePath(NameMap& pMap, RoutingTable& rt, ConfParameter& confParam,
+ const Lsdb& lsdb);
+
+private:
+ /*! \brief Performs a Dijkstra's calculation over the adjacency matrix.
+ \param sourceRouter The origin router to compute paths from.
+ */
+ void
+ doDijkstraPathCalculation(int sourceRouter);
+
+ /*! \brief Sort the elements of a list.
+ \param Q The array that contains the elements to sort.
+ \param dist The array that contains the distances.
+ \param start The first element in the list to sort.
+ \param element The last element in the list to sort through.
+
+ Sorts the list based on distance. The distances are indexed by
+ their mappingNo in dist. Currently uses an insertion sort.
+
+ The cost between two nodes can be zero or greater than zero.
+
+ */
+ void
+ sortQueueByDistance(int* Q, double* dist, int start, int element);
+
+ /*! \brief Returns whether an element has been visited yet.
+ \param Q The list of elements to look through.
+ \param u The element to check.
+ \param start The start of list to look through.
+ \param element The end of the list to look through.
+ */
+ int
+ isNotExplored(int* Q, int u, int start, int element);
+
+ void
+ addAllLsNextHopsToRoutingTable(AdjacencyList& adjacencies, RoutingTable& rt,
+ NameMap& pMap, uint32_t sourceRouter);
+
+ /*! \brief Determines a destination's next hop.
+ \param dest The router whose next hop we want to determine.
+ \param source The router to determine a next path to.
+ */
+ int
+ getLsNextHop(int dest, int source);
+
+ void
+ allocateParent();
+
+ void
+ allocateDistance();
+
+ void
+ freeParent();
+
+ void
+ freeDistance();
+
+private:
+ int* m_parent;
+ double* m_distance;
+};
constexpr int EMPTY_PARENT = -12345;
constexpr double INF_DISTANCE = 2147483647;
constexpr int NO_MAPPING_NUM = -1;
constexpr int NO_NEXT_HOP = -12345;
-constexpr double UNKNOWN_DISTANCE = -1.0;
-constexpr double UNKNOWN_RADIUS = -1.0;
void
RoutingTableCalculator::allocateAdjMatrix()
@@ -426,209 +583,11 @@
}
void
-HyperbolicRoutingCalculator::calculatePath(NameMap& map, RoutingTable& rt,
- Lsdb& lsdb, AdjacencyList& adjacencies)
+calculateLinkStateRoutingPath(NameMap& map, RoutingTable& rt, ConfParameter& confParam,
+ const Lsdb& lsdb)
{
- NLSR_LOG_TRACE("Calculating hyperbolic paths");
-
- auto thisRouter = map.getMappingNoByRouterName(m_thisRouterName);
-
- // Iterate over directly connected neighbors
- std::list<Adjacent> neighbors = adjacencies.getAdjList();
- for (auto adj = neighbors.begin(); adj != neighbors.end(); ++adj) {
-
- // Don't calculate nexthops using an inactive router
- if (adj->getStatus() == Adjacent::STATUS_INACTIVE) {
- NLSR_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;
- }
-
- // Install nexthops for this router to the neighbor; direct neighbors have a 0 cost link
- addNextHop(srcRouterName, adj->getFaceUri(), 0, rt);
-
- auto src = map.getMappingNoByRouterName(srcRouterName);
- if (!src) {
- NLSR_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 (thisRouter && dest != *thisRouter && dest != *src) {
-
- auto destRouterName = map.getRouterNameByMappingNo(dest);
- if (destRouterName) {
- double distance = getHyperbolicDistance(lsdb, srcRouterName, *destRouterName);
-
- // Could not compute distance
- if (distance == UNKNOWN_DISTANCE) {
- NLSR_LOG_WARN("Could not calculate hyperbolic distance from " << srcRouterName
- << " to " << *destRouterName);
- continue;
- }
- addNextHop(*destRouterName, adj->getFaceUri(), distance, rt);
- }
- }
- }
- }
-}
-
-double
-HyperbolicRoutingCalculator::getHyperbolicDistance(Lsdb& lsdb, ndn::Name src, ndn::Name dest)
-{
- NLSR_LOG_TRACE("Calculating hyperbolic distance from " << src << " to " << dest);
-
- double distance = UNKNOWN_DISTANCE;
-
- auto srcLsa = lsdb.findLsa<CoordinateLsa>(src);
- auto destLsa = lsdb.findLsa<CoordinateLsa>(dest);
-
- // Coordinate LSAs do not exist for these routers
- if (srcLsa == nullptr || destLsa == nullptr) {
- return UNKNOWN_DISTANCE;
- }
-
- std::vector<double> srcTheta = srcLsa->getTheta();
- std::vector<double> destTheta = destLsa->getTheta();
-
- double srcRadius = srcLsa->getRadius();
- double destRadius = destLsa->getRadius();
-
- double diffTheta = calculateAngularDistance(srcTheta, destTheta);
-
- if (srcRadius == UNKNOWN_RADIUS || destRadius == UNKNOWN_RADIUS ||
- diffTheta == UNKNOWN_DISTANCE) {
- return UNKNOWN_DISTANCE;
- }
-
- // double r_i, double r_j, double delta_theta, double zeta = 1 (default)
- distance = calculateHyperbolicDistance(srcRadius, destRadius, diffTheta);
-
- NLSR_LOG_TRACE("Distance from " << src << " to " << dest << " is " << distance);
-
- return distance;
-}
-
-double
-HyperbolicRoutingCalculator::calculateAngularDistance(std::vector<double> angleVectorI,
- std::vector<double> angleVectorJ)
-{
- // It is not possible for angle vector size to be zero as ensured by conf-file-processor
-
- // https://en.wikipedia.org/wiki/N-sphere#Spherical_coordinates
-
- // Check if two vector lengths are the same
- if (angleVectorI.size() != angleVectorJ.size()) {
- NLSR_LOG_ERROR("Angle vector sizes do not match");
- return UNKNOWN_DISTANCE;
- }
-
- // Check if all angles are within the [0, PI] and [0, 2PI] ranges
- if (angleVectorI.size() > 1) {
- for (unsigned int k = 0; k < angleVectorI.size() - 1; k++) {
- if ((angleVectorI[k] > M_PI && angleVectorI[k] < 0.0) ||
- (angleVectorJ[k] > M_PI && angleVectorJ[k] < 0.0)) {
- NLSR_LOG_ERROR("Angle outside [0, PI]");
- return UNKNOWN_DISTANCE;
- }
- }
- }
-
- if (angleVectorI[angleVectorI.size()-1] > 2.*M_PI ||
- angleVectorI[angleVectorI.size()-1] < 0.0) {
- NLSR_LOG_ERROR("Angle not within [0, 2PI]");
- return UNKNOWN_DISTANCE;
- }
-
- if (angleVectorI[angleVectorI.size()-1] > 2.*M_PI ||
- angleVectorI[angleVectorI.size()-1] < 0.0) {
- NLSR_LOG_ERROR("Angle not within [0, 2PI]");
- return UNKNOWN_DISTANCE;
- }
-
- // deltaTheta = arccos(vectorI . vectorJ) -> do the inner product
- double innerProduct = 0.0;
-
- // Calculate x0 of the vectors
- double x0i = std::cos(angleVectorI[0]);
- double x0j = std::cos(angleVectorJ[0]);
-
- // Calculate xn of the vectors
- double xni = std::sin(angleVectorI[angleVectorI.size() - 1]);
- double xnj = std::sin(angleVectorJ[angleVectorJ.size() - 1]);
-
- // Do the aggregation of the (n-1) coordinates (if there is more than one angle)
- // i.e contraction of all (n-1)-dimensional angular coordinates to one variable
- for (unsigned int k = 0; k < angleVectorI.size() - 1; k++) {
- xni *= std::sin(angleVectorI[k]);
- xnj *= std::sin(angleVectorJ[k]);
- }
- innerProduct += (x0i * x0j) + (xni * xnj);
-
- // If d > 1
- if (angleVectorI.size() > 1) {
- for (unsigned int m = 1; m < angleVectorI.size(); m++) {
- // calculate euclidean coordinates given the angles and assuming R_sphere = 1
- double xmi = std::cos(angleVectorI[m]);
- double xmj = std::cos(angleVectorJ[m]);
- for (unsigned int l = 0; l < m; l++) {
- xmi *= std::sin(angleVectorI[l]);
- xmj *= std::sin(angleVectorJ[l]);
- }
- innerProduct += xmi * xmj;
- }
- }
-
- // ArcCos of the inner product gives the angular distance
- // between two points on a d-dimensional sphere
- return std::acos(innerProduct);
-}
-
-double
-HyperbolicRoutingCalculator::calculateHyperbolicDistance(double rI, double rJ,
- double deltaTheta)
-{
- if (deltaTheta == UNKNOWN_DISTANCE) {
- return UNKNOWN_DISTANCE;
- }
-
- // Usually, we set zeta = 1 in all experiments
- double zeta = 1;
-
- if (deltaTheta <= 0.0 || rI <= 0.0 || rJ <= 0.0) {
- NLSR_LOG_ERROR("Delta theta or rI or rJ is <= 0");
- NLSR_LOG_ERROR("Please make sure that no two nodes have the exact same HR coordinates");
- return UNKNOWN_DISTANCE;
- }
-
- double xij = (1. / zeta) * std::acosh(std::cosh(zeta*rI) * std::cosh(zeta*rJ) -
- std::sinh(zeta*rI)*std::sinh(zeta*rJ)*std::cos(deltaTheta));
- return xij;
-}
-
-void
-HyperbolicRoutingCalculator::addNextHop(const ndn::Name& dest, const ndn::FaceUri& faceUri,
- double cost, RoutingTable& rt)
-{
- NextHop hop(faceUri, cost);
- hop.setHyperbolic(true);
-
- NLSR_LOG_TRACE("Calculated " << hop << " for destination: " << dest);
-
- if (m_isDryRun) {
- rt.addNextHopToDryTable(dest, hop);
- }
- else {
- rt.addNextHop(dest, hop);
- }
+ LinkStateRoutingTableCalculator calculator(map.size());
+ calculator.calculatePath(map, rt, confParam, lsdb);
}
} // namespace nlsr
diff --git a/src/route/routing-calculator.hpp b/src/route/routing-calculator.hpp
new file mode 100644
index 0000000..92480dc
--- /dev/null
+++ b/src/route/routing-calculator.hpp
@@ -0,0 +1,43 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2014-2024, 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/>.
+ */
+
+#ifndef NLSR_ROUTING_CALCULATOR_HPP
+#define NLSR_ROUTING_CALCULATOR_HPP
+
+#include "common.hpp"
+#include "lsdb.hpp"
+
+namespace nlsr {
+
+class NameMap;
+class RoutingTable;
+
+void
+calculateLinkStateRoutingPath(NameMap& map, RoutingTable& rt, ConfParameter& confParam,
+ const Lsdb& lsdb);
+
+void
+calculateHyperbolicRoutingPath(NameMap& map, RoutingTable& rt, Lsdb& lsdb,
+ AdjacencyList& adjacencies, ndn::Name thisRouterName,
+ bool isDryRun);
+
+} // namespace nlsr
+
+#endif // NLSR_ROUTING_CALCULATOR_HPP
diff --git a/src/route/routing-table-calculator.hpp b/src/route/routing-table-calculator.hpp
deleted file mode 100644
index 35e08eb..0000000
--- a/src/route/routing-table-calculator.hpp
+++ /dev/null
@@ -1,234 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/*
- * Copyright (c) 2014-2024, 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/>.
- */
-
-#ifndef NLSR_ROUTING_TABLE_CALCULATOR_HPP
-#define NLSR_ROUTING_TABLE_CALCULATOR_HPP
-
-#include "common.hpp"
-#include "lsa/lsa.hpp"
-#include "lsa/adj-lsa.hpp"
-#include "lsdb.hpp"
-#include "conf-parameter.hpp"
-
-namespace nlsr {
-
-class NameMap;
-class RoutingTable;
-
-class RoutingTableCalculator
-{
-public:
- RoutingTableCalculator(size_t nRouters)
- {
- m_nRouters = nRouters;
- }
-
-protected:
- /*! \brief Allocate the space needed for the adj. matrix. */
- void
- allocateAdjMatrix();
-
- /*! \brief set NON_ADJACENT_COST i.e. -12345 to every cell of the matrix to
- ensure that the memory is safe. This is also to incorporate zero cost links */
- void
- initMatrix();
-
- /*! \brief Constructs an adj. matrix to calculate with.
- \param lsdb Reference to the Lsdb
- \param pMap The map to populate with the adj. data.
- */
- void
- makeAdjMatrix(const Lsdb& lsdb, NameMap& pMap);
-
- /*! \brief Writes a formated adjacent matrix to DEBUG log
- \param map The map containing adjacent matrix data
- */
- void
- writeAdjMatrixLog(const NameMap& map) const;
-
- /*! \brief Returns how many links a router in the matrix has.
- \param sRouter The router to count the links of.
- */
- int
- getNumOfLinkfromAdjMatrix(int sRouter);
-
- void
- freeAdjMatrix();
- /*! \brief Adjust a link cost in the adj. matrix
- \param source The source router whose adjacency to adjust.
- \param link The adjacency of the source to adjust.
- \param linkCost The cost to change to.
- */
- void
- adjustAdMatrix(int source, int link, double linkCost);
-
- /*! \brief Populates temp. variables with the link costs for some router.
- \param source The router whose values are to be adjusted.
- \param links An integer pointer array for the link mappingNos.
- \param linkCosts A double pointer array that stores the link costs.
-
- Obtains a sparse list of adjacencies and link costs for some
- router. Since this is sparse, that means while generating these
- arrays, if there is no adjacency at i in the matrix, these
- temporary variables will not contain a NON_ADJACENT_COST (-12345) at i,
- but rather will contain the values for the next valid adjacency.
- */
- void
- getLinksFromAdjMatrix(int* links, double* linkCosts, int source);
-
- /*! Allocates an array large enough to hold multipath calculation temps. */
- void
- allocateLinks();
-
- void
- allocateLinkCosts();
-
- void
- freeLinks();
-
- void
- freeLinksCosts();
-
- void
- setNoLink(int nl)
- {
- vNoLink = nl;
- }
-
-protected:
- double** adjMatrix;
- size_t m_nRouters;
-
- int vNoLink;
- int* links;
- double* linkCosts;
-
-};
-
-class LinkStateRoutingTableCalculator: public RoutingTableCalculator
-{
-public:
- LinkStateRoutingTableCalculator(size_t nRouters)
- : RoutingTableCalculator(nRouters)
- {
- }
-
- void
- calculatePath(NameMap& pMap, RoutingTable& rt, ConfParameter& confParam,
- const Lsdb& lsdb);
-
-private:
- /*! \brief Performs a Dijkstra's calculation over the adjacency matrix.
- \param sourceRouter The origin router to compute paths from.
- */
- void
- doDijkstraPathCalculation(int sourceRouter);
-
- /*! \brief Sort the elements of a list.
- \param Q The array that contains the elements to sort.
- \param dist The array that contains the distances.
- \param start The first element in the list to sort.
- \param element The last element in the list to sort through.
-
- Sorts the list based on distance. The distances are indexed by
- their mappingNo in dist. Currently uses an insertion sort.
-
- The cost between two nodes can be zero or greater than zero.
-
- */
- void
- sortQueueByDistance(int* Q, double* dist, int start, int element);
-
- /*! \brief Returns whether an element has been visited yet.
- \param Q The list of elements to look through.
- \param u The element to check.
- \param start The start of list to look through.
- \param element The end of the list to look through.
- */
- int
- isNotExplored(int* Q, int u, int start, int element);
-
- void
- addAllLsNextHopsToRoutingTable(AdjacencyList& adjacencies, RoutingTable& rt,
- NameMap& pMap, uint32_t sourceRouter);
-
- /*! \brief Determines a destination's next hop.
- \param dest The router whose next hop we want to determine.
- \param source The router to determine a next path to.
- */
- int
- getLsNextHop(int dest, int source);
-
- void
- allocateParent();
-
- void
- allocateDistance();
-
- void
- freeParent();
-
- void
- freeDistance();
-
-private:
- int* m_parent;
- double* m_distance;
-};
-
-class AdjacencyList;
-class Lsdb;
-
-class HyperbolicRoutingCalculator
-{
-public:
- HyperbolicRoutingCalculator(size_t nRouters, bool isDryRun, ndn::Name thisRouterName)
- : m_nRouters(nRouters)
- , m_isDryRun(isDryRun)
- , m_thisRouterName(thisRouterName)
- {
- }
-
- void
- calculatePath(NameMap& map, RoutingTable& rt, Lsdb& lsdb, AdjacencyList& adjacencies);
-
-private:
- double
- getHyperbolicDistance(Lsdb& lsdb, ndn::Name src, ndn::Name dest);
-
- void
- addNextHop(const ndn::Name& destinationRouter, const ndn::FaceUri& faceUri, double cost, RoutingTable& rt);
-
- double
- calculateHyperbolicDistance(double rI, double rJ, double deltaTheta);
-
- double
- calculateAngularDistance(std::vector<double> angleVectorI,
- std::vector<double> angleVectorJ);
-
-private:
- const size_t m_nRouters;
- const bool m_isDryRun;
- const ndn::Name m_thisRouterName;
-};
-
-} // namespace nlsr
-
-#endif // NLSR_ROUTING_TABLE_CALCULATOR_HPP
diff --git a/src/route/routing-table.cpp b/src/route/routing-table.cpp
index 16bf2df..b5a5f69 100644
--- a/src/route/routing-table.cpp
+++ b/src/route/routing-table.cpp
@@ -19,12 +19,13 @@
*/
#include "routing-table.hpp"
-#include "nlsr.hpp"
#include "name-map.hpp"
-#include "conf-parameter.hpp"
-#include "routing-table-calculator.hpp"
+#include "routing-calculator.hpp"
#include "routing-table-entry.hpp"
+
+#include "conf-parameter.hpp"
#include "logger.hpp"
+#include "nlsr.hpp"
#include "tlv-nlsr.hpp"
namespace nlsr {
@@ -131,11 +132,7 @@
auto map = NameMap::createFromAdjLsdb(lsaRange.first, lsaRange.second);
NLSR_LOG_DEBUG(map);
- size_t nRouters = map.size();
-
- LinkStateRoutingTableCalculator calculator(nRouters);
-
- calculator.calculatePath(map, *this, m_confParam, m_lsdb);
+ calculateLinkStateRoutingPath(map, *this, m_confParam, m_lsdb);
NLSR_LOG_DEBUG("Calling Update NPT With new Route");
afterRoutingChange(m_rTable);
@@ -156,11 +153,8 @@
auto map = NameMap::createFromCoordinateLsdb(lsaRange.first, lsaRange.second);
NLSR_LOG_DEBUG(map);
- size_t nRouters = map.size();
-
- HyperbolicRoutingCalculator calculator(nRouters, isDryRun, m_confParam.getRouterPrefix());
-
- calculator.calculatePath(map, *this, m_lsdb, m_confParam.getAdjacencyList());
+ calculateHyperbolicRoutingPath(map, *this, m_lsdb, m_confParam.getAdjacencyList(),
+ m_confParam.getRouterPrefix(), isDryRun);
if (!isDryRun) {
NLSR_LOG_DEBUG("Calling Update NPT With new Route");
diff --git a/tests/route/test-hyperbolic-calculator.cpp b/tests/route/test-routing-calculator-hyperbolic.cpp
similarity index 95%
rename from tests/route/test-hyperbolic-calculator.cpp
rename to tests/route/test-routing-calculator-hyperbolic.cpp
index 7d50298..73f0878 100644
--- a/tests/route/test-hyperbolic-calculator.cpp
+++ b/tests/route/test-routing-calculator-hyperbolic.cpp
@@ -19,7 +19,7 @@
* NLSR, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
*/
-#include "route/routing-table-calculator.hpp"
+#include "route/routing-calculator.hpp"
#include "adjacency-list.hpp"
#include "lsdb.hpp"
@@ -105,8 +105,7 @@
void runTest(const double& expectedCost)
{
- HyperbolicRoutingCalculator calculator(map.size(), false, ROUTER_A_NAME);
- calculator.calculatePath(map, routingTable, lsdb, adjacencies);
+ calculateHyperbolicRoutingPath(map, routingTable, lsdb, adjacencies, ROUTER_A_NAME, false);
RoutingTableEntry* entryB = routingTable.findRoutingTableEntry(ROUTER_B_NAME);
@@ -157,7 +156,7 @@
Lsdb& lsdb;
};
-BOOST_FIXTURE_TEST_SUITE(TestHyperbolicRoutingCalculator, HyperbolicCalculatorFixture)
+BOOST_FIXTURE_TEST_SUITE(TestRoutingCalculatorHyperbolic, HyperbolicCalculatorFixture)
BOOST_AUTO_TEST_CASE(Basic)
{
diff --git a/tests/route/test-link-state-calculator.cpp b/tests/route/test-routing-calculator-link-state.cpp
similarity index 94%
rename from tests/route/test-link-state-calculator.cpp
rename to tests/route/test-routing-calculator-link-state.cpp
index 40ed32f..dce29c5 100644
--- a/tests/route/test-link-state-calculator.cpp
+++ b/tests/route/test-routing-calculator-link-state.cpp
@@ -19,7 +19,7 @@
* NLSR, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
*/
-#include "route/routing-table-calculator.hpp"
+#include "route/routing-calculator.hpp"
#include "adjacency-list.hpp"
#include "adjacent.hpp"
@@ -113,12 +113,11 @@
Lsdb& lsdb;
};
-BOOST_FIXTURE_TEST_SUITE(TestLinkStateRoutingCalculator, LinkStateCalculatorFixture)
+BOOST_FIXTURE_TEST_SUITE(TestRoutingCalculatorLinkState, LinkStateCalculatorFixture)
BOOST_AUTO_TEST_CASE(Basic)
{
- LinkStateRoutingTableCalculator calculator(map.size());
- calculator.calculatePath(map, routingTable, conf, lsdb);
+ calculateLinkStateRoutingPath(map, routingTable, conf, lsdb);
RoutingTableEntry* entryB = routingTable.findRoutingTableEntry(ROUTER_B_NAME);
BOOST_REQUIRE(entryB != nullptr);
@@ -165,8 +164,7 @@
c->setLinkCost(higherLinkCost);
// Calculation should consider the link between B and C as having cost = higherLinkCost
- LinkStateRoutingTableCalculator calculator(map.size());
- calculator.calculatePath(map, routingTable, conf, lsdb);
+ calculateLinkStateRoutingPath(map, routingTable, conf, lsdb);
RoutingTableEntry* entryB = routingTable.findRoutingTableEntry(ROUTER_B_NAME);
BOOST_REQUIRE(entryB != nullptr);
@@ -213,8 +211,7 @@
c->setLinkCost(Adjacent::NON_ADJACENT_COST);
// Calculation should consider the link between B and C as down
- LinkStateRoutingTableCalculator calculator(map.size());
- calculator.calculatePath(map, routingTable, conf, lsdb);
+ calculateLinkStateRoutingPath(map, routingTable, conf, lsdb);
// Router A should be able to get to B through B but not through C
RoutingTableEntry* entryB = routingTable.findRoutingTableEntry(ROUTER_B_NAME);
@@ -267,8 +264,7 @@
b->setLinkCost(0);
// Calculation should consider 0 link-cost between B and C
- LinkStateRoutingTableCalculator calculator(map.size());
- calculator.calculatePath(map, routingTable, conf, lsdb);
+ calculateLinkStateRoutingPath(map, routingTable, conf, lsdb);
// Router A should be able to get to B through B and C
RoutingTableEntry* entryB = routingTable.findRoutingTableEntry(ROUTER_B_NAME);