Link State Routing Calculation
diff --git a/nlsr_lsa.cpp b/nlsr_lsa.cpp
index 5495859..38d3fd5 100644
--- a/nlsr_lsa.cpp
+++ b/nlsr_lsa.cpp
@@ -8,11 +8,12 @@
using namespace std;
-string
-Lsa::getLsaKey()
+
+string
+NameLsa::getNameLsaKey()
{
string key;
- key=origRouter + "/" + boost::lexical_cast<std::string>(lsType);
+ key=origRouter + "/" + boost::lexical_cast<std::string>(1);
return key;
}
@@ -72,6 +73,7 @@
}
+
CorLsa::CorLsa(string origR, uint8_t lst, uint32_t lsn, uint32_t lt
, double r, double theta)
{
@@ -83,6 +85,14 @@
corTheta=theta;
}
+string
+CorLsa::getCorLsaKey()
+{
+ string key;
+ key=origRouter + "/" + boost::lexical_cast<std::string>(3);
+ return key;
+}
+
string
CorLsa::getCorLsaData()
{
@@ -131,6 +141,14 @@
}
}
+string
+AdjLsa::getAdjLsaKey()
+{
+ string key;
+ key=origRouter + "/" + boost::lexical_cast<std::string>(2);
+ return key;
+}
+
string
AdjLsa::getAdjLsaData(){
string adjLsaData;
diff --git a/nlsr_lsa.hpp b/nlsr_lsa.hpp
index 225229f..a8d3861 100644
--- a/nlsr_lsa.hpp
+++ b/nlsr_lsa.hpp
@@ -56,7 +56,7 @@
{
lifeTime=lt;
}
- string getLsaKey();
+ //string getLsaKey();
protected:
string origRouter;
uint8_t lsType;
@@ -84,6 +84,8 @@
npl.insertIntoNpl(name);
}
+ string getNameLsaKey();
+
string getNameLsaData();
private:
@@ -113,7 +115,7 @@
{
adl.insert(adj);
}
-
+ string getAdjLsaKey();
string getAdjLsaData();
uint32_t getNoLink()
{
@@ -138,6 +140,7 @@
CorLsa(string origR, uint8_t lst, uint32_t lsn, uint32_t lt
, double r, double theta);
+ string getCorLsaKey();
string getCorLsaData();
double getCorRadius()
diff --git a/nlsr_lsdb.cpp b/nlsr_lsdb.cpp
index ffd49b1..8d7e141 100644
--- a/nlsr_lsdb.cpp
+++ b/nlsr_lsdb.cpp
@@ -33,7 +33,7 @@
static bool
nameLsaCompareByKey(NameLsa& nlsa1, string& key){
- return nlsa1.getLsaKey()==key;
+ return nlsa1.getNameLsaKey()==key;
}
@@ -69,7 +69,7 @@
bool
Lsdb::installNameLsa(NameLsa &nlsa)
{
- bool doesLsaExist_ = doesNameLsaExist(nlsa.getLsaKey());
+ bool doesLsaExist_ = doesNameLsaExist(nlsa.getNameLsaKey());
if ( !doesLsaExist_ )
{
// add name LSA
@@ -81,7 +81,7 @@
else
{
// check for newer name LSA
- NameLsa oldNameLsa=getNameLsa(nlsa.getLsaKey());
+ NameLsa oldNameLsa=getNameLsa(nlsa.getNameLsaKey());
// Discard or Update Name lsa, NPT, FIB
// if its not own LSA
}
@@ -94,7 +94,7 @@
{
std::list<NameLsa >::iterator it = std::find_if( nameLsdb.begin(),
nameLsdb.end(),
- bind(nameLsaCompareByKey, _1, nlsa.getLsaKey()));
+ bind(nameLsaCompareByKey, _1, nlsa.getNameLsaKey()));
if( it == nameLsdb.end())
{
@@ -152,7 +152,7 @@
*/
static bool
corLsaCompareByKey(CorLsa& clsa, string& key){
- return clsa.getLsaKey()==key;
+ return clsa.getCorLsaKey()==key;
}
bool
@@ -184,7 +184,7 @@
bool
Lsdb::installCorLsa(CorLsa &clsa)
{
- bool doesLsaExist_ = doesCorLsaExist(clsa.getLsaKey());
+ bool doesLsaExist_ = doesCorLsaExist(clsa.getCorLsaKey());
if ( !doesLsaExist_ )
{
// add cor LSA
@@ -196,7 +196,7 @@
else
{
// check for newer cor LSA
- CorLsa oldCorLsa=getCorLsa(clsa.getLsaKey());
+ CorLsa oldCorLsa=getCorLsa(clsa.getCorLsaKey());
}
@@ -208,7 +208,7 @@
{
std::list<CorLsa >::iterator it = std::find_if( corLsdb.begin(),
corLsdb.end(),
- bind(corLsaCompareByKey, _1, clsa.getLsaKey()));
+ bind(corLsaCompareByKey, _1, clsa.getCorLsaKey()));
if( it == corLsdb.end())
{
@@ -268,7 +268,7 @@
*/
static bool
adjLsaCompareByKey(AdjLsa& alsa, string& key){
- return alsa.getLsaKey()==key;
+ return alsa.getAdjLsaKey()==key;
}
@@ -315,7 +315,7 @@
{
std::list<AdjLsa >::iterator it = std::find_if( adjLsdb.begin(),
adjLsdb.end(),
- bind(adjLsaCompareByKey, _1, alsa.getLsaKey()));
+ bind(adjLsaCompareByKey, _1, alsa.getAdjLsaKey()));
if( it == adjLsdb.end()){
adjLsdb.push_back(alsa);
@@ -340,7 +340,7 @@
bool
Lsdb::installAdjLsa(nlsr& pnlsr, AdjLsa &alsa)
{
- bool doesLsaExist_ = doesAdjLsaExist(alsa.getLsaKey());
+ bool doesLsaExist_ = doesAdjLsaExist(alsa.getAdjLsaKey());
if ( !doesLsaExist_ )
{
// add Adj LSA
@@ -357,7 +357,7 @@
else
{
// check for newer name LSA
- AdjLsa oldAdjLsa=getAdjLsa(alsa.getLsaKey());
+ AdjLsa oldAdjLsa=getAdjLsa(alsa.getAdjLsaKey());
}
diff --git a/nlsr_rt.cpp b/nlsr_rt.cpp
index b2cc8b9..95b138d 100644
--- a/nlsr_rt.cpp
+++ b/nlsr_rt.cpp
@@ -22,6 +22,7 @@
{
if(pnlsr.getIsBuildAdjLsaSheduled() != 1)
{
+ cout<<"CLearing old routing table ....."<<endl;
clearRoutingTable();
clearDryRoutingTable(); // for dry run options
// calculate Link State routing
@@ -52,7 +53,7 @@
else
{
cout<<"No Adj LSA of router itself,";
- cout<< " so Routint table can not be calculated :("<<endl;
+ cout<< " so Routing table can not be calculated :("<<endl;
clearRoutingTable();
clearDryRoutingTable(); // for dry run options
// need to update NPT here
@@ -73,15 +74,13 @@
void
RoutingTable::calculateLsRoutingTable(nlsr& pnlsr)
{
+ cout<<"RoutingTable::calculateLsRoutingTable Called"<<endl;
Map vMap;
vMap.createMapFromAdjLsdb(pnlsr);
int numOfRouter=vMap.getMapSize();
LinkStateRoutingTableCalculator lsrtc(numOfRouter);
- lsrtc.allocateAdjMatrix();
- lsrtc.makeAdjMatrix(pnlsr,vMap);
lsrtc.calculatePath(vMap,boost::ref(*this),pnlsr);
- lsrtc.freeAdjMatrix();
}
@@ -101,12 +100,18 @@
void
RoutingTable::clearRoutingTable()
{
- rTable.clear();
+ if( rTable.size() > 0 )
+ {
+ rTable.clear();
+ }
}
void
RoutingTable::clearDryRoutingTable()
{
- dryTable.clear();
+ if (dryTable.size()>0 )
+ {
+ dryTable.clear();
+ }
}
diff --git a/nlsr_rtc.cpp b/nlsr_rtc.cpp
index fecc6bc..4dabf6a 100644
--- a/nlsr_rtc.cpp
+++ b/nlsr_rtc.cpp
@@ -42,6 +42,60 @@
}
}
+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()
{
@@ -53,17 +107,221 @@
}
void
-LinkStateRoutingTableCalculator::calculatePath(Map& pMap, RoutingTable& rt, nlsr& pnlsr)
+LinkStateRoutingTableCalculator::calculatePath(Map& pMap,
+ RoutingTable& rt, nlsr& pnlsr)
+{
+ cout<<"LinkStateRoutingTableCalculator::calculatePath Called"<<endl;
+ allocateAdjMatrix();
+ 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();
+
+ if ( pnlsr.getConfParameter().getMaxFacesPerPrefix() == 1 )
+ {
+ // Single Path
+ doDijkstraPathCalculation(sourceRouter);
+ // print all ls path -- debugging purpose
+ printAllLsPath(sourceRouter);
+ // update routing table
+ // update NPT ( FIB )
+ }
+ 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]);
+ doDijkstraPathCalculation(sourceRouter);
+ //update routing table
+ //update NPT ( FIB )
+ }
+
+ 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++){
+ parent[i]=EMPTY_PARENT;
+ distance[i]=INF_DISTANCE;
+ Q[i]=i;
+ }
+
+ if ( sourceRouter != NO_MAPPING_NUM ){
+ distance[sourceRouter]=0;
+ sortQueueByDistance(Q,distance,head,numOfRouter);
+
+ while (head < numOfRouter )
+ {
+ u=Q[head];
+ if(distance[u] == INF_DISTANCE)
+ {
+ break;
+ }
+
+ for(v=0 ; v <numOfRouter; v++)
+ {
+ if( adjMatrix[u][v] > 0 )
+ {
+ if ( isNotExplored(Q,v,head+1,numOfRouter) )
+ {
+ if( distance[u] + adjMatrix[u][v] < distance[v])
+ {
+ distance[v]=distance[u] + adjMatrix[u][v] ;
+ parent[v]=u;
+ }
+
+ }
+
+ }
+
+ }
+
+ head++;
+ sortQueueByDistance(Q,distance,head,numOfRouter);
+ }
+ }
+ delete [] Q;
+}
+
+void
+LinkStateRoutingTableCalculator::printAllLsPath(int sourceRouter)
+{
+ cout<<"LinkStateRoutingTableCalculator::printAllLsPath Called"<<endl;
+ cout<<"Source Router: "<<sourceRouter<<endl;
+ for(int i=0; i < numOfRouter ; i++)
+ {
+ if ( i!= sourceRouter )
+ {
+ printLsPath(i);
+ cout<<endl;
+ }
+ }
+}
+
+void
+LinkStateRoutingTableCalculator::printLsPath(int destRouter)
+{
+ if (parent[destRouter] != EMPTY_PARENT )
+ {
+ printLsPath(parent[destRouter]);
+ }
+
+ 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()
+{
+ parent=new int[numOfRouter];
+}
+
+void
+LinkStateRoutingTableCalculator::allocateDistance()
+{
+ distance= new double[numOfRouter];
+}
+
+void
+LinkStateRoutingTableCalculator::freeParent()
+{
+ delete [] parent;
+}
+
+void LinkStateRoutingTableCalculator::freeDistance()
+{
+ 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)
{
}
void
-HypRoutingTableCalculator::calculatePath(Map& pMap, RoutingTable& rt, nlsr& pnlsr)
-{
-}
-
-void
-HypDryRoutingTableCalculator::calculatePath(Map& pMap, RoutingTable& rt, nlsr& pnlsr)
+HypDryRoutingTableCalculator::calculatePath(Map& pMap,
+ RoutingTable& rt, nlsr& pnlsr)
{
}
diff --git a/nlsr_rtc.hpp b/nlsr_rtc.hpp
index 5b5cc3b..3efc665 100644
--- a/nlsr_rtc.hpp
+++ b/nlsr_rtc.hpp
@@ -23,10 +23,14 @@
{
numOfRouter=rn;
}
-
+protected:
void allocateAdjMatrix();
void makeAdjMatrix(nlsr& pnlsr,Map pMap);
+ void printAdjMatrix();
+ int getNumOfLinkfromAdjMatrix(int sRouter);
void freeAdjMatrix();
+ void adjustAdMatrix(int source, int link, double linkCost);
+ void getLinksFromAdjMatrix(int *links, double *linkCosts, int source);
protected:
double ** adjMatrix;
@@ -37,11 +41,48 @@
{
public:
LinkStateRoutingTableCalculator(int rn)
+ : EMPTY_PARENT(-12345)
+ , INF_DISTANCE(2147483647)
+ , NO_MAPPING_NUM(-1)
{
numOfRouter=rn;
}
+ void setNoLink(int nl)
+ {
+ vNoLink=nl;
+ }
void calculatePath(Map& pMap, RoutingTable& rt, nlsr& pnlsr);
+
+
+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 printAllLsPath(int sourceRouter);
+ void printLsPath(int destRouter);
+
+ 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;
};
diff --git a/nlsr_sm.hpp b/nlsr_sm.hpp
index eaae848..542203b 100644
--- a/nlsr_sm.hpp
+++ b/nlsr_sm.hpp
@@ -1,6 +1,13 @@
#ifndef NLSR_SM_HPP
#define NLSR_SM_HPP
+#include<list>
+#include<string>
+#include <ndn-cpp-dev/face.hpp>
+
+
+using namespace std;
+
class SequencingManager
{
public:
diff --git a/nlsr_test.cpp b/nlsr_test.cpp
index 4303f89..f9e39d7 100644
--- a/nlsr_test.cpp
+++ b/nlsr_test.cpp
@@ -54,7 +54,16 @@
ndn::bind(&nlsrTest::scheduledAddAdjacentLsa,pnlsr.getNlsrTesting(),
boost::ref(pnlsr)
,routerMaia,maiaAdj1,maiaAdj2));
-
+
+ //sheduling Adding LSAs for Router itself
+ string routerPollux("/ndn/memphis.edu/cs/pollux");
+ Adjacent polluxAdj1("/ndn/memphis.edu/cs/maia",9,13,1,0);
+ Adjacent polluxAdj2("/ndn/memphis.edu/cs/altair",12,23,1,0);
+
+ pnlsr.getScheduler().scheduleEvent(ndn::time::seconds(90),
+ ndn::bind(&nlsrTest::scheduledAddAdjacentLsa,pnlsr.getNlsrTesting(),
+ boost::ref(pnlsr)
+ ,routerPollux,polluxAdj1,polluxAdj2));
}