routing-table-calculator.hpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2014-2020, The University of Memphis,
4  * Regents of the University of California
5  *
6  * This file is part of NLSR (Named-data Link State Routing).
7  * See AUTHORS.md for complete list of NLSR authors and contributors.
8  *
9  * NLSR is free software: you can redistribute it and/or modify it under the terms
10  * of the GNU General Public License as published by the Free Software Foundation,
11  * either version 3 of the License, or (at your option) any later version.
12  *
13  * NLSR is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
14  * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
15  * PURPOSE. See the GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License along with
18  * NLSR, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
19  */
20 
21 #ifndef NLSR_ROUTING_TABLE_CALCULATOR_HPP
22 #define NLSR_ROUTING_TABLE_CALCULATOR_HPP
23 
24 #include "common.hpp"
25 #include "lsa/lsa.hpp"
26 #include "lsa/adj-lsa.hpp"
27 #include "lsdb.hpp"
28 #include "conf-parameter.hpp"
29 
30 #include <list>
31 #include <boost/cstdint.hpp>
32 
33 #include <ndn-cxx/name.hpp>
34 
35 namespace nlsr {
36 
37 class Map;
38 class RoutingTable;
39 
41 {
42 public:
43  RoutingTableCalculator(size_t nRouters)
44  {
45  m_nRouters = nRouters;
46  }
47 
48 protected:
50  void
52 
55  void
56  initMatrix();
57 
62  void
63  makeAdjMatrix(const Lsdb& lsdb, Map& pMap);
64 
68  void
69  writeAdjMatrixLog(const Map& map) const;
70 
74  int
75  getNumOfLinkfromAdjMatrix(int sRouter);
76 
77  void
78  freeAdjMatrix();
84  void
85  adjustAdMatrix(int source, int link, double linkCost);
86 
98  void
99  getLinksFromAdjMatrix(int* links, double* linkCosts, int source);
100 
102  void
103  allocateLinks();
104 
105  void
107 
108  void
109  freeLinks();
110 
111  void
112  freeLinksCosts();
113 
114  void
115  setNoLink(int nl)
116  {
117  vNoLink = nl;
118  }
119 
120 protected:
121  double** adjMatrix;
122  size_t m_nRouters;
123 
124  int vNoLink;
125  int* links;
126  double* linkCosts;
127 
128 };
129 
131 {
132 public:
134  : RoutingTableCalculator(nRouters)
135  {
136  }
137 
138  void
139  calculatePath(Map& pMap, RoutingTable& rt, ConfParameter& confParam,
140  const Lsdb& lsdb);
141 
142 private:
146  void
147  doDijkstraPathCalculation(int sourceRouter);
148 
161  void
162  sortQueueByDistance(int* Q, double* dist, int start, int element);
163 
170  int
171  isNotExplored(int* Q, int u, int start, int element);
172 
173  void
174  addAllLsNextHopsToRoutingTable(AdjacencyList& adjacencies, RoutingTable& rt,
175  Map& pMap, uint32_t sourceRouter);
176 
181  int
182  getLsNextHop(int dest, int source);
183 
184  void
185  allocateParent();
186 
187  void
188  allocateDistance();
189 
190  void
191  freeParent();
192 
193  void
194  freeDistance();
195 
196 private:
197  int* m_parent;
198  double* m_distance;
199 
200  static const int EMPTY_PARENT;
201  static const double INF_DISTANCE;
202  static const int NO_MAPPING_NUM;
203 public:
204  static const int NO_NEXT_HOP;
205 
206 };
207 
208 class AdjacencyList;
209 class Lsdb;
210 
212 {
213 public:
214  HyperbolicRoutingCalculator(size_t nRouters, bool isDryRun, ndn::Name thisRouterName)
215  : m_nRouters(nRouters)
216  , m_isDryRun(isDryRun)
217  , m_thisRouterName(thisRouterName)
218  {
219  }
220 
221  void
222  calculatePath(Map& map, RoutingTable& rt, Lsdb& lsdb, AdjacencyList& adjacencies);
223 
224 private:
225  double
226  getHyperbolicDistance(Lsdb& lsdb, ndn::Name src, ndn::Name dest);
227 
228  void
229  addNextHop(ndn::Name destinationRouter, std::string faceUri, double cost, RoutingTable& rt);
230 
231  double
232  calculateHyperbolicDistance(double rI, double rJ, double deltaTheta);
233 
234  double
235  calculateAngularDistance(std::vector<double> angleVectorI,
236  std::vector<double> angleVectorJ);
237 
238 private:
239  const size_t m_nRouters;
240  const bool m_isDryRun;
241  const ndn::Name m_thisRouterName;
242 
243  static const double MATH_PI;
244  static const double UNKNOWN_DISTANCE;
245  static const double UNKNOWN_RADIUS;
246 };
247 
248 } // namespace nlsr
249 
250 #endif // NLSR_ROUTING_TABLE_CALCULATOR_HPP
A class to house all the configuration parameters for NLSR.
void getLinksFromAdjMatrix(int *links, double *linkCosts, int source)
Populates temp. variables with the link costs for some router.
void allocateAdjMatrix()
Allocate the space needed for the adj. matrix.
void adjustAdMatrix(int source, int link, double linkCost)
Adjust a link cost in the adj. matrix.
Copyright (c) 2014-2018, The University of Memphis, Regents of the University of California.
void initMatrix()
set NON_ADJACENT_COST i.e. -12345 to every cell of the matrix to ensure that the memory is safe...
void writeAdjMatrixLog(const Map &map) const
Writes a formated adjacent matrix to DEBUG log.
void makeAdjMatrix(const Lsdb &lsdb, Map &pMap)
Constructs an adj. matrix to calculate with.
Copyright (c) 2014-2020, The University of Memphis, Regents of the University of California, Arizona Board of Regents.
HyperbolicRoutingCalculator(size_t nRouters, bool isDryRun, ndn::Name thisRouterName)
int getNumOfLinkfromAdjMatrix(int sRouter)
Returns how many links a router in the matrix has.