Forwarding Strategies

ndnSIM through its integration with NFD provides simple ways to experiment with the custom Interest/Data forwarding strategies of NFD.

A new forwarding strategy can be implement completely different processing or override just specific actions/events of the forwarding strategy interface. NFD offers the maximum flexibility by allowing per-namespace selection of each specific forwarding strategy.

Please refer to API documentation of the forwarding strategy interface, which lists all default actions/events. For a more detailed specification, you can read NFD Developer’s Guide, section 5.

Available forwarding strategies

Strategy Name Description
/localhost/nfd/strategy/best-route

Best Route Strategy (default)

The best route strategy forwards an Interest to the upstream with lowest routing cost.
   
/localhost/nfd/strategy/ncc

NCC Strategy

The NCC strategy is an reimplementation of CCNx 0.7.2 default strategy. It has similar algorithm but is not guaranteed to be equivalent.
   
/localhost/nfd/strategy/multicast

Multicast Strategy

The multicast strategy forwards every Interest to all upstreams, indicated by the supplied FIB entry.
   
/localhost/nfd/strategy/client-control

Client Control Strategy

The client control strategy allows a local consumer application to choose the outgoing face of each Interest.

Note

ndnSIM 2.0 exactly like NFD allows different namespaces to be associated with different forwarding strategies. By default, the following forwarding strategy configuration is defined:

Namespace Strategy Name
/ /localhost/nfd/strategy/best-route
/localhost /localhost/nfd/strategy/multicast
/localhost/nfd /localhost/nfd/strategy/best-route
/ndn/multicast /localhost/nfd/strategy/multicast

Examples:

StrategyChoiceHelper::Install(nodes, prefix,
                              "/localhost/nfd/strategy/multicast");

Writing your own custom strategy

One of the objectives and features of ndnSIM 2.0 is that it uses NFD codebase for packet forwarding. Therefore, writing strategy in ndnSIM is almost exactly the same process as outlined in Section 5.3 of the NFD Developer’s Guide.

The purpose of the strategy is to decides how to forward Interests and it is not intended to override any processing steps in the forwarding pipelines of NFD. If it is desired to support a new packet type (other than Interest and Data), a new field in Interest or Data packets, or override some actions in the pipelines (e.g., disable ContentStore lookup), it can be accomplished by modification of the forwarding pipelines in nfd::Forwarder class.

The initial step in creating a new strategy is to create a class, say MyStrategy that is derived from nfd::fw::Strategy. This subclass must at least override the triggers that are marked pure virtual and may override other available triggers that are marked just virtual.

If the strategy needs to store information, it is needed to decide whether the information is related to a namespace or an Interest. Information related to a namespace but not specific to an Interest should be stored in Measurements entries; information related to an Interest should be stored in PIT entries, PIT downstream records, or PIT upstream records. After this decision is made, a data structure derived from StrategyInfo class needs to be declared. In the existing implementation, such data structures are declared as nested classes as it provides natural grouping and scope protection of the strategy-specific entity, but it is not required to follow the same model. If timers are needed, EventId fields needs to be added to such data structure(s).

Packet processing in NFD/ndnSIM is broken into a number of small “pipelines” and strategy callbacks

The final step is to implement one or more of the triggers with the desired strategy logic. These triggers are listed below:

  • After Receive Interest Trigger

    When an Interest is received, passes necessary checks, and needs to be forwarded, Incoming Interest pipeline (Section 4.2.1) invokes this trigger with the PIT entry, incoming Interest packet, and FIB entry. At that time, the following conditions hold for the Interest:

    • The Interest does not violate /localhost scope.
    • The Interest is not looped.
    • The Interest cannot be satisfied by ContentStore.
    • The Interest is under a namespace managed by this strategy.

    After being triggered, the strategy should decide whether and where to forward this Interest. If the strategy decides to forward this Interest, it should invoke send Interest action at least once. If the strategy concludes that this Interest cannot be forwarded, it should invoke reject pending Interest action, so that the PIT entry will be deleted shortly.

  • Before Satisfy Interest Trigger

    This method will be triggered just before the pending Interest is being satisfied. It may be useful override this method, e.g., to measure data plane performance.

  • Before Expire Interest Trigger

    This method will be triggered just before the pending Interest is timed out. Same as with the before satisfy interest trigger, this method may be useful o measure data plane performance.

Example

The following code implements a random load balancing forwarding strategy. This strategy was created by Steve DiBenedetto and was found in one of his GitHub repository.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#ifndef NDNSIM_EXAMPLES_NDN_LOAD_BALANCER_RANDOM_LOAD_BALANCER_STRATEGY_HPP
#define NDNSIM_EXAMPLES_NDN_LOAD_BALANCER_RANDOM_LOAD_BALANCER_STRATEGY_HPP

#include <boost/random/mersenne_twister.hpp>
#include "face/face.hpp"
#include "fw/strategy.hpp"
#include "fw/algorithm.hpp"

namespace nfd {
namespace fw {

class RandomLoadBalancerStrategy : public Strategy {
public:
  RandomLoadBalancerStrategy(Forwarder& forwarder, const Name& name = getStrategyName());

  virtual ~RandomLoadBalancerStrategy() override;

  virtual void
  afterReceiveInterest(const Face& inFace, const Interest& interest,
                       const shared_ptr<pit::Entry>& pitEntry) override;

  static const Name&
  getStrategyName();

protected:
  boost::random::mt19937 m_randomGenerator;
};

} // namespace fw
} // namespace nfd

#endif // NDNSIM_EXAMPLES_NDN_LOAD_BALANCER_RANDOM_LOAD_BALANCER_STRATEGY_HPP

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include "random-load-balancer-strategy.hpp"

#include <boost/random/uniform_int_distribution.hpp>

#include <ndn-cxx/util/random.hpp>

#include "core/logger.hpp"

NFD_LOG_INIT("RandomLoadBalancerStrategy");

namespace nfd {
namespace fw {

RandomLoadBalancerStrategy::RandomLoadBalancerStrategy(Forwarder& forwarder, const Name& name)
  : Strategy(forwarder)
{
  this->setInstanceName(makeInstanceName(name, getStrategyName()));
}

RandomLoadBalancerStrategy::~RandomLoadBalancerStrategy()
{
}

static bool
canForwardToNextHop(const Face& inFace, shared_ptr<pit::Entry> pitEntry, const fib::NextHop& nexthop)
{
  return !wouldViolateScope(inFace, pitEntry->getInterest(), nexthop.getFace()) &&
    canForwardToLegacy(*pitEntry, nexthop.getFace());
}

static bool
hasFaceForForwarding(const Face& inFace, const fib::NextHopList& nexthops, const shared_ptr<pit::Entry>& pitEntry)
{
  return std::find_if(nexthops.begin(), nexthops.end(), bind(&canForwardToNextHop, cref(inFace), pitEntry, _1))
         != nexthops.end();
}

void
RandomLoadBalancerStrategy::afterReceiveInterest(const Face& inFace, const Interest& interest,
                                                 const shared_ptr<pit::Entry>& pitEntry)
{
  NFD_LOG_TRACE("afterReceiveInterest");

  if (hasPendingOutRecords(*pitEntry)) {
    // not a new Interest, don't forward
    return;
  }

  const fib::Entry& fibEntry = this->lookupFib(*pitEntry);
  const fib::NextHopList& nexthops = fibEntry.getNextHops();

  // Ensure there is at least 1 Face is available for forwarding
  if (!hasFaceForForwarding(inFace, nexthops, pitEntry)) {
    this->rejectPendingInterest(pitEntry);
    return;
  }

  fib::NextHopList::const_iterator selected;
  do {
    boost::random::uniform_int_distribution<> dist(0, nexthops.size() - 1);
    const size_t randomIndex = dist(m_randomGenerator);

    uint64_t currentIndex = 0;

    for (selected = nexthops.begin(); selected != nexthops.end() && currentIndex != randomIndex;
         ++selected, ++currentIndex) {
    }
  } while (!canForwardToNextHop(inFace, pitEntry, *selected));

  this->sendInterest(pitEntry, selected->getFace(), interest);
}

const Name&
RandomLoadBalancerStrategy::getStrategyName()
{
  static Name strategyName("ndn:/localhost/nfd/strategy/random-load-balancer/%FD%01");
  return strategyName;
}

} // namespace fw
} // namespace nfd

This forwarding strategy can be enabled for a specific name prefix when developing the simulation scenario as follows:

#include "random-load-balancer-strategy.hpp"

...

StrategyChoiceHelper::Install<nfd::fw::RandomLoadBalancerStrategy>(nodes, prefix);

Example of using custom strategy

Please refer to 6-node topology with custom NFD forwarding strategy .