30 #include <boost/math/constants/constants.hpp> 31 #include <ndn-cxx/util/logger.hpp> 62 for (
const auto& adjLsa : adjLsaList) {
65 std::list<Adjacent> adl = adjLsa.getAdl().getAdjList();
67 for (
const auto& adjacent : adl) {
69 double cost = adjacent.getLinkCost();
71 if (row && col && *row < static_cast<int32_t>(
m_nRouters)
90 for (
size_t row = 0; row <
m_nRouters; ++row) {
91 for (
size_t col = 0; col <
m_nRouters; ++col) {
95 if (fromCost != toCost) {
96 double correctedCost = 0.0;
98 if (toCost != 0 && fromCost != 0) {
100 correctedCost = std::max(toCost, fromCost);
103 NLSR_LOG_WARN(
"Cost between [" << row <<
"][" << col <<
"] and [" << col <<
"][" << row <<
104 "] are not the same (" << toCost <<
" != " << fromCost <<
"). " <<
105 "Correcting to cost: " << correctedCost);
117 if (!ndn_cxx_getLogger().isLevelEnabled(ndn::util::LogLevel::DEBUG)) {
122 std::string routerIndex;
123 std::string indexToNameMapping;
124 std::string lengthOfDash =
"--";
127 routerIndex += boost::lexical_cast<std::string>(i);
129 lengthOfDash +=
"--";
131 " Index:" + boost::lexical_cast<std::string>(i));
139 line += boost::lexical_cast<std::string>(
adjMatrix[i][j]);
142 line = boost::lexical_cast<std::string>(i) +
"|" + line;
150 for (
int i = 0; i < static_cast<int>(
m_nRouters); i++) {
224 const std::list<AdjLsa>& adjLsaList)
226 NLSR_LOG_DEBUG(
"LinkStateRoutingTableCalculator::calculatePath Called");
231 ndn::optional<int32_t> sourceRouter =
238 doDijkstraPathCalculation(*sourceRouter);
240 addAllLsNextHopsToRoutingTable(confParam.
getAdjacencyList(), rt, pMap, *sourceRouter);
249 for (
int i = 0 ; i <
vNoLink; i++) {
254 doDijkstraPathCalculation(*sourceRouter);
256 addAllLsNextHopsToRoutingTable(confParam.
getAdjacencyList(), rt, pMap, *sourceRouter);
267 LinkStateRoutingTableCalculator::doDijkstraPathCalculation(
int sourceRouter)
274 for (i = 0 ; i < static_cast<int>(
m_nRouters); i++) {
275 m_parent[i] = EMPTY_PARENT;
277 m_distance[i] = INF_DISTANCE;
280 if (sourceRouter != NO_MAPPING_NUM) {
282 m_distance[sourceRouter] = 0;
283 sortQueueByDistance(Q, m_distance, head,
m_nRouters);
287 if (m_distance[u] == INF_DISTANCE) {
291 for (v = 0 ; v < static_cast<int>(
m_nRouters); v++) {
295 if (isNotExplored(Q, v, head + 1,
m_nRouters)) {
299 if (m_distance[u] +
adjMatrix[u][v] < m_distance[v]) {
301 m_distance[v] = m_distance[u] +
adjMatrix[u][v] ;
310 sortQueueByDistance(Q, m_distance, head,
m_nRouters);
317 LinkStateRoutingTableCalculator::addAllLsNextHopsToRoutingTable(
AdjacencyList& adjacencies,
319 uint32_t sourceRouter)
321 NLSR_LOG_DEBUG(
"LinkStateRoutingTableCalculator::addAllNextHopsToRoutingTable Called");
323 int nextHopRouter = 0;
327 if (i != sourceRouter) {
330 nextHopRouter = getLsNextHop(i, sourceRouter);
333 if (nextHopRouter != NO_NEXT_HOP) {
336 double routeCost = m_distance[i];
339 if (nextHopRouterName) {
340 std::string nextHopFace =
343 NextHop nh(nextHopFace, routeCost);
353 LinkStateRoutingTableCalculator::getLsNextHop(
int dest,
int source)
355 int nextHop = NO_NEXT_HOP;
356 while (m_parent[dest] != EMPTY_PARENT) {
358 dest = m_parent[dest];
360 if (dest != source) {
361 nextHop = NO_NEXT_HOP;
367 LinkStateRoutingTableCalculator::sortQueueByDistance(
int* Q,
369 int start,
int element)
371 for (
int i = start ; i < element ; i++) {
372 for (
int j = i + 1; j < element; j++) {
373 if (dist[Q[j]] < dist[Q[i]]) {
383 LinkStateRoutingTableCalculator::isNotExplored(
int* Q,
384 int u,
int start,
int element)
387 for (
int i = start; i < element; i++) {
397 LinkStateRoutingTableCalculator::allocateParent()
403 LinkStateRoutingTableCalculator::allocateDistance()
409 LinkStateRoutingTableCalculator::freeParent()
414 void LinkStateRoutingTableCalculator::freeDistance()
416 delete [] m_distance;
419 const double HyperbolicRoutingCalculator::MATH_PI = boost::math::constants::pi<double>();
421 const double HyperbolicRoutingCalculator::UNKNOWN_DISTANCE = -1.0;
422 const double HyperbolicRoutingCalculator::UNKNOWN_RADIUS = -1.0;
433 std::list<Adjacent> neighbors = adjacencies.
getAdjList();
434 for (std::list<Adjacent>::iterator adj = neighbors.begin(); adj != neighbors.end(); ++adj) {
438 NLSR_LOG_TRACE(adj->getName() <<
" is inactive; not using it as a nexthop");
442 ndn::Name srcRouterName = adj->getName();
445 if (srcRouterName == m_thisRouterName) {
449 std::string srcFaceUri = adj->getFaceUri().toString();
452 addNextHop(srcRouterName, srcFaceUri, 0, rt);
457 NLSR_LOG_WARN(adj->getName() <<
" does not exist in the router map!");
462 for (
int dest = 0; dest < static_cast<int>(
m_nRouters); ++dest) {
464 if (thisRouter && dest != *thisRouter && dest != *src) {
467 if (destRouterName) {
468 double distance = getHyperbolicDistance(lsdb, srcRouterName, *destRouterName);
471 if (distance == UNKNOWN_DISTANCE) {
472 NLSR_LOG_WARN(
"Could not calculate hyperbolic distance from " << srcRouterName <<
" to " <<
477 addNextHop(*destRouterName, srcFaceUri, distance, rt);
485 HyperbolicRoutingCalculator::getHyperbolicDistance(
Lsdb& lsdb, ndn::Name src, ndn::Name dest)
487 NLSR_LOG_TRACE(
"Calculating hyperbolic distance from " << src <<
" to " << dest);
489 double distance = UNKNOWN_DISTANCE;
491 ndn::Name srcLsaKey = src;
496 ndn::Name destLsaKey = dest;
502 if (srcLsa ==
nullptr || destLsa ==
nullptr) {
503 return UNKNOWN_DISTANCE;
506 std::vector<double> srcTheta = srcLsa->
getCorTheta();
507 std::vector<double> destTheta = destLsa->
getCorTheta();
512 double diffTheta = calculateAngularDistance(srcTheta, destTheta);
514 if (srcRadius == UNKNOWN_RADIUS || destRadius == UNKNOWN_RADIUS ||
515 diffTheta == UNKNOWN_DISTANCE) {
516 return UNKNOWN_DISTANCE;
520 distance = calculateHyperbolicDistance(srcRadius, destRadius, diffTheta);
522 NLSR_LOG_TRACE(
"Distance from " << src <<
" to " << dest <<
" is " << distance);
528 HyperbolicRoutingCalculator::calculateAngularDistance(std::vector<double> angleVectorI,
529 std::vector<double> angleVectorJ)
536 if (angleVectorI.size() != angleVectorJ.size()) {
538 return UNKNOWN_DISTANCE;
542 if (angleVectorI.size() > 1) {
543 for (
unsigned int k = 0; k < angleVectorI.size() - 1; k++) {
544 if ((angleVectorI[k] > M_PI && angleVectorI[k] < 0.0) ||
545 (angleVectorJ[k] > M_PI && angleVectorJ[k] < 0.0)) {
547 return UNKNOWN_DISTANCE;
551 if (angleVectorI[angleVectorI.size()-1] > 2.*M_PI ||
552 angleVectorI[angleVectorI.size()-1] < 0.0) {
554 return UNKNOWN_DISTANCE;
557 if (angleVectorI[angleVectorI.size()-1] > 2.*M_PI ||
558 angleVectorI[angleVectorI.size()-1] < 0.0) {
560 return UNKNOWN_DISTANCE;
564 double innerProduct = 0.0;
567 double x0i = std::cos(angleVectorI[0]);
568 double x0j = std::cos(angleVectorJ[0]);
571 double xni = std::sin(angleVectorI[angleVectorI.size() - 1]);
572 double xnj = std::sin(angleVectorJ[angleVectorJ.size() - 1]);
576 for (
unsigned int k = 0; k < angleVectorI.size() - 1; k++) {
577 xni *= std::sin(angleVectorI[k]);
578 xnj *= std::sin(angleVectorJ[k]);
580 innerProduct += (x0i * x0j) + (xni * xnj);
583 if (angleVectorI.size() > 1) {
584 for (
unsigned int m = 1; m < angleVectorI.size(); m++) {
586 double xmi = std::cos(angleVectorI[m]);
587 double xmj = std::cos(angleVectorJ[m]);
588 for (
unsigned int l = 0; l < m; l++) {
589 xmi *= std::sin(angleVectorI[l]);
590 xmj *= std::sin(angleVectorJ[l]);
592 innerProduct += xmi * xmj;
598 return std::acos(innerProduct);
602 HyperbolicRoutingCalculator::calculateHyperbolicDistance(
double rI,
double rJ,
605 if (deltaTheta == UNKNOWN_DISTANCE) {
606 return UNKNOWN_DISTANCE;
612 if (deltaTheta <= 0.0 || rI <= 0.0 || rJ <= 0.0) {
614 NLSR_LOG_ERROR(
"Please make sure that no two nodes have the exact same HR coordinates");
615 return UNKNOWN_DISTANCE;
618 double xij = (1. / zeta) * std::acosh(std::cosh(zeta*rI) * std::cosh(zeta*rJ) -
619 std::sinh(zeta*rI)*std::sinh(zeta*rJ)*std::cos(deltaTheta));
624 HyperbolicRoutingCalculator::addNextHop(ndn::Name dest, std::string faceUri,
630 NLSR_LOG_TRACE(
"Calculated " << hop <<
" for destination: " << dest);
void writeAdjMatrixLog(const Map &map) const
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.
ndn::optional< ndn::Name > getRouterNameByMappingNo(int32_t mn) const
void calculatePath(Map &map, RoutingTable &rt, Lsdb &lsdb, AdjacencyList &adjacencies)
const ndn::FaceUri & getFaceUri() const
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.
AdjacencyList & getAdjacencyList()
ndn::optional< int32_t > getMappingNoByRouterName(const ndn::Name &rName)
#define NLSR_LOG_DEBUG(x)
const ndn::Name & getRouterPrefix() const
Copyright (c) 2014-2018, The University of Memphis, Regents of the University of California.
Adjacent getAdjacent(const ndn::Name &adjName)
#define INIT_LOGGER(name)
void makeAdjMatrix(const std::list< AdjLsa > &adjLsaList, Map &pMap)
Constructs an adj. matrix to calculate with.
uint32_t getMaxFacesPerPrefix() const
void initMatrix()
Zero every cell of the matrix to ensure that the memory is safe.
CoordinateLsa * findCoordinateLsa(const ndn::Name &key)
Finds a cor. LSA in the LSDB.
#define NLSR_LOG_ERROR(x)
Copyright (c) 2014-2018, The University of Memphis, Regents of the University of California, Arizona Board of Regents.
void calculatePath(Map &pMap, RoutingTable &rt, ConfParameter &confParam, const std::list< AdjLsa > &adjLsaList)
const std::vector< double > getCorTheta() const
void addNextHopToDryTable(const ndn::Name &destRouter, NextHop &nh)
Adds a next hop to a routing table entry in a dry run scenario.
int getNumOfLinkfromAdjMatrix(int sRouter)
Returns how many links a router in the matrix has.
void setHyperbolic(bool b)
void addNextHop(const ndn::Name &destRouter, NextHop &nh)
Adds a next hop to a routing table entry.
std::list< Adjacent > & getAdjList()
#define NLSR_LOG_TRACE(x)
double getCorRadius() const