NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.5: NDN, CCN, CCNx, content centric networks
API Documentation
dead-nonce-list.hpp
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 #ifndef NFD_DAEMON_TABLE_DEAD_NONCE_LIST_HPP
27 #define NFD_DAEMON_TABLE_DEAD_NONCE_LIST_HPP
28 
29 #include "core/common.hpp"
30 
31 #include <boost/multi_index_container.hpp>
32 #include <boost/multi_index/hashed_index.hpp>
33 #include <boost/multi_index/sequenced_index.hpp>
34 
35 namespace nfd {
36 
54 class DeadNonceList : noncopyable
55 {
56 public:
64  explicit
66 
71  bool
72  has(const Name& name, Interest::Nonce nonce) const;
73 
77  void
78  add(const Name& name, Interest::Nonce nonce);
79 
84  size_t
85  size() const;
86 
91  getLifetime() const
92  {
93  return m_lifetime;
94  }
95 
96 private:
97  using Entry = uint64_t;
98 
99  static Entry
100  makeEntry(const Name& name, Interest::Nonce nonce);
101 
104  size_t
105  countMarks() const;
106 
109  void
110  mark();
111 
117  void
118  adjustCapacity();
119 
122  void
123  evictEntries();
124 
125 public:
127  static constexpr time::nanoseconds DEFAULT_LIFETIME = 6_s;
129  static constexpr time::nanoseconds MIN_LIFETIME = 50_ms;
130 
131 private:
132  const time::nanoseconds m_lifetime;
133 
134  struct Queue {};
135  struct Hashtable {};
136  using Container = boost::multi_index_container<
137  Entry,
138  boost::multi_index::indexed_by<
139  boost::multi_index::sequenced<boost::multi_index::tag<Queue>>,
140  boost::multi_index::hashed_non_unique<boost::multi_index::tag<Hashtable>,
141  boost::multi_index::identity<Entry>>
142  >
143  >;
144 
145  Container m_index;
146  Container::index<Queue>::type& m_queue = m_index.get<Queue>();
147  Container::index<Hashtable>::type& m_ht = m_index.get<Hashtable>();
148 
150 
151  // ---- current capacity and hard limits
152 
160  size_t m_capacity;
161 
162  static constexpr size_t INITIAL_CAPACITY = 1 << 14;
163 
168  static constexpr size_t MIN_CAPACITY = 1 << 10;
169 
174  static constexpr size_t MAX_CAPACITY = 1 << 24;
175 
176  // ---- actual entry lifetime estimation
177 
184  static constexpr Entry MARK = 0;
185 
187  static constexpr size_t EXPECTED_MARK_COUNT = 5;
188 
194  std::multiset<size_t> m_actualMarkCounts;
195 
196  const time::nanoseconds m_markInterval;
197  scheduler::ScopedEventId m_markEvent;
198 
199  // ---- capacity adjustments
200 
201  static constexpr double CAPACITY_UP = 1.2;
202  static constexpr double CAPACITY_DOWN = 0.9;
203  const time::nanoseconds m_adjustCapacityInterval;
204  scheduler::ScopedEventId m_adjustCapacityEvent;
205 
207  static constexpr size_t EVICT_LIMIT = 64;
208 };
209 
210 } // namespace nfd
211 
212 #endif // NFD_DAEMON_TABLE_DEAD_NONCE_LIST_HPP
Represents the Dead Nonce List.
time::nanoseconds getLifetime() const
Returns the expected nonce lifetime.
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.
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-common.hpp:39
#define NFD_PUBLIC_WITH_TESTS_ELSE_PRIVATE
Definition: common.hpp:41
static constexpr time::nanoseconds DEFAULT_LIFETIME
Default entry lifetime.
bool has(const Name &name, Interest::Nonce nonce) const
Determines if name+nonce is in the list.
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.
boost::chrono::nanoseconds nanoseconds
Definition: time.hpp:50