route: fix nonexistent router condition in link-state calculator
Previously, if a non-existent source router is passed to the link-state
routing calculator, LinkStateRoutingTableCalculator::calculatePath could
dereference an empty optional. This commit corrects this condition.
Cleanup the test suite.
Add a test case for MaxFacesPerPrefix=1, which has a different code path
in the link-state calculator.
refs #5308
Change-Id: Ieab5a0388d9290095b1eb7924f4d3c693b67d098
diff --git a/src/route/routing-calculator-link-state.cpp b/src/route/routing-calculator-link-state.cpp
index 7d113ee..84ee0bc 100644
--- a/src/route/routing-calculator-link-state.cpp
+++ b/src/route/routing-calculator-link-state.cpp
@@ -401,8 +401,11 @@
auto sourceRouter = pMap.getMappingNoByRouterName(confParam.getRouterPrefix());
allocateParent(); // These two matrices are used in Dijkstra's algorithm.
allocateDistance(); //
- // We only bother to do the calculation if we have a router by that name.
- if (sourceRouter && confParam.getMaxFacesPerPrefix() == 1) {
+
+ if (!sourceRouter) {
+ // We cannot do the calculation if we don't have a router by that name.
+ }
+ else if (confParam.getMaxFacesPerPrefix() == 1) {
// In the single path case we can simply run Dijkstra's algorithm.
doDijkstraPathCalculation(*sourceRouter);
// Inform the routing table of the new next hops.
diff --git a/tests/route/test-routing-calculator-link-state.cpp b/tests/route/test-routing-calculator-link-state.cpp
index dce29c5..5f38703 100644
--- a/tests/route/test-routing-calculator-link-state.cpp
+++ b/tests/route/test-routing-calculator-link-state.cpp
@@ -37,13 +37,26 @@
static const ndn::Name ROUTER_A_NAME = "/ndn/site/%C1.Router/this-router";
static const ndn::Name ROUTER_B_NAME = "/ndn/site/%C1.Router/b";
static const ndn::Name ROUTER_C_NAME = "/ndn/site/%C1.Router/c";
-static const ndn::FaceUri ROUTER_A_FACE("udp4://10.0.0.1");
-static const ndn::FaceUri ROUTER_B_FACE("udp4://10.0.0.2");
-static const ndn::FaceUri ROUTER_C_FACE("udp4://10.0.0.3");
-constexpr double LINK_AB_COST = 5;
-constexpr double LINK_AC_COST = 10;
-constexpr double LINK_BC_COST = 17;
+static const ndn::FaceUri ROUTER_A_FACE("udp4://10.0.0.1:6363");
+static const ndn::FaceUri ROUTER_B_FACE("udp4://10.0.0.2:6363");
+static const ndn::FaceUri ROUTER_C_FACE("udp4://10.0.0.3:6363");
+constexpr double LINK_AB_COST = 5.0;
+constexpr double LINK_AC_COST = 10.0;
+constexpr double LINK_BC_COST = 17.0;
+/**
+ * @brief Provide a topology for link-state routing calculator testing.
+ *
+ * The topology consists of three routers: A, B, C.
+ * After calling all three setupRouter functions, they will form a triangle topology:
+ *
+ * A-----B
+ * \ /
+ * \ /
+ * C
+ *
+ * The local router, as reported by `conf.getRouterPrefix()`, is router A.
+ */
class LinkStateCalculatorFixture : public IoKeyChainFixture
{
public:
@@ -55,51 +68,93 @@
, routingTable(nlsr.m_routingTable)
, lsdb(nlsr.m_lsdb)
{
- setUpTopology();
}
- // Triangle topology with routers A, B, C connected
- void setUpTopology()
+ /**
+ * @brief Insert Adjacency LSA of router A into LSDB.
+ */
+ void
+ setupRouterA(double costAB = LINK_AB_COST, double costAC = LINK_AC_COST)
{
- Adjacent a(ROUTER_A_NAME, ROUTER_A_FACE, 0, Adjacent::STATUS_ACTIVE, 0, 0);
- Adjacent b(ROUTER_B_NAME, ROUTER_B_FACE, 0, Adjacent::STATUS_ACTIVE, 0, 0);
- Adjacent c(ROUTER_C_NAME, ROUTER_C_FACE, 0, Adjacent::STATUS_ACTIVE, 0, 0);
+ AdjacencyList& adjList = conf.getAdjacencyList();
+ if (!std::isnan(costAB)) {
+ adjList.insert(Adjacent(ROUTER_B_NAME, ROUTER_B_FACE, costAB, Adjacent::STATUS_ACTIVE, 0, 0));
+ }
+ if (!std::isnan(costAC)) {
+ adjList.insert(Adjacent(ROUTER_C_NAME, ROUTER_C_FACE, costAC, Adjacent::STATUS_ACTIVE, 0, 0));
+ }
- // Router A
- b.setLinkCost(LINK_AB_COST);
- c.setLinkCost(LINK_AC_COST);
+ lsdb.installLsa(std::make_shared<AdjLsa>(ROUTER_A_NAME, 1, MAX_TIME, adjList));
+ }
- AdjacencyList& adjacencyListA = conf.getAdjacencyList();
- adjacencyListA.insert(b);
- adjacencyListA.insert(c);
+ /**
+ * @brief Insert Adjacency LSA of router B into LSDB.
+ */
+ void
+ setupRouterB(double costBC = LINK_BC_COST, double costBA = LINK_AB_COST)
+ {
+ AdjacencyList adjList;
+ if (!std::isnan(costBC)) {
+ adjList.insert(Adjacent(ROUTER_C_NAME, ROUTER_C_FACE, costBC, Adjacent::STATUS_ACTIVE, 0, 0));
+ }
+ if (!std::isnan(costBA)) {
+ adjList.insert(Adjacent(ROUTER_A_NAME, ROUTER_A_FACE, costBA, Adjacent::STATUS_ACTIVE, 0, 0));
+ }
- AdjLsa adjA(a.getName(), 1, MAX_TIME, adjacencyListA);
- lsdb.installLsa(std::make_shared<AdjLsa>(adjA));
+ lsdb.installLsa(std::make_shared<AdjLsa>(ROUTER_B_NAME, 1, MAX_TIME, adjList));
+ }
- // Router B
- a.setLinkCost(LINK_AB_COST);
- c.setLinkCost(LINK_BC_COST);
+ /**
+ * @brief Insert Adjacency LSA of router C into LSDB.
+ */
+ void
+ setupRouterC(double costCA = LINK_AC_COST, double costCB = LINK_BC_COST)
+ {
+ AdjacencyList adjList;
+ if (!std::isnan(costCA)) {
+ adjList.insert(Adjacent(ROUTER_A_NAME, ROUTER_A_FACE, costCA, Adjacent::STATUS_ACTIVE, 0, 0));
+ }
+ if (!std::isnan(costCB)) {
+ adjList.insert(Adjacent(ROUTER_B_NAME, ROUTER_B_FACE, costCB, Adjacent::STATUS_ACTIVE, 0, 0));
+ }
- AdjacencyList adjacencyListB;
- adjacencyListB.insert(a);
- adjacencyListB.insert(c);
+ lsdb.installLsa(std::make_shared<AdjLsa>(ROUTER_C_NAME, 1, MAX_TIME, adjList));
+ }
- AdjLsa adjB(b.getName(), 1, MAX_TIME, adjacencyListB);
- lsdb.installLsa(std::make_shared<AdjLsa>(adjB));
-
- // Router C
- a.setLinkCost(LINK_AC_COST);
- b.setLinkCost(LINK_BC_COST);
-
- AdjacencyList adjacencyListC;
- adjacencyListC.insert(a);
- adjacencyListC.insert(b);
-
- AdjLsa adjC(c.getName(), 1, MAX_TIME, adjacencyListC);
- lsdb.installLsa(std::make_shared<AdjLsa>(adjC));
-
+ /**
+ * @brief Run link-state routing calculator.
+ */
+ void
+ calculatePath()
+ {
auto lsaRange = lsdb.getLsdbIterator<AdjLsa>();
- map = NameMap::createFromAdjLsdb(lsaRange.first, lsaRange.second);
+ NameMap map = NameMap::createFromAdjLsdb(lsaRange.first, lsaRange.second);
+ calculateLinkStateRoutingPath(map, routingTable, conf, lsdb);
+ }
+
+ /**
+ * @brief Verify that the routing table contains an entry with specific next hops.
+ * @param destination Destination router.
+ * @param expectedNextHops Expected next hops; order does not matter.
+ */
+ void
+ checkRoutingTableEntry(const ndn::Name& destination,
+ std::initializer_list<NextHop> expectedNextHops) const
+ {
+ BOOST_TEST_CONTEXT("Checking routing table entry " << destination)
+ {
+ using NextHopSet = std::set<NextHop, NextHopUriSortedComparator>;
+
+ NextHopSet expectedNextHopSet(expectedNextHops);
+
+ const RoutingTableEntry* entry = routingTable.findRoutingTableEntry(destination);
+ BOOST_REQUIRE(entry != nullptr);
+
+ const NexthopList& actualNextHopList = entry->getNexthopList();
+ NextHopSet actualNextHopSet(actualNextHopList.begin(), actualNextHopList.end());
+
+ BOOST_TEST(expectedNextHopSet == actualNextHopSet, boost::test_tools::per_element());
+ }
}
public:
@@ -107,7 +162,6 @@
ConfParameter conf;
DummyConfFileProcessor confProcessor;
Nlsr nlsr;
- NameMap map;
RoutingTable& routingTable;
Lsdb& lsdb;
@@ -117,180 +171,144 @@
BOOST_AUTO_TEST_CASE(Basic)
{
- calculateLinkStateRoutingPath(map, routingTable, conf, lsdb);
-
- RoutingTableEntry* entryB = routingTable.findRoutingTableEntry(ROUTER_B_NAME);
- BOOST_REQUIRE(entryB != nullptr);
+ setupRouterA();
+ setupRouterB();
+ setupRouterC();
+ calculatePath();
// Router A should be able to get to B through B and to B through C
- NexthopList& bHopList = entryB->getNexthopList();
- BOOST_REQUIRE_EQUAL(bHopList.getNextHops().size(), 2);
-
- for (const NextHop& hop : bHopList) {
- auto faceUri = hop.getConnectingFaceUri();
- uint64_t cost = hop.getRouteCostAsAdjustedInteger();
-
- BOOST_CHECK((faceUri == ROUTER_B_FACE && cost == LINK_AB_COST) ||
- (faceUri == ROUTER_C_FACE && cost == LINK_AC_COST + LINK_BC_COST));
-
- }
-
- RoutingTableEntry* entryC = routingTable.findRoutingTableEntry(ROUTER_C_NAME);
- BOOST_REQUIRE(entryC != nullptr);
+ checkRoutingTableEntry(ROUTER_B_NAME, {
+ {ROUTER_B_FACE, LINK_AB_COST},
+ {ROUTER_C_FACE, LINK_AC_COST + LINK_BC_COST},
+ });
// Router A should be able to get to C through C and to C through B
- NexthopList& cHopList = entryC->getNexthopList();
- BOOST_REQUIRE_EQUAL(cHopList.getNextHops().size(), 2);
-
- for (const NextHop& hop : cHopList) {
- auto faceUri = hop.getConnectingFaceUri();
- uint64_t cost = hop.getRouteCostAsAdjustedInteger();
-
- BOOST_CHECK((faceUri == ROUTER_C_FACE && cost == LINK_AC_COST) ||
- (faceUri == ROUTER_B_FACE && cost == LINK_AB_COST + LINK_BC_COST));
- }
+ checkRoutingTableEntry(ROUTER_C_NAME, {
+ {ROUTER_C_FACE, LINK_AC_COST},
+ {ROUTER_B_FACE, LINK_AB_COST + LINK_BC_COST},
+ });
}
BOOST_AUTO_TEST_CASE(Asymmetric)
{
// Asymmetric link cost between B and C
- auto lsa = nlsr.m_lsdb.findLsa<AdjLsa>(ndn::Name(ROUTER_B_NAME));
- BOOST_REQUIRE(lsa != nullptr);
+ double higherCostBC = LINK_BC_COST + 1;
+ setupRouterA();
+ setupRouterB(higherCostBC);
+ setupRouterC();
- auto c = lsa->m_adl.findAdjacent(ROUTER_C_NAME);
- BOOST_REQUIRE(c != conf.getAdjacencyList().end());
-
- double higherLinkCost = LINK_BC_COST + 1;
- c->setLinkCost(higherLinkCost);
-
- // Calculation should consider the link between B and C as having cost = higherLinkCost
- calculateLinkStateRoutingPath(map, routingTable, conf, lsdb);
-
- RoutingTableEntry* entryB = routingTable.findRoutingTableEntry(ROUTER_B_NAME);
- BOOST_REQUIRE(entryB != nullptr);
+ // Calculation should consider the link between B and C as having cost = higherCostBC
+ calculatePath();
// Router A should be able to get to B through B and to B through C
- NexthopList& bHopList = entryB->getNexthopList();
- BOOST_REQUIRE_EQUAL(bHopList.getNextHops().size(), 2);
-
- for (const NextHop& hop : bHopList) {
- auto faceUri = hop.getConnectingFaceUri();
- uint64_t cost = hop.getRouteCostAsAdjustedInteger();
-
- BOOST_CHECK((faceUri == ROUTER_B_FACE && cost == LINK_AB_COST) ||
- (faceUri == ROUTER_C_FACE && cost == LINK_AC_COST + higherLinkCost));
-
- }
-
- RoutingTableEntry* entryC = routingTable.findRoutingTableEntry(ROUTER_C_NAME);
- BOOST_REQUIRE(entryC != nullptr);
+ checkRoutingTableEntry(ROUTER_B_NAME, {
+ {ROUTER_B_FACE, LINK_AB_COST},
+ {ROUTER_C_FACE, LINK_AC_COST + higherCostBC},
+ });
// Router A should be able to get to C through C and to C through B
- NexthopList& cHopList = entryC->getNexthopList();
- BOOST_REQUIRE_EQUAL(cHopList.getNextHops().size(), 2);
-
- for (const NextHop& hop : cHopList) {
- auto faceUri = hop.getConnectingFaceUri();
- uint64_t cost = hop.getRouteCostAsAdjustedInteger();
-
- BOOST_CHECK((faceUri == ROUTER_C_FACE && cost == LINK_AC_COST) ||
- (faceUri == ROUTER_B_FACE && cost == LINK_AB_COST + higherLinkCost));
- }
+ checkRoutingTableEntry(ROUTER_C_NAME, {
+ {ROUTER_C_FACE, LINK_AC_COST},
+ {ROUTER_B_FACE, LINK_AB_COST + higherCostBC},
+ });
}
BOOST_AUTO_TEST_CASE(NonAdjacentCost)
{
- // Asymmetric link cost between B and C
- auto lsa = nlsr.m_lsdb.findLsa<AdjLsa>(ROUTER_B_NAME);
- BOOST_REQUIRE(lsa != nullptr);
-
- auto c = lsa->m_adl.findAdjacent(ROUTER_C_NAME);
- BOOST_REQUIRE(c != conf.getAdjacencyList().end());
-
- // Break the link between B - C by setting it to a NON_ADJACENT_COST.
- c->setLinkCost(Adjacent::NON_ADJACENT_COST);
+ // Break the link between B - C by setting it to NON_ADJACENT_COST.
+ setupRouterA();
+ setupRouterB(
+ Adjacent::NON_ADJACENT_COST // B to C
+ );
+ setupRouterC();
// Calculation should consider the link between B and C as down
- calculateLinkStateRoutingPath(map, routingTable, conf, lsdb);
+ calculatePath();
// Router A should be able to get to B through B but not through C
- RoutingTableEntry* entryB = routingTable.findRoutingTableEntry(ROUTER_B_NAME);
- BOOST_REQUIRE(entryB != nullptr);
-
- auto bHopList = entryB->getNexthopList();
- BOOST_REQUIRE_EQUAL(bHopList.getNextHops().size(), 1);
-
- const auto nextHopForB = bHopList.getNextHops().begin();
-
- BOOST_CHECK(nextHopForB->getConnectingFaceUri() == ROUTER_B_FACE &&
- nextHopForB->getRouteCostAsAdjustedInteger() == LINK_AB_COST);
+ checkRoutingTableEntry(ROUTER_B_NAME, {
+ {ROUTER_B_FACE, LINK_AB_COST},
+ });
// Router A should be able to get to C through C but not through B
- auto entryC = routingTable.findRoutingTableEntry(ROUTER_C_NAME);
- BOOST_REQUIRE(entryC != nullptr);
-
- NexthopList& cHopList = entryC->getNexthopList();
- BOOST_REQUIRE_EQUAL(cHopList.getNextHops().size(), 1);
-
- const auto nextHopForC = cHopList.getNextHops().begin();
-
- BOOST_CHECK(nextHopForC->getConnectingFaceUri() == ROUTER_C_FACE &&
- nextHopForC->getRouteCostAsAdjustedInteger() == LINK_AC_COST);
+ checkRoutingTableEntry(ROUTER_C_NAME, {
+ {ROUTER_C_FACE, LINK_AC_COST},
+ });
}
BOOST_AUTO_TEST_CASE(AsymmetricZeroCostLink)
{
// Asymmetric and zero link cost between B - C, and B - A.
- auto lsaB = nlsr.m_lsdb.findLsa<AdjLsa>(ROUTER_B_NAME);
- BOOST_REQUIRE(lsaB != nullptr);
+ setupRouterA(
+ 0 // A to B
+ );
+ setupRouterB(
+ 0, // B to C: effective cost is still LINK_BC_COST, as specified on C-B link
+ 0 // B to A
+ );
+ setupRouterC();
- auto c = lsaB->m_adl.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->m_adl.findAdjacent(ROUTER_A_NAME);
- BOOST_REQUIRE(a != conf.getAdjacencyList().end());
-
- auto lsaA = nlsr.m_lsdb.findLsa<AdjLsa>(ROUTER_A_NAME);
- BOOST_REQUIRE(lsaA != nullptr);
-
- auto b = lsaA->m_adl.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
- calculateLinkStateRoutingPath(map, routingTable, conf, lsdb);
+ // Calculation should consider 0 link-cost between A and B
+ calculatePath();
// 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);
+ checkRoutingTableEntry(ROUTER_B_NAME, {
+ {ROUTER_B_FACE, 0},
+ {ROUTER_C_FACE, LINK_AC_COST + LINK_BC_COST},
+ });
// Router A should be able to get to C through C and B
- auto entryC = routingTable.findRoutingTableEntry(ROUTER_C_NAME);
- BOOST_REQUIRE(entryC != nullptr);
+ checkRoutingTableEntry(ROUTER_C_NAME, {
+ {ROUTER_C_FACE, LINK_AC_COST},
+ {ROUTER_B_FACE, 0 + LINK_BC_COST},
+ });
+}
- NexthopList& cHopList = entryC->getNexthopList();
- BOOST_REQUIRE_EQUAL(cHopList.getNextHops().size(), 2);
+BOOST_AUTO_TEST_CASE(OnePath)
+{
+ double costBC = 2.0;
+ setupRouterA();
+ setupRouterB(
+ costBC // B to C
+ );
+ setupRouterC(
+ LINK_AC_COST, // C to A
+ costBC // C to B
+ );
- 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);
+ // Calculate only one path per destination router.
+ conf.setMaxFacesPerPrefix(1);
+ // This triggers a different code path.
+ calculatePath();
+ // Shortest path to router B is via router B.
+ checkRoutingTableEntry(ROUTER_B_NAME, {
+ {ROUTER_B_FACE, LINK_AB_COST},
+ });
+
+ // Shortest path to router C is via router B.
+ checkRoutingTableEntry(ROUTER_C_NAME, {
+ {ROUTER_B_FACE, LINK_AB_COST + costBC},
+ });
+}
+
+BOOST_AUTO_TEST_CASE(SourceRouterAbsent)
+{
+ // RouterA does not exist in the LSDB.
+ // setupRouterA is not invoked.
+ setupRouterB(
+ LINK_BC_COST, // B to C
+ NAN // B to A: skipped
+ );
+ setupRouterC(
+ NAN // C to A: skipped
+ );
+
+ // Calculation should do nothing and not cause errors.
+ calculatePath();
+
+ // There should be no routes.
+ BOOST_CHECK(routingTable.m_rTable.empty());
}
BOOST_AUTO_TEST_SUITE_END()