File name format change and Removed warning messages (Except warning from boost for Logging)
Change-Id: If3a3a5411d377d925527fc3e8809c228a9a81e26
diff --git a/src/route/routing-table-calculator.cpp b/src/route/routing-table-calculator.cpp
new file mode 100644
index 0000000..6c6dad3
--- /dev/null
+++ b/src/route/routing-table-calculator.cpp
@@ -0,0 +1,514 @@
+#include <iostream>
+#include <cmath>
+#include "lsdb.hpp"
+#include "routing-table-calculator.hpp"
+#include "map.hpp"
+#include "lsa.hpp"
+#include "nexthop.hpp"
+#include "nlsr.hpp"
+
+namespace nlsr {
+
+using namespace std;
+
+void
+RoutingTableCalculator::allocateAdjMatrix()
+{
+ adjMatrix = new double*[numOfRouter];
+ for (int i = 0; i < numOfRouter; ++i)
+ {
+ adjMatrix[i] = new double[numOfRouter];
+ }
+}
+
+void
+RoutingTableCalculator::initMatrix()
+{
+ for (int i = 0; i < numOfRouter; i++)
+ {
+ for (int j = 0; j < numOfRouter; j++)
+ adjMatrix[i][j] = 0;
+ }
+}
+
+void
+RoutingTableCalculator::makeAdjMatrix(Nlsr& pnlsr, Map pMap)
+{
+ std::list<AdjLsa> adjLsdb = pnlsr.getLsdb().getAdjLsdb();
+ for (std::list<AdjLsa>::iterator it = adjLsdb.begin();
+ it != adjLsdb.end() ; it++)
+ {
+ string linkStartRouter = (*it).getOrigRouter();
+ int row = pMap.getMappingNoByRouterName(linkStartRouter);
+ std::list<Adjacent> adl = (*it).getAdl().getAdjList();
+ for (std::list<Adjacent>::iterator itAdl = adl.begin();
+ itAdl != adl.end() ; itAdl++)
+ {
+ string linkEndRouter = (*itAdl).getName();
+ int col = pMap.getMappingNoByRouterName(linkEndRouter);
+ double cost = (*itAdl).getLinkCost();
+ if ((row >= 0 && row < numOfRouter) && (col >= 0 && col < numOfRouter))
+ {
+ adjMatrix[row][col] = cost;
+ }
+ }
+ }
+}
+
+void
+RoutingTableCalculator::printAdjMatrix()
+{
+ for (int i = 0; i < numOfRouter; i++)
+ {
+ for (int j = 0; j < numOfRouter; j++)
+ printf("%f ", adjMatrix[i][j]);
+ printf("\n");
+ }
+}
+
+void
+RoutingTableCalculator::adjustAdMatrix(int source, int link, double linkCost)
+{
+ for (int i = 0; i < numOfRouter; i++)
+ {
+ if (i == link)
+ {
+ adjMatrix[source][i] = linkCost;
+ }
+ else
+ {
+ adjMatrix[source][i] = 0;
+ }
+ }
+}
+
+int
+RoutingTableCalculator::getNumOfLinkfromAdjMatrix(int sRouter)
+{
+ int noLink = 0;
+ for (int i = 0; i < numOfRouter; i++)
+ {
+ if (adjMatrix[sRouter][i] > 0)
+ {
+ noLink++;
+ }
+ }
+ return noLink;
+}
+
+void
+RoutingTableCalculator::getLinksFromAdjMatrix(int* links,
+ double* linkCosts, int source)
+{
+ int j = 0;
+ for (int i = 0; i < numOfRouter; i++)
+ {
+ if (adjMatrix[source][i] > 0)
+ {
+ links[j] = i;
+ linkCosts[j] = adjMatrix[source][i];
+ j++;
+ }
+ }
+}
+
+void
+RoutingTableCalculator::freeAdjMatrix()
+{
+ for (int i = 0; i < numOfRouter; ++i)
+ {
+ delete [] adjMatrix[i];
+ }
+ delete [] adjMatrix;
+}
+
+
+void
+RoutingTableCalculator::allocateLinks()
+{
+ links = new int[vNoLink];
+}
+
+void
+RoutingTableCalculator::allocateLinkCosts()
+{
+ linkCosts = new double[vNoLink];
+}
+
+
+void
+RoutingTableCalculator::freeLinks()
+{
+ delete [] links;
+}
+void
+RoutingTableCalculator::freeLinksCosts()
+{
+ delete [] linkCosts;
+}
+
+void
+LinkStateRoutingTableCalculator::calculatePath(Map& pMap,
+ RoutingTable& rt, Nlsr& pnlsr)
+{
+ std::cout << "LinkStateRoutingTableCalculator::calculatePath Called" <<
+ std::endl;
+ allocateAdjMatrix();
+ initMatrix();
+ makeAdjMatrix(pnlsr, pMap);
+ std::cout << pMap;
+ printAdjMatrix();
+ string routerName = pnlsr.getConfParameter().getRouterPrefix();
+ int sourceRouter = pMap.getMappingNoByRouterName(routerName);
+ //int noLink=getNumOfLinkfromAdjMatrix(sourceRouter);
+ allocateParent();
+ allocateDistance();
+ if (pnlsr.getConfParameter().getMaxFacesPerPrefix() == 1)
+ {
+ // Single Path
+ doDijkstraPathCalculation(sourceRouter);
+ // print all ls path -- debugging purpose
+ printAllLsPath(sourceRouter);
+ // update routing table
+ addAllLsNextHopsToRoutingTable(pnlsr, rt, pMap, sourceRouter);
+ }
+ else
+ {
+ // Multi Path
+ setNoLink(getNumOfLinkfromAdjMatrix(sourceRouter));
+ allocateLinks();
+ allocateLinkCosts();
+ getLinksFromAdjMatrix(links, linkCosts, sourceRouter);
+ for (int i = 0 ; i < vNoLink; i++)
+ {
+ adjustAdMatrix(sourceRouter, links[i], linkCosts[i]);
+ printAdjMatrix();
+ doDijkstraPathCalculation(sourceRouter);
+ // print all ls path -- debugging purpose
+ printAllLsPath(sourceRouter);
+ //update routing table
+ addAllLsNextHopsToRoutingTable(pnlsr, rt, pMap, sourceRouter);
+ }
+ freeLinks();
+ freeLinksCosts();
+ }
+ freeParent();
+ freeDistance();
+ freeAdjMatrix();
+}
+
+void
+LinkStateRoutingTableCalculator::doDijkstraPathCalculation(int sourceRouter)
+{
+ int i;
+ int v, u;
+ int* Q = new int[numOfRouter];
+ int head = 0;
+ /* Initiate the Parent */
+ for (i = 0 ; i < numOfRouter; i++)
+ {
+ m_parent[i] = EMPTY_PARENT;
+ m_distance[i] = INF_DISTANCE;
+ Q[i] = i;
+ }
+ if (sourceRouter != NO_MAPPING_NUM)
+ {
+ m_distance[sourceRouter] = 0;
+ sortQueueByDistance(Q, m_distance, head, numOfRouter);
+ while (head < numOfRouter)
+ {
+ u = Q[head];
+ if (m_distance[u] == INF_DISTANCE)
+ {
+ break;
+ }
+ for (v = 0 ; v < numOfRouter; v++)
+ {
+ if (adjMatrix[u][v] > 0)
+ {
+ if (isNotExplored(Q, v, head + 1, numOfRouter))
+ {
+ if (m_distance[u] + adjMatrix[u][v] < m_distance[v])
+ {
+ m_distance[v] = m_distance[u] + adjMatrix[u][v] ;
+ m_parent[v] = u;
+ }
+ }
+ }
+ }
+ head++;
+ sortQueueByDistance(Q, m_distance, head, numOfRouter);
+ }
+ }
+ delete [] Q;
+}
+
+void
+LinkStateRoutingTableCalculator::addAllLsNextHopsToRoutingTable(Nlsr& pnlsr,
+ RoutingTable& rt, Map& pMap, int sourceRouter)
+{
+ std::cout <<
+ "LinkStateRoutingTableCalculator::addAllNextHopsToRoutingTable Called";
+ std::cout << std::endl;
+ int nextHopRouter = 0;
+ for (int i = 0; i < numOfRouter ; i++)
+ {
+ if (i != sourceRouter)
+ {
+ nextHopRouter = getLsNextHop(i, sourceRouter);
+ if (nextHopRouter != NO_NEXT_HOP)
+ {
+ double routeCost = m_distance[i];
+ string nextHopRouterName =
+ pMap.getRouterNameByMappingNo(nextHopRouter);
+ int nxtHopFace =
+ pnlsr.getAdl().getAdjacent(nextHopRouterName).getConnectingFace();
+ std::cout << "Dest Router: " << pMap.getRouterNameByMappingNo(i) << std::endl;
+ std::cout << "Next hop Router: " << nextHopRouterName << std::endl;
+ std::cout << "Next hop Face: " << nxtHopFace << std::endl;
+ std::cout << "Route Cost: " << routeCost << std::endl;
+ std::cout << std::endl;
+ // Add next hop to routing table
+ NextHop nh(nxtHopFace, routeCost);
+ rt.addNextHop(pMap.getRouterNameByMappingNo(i), nh);
+ }
+ }
+ }
+}
+
+int
+LinkStateRoutingTableCalculator::getLsNextHop(int dest, int source)
+{
+ int nextHop = NO_NEXT_HOP;
+ while (m_parent[dest] != EMPTY_PARENT)
+ {
+ nextHop = dest;
+ dest = m_parent[dest];
+ }
+ if (dest != source)
+ {
+ nextHop = NO_NEXT_HOP;
+ }
+ return nextHop;
+}
+
+void
+LinkStateRoutingTableCalculator::printAllLsPath(int sourceRouter)
+{
+ std::cout << "LinkStateRoutingTableCalculator::printAllLsPath Called" <<
+ std::endl;
+ std::cout << "Source Router: " << sourceRouter << std::endl;
+ for (int i = 0; i < numOfRouter ; i++)
+ {
+ if (i != sourceRouter)
+ {
+ printLsPath(i);
+ std::cout << std::endl;
+ }
+ }
+}
+
+void
+LinkStateRoutingTableCalculator::printLsPath(int destRouter)
+{
+ if (m_parent[destRouter] != EMPTY_PARENT)
+ {
+ printLsPath(m_parent[destRouter]);
+ }
+ std:: cout << " " << destRouter;
+}
+
+void
+LinkStateRoutingTableCalculator::sortQueueByDistance(int* Q,
+ double* dist, int start, int element)
+{
+ for (int i = start ; i < element ; i++)
+ {
+ for (int j = i + 1; j < element; j++)
+ {
+ if (dist[Q[j]] < dist[Q[i]])
+ {
+ int tempU = Q[j];
+ Q[j] = Q[i];
+ Q[i] = tempU;
+ }
+ }
+ }
+}
+
+int
+LinkStateRoutingTableCalculator::isNotExplored(int* Q,
+ int u, int start, int element)
+{
+ int ret = 0;
+ for (int i = start; i < element; i++)
+ {
+ if (Q[i] == u)
+ {
+ ret = 1;
+ break;
+ }
+ }
+ return ret;
+}
+
+void
+LinkStateRoutingTableCalculator::allocateParent()
+{
+ m_parent = new int[numOfRouter];
+}
+
+void
+LinkStateRoutingTableCalculator::allocateDistance()
+{
+ m_distance = new double[numOfRouter];
+}
+
+void
+LinkStateRoutingTableCalculator::freeParent()
+{
+ delete [] m_parent;
+}
+
+void LinkStateRoutingTableCalculator::freeDistance()
+{
+ delete [] m_distance;
+}
+
+
+
+void
+HypRoutingTableCalculator::calculatePath(Map& pMap,
+ RoutingTable& rt, Nlsr& pnlsr)
+{
+ makeAdjMatrix(pnlsr, pMap);
+ string routerName = pnlsr.getConfParameter().getRouterPrefix();
+ int sourceRouter = pMap.getMappingNoByRouterName(routerName);
+ int noLink = getNumOfLinkfromAdjMatrix(sourceRouter);
+ setNoLink(noLink);
+ allocateLinks();
+ allocateLinkCosts();
+ getLinksFromAdjMatrix(links, linkCosts, sourceRouter);
+ for (int i = 0 ; i < numOfRouter ; ++i)
+ {
+ int k = 0;
+ if (i != sourceRouter)
+ {
+ allocateLinkFaces();
+ allocateDistanceToNeighbor();
+ allocateDistFromNbrToDest();
+ for (int j = 0; j < vNoLink; j++)
+ {
+ string nextHopRouterName = pMap.getRouterNameByMappingNo(links[j]);
+ int nextHopFace =
+ pnlsr.getAdl().getAdjacent(nextHopRouterName).getConnectingFace();
+ double distToNbr = getHyperbolicDistance(pnlsr, pMap,
+ sourceRouter, links[j]);
+ double distToDestFromNbr = getHyperbolicDistance(pnlsr,
+ pMap, links[j], i);
+ if (distToDestFromNbr >= 0)
+ {
+ m_linkFaces[k] = nextHopFace;
+ m_distanceToNeighbor[k] = distToNbr;
+ m_distFromNbrToDest[k] = distToDestFromNbr;
+ k++;
+ }
+ }
+ addHypNextHopsToRoutingTable(pnlsr, pMap, rt, k, i);
+ freeLinkFaces();
+ freeDistanceToNeighbor();
+ freeDistFromNbrToDest();
+ }
+ }
+ freeLinks();
+ freeLinksCosts();
+ freeAdjMatrix();
+}
+
+void
+HypRoutingTableCalculator::addHypNextHopsToRoutingTable(Nlsr& pnlsr, Map& pMap,
+ RoutingTable& rt, int noFaces, int dest)
+{
+ for (int i = 0 ; i < noFaces ; ++i)
+ {
+ string destRouter = pMap.getRouterNameByMappingNo(dest);
+ NextHop nh(m_linkFaces[i], m_distFromNbrToDest[i]);
+ rt.addNextHop(destRouter, nh);
+ if (m_isDryRun)
+ {
+ rt.addNextHopToDryTable(destRouter, nh);
+ }
+ }
+}
+
+double
+HypRoutingTableCalculator::getHyperbolicDistance(Nlsr& pnlsr,
+ Map& pMap, int src, int dest)
+{
+ double distance = 0.0;
+ string srcRouterKey = pMap.getRouterNameByMappingNo(src) + "/3";
+ string destRouterKey = pMap.getRouterNameByMappingNo(dest) + "/3";
+ double srcRadius = (pnlsr.getLsdb().getCorLsa(
+ srcRouterKey).first).getCorRadius();
+ double srcTheta = (pnlsr.getLsdb().getCorLsa(srcRouterKey).first).getCorTheta();
+ double destRadius = (pnlsr.getLsdb().getCorLsa(
+ destRouterKey).first).getCorRadius();
+ double destTheta = (pnlsr.getLsdb().getCorLsa(
+ destRouterKey).first).getCorTheta();
+ double diffTheta = fabs(srcTheta - destTheta);
+ if (diffTheta > MATH_PI)
+ {
+ diffTheta = 2 * MATH_PI - diffTheta;
+ }
+ if (srcRadius != -1 && destRadius != -1)
+ {
+ if (diffTheta == 0)
+ distance = fabs(srcRadius - destRadius);
+ else
+ distance = acosh((cosh(srcRadius) * cosh(destRadius)) -
+ (sinh(srcRadius) * sinh(destRadius) * cos(diffTheta)));
+ }
+ else
+ {
+ distance = -1;
+ }
+ return distance;
+}
+
+void
+HypRoutingTableCalculator::allocateLinkFaces()
+{
+ m_linkFaces = new int[vNoLink];
+}
+
+void
+HypRoutingTableCalculator::allocateDistanceToNeighbor()
+{
+ m_distanceToNeighbor = new double[vNoLink];
+}
+
+void
+HypRoutingTableCalculator::allocateDistFromNbrToDest()
+{
+ m_distFromNbrToDest = new double[vNoLink];
+}
+
+void
+HypRoutingTableCalculator::freeLinkFaces()
+{
+ delete [] m_linkFaces;
+}
+
+void
+HypRoutingTableCalculator::freeDistanceToNeighbor()
+{
+ delete [] m_distanceToNeighbor;
+}
+
+void
+HypRoutingTableCalculator::freeDistFromNbrToDest()
+{
+ delete [] m_distFromNbrToDest;
+}
+
+}//namespace nlsr