routing-table.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2014-2020, The University of Memphis,
4  * Regents of the University of California
5  *
6  * This file is part of NLSR (Named-data Link State Routing).
7  * See AUTHORS.md for complete list of NLSR authors and contributors.
8  *
9  * NLSR is free software: you can redistribute it and/or modify it under the terms
10  * of the GNU General Public License as published by the Free Software Foundation,
11  * either version 3 of the License, or (at your option) any later version.
12  *
13  * NLSR is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
14  * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
15  * PURPOSE. See the GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License along with
18  * NLSR, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
19  */
20 
21 #include "routing-table.hpp"
22 #include "nlsr.hpp"
23 #include "map.hpp"
24 #include "conf-parameter.hpp"
26 #include "routing-table-entry.hpp"
27 #include "name-prefix-table.hpp"
28 #include "logger.hpp"
29 #include "tlv-nlsr.hpp"
30 
31 #include <list>
32 #include <string>
33 
34 namespace nlsr {
35 
36 INIT_LOGGER(route.RoutingTable);
37 
38 RoutingTable::RoutingTable(ndn::Scheduler& scheduler, Fib& fib, Lsdb& lsdb,
39  NamePrefixTable& namePrefixTable, ConfParameter& confParam)
40  : afterRoutingChange{std::make_unique<AfterRoutingChange>()}
41  , m_scheduler(scheduler)
42  , m_fib(fib)
43  , m_lsdb(lsdb)
44  , m_namePrefixTable(namePrefixTable)
45  , m_routingCalcInterval{confParam.getRoutingCalcInterval()}
46  , m_isRoutingTableCalculating(false)
47  , m_isRouteCalculationScheduled(false)
48  , m_confParam(confParam)
49 {
50 }
51 
52 void
54 {
55  m_lsdb.writeLog();
56  m_namePrefixTable.writeLog();
57  if (m_isRoutingTableCalculating == false) {
58  // setting routing table calculation
59  m_isRoutingTableCalculating = true;
60 
61  bool isHrEnabled = m_confParam.getHyperbolicState() != HYPERBOLIC_STATE_OFF;
62 
63  if ((!isHrEnabled &&
64  m_lsdb.doesLsaExist(m_confParam.getRouterPrefix(), Lsa::Type::ADJACENCY))
65  ||
66  (isHrEnabled &&
67  m_lsdb.doesLsaExist(m_confParam.getRouterPrefix(), Lsa::Type::COORDINATE))) {
68  if (m_lsdb.getIsBuildAdjLsaSheduled() != 1) {
69  NLSR_LOG_TRACE("Clearing old routing table");
70  clearRoutingTable();
71  // for dry run options
72  clearDryRoutingTable();
73 
74  NLSR_LOG_DEBUG("Calculating routing table");
75 
76  // calculate Link State routing
77  if ((m_confParam.getHyperbolicState() == HYPERBOLIC_STATE_OFF) ||
78  (m_confParam.getHyperbolicState() == HYPERBOLIC_STATE_DRY_RUN)) {
79  calculateLsRoutingTable();
80  }
81  // calculate hyperbolic routing
82  if (m_confParam.getHyperbolicState() == HYPERBOLIC_STATE_ON) {
83  calculateHypRoutingTable(false);
84  }
85  // calculate dry hyperbolic routing
86  if (m_confParam.getHyperbolicState() == HYPERBOLIC_STATE_DRY_RUN) {
87  calculateHypRoutingTable(true);
88  }
89  // Inform the NPT that updates have been made
90  NLSR_LOG_DEBUG("Calling Update NPT With new Route");
91  (*afterRoutingChange)(m_rTable);
92  NLSR_LOG_DEBUG(*this);
93  m_namePrefixTable.writeLog();
94  m_fib.writeLog();
95  }
96  else {
97  NLSR_LOG_DEBUG("Adjacency building is scheduled, so routing table can not be calculated :(");
98  }
99  }
100  else {
101  NLSR_LOG_DEBUG("No Adj LSA of router itself, so Routing table can not be calculated :(");
102  clearRoutingTable();
103  clearDryRoutingTable(); // for dry run options
104  // need to update NPT here
105  NLSR_LOG_DEBUG("Calling Update NPT With new Route");
106  (*afterRoutingChange)(m_rTable);
107  NLSR_LOG_DEBUG(*this);
108  m_namePrefixTable.writeLog();
109  m_fib.writeLog();
110  // debugging purpose end
111  }
112  m_isRouteCalculationScheduled = false; // clear scheduled flag
113  m_isRoutingTableCalculating = false; // unsetting routing table calculation
114  }
115  else {
117  }
118 }
119 
120 void
121 RoutingTable::calculateLsRoutingTable()
122 {
123  NLSR_LOG_TRACE("CalculateLsRoutingTable Called");
124 
125  Map map;
126  auto lsaRange = m_lsdb.getLsdbIterator<AdjLsa>();
127  map.createFromAdjLsdb(lsaRange.first, lsaRange.second);
128  map.writeLog();
129 
130  size_t nRouters = map.getMapSize();
131 
132  LinkStateRoutingTableCalculator calculator(nRouters);
133 
134  calculator.calculatePath(map, *this, m_confParam, m_lsdb);
135 }
136 
137 void
138 RoutingTable::calculateHypRoutingTable(bool isDryRun)
139 {
140  Map map;
141  auto lsaRange = m_lsdb.getLsdbIterator<CoordinateLsa>();
142  map.createFromCoordinateLsdb(lsaRange.first, lsaRange.second);
143  map.writeLog();
144 
145  size_t nRouters = map.getMapSize();
146 
147  HyperbolicRoutingCalculator calculator(nRouters, isDryRun, m_confParam.getRouterPrefix());
148 
149  calculator.calculatePath(map, *this, m_lsdb, m_confParam.getAdjacencyList());
150 }
151 
152 void
154 {
155  if (!m_isRouteCalculationScheduled) {
156  NLSR_LOG_DEBUG("Scheduling routing table calculation in " << m_routingCalcInterval);
157  m_scheduler.schedule(m_routingCalcInterval, [this] { calculate(); });
158  m_isRouteCalculationScheduled = true;
159  }
160 }
161 
162 static bool
163 routingTableEntryCompare(RoutingTableEntry& rte, ndn::Name& destRouter)
164 {
165  return rte.getDestination() == destRouter;
166 }
167 
168 void
169 RoutingTable::addNextHop(const ndn::Name& destRouter, NextHop& nh)
170 {
171  NLSR_LOG_DEBUG("Adding " << nh << " for destination: " << destRouter);
172 
173  RoutingTableEntry* rteChk = findRoutingTableEntry(destRouter);
174  if (rteChk == nullptr) {
175  RoutingTableEntry rte(destRouter);
176  rte.getNexthopList().addNextHop(nh);
177  m_rTable.push_back(rte);
178  }
179  else {
180  rteChk->getNexthopList().addNextHop(nh);
181  }
182 }
183 
185 RoutingTable::findRoutingTableEntry(const ndn::Name& destRouter)
186 {
187  auto it = std::find_if(m_rTable.begin(), m_rTable.end(),
188  std::bind(&routingTableEntryCompare, _1, destRouter));
189  if (it != m_rTable.end()) {
190  return &(*it);
191  }
192  return nullptr;
193 }
194 
195 void
196 RoutingTable::addNextHopToDryTable(const ndn::Name& destRouter, NextHop& nh)
197 {
198  NLSR_LOG_DEBUG("Adding " << nh << " to dry table for destination: " << destRouter);
199 
200  auto it = std::find_if(m_dryTable.begin(), m_dryTable.end(),
201  std::bind(&routingTableEntryCompare, _1, destRouter));
202  if (it == m_dryTable.end()) {
203  RoutingTableEntry rte(destRouter);
204  rte.getNexthopList().addNextHop(nh);
205  m_dryTable.push_back(rte);
206  }
207  else {
208  it->getNexthopList().addNextHop(nh);
209  }
210 }
211 
212 void
213 RoutingTable::clearRoutingTable()
214 {
215  if (m_rTable.size() > 0) {
216  m_rTable.clear();
217  }
218 }
219 
220 void
221 RoutingTable::clearDryRoutingTable()
222 {
223  if (m_dryTable.size() > 0) {
224  m_dryTable.clear();
225  }
226 }
227 
228 template<ndn::encoding::Tag TAG>
229 size_t
230 RoutingTableStatus::wireEncode(ndn::EncodingImpl<TAG>& block) const
231 {
232  size_t totalLength = 0;
233 
234  for (auto it = m_dryTable.rbegin(); it != m_dryTable.rend(); ++it) {
235  totalLength += it->wireEncode(block);
236  }
237 
238  for (auto it = m_rTable.rbegin(); it != m_rTable.rend(); ++it) {
239  totalLength += it->wireEncode(block);
240  }
241 
242  totalLength += block.prependVarNumber(totalLength);
243  totalLength += block.prependVarNumber(ndn::tlv::nlsr::RoutingTable);
244 
245  return totalLength;
246 }
247 
249 
250 const ndn::Block&
252 {
253  if (m_wire.hasWire()) {
254  return m_wire;
255  }
256 
257  ndn::EncodingEstimator estimator;
258  size_t estimatedSize = wireEncode(estimator);
259 
260  ndn::EncodingBuffer buffer(estimatedSize, 0);
261  wireEncode(buffer);
262 
263  m_wire = buffer.block();
264 
265  return m_wire;
266 }
267 
268 void
269 RoutingTableStatus::wireDecode(const ndn::Block& wire)
270 {
271  m_rTable.clear();
272 
273  m_wire = wire;
274 
275  if (m_wire.type() != ndn::tlv::nlsr::RoutingTable) {
276  std::stringstream error;
277  error << "Expected RoutingTableStatus Block, but Block is of a different type: #"
278  << m_wire.type();
279  BOOST_THROW_EXCEPTION(Error(error.str()));
280  }
281 
282  m_wire.parse();
283 
284  auto val = m_wire.elements_begin();
285 
286  std::set<ndn::Name> destinations;
287  for (; val != m_wire.elements_end() && val->type() == ndn::tlv::nlsr::RoutingTableEntry; ++val) {
288  auto entry = RoutingTableEntry(*val);
289 
290  if (destinations.emplace(entry.getDestination()).second) {
291  m_rTable.push_back(entry);
292  }
293  else {
294  // If destination already exists then this is the start of dry HR table
295  m_dryTable.push_back(entry);
296  }
297  }
298 
299  if (val != m_wire.elements_end()) {
300  std::stringstream error;
301  error << "Expected the end of elements, but Block is of a different type: #"
302  << val->type();
303  BOOST_THROW_EXCEPTION(Error(error.str()));
304  }
305 }
306 
307 std::ostream&
308 operator<<(std::ostream& os, const RoutingTableStatus& rts)
309 {
310  os << "Routing Table:\n";
311  for (const auto& rte : rts.getRoutingTableEntry()) {
312  os << rte;
313  }
314 
315  if (!rts.getDryRoutingTableEntry().empty()) {
316  os << "Dry-Run Hyperbolic Routing Table:\n";
317  for (const auto& rte : rts.getDryRoutingTableEntry()) {
318  os << rte;
319  }
320  }
321  return os;
322 }
323 
324 } // namespace nlsr
void writeLog()
Definition: fib.cpp:354
void calculate()
Calculates a list of next hops for each router in the network.
Data abstraction for CoordinateLsa CoordinateLsa := COORDINATE-LSA-TYPE TLV-LENGTH Lsa HyperbolicRadi...
A class to house all the configuration parameters for NLSR.
NDN_CXX_DEFINE_WIRE_ENCODE_INSTANTIATIONS(Adjacent)
std::ostream & operator<<(std::ostream &os, const Adjacent &adjacent)
Definition: adjacent.cpp:181
void calculatePath(Map &map, RoutingTable &rt, Lsdb &lsdb, AdjacencyList &adjacencies)
const std::list< RoutingTableEntry > & getDryRoutingTableEntry() const
bool getIsBuildAdjLsaSheduled() const
Definition: lsdb.hpp:110
void createFromCoordinateLsdb(IteratorType begin, IteratorType end)
Definition: map.hpp:99
void scheduleRoutingTableCalculation()
Schedules a calculation event in the event scheduler only if one isn&#39;t already scheduled.
AdjacencyList & getAdjacencyList()
#define NLSR_LOG_DEBUG(x)
Definition: logger.hpp:38
const ndn::Name & getRouterPrefix() const
RoutingTable(ndn::Scheduler &scheduler, Fib &fib, Lsdb &lsdb, NamePrefixTable &namePrefixTable, ConfParameter &confParam)
Copyright (c) 2014-2018, The University of Memphis, Regents of the University of California.
Maps names to lists of next hops, and exports this information to NFD.
Definition: fib.hpp:59
size_t getMapSize() const
Definition: map.hpp:114
std::pair< LsaContainer::index< Lsdb::byType >::type::iterator, LsaContainer::index< Lsdb::byType >::type::iterator > getLsdbIterator() const
Definition: lsdb.hpp:169
#define INIT_LOGGER(name)
Definition: logger.hpp:35
static bool routingTableEntryCompare(RoutingTableEntry &rte, ndn::Name &destRouter)
const ndn::Block & wireEncode() const
std::list< RoutingTableEntry > m_dryTable
Data abstraction for AdjLsa AdjacencyLsa := ADJACENCY-LSA-TYPE TLV-LENGTH Lsa Adjacency*.
Definition: adj-lsa.hpp:37
void writeLog()
Definition: map.cpp:64
std::list< RoutingTableEntry > m_rTable
const ndn::Name & getDestination() const
bool doesLsaExist(const ndn::Name &router, Lsa::Type lsaType)
Returns whether the LSDB contains some LSA.
Definition: lsdb.hpp:74
void createFromAdjLsdb(IteratorType begin, IteratorType end)
Definition: map.hpp:81
Data abstraction for Nexthop.
Definition: nexthop.hpp:44
int32_t getHyperbolicState() const
const std::list< RoutingTableEntry > & getRoutingTableEntry() const
Data abstraction for RouteTableInfo.
Copyright (c) 2014-2020, The University of Memphis, Regents of the University of California, Arizona Board of Regents.
void addNextHop(const NextHop &nh)
Adds a next hop to the list.
void addNextHopToDryTable(const ndn::Name &destRouter, NextHop &nh)
Adds a next hop to a routing table entry in a dry run scenario.
Data abstraction for routing table status.
RoutingTableEntry * findRoutingTableEntry(const ndn::Name &destRouter)
void calculatePath(Map &pMap, RoutingTable &rt, ConfParameter &confParam, const Lsdb &lsdb)
void addNextHop(const ndn::Name &destRouter, NextHop &nh)
Adds a next hop to a routing table entry.
#define NLSR_LOG_TRACE(x)
Definition: logger.hpp:37
void writeLog() const
Definition: lsdb.cpp:116