BGL implementation for ccnx global routing seems to work. Need more debugging
diff --git a/helper/boost-graph-ccnx-global-routing-helper.h b/helper/boost-graph-ccnx-global-routing-helper.h
index 3711278..ef04fac 100644
--- a/helper/boost-graph-ccnx-global-routing-helper.h
+++ b/helper/boost-graph-ccnx-global-routing-helper.h
@@ -24,7 +24,9 @@
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
+#include <boost/ref.hpp>
+#include "ns3/ccnx-face.h"
#include "ns3/node-list.h"
#include "ns3/channel-list.h"
#include "../model/ccnx-global-router.h"
@@ -202,12 +204,65 @@
struct property_traits< EdgeWeights >
{
// Metric property map
- typedef uint16_t value_type;
- typedef uint16_t reference;
+ typedef tuple< ns3::Ptr<ns3::CcnxFace>, uint16_t > value_type;
+ typedef tuple< ns3::Ptr<ns3::CcnxFace>, uint16_t > reference;
typedef ns3::CcnxGlobalRouter::Incidency key_type;
typedef readable_property_map_tag category;
};
+const property_traits< EdgeWeights >::value_type WeightZero (0, 0);
+const property_traits< EdgeWeights >::value_type WeightInf (0, std::numeric_limits<uint16_t>::max ());
+
+struct WeightCompare :
+ public std::binary_function<property_traits< EdgeWeights >::reference,
+ property_traits< EdgeWeights >::reference,
+ bool>
+{
+ bool
+ operator () (property_traits< EdgeWeights >::reference a,
+ property_traits< EdgeWeights >::reference b) const
+ {
+ return a.get<1> () < b.get<1> ();
+ }
+
+ bool
+ operator () (property_traits< EdgeWeights >::reference a,
+ uint32_t b) const
+ {
+ return a.get<1> () < b;
+ }
+
+ bool
+ operator () (uint32_t a,
+ uint32_t b) const
+ {
+ return a < b;
+ }
+
+};
+
+struct WeightCombine :
+ public std::binary_function<uint32_t,
+ property_traits< EdgeWeights >::reference,
+ uint32_t>
+{
+ uint32_t
+ operator () (uint32_t a, property_traits< EdgeWeights >::reference b) const
+ {
+ return a + b.get<1> ();
+ }
+
+ tuple< ns3::Ptr<ns3::CcnxFace>, uint32_t >
+ operator () (tuple< ns3::Ptr<ns3::CcnxFace>, uint32_t > a,
+ property_traits< EdgeWeights >::reference b) const
+ {
+ if (a.get<0> () == 0)
+ return make_tuple (b.get<0> (), a.get<1> () + b.get<1> ());
+ else
+ return make_tuple (a.get<0> (), a.get<1> () + b.get<1> ());
+ }
+};
+
template<>
struct property_traits< VertexIds >
{
@@ -234,12 +289,12 @@
return VertexIds (g);
}
-template<class K, class V>
+template<class M, class K, class V>
inline void
-put (std::map<K,V> &mapp,
+put (reference_wrapper< M > mapp,
K a, V p)
{
- mapp[a] = p;
+ mapp.get ()[a] = p;
}
// void
@@ -251,23 +306,22 @@
return gr->GetId ();
}
-inline uint16_t
+inline property_traits< EdgeWeights >::reference
get(const boost::EdgeWeights&, ns3::CcnxGlobalRouter::Incidency &edge)
{
if (edge.get<1> () == 0)
- return 0;
+ return property_traits< EdgeWeights >::reference (0, 0);
else
- return edge.get<1> ()->GetMetric ();
+ return property_traits< EdgeWeights >::reference (edge.get<1> (), edge.get<1> ()->GetMetric ());
}
-
struct PredecessorsMap :
public std::map< ns3::Ptr< ns3::CcnxGlobalRouter >, ns3::Ptr< ns3::CcnxGlobalRouter > >
{
};
template<>
-struct property_traits< PredecessorsMap >
+struct property_traits< reference_wrapper<PredecessorsMap> >
{
// Metric property map
typedef ns3::Ptr< ns3::CcnxGlobalRouter > value_type;
@@ -278,26 +332,26 @@
struct DistancesMap :
- public std::map< ns3::Ptr< ns3::CcnxGlobalRouter >, uint32_t >
+ public std::map< ns3::Ptr< ns3::CcnxGlobalRouter >, tuple< ns3::Ptr<ns3::CcnxFace>, uint32_t > >
{
};
template<>
-struct property_traits< DistancesMap >
+struct property_traits< reference_wrapper<DistancesMap> >
{
// Metric property map
- typedef uint32_t value_type;
- typedef uint32_t reference;
+ typedef tuple< ns3::Ptr<ns3::CcnxFace>, uint32_t > value_type;
+ typedef tuple< ns3::Ptr<ns3::CcnxFace>, uint32_t > reference;
typedef ns3::Ptr< ns3::CcnxGlobalRouter > key_type;
typedef read_write_property_map_tag category;
};
-inline uint32_t
+inline tuple< ns3::Ptr<ns3::CcnxFace>, 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 ();
+ return tuple< ns3::Ptr<ns3::CcnxFace>, uint32_t > (0, std::numeric_limits<uint32_t>::max ());
else
return i->second;
}
diff --git a/helper/ccnx-global-routing-helper.cc b/helper/ccnx-global-routing-helper.cc
index 63e202e..5fde9cb 100644
--- a/helper/ccnx-global-routing-helper.cc
+++ b/helper/ccnx-global-routing-helper.cc
@@ -35,6 +35,11 @@
#include "ns3/channel-list.h"
#include <boost/lexical_cast.hpp>
+#include <boost/concept/assert.hpp>
+// #include <boost/graph/graph_concepts.hpp>
+// #include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/dijkstra_shortest_paths.hpp>
+
#include "boost-graph-ccnx-global-routing-helper.h"
NS_LOG_COMPONENT_DEFINE ("CcnxGlobalRoutingHelper");
@@ -171,20 +176,10 @@
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 ()
{
+ NS_LOG_DEBUG ("Enter");
BOOST_CONCEPT_ASSERT(( VertexListGraphConcept< CcnxGlobalRouterGraph > ));
BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept< CcnxGlobalRouterGraph > ));
// BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept< CcnxGlobalRouterGraph,
@@ -197,61 +192,56 @@
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) ???
- // };
+ for (NodeList::Iterator node = NodeList::Begin (); node != NodeList::End (); node++)
+ {
+ Ptr<CcnxGlobalRouter> source = (*node)->GetObject<CcnxGlobalRouter> ();
+ if (source == 0)
+ {
+ NS_LOG_DEBUG ("Node " << (*node)->GetId () << " does not export CcnxGlobalRouter interface");
+ continue;
+ }
- // Graph graph;
+ // PredecessorsMap predecessors;
+ DistancesMap distances;
- // for (NodeList::Iterator node = NodeList::Begin (); node != NodeList::End (); node++)
- // {
- // Ptr<CcnxGlobalRouter> gr = (*node)->GetObject<CcnxGlobalRouter> ();
- // if (gr == 0)
- // continue;
+ dijkstra_shortest_paths (graph, source,
+ // predecessor_map (boost::ref(predecessors))
+ // .
+ distance_map (boost::ref(distances))
+ .
+ distance_inf (WeightInf)
+ .
+ distance_zero (WeightZero)
+ .
+ distance_compare (boost::WeightCompare ())
+ .
+ distance_combine (boost::WeightCombine ())
+ );
- // for (CcnxGlobalRouter::IncidencyList::const_iterator i = gr->GetIncidencies ().begin ();
- // i != gr->GetIncidencies ().end ();
- // i++)
- // {
- // add_edge (gr, i->get<1> (), 10, graph);
- // }
- // break;
- // }
+ // NS_LOG_DEBUG (predecessors.size () << ", " << distances.size ());
+ cout << "Reachability from Node: " << source->GetObject<Node> ()->GetId () << endl;
+ for (DistancesMap::iterator i = distances.begin ();
+ i != distances.end ();
+ i++)
+ {
+ if (i->first == source)
+ continue;
+ else
+ {
+ cout << " Node " << i->first->GetObject<Node> ()->GetId ();
+ if (distances[i->first].get<0> () == 0)
+ cout << " is unreachable" << endl;
+ else
+ cout << " reachable via face " << *i->second.get<0> ()
+ << " with distance " << i->second.get<1> () << endl;
+ }
+ }
+
+ }
+ // NS_LOG_DEBUG ("Exit");
}
diff --git a/helper/ccnx-stack-helper.cc b/helper/ccnx-stack-helper.cc
index b7c8a01..22f0f22 100644
--- a/helper/ccnx-stack-helper.cc
+++ b/helper/ccnx-stack-helper.cc
@@ -222,97 +222,4 @@
}
-void
-CcnxStackHelper::InstallFakeGlobalRoutesImpl ()
-{
- for (NodeList::Iterator node = NodeList::Begin ();
- node != NodeList::End ();
- node ++)
- {
- NS_ASSERT_MSG ((*node)->GetObject<Ipv4> () != 0,
- "InternetStack should be installed on all nodes");
-
- NS_ASSERT_MSG (Ipv4RoutingHelper::GetRouting<Ipv4GlobalRoutingOrderedNexthops>
- (
- (*node)->GetObject<Ipv4> ()->GetRoutingProtocol ()
- ),
- "InternetStack should have Ipv4GlobalRoutingOrderedNexthops as routing protocol");
- // Example:
- //
- // Ipv4GlobalRoutingHelper ipv4RoutingHelper ("ns3::Ipv4GlobalRoutingUnorderedNexthops");
- // stack.SetRoutingHelper (ipv4RoutingHelper);
- //
-
- Ptr<GlobalRouter> globalRouter = (*node)->GetObject<GlobalRouter> ();
- if (globalRouter == 0) continue;
-
- globalRouter->InjectRoute (Ipv4Address((*node)->GetId ()), Ipv4Mask("255.255.255.255"));
- }
-}
-
-void
-CcnxStackHelper::InstallFakeGlobalRoutes ()
-{
- InstallFakeGlobalRoutesImpl ();
- Ipv4GlobalRoutingHelper::PopulateAllPossibleRoutingTables ();
-}
-
-void
-CcnxStackHelper::InstallRouteTo (Ptr<Node> destNode)
-{
- InstallRouteTo (boost::lexical_cast<std::string> (destNode->GetId ()), destNode);
-}
-
-void
-CcnxStackHelper::InstallRouteTo (const std::string &prefix, Ptr<Node> destNode)
-{
- Ipv4Address destIpv4 = Ipv4Address(destNode->GetId ());
-
- for (NodeList::Iterator node = NodeList::Begin ();
- node != NodeList::End ();
- node ++)
- {
- if (destNode == *node) continue;
-
- Ptr<Ccnx> ccnx = (*node)->GetObject<Ccnx> ();
- NS_ASSERT_MSG (ccnx != 0, "CCNx stack should be installed on all nodes");
-
- Ptr<Ipv4> ipv4 = (*node)->GetObject<Ipv4> ();
- NS_ASSERT_MSG (ipv4 != 0,
- "InternetStack should be installed on all nodes");
-
- Ptr<Ipv4GlobalRoutingOrderedNexthops> routing =
- Ipv4RoutingHelper::GetRouting<Ipv4GlobalRoutingOrderedNexthops> (ipv4->GetRoutingProtocol ());
- NS_ASSERT_MSG (routing != 0, "Ipv4GlobalRoutingOrderedNexthops should be used in InternetStack");
-
- Ptr<Ipv4GlobalRoutingOrderedNexthops::EntryContainer>
- routes = routing->Lookup (destIpv4);
-
- NS_ASSERT_MSG (routes != 0, "Should not happen... Call the developer");
-
- BOOST_FOREACH (const Ipv4RoutingTableEntry &entry, *routes)
- {
- Ptr<NetDevice> netDevice = ipv4->GetNetDevice (entry.GetInterface ());
- NS_ASSERT_MSG (netDevice != 0, "Should never happen. Call the popos");
-
- Ptr<CcnxFace> face = ccnx->GetFaceByNetDevice (netDevice);
- NS_ASSERT_MSG (face != 0, "Definitely should never happen. Call the president");
-
- AddRoute (*node, prefix, face, entry.GetMetric ());
- }
- }
-}
-
-void
-CcnxStackHelper::InstallRoutesToAll ()
-{
- for (NodeList::Iterator node = NodeList::Begin ();
- node != NodeList::End ();
- node ++)
- {
- InstallRouteTo (*node);
- }
-}
-
-
} // namespace ns3