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-2019, 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 
35 const time::nanoseconds DeadNonceList::DEFAULT_LIFETIME = 6_s;
36 const time::nanoseconds DeadNonceList::MIN_LIFETIME = 1_ms;
37 const size_t DeadNonceList::INITIAL_CAPACITY = 1 << 7;
38 const size_t DeadNonceList::MIN_CAPACITY = 1 << 3;
39 const size_t DeadNonceList::MAX_CAPACITY = 1 << 24;
40 const DeadNonceList::Entry DeadNonceList::MARK = 0;
41 const size_t DeadNonceList::EXPECTED_MARK_COUNT = 5;
42 const double DeadNonceList::CAPACITY_UP = 1.2;
43 const double DeadNonceList::CAPACITY_DOWN = 0.9;
44 const size_t DeadNonceList::EVICT_LIMIT = 1 << 6;
45 
46 DeadNonceList::DeadNonceList(time::nanoseconds lifetime)
47  : m_lifetime(lifetime)
48  , m_queue(m_index.get<0>())
49  , m_ht(m_index.get<1>())
50  , m_capacity(INITIAL_CAPACITY)
51  , m_markInterval(m_lifetime / EXPECTED_MARK_COUNT)
52  , m_adjustCapacityInterval(m_lifetime)
53 {
54  if (m_lifetime < MIN_LIFETIME) {
55  NDN_THROW(std::invalid_argument("lifetime is less than MIN_LIFETIME"));
56  }
57 
58  for (size_t i = 0; i < EXPECTED_MARK_COUNT; ++i) {
59  m_queue.push_back(MARK);
60  }
61 
62  m_markEvent = getScheduler().schedule(m_markInterval, [this] { mark(); });
63  m_adjustCapacityEvent = getScheduler().schedule(m_adjustCapacityInterval, [this] { adjustCapacity(); });
64 }
65 
67 {
68  m_markEvent.cancel();
69  m_adjustCapacityEvent.cancel();
70 
71  BOOST_ASSERT_MSG(DEFAULT_LIFETIME >= MIN_LIFETIME, "DEFAULT_LIFETIME is too small");
72  static_assert(INITIAL_CAPACITY >= MIN_CAPACITY, "INITIAL_CAPACITY is too small");
73  static_assert(INITIAL_CAPACITY <= MAX_CAPACITY, "INITIAL_CAPACITY is too large");
74  BOOST_ASSERT_MSG(static_cast<size_t>(MIN_CAPACITY * CAPACITY_UP) > MIN_CAPACITY,
75  "CAPACITY_UP must be able to increase from MIN_CAPACITY");
76  BOOST_ASSERT_MSG(static_cast<size_t>(MAX_CAPACITY * CAPACITY_DOWN) < MAX_CAPACITY,
77  "CAPACITY_DOWN must be able to decrease from MAX_CAPACITY");
78  BOOST_ASSERT_MSG(CAPACITY_UP > 1.0, "CAPACITY_UP must adjust up");
79  BOOST_ASSERT_MSG(CAPACITY_DOWN < 1.0, "CAPACITY_DOWN must adjust down");
80  static_assert(EVICT_LIMIT >= 1, "EVICT_LIMIT must be at least 1");
81 }
82 
83 size_t
85 {
86  return m_queue.size() - this->countMarks();
87 }
88 
89 bool
90 DeadNonceList::has(const Name& name, uint32_t nonce) const
91 {
92  Entry entry = DeadNonceList::makeEntry(name, nonce);
93  return m_ht.find(entry) != m_ht.end();
94 }
95 
96 void
97 DeadNonceList::add(const Name& name, uint32_t nonce)
98 {
99  Entry entry = DeadNonceList::makeEntry(name, nonce);
100  m_queue.push_back(entry);
101 
102  this->evictEntries();
103 }
104 
105 DeadNonceList::Entry
106 DeadNonceList::makeEntry(const Name& name, uint32_t nonce)
107 {
108  Block nameWire = name.wireEncode();
109  return CityHash64WithSeed(reinterpret_cast<const char*>(nameWire.wire()), nameWire.size(),
110  static_cast<uint64_t>(nonce));
111 }
112 
113 size_t
114 DeadNonceList::countMarks() const
115 {
116  return m_ht.count(MARK);
117 }
118 
119 void
120 DeadNonceList::mark()
121 {
122  m_queue.push_back(MARK);
123  size_t nMarks = this->countMarks();
124  m_actualMarkCounts.insert(nMarks);
125 
126  NFD_LOG_TRACE("mark nMarks=" << nMarks);
127 
128  m_markEvent = getScheduler().schedule(m_markInterval, [this] { mark(); });
129 }
130 
131 void
132 DeadNonceList::adjustCapacity()
133 {
134  auto equalRange = m_actualMarkCounts.equal_range(EXPECTED_MARK_COUNT);
135  if (equalRange.second == m_actualMarkCounts.begin()) {
136  // all counts are above expected count, adjust down
137  m_capacity = std::max(MIN_CAPACITY, static_cast<size_t>(m_capacity * CAPACITY_DOWN));
138  NFD_LOG_TRACE("adjustCapacity DOWN capacity=" << m_capacity);
139  }
140  else if (equalRange.first == m_actualMarkCounts.end()) {
141  // all counts are below expected count, adjust up
142  m_capacity = std::min(MAX_CAPACITY, static_cast<size_t>(m_capacity * CAPACITY_UP));
143  NFD_LOG_TRACE("adjustCapacity UP capacity=" << m_capacity);
144  }
145 
146  m_actualMarkCounts.clear();
147  this->evictEntries();
148 
149  m_adjustCapacityEvent = getScheduler().schedule(m_adjustCapacityInterval, [this] { adjustCapacity(); });
150 }
151 
152 void
153 DeadNonceList::evictEntries()
154 {
155  ssize_t nOverCapacity = m_queue.size() - m_capacity;
156  if (nOverCapacity <= 0) // not over capacity
157  return;
158 
159  for (ssize_t nEvict = std::min<ssize_t>(nOverCapacity, EVICT_LIMIT); nEvict > 0; --nEvict) {
160  m_queue.erase(m_queue.begin());
161  }
162  BOOST_ASSERT(m_queue.size() >= m_capacity);
163 }
164 
165 } // namespace nfd
NFD_LOG_TRACE
#define NFD_LOG_TRACE
Definition: logger.hpp:37
global.hpp
nfd::DeadNonceList::size
size_t size() const
Definition: dead-nonce-list.cpp:84
nonstd::variants::get
R & get(variant< T0, T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15 > &v, nonstd_lite_in_place_type_t(R)=nonstd_lite_in_place_type(R))
Definition: variant.hpp:1753
nfd::DeadNonceList::DEFAULT_LIFETIME
static const time::nanoseconds DEFAULT_LIFETIME
Default entry lifetime.
Definition: dead-nonce-list.hpp:139
nfd::DeadNonceList::DeadNonceList
DeadNonceList(time::nanoseconds lifetime=DEFAULT_LIFETIME)
Constructs the Dead Nonce List.
Definition: dead-nonce-list.cpp:46
ndn::detail::CancelHandle::cancel
void cancel() const
Cancel the operation.
Definition: cancel-handle.cpp:28
nfd::DeadNonceList::add
void add(const Name &name, uint32_t nonce)
Records name+nonce.
Definition: dead-nonce-list.cpp:97
ndn::Name
Represents an absolute name.
Definition: name.hpp:44
nfd::DeadNonceList::~DeadNonceList
~DeadNonceList()
Definition: dead-nonce-list.cpp:66
nfd
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-common.hpp:40
city-hash.hpp
NDN_THROW
#define NDN_THROW(e)
Definition: exception.hpp:61
nfd::getScheduler
Scheduler & getScheduler()
Returns the global Scheduler instance for the calling thread.
Definition: global.cpp:70
nfd::DeadNonceList
Represents the Dead Nonce List.
Definition: dead-nonce-list.hpp:55
dead-nonce-list.hpp
ndn::Block
Represents a TLV element of NDN packet format.
Definition: block.hpp:43
ndn::Block::size
size_t size() const
Return the size of the encoded wire, i.e.
Definition: block.cpp:290
ndn::name
Definition: name-component-types.hpp:33
CityHash64WithSeed
uint64 CityHash64WithSeed(const char *s, size_t len, uint64 seed)
Definition: city-hash.cpp:397
nfd::DeadNonceList::MIN_LIFETIME
static const time::nanoseconds MIN_LIFETIME
Minimum entry lifetime.
Definition: dead-nonce-list.hpp:141
ndn::Block::wire
const uint8_t * wire() const
Return a raw pointer to the beginning of the encoded wire.
Definition: block.cpp:281
nfd::DeadNonceList::has
bool has(const Name &name, uint32_t nonce) const
Determines if name+nonce exists.
Definition: dead-nonce-list.cpp:90
NFD_LOG_INIT
#define NFD_LOG_INIT(name)
Definition: logger.hpp:31
logger.hpp