docs: improve Doxygen comments.
refs: #1435
Change-Id: I21624ef4eec393c82a50229a07e8277fb6ae4ddf
diff --git a/src/route/map.hpp b/src/route/map.hpp
index a37f1ac..b9729fc 100644
--- a/src/route/map.hpp
+++ b/src/route/map.hpp
@@ -43,7 +43,12 @@
{
}
+ /*! \brief Add a map entry to this map.
+ \param rtrName The name of the router.
+ Adds a router to this map. Each entry is also given an arbitrary,
+ ascending mappingNo (mapping number).
+ */
void
addEntry(const ndn::Name& rtrName);
diff --git a/src/route/name-prefix-table-entry.cpp b/src/route/name-prefix-table-entry.cpp
index 1236777..a9682ef 100644
--- a/src/route/name-prefix-table-entry.cpp
+++ b/src/route/name-prefix-table-entry.cpp
@@ -33,9 +33,11 @@
NamePrefixTableEntry::generateNhlfromRteList()
{
m_nexthopList.reset();
+ // For every routing table entry associated with this name prefix
for (std::list<RoutingTableEntry>::iterator it = m_rteList.begin();
it != m_rteList.end(); ++it)
{
+ // Add every next hop from each routing table entry to this entry's NHL.
for (std::list<NextHop>::iterator nhit =
(*it).getNexthopList().getNextHops().begin();
nhit != (*it).getNexthopList().getNextHops().end(); ++nhit)
diff --git a/src/route/name-prefix-table-entry.hpp b/src/route/name-prefix-table-entry.hpp
index a3428dd..ddae8ce 100644
--- a/src/route/name-prefix-table-entry.hpp
+++ b/src/route/name-prefix-table-entry.hpp
@@ -77,12 +77,20 @@
return m_nexthopList;
}
+ /*! \brief Generates a next-hop list from routing table entries. */
void
generateNhlfromRteList();
void
removeRoutingTableEntry(RoutingTableEntry& rte);
+ /*! \brief Adds a routing table entry to this object's list.
+ \param rte The routing table entry.
+
+ Adds a routing table entry to this NPT entry's list. (reminder:
+ each RTE has a next-hop list) They are used to calculate this
+ entry's next-hop list.
+ */
void
addRoutingTableEntry(RoutingTableEntry& rte);
diff --git a/src/route/name-prefix-table.cpp b/src/route/name-prefix-table.cpp
index 0add13e..e5199b0 100644
--- a/src/route/name-prefix-table.cpp
+++ b/src/route/name-prefix-table.cpp
@@ -42,21 +42,22 @@
void
NamePrefixTable::addEntry(const ndn::Name& name, RoutingTableEntry& rte)
{
+ // Check if the advertised name prefix is in the table already.
NptEntryList::iterator it = std::find_if(m_table.begin(),
m_table.end(),
bind(&npteCompare, _1, name));
+ // If not, create a new entry and add it.
if (it == m_table.end()) {
_LOG_TRACE("Adding origin: " << rte.getDestination() << " to new name prefix: " << name);
NamePrefixTableEntry entry(name);
+ entry.addRoutingTableEntry(rte); // Add this RTE to this new NPT entry.
+ entry.generateNhlfromRteList(); // Generate a list of next-hops from the RTE.
+ entry.getNexthopList().sort(); // Sort it.
- entry.addRoutingTableEntry(rte);
+ m_table.push_back(entry); // Add the new, completed entry into the main table.
- entry.generateNhlfromRteList();
- entry.getNexthopList().sort();
-
- m_table.push_back(entry);
-
+ // If the RTE we added has any next hops, we inform the FIB of this.
if (rte.getNexthopList().getSize() > 0) {
_LOG_TRACE("Updating FIB with next hops for " << entry);
m_nlsr.getFib().update(name, entry.getNexthopList());
@@ -64,22 +65,26 @@
}
else {
_LOG_TRACE("Adding origin: " << rte.getDestination() << " to existing prefix: " << *it);
-
+ // Update the existing entry with the new RTE.
it->addRoutingTableEntry(rte);
- it->generateNhlfromRteList();
- it->getNexthopList().sort();
+ it->generateNhlfromRteList(); // Rebuild the list of next-hops
+ it->getNexthopList().sort(); // Sort it.
+ // As above, inform the FIB of this fact.
+ // We may possibly have a new best next-hop for this name prefix
+ // So this is a necessary step.
if (it->getNexthopList().getSize() > 0) {
_LOG_TRACE("Updating FIB with next hops for " << *it);
m_nlsr.getFib().update(name, it->getNexthopList());
}
else {
- // The routing table may recalculate and add a routing table entry with no next hops to
- // replace an existing routing table entry. In this case, the name prefix is no longer
- // reachable through a next hop and should be removed from the FIB. But, the prefix
- // should remain in the Name Prefix Table as a future routing table calculation may
- // add next hops.
+ // The routing table may recalculate and add a routing table
+ // entry with no next hops to replace an existing routing table
+ // entry. In this case, the name prefix is no longer reachable
+ // through a next hop and should be removed from the FIB. But,
+ // the prefix should remain in the Name Prefix Table as a future
+ // routing table calculation may add next hops.
_LOG_TRACE(*it << " has no next hops; removing from FIB");
m_nlsr.getFib().remove(name);
}
@@ -162,7 +167,9 @@
_LOG_DEBUG("Updating table with newly calculated routes");
// Update each name prefix entry in the Name Prefix Table with newly calculated next hops
+ // For each entry in the NPT
for (const NamePrefixTableEntry& prefixEntry : m_table) {
+ // For each routing table entry
for (const RoutingTableEntry& routingEntry : prefixEntry.getRteList()) {
_LOG_TRACE("Updating next hops to origin: " << routingEntry.getDestination()
<< " for prefix: " << prefixEntry);
@@ -170,6 +177,7 @@
RoutingTableEntry* rteCheck =
m_nlsr.getRoutingTable().findRoutingTableEntry(routingEntry.getDestination());
+ // If there is a routing table entry for this prefix, update the NPT with it.
if (rteCheck != nullptr) {
addEntry(prefixEntry.getNamePrefix(), *rteCheck);
}
diff --git a/src/route/name-prefix-table.hpp b/src/route/name-prefix-table.hpp
index 985f91e..d8a3bc1 100644
--- a/src/route/name-prefix-table.hpp
+++ b/src/route/name-prefix-table.hpp
@@ -42,6 +42,20 @@
{
}
+ /*! \brief Adds an entry to the NPT.
+ \param name The name prefix that is being advertised.
+ \param destRouter The destination router that is advertising the prefix.
+
+ Adds a destination router to the name prefix. If there isn't
+ currently an entry present for the prefix, one is made and
+ added. If there is no routing table entry available for the
+ destination router, a placeholder routing table entry without next
+ hops will be made. Since this function can be called when a
+ routing table entry has been updated to have no hops (i.e. is
+ unreachable), this function will check for the number of next hops
+ an entry has. If it is found to have no next hops, the NPT will
+ inform the FIB to remove that prefix.
+ */
void
addEntry(const ndn::Name& name, const ndn::Name& destRouter);
@@ -61,6 +75,11 @@
end() const;
private:
+ /*! \brief Adds an entry to the NPT table.
+ \param name The name prefix to add to the table.
+ \param rte The routing table entry with the next hop information to
+ reach the prefix.
+ */
void
addEntry(const ndn::Name& name, RoutingTableEntry& rte);
diff --git a/src/route/nexthop-list.cpp b/src/route/nexthop-list.cpp
index dc11113..ed46b55 100644
--- a/src/route/nexthop-list.cpp
+++ b/src/route/nexthop-list.cpp
@@ -59,7 +59,7 @@
}
}
-/**
+/*!
Add next hop to the Next Hop list
If next hop is new it is added
If next hop already exists in next
@@ -82,7 +82,7 @@
}
}
-/**
+/*!
Remove a next hop only if both next hop face and route cost are same
*/
diff --git a/src/route/nexthop-list.hpp b/src/route/nexthop-list.hpp
index be0c144..0c57ba3 100644
--- a/src/route/nexthop-list.hpp
+++ b/src/route/nexthop-list.hpp
@@ -45,9 +45,22 @@
{
}
+
+ /*! \brief Adds a next hop to the list.
+ \param nh The next hop.
+
+ Add next hop to the Next Hop list If next hop is new it is added
+ If next hop already exists in next hop list then updates the route
+ cost with new next hop's route cost
+ */
void
addNextHop(NextHop& nh);
+ /*! \brief Removes a next hop.
+ \param nh The next hop.
+
+ Remove a next hop only if both next hop face and route cost are same.
+ */
void
removeNextHop(NextHop& nh);
diff --git a/src/route/nexthop.hpp b/src/route/nexthop.hpp
index 72435cd..8c5ffd1 100644
--- a/src/route/nexthop.hpp
+++ b/src/route/nexthop.hpp
@@ -103,15 +103,15 @@
bool m_isHyperbolic;
PUBLIC_WITH_TESTS_ELSE_PRIVATE:
- /** \brief Used to adjust floating point route costs to integers
- * Since NFD uses integer route costs in the FIB, hyperbolic paths with similar route costs
- * will be rounded to integers and installed with identical nexthop costs.
- *
- * e.g. costs 12.34 and 12.35 will be equal in NFD's FIB
- *
- * This multiplier is used to differentiate similar route costs in the FIB.
- *
- * e.g costs 12.34 and 12.35 will be installed into NFD's FIB as 12340 and 12350
+ /*! \brief Used to adjust floating point route costs to integers
+ Since NFD uses integer route costs in the FIB, hyperbolic paths with similar route costs
+ will be rounded to integers and installed with identical nexthop costs.
+
+ e.g. costs 12.34 and 12.35 will be equal in NFD's FIB
+
+ This multiplier is used to differentiate similar route costs in the FIB.
+
+ e.g costs 12.34 and 12.35 will be installed into NFD's FIB as 12340 and 12350
*/
static const uint64_t HYPERBOLIC_COST_ADJUSTMENT_FACTOR = 1000;
};
diff --git a/src/route/routing-table-calculator.cpp b/src/route/routing-table-calculator.cpp
index ccc6114..b3a66b3 100644
--- a/src/route/routing-table-calculator.cpp
+++ b/src/route/routing-table-calculator.cpp
@@ -60,11 +60,14 @@
RoutingTableCalculator::makeAdjMatrix(Nlsr& pnlsr, Map pMap)
{
std::list<AdjLsa> adjLsdb = pnlsr.getLsdb().getAdjLsdb();
+ // For each LSA represented in the map
for (std::list<AdjLsa>::iterator it = adjLsdb.begin(); it != adjLsdb.end() ; it++) {
+
int32_t row = pMap.getMappingNoByRouterName((*it).getOrigRouter());
std::list<Adjacent> adl = (*it).getAdl().getAdjList();
+ // For each adjacency represented in the LSA
for (std::list<Adjacent>::iterator itAdl = adl.begin(); itAdl != adl.end() ; itAdl++) {
int32_t col = pMap.getMappingNoByRouterName((*itAdl).getName());
@@ -78,14 +81,17 @@
}
}
- // Links that do not have the same cost for both directions should have their
- // costs corrected:
+ // Links that do not have the same cost for both directions should
+ // have their costs corrected:
//
- // If the cost of one side of the link is 0, both sides of the link should have their cost
- // corrected to 0.
+ // If the cost of one side of the link is 0, both sides of the
+ // link should have their cost corrected to 0.
//
// Otherwise, both sides of the link should use the larger of the two costs.
//
+ // Additionally, this means that we can halve the amount of space
+ // that the matrix uses by only maintaining a triangle.
+ // - But that is not yet implemented.
for (size_t row = 0; row < m_nRouters; ++row) {
for (size_t col = 0; col < m_nRouters; ++col) {
double toCost = adjMatrix[row][col];
@@ -173,7 +179,6 @@
delete [] adjMatrix;
}
-
void
RoutingTableCalculator::allocateLinks()
{
@@ -208,12 +213,12 @@
makeAdjMatrix(pnlsr, pMap);
writeAdjMatrixLog();
int sourceRouter = pMap.getMappingNoByRouterName(pnlsr.getConfParameter().getRouterPrefix());
- allocateParent();
- allocateDistance();
+ allocateParent(); // These two matrices are used in Dijkstra's algorithm.
+ allocateDistance(); //
if (pnlsr.getConfParameter().getMaxFacesPerPrefix() == 1) {
- // Single Path
+ // In the single path case we can simply run Dijkstra's algorithm.
doDijkstraPathCalculation(sourceRouter);
- // update routing table
+ // Inform the routing table of the new next hops.
addAllLsNextHopsToRoutingTable(pnlsr, rt, pMap, sourceRouter);
}
else {
@@ -221,12 +226,15 @@
setNoLink(getNumOfLinkfromAdjMatrix(sourceRouter));
allocateLinks();
allocateLinkCosts();
+ // Gets a sparse listing of adjacencies for path calculation
getLinksFromAdjMatrix(links, linkCosts, sourceRouter);
for (int i = 0 ; i < vNoLink; i++) {
+ // Simulate that only the current neighbor is accessible
adjustAdMatrix(sourceRouter, links[i], linkCosts[i]);
writeAdjMatrixLog();
+ // Do Dijkstra's algorithm using the current neighbor as your start.
doDijkstraPathCalculation(sourceRouter);
- //update routing table
+ // Update the routing table with the calculations.
addAllLsNextHopsToRoutingTable(pnlsr, rt, pMap, sourceRouter);
}
freeLinks();
@@ -242,32 +250,44 @@
{
int i;
int v, u;
- int* Q = new int[m_nRouters];
+ int* Q = new int[m_nRouters]; // Each cell represents the router with that mapping no.
int head = 0;
/* Initiate the Parent */
for (i = 0 ; i < static_cast<int>(m_nRouters); i++) {
m_parent[i] = EMPTY_PARENT;
+ // Array where the ith element is the distance to the router with mapping no i.
m_distance[i] = INF_DISTANCE;
Q[i] = i;
}
if (sourceRouter != NO_MAPPING_NUM) {
+ // Distance to source from source is always 0.
m_distance[sourceRouter] = 0;
sortQueueByDistance(Q, m_distance, head, m_nRouters);
+ // While we haven't visited every node.
while (head < static_cast<int>(m_nRouters)) {
- u = Q[head];
+ u = Q[head]; // Set u to be the current node pointed to by head.
if (m_distance[u] == INF_DISTANCE) {
- break;
+ break; // This can only happen when there are no accessible nodes.
}
+ // Iterate over the adjacent nodes to u.
for (v = 0 ; v < static_cast<int>(m_nRouters); v++) {
+ // If the current node is accessible.
if (adjMatrix[u][v] > 0) {
+ // And we haven't visited it yet.
if (isNotExplored(Q, v, head + 1, m_nRouters)) {
+ // And if the distance to this node + from this node to v
+ // is less than the distance from our source node to v
+ // that we got when we built the adj LSAs
if (m_distance[u] + adjMatrix[u][v] < m_distance[v]) {
+ // Set the new distance
m_distance[v] = m_distance[u] + adjMatrix[u][v] ;
+ // Set how we get there.
m_parent[v] = u;
}
}
}
}
+ // Increment the head position, resort the list by distance from where we are.
head++;
sortQueueByDistance(Q, m_distance, head, m_nRouters);
}
@@ -283,14 +303,19 @@
int nextHopRouter = 0;
+ // For each router we have
for (size_t i = 0; i < m_nRouters ; i++) {
if (i != sourceRouter) {
+ // Obtain the next hop that was determined by the algorithm
nextHopRouter = getLsNextHop(i, sourceRouter);
+ // If this router is accessible at all
if (nextHopRouter != NO_NEXT_HOP) {
+ // Fetch its distance
double routeCost = m_distance[i];
+ // Fetch its actual name
ndn::Name nextHopRouterName = pMap.getRouterNameByMappingNo(nextHopRouter);
std::string nextHopFace =
pnlsr.getAdjacencyList().getAdjacent(nextHopRouterName).getConnectingFaceUri();
diff --git a/src/route/routing-table-calculator.hpp b/src/route/routing-table-calculator.hpp
index 4ee683e..bfeeb87 100644
--- a/src/route/routing-table-calculator.hpp
+++ b/src/route/routing-table-calculator.hpp
@@ -46,30 +46,56 @@
m_nRouters = nRouters;
}
protected:
+ /*! \brief Allocate the space needed for the adj. matrix. */
void
allocateAdjMatrix();
+ /*! \brief Zero every cell of the matrix to ensure that the memory is safe. */
void
initMatrix();
+ /*! \brief Constructs an adj. matrix to calculate with.
+ \param pnlsr The NLSR object that contains the LSAs that we need to iterate
+ over.
+ \param pMap The map to populate with the adj. data.
+ */
void
makeAdjMatrix(Nlsr& pnlsr, Map pMap);
void
writeAdjMatrixLog();
+ /*! \brief Returns how many links a router in the matrix has.
+ \param sRouter The router to count the links of.
+ */
int
getNumOfLinkfromAdjMatrix(int sRouter);
void
freeAdjMatrix();
-
+ /*! \brief Adjust a link cost in the adj. matrix
+ \param source The source router whose adjacency to adjust.
+ \param link The adjacency of the source to adjust.
+ \param linkCost The cost to change to.
+ */
void
adjustAdMatrix(int source, int link, double linkCost);
+ /*! \brief Populates temp. variables with the link costs for some router.
+ \param source The router whose values are to be adjusted.
+ \param links An integer pointer array for the link mappingNos.
+ \param linkCosts A double pointer array that stores the link costs.
+
+ Obtains a sparse list of adjacencies and link costs for some
+ router. Since this is sparse, that means while generating these
+ arrays, if there is no adjacency at i in the matrix, these
+ temporary variables will not contain a 0 at i, but rather will
+ contain the values for the next valid adjacency.
+ */
void
getLinksFromAdjMatrix(int* links, double* linkCosts, int source);
+ /*! Allocates an array large enough to hold multipath calculation temps. */
void
allocateLinks();
@@ -113,12 +139,30 @@
calculatePath(Map& pMap, RoutingTable& rt, Nlsr& pnlsr);
private:
+ /*! \brief Performs a Dijkstra's calculation over the adjacency matrix.
+ \param sourceRouter The origin router to compute paths from.
+ */
void
doDijkstraPathCalculation(int sourceRouter);
+ /*! \brief Sort the elements of a list.
+ \param Q The array that contains the elements to sort.
+ \param dist The array that contains the distances.
+ \param start The first element in the list to sort.
+ \param element The last element in the list to sort through.
+
+ Sorts the list based on distance. The distances are indexed by
+ their mappingNo in dist. Currently uses an insertion sort.
+ */
void
sortQueueByDistance(int* Q, double* dist, int start, int element);
+ /*! \brief Returns whether an element has been visited yet.
+ \param Q The list of elements to look through.
+ \param u The element to check.
+ \param start The start of list to look through.
+ \param element The end of the list to look through.
+ */
int
isNotExplored(int* Q, int u, int start, int element);
@@ -126,6 +170,10 @@
addAllLsNextHopsToRoutingTable(Nlsr& pnlsr, RoutingTable& rt,
Map& pMap, uint32_t sourceRouter);
+ /*! \brief Determines a destination's next hop.
+ \param dest The router whose next hop we want to determine.
+ \param source The router to determine a next path to.
+ */
int
getLsNextHop(int dest, int source);
diff --git a/src/route/routing-table.cpp b/src/route/routing-table.cpp
index 9d45f2e..b610722 100644
--- a/src/route/routing-table.cpp
+++ b/src/route/routing-table.cpp
@@ -84,7 +84,7 @@
if (pnlsr.getConfParameter().getHyperbolicState() == HYPERBOLIC_STATE_DRY_RUN) {
calculateHypDryRoutingTable(pnlsr);
}
- //need to update NPT here
+ // Inform the NPT that updates have been made
_LOG_DEBUG("Calling Update NPT With new Route");
pnlsr.getNamePrefixTable().updateWithNewRoute();
writeLog(pnlsr.getConfParameter().getHyperbolicState());
@@ -117,7 +117,6 @@
}
}
-
void
RoutingTable::calculateLsRoutingTable(Nlsr& nlsr)
{
@@ -185,7 +184,6 @@
return rte.getDestination() == destRouter;
}
-// function related to manipulation of routing table
void
RoutingTable::addNextHop(const ndn::Name& destRouter, NextHop& nh)
{
@@ -237,7 +235,6 @@
}
}
-//function related to manipulation of dry routing table
void
RoutingTable::addNextHopToDryTable(const ndn::Name& destRouter, NextHop& nh)
{
@@ -274,4 +271,3 @@
}
} // namespace nlsr
-
diff --git a/src/route/routing-table.hpp b/src/route/routing-table.hpp
index 1fd8049..c8c0c52 100644
--- a/src/route/routing-table.hpp
+++ b/src/route/routing-table.hpp
@@ -47,18 +47,34 @@
{
}
+ /*! \brief Calculates a list of next hops for each router in the network.
+ \param pnlsr The NLSR object that contains the LSAs needed for adj. info.
+
+ Calculates the list of next hops to every other router in the network.
+ */
void
calculate(Nlsr& pnlsr);
+ /*! \brief Adds a next hop to a routing table entry.
+ \param destRouter The destination router whose RTE we want to modify.
+ \param nh The next hop to add to the RTE.
+ */
void
addNextHop(const ndn::Name& destRouter, NextHop& nh);
+ /*! \brief Adds a next hop to a routing table entry in a dry run scenario.
+ \param destRouter The destination router whose RTE we want to modify.
+ \param nh The next hop to add to the router.
+ */
void
addNextHopToDryTable(const ndn::Name& destRouter, NextHop& nh);
RoutingTableEntry*
findRoutingTableEntry(const ndn::Name& destRouter);
+ /*! \brief Schedules a calculation event in the event scheduler.
+ \param pnlsr The NLSR whose scheduling status is needed.
+ */
void
scheduleRoutingTableCalculation(Nlsr& pnlsr);
@@ -81,12 +97,15 @@
}
private:
+ /*! \brief Calculates a link-state routing table. */
void
calculateLsRoutingTable(Nlsr& pnlsr);
+ /*! \brief Calculates a HR routing table. */
void
calculateHypRoutingTable(Nlsr& pnlsr);
+ /*! \brief Calculates a dry-run HR routing table. */
void
calculateHypDryRoutingTable(Nlsr& pnlsr);