NFD

I saw some code submissions in http://gerrit.named-data.net/1868. However, there isn't an approved design for this issue.

Please first submit a design document/slides for review. Upload this document as attachment on Redmine.

I agree with moving the "query Entry" and operator< to Entry base type and make the EntryImpl have some generic fields similar to StrategyInfoHost. If we move these two into the base type, why not move the canStale and unsetUnsolicited operations into Entry base type as these operations should be used for all the Entries?

• not all cache items may need to be cached. The current assumption
  that policy is striclty "replacement" should be related. There are
  many useful use-cases that policy should be "placement" (i.e.,
  determine whether to cache item in the first place)

  For example, onInsert method should return true/false to indicate
  whether item actually inserted or not.

• "evictPick" is very weird name to be used in policy. I prefer a more
  verbose variant that helps understanding what the method is
  doing. For example:

   pickItemForEviction
  

• I missed before that Cs::evictPick() returns a tuple of
  std::tuple<TableIt, std::string>, where the second parameter is
  purely for log purposes. This is not acceptable, as there is
  creation of std::string() upon every single eviction event, even
  when debug logging is not enabled.

  Log statement needs to be moved to the policy. When list-based
  chaining policy is used (see below), a similar log can be displayed
  without the need of introducing extra overhead.

• Cs::evictPick should be removed

• Obscure TableIt should be renamed to Cs::iterator or something like that

• policy should allow chaining.

  • inheritance-based chaining (good, but more complex and requires compile-time changes)
  • list-based chaining (also good and simplifies maintenance)
    • Each policy is strictly independent and manages its own queues.
    • Only one policy (at a time) holds on to the CS item

Here are some implementation ideas for list-based chaining.

...

// insert()
bool isPolicyInserted = false;
for (auto& policy : m_policies) {
  if (!isNewEntry) {
    if (policy->onUpdate(it))
      break;
  }
  else {
    isPolicyInserted = policy->onInsert(it);
    if (isPolicyInserted)
      break;
  }
}

if (!isPolicyInserted) {
  m_table.erase(it);
}

...

// evict()
while (this->size() > m_limit) {
  for (auto& policy : m_policies) {
    TableIt it = policy->evict(m_table.end()); // should call onErase internally
    if (it != m_table.end()) {
      NFD_LOG_DEBUG("evict " << it->getName() << " from " << policy->getName());
      m_table.erase();
    }
  }
}  

I'm assuming that we will implement:

• UnsolicitedFifo
• StaleFifo
• Fifo (with internal pointer to StaleFifo to move items there after they become stale)
• Lru (with internal pointer to StaleFifo to move items there after they become stale)

The problems that I can think of:

• don't know how to move from UnsolicitedFifo to other queues
• reimplementation needed, if we want to have UnsolicitedLru/StaleLru

I think there's some misunderstanding in note-16.
There shouldn't be multiple active policies: it increases complexity significantly.

My vision is to have a policy interface that is functionally same as ndnSIM 1.0. Specifically:

• There is only one active policy.
  Code repository can have multiple alternate policies for different network environments (eg. end host vs router), but which policy to use is a choice in configuration.
• There are two indexes:
  • An index by Name is maintained in ContentStore, and is used for lookups.
  • Another index is maintained in the policy, and is used for cleanups.
• ContentStore capacity is controlled by the policy. The policy can decide not to insert an entry, and can decide to evict entries.

What I tried to show examples in note-16 doesn't contradict the goals you mentioned. It is just the way policy is constructed can be different from ndnSIM 1.0: in 1.0 I used inheritance as a way to combine sub-policies and I feel that it is not too convenient. "List" of policies is just a way to construct a specific policy. This list can also be internal to a specific policy...

I think it's better that ContentStore capacity is controlled by the CS class not the Policy. For example, when we need to change the policy, we need to get the capacity and pass it to the Policy. So if we use CS to control the capacity, we don't need to pass this to the Policy...

note-16 is just the way policy is constructed can be different from ndnSIM 1.0: in 1.0 I used inheritance as a way to combine sub-policies and I feel that it is not too convenient. "List" of policies is just a way to construct a specific policy. This list can also be internal to a specific policy...

Yes, there could be a 'ListPolicy' that combines multiple policies. But ContentStore should see only one policy.

'ListPolicy' is out of scope of this issue.

I think it's better that ContentStore capacity is controlled by the CS class not the Policy. For example, when we need to change the policy, we need to get the capacity and pass it to the Policy. So if we use CS to control the capacity, we don't need to pass this to the Policy...

No. Capacity is an attribute of the policy, because policy is the only component that should take care of cleanups.

I looked at the cs::Policy API design in commit:c0595655da34b8ddd868cd2c4c58dbaf0218b955.

Design comments:

• Method names "onX" are confusing. It's better to indicate either "beforeX" or "afterX".
• public virtual methods should be avoided, before they have the dual role of public API and internal implementation. Instead, declare private virtual methods, and invoke them from public non-virtual methods.
• setLimit is not general enough. The policy base class can have a "hard limit". Policy implementations can have other limits. For example, a policy may define a "soft limit", once exceeded, would start evicting packets from local producers but still accept packets from remote hosts.
• onInsert shouldn't return boolean. Not accepting a new entry is simply expressed as immediately evicting this entry.
• pickItemForEviction shouldn't be exposed. It's policy's responsibility to keep CS size under hard limit. CS size can go over limit after insertion or after changing limit, and the policy can inform CS to erase entries with a signal.

I suggest the following public API:

class Policy : noncopyable
{
public:
  /** \brief gets hard limit (in number of entries)
   */
  size_t
  getHardLimit() const;

  /** \brief sets hard limit (in number of entries)
   *  \post getHardLimit() == nMaxEntries
   *  \post cs.size() <= getHardLimit()
   *
   *  The policy may evict entries if necessary.
   */
  void
  setHardLimit(size_t nMaxEntries);

  /** \brief emits when an entry is being evicted
   *
   *  CS should erase the entry upon signal emission.
   */
  signal::signal<Policy, iterator> beforeEvict;

  /** \brief invoked by CS after an entry is inserted
   *  \post cs.size() <= getHardLimit()
   *
   *  The policy may evict entries if necessary.
   *  During this process, \p i might be evicted.
   */
  void
  afterInsert(iterator i);

  /** \brief invoked by CS before an entry is erased due to management command
   *  \warning CS must not invoke this method if an entry is erased due to eviction.
   */
  void
  beforeErase(iterator i);

  /** \brief invoked by CS before an entry is used to match a lookup
   *
   *  The policy may witness this usage to make better eviction decisions in the future.
   */
  void
  beforeUse(iterator i);
};

Since this is a complex Feature, I suggest the assignee to upload only headers (including protected and private parts) for review, and write implementation code after headers are reviewed.

I don't think I agree with two of the comments

• setLimit is not general enough. The policy base class can have a "hard limit". Policy implementations can have other limits. For example, a policy may define a "soft limit", once exceeded, would start evicting packets from local producers but still accept packets from remote hosts.

This is an implementation detail. I do not think this detail should be defined in the policy interface.

• onInsert shouldn't return boolean. Not accepting a new entry is simply expressed as immediately evicting this entry.

Why? If item is not inserted, it should indicate directly that it will not be inserted.

• setLimit is not general enough. The policy base class can have a "hard limit". Policy implementations can have other limits. For example, a policy may define a "soft limit", once exceeded, would start evicting packets from local producers but still accept packets from remote hosts.

This is an implementation detail. I do not think this detail should be defined in the policy interface.

I could accept keeping the name as setLimit, but the semantics is still "hard limit" and should be indicated in Doxygen description.

• onInsert shouldn't return boolean. Not accepting a new entry is simply expressed as immediately evicting this entry.

Why? If item is not inserted, it should indicate directly that it will not be inserted.

afterInsert (formerly onInsert) takes iterator parameter type, which can be obtained only after an entry is created and inserted into the lookup index.

To undo this insertion is same as to evict this entry.
afterEvict signal would cause CS to erase this entry from the lookup index.
There would be additional complexity if (1) policy must avoid emitting afterEvict signal for this entry (2) CS must look at afterInsert return value and do the same thing as what it does for afterEvict.

I could accept keeping the name as setLimit, but the semantics is still "hard limit" and should be indicated in Doxygen description.

That is ok with me.

afterInsert (formerly onInsert) takes iterator parameter type, which can be obtained only after an entry is created and inserted into the lookup index.

To undo this insertion is same as to evict this entry.
afterEvict signal would cause CS to erase this entry from the lookup index.
There would be additional complexity if (1) policy must avoid emitting afterEvict signal for this entry (2) CS must look at afterInsert return value and do the same thing as what it does for afterEvict.

I'm still not 100% convinced. I understand that it is necessary to insert entry first into the underlying container before doing anything else. However, I do not clearly see why not creating signal "afterEvict" when entry wasn't actually inserted would complicate processing. In any case, I am not going to insist on this, just want to make a statement that this looks a little bit weird to me.

I do not clearly see why not creating signal "afterEvict" when entry wasn't actually inserted would complicate processing.

When *after*Insert is invoked, the entry is already inserted.

There is no such thing that an "entry wasn't actually inserted".

Suppose the policy concludes that the inserted entry should be evicted immediately, its choices are:

• In DESIGN-A and DESIGN-C, either Policy or ContentStore must use a conditional to check whether the entry is newest entry.
• DESIGN-B is basically same as DESIGN-D, because the 'false' return value is ignored.

DESIGN-D as proposed in note-24 is the simplest, because:

• Unlike DESIGN-A or DESIGN-C, no conditional is needed in either Policy or ContentStore.
• The processing of erasing the newest entry or any older entry is exactly the same on ContentStore side. Recall that this doesn't involve timers because all timers should be inside Policy.

Current CS is able to distinguish whether a Data is unsolicited, and differs eviction decisions upon that.

The acceptance of unsolicited Data is to be dropped in #2181, so the Policy design does not take this into consideration.

In order to seamlessly port existing "priority FIFO" policy to be used before #2181 closes, but also avoid polluting Policy API with unsolicited parameter, the suggestion is:

• Policy API should not have unsolicited parameter.
• CS API remained unchanged in #1207.
• CS entry can have fields to indicate whether Data is unsolicited. The "priority FIFO" policy may inspect those fields.

#2181 is about unsolicited data from local apps. What about unsolicited data received from other nodes? As far as I know, the vehicular networking applications rely heavily on nodes caching unsolicited data.

Lan Wang wrote:

As far as I know, the vehicular networking applications rely heavily on nodes caching unsolicited data.

Correct. We don't want to lose the ability of (optionally) caching unsolicited data coming from other nodes.

#2181 is about unsolicited data from local apps. What about unsolicited data received from other nodes? As far as I know, the vehicular networking applications rely heavily on nodes caching unsolicited data.

This makes sense. I've noted this in #2181 note-8.

But still, policy API doesn't need an unsolicited parameter. CS entry has an unsolicited field and policy implementations can peek it.

Because when setLimit() or afterInsert(iterator i) called, it needs to make sure that cs.size() <= getLimit(). Somehow policy needs to know size of CS.

I think there are two options to have the size of CS.

1. pass the cs reference to the policy(in the constructor Policy(const Name& name, const Cs& cs)
   or has a function setCs(const Cs& cs))

2. policy has a function virtual size_t size() = 0 to return the entries it has got.

So which one do you think is better?

Not every policy needs to index ContentStore entries. For example, the "random eviction" policy doesn't need its own index.

Therefore, .setCs(const Cs* cs) is a good solution.

Having a setter (rather than a constructor parameter) makes it easier to create policy instances, but policy code that needs to access CS would need BOOST_ASSERT(m_cs != nullptr).