31 #include <boost/math/constants/constants.hpp> 32 #include <ndn-cxx/util/logger.hpp> 64 for (std::list<AdjLsa>::iterator it = adjLsdb.begin(); it != adjLsdb.end() ; it++) {
69 std::list<Adjacent> adl = (*it).getAdl().getAdjList();
71 for (std::list<Adjacent>::iterator itAdl = adl.begin(); itAdl != adl.end() ; itAdl++) {
74 double cost = (*itAdl).getLinkCost();
76 if (row && col && *row < static_cast<int32_t>(
m_nRouters)
95 for (
size_t row = 0; row <
m_nRouters; ++row) {
96 for (
size_t col = 0; col <
m_nRouters; ++col) {
100 if (fromCost != toCost) {
101 double correctedCost = 0.0;
103 if (toCost != 0 && fromCost != 0) {
105 correctedCost = std::max(toCost, fromCost);
108 NLSR_LOG_WARN(
"Cost between [" << row <<
"][" << col <<
"] and [" << col <<
"][" << row <<
109 "] are not the same (" << toCost <<
" != " << fromCost <<
"). " <<
110 "Correcting to cost: " << correctedCost);
122 if (!getNdnCxxLogger().isLevelEnabled(ndn::util::LogLevel::DEBUG)) {
127 std::string routerIndex;
128 std::string indexToNameMapping;
129 std::string lengthOfDash =
"--";
132 routerIndex += boost::lexical_cast<std::string>(i);
134 lengthOfDash +=
"--";
136 "Index:" + boost::lexical_cast<std::string>(i));
144 line += boost::lexical_cast<std::string>(
adjMatrix[i][j]);
147 line = boost::lexical_cast<std::string>(i) +
"|" + line;
155 for (
int i = 0; i < static_cast<int>(
m_nRouters); i++) {
230 NLSR_LOG_DEBUG(
"LinkStateRoutingTableCalculator::calculatePath Called");
235 ndn::optional<int32_t> sourceRouter =
242 doDijkstraPathCalculation(*sourceRouter);
244 addAllLsNextHopsToRoutingTable(pnlsr, rt, pMap, *sourceRouter);
253 for (
int i = 0 ; i <
vNoLink; i++) {
258 doDijkstraPathCalculation(*sourceRouter);
260 addAllLsNextHopsToRoutingTable(pnlsr, rt, pMap, *sourceRouter);
271 LinkStateRoutingTableCalculator::doDijkstraPathCalculation(
int sourceRouter)
278 for (i = 0 ; i < static_cast<int>(
m_nRouters); i++) {
279 m_parent[i] = EMPTY_PARENT;
281 m_distance[i] = INF_DISTANCE;
284 if (sourceRouter != NO_MAPPING_NUM) {
286 m_distance[sourceRouter] = 0;
287 sortQueueByDistance(Q, m_distance, head,
m_nRouters);
291 if (m_distance[u] == INF_DISTANCE) {
295 for (v = 0 ; v < static_cast<int>(
m_nRouters); v++) {
299 if (isNotExplored(Q, v, head + 1,
m_nRouters)) {
303 if (m_distance[u] +
adjMatrix[u][v] < m_distance[v]) {
305 m_distance[v] = m_distance[u] +
adjMatrix[u][v] ;
314 sortQueueByDistance(Q, m_distance, head,
m_nRouters);
321 LinkStateRoutingTableCalculator::addAllLsNextHopsToRoutingTable(
Nlsr& pnlsr,
RoutingTable& rt,
322 Map& pMap, uint32_t sourceRouter)
324 NLSR_LOG_DEBUG(
"LinkStateRoutingTableCalculator::addAllNextHopsToRoutingTable Called");
326 int nextHopRouter = 0;
330 if (i != sourceRouter) {
333 nextHopRouter = getLsNextHop(i, sourceRouter);
336 if (nextHopRouter != NO_NEXT_HOP) {
339 double routeCost = m_distance[i];
342 if (nextHopRouterName) {
343 std::string nextHopFace =
346 NextHop nh(nextHopFace, routeCost);
356 LinkStateRoutingTableCalculator::getLsNextHop(
int dest,
int source)
358 int nextHop = NO_NEXT_HOP;
359 while (m_parent[dest] != EMPTY_PARENT) {
361 dest = m_parent[dest];
363 if (dest != source) {
364 nextHop = NO_NEXT_HOP;
370 LinkStateRoutingTableCalculator::sortQueueByDistance(
int* Q,
372 int start,
int element)
374 for (
int i = start ; i < element ; i++) {
375 for (
int j = i + 1; j < element; j++) {
376 if (dist[Q[j]] < dist[Q[i]]) {
386 LinkStateRoutingTableCalculator::isNotExplored(
int* Q,
387 int u,
int start,
int element)
390 for (
int i = start; i < element; i++) {
400 LinkStateRoutingTableCalculator::allocateParent()
406 LinkStateRoutingTableCalculator::allocateDistance()
412 LinkStateRoutingTableCalculator::freeParent()
417 void LinkStateRoutingTableCalculator::freeDistance()
419 delete [] m_distance;
422 const double HyperbolicRoutingCalculator::MATH_PI = boost::math::constants::pi<double>();
424 const double HyperbolicRoutingCalculator::UNKNOWN_DISTANCE = -1.0;
425 const double HyperbolicRoutingCalculator::UNKNOWN_RADIUS = -1.0;
436 std::list<Adjacent> neighbors = adjacencies.
getAdjList();
437 for (std::list<Adjacent>::iterator adj = neighbors.begin(); adj != neighbors.end(); ++adj) {
441 NLSR_LOG_TRACE(adj->getName() <<
" is inactive; not using it as a nexthop");
445 ndn::Name srcRouterName = adj->getName();
448 if (srcRouterName == m_thisRouterName) {
452 std::string srcFaceUri = adj->getFaceUri().toString();
455 addNextHop(srcRouterName, srcFaceUri, 0, rt);
460 NLSR_LOG_WARN(adj->getName() <<
" does not exist in the router map!");
465 for (
int dest = 0; dest < static_cast<int>(
m_nRouters); ++dest) {
467 if (thisRouter && dest != *thisRouter && dest != *src) {
470 if (destRouterName) {
471 double distance = getHyperbolicDistance(map, lsdb, srcRouterName, *destRouterName);
474 if (distance == UNKNOWN_DISTANCE) {
475 NLSR_LOG_WARN(
"Could not calculate hyperbolic distance from " << srcRouterName <<
" to " <<
480 addNextHop(*destRouterName, srcFaceUri, distance, rt);
488 HyperbolicRoutingCalculator::getHyperbolicDistance(
Map& map,
Lsdb& lsdb,
489 ndn::Name src, ndn::Name dest)
491 NLSR_LOG_TRACE(
"Calculating hyperbolic distance from " << src <<
" to " << dest);
493 double distance = UNKNOWN_DISTANCE;
495 ndn::Name srcLsaKey = src;
500 ndn::Name destLsaKey = dest;
506 if (srcLsa ==
nullptr || destLsa ==
nullptr) {
507 return UNKNOWN_DISTANCE;
510 std::vector<double> srcTheta = srcLsa->
getCorTheta();
511 std::vector<double> destTheta = destLsa->
getCorTheta();
516 double diffTheta = calculateAngularDistance(srcTheta, destTheta);
518 if (srcRadius == UNKNOWN_RADIUS || destRadius == UNKNOWN_RADIUS ||
519 diffTheta == UNKNOWN_DISTANCE) {
520 return UNKNOWN_DISTANCE;
524 distance = calculateHyperbolicDistance(srcRadius, destRadius, diffTheta);
526 NLSR_LOG_TRACE(
"Distance from " << src <<
" to " << dest <<
" is " << distance);
532 HyperbolicRoutingCalculator::calculateAngularDistance(std::vector<double> angleVectorI,
533 std::vector<double> angleVectorJ)
540 if (angleVectorI.size() != angleVectorJ.size()) {
542 return UNKNOWN_DISTANCE;
546 if (angleVectorI.size() > 1) {
547 for (
unsigned int k = 0; k < angleVectorI.size() - 1; k++) {
548 if ((angleVectorI[k] > M_PI && angleVectorI[k] < 0.0) ||
549 (angleVectorJ[k] > M_PI && angleVectorJ[k] < 0.0)) {
551 return UNKNOWN_DISTANCE;
555 if (angleVectorI[angleVectorI.size()-1] > 2.*M_PI ||
556 angleVectorI[angleVectorI.size()-1] < 0.0) {
558 return UNKNOWN_DISTANCE;
561 if (angleVectorI[angleVectorI.size()-1] > 2.*M_PI ||
562 angleVectorI[angleVectorI.size()-1] < 0.0) {
564 return UNKNOWN_DISTANCE;
568 double innerProduct = 0.0;
571 double x0i = std::cos(angleVectorI[0]);
572 double x0j = std::cos(angleVectorJ[0]);
575 double xni = std::sin(angleVectorI[angleVectorI.size() - 1]);
576 double xnj = std::sin(angleVectorJ[angleVectorJ.size() - 1]);
580 for (
unsigned int k = 0; k < angleVectorI.size() - 1; k++) {
581 xni *= std::sin(angleVectorI[k]);
582 xnj *= std::sin(angleVectorJ[k]);
584 innerProduct += (x0i * x0j) + (xni * xnj);
587 if (angleVectorI.size() > 1) {
588 for (
unsigned int m = 1; m < angleVectorI.size(); m++) {
590 double xmi = std::cos(angleVectorI[m]);
591 double xmj = std::cos(angleVectorJ[m]);
592 for (
unsigned int l = 0; l < m; l++) {
593 xmi *= std::sin(angleVectorI[l]);
594 xmj *= std::sin(angleVectorJ[l]);
596 innerProduct += xmi * xmj;
602 return std::acos(innerProduct);
606 HyperbolicRoutingCalculator::calculateHyperbolicDistance(
double rI,
double rJ,
609 if (deltaTheta == UNKNOWN_DISTANCE) {
610 return UNKNOWN_DISTANCE;
616 if (deltaTheta <= 0.0 || rI <= 0.0 || rJ <= 0.0) {
618 return UNKNOWN_DISTANCE;
621 double xij = (1. / zeta) * std::acosh(std::cosh(zeta*rI) * std::cosh(zeta*rJ) -
622 std::sinh(zeta*rI)*std::sinh(zeta*rJ)*std::cos(deltaTheta));
627 HyperbolicRoutingCalculator::addNextHop(ndn::Name dest, std::string faceUri,
633 NLSR_LOG_TRACE(
"Calculated " << hop <<
" for destination: " << dest);
void writeAdjMatrixLog(const Map &map) const
void getLinksFromAdjMatrix(int *links, double *linkCosts, int source)
Populates temp. variables with the link costs for some router.
ConfParameter & getConfParameter()
ndn::optional< ndn::Name > getRouterNameByMappingNo(int32_t mn) const
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.
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)
AdjacencyList & getAdjacencyList()
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.
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.
void makeAdjMatrix(Nlsr &pnlsr, Map &pMap)
Constructs an adj. matrix to calculate with.
int getNumOfLinkfromAdjMatrix(int sRouter)
Returns how many links a router in the matrix has.
void calculatePath(Map &pMap, RoutingTable &rt, Nlsr &pnlsr)
void calculatePaths(Map &map, RoutingTable &rt, Lsdb &lsdb, AdjacencyList &adjacencies)
void setHyperbolic(bool b)
void addNextHop(const ndn::Name &destRouter, NextHop &nh)
Adds a next hop to a routing table entry.
const std::list< AdjLsa > & getAdjLsdb() const
std::list< Adjacent > & getAdjList()
#define NLSR_LOG_TRACE(x)
double getCorRadius() const