helper: New experimental CalculateAllPossibleRoutes method in ndn::GlobalRoutingHelper
Implementation is not time-efficient and it should not be used for very
large topologies.
diff --git a/helper/ndn-global-routing-helper.cc b/helper/ndn-global-routing-helper.cc
index 135cd4c..44354d4 100644
--- a/helper/ndn-global-routing-helper.cc
+++ b/helper/ndn-global-routing-helper.cc
@@ -317,6 +317,134 @@
}
}
+void
+GlobalRoutingHelper::CalculateAllPossibleRoutes ()
+{
+ /**
+ * Implementation of route calculation is heavily based on Boost Graph Library
+ * See http://www.boost.org/doc/libs/1_49_0/libs/graph/doc/table_of_contents.html for more details
+ */
+
+ int counter = 0;
+
+ BOOST_CONCEPT_ASSERT(( VertexListGraphConcept< NdnGlobalRouterGraph > ));
+ BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept< NdnGlobalRouterGraph > ));
+
+ NdnGlobalRouterGraph graph;
+ typedef graph_traits < NdnGlobalRouterGraph >::vertex_descriptor vertex_descriptor;
+
+ // For now we doing Dijkstra for every node. Can be replaced with Bellman-Ford or Floyd-Warshall.
+ // Other algorithms should be faster, but they need additional EdgeListGraph concept provided by the graph, which
+ // is not obviously how implement in an efficient manner
+ for (NodeList::Iterator node = NodeList::Begin (); node != NodeList::End (); node++)
+ {
+ Ptr<GlobalRouter> source = (*node)->GetObject<GlobalRouter> ();
+ if (source == 0)
+ {
+ NS_LOG_DEBUG ("Node " << (*node)->GetId () << " does not export GlobalRouter interface");
+ continue;
+ }
+
+ Ptr<Fib> fib = source->GetObject<Fib> ();
+ fib->InvalidateAll ();
+ NS_ASSERT (fib != 0);
+
+ NS_LOG_DEBUG ("===========");
+ NS_LOG_DEBUG ("Reachability from Node: " << source->GetObject<Node> ()->GetId () << " (" << Names::FindName (source->GetObject<Node> ()) << ")");
+
+ Ptr<L3Protocol> l3 = source->GetObject<L3Protocol> ();
+ NS_ASSERT (l3 != 0);
+
+ // remember interface statuses
+ std::vector<uint16_t> originalMetric (l3->GetNFaces ());
+ for (uint32_t faceId = 0; faceId < l3->GetNFaces (); faceId++)
+ {
+ originalMetric[faceId] = l3->GetFace (faceId)->GetMetric ();
+ l3->GetFace (faceId)->SetMetric (std::numeric_limits<int16_t>::max ()-1); // value std::numeric_limits<int16_t>::max () MUST NOT be used (reserved)
+ }
+
+ for (uint32_t enabledFaceId = 0; enabledFaceId < l3->GetNFaces (); enabledFaceId++)
+ {
+ if (DynamicCast<ndn::NetDeviceFace> (l3->GetFace (enabledFaceId)) == 0)
+ continue;
+
+ // enabling only faceId
+ l3->GetFace (enabledFaceId)->SetMetric (originalMetric[enabledFaceId]);
+
+ DistancesMap distances;
+
+ NS_LOG_DEBUG ("-----------");
+
+ 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 ())
+ );
+
+ // NS_LOG_DEBUG (predecessors.size () << ", " << distances.size ());
+
+ for (DistancesMap::iterator i = distances.begin ();
+ i != distances.end ();
+ i++)
+ {
+ if (i->first == source)
+ continue;
+ else
+ {
+ // cout << " Node " << i->first->GetObject<Node> ()->GetId ();
+ if (i->second.get<0> () == 0)
+ {
+ // cout << " is unreachable" << endl;
+ }
+ else
+ {
+ BOOST_FOREACH (const Ptr<const NameComponents> &prefix, i->first->GetLocalPrefixes ())
+ {
+ NS_LOG_DEBUG (" prefix " << *prefix << " reachable via face " << *i->second.get<0> ()
+ << " with distance " << i->second.get<1> ()
+ << " with delay " << i->second.get<2> ());
+
+ if (i->second.get<0> ()->GetMetric () == std::numeric_limits<uint16_t>::max ()-1)
+ continue;
+
+ Ptr<fib::Entry> entry = fib->Add (prefix, i->second.get<0> (), i->second.get<1> ());
+ entry->SetRealDelayToProducer (i->second.get<0> (), Seconds (i->second.get<2> ()));
+
+ Ptr<Limits> faceLimits = i->second.get<0> ()->GetObject<Limits> ();
+
+ Ptr<Limits> fibLimits = entry->GetObject<Limits> ();
+ if (fibLimits != 0)
+ {
+ // if it was created by the forwarding strategy via DidAddFibEntry event
+ fibLimits->SetLimits (faceLimits->GetMaxRate (), 2 * i->second.get<2> () /*exact RTT*/);
+ NS_LOG_DEBUG ("Set limit for prefix " << *prefix << " " << faceLimits->GetMaxRate () << " / " <<
+ 2*i->second.get<2> () << "s (" << faceLimits->GetMaxRate () * 2 * i->second.get<2> () << ")");
+ }
+ }
+ }
+ }
+ }
+
+ // disabling the face again
+ l3->GetFace (enabledFaceId)->SetMetric (std::numeric_limits<uint16_t>::max ()-1);
+ }
+
+ // recover original interface statuses
+ for (uint32_t faceId = 0; faceId < l3->GetNFaces (); faceId++)
+ {
+ l3->GetFace (faceId)->SetMetric (originalMetric[faceId]);
+ }
+ }
+}
+
} // namespace ndn
} // namespace ns3
diff --git a/helper/ndn-global-routing-helper.h b/helper/ndn-global-routing-helper.h
index 983c7b0..f233e89 100644
--- a/helper/ndn-global-routing-helper.h
+++ b/helper/ndn-global-routing-helper.h
@@ -98,9 +98,19 @@
/**
* @brief Calculate for every node shortest path trees and install routes to all prefix origins
*/
- void
+ static void
CalculateRoutes ();
+ /**
+ * @brief Calculate all possible next-hop independent alternative routes
+ *
+ * Refer to the implementation for more details.
+ *
+ * Note that this method is highly experimental and should be used with caution (very time consuming).
+ */
+ static void
+ CalculateAllPossibleRoutes ();
+
private:
void
Install (Ptr<Channel> channel);