Represents the Dead Nonce List. More...

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

bool	has (const Name &name, Interest::Nonce nonce) const
	Determines if name+nonce is in the list. More...

void	add (const Name &name, Interest::Nonce nonce)
	Adds name+nonce to the list. More...

size_t	size () const
	Returns the number of stored nonces. More...

time::nanoseconds	getLifetime () const
	Returns the expected nonce lifetime. 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 54 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

lifetime expected 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_argument if lifetime is less than MIN_LIFETIME

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

References DEFAULT_LIFETIME, nfd::getScheduler(), MIN_LIFETIME, and NDN_THROW.

Member Function Documentation

◆ 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 82 of file dead-nonce-list.cpp.

Referenced by nfd::Forwarder::Forwarder().

◆ add()

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

Adds name+nonce to the list.

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

References CityHash64WithSeed(), nfd::getScheduler(), NFD_LOG_TRACE, size(), and ndn::Name::wireEncode().

Referenced by nfd::Forwarder::onNewNextHop().

◆ 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 76 of file dead-nonce-list.cpp.

Referenced by add().

◆ getLifetime()

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

inline

Returns the expected nonce lifetime.

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

Referenced by nfd::Forwarder::onNewNextHop().

Member Data Documentation

◆ DEFAULT_LIFETIME

const time::nanoseconds nfd::DeadNonceList::DEFAULT_LIFETIME = 6_s

static

Default entry lifetime.

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

Referenced by DeadNonceList().

◆ MIN_LIFETIME

const time::nanoseconds nfd::DeadNonceList::MIN_LIFETIME = 50_ms