Project

General

Profile

Actions

Bug #1953

closed

Persistent loop with short InterestLifetime (DeadNonceList)

Added by Junxiao Shi over 9 years ago. Updated over 2 years ago.

Status:
Closed
Priority:
Normal
Assignee:
Category:
Forwarding
Target version:
Start date:
Due date:
% Done:

100%

Estimated time:
18.00 h

Description

Topology:

A-------B
 \     /
  --C--

Each link has 50ms delay.

Steps to reproduce:

  1. on A, install a Route /P toward B
  2. on B, install a Route /P toward C
  3. on C, install a Route /P toward A
  4. on A, send an Interest /P/1 with InterestLifetime=100ms

Expected: Interest does not loop

Actual: Interest loops forever

Root cause: a packet needs 150ms going through the cycle A-B-C-A, but unsatisfy timer deletes the PIT entry after 100ms


Files

dead-nonce-list_20140919.pptx (58.5 KB) dead-nonce-list_20140919.pptx Junxiao Shi, 09/20/2014 09:39 AM
dead-nonce-list_20141004.pptx (58.7 KB) dead-nonce-list_20141004.pptx Junxiao Shi, 10/04/2014 02:51 PM

Related issues 1 (0 open1 closed)

Related to NFD - Task #1782: Redesign loop detection in PIT entryClosedJunxiao Shi

Actions
Actions #1

Updated by Junxiao Shi over 9 years ago

  • Subject changed from Interest loop with low InterestLifetime to Persistent loop with short InterestLifetime

20140829 conference call discussed this problem.

An obvious solution is to impose a minimum InterestLifetime, or to ensure unsatisfy timer is set to be longer than the longest cycle in the system.

However, this solution can't solve all problems:

  • it's non-trivial to calculate what's the longest cycle in a network, especially when it contains laptops from everywhere
  • retaining PIT entries for a long time (eg. 10 seconds) consumes a lot of memory

One other option is changing the packet format to include a TTL, but this is not ideal.

Actions #2

Updated by Lan Wang over 9 years ago

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.

Actions #3

Updated by Junxiao Shi over 9 years ago

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.
Actions #4

Updated by Junxiao Shi over 9 years ago

  • Related to Task #1782: Redesign loop detection in PIT entry added
Actions #5

Updated by Junxiao Shi over 9 years ago

See dead-nonce-list_20140919.pptx for a design based on dead Nonce list.

Actions #6

Updated by Junxiao Shi over 9 years ago

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.

Actions #7

Updated by Lan Wang over 9 years ago

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.

Actions #8

Updated by Junxiao Shi over 9 years ago

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.

Actions #9

Updated by Lan Wang over 9 years ago

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).

Actions #10

Updated by Junxiao Shi over 9 years ago

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

Actions #11

Updated by Alex Afanasyev over 9 years ago

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...

Actions #12

Updated by Junxiao Shi over 9 years ago

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.

Actions #13

Updated by Alex Afanasyev over 9 years ago

ok.

Actions #14

Updated by Junxiao Shi over 9 years ago

  • % Done changed from 0 to 10
  • Estimated time changed from 18.00 h to 12.00 h

The implementation plan is:

  1. Implement Dead Nonce List data structure. I'll use either std::queue+std::map or boost::multi_index_container.
  2. Change forwarding pipelines to make use of Dead Nonce List.
  3. Update Developer Guide.
Actions #15

Updated by Lan Wang over 9 years ago

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.

Actions #16

Updated by Junxiao Shi over 9 years ago

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.

Actions #17

Updated by Junxiao Shi over 9 years ago

Change-Id: I65eb2346716dd47bcf1850c832e37e5354042fd0 implements the dead Nonce list data structure.
It's not yet used by forwarding.

In addition to tasks described in note-14, we also need: change PIT entry to store one Nonce per in-record and out-record, and eliminate PIT Nonce list.

Actions #18

Updated by Junxiao Shi over 9 years ago

  • % Done changed from 40 to 50

It appears that PIT entry already has per-InRecord/OutRecord Nonce field. Therefore I'll go straight to pipeline changes.

Actions #19

Updated by Junxiao Shi over 9 years ago

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.

Actions #20

Updated by Junxiao Shi over 9 years ago

  • % Done changed from 50 to 80

Code is in: Change-Id: I0faef2a985b03fe96387c2e0181588713550b9ce

Next is to update Developer Guide.

Actions #21

Updated by Junxiao Shi over 9 years ago

  • % Done changed from 80 to 90

NFD Developer Guide is updated to describe Dead Nonce List.

I still need to update Forwarding section.

Actions #22

Updated by Junxiao Shi over 9 years ago

  • Status changed from In Progress to Closed
  • % Done changed from 90 to 100

Forwarding section of Developer Guide is updated.

Actions #23

Updated by Junxiao Shi over 2 years ago

  • Tags set to DeadNonceList
Actions #24

Updated by Junxiao Shi over 2 years ago

  • Subject changed from Persistent loop with short InterestLifetime to Persistent loop with short InterestLifetime (DeadNonceList)
Actions

Also available in: Atom PDF