routing-table-calculator.hpp

Go to the documentation of this file.

/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
 * Copyright (c) 2014-2021,  The University of Memphis,
 *                           Regents of the University of California
 *
 * This file is part of NLSR (Named-data Link State Routing).
 * See AUTHORS.md for complete list of NLSR authors and contributors.
 *
 * NLSR is free software: you can redistribute it and/or modify it under the terms
 * of the GNU General Public License as published by the Free Software Foundation,
 * either version 3 of the License, or (at your option) any later version.
 *
 * NLSR is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
 * PURPOSE.  See the GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along with
 * NLSR, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
 */
 
#ifndef NLSR_ROUTING_TABLE_CALCULATOR_HPP
#define NLSR_ROUTING_TABLE_CALCULATOR_HPP
 
#include "common.hpp"
#include "lsa/lsa.hpp"
#include "lsa/adj-lsa.hpp"
#include "lsdb.hpp"
#include "conf-parameter.hpp"
 
#include <list>
 
namespace nlsr {
 
class Map;
class RoutingTable;
 
class RoutingTableCalculator
{
public:
  RoutingTableCalculator(size_t nRouters)
  {
    m_nRouters = nRouters;
  }
 
protected:
  void
  allocateAdjMatrix();
 
  void
  initMatrix();
 
  void
  makeAdjMatrix(const Lsdb& lsdb, Map& pMap);
 
  void
  writeAdjMatrixLog(const Map& map) const;
 
  int
  getNumOfLinkfromAdjMatrix(int sRouter);
 
  void
  freeAdjMatrix();
  void
  adjustAdMatrix(int source, int link, double linkCost);
 
  void
  getLinksFromAdjMatrix(int* links, double* linkCosts, int source);
 
  void
  allocateLinks();
 
  void
  allocateLinkCosts();
 
  void
  freeLinks();
 
  void
  freeLinksCosts();
 
  void
  setNoLink(int nl)
  {
    vNoLink = nl;
  }
 
protected:
  double** adjMatrix;
  size_t m_nRouters;
 
  int vNoLink;
  int* links;
  double* linkCosts;
 
};
 
class LinkStateRoutingTableCalculator: public RoutingTableCalculator
{
public:
  LinkStateRoutingTableCalculator(size_t nRouters)
    : RoutingTableCalculator(nRouters)
  {
  }
 
  void
  calculatePath(Map& pMap, RoutingTable& rt, ConfParameter& confParam,
                const Lsdb& lsdb);
 
private:
  void
  doDijkstraPathCalculation(int sourceRouter);
 
  void
  sortQueueByDistance(int* Q, double* dist, int start, int element);
 
  int
  isNotExplored(int* Q, int u, int start, int element);
 
  void
  addAllLsNextHopsToRoutingTable(AdjacencyList& adjacencies, RoutingTable& rt,
                                 Map& pMap, uint32_t sourceRouter);
 
  int
  getLsNextHop(int dest, int source);
 
  void
  allocateParent();
 
  void
  allocateDistance();
 
  void
  freeParent();
 
  void
  freeDistance();
 
private:
  int* m_parent;
  double* m_distance;
 
  static const int EMPTY_PARENT;
  static const double INF_DISTANCE;
  static const int NO_MAPPING_NUM;
public:
  static const int NO_NEXT_HOP;
 
};
 
class AdjacencyList;
class Lsdb;
 
class HyperbolicRoutingCalculator
{
public:
  HyperbolicRoutingCalculator(size_t nRouters, bool isDryRun, ndn::Name thisRouterName)
    : m_nRouters(nRouters)
    , m_isDryRun(isDryRun)
    , m_thisRouterName(thisRouterName)
  {
  }
 
  void
  calculatePath(Map& map, RoutingTable& rt, Lsdb& lsdb, AdjacencyList& adjacencies);
 
private:
  double
  getHyperbolicDistance(Lsdb& lsdb, ndn::Name src, ndn::Name dest);
 
  void
  addNextHop(ndn::Name destinationRouter, std::string faceUri, double cost, RoutingTable& rt);
 
  double
  calculateHyperbolicDistance(double rI, double rJ, double deltaTheta);
 
  double
  calculateAngularDistance(std::vector<double> angleVectorI,
                           std::vector<double> angleVectorJ);
 
private:
  const size_t m_nRouters;
  const bool m_isDryRun;
  const ndn::Name m_thisRouterName;
 
  static const double MATH_PI;
  static const double UNKNOWN_DISTANCE;
  static const double UNKNOWN_RADIUS;
};
 
} // namespace nlsr
 
#endif // NLSR_ROUTING_TABLE_CALCULATOR_HPP