nfd::DeadNonceList Class Reference

Represents the Dead Nonce List. More...

#include <daemon/table/dead-nonce-list.hpp>

+ Inheritance diagram for nfd::DeadNonceList:
+ Collaboration diagram for nfd::DeadNonceList:

Public Member Functions

 DeadNonceList (time::nanoseconds lifetime=DEFAULT_LIFETIME)
 Constructs the Dead Nonce List. More...
 
void add (const Name &name, Interest::Nonce nonce)
 Adds name+nonce to the list. More...
 
time::nanoseconds getLifetime () const
 Returns the expected nonce lifetime. More...
 
bool has (const Name &name, Interest::Nonce nonce) const
 Determines if name+nonce is in the list. More...
 
size_t size () const
 Returns the number of stored nonces. More...
 

Static Public Attributes

static constexpr time::nanoseconds DEFAULT_LIFETIME = 6_s
 Default entry lifetime. More...
 
static constexpr time::nanoseconds MIN_LIFETIME = 50_ms
 Minimum entry lifetime. More...
 

Detailed Description

Represents the Dead Nonce List.

The Dead Nonce List is a global table that supplements the PIT for loop detection. When a Nonce is erased (dead) from a PIT entry, the Nonce and the Interest Name are added to the Dead Nonce List and kept for a duration in which most loops are expected to have occured.

To reduce memory usage, the Interest Name and Nonce are stored as a 64-bit hash. The probability of false positives (a non-looping Interest considered as looping) is small and a collision is recoverable when the consumer retransmits with a different Nonce.

To reduce memory usage, entries do not have associated timestamps. Instead, the lifetime of the entries is controlled by dynamically adjusting the capacity of the container. At fixed intervals, a MARK (an entry with a special value) is inserted into the container. The number of MARKs stored in the container reflects the lifetime of the entries, because MARKs are inserted at fixed intervals.

Definition at line 56 of file dead-nonce-list.hpp.

Constructor & Destructor Documentation

◆ DeadNonceList()

nfd::DeadNonceList::DeadNonceList ( time::nanoseconds  lifetime = DEFAULT_LIFETIME)
explicit

Constructs the Dead Nonce List.

Parameters
lifetimeexpected lifetime of each nonce, must be no less than MIN_LIFETIME. This should be set to a duration over which most loops would have occured. A loop cannot be detected if the total delay of the cycle is greater than lifetime.
Exceptions
std::invalid_argumentif lifetime is less than MIN_LIFETIME

Definition at line 35 of file dead-nonce-list.cpp.

Member Function Documentation

◆ add()

void nfd::DeadNonceList::add ( const Name &  name,
Interest::Nonce  nonce 
)

Adds name+nonce to the list.

Definition at line 78 of file dead-nonce-list.cpp.

◆ getLifetime()

time::nanoseconds nfd::DeadNonceList::getLifetime ( ) const
inline

Returns the expected nonce lifetime.

Definition at line 93 of file dead-nonce-list.hpp.

◆ has()

bool nfd::DeadNonceList::has ( const Name &  name,
Interest::Nonce  nonce 
) const

Determines if name+nonce is in the list.

Returns
true if name+nonce exists, false otherwise

Definition at line 71 of file dead-nonce-list.cpp.

◆ size()

size_t nfd::DeadNonceList::size ( ) const

Returns the number of stored nonces.

Note
The return value does not contain non-Nonce entries in the index, if any.

Definition at line 65 of file dead-nonce-list.cpp.

Member Data Documentation

◆ DEFAULT_LIFETIME

constexpr time::nanoseconds nfd::DeadNonceList::DEFAULT_LIFETIME = 6_s
staticconstexpr

Default entry lifetime.

Definition at line 129 of file dead-nonce-list.hpp.

◆ MIN_LIFETIME

constexpr time::nanoseconds nfd::DeadNonceList::MIN_LIFETIME = 50_ms
staticconstexpr

Minimum entry lifetime.

Definition at line 131 of file dead-nonce-list.hpp.