routing-calculator-hyperbolic.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2014-2024, The University of Memphis,
4  * Regents of the University of California,
5  * Arizona Board of Regents.
6  *
7  * This file is part of NLSR (Named-data Link State Routing).
8  * See AUTHORS.md for complete list of NLSR authors and contributors.
9  *
10  * NLSR is free software: you can redistribute it and/or modify it under the terms
11  * of the GNU General Public License as published by the Free Software Foundation,
12  * either version 3 of the License, or (at your option) any later version.
13  *
14  * NLSR is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
15  * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
16  * PURPOSE. See the GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License along with
19  * NLSR, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
20  */
21 
22 #include "routing-calculator.hpp"
23 #include "name-map.hpp"
24 #include "nexthop.hpp"
25 
26 #include "adjacent.hpp"
27 #include "logger.hpp"
28 #include "nlsr.hpp"
29 
30 #include <cmath>
31 
32 namespace nlsr {
33 
34 INIT_LOGGER(route.RoutingCalculatorHyperbolic);
35 
36 class HyperbolicRoutingCalculator
37 {
38 public:
39  HyperbolicRoutingCalculator(size_t nRouters, bool isDryRun, ndn::Name thisRouterName)
40  : m_nRouters(nRouters)
41  , m_isDryRun(isDryRun)
42  , m_thisRouterName(thisRouterName)
43  {
44  }
45 
46  void
47  calculatePath(NameMap& map, RoutingTable& rt, Lsdb& lsdb, AdjacencyList& adjacencies);
48 
49 private:
50  double
51  getHyperbolicDistance(Lsdb& lsdb, ndn::Name src, ndn::Name dest);
52 
53  void
54  addNextHop(const ndn::Name& destinationRouter, const ndn::FaceUri& faceUri, double cost, RoutingTable& rt);
55 
56  double
57  calculateHyperbolicDistance(double rI, double rJ, double deltaTheta);
58 
59  double
60  calculateAngularDistance(std::vector<double> angleVectorI,
61  std::vector<double> angleVectorJ);
62 
63 private:
64  const size_t m_nRouters;
65  const bool m_isDryRun;
66  const ndn::Name m_thisRouterName;
67 };
68 
69 constexpr double UNKNOWN_DISTANCE = -1.0;
70 constexpr double UNKNOWN_RADIUS = -1.0;
71 
72 void
73 HyperbolicRoutingCalculator::calculatePath(NameMap& map, RoutingTable& rt,
74  Lsdb& lsdb, AdjacencyList& adjacencies)
75 {
76  NLSR_LOG_TRACE("Calculating hyperbolic paths");
77 
78  auto thisRouter = map.getMappingNoByRouterName(m_thisRouterName);
79 
80  // Iterate over directly connected neighbors
81  std::list<Adjacent> neighbors = adjacencies.getAdjList();
82  for (auto adj = neighbors.begin(); adj != neighbors.end(); ++adj) {
83 
84  // Don't calculate nexthops using an inactive router
85  if (adj->getStatus() == Adjacent::STATUS_INACTIVE) {
86  NLSR_LOG_TRACE(adj->getName() << " is inactive; not using it as a nexthop");
87  continue;
88  }
89 
90  ndn::Name srcRouterName = adj->getName();
91 
92  // Don't calculate nexthops for this router to other routers
93  if (srcRouterName == m_thisRouterName) {
94  continue;
95  }
96 
97  // Install nexthops for this router to the neighbor; direct neighbors have a 0 cost link
98  addNextHop(srcRouterName, adj->getFaceUri(), 0, rt);
99 
100  auto src = map.getMappingNoByRouterName(srcRouterName);
101  if (!src) {
102  NLSR_LOG_WARN(adj->getName() << " does not exist in the router map!");
103  continue;
104  }
105 
106  // Get hyperbolic distance from direct neighbor to every other router
107  for (int dest = 0; dest < static_cast<int>(m_nRouters); ++dest) {
108  // Don't calculate nexthops to this router or from a router to itself
109  if (thisRouter && dest != *thisRouter && dest != *src) {
110 
111  auto destRouterName = map.getRouterNameByMappingNo(dest);
112  if (destRouterName) {
113  double distance = getHyperbolicDistance(lsdb, srcRouterName, *destRouterName);
114 
115  // Could not compute distance
116  if (distance == UNKNOWN_DISTANCE) {
117  NLSR_LOG_WARN("Could not calculate hyperbolic distance from " << srcRouterName
118  << " to " << *destRouterName);
119  continue;
120  }
121  addNextHop(*destRouterName, adj->getFaceUri(), distance, rt);
122  }
123  }
124  }
125  }
126 }
127 
128 double
129 HyperbolicRoutingCalculator::getHyperbolicDistance(Lsdb& lsdb, ndn::Name src, ndn::Name dest)
130 {
131  NLSR_LOG_TRACE("Calculating hyperbolic distance from " << src << " to " << dest);
132 
133  double distance = UNKNOWN_DISTANCE;
134 
135  auto srcLsa = lsdb.findLsa<CoordinateLsa>(src);
136  auto destLsa = lsdb.findLsa<CoordinateLsa>(dest);
137 
138  // Coordinate LSAs do not exist for these routers
139  if (srcLsa == nullptr || destLsa == nullptr) {
140  return UNKNOWN_DISTANCE;
141  }
142 
143  std::vector<double> srcTheta = srcLsa->getTheta();
144  std::vector<double> destTheta = destLsa->getTheta();
145 
146  double srcRadius = srcLsa->getRadius();
147  double destRadius = destLsa->getRadius();
148 
149  double diffTheta = calculateAngularDistance(srcTheta, destTheta);
150 
151  if (srcRadius == UNKNOWN_RADIUS || destRadius == UNKNOWN_RADIUS ||
152  diffTheta == UNKNOWN_DISTANCE) {
153  return UNKNOWN_DISTANCE;
154  }
155 
156  // double r_i, double r_j, double delta_theta, double zeta = 1 (default)
157  distance = calculateHyperbolicDistance(srcRadius, destRadius, diffTheta);
158 
159  NLSR_LOG_TRACE("Distance from " << src << " to " << dest << " is " << distance);
160 
161  return distance;
162 }
163 
164 double
165 HyperbolicRoutingCalculator::calculateAngularDistance(std::vector<double> angleVectorI,
166  std::vector<double> angleVectorJ)
167 {
168  // It is not possible for angle vector size to be zero as ensured by conf-file-processor
169 
170  // https://en.wikipedia.org/wiki/N-sphere#Spherical_coordinates
171 
172  // Check if two vector lengths are the same
173  if (angleVectorI.size() != angleVectorJ.size()) {
174  NLSR_LOG_ERROR("Angle vector sizes do not match");
175  return UNKNOWN_DISTANCE;
176  }
177 
178  // Check if all angles are within the [0, PI] and [0, 2PI] ranges
179  if (angleVectorI.size() > 1) {
180  for (unsigned int k = 0; k < angleVectorI.size() - 1; k++) {
181  if ((angleVectorI[k] > M_PI && angleVectorI[k] < 0.0) ||
182  (angleVectorJ[k] > M_PI && angleVectorJ[k] < 0.0)) {
183  NLSR_LOG_ERROR("Angle outside [0, PI]");
184  return UNKNOWN_DISTANCE;
185  }
186  }
187  }
188 
189  if (angleVectorI[angleVectorI.size()-1] > 2.*M_PI ||
190  angleVectorI[angleVectorI.size()-1] < 0.0) {
191  NLSR_LOG_ERROR("Angle not within [0, 2PI]");
192  return UNKNOWN_DISTANCE;
193  }
194 
195  if (angleVectorI[angleVectorI.size()-1] > 2.*M_PI ||
196  angleVectorI[angleVectorI.size()-1] < 0.0) {
197  NLSR_LOG_ERROR("Angle not within [0, 2PI]");
198  return UNKNOWN_DISTANCE;
199  }
200 
201  // deltaTheta = arccos(vectorI . vectorJ) -> do the inner product
202  double innerProduct = 0.0;
203 
204  // Calculate x0 of the vectors
205  double x0i = std::cos(angleVectorI[0]);
206  double x0j = std::cos(angleVectorJ[0]);
207 
208  // Calculate xn of the vectors
209  double xni = std::sin(angleVectorI[angleVectorI.size() - 1]);
210  double xnj = std::sin(angleVectorJ[angleVectorJ.size() - 1]);
211 
212  // Do the aggregation of the (n-1) coordinates (if there is more than one angle)
213  // i.e contraction of all (n-1)-dimensional angular coordinates to one variable
214  for (unsigned int k = 0; k < angleVectorI.size() - 1; k++) {
215  xni *= std::sin(angleVectorI[k]);
216  xnj *= std::sin(angleVectorJ[k]);
217  }
218  innerProduct += (x0i * x0j) + (xni * xnj);
219 
220  // If d > 1
221  if (angleVectorI.size() > 1) {
222  for (unsigned int m = 1; m < angleVectorI.size(); m++) {
223  // calculate euclidean coordinates given the angles and assuming R_sphere = 1
224  double xmi = std::cos(angleVectorI[m]);
225  double xmj = std::cos(angleVectorJ[m]);
226  for (unsigned int l = 0; l < m; l++) {
227  xmi *= std::sin(angleVectorI[l]);
228  xmj *= std::sin(angleVectorJ[l]);
229  }
230  innerProduct += xmi * xmj;
231  }
232  }
233 
234  // ArcCos of the inner product gives the angular distance
235  // between two points on a d-dimensional sphere
236  return std::acos(innerProduct);
237 }
238 
239 double
240 HyperbolicRoutingCalculator::calculateHyperbolicDistance(double rI, double rJ,
241  double deltaTheta)
242 {
243  if (deltaTheta == UNKNOWN_DISTANCE) {
244  return UNKNOWN_DISTANCE;
245  }
246 
247  // Usually, we set zeta = 1 in all experiments
248  double zeta = 1;
249 
250  if (deltaTheta <= 0.0 || rI <= 0.0 || rJ <= 0.0) {
251  NLSR_LOG_ERROR("Delta theta or rI or rJ is <= 0");
252  NLSR_LOG_ERROR("Please make sure that no two nodes have the exact same HR coordinates");
253  return UNKNOWN_DISTANCE;
254  }
255 
256  double xij = (1. / zeta) * std::acosh(std::cosh(zeta*rI) * std::cosh(zeta*rJ) -
257  std::sinh(zeta*rI)*std::sinh(zeta*rJ)*std::cos(deltaTheta));
258  return xij;
259 }
260 
261 void
262 HyperbolicRoutingCalculator::addNextHop(const ndn::Name& dest, const ndn::FaceUri& faceUri,
263  double cost, RoutingTable& rt)
264 {
265  NextHop hop(faceUri, cost);
266  hop.setHyperbolic(true);
267 
268  NLSR_LOG_TRACE("Calculated " << hop << " for destination: " << dest);
269 
270  if (m_isDryRun) {
271  rt.addNextHopToDryTable(dest, hop);
272  }
273  else {
274  rt.addNextHop(dest, hop);
275  }
276 }
277 
278 void
280  AdjacencyList& adjacencies, ndn::Name thisRouterName,
281  bool isDryRun)
282 {
283  HyperbolicRoutingCalculator calculator(map.size(), isDryRun, thisRouterName);
284  calculator.calculatePath(map, rt, lsdb, adjacencies);
285 }
286 
287 } // namespace nlsr
std::list< Adjacent > & getAdjList()
Assigning numbers to router names.
Definition: name-map.hpp:46
std::optional< ndn::Name > getRouterNameByMappingNo(int32_t mn) const
Find router name by its mapping number.
Definition: name-map.cpp:37
std::optional< int32_t > getMappingNoByRouterName(const ndn::Name &rtrName) const
Find mapping number of a router name.
Definition: name-map.cpp:47
size_t size() const
Return number of entries in this container.
Definition: name-map.hpp:120
Copyright (c) 2014-2018, The University of Memphis, Regents of the University of California.
#define INIT_LOGGER(name)
Definition: logger.hpp:35
#define NLSR_LOG_WARN(x)
Definition: logger.hpp:40
#define NLSR_LOG_ERROR(x)
Definition: logger.hpp:41
#define NLSR_LOG_TRACE(x)
Definition: logger.hpp:37
@ RoutingTable
Definition: tlv-nlsr.hpp:47
@ CoordinateLsa
Definition: tlv-nlsr.hpp:37
Copyright (c) 2014-2020, The University of Memphis, Regents of the University of California.
void calculateHyperbolicRoutingPath(NameMap &map, RoutingTable &rt, Lsdb &lsdb, AdjacencyList &adjacencies, ndn::Name thisRouterName, bool isDryRun)
constexpr double UNKNOWN_RADIUS
constexpr double UNKNOWN_DISTANCE