NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.5: NDN, CCN, CCNx, content centric networks
API Documentation
rib.hpp
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 #ifndef NFD_DAEMON_RIB_RIB_HPP
27 #define NFD_DAEMON_RIB_RIB_HPP
28 
29 #include "rib-entry.hpp"
30 #include "rib-update-batch.hpp"
31 
33 
34 namespace nfd {
35 namespace rib {
36 
38 
39 class FibUpdater;
40 
44 {
45  shared_ptr<RibEntry> entry;
47 };
48 
49 bool
50 operator<(const RibRouteRef& lhs, const RibRouteRef& rhs);
51 
59 class Rib : noncopyable
60 {
61 public:
62  using RibEntryList = std::list<shared_ptr<RibEntry>>;
63  using RibTable = std::map<Name, shared_ptr<RibEntry>>;
64  using const_iterator = RibTable::const_iterator;
65 
66  void
67  setFibUpdater(FibUpdater* updater);
68 
70  find(const Name& prefix) const;
71 
72  Route*
73  find(const Name& prefix, const Route& route) const;
74 
75  Route*
76  findLongestPrefix(const Name& prefix, const Route& route) const;
77 
79  begin() const
80  {
81  return m_rib.begin();
82  }
83 
85  end() const
86  {
87  return m_rib.end();
88  }
89 
90  size_t
91  size() const
92  {
93  return m_nItems;
94  }
95 
96  bool
97  empty() const
98  {
99  return m_rib.empty();
100  }
101 
102  shared_ptr<RibEntry>
103  findParent(const Name& prefix) const;
104 
105 public:
106  using UpdateSuccessCallback = std::function<void()>;
107  using UpdateFailureCallback = std::function<void(uint32_t code, const std::string& error)>;
108 
117  void
118  beginApplyUpdate(const RibUpdate& update,
119  const UpdateSuccessCallback& onSuccess,
120  const UpdateFailureCallback& onFailure);
121 
124  void
125  beginRemoveFace(uint64_t faceId);
126 
127  void
128  beginRemoveFailedFaces(const std::set<uint64_t>& activeFaceIds);
129 
130  void
131  onRouteExpiration(const Name& prefix, const Route& route);
132 
133  void
134  insert(const Name& prefix, const Route& route);
135 
136 private:
137  void
138  enqueueRemoveFace(const RibEntry& entry, uint64_t faceId);
139 
144  void
145  addUpdateToQueue(const RibUpdate& update,
146  const Rib::UpdateSuccessCallback& onSuccess,
147  const Rib::UpdateFailureCallback& onFailure);
148 
151  void
152  sendBatchFromQueue();
153 
154  void
155  onFibUpdateSuccess(const RibUpdateBatch& batch,
156  const RibUpdateList& inheritedRoutes,
157  const Rib::UpdateSuccessCallback& onSuccess);
158 
159  void
160  onFibUpdateFailure(const Rib::UpdateFailureCallback& onFailure,
161  uint32_t code, const std::string& error);
162 
164  void
165  erase(const Name& prefix, const Route& route);
166 
167 private:
168  using RouteComparePredicate = bool (*)(const Route&, const Route&);
169  using RouteSet = std::set<Route, RouteComparePredicate>;
170 
174  std::list<shared_ptr<RibEntry>>
175  findDescendants(const Name& prefix) const;
176 
180  std::list<shared_ptr<RibEntry>>
181  findDescendantsForNonInsertedName(const Name& prefix) const;
182 
183  RibTable::iterator
184  eraseEntry(RibTable::iterator it);
185 
186  void
187  updateRib(const RibUpdateBatch& batch);
188 
193  RouteSet
194  getAncestorRoutes(const RibEntry& entry) const;
195 
202  RouteSet
203  getAncestorRoutes(const Name& name) const;
204 
208  void
209  modifyInheritedRoutes(const RibUpdateList& inheritedRoutes);
210 
211 public:
218 
225 
229 
233 
234 private:
235  RibTable m_rib;
236  std::multimap<uint64_t, shared_ptr<RibEntry>> m_faceEntries;
237  size_t m_nItems = 0;
238  FibUpdater* m_fibUpdater = nullptr;
239 
240  struct UpdateQueueItem
241  {
242  RibUpdateBatch batch;
243  const Rib::UpdateSuccessCallback managerSuccessCallback;
244  const Rib::UpdateFailureCallback managerFailureCallback;
245  };
246 
247  using UpdateQueue = std::list<UpdateQueueItem>;
248  UpdateQueue m_updateBatches;
249  bool m_isUpdateInProgress = false;
250 
251  friend class FibUpdater;
252 };
253 
254 std::ostream&
255 operator<<(std::ostream& os, const Rib& rib);
256 
257 } // namespace rib
258 } // namespace nfd
259 
260 #endif // NFD_DAEMON_RIB_RIB_HPP
PUBLIC_WITH_TESTS_ELSE_PRIVATE
#define PUBLIC_WITH_TESTS_ELSE_PRIVATE
Definition: common.hpp:41
rib-entry.hpp
nfd::rib::RibEntry
Represents a RIB entry, which contains one or more Routes with the same prefix.
Definition: rib-entry.hpp:39
nfd::rib::Rib::const_iterator
RibTable::const_iterator const_iterator
Definition: rib.hpp:64
nfd::rib::Rib::find
const_iterator find(const Name &prefix) const
Definition: rib.cpp:55
nfd::rib::Rib::RibTable
std::map< Name, shared_ptr< RibEntry > > RibTable
Definition: rib.hpp:63
nfd::rib::FibUpdater
computes FibUpdates based on updates to the RIB and sends them to NFD
Definition: fib-updater.hpp:42
nfd::rib::RibRouteRef::route
RibEntry::const_iterator route
Definition: rib.hpp:46
nfd::rib::Rib::onRouteExpiration
void onRouteExpiration(const Name &prefix, const Route &route)
Definition: rib.cpp:202
nfd::rib::Rib::afterInsertEntry
signal::Signal< Rib, Name > afterInsertEntry
signals after a RIB entry is inserted
Definition: rib.hpp:217
nfd::rib::Rib::empty
bool empty() const
Definition: rib.hpp:97
ndn::util::signal::Signal
provides a lightweight signal / event system
Definition: signal.hpp:52
nfd::rib::RibUpdateList
std::list< RibUpdate > RibUpdateList
Definition: rib-update-batch.hpp:36
nfd::rib::operator<
bool operator<(const ReadvertisedRoute &lhs, const ReadvertisedRoute &rhs)
Definition: readvertised-route.hpp:59
ndn::Name
Represents an absolute name.
Definition: name.hpp:44
nfd::rib::Rib::UpdateFailureCallback
std::function< void(uint32_t code, const std::string &error)> UpdateFailureCallback
Definition: rib.hpp:107
nfd::rib::RibUpdate
RibUpdate.
Definition: rib-update.hpp:41
nfd::rib::Rib::beforeRemoveRoute
signal::Signal< Rib, RibRouteRef > beforeRemoveRoute
signals before a route is removed
Definition: rib.hpp:232
nfd
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-common.hpp:40
nfd::rib::Rib::afterEraseEntry
signal::Signal< Rib, Name > afterEraseEntry
signals after a RIB entry is erased
Definition: rib.hpp:224
nfd::rib::Rib::findParent
shared_ptr< RibEntry > findParent(const Name &prefix) const
Definition: rib.cpp:215
nfd::rib::RibEntry::const_iterator
RouteList::const_iterator const_iterator
Definition: rib-entry.hpp:43
nfd::rib::Rib::findLongestPrefix
Route * findLongestPrefix(const Name &prefix, const Route &route) const
Definition: rib.cpp:78
nfd::rib::operator<<
std::ostream & operator<<(std::ostream &os, const FibUpdate &update)
Definition: fib-update.hpp:74
nfd::rib::Rib
represents the Routing Information Base
Definition: rib.hpp:60
nfd::rib::Rib::end
const_iterator end() const
Definition: rib.hpp:85
ndn::tlv::nfd::ControlParameters
@ ControlParameters
Definition: tlv-nfd.hpp:35
nfd::rib::Rib::insert
void insert(const Name &prefix, const Route &route)
Definition: rib.cpp:92
nfd::rib::Rib::setFibUpdater
void setFibUpdater(FibUpdater *updater)
Definition: rib.cpp:49
rib-update-batch.hpp
nfd::rib::RibRouteRef::entry
shared_ptr< RibEntry > entry
Definition: rib.hpp:45
nfd::rib::RibRouteRef
references a route
Definition: rib.hpp:44
nfd::rib::Rib::afterAddRoute
signal::Signal< Rib, RibRouteRef > afterAddRoute
signals after a Route is added
Definition: rib.hpp:228
nfd::rib::Rib::beginRemoveFailedFaces
void beginRemoveFailedFaces(const std::set< uint64_t > &activeFaceIds)
Definition: rib.cpp:373
nfd::rib::Rib::begin
const_iterator begin() const
Definition: rib.hpp:79
nfd::rib::Rib::UpdateSuccessCallback
std::function< void()> UpdateSuccessCallback
Definition: rib.hpp:106
ndn::name
Definition: name-component-types.hpp:33
nfd::rib::Route
represents a route for a name prefix
Definition: route.hpp:44
nfd::rib::Rib::beginRemoveFace
void beginRemoveFace(uint64_t faceId)
starts the FIB update process when a face has been destroyed
Definition: rib.cpp:363
control-parameters.hpp
nfd::rib::RibUpdateBatch
Represents a collection of RibUpdates to be applied to a single FaceId.
Definition: rib-update-batch.hpp:41
nfd::rib::Rib::RibEntryList
std::list< shared_ptr< RibEntry > > RibEntryList
Definition: rib.hpp:62
nfd::rib::Rib::size
size_t size() const
Definition: rib.hpp:91
nfd::rib::Rib::beginApplyUpdate
void beginApplyUpdate(const RibUpdate &update, const UpdateSuccessCallback &onSuccess, const UpdateFailureCallback &onFailure)
passes the provided RibUpdateBatch to FibUpdater to calculate and send FibUpdates.
Definition: rib.cpp:351
nfd::rib::FibUpdater
FibUpdater
Definition: fib-updater.cpp:34