31 #include <boost/lexical_cast.hpp>
32 #include <ndn-cxx/util/logger.hpp>
70 for (
auto lsaIt = lsaRange.first; lsaIt != lsaRange.second; ++lsaIt) {
71 auto adjLsa = std::static_pointer_cast<AdjLsa>(*lsaIt);
74 std::list<Adjacent> adl = adjLsa->getAdl().getAdjList();
76 for (
const auto& adjacent : adl) {
78 double cost = adjacent.getLinkCost();
80 if (row && col && *row <
static_cast<int32_t
>(
m_nRouters)
98 for (
size_t row = 0; row <
m_nRouters; ++row) {
99 for (
size_t col = 0; col <
m_nRouters; ++col) {
103 if (fromCost != toCost) {
106 if (toCost >= 0 && fromCost >= 0) {
108 correctedCost = std::max(toCost, fromCost);
111 NLSR_LOG_WARN(
"Cost between [" << row <<
"][" << col <<
"] and [" << col <<
"][" << row <<
112 "] are not the same (" << toCost <<
" != " << fromCost <<
"). " <<
113 "Correcting to cost: " << correctedCost);
125 if (!ndn_cxx_getLogger().isLevelEnabled(ndn::util::LogLevel::DEBUG)) {
130 std::string routerIndex;
131 std::string indexToNameMapping;
132 std::string lengthOfDash =
"--";
135 routerIndex += boost::lexical_cast<std::string>(i);
137 lengthOfDash +=
"--";
139 " Index:" + boost::lexical_cast<std::string>(i));
151 line += boost::lexical_cast<std::string>(
adjMatrix[i][j]);
155 line = boost::lexical_cast<std::string>(i) +
"|" + line;
163 for (
int i = 0; i < static_cast<int>(
m_nRouters); i++) {
180 if (
adjMatrix[sRouter][i] >= 0 && i !=
static_cast<size_t>(sRouter)) {
189 double* linkCosts,
int source)
194 if (
adjMatrix[source][i] >= 0 && i !=
static_cast<size_t>(source)) {
239 NLSR_LOG_DEBUG(
"LinkStateRoutingTableCalculator::calculatePath Called");
250 doDijkstraPathCalculation(*sourceRouter);
252 addAllLsNextHopsToRoutingTable(confParam.
getAdjacencyList(), rt, pMap, *sourceRouter);
261 for (
int i = 0 ; i <
vNoLink; i++) {
266 doDijkstraPathCalculation(*sourceRouter);
268 addAllLsNextHopsToRoutingTable(confParam.
getAdjacencyList(), rt, pMap, *sourceRouter);
279 LinkStateRoutingTableCalculator::doDijkstraPathCalculation(
int sourceRouter)
286 for (i = 0 ; i < static_cast<int>(
m_nRouters); i++) {
294 m_distance[sourceRouter] = 0;
295 sortQueueByDistance(Q, m_distance, head,
m_nRouters);
303 for (v = 0 ; v < static_cast<int>(
m_nRouters); v++) {
307 if (isNotExplored(Q, v, head + 1,
m_nRouters)) {
311 if (m_distance[u] +
adjMatrix[u][v] < m_distance[v]) {
313 m_distance[v] = m_distance[u] +
adjMatrix[u][v] ;
322 sortQueueByDistance(Q, m_distance, head,
m_nRouters);
329 LinkStateRoutingTableCalculator::addAllLsNextHopsToRoutingTable(AdjacencyList& adjacencies,
331 uint32_t sourceRouter)
333 NLSR_LOG_DEBUG(
"LinkStateRoutingTableCalculator::addAllNextHopsToRoutingTable Called");
335 int nextHopRouter = 0;
339 if (i != sourceRouter) {
342 nextHopRouter = getLsNextHop(i, sourceRouter);
347 double routeCost = m_distance[i];
349 auto nextHopRouterName = pMap.getRouterNameByMappingNo(nextHopRouter);
350 if (nextHopRouterName) {
351 std::string nextHopFace =
352 adjacencies.getAdjacent(*nextHopRouterName).getFaceUri().toString();
354 NextHop nh(nextHopFace, routeCost);
355 rt.addNextHop(*(pMap.getRouterNameByMappingNo(i)), nh);
363 LinkStateRoutingTableCalculator::getLsNextHop(
int dest,
int source)
368 dest = m_parent[dest];
370 if (dest != source) {
377 LinkStateRoutingTableCalculator::sortQueueByDistance(
int* Q,
379 int start,
int element)
381 for (
int i = start ; i < element ; i++) {
382 for (
int j = i + 1; j < element; j++) {
383 if (dist[Q[j]] < dist[Q[i]]) {
393 LinkStateRoutingTableCalculator::isNotExplored(
int* Q,
394 int u,
int start,
int element)
397 for (
int i = start; i < element; i++) {
407 LinkStateRoutingTableCalculator::allocateParent()
413 LinkStateRoutingTableCalculator::allocateDistance()
419 LinkStateRoutingTableCalculator::freeParent()
424 void LinkStateRoutingTableCalculator::freeDistance()
426 delete [] m_distance;
438 std::list<Adjacent> neighbors = adjacencies.
getAdjList();
439 for (std::list<Adjacent>::iterator adj = neighbors.begin(); adj != neighbors.end(); ++adj) {
443 NLSR_LOG_TRACE(adj->getName() <<
" is inactive; not using it as a nexthop");
447 ndn::Name srcRouterName = adj->getName();
450 if (srcRouterName == m_thisRouterName) {
454 std::string srcFaceUri = adj->getFaceUri().toString();
457 addNextHop(srcRouterName, srcFaceUri, 0, rt);
461 NLSR_LOG_WARN(adj->getName() <<
" does not exist in the router map!");
466 for (
int dest = 0; dest < static_cast<int>(m_nRouters); ++dest) {
468 if (thisRouter && dest != *thisRouter && dest != *src) {
471 if (destRouterName) {
472 double distance = getHyperbolicDistance(lsdb, srcRouterName, *destRouterName);
476 NLSR_LOG_WARN(
"Could not calculate hyperbolic distance from " << srcRouterName
477 <<
" to " << *destRouterName);
480 addNextHop(*destRouterName, srcFaceUri, distance, rt);
488 HyperbolicRoutingCalculator::getHyperbolicDistance(
Lsdb& lsdb, ndn::Name src, ndn::Name dest)
490 NLSR_LOG_TRACE(
"Calculating hyperbolic distance from " << src <<
" to " << dest);
498 if (srcLsa ==
nullptr || destLsa ==
nullptr) {
502 std::vector<double> srcTheta = srcLsa->getCorTheta();
503 std::vector<double> destTheta = destLsa->
getCorTheta();
505 double srcRadius = srcLsa->getCorRadius();
508 double diffTheta = calculateAngularDistance(srcTheta, destTheta);
516 distance = calculateHyperbolicDistance(srcRadius, destRadius, diffTheta);
518 NLSR_LOG_TRACE(
"Distance from " << src <<
" to " << dest <<
" is " << distance);
524 HyperbolicRoutingCalculator::calculateAngularDistance(std::vector<double> angleVectorI,
525 std::vector<double> angleVectorJ)
532 if (angleVectorI.size() != angleVectorJ.size()) {
538 if (angleVectorI.size() > 1) {
539 for (
unsigned int k = 0; k < angleVectorI.size() - 1; k++) {
540 if ((angleVectorI[k] > M_PI && angleVectorI[k] < 0.0) ||
541 (angleVectorJ[k] > M_PI && angleVectorJ[k] < 0.0)) {
548 if (angleVectorI[angleVectorI.size()-1] > 2.*M_PI ||
549 angleVectorI[angleVectorI.size()-1] < 0.0) {
554 if (angleVectorI[angleVectorI.size()-1] > 2.*M_PI ||
555 angleVectorI[angleVectorI.size()-1] < 0.0) {
561 double innerProduct = 0.0;
564 double x0i = std::cos(angleVectorI[0]);
565 double x0j = std::cos(angleVectorJ[0]);
568 double xni = std::sin(angleVectorI[angleVectorI.size() - 1]);
569 double xnj = std::sin(angleVectorJ[angleVectorJ.size() - 1]);
573 for (
unsigned int k = 0; k < angleVectorI.size() - 1; k++) {
574 xni *= std::sin(angleVectorI[k]);
575 xnj *= std::sin(angleVectorJ[k]);
577 innerProduct += (x0i * x0j) + (xni * xnj);
580 if (angleVectorI.size() > 1) {
581 for (
unsigned int m = 1; m < angleVectorI.size(); m++) {
583 double xmi = std::cos(angleVectorI[m]);
584 double xmj = std::cos(angleVectorJ[m]);
585 for (
unsigned int l = 0; l < m; l++) {
586 xmi *= std::sin(angleVectorI[l]);
587 xmj *= std::sin(angleVectorJ[l]);
589 innerProduct += xmi * xmj;
595 return std::acos(innerProduct);
599 HyperbolicRoutingCalculator::calculateHyperbolicDistance(
double rI,
double rJ,
609 if (deltaTheta <= 0.0 || rI <= 0.0 || rJ <= 0.0) {
611 NLSR_LOG_ERROR(
"Please make sure that no two nodes have the exact same HR coordinates");
615 double xij = (1. / zeta) * std::acosh(std::cosh(zeta*rI) * std::cosh(zeta*rJ) -
616 std::sinh(zeta*rI)*std::sinh(zeta*rJ)*std::cos(deltaTheta));
621 HyperbolicRoutingCalculator::addNextHop(ndn::Name dest, std::string faceUri,
625 hop.setHyperbolic(
true);
627 NLSR_LOG_TRACE(
"Calculated " << hop <<
" for destination: " << dest);
630 rt.addNextHopToDryTable(dest, hop);
633 rt.addNextHop(dest, hop);
Data abstraction for AdjLsa AdjacencyLsa := ADJACENCY-LSA-TYPE TLV-LENGTH Lsa Adjacency*.
std::list< Adjacent > & getAdjList()
static constexpr double NON_ADJACENT_COST
A class to house all the configuration parameters for NLSR.
const ndn::Name & getRouterPrefix() const
AdjacencyList & getAdjacencyList()
uint32_t getMaxFacesPerPrefix() const
Data abstraction for CoordinateLsa CoordinateLsa := COORDINATE-LSA-TYPE TLV-LENGTH Lsa HyperbolicRadi...
double getCorRadius() const
const std::vector< double > getCorTheta() const
void calculatePath(Map &map, RoutingTable &rt, Lsdb &lsdb, AdjacencyList &adjacencies)
void calculatePath(Map &pMap, RoutingTable &rt, ConfParameter &confParam, const Lsdb &lsdb)
std::shared_ptr< T > findLsa(const ndn::Name &router) const
std::pair< LsaContainer::index< Lsdb::byType >::type::iterator, LsaContainer::index< Lsdb::byType >::type::iterator > getLsdbIterator() const
std::optional< int32_t > getMappingNoByRouterName(const ndn::Name &rName)
std::optional< ndn::Name > getRouterNameByMappingNo(int32_t mn) const
void initMatrix()
set NON_ADJACENT_COST i.e. -12345 to every cell of the matrix to ensure that the memory is safe....
int getNumOfLinkfromAdjMatrix(int sRouter)
Returns how many links a router in the matrix has.
void adjustAdMatrix(int source, int link, double linkCost)
Adjust a link cost in the adj. matrix.
void allocateAdjMatrix()
Allocate the space needed for the adj. matrix.
void makeAdjMatrix(const Lsdb &lsdb, Map &pMap)
Constructs an adj. matrix to calculate with.
void writeAdjMatrixLog(const Map &map) const
Writes a formated adjacent matrix to DEBUG log.
void getLinksFromAdjMatrix(int *links, double *linkCosts, int source)
Populates temp. variables with the link costs for some router.
Copyright (c) 2014-2018, The University of Memphis, Regents of the University of California.
#define NLSR_LOG_DEBUG(x)
#define INIT_LOGGER(name)
#define NLSR_LOG_ERROR(x)
#define NLSR_LOG_TRACE(x)
Copyright (c) 2014-2020, The University of Memphis, Regents of the University of California.
constexpr int NO_NEXT_HOP
constexpr double INF_DISTANCE
constexpr int NO_MAPPING_NUM
constexpr int EMPTY_PARENT
constexpr double UNKNOWN_RADIUS
constexpr double UNKNOWN_DISTANCE