NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.5: NDN, CCN, CCNx, content centric networks
API Documentation
dead-nonce-list.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2014-2021, Regents of the University of California,
4  * Arizona Board of Regents,
5  * Colorado State University,
6  * University Pierre & Marie Curie, Sorbonne University,
7  * Washington University in St. Louis,
8  * Beijing Institute of Technology,
9  * The University of Memphis.
10  *
11  * This file is part of NFD (Named Data Networking Forwarding Daemon).
12  * See AUTHORS.md for complete list of NFD authors and contributors.
13  *
14  * NFD is free software: you can redistribute it and/or modify it under the terms
15  * of the GNU General Public License as published by the Free Software Foundation,
16  * either version 3 of the License, or (at your option) any later version.
17  *
18  * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
19  * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
20  * PURPOSE. See the GNU General Public License for more details.
21  *
22  * You should have received a copy of the GNU General Public License along with
23  * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
24  */
25 
26 #include "dead-nonce-list.hpp"
27 #include "common/city-hash.hpp"
28 #include "common/global.hpp"
29 #include "common/logger.hpp"
30 
31 namespace nfd {
32 
34 
37 const size_t DeadNonceList::INITIAL_CAPACITY;
38 const size_t DeadNonceList::MIN_CAPACITY;
39 const size_t DeadNonceList::MAX_CAPACITY;
40 const DeadNonceList::Entry DeadNonceList::MARK;
41 const size_t DeadNonceList::EXPECTED_MARK_COUNT;
42 const double DeadNonceList::CAPACITY_UP;
43 const double DeadNonceList::CAPACITY_DOWN;
44 const size_t DeadNonceList::EVICT_LIMIT;
45 
47  : m_lifetime(lifetime)
48  , m_capacity(INITIAL_CAPACITY)
49  , m_markInterval(m_lifetime / EXPECTED_MARK_COUNT)
50  , m_adjustCapacityInterval(m_lifetime)
51 {
52  if (m_lifetime < MIN_LIFETIME) {
53  NDN_THROW(std::invalid_argument("lifetime is less than MIN_LIFETIME"));
54  }
55 
56  for (size_t i = 0; i < EXPECTED_MARK_COUNT; ++i) {
57  m_queue.push_back(MARK);
58  }
59 
60  m_markEvent = getScheduler().schedule(m_markInterval, [this] { mark(); });
61  m_adjustCapacityEvent = getScheduler().schedule(m_adjustCapacityInterval, [this] { adjustCapacity(); });
62 
63  BOOST_ASSERT_MSG(DEFAULT_LIFETIME >= MIN_LIFETIME, "DEFAULT_LIFETIME is too small");
64  static_assert(INITIAL_CAPACITY >= MIN_CAPACITY, "INITIAL_CAPACITY is too small");
65  static_assert(INITIAL_CAPACITY <= MAX_CAPACITY, "INITIAL_CAPACITY is too large");
66  BOOST_ASSERT_MSG(static_cast<size_t>(MIN_CAPACITY * CAPACITY_UP) > MIN_CAPACITY,
67  "CAPACITY_UP must be able to increase from MIN_CAPACITY");
68  BOOST_ASSERT_MSG(static_cast<size_t>(MAX_CAPACITY * CAPACITY_DOWN) < MAX_CAPACITY,
69  "CAPACITY_DOWN must be able to decrease from MAX_CAPACITY");
70  BOOST_ASSERT_MSG(CAPACITY_UP > 1.0, "CAPACITY_UP must adjust up");
71  BOOST_ASSERT_MSG(CAPACITY_DOWN < 1.0, "CAPACITY_DOWN must adjust down");
72  static_assert(EVICT_LIMIT >= 1, "EVICT_LIMIT must be at least 1");
73 }
74 
75 size_t
77 {
78  return m_queue.size() - countMarks();
79 }
80 
81 bool
83 {
84  Entry entry = DeadNonceList::makeEntry(name, nonce);
85  return m_ht.find(entry) != m_ht.end();
86 }
87 
88 void
90 {
91  Entry entry = DeadNonceList::makeEntry(name, nonce);
92  const auto iter = m_ht.find(entry);
93  bool isDuplicate = iter != m_ht.end();
94 
95  NFD_LOG_TRACE("adding " << (isDuplicate ? "duplicate " : "") << name << " nonce=" << nonce);
96 
97  if (isDuplicate) {
98  m_queue.relocate(m_queue.end(), m_index.project<Queue>(iter));
99  }
100  else {
101  m_queue.push_back(entry);
102  evictEntries();
103  }
104 }
105 
106 DeadNonceList::Entry
107 DeadNonceList::makeEntry(const Name& name, Interest::Nonce nonce)
108 {
109  const auto& nameWire = name.wireEncode();
110  uint32_t n;
111  std::memcpy(&n, nonce.data(), sizeof(n));
112  return CityHash64WithSeed(reinterpret_cast<const char*>(nameWire.wire()), nameWire.size(), n);
113 }
114 
115 size_t
116 DeadNonceList::countMarks() const
117 {
118  return m_ht.count(MARK);
119 }
120 
121 void
122 DeadNonceList::mark()
123 {
124  m_queue.push_back(MARK);
125  size_t nMarks = countMarks();
126  m_actualMarkCounts.insert(nMarks);
127 
128  NFD_LOG_TRACE("mark nMarks=" << nMarks);
129 
130  m_markEvent = getScheduler().schedule(m_markInterval, [this] { mark(); });
131 }
132 
133 void
134 DeadNonceList::adjustCapacity()
135 {
136  auto oldCapacity = m_capacity;
137  auto equalRange = m_actualMarkCounts.equal_range(EXPECTED_MARK_COUNT);
138  if (equalRange.second == m_actualMarkCounts.begin()) {
139  // all counts are above expected count, adjust down
140  m_capacity = std::max(MIN_CAPACITY, static_cast<size_t>(m_capacity * CAPACITY_DOWN));
141  }
142  else if (equalRange.first == m_actualMarkCounts.end()) {
143  // all counts are below expected count, adjust up
144  m_capacity = std::min(MAX_CAPACITY, static_cast<size_t>(m_capacity * CAPACITY_UP));
145  }
146 
147  if (m_capacity != oldCapacity) {
148  NFD_LOG_TRACE("adjusting capacity " << oldCapacity << " -> " << m_capacity);
149  }
150 
151  m_actualMarkCounts.clear();
152  evictEntries();
153 
154  m_adjustCapacityEvent = getScheduler().schedule(m_adjustCapacityInterval, [this] { adjustCapacity(); });
155 }
156 
157 void
158 DeadNonceList::evictEntries()
159 {
160  if (m_queue.size() <= m_capacity) // not over capacity
161  return;
162 
163  auto nEvict = std::min(m_queue.size() - m_capacity, EVICT_LIMIT);
164  for (size_t i = 0; i < nEvict; i++) {
165  m_queue.pop_front();
166  }
167  BOOST_ASSERT(m_queue.size() >= m_capacity);
168 
169  NFD_LOG_TRACE("evicted=" << nEvict << " size=" << size() << " capacity=" << m_capacity);
170 }
171 
172 } // namespace nfd
Represents the Dead Nonce List.
#define NFD_LOG_INIT(name)
Definition: logger.hpp:31
static constexpr time::nanoseconds MIN_LIFETIME
Minimum entry lifetime.
DeadNonceList(time::nanoseconds lifetime=DEFAULT_LIFETIME)
Constructs the Dead Nonce List.
void add(const Name &name, Interest::Nonce nonce)
Adds name+nonce to the list.
#define NDN_THROW(e)
Definition: exception.hpp:61
Scheduler & getScheduler()
Returns the global Scheduler instance for the calling thread.
Definition: global.cpp:70
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-common.hpp:39
static constexpr time::nanoseconds DEFAULT_LIFETIME
Default entry lifetime.
#define NFD_LOG_TRACE
Definition: logger.hpp:37
bool has(const Name &name, Interest::Nonce nonce) const
Determines if name+nonce is in the list.
uint64 CityHash64WithSeed(const char *s, size_t len, uint64 seed)
Definition: city-hash.cpp:397
Represents an absolute name.
Definition: name.hpp:41
boost::multi_index_container< Policy::EntryRef, boost::multi_index::indexed_by< boost::multi_index::sequenced<>, boost::multi_index::ordered_unique< boost::multi_index::identity< Policy::EntryRef > > > > Queue
size_t size() const
Returns the number of stored nonces.
size_t wireEncode(EncodingImpl< TAG > &encoder) const
Fast encoding or block size estimation.
Definition: name.cpp:117
boost::chrono::nanoseconds nanoseconds
Definition: time.hpp:50