Link State Routing Calculation
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)
{
}