NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.5: NDN, CCN, CCNx, content centric networks
API Documentation
remove-loops.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
21 #include "remove-loops.hpp"
22 
23 #include <boost/graph/adjacency_list.hpp>
24 #include <boost/graph/dijkstra_shortest_paths.hpp>
25 #include <boost/graph/properties.hpp>
26 #include <boost/property_map/property_map.hpp>
27 #include <queue>
28 
29 #include "ns3/abort.h"
30 #include "ns3/ndnSIM/helper/lfid/abstract-fib.hpp"
31 
32 namespace ns3 {
33 namespace ndn {
34 
35 using std::set;
37 
41 void
42 getDigraphFromFib(DiGraph& dg, const AllNodeFib& allNodeFIB, const int dstId)
43 {
44 
45  // 1. Erase All Arcs:
46  dg.clear();
47 
48  // 2. Add Arcs from FIB
49  for (const auto& node : allNodeFIB) {
50  int nodeId = node.first;
51  if (dstId == nodeId) {
52  continue;
53  }
54 
55  for (const auto& fibNh : node.second.getNexthops(dstId)) {
56  NS_ABORT_UNLESS(fibNh.getType() <= NextHopType::UPWARD);
57  boost::add_edge(static_cast<uint64_t>(nodeId), static_cast<uint64_t>(fibNh.getNexthopId()), 1, dg);
58  }
59  }
60 }
61 
62 class NodePrio {
63 public:
64  NodePrio(int nodeId, int remainingNh, set<FibNextHop> nhSet)
65  : m_nodeId{nodeId}
66  , m_remainingNh{remainingNh}
67  , m_uwSet{nhSet}
68  {
69  NS_ABORT_UNLESS(remainingNh > 0 && m_uwSet.size() > 0);
70  NS_ABORT_UNLESS(static_cast<int>(m_uwSet.size()) < remainingNh);
71  }
72 
73  int
74  getId() const
75  {
76  return m_nodeId;
77  }
78 
79  int
81  {
82  return static_cast<int>(m_uwSet.size());
83  }
84 
88  bool
89  operator<(const NodePrio& other) const
90  {
91  return std::make_tuple(m_remainingNh, getHighestCostUw(), m_nodeId)
92  < std::make_tuple(other.m_remainingNh, other.getHighestCostUw(), other.m_nodeId);
93  }
94 
95  // Setters:
98  {
99  const FibNextHop& tmp = getHighestCostUw();
100  eraseUw(tmp);
101  return tmp;
102  }
103 
104  void
106  {
107  m_remainingNh--;
108  // Check that remaining nexthops >= remaining uw nexthops.
109  NS_ABORT_UNLESS(m_remainingNh > 0 && m_remainingNh > getRemainingUw());
110  }
111 
112 private:
113  void
114  eraseUw(FibNextHop nh)
115  {
116  NS_ABORT_UNLESS(m_uwSet.size() > 0);
117  auto success = m_uwSet.erase(nh);
118  NS_ABORT_UNLESS(success == 1);
119  }
120 
121  FibNextHop
122  getHighestCostUw() const
123  {
124  NS_ABORT_UNLESS(m_uwSet.size() > 0);
125  NS_ABORT_UNLESS(std::prev(m_uwSet.end()) != m_uwSet.end());
126  return *(std::prev(m_uwSet.end()));
127  }
128 
129 private:
130  int m_nodeId;
131  int m_remainingNh;
132  set<FibNextHop> m_uwSet;
133 
134  friend std::ostream&
135  operator<<(std::ostream&, const NodePrio& node);
136 };
137 
138 std::ostream&
139 operator<<(std::ostream& os, const NodePrio& node)
140 {
141  return os << "Id: " << node.m_nodeId << ", remaining NH: " << node.m_remainingNh
142  << ", remaining UW: " << node.getRemainingUw() << " ";
143 }
144 
145 int
146 removeLoops(AllNodeFib& allNodeFIB, bool printOutput)
147 {
148  int removedLoopCounter = 0;
149  int upwardCounter = 0;
150 
151  const int NUM_NODES{static_cast<int>(allNodeFIB.size())};
152 
153  // Build graph with boost graph library:
154  DiGraph dg{};
155 
156  // Add all Arcs that fit into FIB. // O(n)
157  for (int dstId = 0; dstId < NUM_NODES; dstId++) {
158  // 1. Get DiGraph from Fib //
159  getDigraphFromFib(dg, allNodeFIB, dstId);
160 
161  // NodeId -> set<UwNexthops>
162  std::priority_queue<NodePrio> q;
163 
164  // 2. Put nodes in the queue, ordered by # remaining nexthops, then CostDelta // O(n^2)
165  for (const auto& node : allNodeFIB) {
166  int nodeId{node.first};
167  const AbstractFib& fib{node.second};
168  if (nodeId == dstId) {
169  continue;
170  }
171 
172  const auto& uwNhSet = fib.getUpwardNexthops(dstId);
173  if (!uwNhSet.empty()) {
174  upwardCounter += uwNhSet.size();
175 
176  int fibSize{fib.numEnabledNhPerDst(dstId)};
177  // NodePrio tmpNode {nodeId, fibSize, uwNhSet};
178  q.emplace(nodeId, fibSize, uwNhSet);
179  }
180  }
181 
182  // 3. Iterate PriorityQueue //
183  while (!q.empty()) {
184  NodePrio node = q.top();
185  q.pop();
186 
187  int nodeId = node.getId();
188  int nhId = node.popHighestCostUw().getNexthopId();
189 
190  // Remove opposite of Uphill link
191  // int arcId1 {getArcId(arcMap, nhId, nodeId)};
192  auto res = boost::edge(static_cast<uint64_t>(nhId), static_cast<uint64_t>(nodeId), dg);
193 
194  auto arc = res.first;
195  bool arcExists = res.second;
196 
197  if (arcExists) {
198  boost::remove_edge(arc, dg);
199  }
200 
201  // 2. Loop Check: Is the current node still reachable for the uphill nexthop?
202  // Uses BFS:
203  // bool willLoop = bfs(dg).run(dg.nodeFromId(nhId), dg.nodeFromId(nodeId)); // O(m^2n)
204 
205  std::vector<int> dists(num_vertices(dg));
206 
207  auto weightmap = get(boost::edge_weight, dg);
208 
209  const auto& x = boost::edges(dg);
210  for (auto e = x.first; e != x.second; e++) {
211  int weight = get(weightmap, *e);
212  NS_ABORT_UNLESS(weight == 1); // Only use uniform weights.
213  }
214 
215  // TODO: Could be replaced by BFS/DFS to improve speed.
216  dijkstra_shortest_paths(dg, static_cast<uint64_t>(nhId),
217  distance_map(
218  boost::make_iterator_property_map(dists.begin(), get(boost::vertex_index, dg))));
219 
220  bool willLoop = (dists.at(static_cast<size_t>(nodeId)) < (std::numeric_limits<int>::max() - 1));
221 
222  // Uphill nexthop loops back to original node
223  if (willLoop) {
224  node.reduceRemainingNh();
225  removedLoopCounter++;
226 
227  // Erase FIB entry
228  allNodeFIB.at(node.getId()).erase(dstId, nhId);
229 
230  auto res2 = boost::edge(static_cast<uint64_t>(node.getId()), static_cast<uint64_t>(nhId), dg);
231  auto arc2 = res2.first;
232  NS_ABORT_UNLESS(res.second);
233 
234  boost::remove_edge(arc2, dg);
235  }
236 
237  // Add opposite of UW link back:
238  if (arcExists) {
239  boost::add_edge(static_cast<uint64_t>(nhId), static_cast<uint64_t>(nodeId), 1, dg);
240  }
241 
242  // If not has further UW nexthops: Requeue.
243  if (node.getRemainingUw() > 0) {
244  q.push(node);
245  }
246  }
247  }
248 
249  if (printOutput) {
250  std::cout << "Found " << upwardCounter << " UW nexthops, Removed " << removedLoopCounter
251  << " Looping UwNhs, Remaining: " << upwardCounter - removedLoopCounter << " NHs\n";
252  }
253  NS_ABORT_UNLESS((upwardCounter - removedLoopCounter) >= 0);
254 
255  return removedLoopCounter;
256 }
257 
258 int
259 removeDeadEnds(AllNodeFib& allNodeFIB, bool printOutput)
260 {
261  int NUM_NODES{static_cast<int>(allNodeFIB.size())};
262  int checkedUwCounter{0};
263  int uwCounter{0};
264  int totalCounter{0};
265  int removedDeadendCounter{0};
266 
267  for (int dstId = 0; dstId < NUM_NODES; dstId++) {
268  // NodeId -> FibNexthops (Order important)
269  set<std::pair<int, FibNextHop>> nhSet;
270 
271  // 1. Put all uwNexthops in set<NodeId, FibNexhtop>:
272  for (const auto& node : allNodeFIB) {
273  int nodeId{node.first};
274  if (nodeId == dstId) {
275  continue;
276  }
277 
278  totalCounter += node.second.getNexthops(dstId).size();
279 
280  const auto& uwNhSet = node.second.getUpwardNexthops(dstId);
281  uwCounter += uwNhSet.size();
282  for (const FibNextHop& fibNh : uwNhSet) {
283  nhSet.emplace(nodeId, fibNh);
284  }
285  }
286 
287  // FibNexthops ordered by (costDelta, cost, nhId).
288  // Start with nexthop with highest cost:
289  while (!nhSet.empty()) {
290  checkedUwCounter++;
291 
292  // Pop from queue:
293  const auto& nhPair = nhSet.begin();
294  NS_ABORT_UNLESS(nhPair != nhSet.end());
295  nhSet.erase(nhPair);
296 
297  int nodeId = nhPair->first;
298  const FibNextHop& nh = nhPair->second;
299  AbstractFib& fib = allNodeFIB.at(nodeId);
300 
301  if (nh.getNexthopId() == dstId) {
302  continue;
303  }
304 
305  int reverseEntries{allNodeFIB.at(nh.getNexthopId()).numEnabledNhPerDst(dstId)};
306 
307  // Must have at least one FIB entry.
308  NS_ABORT_UNLESS(reverseEntries > 0);
309 
310  // If it has exactly 1 entry -> Is downward back through the upward nexthop!
311  // Higher O-Complexity below:
312  if (reverseEntries <= 1) {
313  removedDeadendCounter++;
314 
315  // Erase NhEntry from FIB:
316  fib.erase(dstId, nh.getNexthopId());
317 
318  // Push into Queue: All NhEntries that lead to m_nodeId!
319  const auto& nexthops = fib.getNexthops(dstId);
320 
321  for (const auto& ownNhs : nexthops) {
322  if (ownNhs.getType() == NextHopType::DOWNWARD && ownNhs.getNexthopId() != dstId) {
323  const auto& reverseNh = allNodeFIB.at(ownNhs.getNexthopId()).getNexthops(dstId);
324 
325  for (const auto& y : reverseNh) {
326  if (y.getNexthopId() == nodeId) {
327  NS_ABORT_UNLESS(y.getType() == NextHopType::UPWARD);
328  nhSet.emplace(ownNhs.getNexthopId(), y);
329  break;
330  }
331  }
332  }
333  }
334  }
335  }
336  }
337 
338  if (printOutput) {
339  std::cout << "Checked " << checkedUwCounter << " Upward NHs, Removed " << removedDeadendCounter
340  << " Deadend UwNhs, Remaining: " << uwCounter - removedDeadendCounter << " UW NHs, "
341  << totalCounter - removedDeadendCounter << " total nexthops\n";
342  }
343 
344  return removedDeadendCounter;
345 }
346 
347 } // namespace ndn
348 } // namespace ns3
remove-loops.hpp
ns3::ndn::operator<<
std::ostream & operator<<(std::ostream &os, const AbstractFib &fib)
Definition: abstract-fib.cpp:175
ns3::ndn::AbstractFib::AllNodeFib
std::unordered_map< int, AbstractFib > AllNodeFib
Definition: abstract-fib.hpp:41
ns3::ndn::NodePrio::getRemainingUw
int getRemainingUw() const
Definition: remove-loops.cpp:80
ns3
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-app-link-service.cpp:32
ns3::ndn::NodePrio::getId
int getId() const
Definition: remove-loops.cpp:74
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
ns3::ndn::getDigraphFromFib
void getDigraphFromFib(DiGraph &dg, const AllNodeFib &allNodeFIB, const int dstId)
Fill directed graph only with edges existing in the FIB.
Definition: remove-loops.cpp:42
ns3::ndn::AbstractFib::getNexthops
const std::set< FibNextHop > & getNexthops(int dstId) const
Definition: abstract-fib.cpp:130
ns3::ndn::NextHopType::DOWNWARD
@ DOWNWARD
ns3::ndn::NodePrio::NodePrio
NodePrio(int nodeId, int remainingNh, set< FibNextHop > nhSet)
Definition: remove-loops.cpp:64
ns3::ndn::NodePrio
Definition: remove-loops.cpp:62
ns3::ndn::AbstractFib
An abstract, lightweight representation of the FIB.
Definition: abstract-fib.hpp:39
ns3::ndn::removeLoops
int removeLoops(AllNodeFib &allNodeFIB, bool printOutput)
Definition: remove-loops.cpp:146
ns3::ndn::AllNodeFib
AbstractFib::AllNodeFib AllNodeFib
Definition: remove-loops.cpp:36
ns3::ndn::FibNextHop::getNexthopId
int getNexthopId() const
Definition: fib-nexthop.hpp:50
ns3::ndn::DiGraph
boost::adjacency_list< boost::listS, boost::vecS, boost::bidirectionalS, boost::no_property, boost::property< boost::edge_weight_t, int > > DiGraph
Definition: remove-loops.hpp:35
ns3::ndn::removeDeadEnds
int removeDeadEnds(AllNodeFib &allNodeFIB, bool printOutput)
Definition: remove-loops.cpp:259
ns3::ndn::NodePrio::popHighestCostUw
FibNextHop popHighestCostUw()
Definition: remove-loops.cpp:97
ns3::ndn::NodePrio::operator<
bool operator<(const NodePrio &other) const
Order by Remamining UW NHs, Highest DeltaCost, and then id.
Definition: remove-loops.cpp:89
ns3::ndn::AbstractFib::getUpwardNexthops
const std::set< FibNextHop > & getUpwardNexthops(int dstId) const
Definition: abstract-fib.cpp:140
ns3::ndn::NodePrio::reduceRemainingNh
void reduceRemainingNh()
Definition: remove-loops.cpp:105
ns3::ndn::NextHopType::UPWARD
@ UPWARD
ns3::ndn::FibNextHop
Definition: fib-nexthop.hpp:36
ns3::ndn::AbstractFib::erase
size_t erase(int dstId, int nhId)
Definition: abstract-fib.cpp:102
ns3::ndn::NodePrio::operator<<
friend std::ostream & operator<<(std::ostream &, const NodePrio &node)
Definition: remove-loops.cpp:139
ndn
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-strategy-choice-helper.hpp:34
ns3::ndn::AbstractFib::numEnabledNhPerDst
int numEnabledNhPerDst(int dstId) const
Definition: abstract-fib.hpp:74