31 #include <boost/math/constants/constants.hpp> 63 for (std::list<AdjLsa>::iterator it = adjLsdb.begin(); it != adjLsdb.end() ; it++) {
68 std::list<Adjacent> adl = (*it).getAdl().getAdjList();
70 for (std::list<Adjacent>::iterator itAdl = adl.begin(); itAdl != adl.end() ; itAdl++) {
73 double cost = (*itAdl).getLinkCost();
75 if (row && col && *row < static_cast<int32_t>(
m_nRouters)
94 for (
size_t row = 0; row <
m_nRouters; ++row) {
95 for (
size_t col = 0; col <
m_nRouters; ++col) {
99 if (fromCost != toCost) {
100 double correctedCost = 0.0;
102 if (toCost != 0 && fromCost != 0) {
104 correctedCost = std::max(toCost, fromCost);
107 NLSR_LOG_WARN(
"Cost between [" << row <<
"][" << col <<
"] and [" << col <<
"][" << row <<
108 "] are not the same (" << toCost <<
" != " << fromCost <<
"). " <<
109 "Correcting to cost: " << correctedCost);
124 line += boost::lexical_cast<std::string>(
adjMatrix[i][j]);
134 for (
int i = 0; i < static_cast<int>(
m_nRouters); i++) {
209 NLSR_LOG_DEBUG(
"LinkStateRoutingTableCalculator::calculatePath Called");
214 ndn::optional<int32_t> sourceRouter =
221 doDijkstraPathCalculation(*sourceRouter);
223 addAllLsNextHopsToRoutingTable(pnlsr, rt, pMap, *sourceRouter);
232 for (
int i = 0 ; i <
vNoLink; i++) {
237 doDijkstraPathCalculation(*sourceRouter);
239 addAllLsNextHopsToRoutingTable(pnlsr, rt, pMap, *sourceRouter);
250 LinkStateRoutingTableCalculator::doDijkstraPathCalculation(
int sourceRouter)
257 for (i = 0 ; i < static_cast<int>(
m_nRouters); i++) {
258 m_parent[i] = EMPTY_PARENT;
260 m_distance[i] = INF_DISTANCE;
263 if (sourceRouter != NO_MAPPING_NUM) {
265 m_distance[sourceRouter] = 0;
266 sortQueueByDistance(Q, m_distance, head,
m_nRouters);
270 if (m_distance[u] == INF_DISTANCE) {
274 for (v = 0 ; v < static_cast<int>(
m_nRouters); v++) {
278 if (isNotExplored(Q, v, head + 1,
m_nRouters)) {
282 if (m_distance[u] +
adjMatrix[u][v] < m_distance[v]) {
284 m_distance[v] = m_distance[u] +
adjMatrix[u][v] ;
293 sortQueueByDistance(Q, m_distance, head,
m_nRouters);
300 LinkStateRoutingTableCalculator::addAllLsNextHopsToRoutingTable(
Nlsr& pnlsr,
RoutingTable& rt,
301 Map& pMap, uint32_t sourceRouter)
303 NLSR_LOG_DEBUG(
"LinkStateRoutingTableCalculator::addAllNextHopsToRoutingTable Called");
305 int nextHopRouter = 0;
309 if (i != sourceRouter) {
312 nextHopRouter = getLsNextHop(i, sourceRouter);
315 if (nextHopRouter != NO_NEXT_HOP) {
318 double routeCost = m_distance[i];
321 if (nextHopRouterName) {
322 std::string nextHopFace =
325 NextHop nh(nextHopFace, routeCost);
335 LinkStateRoutingTableCalculator::getLsNextHop(
int dest,
int source)
337 int nextHop = NO_NEXT_HOP;
338 while (m_parent[dest] != EMPTY_PARENT) {
340 dest = m_parent[dest];
342 if (dest != source) {
343 nextHop = NO_NEXT_HOP;
349 LinkStateRoutingTableCalculator::sortQueueByDistance(
int* Q,
351 int start,
int element)
353 for (
int i = start ; i < element ; i++) {
354 for (
int j = i + 1; j < element; j++) {
355 if (dist[Q[j]] < dist[Q[i]]) {
365 LinkStateRoutingTableCalculator::isNotExplored(
int* Q,
366 int u,
int start,
int element)
369 for (
int i = start; i < element; i++) {
379 LinkStateRoutingTableCalculator::allocateParent()
385 LinkStateRoutingTableCalculator::allocateDistance()
391 LinkStateRoutingTableCalculator::freeParent()
396 void LinkStateRoutingTableCalculator::freeDistance()
398 delete [] m_distance;
401 const double HyperbolicRoutingCalculator::MATH_PI = boost::math::constants::pi<double>();
403 const double HyperbolicRoutingCalculator::UNKNOWN_DISTANCE = -1.0;
404 const double HyperbolicRoutingCalculator::UNKNOWN_RADIUS = -1.0;
415 std::list<Adjacent> neighbors = adjacencies.
getAdjList();
416 for (std::list<Adjacent>::iterator adj = neighbors.begin(); adj != neighbors.end(); ++adj) {
420 NLSR_LOG_TRACE(adj->getName() <<
" is inactive; not using it as a nexthop");
424 ndn::Name srcRouterName = adj->getName();
427 if (srcRouterName == m_thisRouterName) {
431 std::string srcFaceUri = adj->getFaceUri().toString();
434 addNextHop(srcRouterName, srcFaceUri, 0, rt);
439 NLSR_LOG_WARN(adj->getName() <<
" does not exist in the router map!");
444 for (
int dest = 0; dest < static_cast<int>(
m_nRouters); ++dest) {
446 if (thisRouter && dest != *thisRouter && dest != *src) {
449 if (destRouterName) {
450 double distance = getHyperbolicDistance(map, lsdb, srcRouterName, *destRouterName);
453 if (distance == UNKNOWN_DISTANCE) {
454 NLSR_LOG_WARN(
"Could not calculate hyperbolic distance from " << srcRouterName <<
" to " <<
459 addNextHop(*destRouterName, srcFaceUri, distance, rt);
467 HyperbolicRoutingCalculator::getHyperbolicDistance(
Map& map,
Lsdb& lsdb,
468 ndn::Name src, ndn::Name dest)
470 NLSR_LOG_TRACE(
"Calculating hyperbolic distance from " << src <<
" to " << dest);
472 double distance = UNKNOWN_DISTANCE;
474 ndn::Name srcLsaKey = src;
479 ndn::Name destLsaKey = dest;
485 if (srcLsa ==
nullptr || destLsa ==
nullptr) {
486 return UNKNOWN_DISTANCE;
489 std::vector<double> srcTheta = srcLsa->
getCorTheta();
490 std::vector<double> destTheta = destLsa->
getCorTheta();
495 double diffTheta = calculateAngularDistance(srcTheta, destTheta);
497 if (srcRadius == UNKNOWN_RADIUS || destRadius == UNKNOWN_RADIUS ||
498 diffTheta == UNKNOWN_DISTANCE) {
499 return UNKNOWN_DISTANCE;
503 distance = calculateHyperbolicDistance(srcRadius, destRadius, diffTheta);
505 NLSR_LOG_TRACE(
"Distance from " << src <<
" to " << dest <<
" is " << distance);
511 HyperbolicRoutingCalculator::calculateAngularDistance(std::vector<double> angleVectorI,
512 std::vector<double> angleVectorJ)
519 if (angleVectorI.size() != angleVectorJ.size()) {
521 return UNKNOWN_DISTANCE;
525 if (angleVectorI.size() > 1) {
526 for (
unsigned int k = 0; k < angleVectorI.size() - 1; k++) {
527 if ((angleVectorI[k] > M_PI && angleVectorI[k] < 0.0) ||
528 (angleVectorJ[k] > M_PI && angleVectorJ[k] < 0.0)) {
530 return UNKNOWN_DISTANCE;
534 if (angleVectorI[angleVectorI.size()-1] > 2.*M_PI ||
535 angleVectorI[angleVectorI.size()-1] < 0.0) {
537 return UNKNOWN_DISTANCE;
540 if (angleVectorI[angleVectorI.size()-1] > 2.*M_PI ||
541 angleVectorI[angleVectorI.size()-1] < 0.0) {
543 return UNKNOWN_DISTANCE;
547 double innerProduct = 0.0;
550 double x0i = std::cos(angleVectorI[0]);
551 double x0j = std::cos(angleVectorJ[0]);
554 double xni = std::sin(angleVectorI[angleVectorI.size() - 1]);
555 double xnj = std::sin(angleVectorJ[angleVectorJ.size() - 1]);
559 for (
unsigned int k = 0; k < angleVectorI.size() - 1; k++) {
560 xni *= std::sin(angleVectorI[k]);
561 xnj *= std::sin(angleVectorJ[k]);
563 innerProduct += (x0i * x0j) + (xni * xnj);
566 if (angleVectorI.size() > 1) {
567 for (
unsigned int m = 1; m < angleVectorI.size(); m++) {
569 double xmi = std::cos(angleVectorI[m]);
570 double xmj = std::cos(angleVectorJ[m]);
571 for (
unsigned int l = 0; l < m; l++) {
572 xmi *= std::sin(angleVectorI[l]);
573 xmj *= std::sin(angleVectorJ[l]);
575 innerProduct += xmi * xmj;
581 return std::acos(innerProduct);
585 HyperbolicRoutingCalculator::calculateHyperbolicDistance(
double rI,
double rJ,
588 if (deltaTheta == UNKNOWN_DISTANCE) {
589 return UNKNOWN_DISTANCE;
595 if (deltaTheta <= 0.0 || rI <= 0.0 || rJ <= 0.0) {
597 return UNKNOWN_DISTANCE;
600 double xij = (1. / zeta) * std::acosh(std::cosh(zeta*rI) * std::cosh(zeta*rJ) -
601 std::sinh(zeta*rI)*std::sinh(zeta*rJ)*std::cos(deltaTheta));
606 HyperbolicRoutingCalculator::addNextHop(ndn::Name dest, std::string faceUri,
612 NLSR_LOG_TRACE(
"Calculated " << hop <<
" for destination: " << dest);
void getLinksFromAdjMatrix(int *links, double *linkCosts, int source)
Populates temp. variables with the link costs for some router.
ConfParameter & getConfParameter()
const ndn::FaceUri & getFaceUri() const
void makeAdjMatrix(Nlsr &pnlsr, Map pMap)
Constructs an adj. matrix to calculate with.
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)
ndn::optional< ndn::Name > getRouterNameByMappingNo(int32_t mn)
#define NLSR_LOG_DEBUG(x)
const ndn::Name & getRouterPrefix() const
Copyright (c) 2014-2017, 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-2017, 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.
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