helper: Add LFID route calculation
Loop-Free In-port Dependent (LFID) route calculation provides a set of loop-free paths.
Basically porting the existing code from https://github.com/schneiderklaus/ndnSIM-routing
Refs: #4985
Change-Id: I1ab25e729851cf2233c3b99be715ba0159cca0c7
diff --git a/helper/lfid/abstract-fib.cpp b/helper/lfid/abstract-fib.cpp
new file mode 100644
index 0000000..c4d736f
--- /dev/null
+++ b/helper/lfid/abstract-fib.cpp
@@ -0,0 +1,188 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2019 Klaus Schneider, The University of Arizona
+ *
+ * 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: Klaus Schneider <klaus@cs.arizona.edu>
+ */
+
+#include "abstract-fib.hpp"
+
+#include <algorithm>
+
+#include "ns3/names.h"
+#include "ns3/ndnSIM/NFD/daemon/fw/forwarder.hpp"
+#include "ns3/ndnSIM/model/ndn-global-router.hpp"
+#include "ns3/ndnSIM/model/ndn-l3-protocol.hpp"
+#include "ns3/node.h"
+
+namespace ns3 {
+namespace ndn {
+
+using std::set;
+
+AbstractFib::AbstractFib(const Ptr<GlobalRouter> own, int numNodes)
+ : nodeId{static_cast<int>(own->GetObject<ns3::Node>()->GetId())}
+ , nodeName{ns3::Names::FindName(own->GetObject<ns3::Node>())}
+ , numberOfNodes{numNodes}
+ , nodeDegree{static_cast<int>(own->GetIncidencies().size())}
+ , ownRouter{own}
+ , upwardCounter{0}
+ , totalNhCounter{0}
+{
+ checkInputs();
+
+ createEmptyFib();
+}
+
+void
+AbstractFib::checkInputs()
+{
+ if (nodeDegree <= 0) {
+ std::cerr << nodeName << " has a degree of " << nodeDegree << "!\n\n";
+ }
+
+ const auto MAX_SIZE{1e5};
+ NS_ABORT_UNLESS(nodeId >= 0 && nodeId <= MAX_SIZE);
+ NS_ABORT_UNLESS(nodeName.size() > 0 && nodeName.size() <= MAX_SIZE);
+ NS_ABORT_UNLESS(nodeDegree >= 0 && nodeDegree <= MAX_SIZE);
+ NS_ABORT_UNLESS(numberOfNodes > 1 && numberOfNodes <= MAX_SIZE);
+}
+
+void
+AbstractFib::createEmptyFib()
+{
+ // Create empty FIB:
+ for (int dstId = 0; dstId < numberOfNodes; dstId++) {
+ if (dstId == nodeId) {
+ continue;
+ }
+ perDstFib.insert({dstId, {}});
+ upwardPerDstFib.insert({dstId, {}});
+ }
+}
+
+Ptr<GlobalRouter>
+AbstractFib::getGR() const
+{
+ return ownRouter;
+}
+
+// Setters:
+void
+AbstractFib::insert(int dstId, const FibNextHop& nh)
+{
+ NS_ABORT_UNLESS(nh.getType() == NextHopType::DOWNWARD || nh.getType() == NextHopType::UPWARD);
+ NS_ABORT_UNLESS(nh.getNexthopId() != nodeId);
+
+ bool inserted1 = perDstFib.at(dstId).insert(nh).second;
+ BOOST_VERIFY(inserted1); // Check if it didn't exist yet.
+ totalNhCounter++;
+
+ if (nh.getType() == NextHopType::UPWARD) {
+ bool inserted2 = upwardPerDstFib.at(dstId).insert(nh).second;
+ BOOST_VERIFY(inserted2);
+ upwardCounter++;
+ }
+}
+
+size_t
+AbstractFib::erase(int dstId, int nhId)
+{
+ auto& fib{perDstFib.at(dstId)};
+
+ auto fibNh = std::find_if(fib.begin(), fib.end(),
+ [&](const FibNextHop& item) { return item.getNexthopId() == nhId; });
+
+ // Element doesn't exist:
+ if (fibNh == fib.end()) {
+
+ // TODO: Figure out why this happens.
+ return 0;
+ }
+
+ NS_ABORT_UNLESS(fibNh != perDstFib.at(dstId).end());
+ NS_ABORT_UNLESS(fibNh->getType() == NextHopType::UPWARD);
+ totalNhCounter--;
+
+ fib.erase(fibNh);
+ auto numErased2 = upwardPerDstFib.at(dstId).erase(*fibNh);
+ NS_ABORT_UNLESS(numErased2 == 1);
+ upwardCounter--;
+
+ return numErased2;
+}
+
+// O(1)
+const set<FibNextHop>&
+AbstractFib::getNexthops(int dstId) const
+{
+ NS_ABORT_MSG_IF(dstId == nodeId, "Requested destination id is the same as current nodeId!");
+ NS_ABORT_MSG_IF(perDstFib.count(dstId) == 0,
+ "Node " << nodeId << " No nexthops for dst: " << dstId << "!");
+ NS_ABORT_UNLESS(perDstFib.count(dstId) != 0);
+ return perDstFib.at(dstId);
+}
+
+const set<FibNextHop>&
+AbstractFib::getUpwardNexthops(int dstId) const
+{
+ NS_ABORT_MSG_IF(dstId == nodeId, "Requested destination id is the same as current nodeId!");
+ NS_ABORT_MSG_IF(perDstFib.count(dstId) == 0,
+ "Node " << nodeId << " No nexthops for dst: " << dstId << "!");
+ return upwardPerDstFib.at(dstId);
+}
+
+void
+AbstractFib::checkFib() const
+{
+ BOOST_VERIFY(perDstFib.size() > 0);
+
+ for (const auto& fibSet : perDstFib) {
+ const size_t numNhs = fibSet.second.size();
+
+ bool hasDownward{false};
+ std::unordered_set<int> nextHopSet{};
+
+ for (const FibNextHop& nextHop : fibSet.second) {
+ BOOST_VERIFY(nextHop.getCost() > 0 && nextHop.getCost() < FibNextHop::MAX_COST);
+ if (nextHop.getType() == NextHopType::DOWNWARD) {
+ hasDownward = true;
+ }
+
+ // Only one FIB entry per nexthop allowed!
+ BOOST_VERIFY(nextHopSet.count(nextHop.getNexthopId()) == 0);
+ nextHopSet.emplace(nextHop.getNexthopId());
+ }
+ BOOST_VERIFY(hasDownward || numNhs == 0);
+ BOOST_VERIFY(nextHopSet.size() == fibSet.second.size());
+ }
+}
+
+std::ostream&
+operator<<(std::ostream& os, const AbstractFib& fib)
+{
+ for (const auto& entry : fib.perDstFib) {
+ os << "\nFIB node: " << fib.nodeName << fib.nodeId << "\n";
+ os << "Dst: " << entry.first << "\n";
+ for (const auto& nh : entry.second) {
+ os << nh << "\n";
+ }
+ }
+ return os;
+}
+
+} // namespace ndn
+} // namespace ns-3