NS-3 based Named Data Networking (NDN) simulator
ndnSIM: NDN, CCN, CCNx, content centric networks
API Documentation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
boost-graph-ndn-global-routing-helper.h
1 /* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2012 University of California, Los Angeles
4  *
5  * This program is free software; you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License version 2 as
7  * published by the Free Software Foundation;
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17  *
18  * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
19  */
20 
21 
22 #ifndef BOOST_GRAPH_NDN_GLOBAL_ROUTING_HELPER_H
23 #define BOOST_GRAPH_NDN_GLOBAL_ROUTING_HELPER_H
24 
26 
27 #include <boost/graph/graph_traits.hpp>
28 #include <boost/graph/properties.hpp>
29 #include <boost/ref.hpp>
30 
31 #include "ns3/ndn-face.h"
32 #include "ns3/ndn-limits.h"
33 #include "ns3/node-list.h"
34 #include "ns3/channel-list.h"
35 #include "../model/ndn-global-router.h"
36 #include <list>
37 #include <map>
38 
39 namespace boost {
40 
41 class NdnGlobalRouterGraph
42 {
43 public:
44  typedef ns3::Ptr< ns3::ndn::GlobalRouter > Vertice;
45  typedef uint16_t edge_property_type;
46  typedef uint32_t vertex_property_type;
47 
48  NdnGlobalRouterGraph ()
49  {
50  for (ns3::NodeList::Iterator node = ns3::NodeList::Begin (); node != ns3::NodeList::End (); node++)
51  {
52  ns3::Ptr<ns3::ndn::GlobalRouter> gr = (*node)->GetObject<ns3::ndn::GlobalRouter> ();
53  if (gr != 0)
54  m_vertices.push_back (gr);
55  }
56 
57  for (ns3::ChannelList::Iterator channel = ns3::ChannelList::Begin (); channel != ns3::ChannelList::End (); channel++)
58  {
59  ns3::Ptr<ns3::ndn::GlobalRouter> gr = (*channel)->GetObject<ns3::ndn::GlobalRouter> ();
60  if (gr != 0)
61  m_vertices.push_back (gr);
62  }
63  }
64 
65  const std::list< Vertice > &
66  GetVertices () const
67  {
68  return m_vertices;
69  }
70 
71 public:
72  std::list< Vertice > m_vertices;
73 };
74 
75 
76 class ndn_global_router_graph_category :
77  public virtual vertex_list_graph_tag,
78  public virtual incidence_graph_tag
79 {
80 };
81 
82 
83 template<>
84 struct graph_traits< NdnGlobalRouterGraph >
85 {
86  // Graph concept
87  typedef NdnGlobalRouterGraph::Vertice vertex_descriptor;
88  typedef ns3::ndn::GlobalRouter::Incidency edge_descriptor;
89  typedef directed_tag directed_category;
90  typedef disallow_parallel_edge_tag edge_parallel_category;
91  typedef ndn_global_router_graph_category traversal_category;
92 
93  // VertexList concept
94  typedef std::list< vertex_descriptor >::const_iterator vertex_iterator;
95  typedef size_t vertices_size_type;
96 
97  // AdjacencyGraph concept
98  typedef ns3::ndn::GlobalRouter::IncidencyList::iterator out_edge_iterator;
99  typedef size_t degree_size_type;
100 
101  // typedef size_t edges_size_type;
102 };
103 
104 } // namespace boost
105 
106 namespace boost
107 {
108 
109 inline
110 graph_traits< NdnGlobalRouterGraph >::vertex_descriptor
111 source(
112  graph_traits< NdnGlobalRouterGraph >::edge_descriptor e,
113  const NdnGlobalRouterGraph& g)
114 {
115  return e.get<0> ();
116 }
117 
118 inline
119 graph_traits< NdnGlobalRouterGraph >::vertex_descriptor
120 target(
121  graph_traits< NdnGlobalRouterGraph >::edge_descriptor e,
122  const NdnGlobalRouterGraph& g)
123 {
124  return e.get<2> ();
125 }
126 
127 inline
128 std::pair< graph_traits< NdnGlobalRouterGraph >::vertex_iterator,
129  graph_traits< NdnGlobalRouterGraph >::vertex_iterator >
130 vertices (const NdnGlobalRouterGraph&g)
131 {
132  return make_pair (g.GetVertices ().begin (), g.GetVertices ().end ());
133 }
134 
135 inline
136 graph_traits< NdnGlobalRouterGraph >::vertices_size_type
137 num_vertices(const NdnGlobalRouterGraph &g)
138 {
139  return g.GetVertices ().size ();
140 }
141 
142 
143 inline
144 std::pair< graph_traits< NdnGlobalRouterGraph >::out_edge_iterator,
145  graph_traits< NdnGlobalRouterGraph >::out_edge_iterator >
146 out_edges(
147  graph_traits< NdnGlobalRouterGraph >::vertex_descriptor u,
148  const NdnGlobalRouterGraph& g)
149 {
150  return std::make_pair(u->GetIncidencies ().begin (),
151  u->GetIncidencies ().end ());
152 }
153 
154 inline
155 graph_traits< NdnGlobalRouterGraph >::degree_size_type
156 out_degree(
157  graph_traits< NdnGlobalRouterGraph >::vertex_descriptor u,
158  const NdnGlobalRouterGraph& g)
159 {
160  return u->GetIncidencies ().size ();
161 }
162 
163 
165 // Property maps
166 
167 struct EdgeWeights
168 {
169  EdgeWeights (const NdnGlobalRouterGraph &graph)
170  : m_graph (graph)
171  {
172  }
173 
174 private:
175  const NdnGlobalRouterGraph &m_graph;
176 };
177 
178 
179 struct VertexIds
180 {
181  VertexIds (const NdnGlobalRouterGraph &graph)
182  : m_graph (graph)
183  {
184  }
185 
186 private:
187  const NdnGlobalRouterGraph &m_graph;
188 };
189 
190 template<>
191 struct property_map< NdnGlobalRouterGraph, edge_weight_t >
192 {
193  typedef const EdgeWeights const_type;
194  typedef EdgeWeights type;
195 };
196 
197 template<>
198 struct property_map< NdnGlobalRouterGraph, vertex_index_t >
199 {
200  typedef const VertexIds const_type;
201  typedef VertexIds type;
202 };
203 
204 
205 template<>
206 struct property_traits< EdgeWeights >
207 {
208  // Metric property map
209  typedef tuple< ns3::Ptr<ns3::ndn::Face>, uint16_t, double > value_type;
210  typedef tuple< ns3::Ptr<ns3::ndn::Face>, uint16_t, double > reference;
211  typedef ns3::ndn::GlobalRouter::Incidency key_type;
212  typedef readable_property_map_tag category;
213 };
214 
215 const property_traits< EdgeWeights >::value_type WeightZero (0, 0, 0.0);
216 const property_traits< EdgeWeights >::value_type WeightInf (0, std::numeric_limits<uint16_t>::max (), 0.0);
217 
218 struct WeightCompare :
219  public std::binary_function<property_traits< EdgeWeights >::reference,
220  property_traits< EdgeWeights >::reference,
221  bool>
222 {
223  bool
224  operator () (tuple< ns3::Ptr<ns3::ndn::Face>, uint32_t, double > a,
225  tuple< ns3::Ptr<ns3::ndn::Face>, uint32_t, double > b) const
226  {
227  return a.get<1> () < b.get<1> ();
228  }
229 
230  bool
231  operator () (property_traits< EdgeWeights >::reference a,
232  uint32_t b) const
233  {
234  return a.get<1> () < b;
235  }
236 
237  bool
238  operator () (uint32_t a,
239  uint32_t b) const
240  {
241  return a < b;
242  }
243 
244 };
245 
246 struct WeightCombine :
247  public std::binary_function<uint32_t,
248  property_traits< EdgeWeights >::reference,
249  uint32_t>
250 {
251  uint32_t
252  operator () (uint32_t a, property_traits< EdgeWeights >::reference b) const
253  {
254  return a + b.get<1> ();
255  }
256 
257  tuple< ns3::Ptr<ns3::ndn::Face>, uint32_t, double >
258  operator () (tuple< ns3::Ptr<ns3::ndn::Face>, uint32_t, double > a,
259  property_traits< EdgeWeights >::reference b) const
260  {
261  if (a.get<0> () == 0)
262  return make_tuple (b.get<0> (), a.get<1> () + b.get<1> (), a.get<2> () + b.get<2> ());
263  else
264  return make_tuple (a.get<0> (), a.get<1> () + b.get<1> (), a.get<2> () + b.get<2> ());
265  }
266 };
267 
268 template<>
269 struct property_traits< VertexIds >
270 {
271  // Metric property map
272  typedef uint32_t value_type;
273  typedef uint32_t reference;
274  typedef ns3::Ptr< ns3::ndn::GlobalRouter > key_type;
275  typedef readable_property_map_tag category;
276 };
277 
278 
279 inline EdgeWeights
280 get(edge_weight_t,
281  const NdnGlobalRouterGraph &g)
282 {
283  return EdgeWeights (g);
284 }
285 
286 
287 inline VertexIds
288 get(vertex_index_t,
289  const NdnGlobalRouterGraph &g)
290 {
291  return VertexIds (g);
292 }
293 
294 template<class M, class K, class V>
295 inline void
296 put (reference_wrapper< M > mapp,
297  K a, V p)
298 {
299  mapp.get ()[a] = p;
300 }
301 
302 // void
303 // put (cref< std::map< ns3::Ptr<ns3::ndn::GlobalRouter>, ns3::Ptr<ns3::ndn::GlobalRouter> > > map,
304 
305 inline uint32_t
306 get (const boost::VertexIds&, ns3::Ptr<ns3::ndn::GlobalRouter> &gr)
307 {
308  return gr->GetId ();
309 }
310 
311 inline property_traits< EdgeWeights >::reference
312 get(const boost::EdgeWeights&, ns3::ndn::GlobalRouter::Incidency &edge)
313 {
314  if (edge.get<1> () == 0)
315  return property_traits< EdgeWeights >::reference (0, 0, 0.0);
316  else
317  {
318  ns3::Ptr<ns3::ndn::Limits> limits = edge.get<1> ()->GetObject<ns3::ndn::Limits> ();
319  double delay = 0.0;
320  if (limits != 0) // valid limits object
321  {
322  delay = limits->GetLinkDelay ();
323  }
324  return property_traits< EdgeWeights >::reference (edge.get<1> (), edge.get<1> ()->GetMetric (), delay);
325  }
326 }
327 
328 struct PredecessorsMap :
329  public std::map< ns3::Ptr< ns3::ndn::GlobalRouter >, ns3::Ptr< ns3::ndn::GlobalRouter > >
330 {
331 };
332 
333 template<>
334 struct property_traits< reference_wrapper<PredecessorsMap> >
335 {
336  // Metric property map
337  typedef ns3::Ptr< ns3::ndn::GlobalRouter > value_type;
338  typedef ns3::Ptr< ns3::ndn::GlobalRouter > reference;
339  typedef ns3::Ptr< ns3::ndn::GlobalRouter > key_type;
340  typedef read_write_property_map_tag category;
341 };
342 
343 
344 struct DistancesMap :
345  public std::map< ns3::Ptr< ns3::ndn::GlobalRouter >, tuple< ns3::Ptr<ns3::ndn::Face>, uint32_t, double > >
346 {
347 };
348 
349 template<>
350 struct property_traits< reference_wrapper<DistancesMap> >
351 {
352  // Metric property map
353  typedef tuple< ns3::Ptr<ns3::ndn::Face>, uint32_t, double > value_type;
354  typedef tuple< ns3::Ptr<ns3::ndn::Face>, uint32_t, double > reference;
355  typedef ns3::Ptr< ns3::ndn::GlobalRouter > key_type;
356  typedef read_write_property_map_tag category;
357 };
358 
359 inline tuple< ns3::Ptr<ns3::ndn::Face>, uint32_t, double >
360 get (DistancesMap &map, ns3::Ptr<ns3::ndn::GlobalRouter> key)
361 {
362  boost::DistancesMap::iterator i = map.find (key);
363  if (i == map.end ())
364  return tuple< ns3::Ptr<ns3::ndn::Face>, uint32_t, double > (0, std::numeric_limits<uint32_t>::max (), 0.0);
365  else
366  return i->second;
367 }
368 
369 } // namespace boost
370 
372 
373 #endif // BOOST_GRAPH_NDN_GLOBAL_ROUTING_HELPER_H
Class representing global router interface for ndnSIM.
boost::tuple< Ptr< GlobalRouter >, Ptr< Face >, Ptr< GlobalRouter > > Incidency
Graph edge.