Face and PacketHandler in NDNph

Face is an overloaded term in Named Data Networking (NDN). My last article explained what is a face in NDN forwarders and NDN libraries, and then described the endpoint design in my NDNts library. This time, I'll introduce a unique face API design in my NDNph library.

NDNph is a C++ header-only library that enables low level application development. It supports multiple platforms, but is primarily designed for microcontrollers with limited hardware resources. In particular, RAM capacity is very limited, with typical values ranging from 50KB (ESP8266) to 320KB (ESP32). This necessitates a different API design for the face.

Overhead of a Traditional Face

Traditionally, a face in NDN libraries has the following features:

  • send and receive NDN network layer packets
  • match incoming Data against outgoing Interests
  • keep track of Interest timeouts
  • dispatch incoming Interests to producer callback functions

Some of these features can have substantial memory overhead on a microcontroller:

  • Interest-Data matching and Interest timeout: the library must keep track of every outgoing pending Interest.
  • Incoming Interest dispatching: the library must maintain a lookup table of producer callback functions and their name prefixes.

NDN-Lite Data Structure Sizes

To quantify the memory consumption of these data structures, let's take a look at NDN-Lite, a standalone NDN stack written in C. It provides "traditional face" semantics via ndn_forwarder_express_interest and ndn_forwarder_register_prefix functions.

Internally, these features are realized with three data structures: NameTree, FIB, and PIT. NameTree arranges names in a tree structure, which naturally deduplicates common prefixes, but each component is limited to 38 octets. FIB and PIT do not contain producer prefixes or Interest names; instead, each entry references a NameTree node that has the name.

When compiling for 32-bit architecture (GCC -m32 flag), the data structure sizes are as follows:

structure header size entry size entry count total size
NameTree 0 46 64 2944
FIB 8 24 20 488
PIT 8 64 32 2056

The total size of the three data structures is 5.4KB. Arguably, this is a modest amount compared to the 256KB memory available on the nRF52840 microcontroller where NDN-Lite was originally designed for. However, if we want to port NDN-Lite to a different platform such as the ESP8266 with only 50KB RAM, 5.4KB would be too much overhead.

NDN-Lite offers several tuning knobs that can change the memory consumption of these structures, including the entry count for each table and the maximum length of each name component. However, it's difficult to come up with optimal parameters for a large application with multiple modules, because each module may generate and process different amount of traffic at different times, while the system integrator is expected to enter a static number as the upper bound of all modules.

Designing a Table-less Face

When I designed NDNph, I wanted to try a different idea: a face that does not remember pending Interests or producer prefixes.

Consumer and producer modules, known as packet handlers, are arranged in a linked list. When a packet arrives, the face passes the incoming packet to each packet handler. The packet handler must determine whether it is the intended recipient of the incoming packet, or the packet should be passed to the next packet handler and eventually dropped.

accept? packethandler face transport drop

PacketHandler API

Each application module is expected to inherit from PacketHandler class, whose API looks like this:

/** Base class to receive packets from face. */
class PacketHandler
{
protected:
  /** Add handler to face. */
  explicit PacketHandler(Face&, int priority = 0);

  /** Remove handler from face. */
  virtual ~PacketHandler();

  /** Send an Interest. */
  void send(Interest);

  /** Send a Data. */
  void send(Data);

private:
  /**
   * Perform periodical tasks.
   * This is called once every loop.
   */
  virtual void loop();

  /**
   * Handle incoming Interest.
   * Return true if Interest is accepted by this handler.
   * Return false to pass Interest to the next handler.
   */
  virtual bool processInterest(Interest);

  /**
   * Handle incoming Data.
   * Return true if Data is accepted by this handler.
   * Return false to pass Data to the next handler.
   */
  virtual bool processData(Data);
};

Producer PacketHandler

A producer module should override the processInterest method. When this method is called with an incoming Interest, the producer should check whether it is responsible for answering the incoming Interest, e.g. by comparing the name prefix. If so, it should return true to indicate acceptance, and then send a reply either immediately or at a later time. Otherwise, it should return false, and the Interest would be passed to the next producer for a potential match.

As an example, a reachability test producer that answers every Interest under a name prefix could be written like this:

class PingServer : public PacketHandler
{
public:
  explicit PingServer(Name prefix, Face& face)
    : PacketHandler(face)
    , m_prefix(prefix)
  {}

private:
  bool processInterest(Interest interest) final
  {
    if (!m_prefix.isPrefixOf(interest.getName())) {
      // Interest does not fall under this producer's prefix.
      return false;
    }

    Data data(interest.getName());
    data.setFreshnessPeriod(1);
    this->sendData(data);
    return true;
    // note: memory allocation code omitted
  }

private:
  Name m_prefix;
};

Although it is common to perform a name prefix matching for determining whether a producer should accept an incoming Interest, this API makes it possible to employ other criteria as needed by the application. For example, a temperature sensor may define two producers: the first producer answers Interests for recently completed measurements from a small cache; the second producer immediately performs a measurement and then replies with the result. In this case, the first producer can return true if the requested measurement is found in the cache; the second producer can return true if the requested timestamp is close enough to the current time.

Consumer PacketHandler

A consumer module should override the processData method. When this method is called with an incoming Data, the consumer should check whether it is expecting this Data, and then return true to accept the Data, or false to pass the Data to the next consumer.

The consumer can remember as much or as little information as it needs for determining whether the Data is relevant. Commonly, the consumer could save the Interest name and compare it with the Data names. Sometimes, the same effect can be achieved with less memory usage. In the below example, a consumer sends multiple Interests under a common prefix to download several segments of a file. It only needs to remember the common prefix and the segment numbers, instead of each Interest name.

class FileDownloader : public PacketHandler
{
private:
  bool processData(Data data) final
  {
    if (!m_prefix.isPrefixOf(data.getName())) {
      // Data does not fall under this consumer's prefix.
      return false;
    }

    if (m_prefix.size() + 1 != data.getName().size()) {
      // Data name length is wrong.
      return false;
    }

    if (!data.getName()[-1].is<ndnph::convention::Segment>()) {
      // Last component is not a Segment number.
      return false;
    }

    uint64_t segmentNum = data.getName()[-1].as<ndnph::convention::Segment>();
    if (segmentNum >= m_segmentPending.size() || !m_segmentPending[segmentNum]) {
      // This consumer is not waiting for this segment.
      // Dropping packet, because no other consumer is expected to want this packet.
      return true;
    }

    m_segmentPending[segmentNum] = false;
    // TODO: save retrieved segment
    return true;
  }

private:
  Name m_prefix;
  std::bitset<MAX_SEGMENTS> m_segmentPending;
};

Consumer OutgoingPendingInterest

If a consumer module needs to know about Interest timeouts, there's a helper class OutgoingPendingInterest that keeps track of expiration time of an outgoing pending Interest.

To emphasize, each OutgoingPendingInterest instance can only keep track of one outgoing pending Interest, because a consumer module in an IoT application typically only needs one pending Interest, so that it can statically allocate an OutgoingPendingInterest as a member field in its PacketHandler subclass. In case a module needs multiple pending Interests (generally it's still a small bounded number), it needs to have multiple instances.

The OutgoingPendingInterest helper remembers the PIT token and expiration time of the outgoing pending Interest. The expiration time is derived from InterestLifetime by default, but the consumer can also set a different timer such as retransmission timeout.

The helper does not contain a copy of the Interest name. If the consumer needs name matching, it still needs to store the name elsewhere.

The helper also does not contain a callback function pointer. Instead, the consumer should call pending.expired() function in its loop() method and ask whether the Interest has expired, and take appropriate actions when the function returns true.

NDNph Data Structure Sizes

The following table lists the size (in bytes) of various data structures in current NDNph implementation. They are measured with sizeof operator when compiling for 32-bit architecture.

structure size
Face 28
PacketHandler 24
OutgoingPendingInterest 16

These numbers are significantly smaller than the 5.4KB needed by NDN-Lite, but there's a caveat: memory needed for producer prefixes and Interest names are not included. The unique design in NDNph face means that, each consumer and producer module can make its own choices of how to determine a packet match and what information must be stored to make this determination, which may or may not include the names.

Each consumer and producer module would bring its own memory for its packet match determination, such as a copy of the name or an OutgoingPendingInterest instance. This avoids having centralized tuning knobs that are difficult to set optimally in a large application. Also, the library would never run into a "table full" condition, because there are no tables to begin with.

Final Words

This article describes the unique table-less Face design in my NDNph library. This design delegates packet match determination to PacketHandlers implemented by consumer and producer modules, to achieve greater flexibility and lower memory overhead.

My last article argued that the traditional "face" is often not the right abstraction for applications, and the library should provide endpoint with additional services such as retransmission and signature verification. In contrast, NDNph Face provides even fewer services than a traditional face. This isn't a step backward, but a compromise for devices with limited memory. Also, I have plans to bring back some of the additional services in the form of helper classes, so stay tuned on the NDNph repository on GitHub.