rib: Generate FIB updates using route flags
refs: #1325
Change-Id: I5c567da1c06819caeba5cc5b024914666ba70ab6
diff --git a/rib/face-entry.hpp b/rib/face-entry.hpp
index 15a8aaf..bd3f1f9 100644
--- a/rib/face-entry.hpp
+++ b/rib/face-entry.hpp
@@ -66,6 +66,10 @@
return (entry.faceId == faceId);
}
+// Method definition in rib-entry.cpp
+std::ostream&
+operator<<(std::ostream& os, const FaceEntry& entry);
+
} // namespace rib
} // namespace nfd
diff --git a/rib/fib-update.cpp b/rib/fib-update.cpp
new file mode 100644
index 0000000..cda4f14
--- /dev/null
+++ b/rib/fib-update.cpp
@@ -0,0 +1,57 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014, Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology,
+ * The University of Memphis
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD 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
+ * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "fib-update.hpp"
+
+namespace nfd {
+namespace rib {
+
+shared_ptr<FibUpdate>
+FibUpdate::createAddUpdate(const Name& name, const uint64_t faceId, const uint64_t cost)
+{
+ shared_ptr<FibUpdate> update = make_shared<FibUpdate>();
+
+ update->name = name;
+ update->faceId = faceId;
+ update->cost = cost;
+ update->action = ADD_NEXTHOP;
+
+ return update;
+}
+
+shared_ptr<FibUpdate>
+FibUpdate::createRemoveUpdate(const Name& name, const uint64_t faceId)
+{
+ shared_ptr<FibUpdate> update = make_shared<FibUpdate>();
+
+ update->name = name;
+ update->faceId = faceId;
+ update->action = REMOVE_NEXTHOP;
+
+ return update;
+}
+
+} // namespace rib
+} // namespace nfd
diff --git a/rib/fib-update.hpp b/rib/fib-update.hpp
new file mode 100644
index 0000000..02713ab
--- /dev/null
+++ b/rib/fib-update.hpp
@@ -0,0 +1,90 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014, Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology,
+ * The University of Memphis
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD 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
+ * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef NFD_RIB_FIB_UPDATE_HPP
+#define NFD_RIB_FIB_UPDATE_HPP
+
+#include "common.hpp"
+
+namespace nfd {
+namespace rib {
+
+/** \class FibUpdate
+ * \brief represents a FIB update
+ */
+class FibUpdate
+{
+public:
+ FibUpdate()
+ : faceId(0)
+ , cost(0)
+ {
+ }
+
+ static shared_ptr<FibUpdate>
+ createAddUpdate(const Name& name, const uint64_t faceId, const uint64_t cost);
+
+ static shared_ptr<FibUpdate>
+ createRemoveUpdate(const Name& name, const uint64_t faceId);
+
+ enum Action
+ {
+ ADD_NEXTHOP = 0,
+ REMOVE_NEXTHOP = 1
+ };
+
+public:
+ Name name;
+ uint64_t faceId;
+ uint64_t cost;
+ Action action;
+};
+
+inline std::ostream&
+operator<<(std::ostream& os, const FibUpdate& update)
+{
+ os << "FibUpdate("
+ << " Name: " << update.name << ", "
+ << "faceId: " << update.faceId << ", ";
+
+ if (update.action == FibUpdate::ADD_NEXTHOP)
+ {
+ os << "cost: " << update.cost << ", "
+ << "action: ADD_NEXTHOP";
+ }
+ else
+ {
+ os << "action: REMOVE_NEXTHOP";
+ }
+
+ os << ")";
+
+ return os;
+}
+
+} // namespace rib
+} // namespace nfd
+
+#endif // NFD_RIB_FIB_UPDATE_HPP
diff --git a/rib/rib-entry.cpp b/rib/rib-entry.cpp
index db72d37..98c3b90 100644
--- a/rib/rib-entry.cpp
+++ b/rib/rib-entry.cpp
@@ -43,6 +43,11 @@
if (it == end())
{
+ if (entry.flags & ndn::nfd::ROUTE_FLAG_CAPTURE)
+ {
+ m_nFacesWithCaptureSet++;
+ }
+
m_faces.push_back(entry);
return true;
}
@@ -56,8 +61,14 @@
RibEntry::eraseFace(const FaceEntry& face)
{
RibEntry::iterator it = std::find_if(begin(), end(), bind(&compareFaceIdAndOrigin, _1, face));
+
if (it != m_faces.end())
{
+ if (it->flags & ndn::nfd::ROUTE_FLAG_CAPTURE)
+ {
+ m_nFacesWithCaptureSet--;
+ }
+
m_faces.erase(it);
return true;
}
@@ -68,11 +79,20 @@
}
bool
+RibEntry::hasFace(const FaceEntry& face)
+{
+ RibEntry::const_iterator it = std::find_if(cbegin(), cend(),
+ bind(&compareFaceIdAndOrigin, _1, face));
+
+ return it != cend();
+}
+
+bool
RibEntry::hasFaceId(const uint64_t faceId) const
{
RibEntry::const_iterator it = std::find_if(cbegin(), cend(), bind(&compareFaceId, _1, faceId));
- return (it != cend());
+ return it != cend();
}
void
@@ -94,7 +114,115 @@
RibEntry::FaceList::iterator
RibEntry::eraseFace(FaceList::iterator face)
{
- return m_faces.erase(face);
+ if (face != m_faces.end())
+ {
+ if (face->flags & ndn::nfd::ROUTE_FLAG_CAPTURE)
+ {
+ m_nFacesWithCaptureSet--;
+ }
+
+ return m_faces.erase(face);
+ }
+
+ return m_faces.end();
+}
+
+void
+RibEntry::addInheritedFace(const FaceEntry& face)
+{
+ m_inheritedFaces.push_back(face);
+}
+
+void
+RibEntry::removeInheritedFace(const FaceEntry& face)
+{
+ FaceList::iterator it = findInheritedFace(face);
+ m_inheritedFaces.erase(it);
+}
+
+RibEntry::FaceList::iterator
+RibEntry::findInheritedFace(const FaceEntry& face)
+{
+ return std::find_if(m_inheritedFaces.begin(), m_inheritedFaces.end(),
+ bind(&compareFaceId, _1, face.faceId));
+}
+
+bool
+RibEntry::hasInheritedFace(const FaceEntry& face)
+{
+ FaceList::const_iterator it = findInheritedFace(face);
+
+ return (it != m_inheritedFaces.end());
+}
+
+bool
+RibEntry::hasCapture() const
+{
+ return m_nFacesWithCaptureSet > 0;
+}
+
+bool
+RibEntry::hasChildInheritOnFaceId(uint64_t faceId) const
+{
+ for (RibEntry::const_iterator it = m_faces.begin(); it != m_faces.end(); ++it)
+ {
+ if (it->faceId == faceId && (it->flags & ndn::nfd::ROUTE_FLAG_CHILD_INHERIT))
+ {
+ return true;
+ }
+ }
+
+ return false;
+}
+
+shared_ptr<FaceEntry>
+RibEntry::getFaceWithLowestCostByFaceId(uint64_t faceId)
+{
+ shared_ptr<FaceEntry> face;
+
+ for (FaceList::iterator it = begin(); it != end(); ++it)
+ {
+ // Correct face ID
+ if (it->faceId == faceId)
+ {
+ // If this is the first face with this ID found
+ if (!static_cast<bool>(face))
+ {
+ face = make_shared<FaceEntry>(*it);
+ }
+ else if (it->cost < face->cost) // Found a face with a lower cost
+ {
+ face = make_shared<FaceEntry>(*it);
+ }
+ }
+ }
+
+ return face;
+}
+
+shared_ptr<FaceEntry>
+RibEntry::getFaceWithLowestCostAndChildInheritByFaceId(uint64_t faceId)
+{
+ shared_ptr<FaceEntry> face;
+
+ for (FaceList::iterator it = begin(); it != end(); ++it)
+ {
+ // Correct face ID and Child Inherit flag set
+ if (it->faceId == faceId && it->flags & ndn::nfd::ROUTE_FLAG_CHILD_INHERIT)
+ {
+ // If this is the first face with this ID found
+ if (!static_cast<bool>(face))
+ {
+ face = make_shared<FaceEntry>(*it);
+ }
+ else if (it->cost < face->cost) // Found a face with a lower cost
+ {
+ face = make_shared<FaceEntry>(*it);
+ }
+ }
+ }
+
+ return face;
}
std::ostream&
diff --git a/rib/rib-entry.hpp b/rib/rib-entry.hpp
index 4726a04..fc78624 100644
--- a/rib/rib-entry.hpp
+++ b/rib/rib-entry.hpp
@@ -42,6 +42,7 @@
typedef FaceList::const_iterator const_iterator;
RibEntry()
+ : m_nFacesWithCaptureSet(0)
{
}
@@ -98,6 +99,60 @@
iterator
findFace(const FaceEntry& face);
+ bool
+ hasFace(const FaceEntry& face);
+
+ void
+ addInheritedFace(const FaceEntry& face);
+
+ void
+ removeInheritedFace(const FaceEntry& face);
+
+ /** \brief Returns the faces this namespace has inherited.
+ * The inherited faces returned represent inherited entries this namespace has in the FIB.
+ * \return{ faces inherited by this namespace }
+ */
+ FaceList&
+ getInheritedFaces();
+
+ /** \brief Finds an inherited face with a matching face ID.
+ * \return{ An iterator to the matching face if one is found;
+ * otherwise, an iterator to the end of the entry's
+ * inherited face list }
+ */
+ FaceList::iterator
+ findInheritedFace(const FaceEntry& face);
+
+ /** \brief Determines if the entry has an inherited face with a matching face ID.
+ * \return{ True, if a matching inherited face is found; otherwise, false. }
+ */
+ bool
+ hasInheritedFace(const FaceEntry& face);
+
+ bool
+ hasCapture() const;
+
+ /** \brief Determines if the entry has an inherited face with the passed
+ * face ID and its child inherit flag set.
+ * \return{ True, if a matching inherited face is found; otherwise, false. }
+ */
+ bool
+ hasChildInheritOnFaceId(uint64_t faceId) const;
+
+ /** \brief Returns the face with the lowest cost that has the passed face ID.
+ * \return{ The face with with the lowest cost that has the passed face ID}
+ */
+ shared_ptr<FaceEntry>
+ getFaceWithLowestCostByFaceId(uint64_t faceId);
+
+ /** \brief Returns the face with the lowest cost that has the passed face ID
+ * and its child inherit flag set.
+ * \return{ The face with with the lowest cost that has the passed face ID
+ * and its child inherit flag set }
+ */
+ shared_ptr<FaceEntry>
+ getFaceWithLowestCostAndChildInheritByFaceId(uint64_t faceId);
+
const_iterator
cbegin() const;
@@ -120,6 +175,14 @@
shared_ptr<RibEntry> m_parent;
FaceList m_faces;
FaceList m_inheritedFaces;
+
+ /** \brief The number of faces on this namespace with the capture flag set.
+ *
+ * This count is used to check if the namespace will block inherited faces.
+ * If the number is greater than zero, a route on the namespace has it's capture
+ * flag set which means the namespace should not inherit any faces.
+ */
+ uint64_t m_nFacesWithCaptureSet;
};
inline void
@@ -158,6 +221,12 @@
return m_faces;
}
+inline RibEntry::FaceList&
+RibEntry::getInheritedFaces()
+{
+ return m_inheritedFaces;
+}
+
inline RibEntry::const_iterator
RibEntry::cbegin() const
{
@@ -182,6 +251,9 @@
return m_faces.end();
}
+std::ostream&
+operator<<(std::ostream& os, const RibEntry& entry);
+
} // namespace rib
} // namespace nfd
diff --git a/rib/rib-manager.cpp b/rib/rib-manager.cpp
index b89b619..8b7010a 100644
--- a/rib/rib-manager.cpp
+++ b/rib/rib-manager.cpp
@@ -64,6 +64,7 @@
, m_localhopValidator(m_face)
, m_faceMonitor(m_face)
, m_isLocalhopEnabled(false)
+ , m_lastTransactionId(0)
, m_verbDispatch(COMMAND_VERBS,
COMMAND_VERBS + (sizeof(COMMAND_VERBS) / sizeof(VerbAndProcessor)))
{
@@ -225,18 +226,9 @@
NFD_LOG_TRACE("register prefix: " << faceEntry);
- /// \todo For right now, just pass the options to fib as is
- /// without processing flags. Later, options will first be added to
- /// Rib tree, nrd will generate fib updates based on flags, and
- /// will then add next hops one by one.
m_managedRib.insert(parameters.getName(), faceEntry);
- m_nfdController.start<ndn::nfd::FibAddNextHopCommand>(
- ControlParameters()
- .setName(parameters.getName())
- .setFaceId(faceEntry.faceId)
- .setCost(faceEntry.cost),
- bind(&RibManager::onRegSuccess, this, request, parameters, faceEntry),
- bind(&RibManager::onCommandError, this, _1, _2, request, faceEntry));
+
+ sendUpdatesToFib(request, parameters);
}
void
@@ -258,12 +250,9 @@
NFD_LOG_TRACE("unregister prefix: " << faceEntry);
- m_nfdController.start<ndn::nfd::FibRemoveNextHopCommand>(
- ControlParameters()
- .setName(parameters.getName())
- .setFaceId(faceEntry.faceId),
- bind(&RibManager::onUnRegSuccess, this, request, parameters, faceEntry),
- bind(&RibManager::onCommandError, this, _1, _2, request, faceEntry));
+ m_managedRib.erase(parameters.getName(), faceEntry);
+
+ sendUpdatesToFib(request, parameters);
}
void
@@ -334,7 +323,6 @@
}
sendResponse(request->getName(), response);
- m_managedRib.erase(request->getName(), faceEntry);
}
void
@@ -368,7 +356,53 @@
NFD_LOG_TRACE("onUnRegSuccess: unregistered " << faceEntry);
sendResponse(request->getName(), response);
- m_managedRib.erase(request->getName(), faceEntry);
+}
+
+void
+RibManager::sendSuccessResponse(const shared_ptr<const Interest>& request,
+ const ControlParameters& parameters)
+{
+ if (!static_cast<bool>(request))
+ {
+ return;
+ }
+
+ ControlResponse response;
+
+ response.setCode(200);
+ response.setText("Success");
+ response.setBody(parameters.wireEncode());
+
+ sendResponse(request->getName(), response);
+}
+
+void
+RibManager::sendErrorResponse(uint32_t code, const std::string& error,
+ const shared_ptr<const Interest>& request)
+{
+ NFD_LOG_ERROR("NFD returned an error: " << error << " (code: " << code << ")");
+
+ if (!static_cast<bool>(request))
+ {
+ return;
+ }
+
+ ControlResponse response;
+
+ if (code == 404)
+ {
+ response.setCode(code);
+ response.setText(error);
+ }
+ else
+ {
+ response.setCode(533);
+ std::ostringstream os;
+ os << "Failure to update NFD " << "(NFD Error: " << code << " " << error << ")";
+ response.setText(os.str());
+ }
+
+ sendResponse(request->getName(), response);
}
void
@@ -383,16 +417,87 @@
throw Error("Error in setting interest filter (" + name.toUri() + "): " + msg);
}
-void
-RibManager::onAddNextHopSuccess(const Name& prefix)
+bool
+RibManager::isTransactionComplete(const TransactionId transactionId)
{
- NFD_LOG_DEBUG("Successfully registered " + prefix.toUri() + " with NFD");
+ FibTransactionTable::iterator it = m_pendingFibTransactions.find(transactionId);
+
+ if (it != m_pendingFibTransactions.end())
+ {
+ int& updatesLeft = it->second;
+
+ updatesLeft--;
+
+ // All of the updates have been applied successfully
+ if (updatesLeft == 0)
+ {
+ m_pendingFibTransactions.erase(it);
+ return true;
+ }
+ }
+
+ return false;
}
void
-RibManager::onAddNextHopError(const Name& name, const std::string& msg)
+RibManager::invalidateTransaction(const TransactionId transactionId)
{
- throw Error("Error in setting interest filter (" + name.toUri() + "): " + msg);
+ FibTransactionTable::iterator it = m_pendingFibTransactions.find(transactionId);
+
+ if (it != m_pendingFibTransactions.end())
+ {
+ m_pendingFibTransactions.erase(it);
+ }
+}
+
+void
+RibManager::onAddNextHopSuccess(const shared_ptr<const Interest>& request,
+ const ControlParameters& parameters,
+ const TransactionId transactionId,
+ const bool shouldSendResponse)
+{
+ if (isTransactionComplete(transactionId) && shouldSendResponse)
+ {
+ sendSuccessResponse(request, parameters);
+ }
+}
+
+void
+RibManager::onAddNextHopError(uint32_t code, const std::string& error,
+ const shared_ptr<const Interest>& request,
+ const TransactionId transactionId, const bool shouldSendResponse)
+{
+ invalidateTransaction(transactionId);
+
+ if (shouldSendResponse)
+ {
+ sendErrorResponse(code, error, request);
+ }
+}
+
+void
+RibManager::onRemoveNextHopSuccess(const shared_ptr<const Interest>& request,
+ const ControlParameters& parameters,
+ const TransactionId transactionId,
+ const bool shouldSendResponse)
+{
+ if (isTransactionComplete(transactionId) && shouldSendResponse)
+ {
+ sendSuccessResponse(request, parameters);
+ }
+}
+
+void
+RibManager::onRemoveNextHopError(uint32_t code, const std::string& error,
+ const shared_ptr<const Interest>& request,
+ const TransactionId transactionId, const bool shouldSendResponse)
+{
+ invalidateTransaction(transactionId);
+
+ if (shouldSendResponse)
+ {
+ sendErrorResponse(code, error, request);
+ }
}
void
@@ -425,9 +530,98 @@
{
/// \todo A notification can be missed, in this case check Facelist
NFD_LOG_TRACE("onNotification: " << notification);
- if (notification.getKind() == ndn::nfd::FACE_EVENT_DESTROYED) { //face destroyed
- m_managedRib.erase(notification.getFaceId());
- }
+ if (notification.getKind() == ndn::nfd::FACE_EVENT_DESTROYED) //face destroyed
+ {
+ m_managedRib.erase(notification.getFaceId());
+
+ sendUpdatesToFibAfterFaceDestroyEvent();
+ }
+}
+
+void
+RibManager::sendUpdatesToFib(const shared_ptr<const Interest>& request,
+ const ControlParameters& parameters)
+{
+ const Rib::FibUpdateList& updates = m_managedRib.getFibUpdates();
+
+ // If no updates were generated, consider the operation a success
+ if (updates.empty())
+ {
+ sendSuccessResponse(request, parameters);
+ return;
+ }
+
+ bool shouldWaitToRespond = false;
+
+ // An application request should wait for all FIB updates to be applied
+ // successfully before sending a response
+ if (parameters.getOrigin() == ndn::nfd::ROUTE_ORIGIN_APP)
+ {
+ shouldWaitToRespond = true;
+ }
+ else // Respond immediately
+ {
+ sendSuccessResponse(request, parameters);
+ }
+
+ NFD_LOG_DEBUG("Applying " << updates.size() << " updates to FIB");
+
+ // Assign an ID to this FIB transaction
+ TransactionId currentTransactionId = ++m_lastTransactionId;
+
+ // Add this transaction to the transaction table
+ m_pendingFibTransactions[currentTransactionId] = updates.size();
+
+ for (Rib::FibUpdateList::const_iterator it = updates.begin(); it != updates.end(); ++it)
+ {
+ shared_ptr<const FibUpdate> update(*it);
+
+ if (update->action == FibUpdate::ADD_NEXTHOP)
+ {
+ FaceEntry faceEntry;
+ faceEntry.faceId = update->faceId;
+ faceEntry.cost = update->cost;
+
+ m_nfdController.start<ndn::nfd::FibAddNextHopCommand>(
+ ControlParameters()
+ .setName(update->name)
+ .setFaceId(faceEntry.faceId)
+ .setCost(faceEntry.cost),
+ bind(&RibManager::onAddNextHopSuccess, this, request,
+ parameters,
+ currentTransactionId,
+ shouldWaitToRespond),
+ bind(&RibManager::onAddNextHopError, this, _1, _2, request, currentTransactionId,
+ shouldWaitToRespond));
+ }
+ else if (update->action == FibUpdate::REMOVE_NEXTHOP)
+ {
+ FaceEntry faceEntry;
+ faceEntry.faceId = update->faceId;
+
+ m_nfdController.start<ndn::nfd::FibRemoveNextHopCommand>(
+ ControlParameters()
+ .setName(update->name)
+ .setFaceId(faceEntry.faceId),
+ bind(&RibManager::onRemoveNextHopSuccess, this, request,
+ parameters,
+ currentTransactionId,
+ shouldWaitToRespond),
+ bind(&RibManager::onRemoveNextHopError, this, _1, _2, request, currentTransactionId,
+ shouldWaitToRespond));
+ }
+ }
+
+ m_managedRib.clearFibUpdates();
+}
+
+void
+RibManager::sendUpdatesToFibAfterFaceDestroyEvent()
+{
+ ControlParameters parameters;
+ parameters.setOrigin(ndn::nfd::ROUTE_ORIGIN_STATIC);
+
+ sendUpdatesToFib(shared_ptr<const Interest>(), parameters);
}
} // namespace rib
diff --git a/rib/rib-manager.hpp b/rib/rib-manager.hpp
index 7721436..6f90a80 100644
--- a/rib/rib-manager.hpp
+++ b/rib/rib-manager.hpp
@@ -68,6 +68,8 @@
setConfigFile(ConfigFile& configFile);
private:
+ typedef uint32_t TransactionId;
+
void
onConfig(const ConfigSection& configSection,
bool isDryRun,
@@ -92,6 +94,14 @@
const std::string& text);
void
+ sendSuccessResponse(const shared_ptr<const Interest>& request,
+ const ControlParameters& parameters);
+
+ void
+ sendErrorResponse(uint32_t code, const std::string& error,
+ const shared_ptr<const Interest>& request);
+
+ void
registerEntry(const shared_ptr<const Interest>& request,
ControlParameters& parameters);
@@ -129,10 +139,26 @@
onNrdCommandPrefixAddNextHopError(const Name& name, const std::string& msg);
void
- onAddNextHopSuccess(const Name& prefix);
+ onAddNextHopSuccess(const shared_ptr<const Interest>& request,
+ const ControlParameters& parameters,
+ const TransactionId transactionId,
+ const bool shouldSendResponse);
void
- onAddNextHopError(const Name& name, const std::string& msg);
+ onAddNextHopError(uint32_t code, const std::string& error,
+ const shared_ptr<const Interest>& request,
+ const TransactionId transactionId, const bool shouldSendResponse);
+
+ void
+ onRemoveNextHopSuccess(const shared_ptr<const Interest>& request,
+ const ControlParameters& parameters,
+ const TransactionId transactionId,
+ const bool shouldSendResponse);
+
+ void
+ onRemoveNextHopError(uint32_t code, const std::string& error,
+ const shared_ptr<const Interest>& request,
+ const TransactionId transactionId, const bool shouldSendResponse);
void
onControlHeaderSuccess();
@@ -150,6 +176,24 @@
void
onNotification(const FaceEventNotification& notification);
+ void
+ sendUpdatesToFib(const shared_ptr<const Interest>& request,
+ const ControlParameters& parameters);
+
+ void
+ sendUpdatesToFibAfterFaceDestroyEvent();
+
+ /** \brief Checks if the transaction has received all of the expected responses
+ * from the FIB.
+ * \return{ True if the transaction with the passed transactionId has applied
+ * all of its FIB updates successfully; otherwise, false }
+ */
+ bool
+ isTransactionComplete(const TransactionId transactionId);
+
+ void
+ invalidateTransaction(const TransactionId transactionId);
+
private:
Rib m_managedRib;
ndn::Face m_face;
@@ -160,6 +204,22 @@
FaceMonitor m_faceMonitor;
bool m_isLocalhopEnabled;
+ /** \brief The last transaction ID for FIB update response messages.
+ * Each group of FIB updates applied to the FIB is assigned an incrementing
+ * ID that is used to track the number of successfully applied updates.
+ */
+ TransactionId m_lastTransactionId;
+
+ /// table of FIB update transactions => count of pending FIB updates
+ typedef std::map<TransactionId, int> FibTransactionTable;
+
+ /** \brief Table used to track the number of FIB updates that have not yet received
+ * a response from the FIB.
+ * The table maps a transaction ID to the number of updates remaining for that
+ * specific transaction.
+ */
+ FibTransactionTable m_pendingFibTransactions;
+
typedef function<void(RibManager*,
const shared_ptr<const Interest>& request,
ControlParameters& parameters)> VerbProcessor;
diff --git a/rib/rib.cpp b/rib/rib.cpp
index f47d840..c3fc399 100644
--- a/rib/rib.cpp
+++ b/rib/rib.cpp
@@ -28,6 +28,36 @@
namespace nfd {
namespace rib {
+static inline bool
+sortFace(const FaceEntry& entry1, const FaceEntry& entry2)
+{
+ return entry1.faceId < entry2.faceId;
+}
+
+static inline bool
+isChildInheritFlagSet(uint64_t flags)
+{
+ return flags & ndn::nfd::ROUTE_FLAG_CHILD_INHERIT;
+}
+
+static inline bool
+isCaptureFlagSet(uint64_t flags)
+{
+ return flags & ndn::nfd::ROUTE_FLAG_CAPTURE;
+}
+
+static inline bool
+isAnyFlagSet(uint64_t flags)
+{
+ return isChildInheritFlagSet(flags) || isCaptureFlagSet(flags);
+}
+
+static inline bool
+areBothFlagsSet(uint64_t flags)
+{
+ return isChildInheritFlagSet(flags) && isCaptureFlagSet(flags);
+}
+
Rib::Rib()
: m_nItems(0)
{
@@ -66,7 +96,6 @@
return shared_ptr<FaceEntry>();
}
-
void
Rib::insert(const Name& prefix, const FaceEntry& face)
{
@@ -83,19 +112,32 @@
if (faceIt == entry->end())
{
+ // Will the new face change the namespace's capture flag?
+ bool captureWasTurnedOn = (entry->hasCapture() == false && isCaptureFlagSet(face.flags));
+
// New face
entry->insertFace(face);
m_nItems++;
// Register with face lookup table
m_faceMap[face.faceId].push_back(entry);
+
+ createFibUpdatesForNewFaceEntry(*entry, face, captureWasTurnedOn);
}
- else
+ else // Entry exists, update fields
{
- // Entry exists, update other fields
+ // Save flags for update processing
+ uint64_t previousFlags = faceIt->flags;
+
+ // If the entry's cost didn't change and child inherit is not set,
+ // no need to traverse subtree.
+ uint64_t previousCost = faceIt->cost;
+
faceIt->flags = face.flags;
faceIt->cost = face.cost;
faceIt->expires = face.expires;
+
+ createFibUpdatesForUpdatedEntry(*entry, face, previousFlags, previousCost);
}
}
else // New name prefix
@@ -136,6 +178,8 @@
// Register with face lookup table
m_faceMap[face.faceId].push_back(entry);
+
+ createFibUpdatesForNewRibEntry(*entry, face);
}
}
@@ -150,15 +194,39 @@
{
shared_ptr<RibEntry> entry(ribIt->second);
- if (entry->eraseFace(face))
+ const bool hadCapture = entry->hasCapture();
+
+ // Need to copy face to do FIB updates with correct cost and flags since nfdc does not
+ // pass flags or cost
+ RibEntry::iterator faceIt = entry->findFace(face);
+ FaceEntry faceToErase = *faceIt;
+ faceToErase.flags = faceIt->flags;
+ faceToErase.cost = faceIt->cost;
+
+ if (faceIt != entry->end())
{
+ entry->eraseFace(faceIt);
m_nItems--;
+ const bool captureWasTurnedOff = (hadCapture && !entry->hasCapture());
+
+ createFibUpdatesForErasedFaceEntry(*entry, faceToErase, captureWasTurnedOff);
+
// If this RibEntry no longer has this faceId, unregister from face lookup table
if (!entry->hasFaceId(face.faceId))
{
m_faceMap[face.faceId].remove(entry);
}
+ else
+ {
+ // The RibEntry still has the face ID; need to update FIB
+ // with lowest cost for the same face instead of removing the face from the FIB
+ shared_ptr<FaceEntry> lowCostFace = entry->getFaceWithLowestCostByFaceId(face.faceId);
+
+ BOOST_ASSERT(static_cast<bool>(lowCostFace));
+
+ createFibUpdatesForNewFaceEntry(*entry, *lowCostFace, false);
+ }
// If a RibEntry's facelist is empty, remove it from the tree
if (entry->getFaces().size() == 0)
@@ -187,12 +255,19 @@
{
shared_ptr<RibEntry> entry = *entryIt;
+ const bool hadCapture = entry->hasCapture();
+
// Find the faces in the entry
for (RibEntry::iterator faceIt = entry->begin(); faceIt != entry->end(); ++faceIt)
{
if (faceIt->faceId == faceId)
{
+ FaceEntry copy = *faceIt;
+
faceIt = entry->eraseFace(faceIt);
+
+ const bool captureWasTurnedOff = (hadCapture && !entry->hasCapture());
+ createFibUpdatesForErasedFaceEntry(*entry, copy, captureWasTurnedOff);
}
}
@@ -264,6 +339,9 @@
shared_ptr<RibEntry> entry(it->second);
+ // Remove inherited routes from namespace
+ createFibUpdatesForErasedRibEntry(*entry);
+
shared_ptr<RibEntry> parent = entry->getParent();
// Remove self from parent's children
@@ -295,6 +373,468 @@
return nextIt;
}
+bool
+compareFibUpdates(const shared_ptr<const FibUpdate> lhs, const shared_ptr<const FibUpdate> rhs)
+{
+ return ((lhs->name == rhs->name) &&
+ (lhs->faceId == rhs->faceId));
+}
+
+void
+Rib::insertFibUpdate(shared_ptr<FibUpdate> update)
+{
+ // If an update with the same name and face already exists,
+ // replace it
+ FibUpdateList::iterator it = std::find_if(m_fibUpdateList.begin(), m_fibUpdateList.end(),
+ bind(&compareFibUpdates, _1, update));
+
+ if (it != m_fibUpdateList.end())
+ {
+ // Get rid of the const to alter the action, prevents copying or removal and
+ // insertion
+ FibUpdate& entry = const_cast<FibUpdate&>(*(*it));
+ entry.action = update->action;
+ entry.cost = update->cost;
+ }
+ else
+ {
+ m_fibUpdateList.push_back(update);
+ }
+}
+
+void
+Rib::createFibUpdatesForNewRibEntry(RibEntry& entry, const FaceEntry& face)
+{
+ // Create FIB update for new entry
+ insertFibUpdate(FibUpdate::createAddUpdate(entry.getName(), face.faceId, face.cost));
+
+ // No flags are set
+ if (!isAnyFlagSet(face.flags))
+ {
+ // Add ancestor faces to self
+ addInheritedFacesToEntry(entry, getAncestorFaces(entry));
+ }
+ else if (areBothFlagsSet(face.flags))
+ {
+ // Add face to children
+ FaceSet facesToAdd;
+ facesToAdd.insert(face);
+
+ // Remove faces blocked by capture and add self to children
+ modifyChildrensInheritedFaces(entry, facesToAdd, getAncestorFaces(entry));
+ }
+ else if (isChildInheritFlagSet(face.flags))
+ {
+ FaceSet ancestorFaces = getAncestorFaces(entry);
+
+ // Add ancestor faces to self
+ addInheritedFacesToEntry(entry, ancestorFaces);
+
+ // If there is an ancestor face which is the same as the new face, replace it
+ // with the new face
+ FaceSet::iterator it = ancestorFaces.find(face);
+
+ // There is a face that needs to be overwritten, erase and then replace
+ if (it != ancestorFaces.end())
+ {
+ ancestorFaces.erase(it);
+ }
+
+ // Add new face to ancestor list so it can be added to children
+ ancestorFaces.insert(face);
+
+ // Add ancestor faces to children
+ modifyChildrensInheritedFaces(entry, ancestorFaces, FaceSet());
+ }
+ else if (isCaptureFlagSet(face.flags))
+ {
+ // Remove faces blocked by capture
+ modifyChildrensInheritedFaces(entry, FaceSet(), getAncestorFaces(entry));
+ }
+}
+
+void
+Rib::createFibUpdatesForNewFaceEntry(RibEntry& entry, const FaceEntry& face,
+ bool captureWasTurnedOn)
+{
+ // Only update if the new face has a lower cost than a previously installed face
+ shared_ptr<FaceEntry> prevFace = entry.getFaceWithLowestCostAndChildInheritByFaceId(face.faceId);
+
+ FaceSet facesToAdd;
+ if (isChildInheritFlagSet(face.flags))
+ {
+ // Add to children if this new face doesn't override a previous lower cost, or
+ // add to children if this new is lower cost than a previous face.
+ // Less than equal, since entry may find this face
+ if (!static_cast<bool>(prevFace) || face.cost <= prevFace->cost)
+ {
+ // Add self to children
+ facesToAdd.insert(face);
+ }
+ }
+
+ FaceSet facesToRemove;
+ if (captureWasTurnedOn)
+ {
+ // Capture flag on
+ facesToRemove = getAncestorFaces(entry);
+
+ // Remove ancestor faces from self
+ removeInheritedFacesFromEntry(entry, facesToRemove);
+ }
+
+ modifyChildrensInheritedFaces(entry, facesToAdd, facesToRemove);
+
+ // If another face with same faceId and lower cost, don't update.
+ // Must be done last so that add updates replace removal updates
+ // Create FIB update for new entry
+ if (face.cost <= entry.getFaceWithLowestCostByFaceId(face.faceId)->cost)
+ {
+ insertFibUpdate(FibUpdate::createAddUpdate(entry.getName(), face.faceId, face.cost));
+ }
+}
+
+void
+Rib::createFibUpdatesForUpdatedEntry(RibEntry& entry, const FaceEntry& face,
+ const uint64_t previousFlags, const uint64_t previousCost)
+{
+ const bool costDidChange = (face.cost != previousCost);
+
+ // Look for an installed face with the lowest cost and child inherit set
+ shared_ptr<FaceEntry> prevFace = entry.getFaceWithLowestCostAndChildInheritByFaceId(face.faceId);
+
+ // No flags changed and cost didn't change, no change in FIB
+ if (face.flags == previousFlags && !costDidChange)
+ {
+ return;
+ }
+
+ // Cost changed so create update for the entry itself
+ if (costDidChange)
+ {
+ // Create update if this face's cost is lower than other faces
+ if (face.cost <= entry.getFaceWithLowestCostByFaceId(face.faceId)->cost)
+ {
+ // Create FIB update for the updated entry
+ insertFibUpdate(FibUpdate::createAddUpdate(entry.getName(), face.faceId, face.cost));
+ }
+ else if (previousCost < entry.getFaceWithLowestCostByFaceId(face.faceId)->cost)
+ {
+ // Create update if this face used to be the lowest face but is no longer
+ // the lowest cost face.
+ insertFibUpdate(FibUpdate::createAddUpdate(entry.getName(), prevFace->faceId,
+ prevFace->cost));
+ }
+
+ // If another face with same faceId and lower cost and ChildInherit exists,
+ // don't update children.
+ if (!static_cast<bool>(prevFace) || face.cost <= prevFace->cost)
+ {
+ // If no flags changed but child inheritance is set, need to update children
+ // with new cost
+ if ((face.flags == previousFlags) && isChildInheritFlagSet(face.flags))
+ {
+ // Add self to children
+ FaceSet facesToAdd;
+ facesToAdd.insert(face);
+ modifyChildrensInheritedFaces(entry, facesToAdd, FaceSet());
+
+ return;
+ }
+ }
+ }
+
+ // Child inherit was turned on
+ if (!isChildInheritFlagSet(previousFlags) && isChildInheritFlagSet(face.flags))
+ {
+ // If another face with same faceId and lower cost and ChildInherit exists,
+ // don't update children.
+ if (!static_cast<bool>(prevFace) || face.cost <= prevFace->cost)
+ {
+ // Add self to children
+ FaceSet facesToAdd;
+ facesToAdd.insert(face);
+ modifyChildrensInheritedFaces(entry, facesToAdd, FaceSet());
+ }
+
+ } // Child inherit was turned off
+ else if (isChildInheritFlagSet(previousFlags) && !isChildInheritFlagSet(face.flags))
+ {
+ // Remove self from children
+ FaceSet facesToRemove;
+ facesToRemove.insert(face);
+
+ FaceSet facesToAdd;
+ // If another face with same faceId and ChildInherit exists, update children with this face.
+ if (static_cast<bool>(prevFace))
+ {
+ facesToAdd.insert(*prevFace);
+ }
+ else
+ {
+ // Look for an ancestor that was blocked previously
+ const FaceSet ancestorFaces = getAncestorFaces(entry);
+ FaceSet::iterator it = ancestorFaces.find(face);
+
+ // If an ancestor is found, add it to children
+ if (it != ancestorFaces.end())
+ {
+ facesToAdd.insert(*it);
+ }
+ }
+
+ modifyChildrensInheritedFaces(entry, facesToAdd, facesToRemove);
+ }
+
+ // Capture was turned on
+ if (!isCaptureFlagSet(previousFlags) && isCaptureFlagSet(face.flags))
+ {
+ FaceSet ancestorFaces = getAncestorFaces(entry);
+
+ // Remove ancestor faces from self
+ removeInheritedFacesFromEntry(entry, ancestorFaces);
+
+ // Remove ancestor faces from children
+ modifyChildrensInheritedFaces(entry, FaceSet(), ancestorFaces);
+ } // Capture was turned off
+ else if (isCaptureFlagSet(previousFlags) && !isCaptureFlagSet(face.flags))
+ {
+ FaceSet ancestorFaces = getAncestorFaces(entry);
+
+ // Add ancestor faces to self
+ addInheritedFacesToEntry(entry, ancestorFaces);
+
+ // Add ancestor faces to children
+ modifyChildrensInheritedFaces(entry, ancestorFaces, FaceSet());
+ }
+}
+
+void
+Rib::createFibUpdatesForErasedFaceEntry(RibEntry& entry, const FaceEntry& face,
+ const bool captureWasTurnedOff)
+{
+ insertFibUpdate(FibUpdate::createRemoveUpdate(entry.getName(), face.faceId));
+
+ if (areBothFlagsSet(face.flags))
+ {
+ // Remove self from children
+ FaceSet facesToRemove;
+ facesToRemove.insert(face);
+
+ // If capture is turned off for the route, need to add ancestors
+ // to self and children
+ FaceSet facesToAdd;
+ if (captureWasTurnedOff)
+ {
+ // Look for an ancestors that were blocked previously
+ facesToAdd = getAncestorFaces(entry);
+
+ // Add ancestor faces to self
+ addInheritedFacesToEntry(entry, facesToAdd);
+ }
+
+ modifyChildrensInheritedFaces(entry, facesToAdd, facesToRemove);
+ }
+ else if (isChildInheritFlagSet(face.flags))
+ {
+ // If not blocked by capture, add inherited routes to children
+ FaceSet facesToAdd;
+ if (!entry.hasCapture())
+ {
+ facesToAdd = getAncestorFaces(entry);
+ }
+
+ FaceSet facesToRemove;
+ facesToRemove.insert(face);
+
+ // Add ancestor faces to children
+ modifyChildrensInheritedFaces(entry, facesToAdd, facesToRemove);
+ }
+ else if (isCaptureFlagSet(face.flags))
+ {
+ // If capture is turned off for the route, need to add ancestors
+ // to self and children
+ FaceSet facesToAdd;
+ if (captureWasTurnedOff)
+ {
+ // Look for an ancestors that were blocked previously
+ facesToAdd = getAncestorFaces(entry);
+
+ // Add ancestor faces to self
+ addInheritedFacesToEntry(entry, facesToAdd);
+ }
+
+ modifyChildrensInheritedFaces(entry, facesToAdd, FaceSet());
+ }
+
+ // Need to check if the removed face was blocking an inherited route
+ FaceSet ancestorFaces = getAncestorFaces(entry);
+
+ if (!entry.hasCapture())
+ {
+ // If there is an ancestor face which is the same as the erased face, add that face
+ // to the current entry
+ FaceSet::iterator it = ancestorFaces.find(face);
+
+ if (it != ancestorFaces.end())
+ {
+ entry.addInheritedFace(*it);
+ insertFibUpdate(FibUpdate::createAddUpdate(entry.getName(), it->faceId, it->cost));
+ }
+ }
+}
+
+void
+Rib::createFibUpdatesForErasedRibEntry(RibEntry& entry)
+{
+ for (RibEntry::FaceList::iterator it = entry.getInheritedFaces().begin();
+ it != entry.getInheritedFaces().end(); ++it)
+ {
+ insertFibUpdate(FibUpdate::createRemoveUpdate(entry.getName(), it->faceId));
+ }
+}
+
+Rib::FaceSet
+Rib::getAncestorFaces(const RibEntry& entry) const
+{
+ FaceSet ancestorFaces(&sortFace);
+
+ shared_ptr<RibEntry> parent = entry.getParent();
+
+ while (static_cast<bool>(parent))
+ {
+ for (RibEntry::iterator it = parent->getFaces().begin();
+ it != parent->getFaces().end(); ++it)
+ {
+ if (isChildInheritFlagSet(it->flags))
+ {
+ ancestorFaces.insert(*it);
+ }
+ }
+
+ if (parent->hasCapture())
+ {
+ break;
+ }
+
+ parent = parent->getParent();
+ }
+
+ return ancestorFaces;
+}
+
+void
+Rib::addInheritedFacesToEntry(RibEntry& entry, const Rib::FaceSet& facesToAdd)
+{
+ for (FaceSet::const_iterator it = facesToAdd.begin(); it != facesToAdd.end(); ++it)
+ {
+ // Don't add an ancestor faceId if the namespace has an entry for that faceId
+ if (!entry.hasFaceId(it->faceId))
+ {
+ entry.addInheritedFace(*it);
+ insertFibUpdate(FibUpdate::createAddUpdate(entry.getName(), it->faceId, it->cost));
+ }
+ }
+}
+
+void
+Rib::removeInheritedFacesFromEntry(RibEntry& entry, const Rib::FaceSet& facesToRemove)
+{
+ for (FaceSet::const_iterator it = facesToRemove.begin(); it != facesToRemove.end(); ++it)
+ {
+ // Only remove if the face has been inherited
+ if (entry.hasInheritedFace(*it))
+ {
+ entry.removeInheritedFace(*it);
+ insertFibUpdate(FibUpdate::createRemoveUpdate(entry.getName(), it->faceId));
+ }
+ }
+}
+
+void
+Rib::modifyChildrensInheritedFaces(RibEntry& entry, const Rib::FaceSet& facesToAdd,
+ const Rib::FaceSet& facesToRemove)
+{
+ RibEntryList children = entry.getChildren();
+
+ for (RibEntryList::iterator child = children.begin(); child != children.end(); ++child)
+ {
+ traverseSubTree(*(*child), facesToAdd, facesToRemove);
+ }
+}
+
+void
+Rib::traverseSubTree(RibEntry& entry, Rib::FaceSet facesToAdd,
+ Rib::FaceSet facesToRemove)
+{
+ // If a route on the namespace has the capture flag set, ignore self and children
+ if (entry.hasCapture())
+ {
+ return;
+ }
+
+ // Remove inherited faces from current namespace
+ for (Rib::FaceSet::const_iterator removeIt = facesToRemove.begin();
+ removeIt != facesToRemove.end(); )
+ {
+ // If a route on the namespace has the same face and child inheritance set, ignore this face
+ if (entry.hasChildInheritOnFaceId(removeIt->faceId))
+ {
+ facesToRemove.erase(removeIt++);
+ continue;
+ }
+
+ // Only remove face if it removes an existing inherited route
+ if (entry.hasInheritedFace(*removeIt))
+ {
+ entry.removeInheritedFace(*removeIt);
+ insertFibUpdate(FibUpdate::createRemoveUpdate(entry.getName(), removeIt->faceId));
+ }
+
+ ++removeIt;
+ }
+
+ // Add inherited faces to current namespace
+ for (Rib::FaceSet::const_iterator addIt = facesToAdd.begin();
+ addIt != facesToAdd.end(); )
+ {
+ // If a route on the namespace has the same face and child inherit set, ignore this face
+ if (entry.hasChildInheritOnFaceId(addIt->faceId))
+ {
+ facesToAdd.erase(addIt++);
+ continue;
+ }
+
+ // Only add face if it does not override an existing route
+ if (!entry.hasFaceId(addIt->faceId))
+ {
+ RibEntry::FaceList::iterator faceIt = entry.findInheritedFace(*addIt);
+
+ // If the entry already has the inherited face, just update the face
+ if (faceIt != entry.getInheritedFaces().end())
+ {
+ faceIt->cost = addIt->cost;
+ }
+ else // Otherwise, this is a newly inherited face
+ {
+ entry.addInheritedFace(*addIt);
+ }
+
+ insertFibUpdate(FibUpdate::createAddUpdate(entry.getName(), addIt->faceId, addIt->cost));
+ }
+
+ ++addIt;
+ }
+
+ Rib::RibEntryList children = entry.getChildren();
+
+ // Apply face operations to current namespace's children
+ for (Rib::RibEntryList::iterator child = children.begin(); child != children.end(); ++child)
+ {
+ traverseSubTree(*(*child), facesToAdd, facesToRemove);
+ }
+}
+
std::ostream&
operator<<(std::ostream& os, const Rib& rib)
{
diff --git a/rib/rib.hpp b/rib/rib.hpp
index 37136bc..89cad32 100644
--- a/rib/rib.hpp
+++ b/rib/rib.hpp
@@ -26,6 +26,8 @@
#ifndef NFD_RIB_RIB_HPP
#define NFD_RIB_RIB_HPP
+#include "rib-entry.hpp"
+#include "fib-update.hpp"
#include "common.hpp"
#include "rib-entry.hpp"
#include <ndn-cxx/management/nfd-control-command.hpp>
@@ -42,6 +44,9 @@
typedef std::map<Name, shared_ptr<RibEntry> > RibTable;
typedef RibTable::const_iterator const_iterator;
typedef std::map<uint64_t, std::list<shared_ptr<RibEntry> > > FaceLookupTable;
+ typedef bool (*FaceComparePredicate)(const FaceEntry&, const FaceEntry&);
+ typedef std::set<FaceEntry, FaceComparePredicate> FaceSet;
+ typedef std::list<shared_ptr<const FibUpdate> > FibUpdateList;
Rib();
@@ -74,7 +79,6 @@
bool
empty() const;
-
shared_ptr<RibEntry>
findParent(const Name& prefix) const;
@@ -84,15 +88,62 @@
std::list<shared_ptr<RibEntry> >
findDescendants(const Name& prefix) const;
+ const std::list<shared_ptr<const FibUpdate> >&
+ getFibUpdates() const;
+
+ void
+ clearFibUpdates();
+
+private:
RibTable::iterator
eraseEntry(RibTable::iterator it);
void
- eraseEntry(const Name& name);
+ insertFibUpdate(shared_ptr<FibUpdate> update);
+
+ void
+ createFibUpdatesForNewRibEntry(RibEntry& entry, const FaceEntry& face);
+
+ void
+ createFibUpdatesForNewFaceEntry(RibEntry& entry, const FaceEntry& face,
+ const bool captureWasTurnedOn);
+
+ void
+ createFibUpdatesForUpdatedEntry(RibEntry& entry, const FaceEntry& face,
+ const uint64_t previousFlags, const uint64_t previousCost);
+ void
+ createFibUpdatesForErasedFaceEntry(RibEntry& entry, const FaceEntry& face,
+ const bool captureWasTurnedOff);
+
+ void
+ createFibUpdatesForErasedRibEntry(RibEntry& entry);
+
+ FaceSet
+ getAncestorFaces(const RibEntry& entry) const;
+
+ void
+ modifyChildrensInheritedFaces(RibEntry& entry, const Rib::FaceSet& facesToAdd,
+ const Rib::FaceSet& facesToRemove);
+
+ void
+ traverseSubTree(RibEntry& entry, Rib::FaceSet facesToAdd,
+ Rib::FaceSet facesToRemove);
+
+ /** \brief Adds passed faces to the entry's inherited faces list
+ */
+ void
+ addInheritedFacesToEntry(RibEntry& entry, const Rib::FaceSet& facesToAdd);
+
+ /** \brief Removes passed faces from the entry's inherited faces list
+ */
+ void
+ removeInheritedFacesFromEntry(RibEntry& entry, const Rib::FaceSet& facesToRemove);
private:
RibTable m_rib;
FaceLookupTable m_faceMap;
+ FibUpdateList m_fibUpdateList;
+
size_t m_nItems;
};
@@ -120,11 +171,17 @@
return m_rib.empty();
}
-std::ostream&
-operator<<(std::ostream& os, const FaceEntry& entry);
+inline const Rib::FibUpdateList&
+Rib::getFibUpdates() const
+{
+ return m_fibUpdateList;
+}
-std::ostream&
-operator<<(std::ostream& os, const RibEntry& entry);
+inline void
+Rib::clearFibUpdates()
+{
+ m_fibUpdateList.clear();
+}
std::ostream&
operator<<(std::ostream& os, const Rib& rib);
diff --git a/tests/rib/fib-updates-common.hpp b/tests/rib/fib-updates-common.hpp
new file mode 100644
index 0000000..c8c0af4
--- /dev/null
+++ b/tests/rib/fib-updates-common.hpp
@@ -0,0 +1,112 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014, Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology,
+ * The University of Memphis
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD 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
+ * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+namespace nfd {
+namespace rib {
+namespace tests {
+
+inline FaceEntry
+createFaceEntry(uint64_t faceId, uint64_t origin, uint64_t cost, uint64_t flags)
+{
+ FaceEntry temp;
+ temp.faceId = faceId;
+ temp.origin = origin;
+ temp.cost = cost;
+ temp.flags = flags;
+
+ return temp;
+}
+
+inline bool
+compareNameFaceIdCostAction(const shared_ptr<const FibUpdate>& lhs,
+ const shared_ptr<const FibUpdate>& rhs)
+{
+ if (lhs->name < rhs->name)
+ {
+ return true;
+ }
+ else if (lhs->name == rhs->name)
+ {
+ if (lhs->faceId < rhs->faceId)
+ {
+ return true;
+ }
+ else if (lhs->faceId == rhs->faceId)
+ {
+ if (lhs->cost < rhs->cost)
+ {
+ return true;
+ }
+ else if (lhs->cost == rhs->cost)
+ {
+ return lhs->action < rhs->action;
+ }
+ }
+ }
+
+ return false;
+}
+
+class FibUpdatesFixture : public nfd::tests::BaseFixture
+{
+public:
+ void
+ insertFaceEntry(const Name& name, uint64_t faceId, uint64_t origin, uint64_t cost, uint64_t flags)
+ {
+ rib::FaceEntry faceEntry;
+ faceEntry.faceId = faceId;
+ faceEntry.origin = origin;
+ faceEntry.cost = cost;
+ faceEntry.flags = flags;
+
+ rib.insert(name, faceEntry);
+ }
+
+ void
+ eraseFaceEntry(const Name& name, uint64_t faceId, uint64_t origin)
+ {
+ rib::FaceEntry faceEntry;
+ faceEntry.faceId = faceId;
+ faceEntry.origin = origin;
+
+ rib.erase(name, faceEntry);
+ }
+
+
+ Rib::FibUpdateList
+ getSortedFibUpdates()
+ {
+ Rib::FibUpdateList updates = rib.getFibUpdates();
+ updates.sort(&compareNameFaceIdCostAction);
+ return updates;
+ }
+
+public:
+ rib::Rib rib;
+};
+
+} // namespace tests
+} // namespace rib
+} // namespace nfd
diff --git a/tests/rib/fib-updates-erase-face.cpp b/tests/rib/fib-updates-erase-face.cpp
new file mode 100644
index 0000000..e56c0d3
--- /dev/null
+++ b/tests/rib/fib-updates-erase-face.cpp
@@ -0,0 +1,396 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014, Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology,
+ * The University of Memphis
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD 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
+ * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "rib/rib.hpp"
+
+#include "tests/test-common.hpp"
+#include "fib-updates-common.hpp"
+
+namespace nfd {
+namespace rib {
+namespace tests {
+
+BOOST_FIXTURE_TEST_SUITE(FibUpdates, FibUpdatesFixture)
+
+BOOST_AUTO_TEST_SUITE(EraseFace)
+
+BOOST_AUTO_TEST_CASE(WithInheritedFace_Root)
+{
+ insertFaceEntry("/", 1, 0, 10, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a", 1, 0, 50, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a/b", 2, 0, 75, 0);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 1 updates: 1 to remove face 1 from /
+ eraseFaceEntry("/", 1, 0);
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 1);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::REMOVE_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_CASE(WithInheritedFace)
+{
+ insertFaceEntry("/a", 5, 0, 10, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a", 5, 255, 5, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a", 2, 0, 20, 0);
+ insertFaceEntry("/a/b", 3, 0, 5, 0);
+
+ // /a should have face 5 with cost 10; /a/b should have face 3 with cost 5 and
+ // face 5 with cost 10
+ eraseFaceEntry("/a", 5, 255);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 2 updates: 1 to remove face 3 from /a/b and one to remove inherited face.
+ eraseFaceEntry("/a/b", 3, 0);
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 2);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/a/b");
+ BOOST_CHECK_EQUAL((*update)->faceId, 3);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::REMOVE_NEXTHOP);
+
+ ++update;
+ BOOST_CHECK_EQUAL((*update)->name, "/a/b");
+ BOOST_CHECK_EQUAL((*update)->faceId, 5);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::REMOVE_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_CASE(MultipleFaces)
+{
+ insertFaceEntry("/a", 5, 0, 10, 0);
+ insertFaceEntry("/a", 5, 255, 5, 0);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 1 updates: 1 to update cost to 10 for /a
+ eraseFaceEntry("/a", 5, 255);
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 1);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/a");
+ BOOST_CHECK_EQUAL((*update)->faceId, 5);
+ BOOST_CHECK_EQUAL((*update)->cost, 10);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_CASE(NoFlags_NoCaptureChange_NoCaptureOnRoute)
+{
+ insertFaceEntry("/", 1, 0, 5, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a", 2, 0, 10, 0);
+ insertFaceEntry("/a/b", 3, 0, 10, 0);
+ insertFaceEntry("/a/c", 1, 0, 100, 0);
+ insertFaceEntry("/a", 1, 128, 50, 0);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 1 updates: 1 to update cost for /a
+ eraseFaceEntry("/a", 1, 128);
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 1);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/a");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 5);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_CASE(MakeRibEmpty)
+{
+ insertFaceEntry("/", 1, 0, 5, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 1 updates: 1 to remove face from /
+ eraseFaceEntry("/", 1, 0);
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 1);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::REMOVE_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_CASE(NoFlags_NoCaptureChange_CaptureOnRoute)
+{
+ insertFaceEntry("/", 1, 0, 5, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a", 2, 0, 10, ndn::nfd::ROUTE_FLAG_CAPTURE);
+ insertFaceEntry("/a/b", 3, 0, 10, 0);
+ insertFaceEntry("/a/c", 1, 0, 100, 0);
+ insertFaceEntry("/a", 1, 128, 50, 0);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 1 updates: 1 to remove face from /a
+ eraseFaceEntry("/a", 1, 128);
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 1);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/a");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::REMOVE_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_CASE(BothFlags_NoCaptureChange_CaptureOnRoute)
+{
+ insertFaceEntry("/", 1, 0, 5, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a", 2, 0, 10, ndn::nfd::ROUTE_FLAG_CAPTURE);
+ insertFaceEntry("/a/b", 3, 0, 10, 0);
+ insertFaceEntry("/a/c", 1, 0, 100, 0);
+ insertFaceEntry("/a", 1, 128, 50, (ndn::nfd::ROUTE_FLAG_CHILD_INHERIT |
+ ndn::nfd::ROUTE_FLAG_CAPTURE));
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 2 updates: 1 to remove face1 from /a and
+ // 1 to remove face1 to /a/b
+ eraseFaceEntry("/a", 1, 128);
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 2);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/a");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::REMOVE_NEXTHOP);
+
+ ++update;
+ BOOST_CHECK_EQUAL((*update)->name, "/a/b");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::REMOVE_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_CASE(BothFlags_CaptureChange_NoCaptureOnRoute)
+{
+ insertFaceEntry("/", 1, 0, 5, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a", 2, 0, 10, 0);
+ insertFaceEntry("/a/b", 3, 0, 10, 0);
+ insertFaceEntry("/a/c", 1, 0, 100, 0);
+ insertFaceEntry("/a", 1, 128, 50, (ndn::nfd::ROUTE_FLAG_CHILD_INHERIT |
+ ndn::nfd::ROUTE_FLAG_CAPTURE));
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 2 updates: 1 to add face1 to /a and
+ // 1 to add face1 to /a/b
+ eraseFaceEntry("/a", 1, 128);
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 2);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/a");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 5);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+
+ ++update;
+ BOOST_CHECK_EQUAL((*update)->name, "/a/b");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 5);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_CASE(ChildInherit_NoCaptureChange_NoCaptureOnRoute)
+{
+ insertFaceEntry("/", 1, 0, 5, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a", 2, 0, 10, 0);
+ insertFaceEntry("/a/b", 3, 0, 10, 0);
+ insertFaceEntry("/a/c", 1, 0, 100, 0);
+ insertFaceEntry("/a", 1, 128, 50, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 2 updates: 2 to add face1 to /a and /a/b
+ eraseFaceEntry("/a", 1, 128);
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 2);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/a");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 5);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+
+ ++update;
+ BOOST_CHECK_EQUAL((*update)->name, "/a/b");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 5);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_CASE(ChildInherit_NoCaptureChange_CaptureOnRoute)
+{
+ insertFaceEntry("/", 1, 0, 5, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a", 2, 0, 10, ndn::nfd::ROUTE_FLAG_CAPTURE);
+ insertFaceEntry("/a/b", 3, 0, 10, 0);
+ insertFaceEntry("/a/c", 1, 0, 100, 0);
+ insertFaceEntry("/a", 1, 128, 50, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 2 updates: 2 to remove face 1 from /a and /a/b
+ eraseFaceEntry("/a", 1, 128);
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 2);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/a");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::REMOVE_NEXTHOP);
+
+ ++update;
+ BOOST_CHECK_EQUAL((*update)->name, "/a/b");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::REMOVE_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_CASE(Capture_CaptureChange_NoCaptureOnRoute)
+{
+ insertFaceEntry("/", 1, 0, 5, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a", 2, 0, 10, 0);
+ insertFaceEntry("/a/b", 3, 0, 10, 0);
+ insertFaceEntry("/a/c", 1, 0, 100, 0);
+ insertFaceEntry("/a", 1, 128, 50, ndn::nfd::ROUTE_FLAG_CAPTURE);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 2 updates: 1 to update cost on /a and
+ // 1 to add face1 to /a/b
+ eraseFaceEntry("/a", 1 ,128);
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 2);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/a");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 5);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+
+ ++update;
+ BOOST_CHECK_EQUAL((*update)->name, "/a/b");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 5);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_CASE(Capture_NoCaptureChange_CaptureOnRoute)
+{
+ insertFaceEntry("/", 1, 0, 5, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a", 2, 0, 10, ndn::nfd::ROUTE_FLAG_CAPTURE);
+ insertFaceEntry("/a/b", 3, 0, 10, 0);
+ insertFaceEntry("/a/c", 1, 0, 100, 0);
+ insertFaceEntry("/a", 1, 128, 50, ndn::nfd::ROUTE_FLAG_CAPTURE);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 1 updates: 1 to remove face from /a
+ eraseFaceEntry("/a", 1, 128);
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 1);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/a");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::REMOVE_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_CASE(EraseFaceById)
+{
+ insertFaceEntry("/", 1, 0, 5, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a", 2, 0, 10, 0);
+ insertFaceEntry("/a/b", 3, 0, 10, 0);
+ insertFaceEntry("/a/c", 4, 0, 100, 0);
+ insertFaceEntry("/a", 1, 128, 50, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 4 updates: 4 to remove face ID 1 from /, /a, /a/b, and /a/c
+ rib.erase(1);
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 4);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::REMOVE_NEXTHOP);
+
+ ++update;
+ BOOST_CHECK_EQUAL((*update)->name, "/a");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::REMOVE_NEXTHOP);
+
+ ++update;
+ BOOST_CHECK_EQUAL((*update)->name, "/a/b");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::REMOVE_NEXTHOP);
+
+ ++update;
+ BOOST_CHECK_EQUAL((*update)->name, "/a/c");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::REMOVE_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_SUITE_END() // EraseFace
+
+BOOST_AUTO_TEST_SUITE_END() // FibUpdates
+
+} // namespace tests
+} // namespace rib
+} // namespace nfd
diff --git a/tests/rib/fib-updates-new-face.cpp b/tests/rib/fib-updates-new-face.cpp
new file mode 100644
index 0000000..b8e7d69
--- /dev/null
+++ b/tests/rib/fib-updates-new-face.cpp
@@ -0,0 +1,272 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014, Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology,
+ * The University of Memphis
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD 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
+ * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "rib/rib.hpp"
+
+#include "tests/test-common.hpp"
+#include "fib-updates-common.hpp"
+
+namespace nfd {
+namespace rib {
+namespace tests {
+
+BOOST_FIXTURE_TEST_SUITE(FibUpdates, FibUpdatesFixture)
+
+BOOST_AUTO_TEST_SUITE(NewFace)
+
+BOOST_AUTO_TEST_CASE(Basic)
+{
+ // should generate 1 update
+ insertFaceEntry("/", 1, 0, 50, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+
+ Rib::FibUpdateList updates = rib.getFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 1);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+
+ BOOST_CHECK_EQUAL((*update)->name, "/");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 50);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+
+ // Clear any updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // should generate 2 updates
+ insertFaceEntry("/a", 2, 0, 50, 0);
+
+ updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 2);
+
+ update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/a");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 50);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+
+ ++update;
+ BOOST_CHECK_EQUAL((*update)->name, "/a");
+ BOOST_CHECK_EQUAL((*update)->faceId, 2);
+ BOOST_CHECK_EQUAL((*update)->cost, 50);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // should generate 2 updates
+ insertFaceEntry("/a/b", 3, 0, 10, 0);
+
+ updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 2);
+
+ update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/a/b");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 50);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+
+ ++update;
+ BOOST_CHECK_EQUAL((*update)->name, "/a/b");
+ BOOST_CHECK_EQUAL((*update)->faceId, 3);
+ BOOST_CHECK_EQUAL((*update)->cost, 10);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_CASE(UpdateOnLowerCostNoChildInherit)
+{
+ insertFaceEntry("/", 1, 0, 50, 0);
+
+ // Clear any updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 0 updates
+ insertFaceEntry("/", 1, 128, 75, 0);
+
+ BOOST_CHECK_EQUAL(rib.getFibUpdates().size(), 0);
+}
+
+BOOST_AUTO_TEST_CASE(UpdateOnLowerCostOnly)
+{
+ insertFaceEntry("/", 1, 0, 50, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a", 2, 0, 10, 0);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 2 updates: to update cost for face 1 on / and /a
+ insertFaceEntry("/", 1, 0, 25, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 2);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 25);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+
+ ++update;
+ BOOST_CHECK_EQUAL((*update)->name, "/a");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 25);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 0 updates
+ insertFaceEntry("/", 1, 128, 50, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+
+ BOOST_CHECK_EQUAL(rib.getFibUpdates().size(), 0);
+}
+
+BOOST_AUTO_TEST_CASE(NoCaptureChangeWithoutChildInherit)
+{
+ insertFaceEntry("/", 1, 0, 50, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a", 2, 0, 10, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a/b", 3, 0, 10, 0);
+ insertFaceEntry("/a/c", 4, 0, 10, ndn::nfd::ROUTE_FLAG_CAPTURE);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 1 update: 1 to add face 5 to /a
+ insertFaceEntry("/a", 5, 128, 50, 0);
+
+ const Rib::FibUpdateList& updates = rib.getFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 1);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+
+ BOOST_CHECK_EQUAL((*update)->name, "/a");
+ BOOST_CHECK_EQUAL((*update)->faceId, 5);
+ BOOST_CHECK_EQUAL((*update)->cost, 50);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_CASE(NoCaptureChangeWithChildInherit)
+{
+ insertFaceEntry("/", 1, 0, 50, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a", 2, 0, 10, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a/b", 3, 0, 10, 0);
+ insertFaceEntry("/a/c", 4, 0, 10, ndn::nfd::ROUTE_FLAG_CAPTURE);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 2 updates: one for the inserted face and
+ // one to add face to /a/b
+ insertFaceEntry("/a", 4, 128, 5, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 2);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/a");
+ BOOST_CHECK_EQUAL((*update)->faceId, 4);
+ BOOST_CHECK_EQUAL((*update)->cost, 5);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+
+ ++update;
+ BOOST_CHECK_EQUAL((*update)->name, "/a/b");
+ BOOST_CHECK_EQUAL((*update)->faceId, 4);
+ BOOST_CHECK_EQUAL((*update)->cost, 5);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_CASE(CaptureTurnedOnWithoutChildInherit)
+{
+ insertFaceEntry("/", 1, 0, 50, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a", 2, 0, 10, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a/b", 3, 0, 10, 0);
+ insertFaceEntry("/a/c", 4, 0, 10, 0);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 3 updates:
+ // - one for the inserted face for /a and
+ // - two to remove face1 from /a/b and /a/c
+ insertFaceEntry("/a", 1, 128, 50, ndn::nfd::ROUTE_FLAG_CAPTURE);
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 3);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/a");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 50);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+
+ ++update;
+ BOOST_CHECK_EQUAL((*update)->name, "/a/b");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::REMOVE_NEXTHOP);
+
+ ++update;
+ BOOST_CHECK_EQUAL((*update)->name, "/a/c");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::REMOVE_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_CASE(CaptureTurnedOnWithChildInherit)
+{
+ insertFaceEntry("/", 1, 0, 50, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a", 2, 0, 10, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a/b", 3, 0, 10, 0);
+ insertFaceEntry("/a/c", 4, 0, 10, 0);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 2 updates:
+ // - one for the inserted face for /a and
+ // - one to update /a/b with the new cost
+ insertFaceEntry("/a", 1, 128, 50, (ndn::nfd::ROUTE_FLAG_CAPTURE |
+ ndn::nfd::ROUTE_FLAG_CHILD_INHERIT));
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 3);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/a");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 50);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+
+ ++update;
+ BOOST_CHECK_EQUAL((*update)->name, "/a/b");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 50);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_SUITE_END() // NewFace
+
+BOOST_AUTO_TEST_SUITE_END() // FibUpdates
+
+} // namespace tests
+} // namespace rib
+} // namespace nfd
diff --git a/tests/rib/fib-updates-new-namespace.cpp b/tests/rib/fib-updates-new-namespace.cpp
new file mode 100644
index 0000000..e409c51
--- /dev/null
+++ b/tests/rib/fib-updates-new-namespace.cpp
@@ -0,0 +1,202 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014, Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology,
+ * The University of Memphis
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD 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
+ * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "rib/rib.hpp"
+
+#include "tests/test-common.hpp"
+#include "fib-updates-common.hpp"
+
+namespace nfd {
+namespace rib {
+namespace tests {
+
+BOOST_FIXTURE_TEST_SUITE(FibUpdates, FibUpdatesFixture)
+
+BOOST_AUTO_TEST_SUITE(NewNamespace)
+
+BOOST_AUTO_TEST_CASE(NoFlags)
+{
+ // No flags, empty RIB, should generate 1 update for the inserted face
+ insertFaceEntry("/a/b", 1, 0, 10, 0);
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 1);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/a/b");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 10);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+
+ // Reset RIB
+ eraseFaceEntry("/a/b", 1, 0);
+ rib.clearFibUpdates();
+
+ // Parent with child inherit flag
+ insertFaceEntry("/a", 2, 0, 70, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a", 3, 0, 30, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 3 updates, 1 for the inserted face and 2 from inheritance
+ insertFaceEntry("/a/b", 1, 0, 10, 0);
+
+ updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 3);
+
+ update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/a/b");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 10);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+
+ ++update;
+ BOOST_CHECK_EQUAL((*update)->name, "/a/b");
+ BOOST_CHECK_EQUAL((*update)->faceId, 2);
+ BOOST_CHECK_EQUAL((*update)->cost, 70);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+
+ ++update;
+ BOOST_CHECK_EQUAL((*update)->name, "/a/b");
+ BOOST_CHECK_EQUAL((*update)->faceId, 3);
+ BOOST_CHECK_EQUAL((*update)->cost, 30);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_CASE(BothFlags)
+{
+ // Empty RIB, should generate 1 update for the inserted face
+ insertFaceEntry("/a", 1, 0, 10, (ndn::nfd::ROUTE_FLAG_CHILD_INHERIT |
+ ndn::nfd::ROUTE_FLAG_CAPTURE));
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 1);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/a");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 10);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+
+ // Reset RIB
+ eraseFaceEntry("/a", 1, 0);
+ rib.clearFibUpdates();
+
+ insertFaceEntry("/", 2, 0, 70, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a/b", 3, 0, 30, 0);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 3 updates, 1 for the inserted face, 1 to add the face to the child,
+ // and 1 to remove the previously inherited entry
+ insertFaceEntry("/a", 1, 0, 10, (ndn::nfd::ROUTE_FLAG_CHILD_INHERIT |
+ ndn::nfd::ROUTE_FLAG_CAPTURE));
+
+ updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 3);
+
+ update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/a");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 10);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+
+ ++update;
+ BOOST_CHECK_EQUAL((*update)->name, "/a/b");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 10);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+
+ ++update;
+ BOOST_CHECK_EQUAL((*update)->name, "/a/b");
+ BOOST_CHECK_EQUAL((*update)->faceId, 2);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::REMOVE_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_CASE(ChildInherit)
+{
+ insertFaceEntry("/", 1, 0, 50, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a/b", 2, 0, 10, 0);
+ insertFaceEntry("/a/c", 3, 0, 10, ndn::nfd::ROUTE_FLAG_CAPTURE);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 2 updates: 1 for the inserted face and 1 to add the face to "/a/b"
+ insertFaceEntry("/a", 1, 0, 10, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 2);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/a");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 10);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+
+ ++update;
+ BOOST_CHECK_EQUAL((*update)->name, "/a/b");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 10);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_CASE(Capture)
+{
+ insertFaceEntry("/", 1, 0, 50, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a/b", 2, 0, 10, 0);
+ insertFaceEntry("/a/c", 3, 0, 10, ndn::nfd::ROUTE_FLAG_CAPTURE);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 2 updates: 1 for the inserted face and
+ // 1 to remove inherited face from "/a/b"
+ insertFaceEntry("/a", 1, 0, 10, ndn::nfd::ROUTE_FLAG_CAPTURE);
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 2);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/a");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 10);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+
+ ++update;
+ BOOST_CHECK_EQUAL((*update)->name, "/a/b");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::REMOVE_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_SUITE_END() // NewNamespace
+
+BOOST_AUTO_TEST_SUITE_END() // FibUpdates
+
+} // namespace tests
+} // namespace rib
+} // namespace nfd
diff --git a/tests/rib/fib-updates-update-face.cpp b/tests/rib/fib-updates-update-face.cpp
new file mode 100644
index 0000000..13f5e21
--- /dev/null
+++ b/tests/rib/fib-updates-update-face.cpp
@@ -0,0 +1,266 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014, Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology,
+ * The University of Memphis
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD 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
+ * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "rib/rib.hpp"
+
+#include "tests/test-common.hpp"
+#include "fib-updates-common.hpp"
+
+namespace nfd {
+namespace rib {
+namespace tests {
+
+BOOST_FIXTURE_TEST_SUITE(FibUpdates, FibUpdatesFixture)
+
+BOOST_AUTO_TEST_SUITE(UpdateFace)
+
+BOOST_AUTO_TEST_CASE(TurnOffChildInheritLowerCost)
+{
+ insertFaceEntry("/", 1, 0, 50, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a", 2, 0, 10, 0);
+ insertFaceEntry("/", 1, 128, 25, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 2 updates: 1 to update the cost of / face 1 to 50 and
+ // 1 to update the cost of /a face 1 to 50
+ insertFaceEntry("/", 1, 128, 75, 0);
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 2);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 50);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+
+ ++update;
+ BOOST_CHECK_EQUAL((*update)->name, "/a");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 50);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_CASE(UpdateOnLowerCostOnly)
+{
+ insertFaceEntry("/", 1, 0, 50, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a", 2, 0, 10, 0);
+ insertFaceEntry("/", 1, 128, 100, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 0 updates
+ insertFaceEntry("/", 1, 128, 75, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 0);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 2 updates
+ insertFaceEntry("/", 1, 128, 25, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+
+ updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 2);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 25);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+
+ ++update;
+ BOOST_CHECK_EQUAL((*update)->name, "/a");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 25);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_CASE(NoChangeInCost)
+{
+ insertFaceEntry("/", 1, 0, 50, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a", 2, 0, 100, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a/b", 3, 0, 10, 0);
+ insertFaceEntry("/a/c", 4, 0, 10, ndn::nfd::ROUTE_FLAG_CAPTURE);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 0 updates
+ insertFaceEntry("/a", 2, 0, 100, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 0);
+}
+
+BOOST_AUTO_TEST_CASE(ChangeCost)
+{
+ insertFaceEntry("/", 1, 0, 50, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a", 2, 0, 100, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a/b", 3, 0, 10, 0);
+ insertFaceEntry("/a/c", 4, 0, 10, ndn::nfd::ROUTE_FLAG_CAPTURE);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Should generate 2 updates: 1 to add face2 with new cost to /a and
+ // 1 to add face2 with new cost to /a/b
+ insertFaceEntry("/a", 2, 0, 300, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 2);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/a");
+ BOOST_CHECK_EQUAL((*update)->faceId, 2);
+ BOOST_CHECK_EQUAL((*update)->cost, 300);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+
+ ++update;
+ BOOST_CHECK_EQUAL((*update)->name, "/a/b");
+ BOOST_CHECK_EQUAL((*update)->faceId, 2);
+ BOOST_CHECK_EQUAL((*update)->cost, 300);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_CASE(TurnOnChildInherit)
+{
+ insertFaceEntry("/", 1, 0, 50, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a", 2, 0, 10, 0);
+ insertFaceEntry("/a/b", 3, 0, 10, 0);
+ insertFaceEntry("/a/c", 4, 0, 10, ndn::nfd::ROUTE_FLAG_CAPTURE);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Turn on child inherit flag for the entry in /a
+ // Should generate 1 updates: 1 to add face to /a/b
+ insertFaceEntry("/a", 2, 0, 10, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 1);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/a/b");
+ BOOST_CHECK_EQUAL((*update)->faceId, 2);
+ BOOST_CHECK_EQUAL((*update)->cost, 10);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_CASE(TurnOffChildInherit)
+{
+ insertFaceEntry("/", 1, 0, 50, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a", 1, 0, 100, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a/b", 2, 0, 10, 0);
+ insertFaceEntry("/a/c", 1, 0, 25, 0);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Turn off child inherit flag for the entry in /a
+ // Should generate 1 update: 1 to add face1 to /a/b
+ insertFaceEntry("/a", 1, 0, 100, 0);
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 1);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/a/b");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 50);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_CASE(TurnOnCapture)
+{
+ insertFaceEntry("/", 1, 0, 50, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a", 2, 0, 10, 0);
+ insertFaceEntry("/a/b", 3, 0, 10, 0);
+ insertFaceEntry("/a/c", 1, 0, 10, 0);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Turn on capture flag for the entry in /a
+ // Should generate 2 updates: 1 to remove face1 from /a and
+ // 1 to remove face1 from /a/b
+ insertFaceEntry("/a", 2, 0, 10, ndn::nfd::ROUTE_FLAG_CAPTURE);
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 2);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/a");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::REMOVE_NEXTHOP);
+
+ ++update;
+ BOOST_CHECK_EQUAL((*update)->name, "/a/b");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::REMOVE_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_CASE(TurnOffCapture)
+{
+ insertFaceEntry("/", 1, 0, 50, ndn::nfd::ROUTE_FLAG_CHILD_INHERIT);
+ insertFaceEntry("/a", 2, 0, 10, ndn::nfd::ROUTE_FLAG_CAPTURE);
+ insertFaceEntry("/a/b", 3, 0, 10, 0);
+ insertFaceEntry("/a/c", 1, 0, 10, 0);
+
+ // Clear updates generated from previous insertions
+ rib.clearFibUpdates();
+
+ // Turn off capture flag for the entry in /a
+ // Should generate 2 updates: 1 to add face1 to /a and
+ // 1 to add face1 to /a/b
+ insertFaceEntry("/a", 2, 0, 10, 0);
+
+ Rib::FibUpdateList updates = getSortedFibUpdates();
+ BOOST_REQUIRE_EQUAL(updates.size(), 2);
+
+ Rib::FibUpdateList::const_iterator update = updates.begin();
+ BOOST_CHECK_EQUAL((*update)->name, "/a");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 50);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+
+ ++update;
+ BOOST_CHECK_EQUAL((*update)->name, "/a/b");
+ BOOST_CHECK_EQUAL((*update)->faceId, 1);
+ BOOST_CHECK_EQUAL((*update)->cost, 50);
+ BOOST_CHECK_EQUAL((*update)->action, FibUpdate::ADD_NEXTHOP);
+}
+
+BOOST_AUTO_TEST_SUITE_END() // UpdateFace
+
+BOOST_AUTO_TEST_SUITE_END() // FibUpdates
+
+} // namespace tests
+} // namespace rib
+} // namespace nfd
diff --git a/tests/rib/rib.cpp b/tests/rib/rib.cpp
index c3b0eab..2ee3070 100644
--- a/tests/rib/rib.cpp
+++ b/tests/rib/rib.cpp
@@ -63,7 +63,7 @@
BOOST_CHECK_EQUAL(entry.eraseFace(face1), false);
}
-BOOST_AUTO_TEST_CASE(Rib_Parent)
+BOOST_AUTO_TEST_CASE(Parent)
{
rib::Rib rib;
@@ -104,7 +104,7 @@
BOOST_CHECK(ribEntry->getFaces().front().faceId == 2);
}
-BOOST_AUTO_TEST_CASE(Rib_Children)
+BOOST_AUTO_TEST_CASE(Children)
{
rib::Rib rib;
@@ -150,7 +150,7 @@
BOOST_CHECK_EQUAL((rib.find(name3)->second)->getParent()->getName(), name4);
}
-BOOST_AUTO_TEST_CASE(Rib_EraseFace)
+BOOST_AUTO_TEST_CASE(EraseFace)
{
rib::Rib rib;
@@ -195,7 +195,7 @@
rib.erase(name4, entry4);
}
-BOOST_AUTO_TEST_CASE(Rib_EraseRibEntry)
+BOOST_AUTO_TEST_CASE(EraseRibEntry)
{
rib::Rib rib;
@@ -229,7 +229,7 @@
BOOST_CHECK(ribEntry3->getParent() == ribEntry1);
}
-BOOST_AUTO_TEST_CASE(Rib_EraseByFaceId)
+BOOST_AUTO_TEST_CASE(EraseByFaceId)
{
rib::Rib rib;