tests/test-link-state-calculator.cpp - NLSR - Gitiles

 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
  * Copyright (c) 2014-2017,  The University of Memphis,
  *                           Regents of the University of California,
  *                           Arizona Board of Regents.
  *
  * This file is part of NLSR (Named-data Link State Routing).
  * See AUTHORS.md for complete list of NLSR authors and contributors.
  *
  * NLSR is free software: you can redistribute it and/or modify it under the terms
  * of the GNU General Public License as published by the Free Software Foundation,
  * either version 3 of the License, or (at your option) any later version.
  *
  * NLSR is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
  * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  * PURPOSE.  See the GNU General Public License for more details.
  *
  * You should have received a copy of the GNU General Public License along with
  * NLSR, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
  **/

 #include "route/routing-table-calculator.hpp"

 #include "adjacency-list.hpp"
 #include "lsa.hpp"
 #include "lsdb.hpp"
 #include "nlsr.hpp"
 #include "test-common.hpp"
 #include "route/map.hpp"
 #include "route/routing-table.hpp"

 #include <ndn-cxx/util/dummy-client-face.hpp>

 namespace nlsr {
 namespace test {

 static const ndn::time::system_clock::TimePoint MAX_TIME =
   ndn::time::system_clock::TimePoint::max();

 class LinkStateCalculatorFixture : public BaseFixture
 {
 public:
   LinkStateCalculatorFixture()
     : face(m_ioService, m_keyChain)
     , nlsr(m_ioService, m_scheduler, face, m_keyChain)
     , routingTable(nlsr.getRoutingTable())
     , lsdb(nlsr.getLsdb())
   {
     setUpTopology();
   }

   // Triangle topology with routers A, B, C connected
   void setUpTopology()
   {
     INIT_LOGGERS("/tmp", "TRACE");

     ConfParameter& conf = nlsr.getConfParameter();
     conf.setNetwork("/ndn");
     conf.setSiteName("/router");
     conf.setRouterName("/a");
     conf.buildRouterPrefix();

     Adjacent a(ROUTER_A_NAME, ndn::FaceUri(ROUTER_A_FACE), 0, Adjacent::STATUS_ACTIVE, 0, 0);
     Adjacent b(ROUTER_B_NAME, ndn::FaceUri(ROUTER_B_FACE), 0, Adjacent::STATUS_ACTIVE, 0, 0);
     Adjacent c(ROUTER_C_NAME, ndn::FaceUri(ROUTER_C_FACE), 0, Adjacent::STATUS_ACTIVE, 0, 0);

     // Router A
     b.setLinkCost(LINK_AB_COST);
     c.setLinkCost(LINK_AC_COST);

     AdjacencyList& adjacencyListA = nlsr.getAdjacencyList();
     adjacencyListA.insert(b);
     adjacencyListA.insert(c);

     AdjLsa adjA(a.getName(), 1, MAX_TIME, 2, adjacencyListA);
     lsdb.installAdjLsa(adjA);

     // Router B
     a.setLinkCost(LINK_AB_COST);
     c.setLinkCost(LINK_BC_COST);

     AdjacencyList adjacencyListB;
     adjacencyListB.insert(a);
     adjacencyListB.insert(c);

     AdjLsa adjB(b.getName(), 1, MAX_TIME, 2, adjacencyListB);
     lsdb.installAdjLsa(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, 2, adjacencyListC);
     lsdb.installAdjLsa(adjC);

     map.createFromAdjLsdb(lsdb.getAdjLsdb().begin(), lsdb.getAdjLsdb().end());
   }

 public:
   ndn::util::DummyClientFace face;
   Nlsr nlsr;
   Map map;

   RoutingTable& routingTable;
   Lsdb& lsdb;

   static const ndn::Name ROUTER_A_NAME;
   static const ndn::Name ROUTER_B_NAME;
   static const ndn::Name ROUTER_C_NAME;

   static const std::string ROUTER_A_FACE;
   static const std::string ROUTER_B_FACE;
   static const std::string ROUTER_C_FACE;

   static const double LINK_AB_COST;
   static const double LINK_AC_COST;
   static const double LINK_BC_COST;
 };

 const ndn::Name LinkStateCalculatorFixture::ROUTER_A_NAME = "/ndn/router/a";
 const ndn::Name LinkStateCalculatorFixture::ROUTER_B_NAME = "/ndn/router/b";
 const ndn::Name LinkStateCalculatorFixture::ROUTER_C_NAME = "/ndn/router/c";

 const std::string LinkStateCalculatorFixture::ROUTER_A_FACE = "udp4://10.0.0.1";
 const std::string LinkStateCalculatorFixture::ROUTER_B_FACE = "udp4://10.0.0.2";
 const std::string LinkStateCalculatorFixture::ROUTER_C_FACE = "udp4://10.0.0.3";

 const double LinkStateCalculatorFixture::LINK_AB_COST = 5;
 const double LinkStateCalculatorFixture::LINK_AC_COST = 10;
 const double LinkStateCalculatorFixture::LINK_BC_COST = 17;

 BOOST_FIXTURE_TEST_SUITE(TestLinkStateRoutingCalculator, LinkStateCalculatorFixture)

 BOOST_AUTO_TEST_CASE(Basic)
 {
   LinkStateRoutingTableCalculator calculator(map.getMapSize());
   calculator.calculatePath(map, routingTable, nlsr);

   RoutingTableEntry* entryB = routingTable.findRoutingTableEntry(ROUTER_B_NAME);
   BOOST_REQUIRE(entryB != nullptr);

   // 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) {
     std::string 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);

   // 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) {
     std::string 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));
   }
 }

 BOOST_AUTO_TEST_CASE(Asymmetric)
 {
   // 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.getLsdb().findAdjLsa(key);
   BOOST_REQUIRE(lsa != nullptr);

   auto c = lsa->getAdl().findAdjacent(ROUTER_C_NAME);
   BOOST_REQUIRE(c != nlsr.getAdjacencyList().end());

   double higherLinkCost = LINK_BC_COST + 1;
   c->setLinkCost(higherLinkCost);

   // Calculation should consider the link between B and C as having cost = higherLinkCost
   LinkStateRoutingTableCalculator calculator(map.getMapSize());
   calculator.calculatePath(map, routingTable, nlsr);

   RoutingTableEntry* entryB = routingTable.findRoutingTableEntry(ROUTER_B_NAME);
   BOOST_REQUIRE(entryB != nullptr);

   // 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) {
     std::string 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);

   // 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) {
     std::string 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));
   }
 }

 BOOST_AUTO_TEST_CASE(AsymmetricZeroCost)
 {
   // 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.getLsdb().findAdjLsa(key);
   BOOST_REQUIRE(lsa != nullptr);

   auto c = lsa->getAdl().findAdjacent(ROUTER_C_NAME);
   BOOST_REQUIRE(c != nlsr.getAdjacencyList().end());

   c->setLinkCost(0);

   // Calculation should consider the link between B and C as down
   LinkStateRoutingTableCalculator calculator(map.getMapSize());
   calculator.calculatePath(map, routingTable, nlsr);

   // 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);

   NexthopList& bHopList = entryB->getNexthopList();
   BOOST_REQUIRE_EQUAL(bHopList.getNextHops().size(), 1);

   const NextHop& nextHopForB = *(bHopList.getNextHops().begin());

   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);
   BOOST_REQUIRE(entryC != nullptr);

   NexthopList& cHopList = entryC->getNexthopList();
   BOOST_REQUIRE_EQUAL(cHopList.getNextHops().size(), 1);

   const NextHop& nextHopForC = *(cHopList.getNextHops().begin());

   BOOST_CHECK(nextHopForC.getConnectingFaceUri() == ROUTER_C_FACE &&
               nextHopForC.getRouteCostAsAdjustedInteger() == LINK_AC_COST);
 }

 BOOST_AUTO_TEST_SUITE_END()

 } // namespace test
 } // namespace nlsr
	/* -- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -- */
	/**
	* Copyright (c) 2014-2017, The University of Memphis,
	* Regents of the University of California,
	* Arizona Board of Regents.
	*
	* This file is part of NLSR (Named-data Link State Routing).
	* See AUTHORS.md for complete list of NLSR authors and contributors.
	*
	* NLSR is free software: you can redistribute it and/or modify it under the terms
	* of the GNU General Public License as published by the Free Software Foundation,
	* either version 3 of the License, or (at your option) any later version.
	*
	* NLSR is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
	* without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
	* PURPOSE. See the GNU General Public License for more details.
	*
	* You should have received a copy of the GNU General Public License along with
	* NLSR, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
	**/

	#include "route/routing-table-calculator.hpp"

	#include "adjacency-list.hpp"
	#include "lsa.hpp"
	#include "lsdb.hpp"
	#include "nlsr.hpp"
	#include "test-common.hpp"
	#include "route/map.hpp"
	#include "route/routing-table.hpp"

	#include <ndn-cxx/util/dummy-client-face.hpp>

	namespace nlsr {
	namespace test {

	static const ndn::time::system_clock::TimePoint MAX_TIME =
	ndn::time::system_clock::TimePoint::max();

	class LinkStateCalculatorFixture : public BaseFixture
	{
	public:
	LinkStateCalculatorFixture()
	: face(m_ioService, m_keyChain)
	, nlsr(m_ioService, m_scheduler, face, m_keyChain)
	, routingTable(nlsr.getRoutingTable())
	, lsdb(nlsr.getLsdb())
	{
	setUpTopology();
	}

	// Triangle topology with routers A, B, C connected
	void setUpTopology()
	{
	INIT_LOGGERS("/tmp", "TRACE");

	ConfParameter& conf = nlsr.getConfParameter();
	conf.setNetwork("/ndn");
	conf.setSiteName("/router");
	conf.setRouterName("/a");
	conf.buildRouterPrefix();

	Adjacent a(ROUTER_A_NAME, ndn::FaceUri(ROUTER_A_FACE), 0, Adjacent::STATUS_ACTIVE, 0, 0);
	Adjacent b(ROUTER_B_NAME, ndn::FaceUri(ROUTER_B_FACE), 0, Adjacent::STATUS_ACTIVE, 0, 0);
	Adjacent c(ROUTER_C_NAME, ndn::FaceUri(ROUTER_C_FACE), 0, Adjacent::STATUS_ACTIVE, 0, 0);

	// Router A
	b.setLinkCost(LINK_AB_COST);
	c.setLinkCost(LINK_AC_COST);

	AdjacencyList& adjacencyListA = nlsr.getAdjacencyList();
	adjacencyListA.insert(b);
	adjacencyListA.insert(c);

	AdjLsa adjA(a.getName(), 1, MAX_TIME, 2, adjacencyListA);
	lsdb.installAdjLsa(adjA);

	// Router B
	a.setLinkCost(LINK_AB_COST);
	c.setLinkCost(LINK_BC_COST);

	AdjacencyList adjacencyListB;
	adjacencyListB.insert(a);
	adjacencyListB.insert(c);

	AdjLsa adjB(b.getName(), 1, MAX_TIME, 2, adjacencyListB);
	lsdb.installAdjLsa(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, 2, adjacencyListC);
	lsdb.installAdjLsa(adjC);

	map.createFromAdjLsdb(lsdb.getAdjLsdb().begin(), lsdb.getAdjLsdb().end());
	}

	public:
	ndn::util::DummyClientFace face;
	Nlsr nlsr;
	Map map;

	RoutingTable& routingTable;
	Lsdb& lsdb;

	static const ndn::Name ROUTER_A_NAME;
	static const ndn::Name ROUTER_B_NAME;
	static const ndn::Name ROUTER_C_NAME;

	static const std::string ROUTER_A_FACE;
	static const std::string ROUTER_B_FACE;
	static const std::string ROUTER_C_FACE;

	static const double LINK_AB_COST;
	static const double LINK_AC_COST;
	static const double LINK_BC_COST;
	};

	const ndn::Name LinkStateCalculatorFixture::ROUTER_A_NAME = "/ndn/router/a";
	const ndn::Name LinkStateCalculatorFixture::ROUTER_B_NAME = "/ndn/router/b";
	const ndn::Name LinkStateCalculatorFixture::ROUTER_C_NAME = "/ndn/router/c";

	const std::string LinkStateCalculatorFixture::ROUTER_A_FACE = "udp4://10.0.0.1";
	const std::string LinkStateCalculatorFixture::ROUTER_B_FACE = "udp4://10.0.0.2";
	const std::string LinkStateCalculatorFixture::ROUTER_C_FACE = "udp4://10.0.0.3";

	const double LinkStateCalculatorFixture::LINK_AB_COST = 5;
	const double LinkStateCalculatorFixture::LINK_AC_COST = 10;
	const double LinkStateCalculatorFixture::LINK_BC_COST = 17;

	BOOST_FIXTURE_TEST_SUITE(TestLinkStateRoutingCalculator, LinkStateCalculatorFixture)

	BOOST_AUTO_TEST_CASE(Basic)
	{
	LinkStateRoutingTableCalculator calculator(map.getMapSize());
	calculator.calculatePath(map, routingTable, nlsr);

	RoutingTableEntry* entryB = routingTable.findRoutingTableEntry(ROUTER_B_NAME);
	BOOST_REQUIRE(entryB != nullptr);

	// 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) {
	std::string 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);

	// 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) {
	std::string 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));
	}
	}

	BOOST_AUTO_TEST_CASE(Asymmetric)
	{
	// 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.getLsdb().findAdjLsa(key);
	BOOST_REQUIRE(lsa != nullptr);

	auto c = lsa->getAdl().findAdjacent(ROUTER_C_NAME);
	BOOST_REQUIRE(c != nlsr.getAdjacencyList().end());

	double higherLinkCost = LINK_BC_COST + 1;
	c->setLinkCost(higherLinkCost);

	// Calculation should consider the link between B and C as having cost = higherLinkCost
	LinkStateRoutingTableCalculator calculator(map.getMapSize());
	calculator.calculatePath(map, routingTable, nlsr);

	RoutingTableEntry* entryB = routingTable.findRoutingTableEntry(ROUTER_B_NAME);
	BOOST_REQUIRE(entryB != nullptr);

	// 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) {
	std::string 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);

	// 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) {
	std::string 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));
	}
	}

	BOOST_AUTO_TEST_CASE(AsymmetricZeroCost)
	{
	// 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.getLsdb().findAdjLsa(key);
	BOOST_REQUIRE(lsa != nullptr);

	auto c = lsa->getAdl().findAdjacent(ROUTER_C_NAME);
	BOOST_REQUIRE(c != nlsr.getAdjacencyList().end());

	c->setLinkCost(0);

	// Calculation should consider the link between B and C as down
	LinkStateRoutingTableCalculator calculator(map.getMapSize());
	calculator.calculatePath(map, routingTable, nlsr);

	// 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);

	NexthopList& bHopList = entryB->getNexthopList();
	BOOST_REQUIRE_EQUAL(bHopList.getNextHops().size(), 1);

	const NextHop& nextHopForB = *(bHopList.getNextHops().begin());

	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);
	BOOST_REQUIRE(entryC != nullptr);

	NexthopList& cHopList = entryC->getNexthopList();
	BOOST_REQUIRE_EQUAL(cHopList.getNextHops().size(), 1);

	const NextHop& nextHopForC = *(cHopList.getNextHops().begin());

	BOOST_CHECK(nextHopForC.getConnectingFaceUri() == ROUTER_C_FACE &&
	nextHopForC.getRouteCostAsAdjustedInteger() == LINK_AC_COST);
	}

	BOOST_AUTO_TEST_SUITE_END()

	} // namespace test
	} // namespace nlsr