tests/daemon/fw/asf-strategy.t.cpp - NFD - Gitiles

 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /*
  * Copyright (c) 2014-2020,  Regents of the University of California,
  *                           Arizona Board of Regents,
  *                           Colorado State University,
  *                           University Pierre & Marie Curie, Sorbonne University,
  *                           Washington University in St. Louis,
  *                           Beijing Institute of Technology,
  *                           The University of Memphis.
  *
  * This file is part of NFD (Named Data Networking Forwarding Daemon).
  * See AUTHORS.md for complete list of NFD authors and contributors.
  *
  * NFD 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.
  *
  * NFD 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
  * NFD, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
  */

 #include "fw/asf-strategy.hpp"

 #include "strategy-tester.hpp"
 #include "topology-tester.hpp"

 namespace nfd {
 namespace fw {
 namespace asf {
 namespace tests {

 using namespace nfd::fw::tests;

 // The tester is unused in this file, but it's used in various templated test suites.
 using AsfStrategyTester = StrategyTester<AsfStrategy>;
 NFD_REGISTER_STRATEGY(AsfStrategyTester);

 BOOST_AUTO_TEST_SUITE(Fw)
 BOOST_FIXTURE_TEST_SUITE(TestAsfStrategy, GlobalIoTimeFixture)

 class AsfGridFixture : public GlobalIoTimeFixture
 {
 protected:
   explicit
   AsfGridFixture(const Name& params = AsfStrategy::getStrategyName(), time::nanoseconds replyDelay = 0_ms)
     : parameters(params)
   {
     /*
      *                  +---------+
      *           +----->|  nodeB  |<------+
      *           |      +---------+       |
      *      10ms |                        | 10ms
      *           v                        v
      *      +---------+              +---------+
      *      |  nodeA  |              |  nodeC  |
      *      +---------+              +---------+
      *           ^                        ^
      *     100ms |                        | 100ms
      *           |      +---------+       |
      *           +----->|  nodeD  |<------+
      *                  +---------+
      */

     nodeA = topo.addForwarder("A");
     nodeB = topo.addForwarder("B");
     nodeC = topo.addForwarder("C");
     nodeD = topo.addForwarder("D");

     topo.setStrategy<AsfStrategy>(nodeA, Name("ndn:/"), parameters);
     topo.setStrategy<AsfStrategy>(nodeB, Name("ndn:/"), parameters);
     topo.setStrategy<AsfStrategy>(nodeC, Name("ndn:/"), parameters);
     topo.setStrategy<AsfStrategy>(nodeD, Name("ndn:/"), parameters);

     linkAB = topo.addLink("AB", 10_ms, {nodeA, nodeB});
     linkAD = topo.addLink("AD", 100_ms, {nodeA, nodeD});
     linkBC = topo.addLink("BC", 10_ms, {nodeB, nodeC});
     linkCD = topo.addLink("CD", 100_ms, {nodeC, nodeD});

     consumer = topo.addAppFace("c", nodeA);
     producer = topo.addAppFace("p", nodeC, PRODUCER_PREFIX);

     topo.addEchoProducer(producer->getClientFace(), PRODUCER_PREFIX, replyDelay);

     // Register producer prefix on consumer node
     topo.registerPrefix(nodeA, linkAB->getFace(nodeA), PRODUCER_PREFIX, 10);
     topo.registerPrefix(nodeA, linkAD->getFace(nodeA), PRODUCER_PREFIX, 5);
   }

   void
   runConsumer(int numInterests = 30)
   {
     topo.addIntervalConsumer(consumer->getClientFace(), PRODUCER_PREFIX, 1_s, numInterests);
     this->advanceClocks(10_ms, time::seconds(numInterests));
   }

 protected:
   Name parameters;
   TopologyTester topo;

   TopologyNode nodeA;
   TopologyNode nodeB;
   TopologyNode nodeC;
   TopologyNode nodeD;

   shared_ptr<TopologyLink> linkAB;
   shared_ptr<TopologyLink> linkAD;
   shared_ptr<TopologyLink> linkBC;
   shared_ptr<TopologyLink> linkCD;

   shared_ptr<TopologyAppLink> consumer;
   shared_ptr<TopologyAppLink> producer;

   static const Name PRODUCER_PREFIX;
 };

 class AsfStrategyParametersGridFixture : public AsfGridFixture
 {
 protected:
   AsfStrategyParametersGridFixture()
     : AsfGridFixture(Name(AsfStrategy::getStrategyName())
                      .append("probing-interval~30000")
                      .append("n-silent-timeouts~5"))
   {
   }
 };

 const Name AsfGridFixture::PRODUCER_PREFIX = Name("ndn:/hr/C");

 BOOST_FIXTURE_TEST_CASE(Basic, AsfGridFixture)
 {
   // Both nodeB and nodeD have FIB entries to reach the producer
   topo.registerPrefix(nodeB, linkBC->getFace(nodeB), PRODUCER_PREFIX);
   topo.registerPrefix(nodeD, linkCD->getFace(nodeD), PRODUCER_PREFIX);

   runConsumer();

   // ASF should use the Face to nodeD because it has lower routing cost.
   // After 5 seconds, a probe Interest should be sent to the Face to nodeB,
   // and the probe should return Data quicker. ASF should then use the Face
   // to nodeB to forward the remaining Interests.
   BOOST_CHECK_EQUAL(consumer->getForwarderFace().getCounters().nOutData, 30);
   // Because of exploration, will forward to AB and AD simultaneously at least once
   BOOST_CHECK_GE(linkAB->getFace(nodeA).getCounters().nOutInterests, 25);
   BOOST_CHECK_LE(linkAD->getFace(nodeA).getCounters().nOutInterests, 6);

   // If the link from nodeA to nodeB fails, ASF should start using the Face
   // to nodeD again.
   linkAB->fail();

   runConsumer();
   // We experience 3 silent timeouts before marking AB as timed out on the fourth interest.
   BOOST_CHECK_EQUAL(consumer->getForwarderFace().getCounters().nOutData, 56);
   BOOST_CHECK_LE(linkAB->getFace(nodeA).getCounters().nOutInterests, 36);
   BOOST_CHECK_GE(linkAD->getFace(nodeA).getCounters().nOutInterests, 24);

   // If the link from nodeA to nodeB recovers, ASF should probe the Face
   // to nodeB and start using it again.
   linkAB->recover();

   // Advance time to ensure probing is due
   this->advanceClocks(10_ms, 10_s);

   runConsumer();
   BOOST_CHECK_EQUAL(consumer->getForwarderFace().getCounters().nOutData, 86);
   BOOST_CHECK_GE(linkAB->getFace(nodeA).getCounters().nOutInterests, 50);
   BOOST_CHECK_LE(linkAD->getFace(nodeA).getCounters().nOutInterests, 40);

   // If both links fail, nodeA should forward to the next hop with the lowest cost
   linkAB->fail();
   linkAD->fail();

   runConsumer();

   BOOST_CHECK_EQUAL(consumer->getForwarderFace().getCounters().nOutData, 86);
   BOOST_CHECK_LE(linkAB->getFace(nodeA).getCounters().nOutInterests, 65); // FIXME #3830
   BOOST_CHECK_GE(linkAD->getFace(nodeA).getCounters().nOutInterests, 57); // FIXME #3830
 }

 BOOST_FIXTURE_TEST_CASE(Nack, AsfGridFixture)
 {
   // nodeB has a FIB entry to reach the producer, but nodeD does not
   topo.registerPrefix(nodeB, linkBC->getFace(nodeB), PRODUCER_PREFIX);

   // The strategy should first try to send to nodeD. But since nodeD does not have a route for
   // the producer's prefix, it should return a NO_ROUTE Nack. The strategy should then start using the Face to
   // nodeB.
   runConsumer();

   BOOST_CHECK_GE(linkAD->getFace(nodeA).getCounters().nInNacks, 1);
   BOOST_CHECK_EQUAL(consumer->getForwarderFace().getCounters().nOutData, 29);
   BOOST_CHECK_EQUAL(linkAB->getFace(nodeA).getCounters().nOutInterests, 29);

   // nodeD should receive 2 Interests: one for the very first Interest and
   // another from a probe
   BOOST_CHECK_GE(linkAD->getFace(nodeA).getCounters().nOutInterests, 2);
 }

 class AsfStrategyDelayedDataFixture : public AsfGridFixture
 {
 protected:
   AsfStrategyDelayedDataFixture()
     : AsfGridFixture(Name(AsfStrategy::getStrategyName()), 400_ms)
   {
   }
 };

 BOOST_FIXTURE_TEST_CASE(InterestForwarding, AsfStrategyDelayedDataFixture)
 {

   Name name(PRODUCER_PREFIX);
   name.appendTimestamp();
   shared_ptr<Interest> interest = makeInterest(name, true);

   topo.registerPrefix(nodeB, linkBC->getFace(nodeB), PRODUCER_PREFIX);
   topo.registerPrefix(nodeD, linkCD->getFace(nodeD), PRODUCER_PREFIX);

   // The first interest should go via link AD
   consumer->getClientFace().expressInterest(*interest, nullptr, nullptr, nullptr);
   this->advanceClocks(10_ms, 100_ms);
   BOOST_CHECK_EQUAL(linkAD->getFace(nodeA).getCounters().nOutInterests, 1);

   // Second interest should go via link AB
   interest->refreshNonce();
   consumer->getClientFace().expressInterest(*interest, nullptr, nullptr, nullptr);
   this->advanceClocks(10_ms, 100_ms);
   BOOST_CHECK_EQUAL(linkAB->getFace(nodeA).getCounters().nOutInterests, 1);

   // The third interest should again go via AD, since both the face from A is already used
   // and so asf should choose the earliest used face i.e. AD
   interest->refreshNonce();
   consumer->getClientFace().expressInterest(*interest, nullptr, nullptr, nullptr);
   this->advanceClocks(10_ms, 100_ms);
   BOOST_CHECK_EQUAL(linkAD->getFace(nodeA).getCounters().nOutInterests, 2);

   this->advanceClocks(time::milliseconds(500), time::seconds(5));
   BOOST_CHECK_EQUAL(linkAD->getFace(nodeA).getCounters().nInData, 1);
   BOOST_CHECK_EQUAL(linkAB->getFace(nodeA).getCounters().nInData, 1);
   BOOST_CHECK_EQUAL(consumer->getForwarderFace().getCounters().nOutData, 1);

 }

 BOOST_AUTO_TEST_CASE(Retransmission)
 {
   // This is a unit test written to recreate the following issue
   // https://redmine.named-data.net/issues/4874
   /*
    *                  +---------+   10ms   +---------+
    *                  |  nodeB  | ------>  |  nodeC  |
    *                  +---------+          +---------+
    */
   // Avoid clearing pit entry for those incoming interest that have pit entry but no next hops

   static const Name PRODUCER_PREFIX = "ndn:/pnr/C";
   Name parameters = AsfStrategy::getStrategyName();
   TopologyTester topo;

   TopologyNode nodeB = topo.addForwarder("B"),
                nodeC = topo.addForwarder("C");

   topo.setStrategy<AsfStrategy>(nodeB, Name("ndn:/"), parameters);
   topo.setStrategy<AsfStrategy>(nodeC, Name("ndn:/"), parameters);

   shared_ptr<TopologyLink> linkBC = topo.addLink("BC", time::milliseconds(10), {nodeB, nodeC});

   shared_ptr<TopologyAppLink> consumer = topo.addAppFace("c", nodeB),
                               producer = topo.addAppFace("p", nodeC, PRODUCER_PREFIX);

   topo.addEchoProducer(producer->getClientFace(), PRODUCER_PREFIX, 100_ms);

   Name name(PRODUCER_PREFIX);
   name.appendTimestamp();
   auto interest = makeInterest(name, true);

   nfd::pit::Pit& pit = topo.getForwarder(nodeB).getPit();
   shared_ptr<pit::Entry> pitEntry = pit.insert(*interest).first;

   topo.getForwarder(nodeB).onOutgoingInterest(pitEntry, FaceEndpoint(linkBC->getFace(nodeB), 0), *interest);
   this->advanceClocks(time::milliseconds(100));

   interest->refreshNonce();
   consumer->getClientFace().expressInterest(*interest, nullptr, nullptr, nullptr);
   this->advanceClocks(time::milliseconds(100));

   pit::OutRecordCollection::const_iterator outRecord = pitEntry->getOutRecord(linkBC->getFace(nodeB));
   BOOST_CHECK(outRecord != pitEntry->out_end());

   this->advanceClocks(time::milliseconds(100));
   BOOST_CHECK_EQUAL(linkBC->getFace(nodeC).getCounters().nOutData, 1);
   BOOST_CHECK_EQUAL(linkBC->getFace(nodeB).getCounters().nInData, 1);
 }

 BOOST_AUTO_TEST_CASE(NoPitOutRecordAndProbeInterestNewNonce)
 {
   /*                 +---------+
   *                  |  nodeD  |
   *                  +---------+
   *                       |
   *                       | 80ms
   *                       |
   *                       |
   *                  +---------+
   *           +----->|  nodeB  |<------+
   *           |      +---------+       |
   *      15ms |                        | 16ms
   *           v                        v
   *      +---------+              +---------+
   *      |  nodeA  |--------------|  nodeC  |
   *      +---------+     14ms      +---------+
   */

   const Name PRODUCER_PREFIX = "/ndn/edu/nodeD/ping";

   TopologyTester topo;
   TopologyNode nodeA = topo.addForwarder("A"),
                nodeB = topo.addForwarder("B"),
                nodeC = topo.addForwarder("C"),
                nodeD = topo.addForwarder("D");

   for (TopologyNode node : {nodeA, nodeB, nodeC, nodeD}) {
     topo.setStrategy<AsfStrategy>(node);
   }

   shared_ptr<TopologyLink> linkAB = topo.addLink("AB", 15_ms, {nodeA, nodeB}),
                            linkAC = topo.addLink("AC", 14_ms, {nodeA, nodeC}),
                            linkBC = topo.addLink("BC", 16_ms, {nodeB, nodeC}),
                            linkBD = topo.addLink("BD", 80_ms, {nodeB, nodeD});

   shared_ptr<TopologyAppLink> ping = topo.addAppFace("c", nodeA),
                         pingServer = topo.addAppFace("p", nodeD, PRODUCER_PREFIX);
   topo.addEchoProducer(pingServer->getClientFace());

   // Register prefixes
   topo.registerPrefix(nodeA, linkAB->getFace(nodeA), PRODUCER_PREFIX, 15);
   topo.registerPrefix(nodeA, linkAC->getFace(nodeA), PRODUCER_PREFIX, 14);
   topo.registerPrefix(nodeC, linkBC->getFace(nodeC), PRODUCER_PREFIX, 16);
   topo.registerPrefix(nodeB, linkBD->getFace(nodeB), PRODUCER_PREFIX, 80);

   // Send 6 interest since probes can be scheduled b/w 0-5 seconds
   for (int i = 1; i < 7; i++) {
     // Send ping number i
     Name name(PRODUCER_PREFIX);
     name.appendTimestamp();
     auto interest = makeInterest(name);
     ping->getClientFace().expressInterest(*interest, nullptr, nullptr, nullptr);
     auto nonce = interest->getNonce();

     // Don't know when the probe will be triggered since it is random between 0-5 seconds
     // or whether it will be triggered for this interest
     for (int j = 1; j <= 1000 && linkAB->getFace(nodeA).getCounters().nOutInterests != 1; ++j) {
       this->advanceClocks(1_ms);
     }

     // Check if probe is sent to B else send another ping
     if (linkAB->getFace(nodeA).getCounters().nOutInterests == 1) {
       // Get pitEntry of node A
       auto pitEntry = topo.getForwarder(nodeA).getPit().find(*interest);
       // Get outRecord associated with face towards B
       auto outRecord = pitEntry->getOutRecord(linkAB->getFace(nodeA));
       BOOST_REQUIRE(outRecord != pitEntry->out_end());

       // Check that Nonce of interest is not equal to Nonce of Probe
       BOOST_CHECK_NE(nonce, outRecord->getLastNonce());

       // B should not have received the probe interest yet
       BOOST_CHECK_EQUAL(linkAB->getFace(nodeB).getCounters().nInInterests, 0);

       // i-1 interests through B when no probe
       BOOST_CHECK_EQUAL(linkBD->getFace(nodeB).getCounters().nOutInterests, i - 1);

       // After 15ms, B should get the probe interest
       this->advanceClocks(1_ms, 15_ms);
       BOOST_CHECK_EQUAL(linkAB->getFace(nodeB).getCounters().nInInterests, 1);
       BOOST_CHECK_EQUAL(linkBD->getFace(nodeB).getCounters().nOutInterests, i);

       pitEntry = topo.getForwarder(nodeB).getPit().find(*interest);

       // Get outRecord associated with face towards D.
       outRecord = pitEntry->getOutRecord(linkBD->getFace(nodeB));
       BOOST_CHECK(outRecord != pitEntry->out_end());

       // RTT between B and D
       this->advanceClocks(5_ms, 160_ms);
       outRecord = pitEntry->getOutRecord(linkBD->getFace(nodeB));

       BOOST_CHECK_EQUAL(linkBD->getFace(nodeB).getCounters().nInData, i);

       BOOST_CHECK(outRecord == pitEntry->out_end());

       // Data is returned for the ping after 15 ms - will result in false measurement
       // 14+16-15 = 15ms
       // Since outRecord == pitEntry->out_end()
       this->advanceClocks(1_ms, 15_ms);
       BOOST_CHECK_EQUAL(linkBD->getFace(nodeB).getCounters().nInData, i+1);

       break;
     }
   }
 }

 BOOST_FIXTURE_TEST_CASE(IgnoreTimeouts, AsfStrategyParametersGridFixture)
 {
   // Both nodeB and nodeD have FIB entries to reach the producer
   topo.registerPrefix(nodeB, linkBC->getFace(nodeB), PRODUCER_PREFIX);
   topo.registerPrefix(nodeD, linkCD->getFace(nodeD), PRODUCER_PREFIX);

   // Send 15 interests let it change to use the 10 ms link
   runConsumer(15);

   int outInterestsBeforeFailure = linkAD->getFace(nodeA).getCounters().nOutInterests;

   // Bring down 10 ms link
   linkAB->fail();

   // Send 6 interests, first 5 will be ignored and on the 6th it will record the timeout
   // ready to switch for the next interest
   runConsumer(6);

   // Check that link has not been switched to 100 ms because n-silent-timeouts = 5
   BOOST_CHECK_EQUAL(linkAD->getFace(nodeA).getCounters().nOutInterests - outInterestsBeforeFailure, 0);

   // Send 5 interests, check that 100 ms link is used
   runConsumer(5);

   BOOST_CHECK_EQUAL(linkAD->getFace(nodeA).getCounters().nOutInterests - outInterestsBeforeFailure, 5);
 }

 BOOST_FIXTURE_TEST_CASE(ProbingInterval, AsfStrategyParametersGridFixture)
 {
   // Both nodeB and nodeD have FIB entries to reach the producer
   topo.registerPrefix(nodeB, linkBC->getFace(nodeB), PRODUCER_PREFIX);
   topo.registerPrefix(nodeD, linkCD->getFace(nodeD), PRODUCER_PREFIX);

   // Send 6 interests let it change to use the 10 ms link
   runConsumer(6);

   shared_ptr<TopologyLink> linkAC = topo.addLink("AC", 5_ms, {nodeA, nodeD});
   topo.registerPrefix(nodeA, linkAC->getFace(nodeA), PRODUCER_PREFIX, 1);

   BOOST_CHECK_EQUAL(linkAC->getFace(nodeA).getCounters().nOutInterests, 0);

   // After 30 seconds a probe would be sent that would switch make ASF switch
   runConsumer(30);

   BOOST_CHECK_EQUAL(linkAC->getFace(nodeA).getCounters().nOutInterests, 1);
 }

 class ParametersFixture
 {
 public:
   void
   checkValidity(std::string parameters, bool isCorrect)
   {
     Name strategyName(Name(AsfStrategy::getStrategyName()).append(parameters));
     if (isCorrect) {
       BOOST_CHECK_NO_THROW(make_unique<AsfStrategy>(forwarder, strategyName));
     }
     else {
       BOOST_CHECK_THROW(make_unique<AsfStrategy>(forwarder, strategyName), std::invalid_argument);
     }
   }

 protected:
   FaceTable faceTable;
   Forwarder forwarder{faceTable};
 };

 BOOST_FIXTURE_TEST_CASE(InstantiationTest, ParametersFixture)
 {
   checkValidity("/probing-interval~30000/n-silent-timeouts~5", true);
   checkValidity("/n-silent-timeouts~5/probing-interval~30000", true);
   checkValidity("/probing-interval~30000", true);
   checkValidity("/n-silent-timeouts~5", true);
   checkValidity("", true);

   checkValidity("/probing-interval~500", false); // At least 1 seconds
   checkValidity("/probing-interval~-5000", false);
   checkValidity("/n-silent-timeouts~-5", false);
   checkValidity("/n-silent-timeouts~-5/probing-interval~-30000", false);
   checkValidity("/n-silent-timeouts", false);
   checkValidity("/probing-interval~", false);
   checkValidity("/~1000", false);
   checkValidity("/probing-interval~foo", false);
   checkValidity("/n-silent-timeouts~1~2", false);
 }

 BOOST_AUTO_TEST_SUITE_END() // TestAsfStrategy
 BOOST_AUTO_TEST_SUITE_END() // Fw

 } // namespace tests
 } // namespace asf
 } // namespace fw
 } // namespace nfd
	/* -- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -- */
	/*
	* Copyright (c) 2014-2020, Regents of the University of California,
	* Arizona Board of Regents,
	* Colorado State University,
	* University Pierre & Marie Curie, Sorbonne University,
	* Washington University in St. Louis,
	* Beijing Institute of Technology,
	* The University of Memphis.
	*
	* This file is part of NFD (Named Data Networking Forwarding Daemon).
	* See AUTHORS.md for complete list of NFD authors and contributors.
	*
	* NFD 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.
	*
	* NFD 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
	* NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
	*/

	#include "fw/asf-strategy.hpp"

	#include "strategy-tester.hpp"
	#include "topology-tester.hpp"

	namespace nfd {
	namespace fw {
	namespace asf {
	namespace tests {

	using namespace nfd::fw::tests;

	// The tester is unused in this file, but it's used in various templated test suites.
	using AsfStrategyTester = StrategyTester<AsfStrategy>;
	NFD_REGISTER_STRATEGY(AsfStrategyTester);

	BOOST_AUTO_TEST_SUITE(Fw)
	BOOST_FIXTURE_TEST_SUITE(TestAsfStrategy, GlobalIoTimeFixture)

	class AsfGridFixture : public GlobalIoTimeFixture
	{
	protected:
	explicit
	AsfGridFixture(const Name& params = AsfStrategy::getStrategyName(), time::nanoseconds replyDelay = 0_ms)
	: parameters(params)
	{
	/*
	* +---------+
	* +----->\| nodeB \|<------+
	* \| +---------+ \|
	* 10ms \| \| 10ms
	* v v
	* +---------+ +---------+
	* \| nodeA \| \| nodeC \|
	* +---------+ +---------+
	* ^ ^
	* 100ms \| \| 100ms
	* \| +---------+ \|
	* +----->\| nodeD \|<------+
	* +---------+
	*/

	nodeA = topo.addForwarder("A");
	nodeB = topo.addForwarder("B");
	nodeC = topo.addForwarder("C");
	nodeD = topo.addForwarder("D");

	topo.setStrategy<AsfStrategy>(nodeA, Name("ndn:/"), parameters);
	topo.setStrategy<AsfStrategy>(nodeB, Name("ndn:/"), parameters);
	topo.setStrategy<AsfStrategy>(nodeC, Name("ndn:/"), parameters);
	topo.setStrategy<AsfStrategy>(nodeD, Name("ndn:/"), parameters);

	linkAB = topo.addLink("AB", 10_ms, {nodeA, nodeB});
	linkAD = topo.addLink("AD", 100_ms, {nodeA, nodeD});
	linkBC = topo.addLink("BC", 10_ms, {nodeB, nodeC});
	linkCD = topo.addLink("CD", 100_ms, {nodeC, nodeD});

	consumer = topo.addAppFace("c", nodeA);
	producer = topo.addAppFace("p", nodeC, PRODUCER_PREFIX);

	topo.addEchoProducer(producer->getClientFace(), PRODUCER_PREFIX, replyDelay);

	// Register producer prefix on consumer node
	topo.registerPrefix(nodeA, linkAB->getFace(nodeA), PRODUCER_PREFIX, 10);
	topo.registerPrefix(nodeA, linkAD->getFace(nodeA), PRODUCER_PREFIX, 5);
	}

	void
	runConsumer(int numInterests = 30)
	{
	topo.addIntervalConsumer(consumer->getClientFace(), PRODUCER_PREFIX, 1_s, numInterests);
	this->advanceClocks(10_ms, time::seconds(numInterests));
	}

	protected:
	Name parameters;
	TopologyTester topo;

	TopologyNode nodeA;
	TopologyNode nodeB;
	TopologyNode nodeC;
	TopologyNode nodeD;

	shared_ptr<TopologyLink> linkAB;
	shared_ptr<TopologyLink> linkAD;
	shared_ptr<TopologyLink> linkBC;
	shared_ptr<TopologyLink> linkCD;

	shared_ptr<TopologyAppLink> consumer;
	shared_ptr<TopologyAppLink> producer;

	static const Name PRODUCER_PREFIX;
	};

	class AsfStrategyParametersGridFixture : public AsfGridFixture
	{
	protected:
	AsfStrategyParametersGridFixture()
	: AsfGridFixture(Name(AsfStrategy::getStrategyName())
	.append("probing-interval~30000")
	.append("n-silent-timeouts~5"))
	{
	}
	};

	const Name AsfGridFixture::PRODUCER_PREFIX = Name("ndn:/hr/C");

	BOOST_FIXTURE_TEST_CASE(Basic, AsfGridFixture)
	{
	// Both nodeB and nodeD have FIB entries to reach the producer
	topo.registerPrefix(nodeB, linkBC->getFace(nodeB), PRODUCER_PREFIX);
	topo.registerPrefix(nodeD, linkCD->getFace(nodeD), PRODUCER_PREFIX);

	runConsumer();

	// ASF should use the Face to nodeD because it has lower routing cost.
	// After 5 seconds, a probe Interest should be sent to the Face to nodeB,
	// and the probe should return Data quicker. ASF should then use the Face
	// to nodeB to forward the remaining Interests.
	BOOST_CHECK_EQUAL(consumer->getForwarderFace().getCounters().nOutData, 30);
	// Because of exploration, will forward to AB and AD simultaneously at least once
	BOOST_CHECK_GE(linkAB->getFace(nodeA).getCounters().nOutInterests, 25);
	BOOST_CHECK_LE(linkAD->getFace(nodeA).getCounters().nOutInterests, 6);

	// If the link from nodeA to nodeB fails, ASF should start using the Face
	// to nodeD again.
	linkAB->fail();

	runConsumer();
	// We experience 3 silent timeouts before marking AB as timed out on the fourth interest.
	BOOST_CHECK_EQUAL(consumer->getForwarderFace().getCounters().nOutData, 56);
	BOOST_CHECK_LE(linkAB->getFace(nodeA).getCounters().nOutInterests, 36);
	BOOST_CHECK_GE(linkAD->getFace(nodeA).getCounters().nOutInterests, 24);

	// If the link from nodeA to nodeB recovers, ASF should probe the Face
	// to nodeB and start using it again.
	linkAB->recover();

	// Advance time to ensure probing is due
	this->advanceClocks(10_ms, 10_s);

	runConsumer();
	BOOST_CHECK_EQUAL(consumer->getForwarderFace().getCounters().nOutData, 86);
	BOOST_CHECK_GE(linkAB->getFace(nodeA).getCounters().nOutInterests, 50);
	BOOST_CHECK_LE(linkAD->getFace(nodeA).getCounters().nOutInterests, 40);

	// If both links fail, nodeA should forward to the next hop with the lowest cost
	linkAB->fail();
	linkAD->fail();

	runConsumer();

	BOOST_CHECK_EQUAL(consumer->getForwarderFace().getCounters().nOutData, 86);
	BOOST_CHECK_LE(linkAB->getFace(nodeA).getCounters().nOutInterests, 65); // FIXME #3830
	BOOST_CHECK_GE(linkAD->getFace(nodeA).getCounters().nOutInterests, 57); // FIXME #3830
	}

	BOOST_FIXTURE_TEST_CASE(Nack, AsfGridFixture)
	{
	// nodeB has a FIB entry to reach the producer, but nodeD does not
	topo.registerPrefix(nodeB, linkBC->getFace(nodeB), PRODUCER_PREFIX);

	// The strategy should first try to send to nodeD. But since nodeD does not have a route for
	// the producer's prefix, it should return a NO_ROUTE Nack. The strategy should then start using the Face to
	// nodeB.
	runConsumer();

	BOOST_CHECK_GE(linkAD->getFace(nodeA).getCounters().nInNacks, 1);
	BOOST_CHECK_EQUAL(consumer->getForwarderFace().getCounters().nOutData, 29);
	BOOST_CHECK_EQUAL(linkAB->getFace(nodeA).getCounters().nOutInterests, 29);

	// nodeD should receive 2 Interests: one for the very first Interest and
	// another from a probe
	BOOST_CHECK_GE(linkAD->getFace(nodeA).getCounters().nOutInterests, 2);
	}

	class AsfStrategyDelayedDataFixture : public AsfGridFixture
	{
	protected:
	AsfStrategyDelayedDataFixture()
	: AsfGridFixture(Name(AsfStrategy::getStrategyName()), 400_ms)
	{
	}
	};

	BOOST_FIXTURE_TEST_CASE(InterestForwarding, AsfStrategyDelayedDataFixture)
	{

	Name name(PRODUCER_PREFIX);
	name.appendTimestamp();
	shared_ptr<Interest> interest = makeInterest(name, true);

	topo.registerPrefix(nodeB, linkBC->getFace(nodeB), PRODUCER_PREFIX);
	topo.registerPrefix(nodeD, linkCD->getFace(nodeD), PRODUCER_PREFIX);

	// The first interest should go via link AD
	consumer->getClientFace().expressInterest(*interest, nullptr, nullptr, nullptr);
	this->advanceClocks(10_ms, 100_ms);
	BOOST_CHECK_EQUAL(linkAD->getFace(nodeA).getCounters().nOutInterests, 1);

	// Second interest should go via link AB
	interest->refreshNonce();
	consumer->getClientFace().expressInterest(*interest, nullptr, nullptr, nullptr);
	this->advanceClocks(10_ms, 100_ms);
	BOOST_CHECK_EQUAL(linkAB->getFace(nodeA).getCounters().nOutInterests, 1);

	// The third interest should again go via AD, since both the face from A is already used
	// and so asf should choose the earliest used face i.e. AD
	interest->refreshNonce();
	consumer->getClientFace().expressInterest(*interest, nullptr, nullptr, nullptr);
	this->advanceClocks(10_ms, 100_ms);
	BOOST_CHECK_EQUAL(linkAD->getFace(nodeA).getCounters().nOutInterests, 2);

	this->advanceClocks(time::milliseconds(500), time::seconds(5));
	BOOST_CHECK_EQUAL(linkAD->getFace(nodeA).getCounters().nInData, 1);
	BOOST_CHECK_EQUAL(linkAB->getFace(nodeA).getCounters().nInData, 1);
	BOOST_CHECK_EQUAL(consumer->getForwarderFace().getCounters().nOutData, 1);

	}

	BOOST_AUTO_TEST_CASE(Retransmission)
	{
	// This is a unit test written to recreate the following issue
	// https://redmine.named-data.net/issues/4874
	/*
	* +---------+ 10ms +---------+
	* \| nodeB \| ------> \| nodeC \|
	* +---------+ +---------+
	*/
	// Avoid clearing pit entry for those incoming interest that have pit entry but no next hops

	static const Name PRODUCER_PREFIX = "ndn:/pnr/C";
	Name parameters = AsfStrategy::getStrategyName();
	TopologyTester topo;

	TopologyNode nodeB = topo.addForwarder("B"),
	nodeC = topo.addForwarder("C");

	topo.setStrategy<AsfStrategy>(nodeB, Name("ndn:/"), parameters);
	topo.setStrategy<AsfStrategy>(nodeC, Name("ndn:/"), parameters);

	shared_ptr<TopologyLink> linkBC = topo.addLink("BC", time::milliseconds(10), {nodeB, nodeC});

	shared_ptr<TopologyAppLink> consumer = topo.addAppFace("c", nodeB),
	producer = topo.addAppFace("p", nodeC, PRODUCER_PREFIX);

	topo.addEchoProducer(producer->getClientFace(), PRODUCER_PREFIX, 100_ms);

	Name name(PRODUCER_PREFIX);
	name.appendTimestamp();
	auto interest = makeInterest(name, true);

	nfd::pit::Pit& pit = topo.getForwarder(nodeB).getPit();
	shared_ptr<pit::Entry> pitEntry = pit.insert(*interest).first;

	topo.getForwarder(nodeB).onOutgoingInterest(pitEntry, FaceEndpoint(linkBC->getFace(nodeB), 0), *interest);
	this->advanceClocks(time::milliseconds(100));

	interest->refreshNonce();
	consumer->getClientFace().expressInterest(*interest, nullptr, nullptr, nullptr);
	this->advanceClocks(time::milliseconds(100));

	pit::OutRecordCollection::const_iterator outRecord = pitEntry->getOutRecord(linkBC->getFace(nodeB));
	BOOST_CHECK(outRecord != pitEntry->out_end());

	this->advanceClocks(time::milliseconds(100));
	BOOST_CHECK_EQUAL(linkBC->getFace(nodeC).getCounters().nOutData, 1);
	BOOST_CHECK_EQUAL(linkBC->getFace(nodeB).getCounters().nInData, 1);
	}

	BOOST_AUTO_TEST_CASE(NoPitOutRecordAndProbeInterestNewNonce)
	{
	/* +---------+
	* \| nodeD \|
	* +---------+
	* \|
	* \| 80ms
	* \|
	* \|
	* +---------+
	* +----->\| nodeB \|<------+
	* \| +---------+ \|
	* 15ms \| \| 16ms
	* v v
	* +---------+ +---------+
	* \| nodeA \|--------------\| nodeC \|
	* +---------+ 14ms +---------+
	*/

	const Name PRODUCER_PREFIX = "/ndn/edu/nodeD/ping";

	TopologyTester topo;
	TopologyNode nodeA = topo.addForwarder("A"),
	nodeB = topo.addForwarder("B"),
	nodeC = topo.addForwarder("C"),
	nodeD = topo.addForwarder("D");

	for (TopologyNode node : {nodeA, nodeB, nodeC, nodeD}) {
	topo.setStrategy<AsfStrategy>(node);
	}

	shared_ptr<TopologyLink> linkAB = topo.addLink("AB", 15_ms, {nodeA, nodeB}),
	linkAC = topo.addLink("AC", 14_ms, {nodeA, nodeC}),
	linkBC = topo.addLink("BC", 16_ms, {nodeB, nodeC}),
	linkBD = topo.addLink("BD", 80_ms, {nodeB, nodeD});

	shared_ptr<TopologyAppLink> ping = topo.addAppFace("c", nodeA),
	pingServer = topo.addAppFace("p", nodeD, PRODUCER_PREFIX);
	topo.addEchoProducer(pingServer->getClientFace());

	// Register prefixes
	topo.registerPrefix(nodeA, linkAB->getFace(nodeA), PRODUCER_PREFIX, 15);
	topo.registerPrefix(nodeA, linkAC->getFace(nodeA), PRODUCER_PREFIX, 14);
	topo.registerPrefix(nodeC, linkBC->getFace(nodeC), PRODUCER_PREFIX, 16);
	topo.registerPrefix(nodeB, linkBD->getFace(nodeB), PRODUCER_PREFIX, 80);

	// Send 6 interest since probes can be scheduled b/w 0-5 seconds
	for (int i = 1; i < 7; i++) {
	// Send ping number i
	Name name(PRODUCER_PREFIX);
	name.appendTimestamp();
	auto interest = makeInterest(name);
	ping->getClientFace().expressInterest(*interest, nullptr, nullptr, nullptr);
	auto nonce = interest->getNonce();

	// Don't know when the probe will be triggered since it is random between 0-5 seconds
	// or whether it will be triggered for this interest
	for (int j = 1; j <= 1000 && linkAB->getFace(nodeA).getCounters().nOutInterests != 1; ++j) {
	this->advanceClocks(1_ms);
	}

	// Check if probe is sent to B else send another ping
	if (linkAB->getFace(nodeA).getCounters().nOutInterests == 1) {
	// Get pitEntry of node A
	auto pitEntry = topo.getForwarder(nodeA).getPit().find(*interest);
	// Get outRecord associated with face towards B
	auto outRecord = pitEntry->getOutRecord(linkAB->getFace(nodeA));
	BOOST_REQUIRE(outRecord != pitEntry->out_end());

	// Check that Nonce of interest is not equal to Nonce of Probe
	BOOST_CHECK_NE(nonce, outRecord->getLastNonce());

	// B should not have received the probe interest yet
	BOOST_CHECK_EQUAL(linkAB->getFace(nodeB).getCounters().nInInterests, 0);

	// i-1 interests through B when no probe
	BOOST_CHECK_EQUAL(linkBD->getFace(nodeB).getCounters().nOutInterests, i - 1);

	// After 15ms, B should get the probe interest
	this->advanceClocks(1_ms, 15_ms);
	BOOST_CHECK_EQUAL(linkAB->getFace(nodeB).getCounters().nInInterests, 1);
	BOOST_CHECK_EQUAL(linkBD->getFace(nodeB).getCounters().nOutInterests, i);

	pitEntry = topo.getForwarder(nodeB).getPit().find(*interest);

	// Get outRecord associated with face towards D.
	outRecord = pitEntry->getOutRecord(linkBD->getFace(nodeB));
	BOOST_CHECK(outRecord != pitEntry->out_end());

	// RTT between B and D
	this->advanceClocks(5_ms, 160_ms);
	outRecord = pitEntry->getOutRecord(linkBD->getFace(nodeB));

	BOOST_CHECK_EQUAL(linkBD->getFace(nodeB).getCounters().nInData, i);

	BOOST_CHECK(outRecord == pitEntry->out_end());

	// Data is returned for the ping after 15 ms - will result in false measurement
	// 14+16-15 = 15ms
	// Since outRecord == pitEntry->out_end()
	this->advanceClocks(1_ms, 15_ms);
	BOOST_CHECK_EQUAL(linkBD->getFace(nodeB).getCounters().nInData, i+1);

	break;
	}
	}
	}

	BOOST_FIXTURE_TEST_CASE(IgnoreTimeouts, AsfStrategyParametersGridFixture)
	{
	// Both nodeB and nodeD have FIB entries to reach the producer
	topo.registerPrefix(nodeB, linkBC->getFace(nodeB), PRODUCER_PREFIX);
	topo.registerPrefix(nodeD, linkCD->getFace(nodeD), PRODUCER_PREFIX);

	// Send 15 interests let it change to use the 10 ms link
	runConsumer(15);

	int outInterestsBeforeFailure = linkAD->getFace(nodeA).getCounters().nOutInterests;

	// Bring down 10 ms link
	linkAB->fail();

	// Send 6 interests, first 5 will be ignored and on the 6th it will record the timeout
	// ready to switch for the next interest
	runConsumer(6);

	// Check that link has not been switched to 100 ms because n-silent-timeouts = 5
	BOOST_CHECK_EQUAL(linkAD->getFace(nodeA).getCounters().nOutInterests - outInterestsBeforeFailure, 0);

	// Send 5 interests, check that 100 ms link is used
	runConsumer(5);

	BOOST_CHECK_EQUAL(linkAD->getFace(nodeA).getCounters().nOutInterests - outInterestsBeforeFailure, 5);
	}

	BOOST_FIXTURE_TEST_CASE(ProbingInterval, AsfStrategyParametersGridFixture)
	{
	// Both nodeB and nodeD have FIB entries to reach the producer
	topo.registerPrefix(nodeB, linkBC->getFace(nodeB), PRODUCER_PREFIX);
	topo.registerPrefix(nodeD, linkCD->getFace(nodeD), PRODUCER_PREFIX);

	// Send 6 interests let it change to use the 10 ms link
	runConsumer(6);

	shared_ptr<TopologyLink> linkAC = topo.addLink("AC", 5_ms, {nodeA, nodeD});
	topo.registerPrefix(nodeA, linkAC->getFace(nodeA), PRODUCER_PREFIX, 1);

	BOOST_CHECK_EQUAL(linkAC->getFace(nodeA).getCounters().nOutInterests, 0);

	// After 30 seconds a probe would be sent that would switch make ASF switch
	runConsumer(30);

	BOOST_CHECK_EQUAL(linkAC->getFace(nodeA).getCounters().nOutInterests, 1);
	}

	class ParametersFixture
	{
	public:
	void
	checkValidity(std::string parameters, bool isCorrect)
	{
	Name strategyName(Name(AsfStrategy::getStrategyName()).append(parameters));
	if (isCorrect) {
	BOOST_CHECK_NO_THROW(make_unique<AsfStrategy>(forwarder, strategyName));
	}
	else {
	BOOST_CHECK_THROW(make_unique<AsfStrategy>(forwarder, strategyName), std::invalid_argument);
	}
	}

	protected:
	FaceTable faceTable;
	Forwarder forwarder{faceTable};
	};

	BOOST_FIXTURE_TEST_CASE(InstantiationTest, ParametersFixture)
	{
	checkValidity("/probing-interval~30000/n-silent-timeouts~5", true);
	checkValidity("/n-silent-timeouts~5/probing-interval~30000", true);
	checkValidity("/probing-interval~30000", true);
	checkValidity("/n-silent-timeouts~5", true);
	checkValidity("", true);

	checkValidity("/probing-interval~500", false); // At least 1 seconds
	checkValidity("/probing-interval~-5000", false);
	checkValidity("/n-silent-timeouts~-5", false);
	checkValidity("/n-silent-timeouts~-5/probing-interval~-30000", false);
	checkValidity("/n-silent-timeouts", false);
	checkValidity("/probing-interval~", false);
	checkValidity("/~1000", false);
	checkValidity("/probing-interval~foo", false);
	checkValidity("/n-silent-timeouts~1~2", false);
	}

	BOOST_AUTO_TEST_SUITE_END() // TestAsfStrategy
	BOOST_AUTO_TEST_SUITE_END() // Fw

	} // namespace tests
	} // namespace asf
	} // namespace fw
	} // namespace nfd