NFD

ccnx has a nonce list to catch the loops. This list can keep the nonce longer than the PIT entry (the PIT entry can be removed when Interest expires). It may be less overhead than keeping the PIT entry.

CCNx protocol defines that Nonce is used to improve the efficiency of loop detection, and does not clearly define the granularity of Nonce comparison.

ccnd has a global Nonce table for loop detection.
Nonce is retained for 6 seconds since Interest arrival.

Having a global Nonce table implies that Nonces can be compared across all Interest passing through ccnd, instead of just those Interests with same Name and Selectors.

CCNx protocol defines Nonce as a BLOB of any length.

ccnd generates 6-octet Nonces.

Applications are permitted (but not recommended) to generate Nonces, which may have a different length.

NDN-TLV protocol requires combination of Name and Nonce to be unique, and Nonce is 4 octets.

If NFD adopts global Nonce table, NFD would require Nonce to be unique (instead of the combination of Name and Nonce).
Principle 3 "relax system requirements" does not apply here, because NDN-TLV Nonce is 4 octets (instead of ccnd's 6 octets), so that the probability of having a collision is much higher.

One option is to design a backup Nonce table:

• The backup Nonce table stores the combination of (Name,Nonce) after PIT entry is deleted.
  • Name is stored as a 32-bit hash; the actual Name is not stored.
  • Every entry is retained for 6 seconds.
  • A small number of expired entries are cleaned out upon each access (same as ccnd nonce_ok).
  • Each entry is 16 octets (4 octets for Name hash, 4 octets for Nonce, 8 octets from expiration time). Memory usage is 768K for 8000 Interests/s rate.
• When a PIT entry is deleted, all Nonces recorded in the PIT entry are inserted to the backup Nonce table.
  • This should happen regardless of whether PIT entry is satisfied, or expired without being satisfied. Interest for a satisfied PIT entry are usually returned with cached Data, but this is not guaranteed because FreshnessPeriod can be very short.
• To detect incoming Interest loop, both PIT entry and backup Nonce table should be consulted.
  • The backup Nonce table lookup is necessary even if there is a PIT entry, because the PIT entry could be created by a non-looped Interest from another downstream, but the incoming Interest is looped.

One small comment: instead of holding nonce for 6sec, one can cheat with a simpler implementation of a fixed size fifo ring, with the assumption of not too many looping interests at any given time

The intention is to keep every Nonce for 6 seconds. The optimal size of dead Nonce list depends on traffic volume.

A fixed size from compile-time constant cannot fit every network scenario.

A fixed size from configuration file cannot fit dynamically changing traffic, and the operator still needs to calculate the optimal size.

Adding a timestamp to each entry can ensure every Nonce is kept for exactly 6 second, but there's storage overhead.

Therefore, the design uses "time markers" to periodically adjust the size of dead Nonce list, so that it approximately keeps every Nonce for 6 seconds.

Looks good to me except one detail. The name hash is 4 bytes and if you use a cheap hash, then a collision on a high-speed link may not be negligible. Now the question is how random the nonces are? If not, maybe concatenating the name and nonce and do a hash of 8 bytes may be better.

I don't think collision of (Name hash, Nonce) is likely.
The recommendation is to generate Nonce with a non cryptographic secure random number generator.
Such RNG is still able to produce non-predictable random numbers.

Statistically speaking, H(Name Nonce) vs (H(Name), Nonce) have the same probability of collision.

Comparing these two, H(Name Nonce) MAY be more expensive to compute, because some hash functions can only take a single block.

If nonces are randomly generated, then that's fine. But it may or may not be done in practice (all depends on the library implementation at the consumer end).

Please list libraries that do not generate Nonce as random number.

Ok in general, but I don't agree with unnecessary complications by handling various special cases. This achieves nothing, but just complicates all logic and raises bunch of questions.

I would suggest simply adding nonces to the global dead nonce list whenever PIT is removed...

Alex Afanasyev wrote:

Ok in general, but I don't agree with unnecessary complications by handling various special cases. This achieves nothing, but just complicates all logic and raises bunch of questions.

I would suggest simply adding nonces to the global dead nonce list whenever PIT is removed...

Does "various special cases" refer to the following?

If a Data satisfies a PIT entry and is admitted to the ContentStore, looping Interests can be satisfied by cached Data if:

• Interest doesn't have MustBeFresh=yes selector, OR
• Data FreshnessPeriod is long enough to cover delay of a cycle

We can take chances by not inserting Nonces from such a PIT entry.

This optimization is important because the majority of PIT entries can satisfy this condition, so that Dead Nonce List can be kept small.

ok.

Reply to Note 10: I wasn't talking about a specific library. What I meant is that if there's a library that doesn't generate nonces randomly, then there might be a problem for your approach. The only requirement for a (name, nonce) pair is to be unique. Whether the nonce is random or not is up to the library implementation. In any case, if others don't think this is a problem, I won't further pursue this issue. Just want to document the potential problem here.

Lan Wang wrote:

The only requirement for a (name, nonce) pair is to be unique. Whether the nonce is random or not is up to the library implementation.

I think I should define the entry in Dead Nonce List to be F(Name, Nonce) where F is a function that returns a 64-bit integer that is representative of Name and Nonce.

The implementation could use CityHash64WithSeed.

The design introduces a new Interest finalize pipeline which is used in place of PIT delete algorithm.

It invokes Dead Nonce List insert algorithm if needed, and then goes to PIT delete.

During implementation I found a design problem:

1. incoming Data pipeline deletes the OutRecord of the upstream face.
2. Interest finalize pipeline may need the Nonce recorded in that OutRecord, if Interest has MustBeFresh=yes and Data FreshnessPeriod is short.

I'm thinking about a solution.