route: handle zero cost links
refs: #4978
Change-Id: I461bdac9e10cb8362a7624b177ee68aa20d3ff3e
diff --git a/src/adjacent.cpp b/src/adjacent.cpp
index 950a7ae..4afe6d7 100644
--- a/src/adjacent.cpp
+++ b/src/adjacent.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2014-2018, The University of Memphis,
+ * Copyright (c) 2014-2019, The University of Memphis,
* Regents of the University of California
*
* This file is part of NLSR (Named-data Link State Routing).
@@ -30,7 +30,8 @@
INIT_LOGGER(Adjacent);
-const float Adjacent::DEFAULT_LINK_COST = 10.0;
+const double Adjacent::DEFAULT_LINK_COST = 10.0;
+const double Adjacent::NON_ADJACENT_COST = -12345;
Adjacent::Adjacent()
: m_name()
@@ -56,13 +57,27 @@
Status s, uint32_t iton, uint64_t faceId)
: m_name(an)
, m_faceUri(faceUri)
- , m_linkCost(lc)
, m_status(s)
, m_interestTimedOutNo(iton)
, m_faceId(faceId)
{
+ this->setLinkCost(lc);
}
+void
+Adjacent::setLinkCost(double lc)
+{
+ // NON_ADJACENT_COST is a negative value and is used for nodes that aren't direct neighbors.
+ // But for direct/active neighbors, the cost cannot be negative.
+ if (lc < 0 && lc != NON_ADJACENT_COST)
+ {
+ NLSR_LOG_ERROR(" Neighbor's link-cost cannot be negative");
+ BOOST_THROW_EXCEPTION(ndn::tlv::Error("Neighbor's link-cost cannot be negative"));
+ }
+
+ m_linkCost = lc;
+}
+
bool
Adjacent::operator==(const Adjacent& adjacent) const
{
diff --git a/src/adjacent.hpp b/src/adjacent.hpp
index 72a8d98..c85f0ff 100644
--- a/src/adjacent.hpp
+++ b/src/adjacent.hpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2014-2018, The University of Memphis,
+ * Copyright (c) 2014-2019, The University of Memphis,
* Regents of the University of California
*
* This file is part of NLSR (Named-data Link State Routing).
@@ -77,18 +77,14 @@
m_faceUri = faceUri;
}
- uint64_t
+ double
getLinkCost() const
{
- uint64_t linkCost = static_cast<uint64_t>(ceil(m_linkCost));
- return linkCost;
+ return ceil(m_linkCost);
}
void
- setLinkCost(double lc)
- {
- m_linkCost = lc;
- }
+ setLinkCost(double lc);
Status
getStatus() const
@@ -161,7 +157,8 @@
writeLog();
public:
- static const float DEFAULT_LINK_COST;
+ static const double DEFAULT_LINK_COST;
+ static const double NON_ADJACENT_COST;
private:
/*! m_name The NLSR-configured router name of the neighbor */
diff --git a/src/conf-parameter.hpp b/src/conf-parameter.hpp
index 1ecf6c8..6b63937 100644
--- a/src/conf-parameter.hpp
+++ b/src/conf-parameter.hpp
@@ -415,7 +415,8 @@
return m_stateFileDir;
}
- void setConfFileNameDynamic(const std::string& confFileDynamic)
+ void
+ setConfFileNameDynamic(const std::string& confFileDynamic)
{
m_confFileNameDynamic = confFileDynamic;
}
diff --git a/src/lsa.cpp b/src/lsa.cpp
index bee69db..5930e99 100644
--- a/src/lsa.cpp
+++ b/src/lsa.cpp
@@ -248,11 +248,16 @@
ndn::Name adjName(*tok_iter++);
std::string connectingFaceUri(*tok_iter++);
double linkCost = boost::lexical_cast<double>(*tok_iter++);
+
Adjacent adjacent(adjName, ndn::FaceUri(connectingFaceUri), linkCost,
Adjacent::STATUS_INACTIVE, 0, 0);
addAdjacent(adjacent);
}
}
+ // Ignore neighbors with negative cost received from the Adjacent LSA data.
+ catch (const ndn::tlv::Error& e) {
+ NLSR_LOG_ERROR(e.what());
+ }
catch (const std::exception& e) {
NLSR_LOG_ERROR("Could not deserialize from content: " << e.what());
return false;
diff --git a/src/lsdb.cpp b/src/lsdb.cpp
index 01c1ee0..1e3cf1b 100644
--- a/src/lsdb.cpp
+++ b/src/lsdb.cpp
@@ -218,12 +218,10 @@
m_namePrefixTable.addEntry(name, nlsa.getOrigRouter());
}
}
- }
- if (nlsa.getOrigRouter() != m_confParam.getRouterPrefix()) {
- ndn::time::system_clock::Duration duration = nlsa.getExpirationTimePoint() -
- ndn::time::system_clock::now();
+ auto duration = nlsa.getExpirationTimePoint() - ndn::time::system_clock::now();
timeToExpire = ndn::time::duration_cast<ndn::time::seconds>(duration);
}
+
nlsa.setExpiringEventId(scheduleNameLsaExpiration(nlsa.getKey(),
nlsa.getLsSeqNo(),
timeToExpire));
diff --git a/src/route/routing-table-calculator.cpp b/src/route/routing-table-calculator.cpp
index 68a7ca2..a079933 100644
--- a/src/route/routing-table-calculator.cpp
+++ b/src/route/routing-table-calculator.cpp
@@ -25,6 +25,7 @@
#include "nexthop.hpp"
#include "nlsr.hpp"
#include "logger.hpp"
+#include "adjacent.hpp"
#include <iostream>
#include <boost/math/constants/constants.hpp>
@@ -35,6 +36,11 @@
INIT_LOGGER(route.RoutingTableCalculator);
+const int LinkStateRoutingTableCalculator::EMPTY_PARENT = -12345;
+const double LinkStateRoutingTableCalculator::INF_DISTANCE = 2147483647;
+const int LinkStateRoutingTableCalculator::NO_MAPPING_NUM = -1;
+const int LinkStateRoutingTableCalculator::NO_NEXT_HOP = -12345;
+
void
RoutingTableCalculator::allocateAdjMatrix()
{
@@ -50,7 +56,7 @@
{
for (size_t i = 0; i < m_nRouters; i++) {
for (size_t j = 0; j < m_nRouters; j++) {
- adjMatrix[i][j] = 0;
+ adjMatrix[i][j] = Adjacent::NON_ADJACENT_COST;
}
}
}
@@ -79,8 +85,8 @@
// 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 NON_ADJACENT_COST (i.e. broken) or negative,
+ // both direction of the link should have their cost corrected to NON_ADJACENT_COST.
//
// Otherwise, both sides of the link should use the larger of the two costs.
//
@@ -93,10 +99,10 @@
double fromCost = adjMatrix[col][row];
if (fromCost != toCost) {
- double correctedCost = 0.0;
+ double correctedCost = Adjacent::NON_ADJACENT_COST;
- if (toCost != 0 && fromCost != 0) {
- // If both sides of the link are up, use the larger cost
+ if (toCost >= 0 && fromCost >= 0) {
+ // If both sides of the link are up, use the larger cost else break the link
correctedCost = std::max(toCost, fromCost);
}
@@ -152,7 +158,8 @@
adjMatrix[source][i] = linkCost;
}
else {
- adjMatrix[source][i] = 0;
+ // if "i" is not a link to the source, set it's cost to a non adjacent value.
+ adjMatrix[source][i] = Adjacent::NON_ADJACENT_COST;
}
}
}
@@ -163,7 +170,7 @@
int noLink = 0;
for (size_t i = 0; i < m_nRouters; i++) {
- if (adjMatrix[sRouter][i] > 0) {
+ if (adjMatrix[sRouter][i] >= 0 && i != static_cast<size_t>(sRouter)) { // make sure "i" is not self
noLink++;
}
}
@@ -177,7 +184,7 @@
int j = 0;
for (size_t i = 0; i < m_nRouters; i++) {
- if (adjMatrix[source][i] > 0) {
+ if (adjMatrix[source][i] >= 0 && i != static_cast<size_t>(source)) {// make sure "i" is not self
links[j] = i;
linkCosts[j] = adjMatrix[source][i];
j++;
@@ -290,7 +297,7 @@
// 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) {
+ 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
@@ -328,7 +335,6 @@
// 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) {
@@ -469,11 +475,10 @@
// Could not compute distance
if (distance == UNKNOWN_DISTANCE) {
- NLSR_LOG_WARN("Could not calculate hyperbolic distance from " << srcRouterName << " to " <<
- *destRouterName);
+ NLSR_LOG_WARN("Could not calculate hyperbolic distance from " << srcRouterName
+ << " to " << *destRouterName);
continue;
}
-
addNextHop(*destRouterName, srcFaceUri, distance, rt);
}
}
diff --git a/src/route/routing-table-calculator.hpp b/src/route/routing-table-calculator.hpp
index dd1e658..0a40a1c 100644
--- a/src/route/routing-table-calculator.hpp
+++ b/src/route/routing-table-calculator.hpp
@@ -40,19 +40,18 @@
class RoutingTableCalculator
{
public:
- RoutingTableCalculator()
- {
- }
RoutingTableCalculator(size_t nRouters)
{
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. */
+ /*! \brief set NON_ADJACENT_COST i.e. -12345 to every cell of the matrix to
+ ensure that the memory is safe. This is also to incorporate zero cost links */
void
initMatrix();
@@ -63,6 +62,9 @@
void
makeAdjMatrix(const std::list<AdjLsa>& adjLsaList, Map& pMap);
+ /*! \brief Writes a formated adjacent matrix to DEBUG log
+ \param map The map containing adjacent matrix data
+ */
void
writeAdjMatrixLog(const Map& map) const;
@@ -90,8 +92,8 @@
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.
+ temporary variables will not contain a NON_ADJACENT_COST (-12345) at i,
+ but rather will contain the values for the next valid adjacency.
*/
void
getLinksFromAdjMatrix(int* links, double* linkCosts, int source);
@@ -122,6 +124,7 @@
int vNoLink;
int* links;
double* linkCosts;
+
};
class LinkStateRoutingTableCalculator: public RoutingTableCalculator
@@ -129,10 +132,6 @@
public:
LinkStateRoutingTableCalculator(size_t nRouters)
: RoutingTableCalculator(nRouters)
- , EMPTY_PARENT(-12345)
- , INF_DISTANCE(2147483647)
- , NO_MAPPING_NUM(-1)
- , NO_NEXT_HOP(-12345)
{
}
@@ -155,6 +154,9 @@
Sorts the list based on distance. The distances are indexed by
their mappingNo in dist. Currently uses an insertion sort.
+
+ The cost between two nodes can be zero or greater than zero.
+
*/
void
sortQueueByDistance(int* Q, double* dist, int start, int element);
@@ -195,10 +197,10 @@
int* m_parent;
double* m_distance;
- const int EMPTY_PARENT;
- const double INF_DISTANCE;
- const int NO_MAPPING_NUM;
- const int NO_NEXT_HOP;
+ static const int EMPTY_PARENT;
+ static const double INF_DISTANCE;
+ static const int NO_MAPPING_NUM;
+ static const int NO_NEXT_HOP;
};
diff --git a/tests/test-link-state-calculator.cpp b/tests/test-link-state-calculator.cpp
index 7ca4fb9..8e1710b 100644
--- a/tests/test-link-state-calculator.cpp
+++ b/tests/test-link-state-calculator.cpp
@@ -28,6 +28,7 @@
#include "test-common.hpp"
#include "route/map.hpp"
#include "route/routing-table.hpp"
+#include "adjacent.hpp"
#include <ndn-cxx/util/dummy-client-face.hpp>
@@ -217,17 +218,18 @@
}
}
-BOOST_AUTO_TEST_CASE(AsymmetricZeroCost)
+BOOST_AUTO_TEST_CASE(NonAdjacentCost)
{
// Asymmetric link cost between B and C
ndn::Name key = ndn::Name(ROUTER_B_NAME).append(std::to_string(Lsa::Type::ADJACENCY));
- AdjLsa* lsa = nlsr.m_lsdb.findAdjLsa(key);
+ auto lsa = nlsr.m_lsdb.findAdjLsa(key);
BOOST_REQUIRE(lsa != nullptr);
auto c = lsa->getAdl().findAdjacent(ROUTER_C_NAME);
BOOST_REQUIRE(c != conf.getAdjacencyList().end());
- c->setLinkCost(0);
+ // Break the link between B - C by setting it to a NON_ADJACENT_COST.
+ c->setLinkCost(Adjacent::NON_ADJACENT_COST);
// Calculation should consider the link between B and C as down
LinkStateRoutingTableCalculator calculator(map.getMapSize());
@@ -237,25 +239,83 @@
RoutingTableEntry* entryB = routingTable.findRoutingTableEntry(ROUTER_B_NAME);
BOOST_REQUIRE(entryB != nullptr);
- NexthopList& bHopList = entryB->getNexthopList();
+ auto bHopList = entryB->getNexthopList();
BOOST_REQUIRE_EQUAL(bHopList.getNextHops().size(), 1);
- const NextHop& nextHopForB = *(bHopList.getNextHops().begin());
+ const auto nextHopForB = bHopList.getNextHops().begin();
- BOOST_CHECK(nextHopForB.getConnectingFaceUri() == ROUTER_B_FACE &&
- nextHopForB.getRouteCostAsAdjustedInteger() == LINK_AB_COST);
+ BOOST_CHECK(nextHopForB->getConnectingFaceUri() == ROUTER_B_FACE &&
+ nextHopForB->getRouteCostAsAdjustedInteger() == LINK_AB_COST);
// Router A should be able to get to C through C but not through B
- RoutingTableEntry* entryC = routingTable.findRoutingTableEntry(ROUTER_C_NAME);
+ auto entryC = routingTable.findRoutingTableEntry(ROUTER_C_NAME);
BOOST_REQUIRE(entryC != nullptr);
NexthopList& cHopList = entryC->getNexthopList();
BOOST_REQUIRE_EQUAL(cHopList.getNextHops().size(), 1);
- const NextHop& nextHopForC = *(cHopList.getNextHops().begin());
+ const auto nextHopForC = cHopList.getNextHops().begin();
- BOOST_CHECK(nextHopForC.getConnectingFaceUri() == ROUTER_C_FACE &&
- nextHopForC.getRouteCostAsAdjustedInteger() == LINK_AC_COST);
+ BOOST_CHECK(nextHopForC->getConnectingFaceUri() == ROUTER_C_FACE &&
+ nextHopForC->getRouteCostAsAdjustedInteger() == LINK_AC_COST);
+}
+
+BOOST_AUTO_TEST_CASE(AsymmetricZeroCostLink)
+{
+ // Asymmetric and zero link cost between B - C, and B - A.
+ ndn::Name keyB = ndn::Name(ROUTER_B_NAME).append(std::to_string(Lsa::Type::ADJACENCY));
+ auto lsaB = nlsr.m_lsdb.findAdjLsa(keyB);
+ BOOST_REQUIRE(lsaB != nullptr);
+
+ auto c = lsaB->getAdl().findAdjacent(ROUTER_C_NAME);
+ BOOST_REQUIRE(c != conf.getAdjacencyList().end());
+ // Re-adjust link cost to 0 from B-C. However, this should not set B-C cost 0 because C-B
+ // cost is greater that 0 i.e. 17
+ c->setLinkCost(0);
+
+ auto a = lsaB->getAdl().findAdjacent(ROUTER_A_NAME);
+ BOOST_REQUIRE(a != conf.getAdjacencyList().end());
+
+ ndn::Name keyA = ndn::Name(ROUTER_A_NAME).append(std::to_string(Lsa::Type::ADJACENCY));
+ auto lsaA = nlsr.m_lsdb.findAdjLsa(keyA);
+ BOOST_REQUIRE(lsaA != nullptr);
+
+ auto b = lsaA->getAdl().findAdjacent(ROUTER_B_NAME);
+ BOOST_REQUIRE(b != conf.getAdjacencyList().end());
+
+ // Re-adjust link cost to 0 from both the direction i.e B-A and A-B
+ a->setLinkCost(0);
+ b->setLinkCost(0);
+
+ // Calculation should consider 0 link-cost between B and C
+ LinkStateRoutingTableCalculator calculator(map.getMapSize());
+ calculator.calculatePath(map, routingTable, conf, lsdb.getAdjLsdb());
+
+ // Router A should be able to get to B through B and C
+ RoutingTableEntry* entryB = routingTable.findRoutingTableEntry(ROUTER_B_NAME);
+ BOOST_REQUIRE(entryB != nullptr);
+
+ // Node can have neighbors with zero cost, so the nexthop count should be 2
+ NexthopList& bHopList = entryB->getNexthopList();
+ BOOST_REQUIRE_EQUAL(bHopList.getNextHops().size(), 2);
+
+ const auto nextHopForB = bHopList.getNextHops().begin();
+ // Check if the next hop via B is through A or not after the cost adjustment
+ BOOST_CHECK(nextHopForB->getConnectingFaceUri() == ROUTER_B_FACE &&
+ nextHopForB->getRouteCostAsAdjustedInteger() == 0);
+
+ // Router A should be able to get to C through C and B
+ auto entryC = routingTable.findRoutingTableEntry(ROUTER_C_NAME);
+ BOOST_REQUIRE(entryC != nullptr);
+
+ NexthopList& cHopList = entryC->getNexthopList();
+ BOOST_REQUIRE_EQUAL(cHopList.getNextHops().size(), 2);
+
+ const auto nextHopForC = cHopList.getNextHops().begin();
+ // Check if the nextHop from C is via A or not
+ BOOST_CHECK(nextHopForC->getConnectingFaceUri() == ROUTER_C_FACE &&
+ nextHopForC->getRouteCostAsAdjustedInteger() == LINK_AC_COST);
+
}
BOOST_AUTO_TEST_SUITE_END()