Initial support for route calculations with Boost.Graph library (BGL)
diff --git a/helper/boost-graph-ccnx-global-routing-helper.h b/helper/boost-graph-ccnx-global-routing-helper.h
new file mode 100644
index 0000000..3711278
--- /dev/null
+++ b/helper/boost-graph-ccnx-global-routing-helper.h
@@ -0,0 +1,307 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+
+#ifndef BOOST_GRAPH_CCNX_GLOBAL_ROUTING_HELPER_H
+#define BOOST_GRAPH_CCNX_GLOBAL_ROUTING_HELPER_H
+
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/properties.hpp>
+
+#include "ns3/node-list.h"
+#include "ns3/channel-list.h"
+#include "../model/ccnx-global-router.h"
+#include <list>
+#include <map>
+
+namespace boost
+{
+
+class CcnxGlobalRouterGraph
+{
+public:
+ typedef ns3::Ptr< ns3::CcnxGlobalRouter > Vertice;
+ typedef uint16_t edge_property_type;
+ typedef uint32_t vertex_property_type;
+
+ CcnxGlobalRouterGraph ()
+ {
+ for (ns3::NodeList::Iterator node = ns3::NodeList::Begin (); node != ns3::NodeList::End (); node++)
+ {
+ ns3::Ptr<ns3::CcnxGlobalRouter> gr = (*node)->GetObject<ns3::CcnxGlobalRouter> ();
+ if (gr != 0)
+ m_vertices.push_back (gr);
+ }
+
+ for (ns3::ChannelList::Iterator channel = ns3::ChannelList::Begin (); channel != ns3::ChannelList::End (); channel++)
+ {
+ ns3::Ptr<ns3::CcnxGlobalRouter> gr = (*channel)->GetObject<ns3::CcnxGlobalRouter> ();
+ if (gr != 0)
+ m_vertices.push_back (gr);
+ }
+ }
+
+ const std::list< Vertice > &
+ GetVertices () const
+ {
+ return m_vertices;
+ }
+
+public:
+ std::list< Vertice > m_vertices;
+};
+
+
+class ccnx_global_router_graph_category :
+ public virtual vertex_list_graph_tag,
+ public virtual incidence_graph_tag
+{
+};
+
+
+template<>
+struct graph_traits< CcnxGlobalRouterGraph >
+{
+ // Graph concept
+ typedef CcnxGlobalRouterGraph::Vertice vertex_descriptor;
+ typedef ns3::CcnxGlobalRouter::Incidency edge_descriptor;
+ typedef directed_tag directed_category;
+ typedef disallow_parallel_edge_tag edge_parallel_category;
+ typedef ccnx_global_router_graph_category traversal_category;
+
+ // VertexList concept
+ typedef std::list< vertex_descriptor >::const_iterator vertex_iterator;
+ typedef size_t vertices_size_type;
+
+ // AdjacencyGraph concept
+ typedef ns3::CcnxGlobalRouter::IncidencyList::iterator out_edge_iterator;
+ typedef size_t degree_size_type;
+
+ // typedef size_t edges_size_type;
+};
+
+} // namespace boost
+
+namespace boost
+{
+
+inline
+graph_traits< CcnxGlobalRouterGraph >::vertex_descriptor
+source(
+ graph_traits< CcnxGlobalRouterGraph >::edge_descriptor e,
+ const CcnxGlobalRouterGraph& g)
+{
+ return e.get<0> ();
+}
+
+inline
+graph_traits< CcnxGlobalRouterGraph >::vertex_descriptor
+target(
+ graph_traits< CcnxGlobalRouterGraph >::edge_descriptor e,
+ const CcnxGlobalRouterGraph& g)
+{
+ return e.get<2> ();
+}
+
+inline
+std::pair< graph_traits< CcnxGlobalRouterGraph >::vertex_iterator,
+ graph_traits< CcnxGlobalRouterGraph >::vertex_iterator >
+vertices (const CcnxGlobalRouterGraph&g)
+{
+ return make_pair (g.GetVertices ().begin (), g.GetVertices ().end ());
+}
+
+inline
+graph_traits< CcnxGlobalRouterGraph >::vertices_size_type
+num_vertices(const CcnxGlobalRouterGraph &g)
+{
+ return g.GetVertices ().size ();
+}
+
+
+inline
+std::pair< graph_traits< CcnxGlobalRouterGraph >::out_edge_iterator,
+ graph_traits< CcnxGlobalRouterGraph >::out_edge_iterator >
+out_edges(
+ graph_traits< CcnxGlobalRouterGraph >::vertex_descriptor u,
+ const CcnxGlobalRouterGraph& g)
+{
+ return std::make_pair(u->GetIncidencies ().begin (),
+ u->GetIncidencies ().end ());
+}
+
+inline
+graph_traits< CcnxGlobalRouterGraph >::degree_size_type
+out_degree(
+ graph_traits< CcnxGlobalRouterGraph >::vertex_descriptor u,
+ const CcnxGlobalRouterGraph& g)
+{
+ return u->GetIncidencies ().size ();
+}
+
+
+//////////////////////////////////////////////////////////////
+// Property maps
+
+struct EdgeWeights
+{
+ EdgeWeights (const CcnxGlobalRouterGraph &graph)
+ : m_graph (graph)
+ {
+ }
+
+private:
+ const CcnxGlobalRouterGraph &m_graph;
+};
+
+
+struct VertexIds
+{
+ VertexIds (const CcnxGlobalRouterGraph &graph)
+ : m_graph (graph)
+ {
+ }
+
+private:
+ const CcnxGlobalRouterGraph &m_graph;
+};
+
+template<>
+struct property_map< CcnxGlobalRouterGraph, edge_weight_t >
+{
+ typedef const EdgeWeights const_type;
+ typedef EdgeWeights type;
+};
+
+template<>
+struct property_map< CcnxGlobalRouterGraph, vertex_index_t >
+{
+ typedef const VertexIds const_type;
+ typedef VertexIds type;
+};
+
+
+template<>
+struct property_traits< EdgeWeights >
+{
+ // Metric property map
+ typedef uint16_t value_type;
+ typedef uint16_t reference;
+ typedef ns3::CcnxGlobalRouter::Incidency key_type;
+ typedef readable_property_map_tag category;
+};
+
+template<>
+struct property_traits< VertexIds >
+{
+ // Metric property map
+ typedef uint32_t value_type;
+ typedef uint32_t reference;
+ typedef ns3::Ptr< ns3::CcnxGlobalRouter > key_type;
+ typedef readable_property_map_tag category;
+};
+
+
+inline EdgeWeights
+get(edge_weight_t,
+ const CcnxGlobalRouterGraph &g)
+{
+ return EdgeWeights (g);
+}
+
+
+inline VertexIds
+get(vertex_index_t,
+ const CcnxGlobalRouterGraph &g)
+{
+ return VertexIds (g);
+}
+
+template<class K, class V>
+inline void
+put (std::map<K,V> &mapp,
+ K a, V p)
+{
+ mapp[a] = p;
+}
+
+// void
+// put (cref< std::map< ns3::Ptr<ns3::CcnxGlobalRouter>, ns3::Ptr<ns3::CcnxGlobalRouter> > > map,
+
+uint32_t
+get (const boost::VertexIds&, ns3::Ptr<ns3::CcnxGlobalRouter> &gr)
+{
+ return gr->GetId ();
+}
+
+inline uint16_t
+get(const boost::EdgeWeights&, ns3::CcnxGlobalRouter::Incidency &edge)
+{
+ if (edge.get<1> () == 0)
+ return 0;
+ else
+ return edge.get<1> ()->GetMetric ();
+}
+
+
+struct PredecessorsMap :
+ public std::map< ns3::Ptr< ns3::CcnxGlobalRouter >, ns3::Ptr< ns3::CcnxGlobalRouter > >
+{
+};
+
+template<>
+struct property_traits< PredecessorsMap >
+{
+ // Metric property map
+ typedef ns3::Ptr< ns3::CcnxGlobalRouter > value_type;
+ typedef ns3::Ptr< ns3::CcnxGlobalRouter > reference;
+ typedef ns3::Ptr< ns3::CcnxGlobalRouter > key_type;
+ typedef read_write_property_map_tag category;
+};
+
+
+struct DistancesMap :
+ public std::map< ns3::Ptr< ns3::CcnxGlobalRouter >, uint32_t >
+{
+};
+
+template<>
+struct property_traits< DistancesMap >
+{
+ // Metric property map
+ typedef uint32_t value_type;
+ typedef uint32_t reference;
+ typedef ns3::Ptr< ns3::CcnxGlobalRouter > key_type;
+ typedef read_write_property_map_tag category;
+};
+
+inline uint32_t
+get (DistancesMap &map, ns3::Ptr<ns3::CcnxGlobalRouter> key)
+{
+ boost::DistancesMap::iterator i = map.find (key);
+ if (i == map.end ())
+ return std::numeric_limits<uint32_t>::max ();
+ else
+ return i->second;
+}
+
+} // namespace boost
+
+#endif // BOOST_GRAPH_CCNX_GLOBAL_ROUTING_HELPER_H
diff --git a/helper/ccnx-global-routing-helper.cc b/helper/ccnx-global-routing-helper.cc
new file mode 100644
index 0000000..63e202e
--- /dev/null
+++ b/helper/ccnx-global-routing-helper.cc
@@ -0,0 +1,258 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2011 UCLA
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "ccnx-global-routing-helper.h"
+
+#include "ns3/ccnx.h"
+#include "../model/ccnx-net-device-face.h"
+#include "../model/ccnx-global-router.h"
+#include "ns3/ccnx-name-components.h"
+
+#include "ns3/node.h"
+#include "ns3/net-device.h"
+#include "ns3/channel.h"
+#include "ns3/log.h"
+#include "ns3/assert.h"
+#include "ns3/names.h"
+#include "ns3/node-list.h"
+#include "ns3/channel-list.h"
+
+#include <boost/lexical_cast.hpp>
+#include "boost-graph-ccnx-global-routing-helper.h"
+
+NS_LOG_COMPONENT_DEFINE ("CcnxGlobalRoutingHelper");
+
+using namespace std;
+using namespace boost;
+
+namespace ns3 {
+
+void
+CcnxGlobalRoutingHelper::Install (Ptr<Node> node)
+{
+ NS_LOG_LOGIC ("Node: " << node->GetId ());
+
+ Ptr<Ccnx> ccnx = node->GetObject<Ccnx> ();
+ NS_ASSERT_MSG (ccnx != 0, "Cannot install CcnxGlobalRoutingHelper before Ccnx is installed on a node");
+
+ Ptr<CcnxGlobalRouter> gr = node->GetObject<CcnxGlobalRouter> ();
+ if (gr != 0)
+ {
+ NS_LOG_DEBUG ("CcnxGlobalRouter is already installed: " << gr);
+ return; // already installed
+ }
+
+ gr = CreateObject<CcnxGlobalRouter> ();
+ node->AggregateObject (gr);
+
+ for (uint32_t faceId = 0; faceId < ccnx->GetNFaces (); faceId++)
+ {
+ Ptr<CcnxNetDeviceFace> face = DynamicCast<CcnxNetDeviceFace> (ccnx->GetFace (faceId));
+ if (face == 0)
+ {
+ NS_LOG_DEBUG ("Skipping non-netdevice face");
+ continue;
+ }
+
+ Ptr<NetDevice> nd = face->GetNetDevice ();
+ if (nd == 0)
+ {
+ NS_LOG_DEBUG ("Not a NetDevice associated with CcnxNetDeviceFace");
+ continue;
+ }
+
+ Ptr<Channel> ch = nd->GetChannel ();
+
+ if (ch == 0)
+ {
+ NS_LOG_DEBUG ("Channel is not associated with NetDevice");
+ continue;
+ }
+
+ if (ch->GetNDevices () == 2) // e.g., point-to-point channel
+ {
+ for (uint32_t deviceId = 0; deviceId < ch->GetNDevices (); deviceId ++)
+ {
+ Ptr<NetDevice> otherSide = ch->GetDevice (deviceId);
+ if (nd == otherSide) continue;
+
+ Ptr<Node> otherNode = otherSide->GetNode ();
+ NS_ASSERT (otherNode != 0);
+
+ Ptr<CcnxGlobalRouter> otherGr = otherNode->GetObject<CcnxGlobalRouter> ();
+ if (otherGr == 0)
+ {
+ Install (otherNode);
+ }
+ otherGr = otherNode->GetObject<CcnxGlobalRouter> ();
+ NS_ASSERT (otherGr != 0);
+ gr->AddIncidency (face, otherGr);
+ }
+ }
+ else
+ {
+ Ptr<CcnxGlobalRouter> grChannel = ch->GetObject<CcnxGlobalRouter> ();
+ if (grChannel == 0)
+ {
+ Install (ch);
+ }
+ grChannel = ch->GetObject<CcnxGlobalRouter> ();
+
+ gr->AddIncidency (0, grChannel);
+ }
+ }
+}
+
+void
+CcnxGlobalRoutingHelper::Install (Ptr<Channel> channel)
+{
+ NS_LOG_LOGIC ("Channel: " << channel->GetId ());
+
+ Ptr<CcnxGlobalRouter> gr = channel->GetObject<CcnxGlobalRouter> ();
+ if (gr != 0)
+ return;
+
+ gr = CreateObject<CcnxGlobalRouter> ();
+ channel->AggregateObject (gr);
+
+ for (uint32_t deviceId = 0; deviceId < channel->GetNDevices (); deviceId ++)
+ {
+ Ptr<NetDevice> dev = channel->GetDevice (deviceId);
+
+ Ptr<Node> node = dev->GetNode ();
+ NS_ASSERT (node != 0);
+
+ Ptr<CcnxGlobalRouter> grOther = node->GetObject<CcnxGlobalRouter> ();
+ if (grOther == 0)
+ {
+ Install (node);
+ }
+ grOther = node->GetObject<CcnxGlobalRouter> ();
+ NS_ASSERT (grOther != 0);
+
+ gr->AddIncidency (0, grOther);
+ }
+}
+
+void
+CcnxGlobalRoutingHelper::AddOrigin (const std::string &prefix, Ptr<Node> node)
+{
+ Ptr<CcnxGlobalRouter> gr = node->GetObject<CcnxGlobalRouter> ();
+ NS_ASSERT_MSG (gr != 0,
+ "CcnxGlobalRouter is not installed on the node");
+
+ Ptr<CcnxNameComponents> name = Create<CcnxNameComponents> (boost::lexical_cast<CcnxNameComponents> (prefix));
+ gr->AddLocalPrefix (name);
+}
+
+void
+CcnxGlobalRoutingHelper::AddOrigin (const std::string &prefix, const std::string &nodeName)
+{
+ Ptr<Node> node = Names::Find<Node> (nodeName);
+ NS_ASSERT_MSG (node != 0, nodeName << "is not a Node");
+
+ AddOrigin (prefix, node);
+}
+
+} // namespace ns3
+
+
+
+#include <boost/concept/assert.hpp>
+#include <boost/graph/graph_concepts.hpp>
+// #include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/dijkstra_shortest_paths.hpp>
+
+namespace ns3 {
+
+void
+CcnxGlobalRoutingHelper::CalculateRoutes ()
+{
+ BOOST_CONCEPT_ASSERT(( VertexListGraphConcept< CcnxGlobalRouterGraph > ));
+ BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept< CcnxGlobalRouterGraph > ));
+ // BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept< CcnxGlobalRouterGraph,
+ // graph_traits < CcnxGlobalRouterGraph >::edge_descriptor > ));
+ // BOOST_CONCEPT_ASSERT(( PropertyGraphConcept< CcnxGlobalRouterGraph,
+ // graph_traits < CcnxGlobalRouterGraph >::edge_descriptor,
+ // edge_weight_t> ));
+ // BOOST_CONCEPT_ASSERT(( PropertyMapConcept< CcnxGlobalRouterGraph, edge_weight_t,
+ // graph_traits < CcnxGlobalRouterGraph >::edge_descriptor> ));
+
+
+ CcnxGlobalRouterGraph graph;
+ Ptr<CcnxGlobalRouter> source = (*NodeList::Begin ())->GetObject<CcnxGlobalRouter> ();
+
+ typedef graph_traits < CcnxGlobalRouterGraph >::vertex_descriptor vertex_descriptor;
+
+ PredecessorsMap predecessors;
+ DistancesMap distances;
+ // std::map< vertex_descriptor, int > distances;
+ // std::vector<uint32_t> d (num_vertices (graph));
+ // std::vector<int> distances;
+ // std::map< vertex_descriptor, std::
+
+ dijkstra_shortest_paths (graph, source,
+ predecessor_map (predecessors)
+ .
+ distance_map (distances)
+ );
+
+ // BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<CcnxGlobalRouterGraph> ));
+ // BOOST_CONCEPT_ASSERT(( MutableGraphConcept<CcnxGlobalRouterGraph> ));
+
+ // typedef adjacency_list < listS, vecS, undirectedS, no_property, property < edge_weight_t, uint16_t > > Graph;
+ // typedef Graph::vertex_descriptor Vertex;
+
+ // class Graph
+ // {
+ // public:
+ // typedef Ptr<CcnxGlobalRouter> vertex_descriptor;
+ // typedef pair< Ptr<CcnxGlobalRouter>, Ptr<CcnxGlobalRouter> > edge_descriptor;
+ // typedef directed_tag directed_category;
+ // typedef disallow_parallel_edge_tag edge_parallel_category;
+ // typedef adjacency_graph_tag traversal_category;
+
+ // typedef CcnxGlobalRouter::Incidency adjacency_iterator;
+
+ // // null_vertex() ???
+ // // adjacent_vertices(v, g) ???
+ // };
+
+ // Graph graph;
+
+ // for (NodeList::Iterator node = NodeList::Begin (); node != NodeList::End (); node++)
+ // {
+ // Ptr<CcnxGlobalRouter> gr = (*node)->GetObject<CcnxGlobalRouter> ();
+ // if (gr == 0)
+ // continue;
+
+ // for (CcnxGlobalRouter::IncidencyList::const_iterator i = gr->GetIncidencies ().begin ();
+ // i != gr->GetIncidencies ().end ();
+ // i++)
+ // {
+ // add_edge (gr, i->get<1> (), 10, graph);
+ // }
+ // break;
+ // }
+
+}
+
+
+}
diff --git a/helper/ccnx-global-routing-helper.h b/helper/ccnx-global-routing-helper.h
new file mode 100644
index 0000000..0012d25
--- /dev/null
+++ b/helper/ccnx-global-routing-helper.h
@@ -0,0 +1,52 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2011 UCLA
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef CCNX_GLOBAL_ROUTING_HELPER_H
+#define CCNX_GLOBAL_ROUTING_HELPER_H
+
+#include "ns3/ptr.h"
+
+namespace ns3 {
+
+class Node;
+class Channel;
+
+class CcnxGlobalRoutingHelper
+{
+public:
+ void
+ Install (Ptr<Node> node);
+
+ void
+ Install (Ptr<Channel> channel);
+
+ void
+ AddOrigin (const std::string &prefix, Ptr<Node> node);
+
+ void
+ AddOrigin (const std::string &prefix, const std::string &nodeName);
+
+ void
+ CalculateRoutes ();
+};
+
+}
+
+#endif // CCNX_GLOBAL_ROUTING_HELPER_H