Routing Table Calculation Complete(Ls, Hp)
diff --git a/nlsr_adjacent.hpp b/nlsr_adjacent.hpp
index dc4a712..2f5106f 100644
--- a/nlsr_adjacent.hpp
+++ b/nlsr_adjacent.hpp
@@ -38,7 +38,7 @@
return connectingFace;
}
- void getConnectingFace(int cf){
+ void setConnectingFace(int cf){
connectingFace=cf;
}
diff --git a/nlsr_adl.cpp b/nlsr_adl.cpp
index 55cbb29..055a792 100644
--- a/nlsr_adl.cpp
+++ b/nlsr_adl.cpp
@@ -46,6 +46,22 @@
}
+Adjacent
+Adl::getAdjacent(string adjName)
+{
+ Adjacent adj(adjName);
+
+ std::list<Adjacent >::iterator it = std::find_if( adjList.begin(),
+ adjList.end(),
+ bind(&adjacent_compare, _1, adj));
+
+ if( it != adjList.end()){
+ return (*it);
+ }
+
+ return adj;
+}
+
int
Adl::updateAdjacentLinkCost(string adjName, double lc){
Adjacent adj(adjName);
diff --git a/nlsr_adl.hpp b/nlsr_adl.hpp
index 70e250d..ec5cf96 100644
--- a/nlsr_adl.hpp
+++ b/nlsr_adl.hpp
@@ -27,6 +27,7 @@
bool isAdjLsaBuildable(nlsr& pnlsr);
int getNumOfActiveNeighbor();
+ Adjacent getAdjacent(string adjName);
int getAdlSize()
{
diff --git a/nlsr_lsa.hpp b/nlsr_lsa.hpp
index a8d3861..2a7294a 100644
--- a/nlsr_lsa.hpp
+++ b/nlsr_lsa.hpp
@@ -145,7 +145,14 @@
double getCorRadius()
{
- return corRad;
+ if ( corRad >= 0 )
+ {
+ return corRad;
+ }
+ else
+ {
+ return -1;
+ }
}
void setCorRadius(double cr)
diff --git a/nlsr_lsdb.cpp b/nlsr_lsdb.cpp
index 8d7e141..855f1c7 100644
--- a/nlsr_lsdb.cpp
+++ b/nlsr_lsdb.cpp
@@ -164,7 +164,7 @@
, pnlsr.getConfParameter().getCorR()
, pnlsr.getConfParameter().getCorTheta() );
pnlsr.getSm().setCorLsaSeq(pnlsr.getSm().getCorLsaSeq()+1);
- installCorLsa(corLsa);
+ installCorLsa(pnlsr, corLsa);
return true;
}
@@ -182,16 +182,27 @@
}
bool
-Lsdb::installCorLsa(CorLsa &clsa)
+Lsdb::installCorLsa(nlsr& pnlsr, CorLsa &clsa)
{
bool doesLsaExist_ = doesCorLsaExist(clsa.getCorLsaKey());
if ( !doesLsaExist_ )
{
// add cor LSA
addCorLsa(clsa);
+ printCorLsdb(); //debugging purpose
//schedule routing table calculation only if
//hyperbolic calculation is scheduled
- printCorLsdb();
+ if (pnlsr.getConfParameter().getIsHyperbolicCalc() >=1 )
+ {
+ if ( pnlsr.getIsRouteCalculationScheduled() != 1 )
+ {
+ pnlsr.getScheduler().scheduleEvent(ndn::time::seconds(15),
+ ndn::bind(&RoutingTable::calculate,
+ &pnlsr.getRoutingTable(),boost::ref(pnlsr)));
+ pnlsr.setIsRouteCalculationScheduled(1);
+ }
+ }
+
}
else
{
diff --git a/nlsr_lsdb.hpp b/nlsr_lsdb.hpp
index 1225969..5961b98 100644
--- a/nlsr_lsdb.hpp
+++ b/nlsr_lsdb.hpp
@@ -25,7 +25,7 @@
//function related to Cor LSDB
bool buildAndInstallOwnCorLsa(nlsr& pnlsr);
CorLsa& getCorLsa(string key);
- bool installCorLsa(CorLsa &clsa);
+ bool installCorLsa(nlsr& pnlsr, CorLsa &clsa);
bool removeCorLsa(string& key);
void printCorLsdb(); //debugging
diff --git a/nlsr_nhl.cpp b/nlsr_nhl.cpp
index 9675467..6654e8e 100644
--- a/nlsr_nhl.cpp
+++ b/nlsr_nhl.cpp
@@ -27,8 +27,10 @@
if ( it == nexthopList.end() ){
nexthopList.push_back(nh);
}
-
- (*it).setRouteCost(nh.getRouteCost());
+ if ( (*it).getRouteCost() > nh.getRouteCost() )
+ {
+ (*it).setRouteCost(nh.getRouteCost());
+ }
}
diff --git a/nlsr_rt.cpp b/nlsr_rt.cpp
index 95b138d..2487db5 100644
--- a/nlsr_rt.cpp
+++ b/nlsr_rt.cpp
@@ -6,6 +6,7 @@
#include "nlsr.hpp"
#include "nlsr_map.hpp"
#include "nlsr_rtc.hpp"
+#include "nlsr_rte.hpp"
using namespace std;
@@ -59,6 +60,8 @@
// need to update NPT here
}
+ printRoutingTable();
+
pnlsr.setIsRouteCalculationScheduled(0); //clear scheduled flag
pnlsr.setIsRoutingTableCalculating(0); //unsetting routing table calculation
}
@@ -81,22 +84,107 @@
LinkStateRoutingTableCalculator lsrtc(numOfRouter);
lsrtc.calculatePath(vMap,boost::ref(*this),pnlsr);
-
-
}
void
RoutingTable::calculateHypRoutingTable(nlsr& pnlsr)
{
-
+ Map vMap;
+ vMap.createMapFromAdjLsdb(pnlsr);
+ int numOfRouter=vMap.getMapSize();
+ HypRoutingTableCalculator hrtc(numOfRouter,0);
+ hrtc.calculatePath(vMap,boost::ref(*this),pnlsr);
}
void
-RoutingTable::calculateHypDryRoutingTable(nlsr&pnlsr)
+RoutingTable::calculateHypDryRoutingTable(nlsr& pnlsr)
{
+ Map vMap;
+ vMap.createMapFromAdjLsdb(pnlsr);
+ int numOfRouter=vMap.getMapSize();
+ HypRoutingTableCalculator hrtc(numOfRouter,1);
+ hrtc.calculatePath(vMap,boost::ref(*this),pnlsr);
+}
+
+static bool
+routingTableEntryCompare(RoutingTableEntry& rte, string& destRouter){
+ return rte.getDestination()==destRouter;
+}
+
+// function related to manipulation of routing table
+void
+RoutingTable::addNextHop(string destRouter, NextHop& nh)
+{
+ std::pair<RoutingTableEntry&, bool> rte=findRoutingTableEntry(destRouter);
+ if( !rte.second )
+ {
+ RoutingTableEntry rte(destRouter);
+ rte.getNhl().addNextHop(nh);
+ rTable.push_back(rte);
+ }
+ else
+ {
+ (rte.first).getNhl().addNextHop(nh);
+ }
+}
+
+std::pair<RoutingTableEntry&, bool>
+RoutingTable::findRoutingTableEntry(string destRouter)
+{
+ std::list<RoutingTableEntry >::iterator it = std::find_if( rTable.begin(),
+ rTable.end(),
+ bind(&routingTableEntryCompare, _1, destRouter));
+ if ( it != rTable.end() )
+ {
+ return std::make_pair(boost::ref((*it)),true);
+ }
+ RoutingTableEntry rteEmpty;
+ return std::make_pair(boost::ref(rteEmpty),false);
+}
+
+void
+RoutingTable::printRoutingTable()
+{
+ cout<<"---------------Routing Table------------------"<<endl;
+ for(std::list<RoutingTableEntry>::iterator it=rTable.begin() ;
+ it != rTable.end(); ++it)
+ {
+ cout<<(*it)<<endl;
+ }
+}
+
+
+//function related to manipulation of dry routing table
+void
+RoutingTable::addNextHopToDryTable(string destRouter, NextHop& nh)
+{
+ std::list<RoutingTableEntry >::iterator it = std::find_if( dryTable.begin(),
+ dryTable.end(),
+ bind(&routingTableEntryCompare, _1, destRouter));
+ if ( it == dryTable.end() ){
+ RoutingTableEntry rte(destRouter);
+ rte.getNhl().addNextHop(nh);
+ dryTable.push_back(rte);
+ }
+ else
+ {
+ (*it).getNhl().addNextHop(nh);
+ }
}
+void
+RoutingTable::printDryRoutingTable()
+{
+ cout<<"--------Dry Run's Routing Table--------------"<<endl;
+ for(std::list<RoutingTableEntry>::iterator it=dryTable.begin() ;
+ it != dryTable.end(); ++it)
+ {
+ cout<<(*it)<<endl;
+ }
+}
+
+
void
RoutingTable::clearRoutingTable()
{
diff --git a/nlsr_rt.hpp b/nlsr_rt.hpp
index 05beda4..8585184 100644
--- a/nlsr_rt.hpp
+++ b/nlsr_rt.hpp
@@ -2,11 +2,13 @@
#define NLSR_RT_HPP
#include<iostream>
+#include<utility>
#include<string>
#include "nlsr_rte.hpp"
class nlsr;
+class NextHop;
using namespace std;
@@ -14,9 +16,16 @@
{
public:
RoutingTable()
+ : NO_NEXT_HOP(-12345)
{
}
void calculate(nlsr& pnlsr);
+ void addNextHop(string destRouter, NextHop& nh);
+ void printRoutingTable();
+
+ void addNextHopToDryTable(string destRouter, NextHop& nh);
+ void printDryRoutingTable();
+ std::pair<RoutingTableEntry&, bool> findRoutingTableEntry(string destRouter);
private:
void calculateLsRoutingTable(nlsr& pnlsr);
@@ -25,6 +34,8 @@
void clearRoutingTable();
void clearDryRoutingTable();
+
+ const int NO_NEXT_HOP;
std::list< RoutingTableEntry > rTable;
std::list< RoutingTableEntry > dryTable;
diff --git a/nlsr_rtc.cpp b/nlsr_rtc.cpp
index 4dabf6a..f7ec5cd 100644
--- a/nlsr_rtc.cpp
+++ b/nlsr_rtc.cpp
@@ -1,8 +1,10 @@
#include <iostream>
+#include <cmath>
#include "nlsr_lsdb.hpp"
#include "nlsr_rtc.hpp"
#include "nlsr_map.hpp"
#include "nlsr_lsa.hpp"
+#include "nlsr_nexthop.hpp"
#include "nlsr.hpp"
using namespace std;
@@ -17,6 +19,16 @@
}
}
+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)
{
@@ -106,18 +118,41 @@
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)
{
cout<<"LinkStateRoutingTableCalculator::calculatePath Called"<<endl;
allocateAdjMatrix();
+ initMatrix();
makeAdjMatrix(pnlsr,pMap);
cout<<pMap;
printAdjMatrix();
string routerName=pnlsr.getConfParameter().getRouterPrefix();
int sourceRouter=pMap.getMappingNoByRouterName(routerName);
- cout<<"Calculating Router: "<< routerName <<" Mapping no: "<<sourceRouter<<endl;
int noLink=getNumOfLinkfromAdjMatrix(sourceRouter);
allocateParent();
allocateDistance();
@@ -129,7 +164,7 @@
// print all ls path -- debugging purpose
printAllLsPath(sourceRouter);
// update routing table
- // update NPT ( FIB )
+ addAllLsNextHopsToRoutingTable(pnlsr, rt, pMap, sourceRouter);
}
else
{
@@ -141,10 +176,14 @@
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
- //update NPT ( FIB )
+ addAllLsNextHopsToRoutingTable(pnlsr, rt, pMap, sourceRouter);
}
freeLinks();
@@ -207,6 +246,53 @@
delete [] Q;
}
+void
+LinkStateRoutingTableCalculator::addAllLsNextHopsToRoutingTable(nlsr& pnlsr,
+ RoutingTable& rt, Map& pMap, int sourceRouter)
+{
+ cout<<"LinkStateRoutingTableCalculator::addAllNextHopsToRoutingTable Called";
+ cout<<endl;
+ for(int i=0; i < numOfRouter ; i++)
+ {
+ if ( i!= sourceRouter )
+ {
+ int nextHopRouter=getLsNextHop(i,sourceRouter);
+ double routeCost=distance[i];
+ string nextHopRouterName=pMap.getRouterNameByMappingNo(nextHopRouter);
+ int nxtHopFace=
+ pnlsr.getAdl().getAdjacent(nextHopRouterName).getConnectingFace();
+ cout<<"Dest Router: "<<pMap.getRouterNameByMappingNo(i)<<endl;
+ cout<<"Next hop Router: "<<nextHopRouterName<<endl;
+ cout<<"Next hop Face: "<<nxtHopFace<<endl;
+ cout<<"Route Cost: "<<routeCost<<endl;
+ cout<<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;
+ while ( parent[dest] != EMPTY_PARENT )
+ {
+ nextHop=dest;
+ dest=parent[dest];
+
+ }
+
+ if ( dest != source )
+ {
+ nextHop=NO_NEXT_HOP;
+ }
+
+ return nextHop;
+}
+
void
LinkStateRoutingTableCalculator::printAllLsPath(int sourceRouter)
{
@@ -291,37 +377,146 @@
delete [] distance;
}
-void
-LinkStateRoutingTableCalculator::allocateLinks()
-{
- links=new int[vNoLink];
-}
-void LinkStateRoutingTableCalculator::allocateLinkCosts()
-{
- linkCosts=new double[vNoLink];
-}
-
-void
-LinkStateRoutingTableCalculator::freeLinks()
-{
- delete [] links;
-}
-void
-LinkStateRoutingTableCalculator::freeLinksCosts()
-{
- delete [] linkCosts;
-}
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 )
+ {
+ linkFaces[k] = nextHopFace;
+ distanceToNeighbor[k] = distToNbr;
+ distFromNbrToDest[k] = distToDestFromNbr;
+ k++;
+ }
+ }
+
+ addHypNextHopsToRoutingTable(pnlsr,pMap,rt,k,i);
+
+ freeLinkFaces();
+ freeDistanceToNeighbor();
+ freeDistFromNbrToDest();
+ }
+ }
+
+ freeLinks();
+ freeLinksCosts();
+ freeAdjMatrix();
}
void
-HypDryRoutingTableCalculator::calculatePath(Map& pMap,
- RoutingTable& rt, nlsr& pnlsr)
+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(linkFaces[i],distFromNbrToDest[i]);
+ rt.addNextHop(destRouter,nh);
+ if( isDryRun == 1 )
+ {
+ 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).getCorRadius();
+ double srcTheta=pnlsr.getLsdb().getCorLsa(srcRouterKey).getCorTheta();
+
+ double destRadius=pnlsr.getLsdb().getCorLsa(destRouterKey).getCorRadius();
+ double destTheta=pnlsr.getLsdb().getCorLsa(destRouterKey).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()
+{
+ linkFaces=new int[vNoLink];
+}
+
+void
+HypRoutingTableCalculator::allocateDistanceToNeighbor()
+{
+ distanceToNeighbor=new double[vNoLink];
+}
+
+void
+HypRoutingTableCalculator::allocateDistFromNbrToDest()
+{
+ distFromNbrToDest=new double[vNoLink];
+}
+
+void
+HypRoutingTableCalculator::freeLinkFaces()
+{
+ delete [] linkFaces;
+}
+
+void
+HypRoutingTableCalculator::freeDistanceToNeighbor()
+{
+ delete [] distanceToNeighbor;
+}
+
+void
+HypRoutingTableCalculator::freeDistFromNbrToDest()
+{
+ delete [] distFromNbrToDest;
+}
diff --git a/nlsr_rtc.hpp b/nlsr_rtc.hpp
index 3efc665..cba183b 100644
--- a/nlsr_rtc.hpp
+++ b/nlsr_rtc.hpp
@@ -25,6 +25,7 @@
}
protected:
void allocateAdjMatrix();
+ void initMatrix();
void makeAdjMatrix(nlsr& pnlsr,Map pMap);
void printAdjMatrix();
int getNumOfLinkfromAdjMatrix(int sRouter);
@@ -32,9 +33,23 @@
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;
int numOfRouter;
+
+ int vNoLink;
+ int *links;
+ double *linkCosts;
};
class LinkStateRoutingTableCalculator: public RoutingTableCalculator
@@ -44,13 +59,11 @@
: EMPTY_PARENT(-12345)
, INF_DISTANCE(2147483647)
, NO_MAPPING_NUM(-1)
+ , NO_NEXT_HOP(-12345)
{
numOfRouter=rn;
}
- void setNoLink(int nl)
- {
- vNoLink=nl;
- }
+
void calculatePath(Map& pMap, RoutingTable& rt, nlsr& pnlsr);
@@ -61,28 +74,27 @@
int isNotExplored(int *Q, int u,int start, int element);
void printAllLsPath(int sourceRouter);
void printLsPath(int destRouter);
+ void addAllLsNextHopsToRoutingTable(nlsr& pnlsr, RoutingTable& rt,
+ Map& pMap,int sourceRouter);
+ int getLsNextHop(int dest, int source);
void allocateParent();
void allocateDistance();
void freeParent();
void freeDistance();
- void allocateLinks();
- void allocateLinkCosts();
- void freeLinks();
- void freeLinksCosts();
+
private:
int *parent;
double *distance;
- int vNoLink;
- int *links;
- double *linkCosts;
+
const int EMPTY_PARENT;
const double INF_DISTANCE;
const int NO_MAPPING_NUM;
+ const int NO_NEXT_HOP;
};
@@ -90,23 +102,40 @@
{
public:
HypRoutingTableCalculator(int rn)
+ : MATH_PI(3.141592654)
{
numOfRouter=rn;
+ isDryRun=0;
+ }
+ HypRoutingTableCalculator(int rn, int idr)
+ : MATH_PI(3.141592654)
+ {
+ numOfRouter=rn;
+ isDryRun=idr;
}
void calculatePath(Map& pMap, RoutingTable& rt, nlsr& pnlsr);
-};
+private:
+ void allocateLinkFaces();
+ void allocateDistanceToNeighbor();
+ void allocateDistFromNbrToDest();
+ void freeLinkFaces();
+ void freeDistanceToNeighbor();
+ void freeDistFromNbrToDest();
-class HypDryRoutingTableCalculator: public RoutingTableCalculator
-{
- public:
- HypDryRoutingTableCalculator(int rn)
- {
- numOfRouter=rn;
- }
+ double getHyperbolicDistance(nlsr& pnlsr,Map& pMap, int src, int dest);
+ void addHypNextHopsToRoutingTable(nlsr& pnlsr,Map& pMap,
+ RoutingTable& rt, int noFaces,int dest);
- void calculatePath(Map& pMap, RoutingTable& rt, nlsr& pnlsr);
+private:
+ int isDryRun;
+
+ int *linkFaces;
+ double *distanceToNeighbor;
+ double *distFromNbrToDest;
+
+ const double MATH_PI;
};
diff --git a/nlsr_test.cpp b/nlsr_test.cpp
index f9e39d7..6138620 100644
--- a/nlsr_test.cpp
+++ b/nlsr_test.cpp
@@ -87,7 +87,7 @@
nlsrTest::secheduledAddCorLsa(nlsr& pnlsr,string router, double r, double angle)
{
CorLsa corLsa(router,3,1,3600,r,angle);
- pnlsr.getLsdb().installCorLsa(corLsa);
+ pnlsr.getLsdb().installCorLsa(pnlsr, corLsa);
}
void