NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.5: NDN, CCN, CCNx, content centric networks
API Documentation
ndn-global-routing-helper.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
20 #if __clang__
21 #pragma clang diagnostic push
22 #pragma clang diagnostic ignored "-Wunused-variable"
23 #pragma clang diagnostic ignored "-Wunneeded-internal-declaration"
24 #endif
25 
27 
32 
33 #include "daemon/table/fib.hpp"
34 #include "daemon/fw/forwarder.hpp"
37 
38 #include "ns3/object.h"
39 #include "ns3/node.h"
40 #include "ns3/node-container.h"
41 #include "ns3/net-device.h"
42 #include "ns3/channel.h"
43 #include "ns3/log.h"
44 #include "ns3/assert.h"
45 #include "ns3/names.h"
46 #include "ns3/node-list.h"
47 #include "ns3/channel-list.h"
48 #include "ns3/object-factory.h"
49 
50 #include <boost/lexical_cast.hpp>
51 #include <boost/foreach.hpp>
52 #include <boost/concept/assert.hpp>
53 #include <boost/graph/dijkstra_shortest_paths.hpp>
54 
55 #include <unordered_map>
56 
58 
59 #include <math.h>
60 
61 NS_LOG_COMPONENT_DEFINE("ndn.GlobalRoutingHelper");
62 
63 namespace ns3 {
64 namespace ndn {
65 
66 void
68 {
69  NS_LOG_LOGIC("Node: " << node->GetId());
70 
71  Ptr<L3Protocol> ndn = node->GetObject<L3Protocol>();
72  NS_ASSERT_MSG(ndn != 0, "Cannot install GlobalRoutingHelper before Ndn is installed on a node");
73 
74  Ptr<GlobalRouter> gr = node->GetObject<GlobalRouter>();
75  if (gr != 0) {
76  NS_LOG_DEBUG("GlobalRouter is already installed: " << gr);
77  return; // already installed
78  }
79 
80  gr = CreateObject<GlobalRouter>();
81  node->AggregateObject(gr);
82 
83  for (auto& face : ndn->getFaceTable()) {
84  auto transport = dynamic_cast<NetDeviceTransport*>(face.getTransport());
85  if (transport == nullptr) {
86  NS_LOG_DEBUG("Skipping non ndnSIM-specific transport face");
87  continue;
88  }
89 
90  Ptr<NetDevice> nd = transport->GetNetDevice();
91  if (nd == 0) {
92  NS_LOG_DEBUG("Not a NetDevice associated with an ndnSIM-specific transport instance");
93  continue;
94  }
95 
96  Ptr<Channel> ch = nd->GetChannel();
97 
98  if (ch == 0) {
99  NS_LOG_DEBUG("Channel is not associated with NetDevice");
100  continue;
101  }
102 
103  if (ch->GetNDevices() == 2) // e.g., point-to-point channel
104  {
105  for (uint32_t deviceId = 0; deviceId < ch->GetNDevices(); deviceId++) {
106  Ptr<NetDevice> otherSide = ch->GetDevice(deviceId);
107  if (nd == otherSide)
108  continue;
109 
110  Ptr<Node> otherNode = otherSide->GetNode();
111  NS_ASSERT(otherNode != 0);
112 
113  Ptr<GlobalRouter> otherGr = otherNode->GetObject<GlobalRouter>();
114  if (otherGr == 0) {
115  Install(otherNode);
116  }
117  otherGr = otherNode->GetObject<GlobalRouter>();
118  NS_ASSERT(otherGr != 0);
119  gr->AddIncidency(face.shared_from_this(), otherGr);
120  }
121  }
122  else {
123  Ptr<GlobalRouter> grChannel = ch->GetObject<GlobalRouter>();
124  if (grChannel == 0) {
125  Install(ch);
126  }
127  grChannel = ch->GetObject<GlobalRouter>();
128 
129  gr->AddIncidency(face.shared_from_this(), grChannel);
130  }
131  }
132 }
133 
134 void
135 GlobalRoutingHelper::Install(Ptr<Channel> channel)
136 {
137  NS_LOG_LOGIC("Channel: " << channel->GetId());
138 
139  Ptr<GlobalRouter> gr = channel->GetObject<GlobalRouter>();
140  if (gr != 0)
141  return;
142 
143  gr = CreateObject<GlobalRouter>();
144  channel->AggregateObject(gr);
145 
146  for (uint32_t deviceId = 0; deviceId < channel->GetNDevices(); deviceId++) {
147  Ptr<NetDevice> dev = channel->GetDevice(deviceId);
148 
149  Ptr<Node> node = dev->GetNode();
150  NS_ASSERT(node != 0);
151 
152  Ptr<GlobalRouter> grOther = node->GetObject<GlobalRouter>();
153  if (grOther == 0) {
154  Install(node);
155  }
156  grOther = node->GetObject<GlobalRouter>();
157  NS_ASSERT(grOther != 0);
158 
159  gr->AddIncidency(0, grOther);
160  }
161 }
162 
163 void
164 GlobalRoutingHelper::Install(const NodeContainer& nodes)
165 {
166  for (NodeContainer::Iterator node = nodes.Begin(); node != nodes.End(); node++) {
167  Install(*node);
168  }
169 }
170 
171 void
173 {
174  Install(NodeContainer::GetGlobal());
175 }
176 
177 void
178 GlobalRoutingHelper::AddOrigin(const std::string& prefix, Ptr<Node> node)
179 {
180  Ptr<GlobalRouter> gr = node->GetObject<GlobalRouter>();
181  NS_ASSERT_MSG(gr != 0, "GlobalRouter is not installed on the node");
182 
183  auto name = make_shared<Name>(prefix);
184  gr->AddLocalPrefix(name);
185 }
186 
187 void
188 GlobalRoutingHelper::AddOrigins(const std::string& prefix, const NodeContainer& nodes)
189 {
190  for (NodeContainer::Iterator node = nodes.Begin(); node != nodes.End(); node++) {
191  AddOrigin(prefix, *node);
192  }
193 }
194 
195 void
196 GlobalRoutingHelper::AddOrigin(const std::string& prefix, const std::string& nodeName)
197 {
198  Ptr<Node> node = Names::Find<Node>(nodeName);
199  NS_ASSERT_MSG(node != 0, nodeName << "is not a Node");
200 
201  AddOrigin(prefix, node);
202 }
203 
204 void
206 {
207  for (NodeList::Iterator node = NodeList::Begin(); node != NodeList::End(); node++) {
208  Ptr<GlobalRouter> gr = (*node)->GetObject<GlobalRouter>();
209  std::string name = Names::FindName(*node);
210 
211  if (gr != 0 && !name.empty()) {
212  AddOrigin("/" + name, *node);
213  }
214  }
215 }
216 
217 void
219 {
225  BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept<boost::NdnGlobalRouterGraph>));
226  BOOST_CONCEPT_ASSERT((boost::IncidenceGraphConcept<boost::NdnGlobalRouterGraph>));
227 
228  boost::NdnGlobalRouterGraph graph;
229  // typedef graph_traits < NdnGlobalRouterGraph >::vertex_descriptor vertex_descriptor;
230 
231  // For now we doing Dijkstra for every node. Can be replaced with Bellman-Ford or Floyd-Warshall.
232  // Other algorithms should be faster, but they need additional EdgeListGraph concept provided by
233  // the graph, which
234  // is not obviously how implement in an efficient manner
235  for (NodeList::Iterator node = NodeList::Begin(); node != NodeList::End(); node++) {
236  Ptr<GlobalRouter> source = (*node)->GetObject<GlobalRouter>();
237  if (source == 0) {
238  NS_LOG_DEBUG("Node " << (*node)->GetId() << " does not export GlobalRouter interface");
239  continue;
240  }
241 
242  boost::DistancesMap distances;
243 
244  dijkstra_shortest_paths(graph, source,
245  // predecessor_map (boost::ref(predecessors))
246  // .
247  distance_map(boost::ref(distances))
248  .distance_inf(boost::WeightInf)
249  .distance_zero(boost::WeightZero)
250  .distance_compare(boost::WeightCompare())
251  .distance_combine(boost::WeightCombine()));
252 
253  // NS_LOG_DEBUG (predecessors.size () << ", " << distances.size ());
254 
255  Ptr<L3Protocol> L3protocol = (*node)->GetObject<L3Protocol>();
256  shared_ptr<nfd::Forwarder> forwarder = L3protocol->getForwarder();
257 
258  NS_LOG_DEBUG("Reachability from Node: " << source->GetObject<Node>()->GetId());
259  for (const auto& dist : distances) {
260  if (dist.first == source)
261  continue;
262  else {
263  // cout << " Node " << dist.first->GetObject<Node> ()->GetId ();
264  if (std::get<0>(dist.second) == 0) {
265  // cout << " is unreachable" << endl;
266  }
267  else {
268  for (const auto& prefix : dist.first->GetLocalPrefixes()) {
269  NS_LOG_DEBUG(" prefix " << prefix << " reachable via face " << *std::get<0>(dist.second)
270  << " with distance " << std::get<1>(dist.second) << " with delay "
271  << std::get<2>(dist.second));
272 
273  FibHelper::AddRoute(*node, *prefix, std::get<0>(dist.second),
274  std::get<1>(dist.second));
275  }
276  }
277  }
278  }
279  }
280 }
281 
282 void
284 {
290  BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept<boost::NdnGlobalRouterGraph>));
291  BOOST_CONCEPT_ASSERT((boost::IncidenceGraphConcept<boost::NdnGlobalRouterGraph>));
292 
293  boost::NdnGlobalRouterGraph graph;
294  // typedef graph_traits < NdnGlobalRouterGraph >::vertex_descriptor vertex_descriptor;
295 
296  // For now we doing Dijkstra for every node. Can be replaced with Bellman-Ford or Floyd-Warshall.
297  // Other algorithms should be faster, but they need additional EdgeListGraph concept provided by
298  // the graph, which
299  // is not obviously how implement in an efficient manner
300  for (NodeList::Iterator node = NodeList::Begin(); node != NodeList::End(); node++) {
301  Ptr<GlobalRouter> source = (*node)->GetObject<GlobalRouter>();
302  if (source == 0) {
303  NS_LOG_DEBUG("Node " << (*node)->GetId() << " does not export GlobalRouter interface");
304  continue;
305  }
306 
307  Ptr<L3Protocol> L3protocol = (*node)->GetObject<L3Protocol>();
308  shared_ptr<nfd::Forwarder> forwarder = L3protocol->getForwarder();
309 
310  NS_LOG_DEBUG("Reachability from Node: " << source->GetObject<Node>()->GetId() << " ("
311  << Names::FindName(source->GetObject<Node>()) << ")");
312 
313  Ptr<L3Protocol> l3 = source->GetObject<L3Protocol>();
314  NS_ASSERT(l3 != 0);
315 
316  // remember interface statuses
317  std::list<nfd::FaceId> faceIds;
318  std::unordered_map<nfd::FaceId, uint16_t> originalMetrics;
319  for (auto& nfdFace : l3->getFaceTable()) {
320  faceIds.push_back(nfdFace.getId());
321  originalMetrics[nfdFace.getId()] = nfdFace.getMetric();
322  nfdFace.setMetric(std::numeric_limits<uint16_t>::max() - 1);
323  // value std::numeric_limits<uint16_t>::max () MUST NOT be used (reserved)
324  }
325 
326  for (auto& faceId : faceIds) {
327  auto* face = l3->getFaceTable().get(faceId);
328  NS_ASSERT(face != nullptr);
329  auto transport = dynamic_cast<NetDeviceTransport*>(face->getTransport());
330  if (transport == nullptr) {
331  NS_LOG_DEBUG("Skipping non ndnSIM-specific transport face");
332  continue;
333  }
334 
335  // enabling only faceId
336  face->setMetric(originalMetrics[faceId]);
337 
338  boost::DistancesMap distances;
339 
340  NS_LOG_DEBUG("-----------");
341 
342  dijkstra_shortest_paths(graph, source,
343  // predecessor_map (boost::ref(predecessors))
344  // .
345  distance_map(boost::ref(distances))
346  .distance_inf(boost::WeightInf)
347  .distance_zero(boost::WeightZero)
348  .distance_compare(boost::WeightCompare())
349  .distance_combine(boost::WeightCombine()));
350 
351  // NS_LOG_DEBUG (predecessors.size () << ", " << distances.size ());
352 
353  for (const auto& dist : distances) {
354  if (dist.first == source)
355  continue;
356  else {
357  // cout << " Node " << dist.first->GetObject<Node> ()->GetId ();
358  if (std::get<0>(dist.second) == 0) {
359  // cout << " is unreachable" << endl;
360  }
361  else {
362  for (const auto& prefix : dist.first->GetLocalPrefixes()) {
363  NS_LOG_DEBUG(" prefix " << *prefix << " reachable via face "
364  << *std::get<0>(dist.second)
365  << " with distance " << std::get<1>(dist.second)
366  << " with delay " << std::get<2>(dist.second));
367 
368  if (std::get<0>(dist.second)->getMetric() == std::numeric_limits<uint16_t>::max() - 1)
369  continue;
370 
371  FibHelper::AddRoute(*node, *prefix, std::get<0>(dist.second),
372  std::get<1>(dist.second));
373  }
374  }
375  }
376  }
377 
378  // disabling the face again
379  face->setMetric(std::numeric_limits<uint16_t>::max() - 1);
380  }
381 
382  // recover original interface statuses
383  for (auto& i : originalMetrics) {
384  l3->getFaceTable().get(i.first)->setMetric(i.second);
385  }
386  }
387 }
388 
389 } // namespace ndn
390 } // namespace ns3
ns3::ndn::GlobalRoutingHelper::InstallAll
void InstallAll()
Install GlobalRouter interface on all nodes.
Definition: ndn-global-routing-helper.cpp:172
ns3::ndn::L3Protocol::getForwarder
shared_ptr< nfd::Forwarder > getForwarder()
Get smart pointer to nfd::Forwarder installed on the node.
Definition: ndn-l3-protocol.cpp:328
ndn-global-router.hpp
ns3
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-app-link-service.cpp:32
boost-graph-ndn-global-routing-helper.hpp
ns3::ndn::GlobalRouter::AddIncidency
void AddIncidency(shared_ptr< Face > face, Ptr< GlobalRouter > ndn)
Add edge to the node.
Definition: ndn-global-router.cpp:74
ns3::ndn::GlobalRoutingHelper::AddOrigins
void AddOrigins(const std::string &prefix, const NodeContainer &nodes)
Add ‘prefix’ as origin on all ‘nodes’.
Definition: ndn-global-routing-helper.cpp:188
fib.hpp
fib-entry.hpp
ndn-global-routing-helper.hpp
ns3::ndn::GlobalRoutingHelper::CalculateAllPossibleRoutes
static void CalculateAllPossibleRoutes()
Calculate all possible next-hop independent alternative routes.
Definition: ndn-global-routing-helper.cpp:283
forwarder.hpp
ndn-net-device-transport.hpp
ns3::ndn::GlobalRouter
Class representing global router interface for ndnSIM.
Definition: ndn-global-router.hpp:43
ns3::ndn::FibHelper::AddRoute
static void AddRoute(Ptr< Node > node, const Name &prefix, shared_ptr< Face > face, int32_t metric)
Add forwarding entry to FIB.
Definition: ndn-fib-helper.cpp:85
ns3::ndn::NetDeviceTransport
ndnSIM-specific transport
Definition: ndn-net-device-transport.hpp:43
nfd::face
Definition: ndn-common.hpp:84
ndn-fib-helper.hpp
ns3::ndn::GlobalRoutingHelper::CalculateRoutes
static void CalculateRoutes()
Calculate for every node shortest path trees and install routes to all prefix origins.
Definition: ndn-global-routing-helper.cpp:218
ndn::name
Definition: name-component-types.hpp:33
ns3::ndn::L3Protocol
Implementation network-layer of NDN stack.
Definition: ndn-l3-protocol.hpp:81
ns3::ndn::GlobalRoutingHelper::AddOrigin
void AddOrigin(const std::string &prefix, Ptr< Node > node)
Add ‘prefix’ as origin on ‘node’.
Definition: ndn-global-routing-helper.cpp:178
ns3::ndn::GlobalRoutingHelper::AddOriginsForAll
void AddOriginsForAll()
Add origin to each node based on the node's name (using Names class)
Definition: ndn-global-routing-helper.cpp:205
ndn-l3-protocol.hpp
fib-nexthop.hpp
ndn
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-strategy-choice-helper.hpp:34
ns3::ndn::GlobalRoutingHelper::Install
void Install(Ptr< Node > node)
Install GlobalRouter interface on a node.
Definition: ndn-global-routing-helper.cpp:67