Project

General

Profile

Bug #2535 » ndn-global-routing-helper.cpp

Full NDN Global Routing Helper File - Christian Kreuzberger, 02/18/2015 05:38 AM

 
1
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2
/**
3
 * Copyright (c) 2011-2015  Regents of the University of California.
4
 *
5
 * This file is part of ndnSIM. See AUTHORS for complete list of ndnSIM authors and
6
 * contributors.
7
 *
8
 * ndnSIM is free software: you can redistribute it and/or modify it under the terms
9
 * of the GNU General Public License as published by the Free Software Foundation,
10
 * either version 3 of the License, or (at your option) any later version.
11
 *
12
 * ndnSIM is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
13
 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
14
 * PURPOSE.  See the GNU General Public License for more details.
15
 *
16
 * You should have received a copy of the GNU General Public License along with
17
 * ndnSIM, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
18
 **/
19

    
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

    
26
#include "ndn-global-routing-helper.hpp"
27

    
28
#include "model/ndn-l3-protocol.hpp"
29
#include "helper/ndn-fib-helper.hpp"
30
#include "model/ndn-net-device-face.hpp"
31
#include "model/ndn-global-router.hpp"
32

    
33
#include "daemon/table/fib.hpp"
34
#include "daemon/fw/forwarder.hpp"
35
#include "daemon/table/fib-entry.hpp"
36
#include "daemon/table/fib-nexthop.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 "boost-graph-ndn-global-routing-helper.hpp"
56

    
57
#include <math.h>
58

    
59
NS_LOG_COMPONENT_DEFINE("ndn.GlobalRoutingHelper");
60

    
61
namespace ns3 {
62
namespace ndn {
63

    
64
void
65
GlobalRoutingHelper::Install(Ptr<Node> node)
66
{
67
  NS_LOG_LOGIC("Node: " << node->GetId());
68

    
69
  Ptr<L3Protocol> ndn = node->GetObject<L3Protocol>();
70
  NS_ASSERT_MSG(ndn != 0, "Cannot install GlobalRoutingHelper before Ndn is installed on a node");
71

    
72
  Ptr<GlobalRouter> gr = node->GetObject<GlobalRouter>();
73
  if (gr != 0) {
74
    NS_LOG_DEBUG("GlobalRouter is already installed: " << gr);
75
    return; // already installed
76
  }
77

    
78
  gr = CreateObject<GlobalRouter>();
79
  node->AggregateObject(gr);
80

    
81
  for (auto& i : ndn->getForwarder()->getFaceTable()) {
82
    shared_ptr<NetDeviceFace> face = std::dynamic_pointer_cast<NetDeviceFace>(i);
83
    if (face == 0) {
84
      NS_LOG_DEBUG("Skipping non-netdevice face");
85
      continue;
86
    }
87

    
88
    Ptr<NetDevice> nd = face->GetNetDevice();
89
    if (nd == 0) {
90
      NS_LOG_DEBUG("Not a NetDevice associated with NetDeviceFace");
91
      continue;
92
    }
93

    
94
    Ptr<Channel> ch = nd->GetChannel();
95

    
96
    if (ch == 0) {
97
      NS_LOG_DEBUG("Channel is not associated with NetDevice");
98
      continue;
99
    }
100

    
101
    if (ch->GetNDevices() == 2) // e.g., point-to-point channel
102
    {
103
      for (uint32_t deviceId = 0; deviceId < ch->GetNDevices(); deviceId++) {
104
        Ptr<NetDevice> otherSide = ch->GetDevice(deviceId);
105
        if (nd == otherSide)
106
          continue;
107

    
108
        Ptr<Node> otherNode = otherSide->GetNode();
109
        NS_ASSERT(otherNode != 0);
110

    
111
        Ptr<GlobalRouter> otherGr = otherNode->GetObject<GlobalRouter>();
112
        if (otherGr == 0) {
113
          Install(otherNode);
114
        }
115
        otherGr = otherNode->GetObject<GlobalRouter>();
116
        NS_ASSERT(otherGr != 0);
117
        gr->AddIncidency(face, otherGr);
118
      }
119
    }
120
    else {
121
      Ptr<GlobalRouter> grChannel = ch->GetObject<GlobalRouter>();
122
      if (grChannel == 0) {
123
        Install(ch);
124
      }
125
      grChannel = ch->GetObject<GlobalRouter>();
126

    
127
      gr->AddIncidency(face, grChannel);
128
    }
129
  }
130
}
131

    
132
void
133
GlobalRoutingHelper::Install(Ptr<Channel> channel)
134
{
135
  NS_LOG_LOGIC("Channel: " << channel->GetId());
136

    
137
  Ptr<GlobalRouter> gr = channel->GetObject<GlobalRouter>();
138
  if (gr != 0)
139
    return;
140

    
141
  gr = CreateObject<GlobalRouter>();
142
  channel->AggregateObject(gr);
143

    
144
  for (uint32_t deviceId = 0; deviceId < channel->GetNDevices(); deviceId++) {
145
    Ptr<NetDevice> dev = channel->GetDevice(deviceId);
146

    
147
    Ptr<Node> node = dev->GetNode();
148
    NS_ASSERT(node != 0);
149

    
150
    Ptr<GlobalRouter> grOther = node->GetObject<GlobalRouter>();
151
    if (grOther == 0) {
152
      Install(node);
153
    }
154
    grOther = node->GetObject<GlobalRouter>();
155
    NS_ASSERT(grOther != 0);
156

    
157
    gr->AddIncidency(0, grOther);
158
  }
159
}
160

    
161
void
162
GlobalRoutingHelper::Install(const NodeContainer& nodes)
163
{
164
  for (NodeContainer::Iterator node = nodes.Begin(); node != nodes.End(); node++) {
165
    Install(*node);
166
  }
167
}
168

    
169
void
170
GlobalRoutingHelper::InstallAll()
171
{
172
  Install(NodeContainer::GetGlobal());
173
}
174

    
175
void
176
GlobalRoutingHelper::AddOrigin(const std::string& prefix, Ptr<Node> node)
177
{
178
  Ptr<GlobalRouter> gr = node->GetObject<GlobalRouter>();
179
  NS_ASSERT_MSG(gr != 0, "GlobalRouter is not installed on the node");
180

    
181
  auto name = make_shared<Name>(prefix);
182
  gr->AddLocalPrefix(name);
183
}
184

    
185
void
186
GlobalRoutingHelper::AddOrigins(const std::string& prefix, const NodeContainer& nodes)
187
{
188
  for (NodeContainer::Iterator node = nodes.Begin(); node != nodes.End(); node++) {
189
    AddOrigin(prefix, *node);
190
  }
191
}
192

    
193
void
194
GlobalRoutingHelper::AddOrigin(const std::string& prefix, const std::string& nodeName)
195
{
196
  Ptr<Node> node = Names::Find<Node>(nodeName);
197
  NS_ASSERT_MSG(node != 0, nodeName << "is not a Node");
198

    
199
  AddOrigin(prefix, node);
200
}
201

    
202
void
203
GlobalRoutingHelper::AddOriginsForAll()
204
{
205
  for (NodeList::Iterator node = NodeList::Begin(); node != NodeList::End(); node++) {
206
    Ptr<GlobalRouter> gr = (*node)->GetObject<GlobalRouter>();
207
    std::string name = Names::FindName(*node);
208

    
209
    if (gr != 0 && !name.empty()) {
210
      AddOrigin("/" + name, *node);
211
    }
212
  }
213
}
214

    
215
void
216
GlobalRoutingHelper::CalculateRoutes()
217
{
218
  /**
219
   * Implementation of route calculation is heavily based on Boost Graph Library
220
   * See http://www.boost.org/doc/libs/1_49_0/libs/graph/doc/table_of_contents.html for more details
221
   */
222

    
223
  BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept<boost::NdnGlobalRouterGraph>));
224
  BOOST_CONCEPT_ASSERT((boost::IncidenceGraphConcept<boost::NdnGlobalRouterGraph>));
225

    
226
  boost::NdnGlobalRouterGraph graph;
227
  // typedef graph_traits < NdnGlobalRouterGraph >::vertex_descriptor vertex_descriptor;
228

    
229
  // For now we doing Dijkstra for every node.  Can be replaced with Bellman-Ford or Floyd-Warshall.
230
  // Other algorithms should be faster, but they need additional EdgeListGraph concept provided by
231
  // the graph, which
232
  // is not obviously how implement in an efficient manner
233
  for (NodeList::Iterator node = NodeList::Begin(); node != NodeList::End(); node++) {
234
    Ptr<GlobalRouter> source = (*node)->GetObject<GlobalRouter>();
235
    if (source == 0) {
236
      NS_LOG_DEBUG("Node " << (*node)->GetId() << " does not export GlobalRouter interface");
237
      continue;
238
    }
239

    
240
    boost::DistancesMap distances;
241

    
242
    dijkstra_shortest_paths(graph, source,
243
                            // predecessor_map (boost::ref(predecessors))
244
                            // .
245
                            distance_map(boost::ref(distances))
246
                              .distance_inf(boost::WeightInf)
247
                              .distance_zero(boost::WeightZero)
248
                              .distance_compare(boost::WeightCompare())
249
                              .distance_combine(boost::WeightCombine()));
250

    
251
    // NS_LOG_DEBUG (predecessors.size () << ", " << distances.size ());
252

    
253
    Ptr<L3Protocol> L3protocol = (*node)->GetObject<L3Protocol>();
254
    shared_ptr<nfd::Forwarder> forwarder = L3protocol->getForwarder();
255

    
256
    NS_LOG_DEBUG("Reachability from Node: " << source->GetObject<Node>()->GetId());
257
    for (const auto& dist : distances) {
258
      if (dist.first == source)
259
        continue;
260
      else {
261
        // cout << "  Node " << dist.first->GetObject<Node> ()->GetId ();
262
        if (std::get<0>(dist.second) == 0) {
263
          // cout << " is unreachable" << endl;
264
        }
265
        else {
266
          for (const auto& prefix : dist.first->GetLocalPrefixes()) {
267
            NS_LOG_DEBUG(" prefix " << prefix << " reachable via face " << *std::get<0>(dist.second)
268
                         << " with distance " << std::get<1>(dist.second) << " with delay "
269
                         << std::get<2>(dist.second));
270

    
271
            FibHelper::AddRoute(*node, *prefix, std::get<0>(dist.second),
272
                                std::get<1>(dist.second));
273
          }
274
        }
275
      }
276
    }
277
  }
278
}
279

    
280
void
281
GlobalRoutingHelper::CalculateAllPossibleRoutes()
282
{
283
  /**
284
   * Implementation of route calculation is heavily based on Boost Graph Library
285
   * See http://www.boost.org/doc/libs/1_49_0/libs/graph/doc/table_of_contents.html for more details
286
   */
287

    
288
  BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept<boost::NdnGlobalRouterGraph>));
289
  BOOST_CONCEPT_ASSERT((boost::IncidenceGraphConcept<boost::NdnGlobalRouterGraph>));
290

    
291
  boost::NdnGlobalRouterGraph graph;
292
  // typedef graph_traits < NdnGlobalRouterGraph >::vertex_descriptor vertex_descriptor;
293

    
294
  // For now we doing Dijkstra for every node.  Can be replaced with Bellman-Ford or Floyd-Warshall.
295
  // Other algorithms should be faster, but they need additional EdgeListGraph concept provided by
296
  // the graph, which
297
  // is not obviously how implement in an efficient manner
298
  for (NodeList::Iterator node = NodeList::Begin(); node != NodeList::End(); node++) {
299
    Ptr<GlobalRouter> source = (*node)->GetObject<GlobalRouter>();
300
    if (source == 0) {
301
      NS_LOG_DEBUG("Node " << (*node)->GetId() << " does not export GlobalRouter interface");
302
      continue;
303
    }
304

    
305
    Ptr<L3Protocol> L3protocol = (*node)->GetObject<L3Protocol>();
306
    shared_ptr<nfd::Forwarder> forwarder = L3protocol->getForwarder();
307

    
308
    NS_LOG_DEBUG("Reachability from Node: " << source->GetObject<Node>()->GetId() << " ("
309
                                            << Names::FindName(source->GetObject<Node>()) << ")");
310

    
311
    Ptr<L3Protocol> l3 = source->GetObject<L3Protocol>();
312
    NS_ASSERT(l3 != 0);
313

    
314
    // remember interface statuses
315
    int faceNumber = 0;
316
    std::vector<uint16_t> originalMetric(uint32_t(l3->getForwarder()->getFaceTable().size()));
317
    for (auto& i : l3->getForwarder()->getFaceTable()) {
318
      shared_ptr<Face> nfdFace = std::dynamic_pointer_cast<Face>(i);
319
      originalMetric[uint32_t(faceNumber)] = nfdFace->getMetric();
320
      nfdFace->setMetric(std::numeric_limits<uint16_t>::max() - 1);
321

    
322
      faceNumber++;
323
      // value std::numeric_limits<uint16_t>::max () MUST NOT be used (reserved)
324
    }
325

    
326
    faceNumber = 0;
327
    for (auto& k : l3->getForwarder()->getFaceTable()) {
328
      faceNumber++;
329
      shared_ptr<NetDeviceFace> face = std::dynamic_pointer_cast<NetDeviceFace>(k);
330
      if (face == 0) {
331
        NS_LOG_DEBUG("Skipping non-netdevice face");
332
        continue;
333
      }
334

    
335
      // enabling only faceId
336
      face->setMetric(originalMetric[uint32_t(faceNumber)-1]);
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
    faceNumber = 0;
384
    for (auto& i : l3->getForwarder()->getFaceTable()) {
385
      shared_ptr<Face> face = std::dynamic_pointer_cast<Face>(i);
386
      face->setMetric(originalMetric[faceNumber]);
387
      faceNumber++;
388
    }
389
  }
390
}
391

    
392
} // namespace ndn
393
} // namespace ns3
(2-2/3)