NFD

Here's what I have for the design of the fragmentation, reassembly, and sequence number assignment modules:

/** \brief fragments a network-layer packet into link-layer packets
 *  \return vector of fragmented packets
 */
std::vector<lp::Packet>
fragmentPacket(lp::Packet packet, size_t mtu);

/** \brief reassembles fragmented network-layer packets
 */
class LpReassembler
{
public:
  // Holds all fragments of packet until reassembled
  struct PartialPacket
  {
    std::map<uint64_t, lp::Packet> fragments;
    size_t fragCount;
    boost::steady_clock::TimePoint lastReceiveTime;
  };

public:
  /** \param timeout timeout before packet dropped after last fragment received
   */
  LpReassembler(boost::posix_time::time_duration timeout);

  /** \brief adds received fragment to buffer
   *  \param packet fragment of network-layer packet
   *  \return if network-layer packet completely received
   */
  bool
  addReceived(lp::Packet packet);

  /** \brief reassembles network-layer packet starting with sequence number from fragments
   *  \throws std::length_error if recvCount != totalFrags
   */
  lp::Packet
  reassemble(uint64_t startSeq);

private:
  // Called on every invocation of addReceived
  /** \brief called to process drops and other events
   */
  void
  processEvents();

private:
  boost::steady_clock::TimePoint m_lastReceiveTime;
  boost::posix_time::time_duration m_timeout;
  std::unordered_map<lp::Sequence, PartialPacket> m_packets; // key is starting sequence of packet
};

class LinkService
{
private:
  // Called on receive packet
  /** \brief called to process deletion of old reassemblers and other events
   */
  void
  processEvents();

private:
  // One reassembler for each endpoint in multi-access link, on point-to-point links just has a single member
  // On multi-access links, reassemblers deleted after no use within timeout period
  std::unordered_map<uint64_t, LpReassembler> m_reassembler;
  uint64_t m_nextSeq; // initialized by constructor
  boost::posix_time::time_duration m_timeout;
};

• PartialPacket::fragments can simply be a vector, because FragIndex is sequential and starts from zero. You should call reserve(fragCount) on the vector upon receiving the first fragment, in order to preallocate enough memory for all fragments without resizing the vector later.

• In a few places where you use uint64_t I think you mean lp::Sequence.

• I'm not sure why you need processEvents... can't you use timers?

• How does the link service know the right startSeq to be passed to reassemble?

Updated design:

// Maximum number of fragments in a packet
// (given 8800 bytes max in each packet / 1000 fragments = 8.8 bytes per fragment)
#define LP_MAX_FRAGMENTS = 1000;

/** \brief fragments a network-layer packet into link-layer packets
 *  \return vector of fragmented packets
 */
std::vector<lp::Packet>
fragmentPacket(lp::Packet packet, size_t mtu);

/** \brief reassembles fragmented network-layer packets
 */
class LpReassembler
{
public:
  // Holds all fragments of packet until reassembled
  struct PartialPacket
  {
    std::vector<lp::Packet> fragments;
    size_t fragCount;
    ndn::scheduler::EventId dropTimeout;
  };

public:
  /** \param timeout timeout before packet dropped after last fragment received
   */
  LpReassembler(boost::posix_time::time_duration timeout);

  /** \brief adds received fragment to buffer
   *  \param packet fragment of network-layer packet
   *  \return if network-layer packet completely received
   */
  bool
  addReceived(lp::Packet packet);

  /** \brief reassembles network-layer packet starting with sequence number from fragments
   *  \throws std::length_error if recvCount != totalFrags
   */
  lp::Packet
  reassemble(lp::Sequence startSeq);

private:
  boost::steady_clock::TimePoint m_lastReceiveTime;
  boost::posix_time::time_duration m_timeout;
  std::unordered_map<lp::Sequence, PartialPacket> m_packets; // key is starting sequence of packet
  // startSeq = (seq - fragIndex) of received packet
  ndn::scheduler::Scheduler m_scheduler;
  ndn::scheduler::EventId m_deleteTimeout;
};

class LinkService
{
private:
  // One reassembler for each endpoint in multi-access link, on point-to-point links just has a single member
  // On multi-access links, reassemblers deleted after no use within timeout period
  std::unordered_map<uint64_t, LpReassembler> m_reassembler; // uint64_t is a representation of the network address of the remote endpoint
  lp::Sequence m_nextSeq; // initialized by constructor
  boost::posix_time::time_duration m_timeout;
  ndn::scheduler::Scheduler m_scheduler;
};

• LinkService::m_reassembler should use EndpointId

• How did you solve the last point in note-8? exposing the logic "startSeq = seq - fragIndex" to the LinkService is not good encapsulation in my opinion.

The startSeq is calculated by the LpReassembler by subtracting the FragIndex from the sequence number of the LpPacket. Since all fragments of a packet will have sequential sequence numbers, I believe this is a reliable way to determine the sequence number of the first fragment from any fragment of the packet.

I also updated the design per your suggestions:

// Maximum number of fragments in a packet
// (given 8800 bytes max in each packet / 1000 fragments = at least 8.8 bytes per fragment)
#define LP_MAX_FRAGMENTS = 1000;

/** \brief fragments a network-layer packet into link-layer packets
 *  \return vector of fragmented packets
 */
std::vector<lp::Packet>
fragmentPacket(lp::Packet packet, size_t mtu);

/** \brief reassembles fragmented network-layer packets
 */
class LpReassembler
{
public:
  // Holds all fragments of packet until reassembled
  struct PartialPacket
  {
    std::vector<lp::Packet> fragments;
    size_t fragCount;
    ndn::scheduler::EventId dropTimeout;
  };

public:
  /** \param timeout timeout before packet dropped after last fragment received
   */
  LpReassembler(boost::posix_time::time_duration timeout);

  /** \brief adds received fragment to buffer
   *  \param packet fragment of network-layer packet
   *  \return if network-layer packet completely received
   */
  bool
  addReceived(lp::Packet packet);

  /** \brief reassembles network-layer packet starting with sequence number from fragments
   *  \throws std::length_error if recvCount != totalFrags
   */
  lp::Packet
  reassemble(lp::Sequence startSeq);

private:
  boost::steady_clock::TimePoint m_lastReceiveTime;
  boost::posix_time::time_duration m_timeout;
  std::unordered_map<lp::Sequence, PartialPacket> m_packets; // key is starting sequence of packet
  // How startSeq is calculated: (seq - fragIndex) of received packet
  ndn::scheduler::Scheduler m_scheduler;
  ndn::scheduler::EventId m_deleteTimeout;
};

class LinkService
{
private:
  // One reassembler for each endpoint in multi-access link, on point-to-point links just has a single member
  // On multi-access links, reassemblers deleted after no use within timeout period
  std::unordered_map<EndpointId, LpReassembler> m_reassembler;
  lp::Sequence m_nextSeq; // initialized by constructor
  boost::posix_time::time_duration m_timeout;
  ndn::scheduler::Scheduler m_scheduler;
};

#define LP_MAX_FRAGMENTS = 1000;

This shall be a field in Options. 1000 can be the default.

ndn::scheduler::EventId dropTimeout;

scheduler::ScopedEventId can save you lots of trouble: event is cancelled automatically when the PartialPacket is destructed or when a new event is assigned to this variable.

LpReassembler(boost::posix_time::time_duration timeout);

Use time::nanoseconds for duration, unless there's specific reason to use another type.

The startSeq is calculated by the LpReassembler by subtracting the FragIndex from the sequence number of the LpPacket. Since all fragments of a packet will have sequential sequence numbers, I believe this is a reliable way to determine the sequence number of the first fragment from any fragment of the packet.

bool addReceived(lp::Packet packet);

lp::Packet reassemble(lp::Sequence startSeq);

It is correct that EndpointId+startSeq can be used to uniquely identify a partial packet.
However, this API forces LinkService to understand how startSeq is computed, which is undesirable.

An alternate is: std::tuple<bool, lp::Packet> receiveFragment(const lp::Packet& packet).

std::unordered_map<lp::Sequence, PartialPacket> m_packets;

std::unordered_map<EndpointId, LpReassembler> m_reassembler;

This conflicts with the decision in 20151016 meeting: we have decided to use one reassembler for all senders, and index partial packets in std::unordered_map<std::tuple<EndpointId, lp::Sequence>, PartialPacket> container, so that only one timeout needs to be maintained.

boost::posix_time::time_duration m_timeout;

This timeout shall be a field in Options, with a meaningful default (look at NDNLPv1 implementation and old EthernetFace for a good default).

ndn::scheduler::Scheduler m_scheduler;

NFD has a global scheduler.

Updated: Changed default for Options::lpMaxFragments and added default for lp::packetTimeout

class Options
{
  // Maximum number of fragments in a packet
  // (given 8800 bytes max in each packet / 1000 fragments = at least 8.8 bytes per fragment)
  size_t lpMaxFragments; // 400 by default
  time::nanoseconds packetTimeout; // 60 seconds by default
};

/** \brief fragments a network-layer packet into link-layer packets
 *  \return vector of fragmented packets
 */
std::vector<lp::Packet>
fragmentPacket(lp::Packet packet, size_t mtu);

/** \brief reassembles fragmented network-layer packets
 */
class LpReassembler
{
public:
  // Holds all fragments of packet until reassembled
  struct PartialPacket
  {
    std::vector<lp::Packet> fragments;
    size_t fragCount;
    ndn::scheduler::ScopedEventId dropTimeout;
  };

public:
  /** \param timeout timeout before packet dropped after last fragment received
   */
  LpReassembler(Options& options);

  /** \brief adds received fragment to buffer
   *  \param packet fragment of network-layer packet
   *  \return if network-layer packet completely received and (if complete) reassembled network-layer packet
   */
  std::tuple<bool, lp::Packet>
  addReceived(lp::Packet packet);

private:
  time::nanoseconds m_timeout;
  std::unordered_map<std::tuple<EndpointId, lp::Sequence>, PartialPacket> m_packets;
  // How startSeq is calculated: (seq - fragIndex) of received packet
};

class LinkService
{
private:
  LpReassembler m_reassembler;
  lp::Sequence m_nextSeq; // initialized by constructor
};

Junxiao Shi wrote:

#define LP_MAX_FRAGMENTS = 1000;

This shall be a field in Options. 1000 can be the default.

I'd use a lower default... 200 or 400 seems sufficient for the normal cases. Very low MTU links can set the option to a higher value.

The startSeq is calculated by the LpReassembler by subtracting the FragIndex from the sequence number of the LpPacket. Since all fragments of a packet will have sequential sequence numbers, I believe this is a reliable way to determine the sequence number of the first fragment from any fragment of the packet.

bool addReceived(lp::Packet packet);

lp::Packet reassemble(lp::Sequence startSeq);

It is correct that EndpointId+startSeq can be used to uniquely identify a partial packet.
However, this API forces LinkService to understand how startSeq is computed, which is undesirable.

Yeah this is exactly what I meant.

An alternate is: std::tuple<bool, lp::Packet> receiveFragment(const lp::Packet& packet).

I had the same API in mind.

I think the design in note-13 is good enough, except that addReceived should be renamed to receiveFragment.

Implementation can start.
To reduce risk of getting rejected in code review, you may first upload:

• headers, including all methods and full Doxygen
• procedure of each method (written as comments)
• procedure of each test case (written as comments)